kaisehのブログ

要素の挿入、削除、ランダムアクセスが全部高速なリストを作った

Algorithm, Java

スキップリスト（Skip List）は1990年に発表された比較的新しいアルゴリズムで、要素の挿入や削除、検索を平衡木と同等のパフォーマンスで実行可能なリスト構造です。

Skip Listは連結リストの多層構成になっています。路線に例えると、最下層のリンクは各駅停車のように、全要素を結んでいます。一方、上層のリンクは急行や特急のように、途中の要素をスキップするようになっています。この路線を特急→急行→…→各駅と乗り継ぐことで、目的の要素に高速に到達できる仕組みです。もっと詳しい解説はこちらやこちらにあります。

で、ここからが本題です。Skip Listの実装はいくつも出ているんですが、Sorted Listとしての実装ばかりで、要素を任意順序で格納できてランダムアクセス（indexを指定してのアクセス）可能なSkip Listが見つからなかったので、自分で作ってみました。

通常のSkip Listでは、各ノードは次のノードへのリンクしか保持していません。ここに少し工夫を加えて、上の画像のように、次ノードまでの「距離」を持たせるようにしました。ノード探索時にこの距離を加算していくことで、indexによる要素の取得をO(logN)で実行できます。

このSkipListに加えて、java.util.Listとjava.util.Setを両方実装したSkipListSetというものも作りました。こちらは内部的にHashMapを併用していて、indexOf()やcontains()も高速になっています。各メソッドの計算量比較は以下の通りです。

ソースは以下からどうぞ。

• SkipList.java
• SkipListSet.java

Permalink | コメント(3) | トラックバック(1) | 02:27