Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
質より量に学ぶ - Radium Software
Coding Horror - Quantity Always Trumps Quality Art & Fear という芸術家向けの本の中に，こんなエピソードがある ― ある陶芸クラスでのこと，最初の授業において，教師は生徒をふたつのグループに分けた。一方のグループは作品の「量」によって評価を行うとし，もう一方のグループは作品の「質」によって評価を行うとした。 これはどういうことかというと，「量」グループの生徒たちは，提出した作品の量のみによって評価が下される。作品の総重量が５０ポンドに達していたらＡ評価，４０ポンド台ならＢ評価，というように。それに対して「質」グループの生徒たちは，たったひとつの最高の作品を提出すればいい。その作品の出来に対して評価が下される。 すべての授業が終わり，さて評価は，となったとき，少し奇妙な事実が判明した。提出された作品のうち，最も高い質を持つものは，すべて
YAML 1.2 - Radium Software
YAML 1.2 Ensconces and Envelopes JSON - hackety.org why さんより YAML ワーキングドラフト 1.2 のお知らせ。 YAML 1.2 の目玉は JSON との互換性が正式にサポートされていること。 JSON は YAML のサブセットという扱いになって，すなわち YAML 1.2 に対応すれば自動的に JSON 対応にもなるという美味しい話。 ところで， YAML って使ったことある？ Ruby 界隈では比較的出番が多いのかな。個人的には，数年前に XML の代替物を探していたとき，はじめて YAML と出合った記憶がある。その頃はまだマイナーな存在で，サポートの弱さを理由に導入を見送ったんだ。今ならどうかな……。 それにしても，いつのまに XML はこんなにも冴えない存在になってしまったんだろう。 YAML は「human-rea
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
