おもこん

おもこんは「思いつくままにコンピュターの話し」の省略形です

徒然Ruby（８）シンボルとハッシュ

Ruby

（追記）ハッシュをシンボルテーブルに使う例を追加しました（2022/9/20）

今回はシンボルとハッシュについて説明します。

Rubyのドキュメントには、シンボルについて次のように書かれています。

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

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

この説明を理解するには、一般にプログラム言語が変数などをどのように管理しているかを、おおまかにでも理解する必要があります。

シンボルテーブル

ここでは非常に簡単なプログラム言語を考え、変数をどう扱えば良いかを考えてみます。 この言語は名前を「mini」ということにします。

  • 変数はアルファベットの並びとする。 「abc」「hello」などは変数とすることができる。 「abc1」は数字が含まれるので変数にはならない
  • 変数には正の整数を代入できる。 「abc = 100」のように「変数 = 正の整数」の形で代入文を表す
  • 変数を表示することができる。 「print abc」のように「print 変数」の形で変数に代入されていた正整数を表示する。 このとき、改行も出力する
  • 空行や空白のみからなる行は無視する

この言語のプログラムは例えば次のようなものです。

abc = 100
efg = 50
print abc
print efg

abc = 200
print abc

このプログラムを実行すると

100
50
200

と表示されます。

では、miniは変数をどのように扱うのでしょうか？ プログラムの各行に対するminiの動作は次のようになります。

  • 1: 「abcという名前の変数は100を値に持つ」ことを記録する
  • 2: 「efgという名前の変数は50を値に持つ」ことを記録する
  • 3: 記録から変数abcを探し、その値を出力する（表示する）
  • 4: 記録から変数efgを探し、その値を出力する
  • 5: 空行なので無視して、次の行に進む
  • 6: 変数abcは記録済みである。その変数の値を200に変更する
  • 7: 記録から変数abcを探し、その値を出力する

このことから、miniには変数名とその値を記録する表（table）が必要です。 この表を「シンボル・テーブル」ともいいます。

Rubyでminiを書いてみましょう。 シンボルテーブルは二重配列で表すことにします。 上の例では最終的にシンボルテーブルは

[ [ "abc", 200], [ "efg", 50 ] ]

となります。 miniのプログラムは次のようになります。

@sym_table = []

def lookup(k)
  @sym_table.each do |a|
    if a[0] == k
      return a[1]
    end
  end
  nil
end

def install (k, v)
  @sym_table.each do |a|
    if a[0] == k
      a[1] = v
      return
    end
  end
  @sym_table << [k, v]
end

File.readlines(ARGV[0]).each_with_index do |s, i|
  if /^print +(\w+)$/ =~ s
    k = $1
    v = lookup(k)
    if v
      print v, "\n"
    else
      print "Error #{k} is not defined.\n"
      exit
    end
  elsif /(\w+) *= *(\d+)$/ =~ s
    k = $1
    v = $2
    install(k, v)
  elsif /^ *$/ =~ s
    # ignore
  else 
    print "Syntax error in #{i+1}\n"
    exit
  end
end

@のつく変数がここではじめて出てきました。 この変数は「インスタンス変数」といいます。 インスタンス変数はメソッド定義の外でも内でも参照することができます。 インスタンス変数の説明はクラス定義のところでします。 @sym_tableがシンボルテーブルです。

  • lookup(k)はシンボルテーブルから名前がkの変数をさがし、その値を返す。 変数が未登録の場合はnilを返す
  • install(k, v)はシンボルテーブルに名前がkで値がvである変数を登録する。 変数が既に登録済みである場合はその値を更新する
  • each_with_indexのイテレーションでは、まず最初の引数を取り出し、その名前のファイルを行ごとに読み込んで配列にする。 その各行に対して、代入、print、空行、その他に対してそれぞれ必要なことを行う
  • 代入では、installを使って変数をシンボルテーブルに登録したり、値を更新したりする
  • printではlookupを使って変数の値を取得し、表示する
  • 空行は無視（Rubyでは#以下はコメントとして実行せず、無視します）
  • その他の場合はエラーメッセージを出す

