■使用したアルゴリズムとデータ構造
スキップリスト 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
![[Home]](./images/amatubu.png)
スキップリストの各ノードは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 を用いて動作確認を行った
■使用したコード