Rubyのハッシュと配列の検索速度の違い

Ruby(1.8.6)で大量のデータを検索することがあったので、ハッシュと配列の検索速度はどのくらい違うのかを検証してみた。

検証用コード

※面倒なので変数名とか超適当にした。

# compare_hash_speed_with_array.rb
  1 #!/usr/local/bin/ruby
  2 n = 120000
  3 
  4 a = {}
  5 t1 = Time.now
  6 n.times do |t|
  7   a.update(t * 10000 + t  => t + 123456)
  8 end
  9 t2 = Time.now
 10 p "#{t2 - t1} sec for making hash sample"
 11 
 12 b = []
 13 t3 = Time.now
 14 n.times do |t|
 15   b << [t * 10000 + t, t + 123456]
 16 end
 17 t4 = Time.now
 18 p "#{t4 - t3} sec for making array sample"
 19 
 20 t5 = Time.now
 21 n.times do |t|
 22   a[t * 10000 + t]
 23 end
 24 t6 = Time.now
 25 p "#{t6 - t5} sec by hash"
 26 
 27 t7 = Time.now
 28 n.times do |t|
 29   b.assoc(t * 10000 + t)[1]  #assocメソッドは、配列の配列を連想配列のように扱い、キーに対応する配列を取り出す。
 30 end
 31 t8 = Time.now
 32 p "#{t8 - t7} sec by array using assoc"
 33 
 34 t9 = Time.now
 35 n.times do |t|
 36   b[t][1]  #格納される場所を知っている場合。
 37 end
 38 t10 = Time.now
 39 p "#{t10 - t9} sec by array"

結果

# 作成速度
"0.31359 sec for making hash sample"
"0.157614 sec for making array sample"

# 検索速度
"0.114167 sec by hash"
"1179.130342 sec by array using assoc"
"0.07597 sec by array"

ハッシュと配列のassocを使ってキーの値を探した場合、ハッシュの方が圧倒的に速い。約10,000倍違う。
しかし、arrayの値の場所を知っている場合、arrayの方がハッシュより2倍速い。
ちなみに、作成はハッシュが遅い。

Rubyのハッシュテーブルの仕組みを徹底的に理解する - ザリガニが見ていた...。によると、
Rubyのハッシュは、チェイン法を用いている。
※チェイン法に関しては、http://www.geocities.jp/ky_webid/algorithm/014.htmlが参考になる。
簡単に言うと、

• データを格納する位置を、ある計算によって求め、計算の元となる数(キー)の値をデータの格納位置と直接関連付ける。
  • キーの値を格納位置に変換するために使う計算式を、ハッシュ関数と呼ぶ。
  • ハッシュ関数が返す値（これが格納位置になっている）をハッシュ値と呼ぶ。
  • データを格納する配列をハッシュ表と呼び、その各要素をバケットと呼ぶ。
• 格納するデータは、キーとセットになっていて、このキーをハッシュ関数に渡して、格納位置を決定し、その位置へデータを格納する。

これから以下のことがわかった（推測を含む）。

• ハッシュを作ったとき、格納する位置を計算によって決めているので、中の順番はパッと見、バラバラになる。
• ハッシュは格納するときに処理を行っているので、作成に時間がかかる。
• 格納される場所がわかっているので、ハッシュは速い。
• 配列の場合、値が格納されている場所を知っていれば、ハッシュよりも場所を特定するのに時間がかからないので、ハッシュよりも速く値を取得できる。

ハッシュの中の順番に関しては、例えば、

a = {}
100.times do |t|
  a.update(t=>t)
end

としたとき、aの値は、

{85 => 85, 66 => 66, 9 => 9, 47 => 47, 28 => 28, 95 => 95,・・・・}

となる。

ちゃんと理解するには、Rubyソースコード完全解説とかを参考にしつつ、ソースコードをちゃんと読む必要があるが、とりあえず感覚的に理解した。

オススメ書籍

作りながら学ぶRuby入門 第2版

プログラミング初心者がRubyを学ぶのにオススメ。
言語を学ぶのは文法から入るより実践から入ったほうがよいというのがよくわかる。

初めてのRuby

プログラミング中級者がRubyを学ぶのにオススメ。
Rubyのポイントがシンプルにまとめられていて、Rubyへの理解が深まる。

お読み頂きありがとうございます。
もしブログの内容を気に入って頂けましたら、RSSリーダーの登録よろしくお願いします。
twitter@kbktもやってます。IT系の最新情報やライフハック情報をよくつぶやいています。よろしければフォローしてください。

　　


◆◆このブログのサイトマップへ◆◆