このプログラムを動かしてみましょう。 最初に示したminiのプログラムを「mini_sample.txt」という名前で保存しておきます。

$ ruby mini.rb mini_sample.txt
100
50
200
$

期待通りに動作しました。

さて、このプログラムは動作しますが、プログラムが長くなり、変数が多くなると時間がかかるようになります。 ですから、シンボルテーブルへの登録と参照をもっと高速にするアルゴリズムが必要ですが、ここでその説明をすると長くなるので詳しいことは省略します。

シンボル

さて、mini言語の例ででてきた変数名と配列のインデックス（整数）は1対1に対応しています。

  • abcのインデックスは0
  • efgのインデックスは1

これから文字列（変数名）の代わりに整数（インデックス）を使っても良いわけです。 この整数をRubyではシンボルといいます。

ただ、Rubyの実装は上記の例とは全然違うので、例え話と考えてください。 いずれにしても「文字列と整数が1対1に対応する仕組みがあるので、文字列の代わりに整数を使っても良い」というのがシンボルのアイディアです。

シンボルの良いところは、あるシンボルと別のシンボルが同じかどうかはその整数値がイコールかどうかで判断できる、したがって「比較（イコールの判定）を高速にできる」ということです。 このように、シンボルを文字列の代わりに使うと良い面がありますが、逆もあります。 例えばシンボルの文字列を「小文字から大文字に変換する」ためには、いったんシンボルを文字列に直してからその操作を行い、得られた文字列を再びシンボルに直すので、余計な時間がかかることになります。 この場合は文字列のままで操作をするほうが合理的です。

では、シンボルを使うと良いのはどのような場面でしょうか？ Rubyのドキュメントには次のように書かれています。

実用面では、シンボルは文字の意味を明確にします。「名前」を指し示す時など、文字列そのものが必要なわけではない時に用います。

  • ハッシュのキー { :key => "value" }
  • アクセサの引数で渡すインスタンス変数名 attr_reader :name
  • メソッド引数で渡すメソッド名 __send__ :to_s
  • C の enum 的な使用 (値そのものは無視してよい場合)

シンボルを使うメリットは

  • 新しく文字列を生成しない分やや効率がよく、比較も高速。
  • 文字の意味がはっきりするのでコードが読みやすくなる
  • immutable なので内容を書き換えられる心配がない

これを現時点で完全に理解するのは難しいと思います。 一番用いられるのは、次の項で説明するハッシュのキーとしてなので、それだけでも覚えておけば十分だと思います。 通常は文字列を使っていれば良いと思います。

さて、シンボルのリテラルは3通りあります。

  • :abc
  • :'abc'
  • %s!abc!

この3つはいずれも文字列abcに対応するシンボルを表します。 最初の書き方が一番使われますが、すべての文字が使えるわけではありません。 アルファベットや数字は大丈夫ですが区切り文字の一部は使えません。 詳しくはRubyのドキュメントで確認してください。

シンボルは文字列オブジェクトと違い、同じ文字列のシンボルはオブジェクトとしても同じです。

  • "abc" == "abc" はtrue。==は異なるオブジェクトでも文字列が同じならばtrueだから
  • "abc".equal?("abc")はfalse。equal?メソッドは同じオブジェクトでなければfalseになるから。 最初の"abc"で文字列オブジェクトが作られ、2番目の"abc"で別の文字列オブジェクトが作られるから。
  • :abc == :abcはtrue。==は同じシンボルならばtrueになる（この「同じ」というのはオブジェクトとして同じと考えても、文字列として同じと考えてもよい）
  • :abc.equal?(:abc)はtrue。同じ文字列のシンボルはひとつしかないから。 最初の:abcでシンボルオブジェクトが作られ、2番目の:abcでは同じオブジェクトが参照されている。

