記憶装置トリアニーの謎を解け!

問題

記憶装置トリアニーの謎を解け!

《辞書プログラム》で使ったデータ構造とアルゴリズム

データ構造にトライ木を使用しました。
トライ木については トライ木 - Wikipedia を参照してください。
本プログラムでは、トリアニーのaフィールドに辞書の値を、b,cフィールドに枝（次のトリアニーのid）を格納しています。
このとき、bフィールドの枝には「0」、cフィールドの枝には「1」というラベルが付いていると考えることにします。
トライ木のキーには、辞書のキーを2進数に変換し、下位ビットから見たものを使用します。

キーに対応する値の格納方法
  1. ルート・トリアニーに注目する
  2. キーを2進数にして下位ビットから1ビットずつ見ていく
  3. ビットが0ならbフィールドの枝をたどる。ビットが1ならcフィールドの枝をたどる。このとき、枝をたどった先にノードがなければ、新しいノードを追加する
  4. ビットをすべて見終えたところで、注目しているノードがキーに対応するノード。aフィールドに値をセットする
キーに対応する値の検索方法
  1. ルート・トリアニーに注目する
  2. キーを2進数にして下位ビットから1ビットずつ見ていく
  3. ビットが0ならbフィールドの枝をたどる。ビットが1ならcフィールドの枝をたどる。このとき、枝をたどった先にノードがなければ、エントリがないことになる。検索失敗
  4. ビットをすべて見終えたところで、注目しているノードがキーに対応するノード。aフィールドが検索された値

データ構造にトライ木を選択した理由

線形リストにくらべて検索が速いためです。
以下にノード数nの線形リスト、トライ木に対しての検索、挿入の計算量を示します。

検索 挿入(*1)
線形リスト O(n) O(1)
トライ木(*2) O(log n) O(1)

*1:検索の時間を含まない
*2:平衡のとき

ベンチマーク

以下に、線形リストで実装した辞書と、トライ木で実装した辞書のベンチマークを示します（3回実行中の中央値）
CPU：Intel(R) Core(TM)2 Duo CPU E6850 @ 3.00GHz
テストデータ：testdata.txt

線形リストで実装した場合
$ time ruby triany1.rb
141421356

real    0m9.876s
user    0m9.833s
sys     0m0.044s
トライ木で実装した場合
$ time ruby triany2.rb
141421356

real    0m0.507s
user    0m0.452s
sys     0m0.056s

使用したプログラミング言語

Ruby 1.9.3

コード

#!/usr/bin/ruby
# -*- coding: utf-8 -*-


#
# TrianyMemoryクラス
#
class TrianyMemory

  #
  # トリアニーを要素数3のArrayで表す。例：[1,2,3]
  # @trianys はアロケート済みのトリアニーを保持する配列
  # @trianys の添字がトリアニーのidを表す。例：@trianys[1]はidが1のトリアニー
  # @trianys の初期状態は 1:[0,0,0]
  #
  def initialize() @trianys = [nil, [0,0,0]] end
  def to_s() @trianys[1, @trianys.length].each_with_index.map {|t,i| "#{(i+1).to_s}:#{t.to_s}\n" }.join end

  #
  # TLLI - Triany Low Level Interface
  # メソッドの仕様については技術ドキュメントをご覧ください
  #
  def root_triany() 1 end
  def allocate_triany() (@trianys << [0,0,0]).length - 1 end
  def set_a(id, value) (id<=0 or @trianys[id].nil? or value<0) ? nil : @trianys[id][0] = value end
  def set_b(id, value) (id<=0 or @trianys[id].nil? or value<0) ? nil : @trianys[id][1] = value end
  def set_c(id, value) (id<=0 or @trianys[id].nil? or value<0) ? nil : @trianys[id][2] = value end
  def get_a(id) (id<=0 or @trianys[id].nil?) ? nil : @trianys[id][0] end
  def get_b(id) (id<=0 or @trianys[id].nil?) ? nil : @trianys[id][1] end
  def get_c(id) (id<=0 or @trianys[id].nil?) ? nil : @trianys[id][2] end
end


#
# TrianyMemoryで実装した辞書のクラス
#
class Dictionary
  def initialize() @tm = TrianyMemory.new end
  def to_s() @tm.to_s end

  #
  # DICTI - Dictionary Interface
  # メソッドの仕様については技術ドキュメントをご覧ください
  #
  def set_entry(key, value)
    id = @tm.root_triany                                    # ←idは現在注目しているノードの番号
    key.to_s(2).each_char.map(&:to_i).reverse_each do |bit| # ←キーを2進数に変換して下位ビットから見る
      if (bit==0 ? @tm.get_b(id) : @tm.get_c(id)) == 0      # ←ビットが0ならbの枝の先を見る。ビットが1ならcの枝の先を見る
        bit==0 ? @tm.set_b(id, @tm.allocate_triany) : @tm.set_c(id, @tm.allocate_triany)  # ←枝の先にノードがなかった。新しいノードを付ける
      end
      id = bit==0 ? @tm.get_b(id) : @tm.get_c(id)           # ←枝の先のノードに注目する
    end
    @tm.set_a(id,value)                                     # ←ビットを全部見終えたところで注目しているノードのaフィールドに値をセットする
  end

  def find_entry(key)
    id = @tm.root_triany                                    # ←idは現在注目しているノードの番号
    key.to_s(2).each_char.map(&:to_i).reverse_each do |bit| # ←キーを2進数に変換して下位ビットから見る
      id = bit==0 ? @tm.get_b(id) : @tm.get_c(id)           # ←ビットが0ならbの枝の先のノードに注目する。ビットが1ならcの枝の先のノードに注目する
      return 0 if id==0                                     # ←枝の先にノードがなかった。ビットを全部たどれない（=エントリがない）ので0を返して終了
    end
    @tm.get_a(id)                                           # ←ビットを全部見終えたところで注目しているノードのaフィールドを返す
  end
end


#
# Dictionaryを使ってテストデータを処理する
#
dic = Dictionary.new

sum = File.open('testdata.txt', 'r:CP932').read.each_line.inject(0) do |sum,line|
  case line
  when /^s +(\d+) +(\d+)/
    dic.set_entry($1.to_i, $2.to_i)
  when /^f +(\d+)/
    sum += dic.find_entry($1.to_i)
  end
  sum
end

puts sum

感想

こうやって考えました。
  1. とりあえず線形リストで実装してみる → 遅い
  2. じゃあ木にしよう → フィールドが3つしかないから二分木にできない？
  3. 適当な木がないか Wikipedia の木の一覧から探す → 名前がトリアニーだしトライ木っぽい？
  4. キーが1文字っぽいけど、数値を格納するとしたら0-9の枝を作るの？ → そんなに枝は作れない
  5. 紆余曲折（じゃあトライ木じゃない？ / 枝を線形リストに格納しよう！ / トリアニーを2つ組み合わせて二分木しよう！！）
  6. よく考えたらキーを2進数にすればいいじゃん → よく読んだら Wikipedia にもそう書いてありました
感想

極めてシンプルな構造になって嬉しく思っています。
トライ木の枝を線形リストにしたり、トリアニーを2つ組み合わせたりしていたら目も当てられない事になっていたでしょう。

おまけ

テストデータから生成したトライ木のグラフを描いてみました。おもしろい絵になりました。
http://dl.dropbox.com/u/98984964/triany/triany.dot （ソース）
http://dl.dropbox.com/u/98984964/triany/triany.svg （SVG. 注意：17MB）
スクリーンショット（一部）