hash vs. bloomfilter

ruby

最近仕事でも ruby をぼちぼちと使い始めているのだけど、お手軽に結果をみているフェーズでは良いとして、大規模なデータを扱うようになるとどうしても速度とメモリの問題にぶつかってしまう。これは perl などの他のLLを使ってももちろん同じで、C だとしてもナイーブな実装だと速度が多少向上することはあってもメモリの問題は根本的に変わらない。例えば、レコード数が大きいデータを読み込み、異なる tuple がいくつ出現したかを数え上げる問題があったとして、ナイーブな実装だと下記のようにすればカウントはできる。

#!/usr/bin/env ruby
hash = Hash.new
while line = ARGF.gets
  if !hash.key?(line)
    hash[line] = 1
  end
end
print "#distinct elements=#{hash.length}\n"

しかしこれをやってしまうと少なくとも tupleのサイズ ×レコード数のメモリ量が必要になることと、新たなレコードが既にカウントした tuple であるか否かをチェックするための処理が、読み込みレコード数が増えるとともに非線形に増大してしまうという問題がある。Ruby での Hash の実装がどうなっているかは知らないのだけど、探索の部分は色々と工夫されているにしても、必要メモリ量に関しては少なくとも (key, value) x レコード数を消費していると思われる([要出典])。今直面している問題は、上記の問題をもう少し複雑にしたものなのだけど、要はメモリ消費量がボトルネックになってしまっているので、なんとかしたいところ。

ところでこの手のカウントをするのに、ある程度の誤差が許されるのであれば、ハッシュ関数を使って確率的にカウントするというアルゴリズムがいくつか提案されているので、それを使うという手がある。という話は上記の問題とは別に進めている仕事に密接に関係していたりするのだけど、それはさておき、よく知られたアルゴリズムで Bloom Filter というのがある。これは新規エントリーであるか否かを複数のハッシュ関数を使って高速に調べる方法なのだけど、速度の面ならず、メモリ量の観点でも tuple のサイズに関係なく1レコードに対応する情報が 1 x K ビットに圧縮されるので、とても効率が良い。トレードオフは原理的に false positive があるということで（ただし false negative はない）、tuple に対して同時にかけるハッシュ関数の数 K を増やす事で false positive は減る。

というわけで(?)、Bloom Filter の Ruby 版実装である pbloomfilter というのががあったので、どれだけ使えるものか試してみる事にした。
・・・のだけど、Bitset というビット演算を行うCの外部ライブラリを使っているのにも関わらずどうも速度が出ず、上記のナイーブな方法の方がまだ速いという結果になってしまった。

#!/usr/bin/env ruby
require 'bloomfilter'
bf = BloomFilter.new(10000,0.1) # m=10000, fp=10%
num = 0
while line=ARGF.gets
  if !bf.has?(line)
    num += 1
    bf.insert(line)
  end
end
print "#distinct elements = #{num}\n"

という bloomfilter のコードを用意し、最大エントリー数を 10,000 として、false-positive を 10% にすると（それに見合った K をライブラリが自動的に算出してくれる）以下のような結果になった。

% time ruby hash-distinct.rb hoge.dat                         
#element = 10000
ruby hash-distinct.rb hoge.dat  0.04s user 0.01s system 94% cpu 0.047 total
% time ruby bf.rb hoge.dat
#element = 9692
ruby bf.rb hoge.dat  2.26s user 0.03s system 98% cpu 2.322 total

うーむ・・・。メモリ消費量の観点では bloom filter が優れている点は確認できたのだけど、どうにもこうにも速度が遅くて仕方がない。しかもこの傾向はレコード数を増やすほど顕著になってしまい、100万オーダーのデータだと数分たっても結果が返ってこないので強制終了してしまった。元のコードをあたってないので原因はまだよくわからないのだけど、既エントリのメンバであるかをチェックするのに(has?の部分)時間がかかっているようにみえる。深追いはまた別の機会にやるとして、当面別の方法を使わないと仕事が進まないなぁ・・・。かといって今更Cに戻すのはなんだかなぁという気分なのでどうしたものか。