最後に注意を述べます。 「シンボルは文字列を整数で表したもの」といいましたが、シンボル・オブジェクトは整数オブジェクトではありません。 したがって、整数のメソッドのabsなどはシンボルには使えません。 また、シンボルを整数に直すメソッドもありません。 あくまでシンボルは「文字列を表すもの」です。

ハッシュ

ハッシュは配列に似ていますが、インデックスに代わって任意のオブジェクトを用いることができます。

a = [ 10, 100, 1000 ]
h = { "ten" => 10, 100 => 100, nil => 1000 }
print a[0], "\n"
print a[1], "\n"
print a[2], "\n"
print h["ten"], "\n"
print h[100], "\n"
print h[nil], "\n"

実行すると

10
100
1000
10
100
1000

となります。 配列ではインデックスが0から始まる数字で、0番目の要素はa[0]で取り出せました。 ハッシュの場合は任意のオブジェクトに対して値が対応します。 上の例では文字列"ten"に対して整数10が対応するので、h["ten"]で10が取り出せます。

ハッシュのことを連想配列ということもあります。 ハッシュは波カッコで囲み、各要素をコンマで区切ります。 各要素は、「キー」=>「値」というパターンで記述します。

キーとなるオブジェクトにはhashとequ?の2つのメソッドが定義されていなければなりません。 Rubyのドキュメントを見ると、Stringクラス（文字列オブジェクトのクラス）にはhashメソッドがありますが、Integerクラス（整数オブジェクトのクラス）にはhashメソッドがありません。 しかし、IntegerクラスにはRubyの組み込みのhash関数が適用されるので、実はhash関数が備わっています。

hashはキーになるオブジェクトからhashメソッドを使い、そのハッシュ値（整数値）を求めて保持して、 a["tex"]を実行する時に、"tex"のhash値とそれを比較して、対応する値を返しています（おそらく）。 キーであるオブジェクトが変更可能で、変更してしまうと、値を取り出せなくなってしまいます。 （そのときはrehashするという方法がありますが）。 ですから、キーは変更不可能なオブジェクトが適しています。 なお、文字列をキーにした場合、「文字列は変更可能」で「キーは変更不可能がのぞましい」という相反する条件を解決するために「ハッシュはキー文字列をコピーし、その複製をフリーズ」します（変更不可にする）。 元の文字列は変更可能のままです。

ハッシュのキーは文字列よりもシンボルの方が適しています。

  • シンボルは元々変更不可である
  • シンボルは比較（イコールかどうか）が高速なのでハッシュの値を高速に取得できる

これより、キーをシンボルで書けるならば、そうすることが望ましいです。

h = { :ten => 10, :hundred => 100, :thousand => 1000 }

この書き方の簡略な方法として、コロンを文字列の右に書くことができます。

h = { ten: 10, hundred: 00, thousand: 000 }

矢印を省略でいるのでタイプ量も減り、効率的です。

ハッシュの例

ハッシュはユーザ管理などに使えます。 ひとりひとりのユーザをハッシュで表し、

a = {name: "山田　太郎", email: "taro@example.co.jp" }
b = {name: "鈴木　花子", email: "hanako@example.com" }

このようにハッシュにすると分かりやすくなります。 同じデータを配列にした場合、どうなるかを見てみましょう。

a = [ "山田　太郎", "taro@example.co.jp" ]
b = [ "鈴木　花子", "hanako@example.com" ]

変数aのユーザ名を表すには、

  • ハッシュならばa[:name]
  • 配列ならばa[0]

明らかにハッシュのほうが分かりやすいです。 項目が増えれば増えるほどハッシュの方に軍配があがります。

ハッシュを使ったシンボルテーブル

