質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

Q&A

解決済

3回答

1284閲覧

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

witchy

総合スコア74

Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

0グッド

0クリップ

投稿2019/05/29 09:13

編集2019/05/29 09:25

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

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

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

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

ex7alt.rb

Ruby

1# coding: utf-8 2require 'benchmark' 3reserved_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"} 4 5print "input a line: " 6while line=gets do 7 until line.empty? do 8 case line 9 when /\A\s+/ 10 when /\A([0-9]+)/ 11 puts "number (#{$1})" 12 when /\A([_a-zA-Z]\w*)/ 13 word = $1.to_sym 14 result = Benchmark.realtime do 15 if reserved_words[word] 16 puts "reserved words (#{$1})" 17 else 18 puts "identifier (#{$1})" 19 end 20 end 21 puts "所要時間 #{result}s" 22 when /\A(\S)/ 23 puts "other (#{$1})" 24 end 25 line = $'.to_s 26 end 27end

ex7alt2.rb

Ruby

1# coding: utf-8 2require 'benchmark' 3reserved_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} 4 5print "input a line=> " 6while line=gets do 7 until line.empty? do 8 case line 9 when /\A\s+/ 10 when /\A([0-9]+)/ 11 puts "number (#{$1})" 12 when /\A([_a-zA-Z]\w*)/ 13 result = Benchmark.realtime do 14 if reserved_words[$1] 15 puts "reserved words (#{$1})" 16 else 17 puts "identifier (#{$1})" 18 end 19 end 20 puts "所要時間 #{result}s" 21 when /\A(\S)/ 22 puts "other (#{$1})" 23 end 24 line = $'.to_s 25 end 26end

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

text

1return 2if 3double 4int 5unsigned 6while

実行結果
イメージ説明
イメージ説明

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

reserved_words[$1]
でなく、

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

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

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

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

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

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

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

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

投稿2019/05/29 21:31

katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

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

Ruby

1 flag = nil 2 result = Benchmark.realtime do 3 flag = reserved_words[$1] 4 end 5 if flag 6 puts "reserved words (#{$1})" 7 else 8 puts "identifier (#{$1})" 9 end

投稿2019/05/29 12:30

otn

総合スコア84421

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

otn

2019/05/29 12:51

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

2019/05/29 16:32

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

2019/05/30 14:07

リファレンスマニュアルの下記が参考になります。 シンボルの実装と用途 実装 Rubyの内部実装では、メソッド名や変数名、定数名、クラス名など の`名前'を整数で管理しています。これは名前を直接文字列として処理するよりも 速度面で有利だからです。そしてその整数をRubyのコード上で表現したものがシンボルです。 シンボルは、ソース上では文字列のように見え、内部では整数として扱われる、両者を仲立ちするような存在です。
guest

0

ベストアンサー

word = $1.to_sym

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


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

ruby

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

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

投稿2019/05/29 10:38

asm

総合スコア15147

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

asm

2019/05/29 10:46

ちなみに昔書いたやつ https://teratail.com/questions/140136 今回の場合は、入力された文字列からキーを検索するので文字列キーの方が適しています
witchy

2019/05/29 16:56

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問