Indexable skiplist
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/12 19:08 UTC 版)
「スキップリスト」の記事における「Indexable skiplist」の解説
上で述べられているように、スキップリストでは、データ系列への値の挿入や削除は高速に（ O ( log n ) {\displaystyle {\mathcal {O}}(\log n)} で）可能であるが、系列の中のある指定した場所の値の取り出し（例えば、500番目の値を返す）は遅く、 O ( n ) {\displaystyle {\mathcal {O}}(n)} の時間がかかる。しかし、少し変更を加えることで、ランダムアクセス の実行時間は O ( log n ) {\displaystyle {\mathcal {O}}(\log n)} にまで改良することができる。 すべてのリンクに対し、リンクの「幅」も格納することにする。ここでリンクの「幅」とは、「急行列車」のリンクが飛ばす（最下層での）リンクの数である。 例として、上で挙げた例のリンクの幅を次に示す。 1 10 o---> o---------------------------------------------------------> o 最上層 1 3 2 5 o---> o---------------> o---------> o---------------------------> o 第3層 1 2 1 2 3 2 o---> o---------> o---> o---------> o---------------> o---------> o 第2層 1 1 1 1 1 1 1 1 1 1 1 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o 最下層 Head 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th NIL Node Node Node Node Node Node Node Node Node Node 第2層以上のリンクの幅は、そのリンクの下にある、下位層のリンク幅の和に等しいことに注意。（例えば、最上位層のリンク幅10は、そのすぐ下にある3つのリンクの幅 3、2、5の和になっている。）したがって、すべての層において、すべてのリンクの幅の和は等しい (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 5)。 スキップリストにインデクスをつけて i 番目の値を探すには、スキップリスト内を、進んだリンクの幅の分だけ必要ステップ数を減らしながら、リンクを辿っていけばよい。次のリンク幅が大きすぎる場合には、下の層へ降りる。 例えば、上の例で5番目の値を得たい場合には、まず最上位層の幅1のリンクを進む。残りの必要ステップ数は 4=5-1 であるが、次のステップ幅は10であり大きすぎるので、第3層へ降りる。この層で、幅3のリンクを進む。 残りの必要ステップ数は1で、次のリンク幅は2のため大きすぎ、下の層へ降りる。第2層の次のリンクも幅が2で大きすぎるため、最下層に降りる。最後に幅1のリンクを1つ進めば、5(=1+3+1)ステップ進んだことになり、目的のノードにたどり着く。 function lookupByPositionIndex(i) node ← head i ← i + 1 # don't count the head as a step for level from top to bottom do while i ? node.width[level] do # if next step is not too far i ← i - node.width[level] # subtract the current width node ← node.next[level] # traverse forward at the current level repeat repeat return node.value end function このインデクス付けの実装方法については、Section 3.4 Linear List Operations in "A skip list cookbook" by William Pughに詳細がある。
※この「Indexable skiplist」の解説は、「スキップリスト」の解説の一部です。
「Indexable skiplist」を含む「スキップリスト」の記事については、「スキップリスト」の概要を参照ください。
- Indexable skiplistのページへのリンク
