prog_0002

スキップリスト

• (by K, 2014.10.14)

(0)

• 今回はスキップリスト（SkipLists）の話。

(1)

• 多数のオブジェクトがある状態で、オブジェクトを高速に検索するためにインデックスを張りたい、というニーズは時々ある。そんな時にどんなアルゴリズムを使えばいいだろうかと考えた。
• 行いたい操作は、次の通り。
  • (a)要素の追加
  • (b)要素の削除
  • (c)要素をキーで整列させておいた状態において、i番目の要素を得る
    • これができれば先頭や末尾も取れる
  • (d)ある要素を指定した時に、その要素が先頭から何番目であるかを返す
  • (e)あるキーを指定して、それより小さい要素のうちで最大のものを得る
    • つまり、2,4,6,8,10が登録されているときに、key=7で検索すると、6のオブジェクトが得られる。
  • (f)あるキーを指定して、それよりも大きい要素のうちで最小のものを得る
  • (g)2つの要素の間にいくつの要素があるかを返す
  • (h)2つの要素の間の要素を順番に列挙する
  • なお、前提条件として、キーの重複はないとする。
• これらをやりたいならスキップリストがよさそうだと思った。
  • 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
  • http://www.dd.iij4u.or.jp/~okuyamak/Information/SkipLists.html
• スキップリストなら、(a)～(g)の操作がO(logN)でできそう。(h)は列挙する要素の個数にも比例して、O(MlogN)とかになりそう。これはなかなか優秀である。
  • 上記のwikipediaのページによれば、B木はさらに優秀らしいが、B木は構成の変化に応じて再構成が必要になり、その分だけプログラムが複雑になる。それが悩ましい。まあ一度本気で作ってライブラリ化してしまえば問題にはならないのかもしれないけれど・・・。

(2)

• 僕は先日これを実装した。高速化を少し意識して冗長な部分もあるけれど、しかしそれでも350行程度だった。なかなか便利だ。
• ちなみにp=1/4くらいがちょうどいいかなと思っている。p=1/2とかだとmaxLevelを2倍くらいにしないといけなくなる。1/4なら、maxLevel=8でも64K個くらいの要素は管理できると思う。
• この実装では、もちろん一般化された比較関数を採用して（参照：prog_0001）、比較関数の第一引数はcustomizeポインタになっている。

(3)

• 乱数を使うというのは、結果が乱数によって左右されてしまうという不安定さがあるものの、しかしアルゴリズムが単純になるというメリットもあって、なかなか考えらせられる。これからは乱数アルゴリズムの時代なんじゃないかとよく思う。
  • 乱数が主役というのがいいすぎだとしても、確率計算が重要になるという感じは、たぶん合っているような気がする。

(4)

• JavaにはTreeMapが標準で用意されていてちょっとうらやましい。

こめんと欄

• 実際にベンチマークを書いて少し試したところでは、p=1/2よりもp=1/4のほうが性能は良かった。 -- K 2014-10-26 (日) 02:15:22