Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
Rubyの拡張ライブラリを作ってみよう！ - ser1zw's blog
はじめに Ruby Advent Calendar jp: 2011 : ATNDの17日目の記事です。昨日は@yoppiblogさんのSeleniumの自動テストをCI環境(Jenkins)で快適に実施するでした。 Rubyを使ってて 遅い…ここだけ超遅い… とか あのライブラリが使いたい！でもRuby用のライブラリじゃないし… みたいなこと、ありますよね？ そんなとき、Rubyの拡張ライブラリで解決できるかもしれません。 Rubyの拡張ライブラリは、普通のライブラリと異なりC(とかC++とかその他の言語とか)で作成します。そのため、Rubyで直接書くよりも高速に処理できたり、Cのインタフェースが用意されているライブラリをRubyから呼びだしたりすることができます。すばらしい！ そんなわけで、拡張ライブラリの作り方をざっくり説明したいと思います。 用意するもの Cコンパイラとかmakeと
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
