解説 6月7日A

今回の学習項目です。


Rubyのハッシュ

前回はハッシュ法を学びました。これはメモリを多く使うけれども、探索がO(1)と、とても早くできるデータ構造でした。

私たちが学んできたRubyでは、組み込みクラスとしてハッシュを使うことができます。 今日の講義ではRubyでのハッシュの使い方やその応用について学びます。

配列とハッシュ

Rubyではハッシュテーブルは「連想配列」とも呼ばれている。そう呼ばれる理由は次のとおり: 配列では数が指標として要素を取り出す(例えば、aが配列として3を指標とするとa[3]で要素を取り出す)。 それに対しハッシュテーブルでは、数も文字列もキーとして使え、それを手がかりにして要素を取り出すからである。例えばhをハッシュとすると、数5をキーとした場合h[5]、文字列"abc"をキーとした場合 h["abc"]により要素が返される。

配列と比較してRubyにおけるハッシュテーブルの使い方を説明する:

a = Array.new       # 空っぽの配列を作る
                     h = Hash.new         # 空っぽのハッシュテーブルを作る
a = [5, 10, "abc"]   # 指標0,1,2にそれぞれ5,10,"abc"という要素を持つ配列を作る
                h = {0 => 5, "xyz" => "abc"}   # キー0に対して5、キー"xyz"に対して"abc"を値とするハッシュテーブルを作る
p a[3]       # 配列aにおける指標3の要素を取り出して表示する
                     p h[0]          # キーを0としてハッシュhに格納された要素を取り出す
                     p h["xyz"]      # キーを"xyz"としてハッシュhに格納された要素を取り出す
a[1] = "xyz"       # 配列aの指標1の要素として"xyz"を格納する
                     h[3] = "xyz"        # キーを3としてハッシュhに"xyz"を格納する
                     h["abc"] = "xyz"    # キーを"abc"としてハッシュhに"xyz"を格納する

Rubyでは配列(仮にaとする)の要素数より大きな数(仮にnとする)を指標としたa[n]はエラーではなくnilを返すように、ハッシュテーブル(仮にhとする)も登録されていないキー(仮に"x"とする)に対して(つまりh[x]は)エラーではなく(デフォルトでは)nilを返す。

課題1

課題1-1から課題1-5までを通して、教科書の課題4.4(p.45)を解くプログラムを作って走らせ、結果を報告せよ。

課題1-1

正の整数(n)を引数とする関数gen(n)を作る。ただし、この関数は、 乱数関数randを用いて、0以上100万以下の整数をn個生成し、それを要素とする配列を 返すものとする。以下はgen(10)を実行した結果の例である:
[902177, 381988, 840846, 385628, 252504, 425694, 4589, 583681, 88039, 521113]

課題1-2

課題1-3

0以上の整数を要素とする配列(ar)を引数とする関数checkA(ar)を作る。 ただし、この関数はまず空の配列(box)を作り、カウンタとして使う変数(名前をc)に初期値として0を与える。 次にarの要素を一つずつ取り出し(その値をnとする)、 「box[n]がnilならばtrueに値を書き換え、cの値を1増やす」ということを繰り返す。 最後にcの値を返す。

そして課題1-1で作成した関数genを用いて以下を実行し、どのような結果を返したかと、 どのくらい時間がかかったかを報告せよ。

for i in [10,100,1000,10000,100000,200000,500000,800000,1000000]
  print i," => ",checkA(gen(i)),"\n"
end
その結果はおよそ以下のようになるだろう(乱数を使っているため、数は必ずしも一致しない)
10 => 10
100 => 100
1000 => 999
10000 => 9940
100000 => 95187
200000 => 181393
500000 => 393000
800000 => 550641
1000000 => 632176

課題1-4

課題1-3で作成した関数checkAは「何を調べるものか」、言い換えればこの関数が返した値はどのような意味を持つものなのか、説明せよ。

課題1-5

課題1-3で作ったものとほぼ同じ関数checkH(ar)を作る。 この関数と関数checkAとの違いは、checkAでは配列boxを使っていたのに対して、 checkH(ar)ではハッシュテーブル(名前をhとする)を使うということである。

具体的に書けば以下のとおり: この関数はまず空のハッシュ(h)を作り、カウンタとして使う変数(名前をc)に初期値として0を与える。 次にarの要素を一つずつ取り出し(その値をnとする)、 「h[n]がnilならばtrueに値を書き換え、cの値を1増やす」ということを繰り返す。 最後にcの値を返す。

そして課題1-1で作成した関数genを用いて以下を実行し、どのような結果を返したかと、 どのくらい時間がかかったかを報告せよ。

for i in [10,100,1000,10000,100000,200000,500000,800000,1000000]
  print i," => ",checkH(gen(i)),"\n"
end

課題1-6

checkXとcheckHではどちらが時間がかかっただろうか。n=1000とするとどのくらい差があると考えられるか。またその理由はどうしてだろうか、説明せよ。

課題2-1

nekos.txtにはいろいろな種類の猫が多数書かれている。ハッシュを用いて、(1)何種類の猫が、(2)それぞれ何回現れているか、を求めるプログラムを書き、実行して結果を答えよ。
[ヒント]
ファイルから行を読み込み、splitを使って単語に分ける。 そして、それぞれの単語をキーとし、出現回数を値としてハッシュ(仮にhとする)に書きこむ。 ある単語(仮にxとする)がはじめて現れる場合、ハッシュの値(h[x])としてはnilが返されるはずなので、そのときに h[1]=1 とすること。何種類の猫がいるかは、keysを使うか、猫の名前を記録するために配列(仮にnekosとする)を用意しておき、初めてその猫が現れたときにnekos << xとすればよい。
[keys]
Rubyのハッシュは、どのようなキーが使われたかを記憶している。 ハッシュの名前をhとすると、そのハッシュで使われたキーは、h.keys でとりだせます。次を走らせて確かめてみてください。
h = Hash.new
h["abc"] = 3
h[10] = 1
h["x"] = "yz"
p h.keys  # hのキーの配列が表示される

「アルゴリズムとデータ構造」のホームに戻る