とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

スキップリスト

http://pc11.2ch.net/test/read.cgi/tech/1231640024/

23 名前:デフォルトの名無しさん[sage] 投稿日:2009/01/15(木) 03:54:50
連結リストはランダムアクセス時に後方要素を検索するのに時間がかかるけど、
内部にさらにリストを使ったりして10000個とかジャンプさせればかなり安定すると
思うけどな。

ちょっと自分で作って比較検証してみるか……
26 名前:デフォルトの名無しさん[sage] 投稿日:2009/01/15(木) 12:10:37
>>23
それはスキップリストっていうデータ構造
結構古典的なデータ構造だから検証しなくても大体O(log N)になるよ

へー。スキップさせる定数はどうやって求めるんだろ?
追記:
スキップリスト - Wikipedia
普通にあったw