ハッシュの宣言方法による実行速度の違いについて

Question

こんにちは、いつもお世話になっております。

今、コンパイラを学ぶにあたり、RubyによるC言語の字句解析器を試しに作成しているのですが、そのコードの中で、標準入力から取得した文字列が、C言語の予約語(if,return等)に当てはまるか否かのチェックを、ハッシュで行うようにしました。
その理由としては、配列の場合だと、==演算を最大で配列のサイズ分行うことになってしまい、実行速度が遅くなると思ったので、取得した文字列をハッシュ演算にかけることで、要素のアドレスを直で得ることができるハッシュを使うことにしました。(ハッシュの理解が間違っていたら申し訳ございません。)

今回質問させていただきたいことは、ハッシュのキーと要素のクラスを文字列とシンボルで入れ替えた場合、実行速度はどうなるかということです。
調べたところ、ハッシュではシンボルを利用したほうが実行速度が速いと一般的に言われていますが、では、ハッシュの中のキーと要素のどちらにシンボルを利用したほうが速いのだろうかと思った次第です。(なお、調べた例では、キーにシンボルを利用していることが多かった。)

以下試しに書いたコードです。
ex7alt.rbはキーがシンボル、値が文字列です。
ex7alt2.rbはキーが文字列、値がシンボルです。
また、一応呼び出しにかかる時間も計測してみました。

ex7alt.rb

# coding: utf-8
require 'benchmark'
reserved_words={auto:"auto", break:"break", case:"case", char:"char", const:"const", continue:"continue", default:"default", double:"double", do:"do", else:"else", enum:"enum", extern:"extern", float:"float", for:"for", goto:"goto", if:"if", int:"int", long:"long", register:"register", return:"return", short:"short", signed:"signed", sizeof:"sizeof", static:"static", struct:"struct", switch:"switch", typedef:"typedef", union:"union", unsigned:"unsigned", void:"void", volatile:"volatile", while:"while"}

print "input a line: "
while line=gets do
  until line.empty? do
    case line
    when /\A\s+/
    when /\A([0-9]+)/
      puts "number (#{$1})"
    when /\A([_a-zA-Z]\w*)/
      word = $1.to_sym
      result = Benchmark.realtime do
        if reserved_words[word]
          puts "reserved words (#{$1})"
        else
          puts "identifier (#{$1})"
        end
      end
      puts "所要時間 #{result}s"
    when /\A(\S)/
      puts "other (#{$1})"
    end
    line = $'.to_s
  end
end

ex7alt2.rb

# coding: utf-8
require 'benchmark'
reserved_words={"auto"=>:auto, "break"=>:break, "case"=>:case, "char"=>:char, "const"=>:const, "continue"=>:continue, "default"=>:default, "double"=>:double, "do"=>:do, "else"=>:else, "enum"=>:enum, "extern"=>:extern, "float"=>:float, "for"=>:for, "goto"=>:goto, "if"=>:if, "int"=>:int, "long"=>:long, "register"=>:register, "return"=>:return, "short"=>:short, "signed"=>:signed, "sizeof"=>:sizeof, "static"=>:static, "struct"=>:struct, "switch"=>:switch, "typedef"=>:typedef, "union"=>:union, "unsigned"=>:unsigned, "void"=>:void, "volatile"=>:volatile, "while"=>:while}

print "input a line=> "
while line=gets do
  until line.empty? do
    case line
    when /\A\s+/
    when /\A([0-9]+)/
      puts "number (#{$1})"
    when /\A([_a-zA-Z]\w*)/
      result = Benchmark.realtime do
        if reserved_words[$1]
          puts "reserved words (#{$1})"
        else
          puts "identifier (#{$1})"
        end
      end
      puts "所要時間 #{result}s"
    when /\A(\S)/
      puts "other (#{$1})"
    end
    line = $'.to_s
  end
end

入力には下のテキストファイルを使用しました。
sample.txt

return
if
double
int
unsigned
while

実行結果

実行して見たところ、余り大差はないように見えますが、すこしだけ、シンボルをキーとしたときのほうが速いように見えます。しかし、どうしてこのような結果となるのかがわかりません。
もし、このような実行結果となる要因や、ハッシュのキーと要素のクラスを文字列とシンボルで入れ替えた場合、実行速度はどうなるかということについて、ご存じの方がいらっしゃいましたら教えていただけたら幸いです。

Answer 1

reserved_words[$1]
でなく、

keys = reserved_words.keys
keys.include?[$1]