このセクションのはじめにシンボルテーブルを説明しました。 その例では配列でシンボルテーブルを作りましたが、これは実用上は遅く、大量の名前を処理するには向きません。 それは配列を頭から検索するのに時間がかかるからです。 そこで、シンボルをキーにしたハッシュならば時間を短縮できるのではないかと考えました。 シンボルの比較は文字列より高速だからです。

その実験として、「不思議の国のアリス」の単語の頻度を調べるプログラムを作ってみました。 ルイス・キャロルの書いた「不思議の国のアリス」（Alice's Adventures in Wonderland）は1865年刊行ですでに著作権が切れています。 そして、「プロジェクト・グーテンベルク」というウェブサイトにその電子版が掲載され、無料でダウンロードできます。 そこからプレーンテキスト版「pg28885.txt」をダウンロードして使います。 単語は、アルファベットのみからなるので、文字列メソッドのsplitを使いました。

@a = File.read("pg28885.txt").split(/[^A-Za-z]+/)
  • File.read(ファイル名)でファイルを読み込み、それを文字列にしたものを返す
  • splitメソッドは引数を区切りとして文字列を分割し、その配列を返す
  • /[^A-Za-z]+/は正規表現で、アルファベット以外の文字が1つ以上続くものを表す

これで単語の配列が得られます。 以下のプログラムでは配列を頭から検索する方法（wc1）と、シンボルをキーとしたハッシュを使う方法（wc2）を行い、 ベンチマーク・オブジェクトを使って時間計測を行いました。

require 'benchmark'

@a = File.read("pg28885.txt").split(/[^A-Za-z]+/)

# 配列による単語の頻度調査

def install_a (w)
  @word_table_a.each do |a|
    if a[0] == w
      a[1] += 1
      return
    end
  end
  @word_table_a << [w, 1]
end

def wc1
  @word_table_a = []
  @a.each { |s| install_a(s) }
  @word_table_a.sort{|a,b| a[1] <=> b[1]}.reverse.take(10)
end

# ハッシュによる単語の頻度調査

def install_s (w)
  s = w.to_sym
  if @word_table_s.has_key?(s)
    @word_table_s[s] += 1
  else
    @word_table_s[s] = 1
  end
end

def wc2
  @word_table_s = {}
  @a.each { |s| install_s(s) }
  @word_table_s.to_a.sort{|a,b| a[1] <=> b[1]}.reverse.take(10).map{|a| [a[0].to_s, a[1]]}
end

# 両者の結果が同じかどうかチェック

def w_test
  if wc1 != wc2
    print "wc1 != wc2\n"
  end
end

# ベンチマーク

def bm
  Benchmark.benchmark(Benchmark::CAPTION, 14, nil) do |rep|
    rep.report("wc with array") { wc1 }
    rep.report("wc with hash") { wc2 }
  end
end

# 最も多く現れた単語から10番目まで

def top10
  wc2.each do |a|
    print "#{a[0]}:  #{a[1]}\n"
  end
end

# 実行する作業を選択

# w_test
# top10
bm

このプログラムでは3つの作業を選択できます

  • w_test: 2つの方法で行った結果が等しくなるかのチェック
  • top10: 上位10単語とその出現回数を表示
  • bm: ベンチマーク。両者の実行時間を計測して表示

ベンチマークの結果は次のとおりです。

                     user     system      total        real
wc with array    1.345434   0.000000   1.345434 (  1.345614)
wc with hash     0.027752   0.000000   0.027752 (  0.027792)

ハッシュを用いたほうが圧倒的に速くその時間の比は約48:1です。 この方法が最速ではありませんが、プログラム作成の容易さから考えると有力な手法であると思います。 なお、上位10単語は以下のとおりでした。

the:  1716
and:  886
to:  827
a:  687
of:  616
it:  550
I:  545
she:  520
said:  465
in:  420

冠詞のtheが圧倒的に多く、次がandでした。 saidが9位に入っているのは物語だからでしょう。