みんな、これ読んだ？
MIT、大規模マルチコアCPUの効率を向上させるデータ構造を開発 | スラッシュドット・ジャパン IT
SprayListというアルゴリズム、大規模分散CPUでもデータ集中を防いで性能を維持できるアルゴリズム、なんだそれと思ってい気になった。 という訳で論文を漁ってみた。
http://www.mit.edu/~jerryzli/SprayList-TR.pdf
ほほう、読み進めてみると、前提条件として、「SkipListのアルゴリズムを知っていること」とあった。なんだこれ、SkipListなんてアルゴリズム知らないぞ？
という訳で、SkipListについてまずは勉強するはめになった。SkipListについては、論文というよりも、普通の解説書が役に立ちそうだ (というか、解説書が出ているのに僕はこのアルゴリズムを知らなかったということか...情けない)。
資料としては、この辺りが分かりやすかった。
http://www.ics.uci.edu/~pattis/ICS-23/lectures/notes/Skip%20Lists.pdf
おー、イメージとしては、急行、快速、各停みたいなものだった。
一番下側のリストには、全てのデータがソートされて入っている。そして、上位レイヤのリストは、その部分集合となっている訳だ。上側のリストに含まれているエントリは、下側の同一エントリと同じポインタを共有している。
まず、このSkipListをどのように構成するか、という話だが、これはベースとなるソート済みの要素から、確率的に要素を選択していき、上位レイヤを作っていく。ここにあまり法則というか、ルールは無さそうだ。 上記の資料では、1/2の確率で上位のレイヤに登録していく。電車で言うならば、一駅毎に急行が止まっていく感じだ。 かといって、あまりレイヤを深くしていっても良くないらしい。いくら大きなリストでも、10レイヤ以上はあまり意味が無い、ということだ。
探索は非常に単純だ。基本的にどのレイヤもソートされているので、一番上のレイヤから順に、探した値になるまでレイヤを下っていく。
挿入や削除などの操作も定義されているが、それはまた今度。