とした場合も計測をしてみては？

時間計測は 1万回レベルの呼び出しをするとよいです。(計測結果が 数分を超える程度にしておかないと、速度差を抽出しにくいから)

1万個の単語の text を用意するか、 １０００ 単語の text 処理を 10 回繰り返すとか。
そして、プロブラム全体処理り時間を計測します。(無駄な puts は削除しておくこと)

行単位で、実機雨回数、処理時間を計測する方法もあります。

• Rubyで処理が遅い行を特定する方法

https://rooter.jp/programming/rblineprof/

こういったツールもつかうと良いです。

Answer 2

計測内でputsしてるので、putsの時間に比べてハッシュを引く時間が無視できる程度なんだと思いま
す。

計測内では結果を変数に入れるだけにして、putsは計測外に出してみてください。

      flag = nil
      result = Benchmark.realtime do
        flag = reserved_words[$1]
      end
      if flag
        puts "reserved words (#{$1})"
      else
        puts "identifier (#{$1})"
      end

Comments

[otn]

あと、「文字列→ハッシュ値」の変換と「文字列→シンボル→ハッシュ値」の変換だと、当然前者が速いので、ハッシュを引くのがこのときだけならシンボル化する意味は無いです。

[witchy]

otnさんいつもありがとうございます。
otnさんに教えていただいたころを試したところ、ex7alt.rb(シンボル->ハッシュ値)のほうが二倍程度処理が速いという結果になりました。追記していただいたことはごもっともです。文字列->シンボルと変換した場合は、先ほどの結果と逆になりました。
実装の上では、処理時間も全く気にならないですし、またシンボル化の処理を挟むとかえって遅くなるので、単純に文字列からハッシュをひこうと思います。しかし、文字列->ハッシュ値よりもシンボル->ハッシュ値のほうが速いというのは、実験としては面白く感じました。
また、何故このような結果になったのか、ハッシュの原理、シンボルの原理等、もう少し勉強してみようと思います。ご回答いただき有り難うございました。

[otn]

リファレンスマニュアルの下記が参考になります。

シンボルの実装と用途
実装

Rubyの内部実装では、メソッド名や変数名、定数名、クラス名など の`名前'を整数で管理しています。これは名前を直接文字列として処理するよりも 速度面で有利だからです。そしてその整数をRubyのコード上で表現したものがシンボルです。

シンボルは、ソース上では文字列のように見え、内部では整数として扱われる、両者を仲立ちするような存在です。

Answer 3

word = $1.to_sym

単語をシンボルに変換する分のコストをベンチマークに入れてないからです。

---

他に、setライブラリを使うという方法もあります。

reserved_words = Set.new(%w[auto break case char const continue default double do else
  enum extern float for goto if int long register return short signed sizeof static
  struct switch typedef union unsigned void volatile while])
reserved_words.include?("return") # => true

まぁ、内部的にはHashなので文字列キーのハッシュと大差ありませんし速度的には微妙に負けますが
そこまでの速度を求めるならばRubyを使うこと自体をやめた方が速度は出るので
どちらが書いてて楽しいor読みやすいかで選択するとよいでしょう。

Comments

[asm]

ちなみに昔書いたやつ
https://teratail.com/questions/140136

今回の場合は、入力された文字列からキーを検索するので文字列キーの方が適しています

[witchy]

asmさんこの間に引き続きありがとうございます。
なるほど、teratailに過去の質問があったのですね。ググラビリティが低くお恥ずかしい限りです。もう少し調べれば、自己解決できたかもしれないと思うと悔しいです...
過去の質問でasmさんがおっしゃっていた場合がまさにこの場合なのですね。シンボルをキーとした場合のハッシュの短縮記法はこのコード書くときとても楽に感じました。ですが、asmさんがおっしゃったとおり、実装面では文字列->シンボルの変換の処理時間を加味すると、文字列->ハッシュ値のほうが早かったので、単純に文字列からハッシュをひこうと思います。ただ純粋に文字列またはシンボルからハッシュ値を求める時間を比べると、過去の質問者や、https://melborne.github.io/2008/08/02/Ruby/の記事にある内容から、シンボルのほうがハッシュのキーに適しているのですね。otnさんの指摘からコードを修正し、実験した結果もシンボルのほうが安定して２倍近く速かったです。
また、Set、Sortedライブラリも試してみようと思います。配列とハッシュ以外にもこんなクラスがあるとは知りませんでした。勉強になります!
本当にご回答頂きありがとうございました！！