記憶装置トリアニーの謎を解け!
問題
[記憶装置トリアニーの謎を解け!]
使用したアルゴリズムとデータ構造
スキップリスト
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 を用いて動作確認を行った
使用したコード
![[Home]](./images/amatubu.png)