記憶装置トリアニーの謎を解け!
問題
[記憶装置トリアニーの謎を解け!]
使用したアルゴリズムとデータ構造
- スキップリスト
- http://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AD%E3%83%83%E3%83%97%E3%83%AA%E3%82%B9%E3%83%88
- スキップリストの各ノードは2つの Triany で管理する
- ひとつめの Triany の各フィールドの値:
- a : ノードのキー
- b : ふたつめの Triany の id (存在しないときは 0)
- c : 同じレベルの次のノードの id
- ふたつめの Triany の各フィールドの値:
- a : ノードの値
- b : ノードのレベル (記録はしているが、使用していない)
- c : ノードの下のレベルのノードの id (存在しないときは 0)
- また、スキップリストへのデータ挿入時に更新が必要なノードを記録するため、Triany を用いた双方向リストを用いる
- ノード記録領域の各ノードはひとつの Triany で管理する
- Triany の各フィールドの値:
- a : 更新が必要なノードの id (データ探索時にセットし、挿入時に利用)
- b : 次のノードの id
- c : 前のノードの id
- これらのデータのエントリポイントを記録するために Root Triany を利用する
- Root Triany の各フィールドの値:
- a : スキップリストの最大レベルの最初のノード
- b : ノード記録領域の最大レベルのノード
- c : ノード記録領域の最小レベル(0)のノード
- DICTI においては Triany Memory 以外には配列等を用いずに実装した
アルゴリズム、データ構造を選択した理由
- アルゴリズムについては、実装が簡単でそこそこの速度が出そうなことから
- データ構造については、スキップリストは、探索時に頻繁に利用されるキーと次のノードの id をひとつめの Triany に格納することとした
- 下のレベルのノードの id もよく利用するが、今回の問題でテストしたところでは次のノードへの移動の方が多かったため、このような構造とした
- 更新時のノード記録領域については、ノード情報を記録する探索時にはレベルの高いところから、データ挿入時にはレベルの低いところから行なうため、最大、最小のどちらからでも参照できるよう、双方向リストとした
特記事項
- Triany の id は符号付き 32 ビットの 正の整数とした (最大値は LONG_MAX)
- この値は、Triany::TLLI で定義された「$triany_max_id」を変更することによりカスタマイズ可能である
- Triany を割り当てたときの id は、1 から LONG_MAX までの間でランダムに振ることとした ( ただし 1 は Root Triany で予約されているため、それ以外の Triany で利用することはできない)
- Perl の rand 関数では 32767 までの値しか扱えないため、Math::Random::MT モジュールを用いている
- スキップリストへのデータ挿入時にレベル k+1 となる確率 / レベル k となる確率は、1/2 とした (期待値としては、レベル k+1 に格納されるリストの要素の数は、レベル k の 1/2 となる)
- この値は現在はハードコーディングされている
- スキップリストの最大レベルは 31 とした (上記により、LONG_MAX までからなる id を上のレベルに行くにつき半分になっていくとすると、レベル 31 での期待値は、1個となる)
- この値は Trinity::DICTI で定義された「$skiplist_max_level」を変更することによりカスタマイズ可能である
- 問題のデータでは、24 あたりにしたほうがパフォーマンスがよいようだ
- 処理時間は要素数の対数に比例して増加する ( O(log n) である)
使用したプログラミング言語の名前
- Perl
- Perl v5.12.4 + Math::Random::MT 1.16 で動作確認
- ActivePerl v5.8.9 では Math::Random::MT::Auto を用いて動作確認を行った
使用したコード
- [dict.pl - 辞書プログラム]
- [Triany/TLLI.pm - TLLI (Triany Low Level Interface) モジュール]
- [Triany/DICTI.pm - Triany DICTI (Dictionary Interface) モジュール]
- [TLLI の単体テスト]
- [DICTI の単体テスト]
感想
- 問題を読んで、最初は二分探索木を実装しようかと思ったのですが、問題データを見ると、そのまま実装するとバランスが悪くなりそうだったので、平衡二分探索木よりも実装が簡単そうなスキップリストを利用してみました。
- いずれにしてもひとつの Triany ではひとつのノードを表すことができないため、データ構造としては非効率な方法になってしまいました。
- テストデータを使って計算したところ、今回書いたプログラムよりも、単純に連想配列を用いて計算した場合のほうが数十倍も速いことがわかりましたが、単純な連結リストに比べれば十分な速度が得られました。
- データ構造について制約があるという環境でのプログラムはあまり書いたことがなかったため、新鮮な感じがしました。
- データがちゃんと連結されているかどうか不安があったので一通りのテストも書きました。