Cuckoo HashingをRubyで作る(その2)
Rubyの標準ライブラリのうちRubyで書いてあるもののトークンの数を数えるプログラムでいろいろCuckoo Hashingの挙動を調べてみました。
組み込みのHashを使うものと、Cuckoo Hashingのもののベンチマークを取ってみました。
トークンの切り出しにかなり時間が掛かるので、トークンの切り出しだけを行う処理の時間も測りました。
user system total real ScanOnly 57.046000 1.546000 58.592000 ( 59.649000) Hash 65.328000 1.750000 67.078000 ( 67.651000) Cukoo 92.937000 1.719000 94.656000 ( 95.439000)
それぞれScanOnlyの分を引くと次のようになります。
user real Hash 8.282000 ( 8.002000) Cukoo 35.891000 ( 35.790000)
userの方が、realより大きいのはおかしいですが、誤差の範囲だと思います。Rubyで書いたものがCで書いたものの4倍強で収まるということで、この問題に対してはCuckoo Hashingは有効じゃないかと思います。
もっとも、切り出したトークンは4,269,036個で60,946種類です。挿入処理が入る確率が1.417% とかなりCukoo Hashingに有利な条件です。
トークンを数える問題について、ハッシュバケットの使用率をいろいろハッシュ関数を替えて調べてみたのですが、どの関数もTable1が60% 前後、Table2が40%前後でした。Table2が使用率の足を引っ張っているようなので、Table1とTable2でサイズを変えてみるといいような気がします。
ベンチマークのリストです
require 'find' require 'ripper' require 'benchmark' require 'cuckoo' def token_scan Find.find('c:/cygwin/usr/local/lib/ruby/') do |f| if File.file?(f) and /\.rb$/ =~ f then Ripper.tokenize(File.read(f)).each do |token| end end end end def token_count(table) tot = 0 uni = 0 Find.find('c:/cygwin/usr/local/lib/ruby/') do |f| if File.file?(f) and /\.rb$/ =~ f then Ripper.tokenize(File.read(f)).each do |token| if table[token] == nil table[token] = 0 end table[token] += 1 end end end end Benchmark.bm(9) do |x| x.report("ScanOnly "){ token_scan} x.report("Hash "){ token_count(Hash.new)} x.report("Cukoo"){ token_count(CuckooHash.new)} end