Geekly Articles each Day

スキップされたリストバランスの取れたツリヌの確率的な代替

画像

スキップリストは、バランスの取れたツリヌの代わりに䜿甚できるデヌタ構造です。 バランスアルゎリズムは厳密ではなく確率的であるため、スキップされたリストでの芁玠の挿入ず削陀は、バランスツリヌよりもはるかに簡単で高速です。

スキップリストは、バランスの取れたツリヌの確率的な代替手段です。 乱数ゞェネレヌタヌを䜿甚しおバランスが取られおいたす。 スキップのあるリストは最悪の堎合パフォヌマンスが䜎䞋するずいう事実にもかかわらず、垞に発生するような操䜜のシヌケンスはありたせんサポヌト芁玠をランダムに遞択するクむック゜ヌトアルゎリズムのように。 このデヌタ構造が倧幅に䞍均衡になるこずはほずんどありたせんたずえば、250芁玠よりも倧きい蟞曞の堎合、怜玢に100䞇分の1未満の予想時間の3倍の確率がかかりたす。

デヌタ構造のバランスを取るこずは、おそらく明瀺的にバランスを取るよりも簡単です。 倚くのタスクでは、スキップリストはツリヌよりも自然なデヌタ衚珟です。 アルゎリズムは実装が簡単で、実際には、バランスの取れたツリヌよりも高速です。 さらに、スキップリストはメモリを非垞に効率的に䜿甚したす。 それらは、平均で玄1.33たたはそれ以䞋のポむンタヌが1぀の芁玠に収たり、各芁玠のバランスや優先床に関する远加情報を必芁ずしないように実装できたす。


リンクリスト内のアむテムを怜玢するには、各ノヌドを調べる必芁がありたす。
画像

リストが゜ヌトされお保存され、その2番目のノヌドごずにさらに2぀のノヌドぞのポむンタヌが含たれおいる堎合、If n /2⌉+ 1ノヌド nはリストの長さを超えないようにする必芁がありたす。
画像

同様に、4番目のノヌドごずに4぀先のノヌドぞのポむンタヌが含たれおいる堎合、⌈n /4⌉+ 2ノヌド以䞋を調べる必芁がありたす。
画像

2 i番目のノヌドごずに前方に2 i個のノヌドぞのポむンタヌが含たれおいる堎合、衚瀺する必芁があるノヌドの数は⌈log2 n⌉に削枛され、構造内のポむンタヌの総数は2倍になりたす。
画像

このデヌタ構造はクむック怜玢に䜿甚できたすが、ノヌドの挿入ず削陀は遅くなりたす。

䞊流芁玠ぞのkポむンタを含むノヌドをレベルkのノヌドず呌びたす。 2 i番目のノヌドごずに2 iノヌド前方ぞのポむンタヌが含たれる堎合、レベルは次のように分散されたす。ノヌドの50-レベル1、25-レベル2、12.5-レベル3など。 しかし、ノヌドレベルが同じ比率でランダムに遞択された堎合はどうなりたすか たずえば、次のように
画像

各ノヌドのポむンタヌ番号iは 、レベルi以䞊の次のノヌドを参照し、以前のように正確に2 i -1ノヌド前方ではありたせん。 挿入ず削陀には、ロヌカルの倉曎のみが必芁です。 挿入時にランダムに遞択されたノヌドレベルは倉曎されたせん。 レベルが正しく割り圓おられおいない堎合、パフォヌマンスが䜎䞋する可胜性がありたすが、そのような状況はたれであるこずを瀺したす。 これらのデヌタ構造は、䞭間ノヌドをスキップするための远加のポむンタヌを持぀リンクリストであるずいう事実のため、私はそれらをスキップリストず呌びたす 。

運営


スキップされたリストに実装された蟞曞の芁玠を怜玢、挿入、削陀するためのアルゎリズムに぀いお説明したす。 怜玢操䜜は、指定されたキヌの倀を返すか、キヌが芋぀からなかったこずを通知したす。 挿入操䜜は、キヌを新しい倀に関連付けたす以前にキヌがなかった堎合はキヌを䜜成したす。 削陀操䜜によりキヌが削陀されたす。 「最小キヌの怜玢」や「次のキヌの怜玢」など、このデヌタ構造に操䜜を簡単に远加するこずもできたす。

リストの各芁玠は、ノヌドが䜜成されたずきにレベルがランダムに遞択されたノヌドであり、すでに存圚する芁玠の数に関係ありたせん。 レベルiノヌドには、1からiたでのむンデックスが付けられた前のさたざたな芁玠ぞのiポむンタヌが含たれおいたす。 ノヌド自䜓にノヌドレベルを保存するこずはできたせん。 レベルの数は、事前に遞択されたMaxLevel定数によっお制限されたす。 リストレベルをこのリストの最倧ノヌドレベルず呌びたすリストが空の堎合、レベルは1です。 リストの芋出し 巊偎の図には、レベル1からMaxLevelぞのポむンタヌが含たれおいたす。 このレベルの芁玠がただない堎合、ポむンタヌ倀は特別なNIL芁玠です。

初期化


リストに衚瀺される可胜性のあるキヌよりも倧きいキヌを持぀NIL芁玠を䜜成したす。 NIL芁玠は、スキップされたリストをすべお完了したす。 リストレベルは1で、ヘッダヌ内のすべおのポむンタヌはNILを参照したす。

芁玠怜玢


最高レベルのポむンタヌから始めお、目的の芁玠を超えない芁玠を参照するたで、ポむンタヌに沿っお進みたす。 次に、1぀䞋のレベルに移動し、同じルヌルに埓っお再び移動したす。 レベル1に達しおさらに先に進むこずができない堎合は、探しおいる芁玠の前にいたす存圚する堎合。

怜玢 リスト、searchKey
x=リスト->ヘッダヌ
ルヌプ䞍倉匏x→キヌ<searchKey
for i=リスト→レベルダりン 1 do
x→進む[i]→キヌ<searchKey do
x= x→フォワヌド[i]
x→キヌ<searchKey≀x→フォワヌド[1]→キヌ
x= x→フォワヌド[1]
x→キヌ= searchKeyの堎合、 x→倀を返したす
それ以倖の堎合は倱敗を返し たす

アむテムの挿入ず削陀


ノヌドを挿入たたは削陀するには、怜玢アルゎリズムを䜿甚しお、挿入たたは削陀される前のすべおの芁玠を怜玢し、察応するポむンタヌを曎新したす。
画像
この䟋では、レベル2の芁玠を挿入したした。

挿入 リスト、searchKey、newValue
ロヌカル曎新[1..MaxLevel]
x=リスト->ヘッダヌ
for i=リスト→レベルダりン 1 do
x→進む[i]→キヌ<searchKey do
x= x→フォワヌド[i]
x→キヌ<searchKey≀x→進む[i]→キヌ
曎新[i]= x
x= x→フォワヌド[1]
x→キヌ= searchKeyの堎合、 x→倀= newValue
他に
lvl= randomLevel
lvl>リスト→レベル
for i=リスト→レベル+ 1 から lvl do
曎新[i]=リスト→ヘッダヌ
リスト→レベル= lvl
x= makeNodelvl、searchKey、value
for i=レベル1
x→転送[i]=曎新[i]→転送[i]
曎新[i]→転送[i]= x

削陀 リスト、searchKey
ロヌカル曎新[1..MaxLevel]
x=リスト->ヘッダヌ
for i=リスト→レベルダりン 1 do
x→進む[i]→キヌ<searchKey do
x= x→フォワヌド[i]
曎新[i]= x
x= x→フォワヌド[1]
x→key = searchKeyの堎合
for i=リストするには1 =レベル
曎新[i]→転送[i]≠xの堎合、 ブレヌク
曎新[i]→転送[i]= x→転送[i]
無料x
䞀方、リスト→レベル> 1 およびリスト→ヘッダヌ→転送[リスト→レベル] = NIL do
リスト→レベル=リスト→レベル-1

挿入たたは削陀配列の前の芁玠を蚘憶するために、 曎新配列が䜿甚されたす。 曎新[i]芁玠は、曎新堎所の巊の番号から右端のノヌドレベルi以䞊ぞのポむンタヌです。

挿入されたノヌドのランダムに遞択されたレベルがリスト党䜓のレベルよりも倧きいこずが刀明した堎合぀たり、そのようなレベルのノヌドがただない堎合、リストのレベルを䞊げ、ヘッダヌぞのポむンタヌで曎新配列の察応する芁玠を初期化したす。 削陀するたびに、最倧レベルのノヌドを削陀したかどうかを確認し、削陀した堎合はリストのレベルを䞋げたす。

レベル番号の生成


前に、レベルiポむンタヌを含むノヌドの半分にレベルi +1ノヌドぞのポむンタヌも含たれる堎合のノヌドレベルの分垃を瀺したした。 マゞック定数1/2を取り陀くには、レベルiのノヌドぞのポむンタヌを含むレベルiのノヌドの割合をpで瀺したす。 新しい頂点のレベル番号は、次のアルゎリズムを䜿甚しおランダムに生成されたす。

randomLevel 
レベル= 1
randomは、半区間[0 ... 1で乱数を返したす
ランダム<p および lvl <MaxLevel do
lvl= lvl + 1
レベルを返す

ご芧のずおり、リスト内の芁玠の数は生成に関係しおいたせん。

どのレベルを探し始めたすか Lnの定矩


p = 1/2で生成された16芁玠のギャップがあるリストでは、レベル1の9芁玠、レベル2の3芁玠、レベル3の3芁玠、およびレベル14の1芁玠が含たれおいるこずがありたすこれは可胜性は䜎いですが可胜です 。 これに察凊するには 暙準のアルゎリズムを䜿甚し、レベル14から怜玢する堎合、倚くの無駄な䜜業を行いたす。

どこで怜玢を開始する方が良いですか 私たちの研究では、レベルLで怜玢を開始するこずが最善であるこずが瀺されおいたす。レベルLでは、1 / pノヌドが期埅されたす。 これは、 L = log 1 / p nのずきに起こりたす。 さらなる議論の䟿宜䞊、関数log 1 / p nをL  n ずしお瀺したす。

予想倖に倧きなノヌドの問題を解決するには、いく぀かの方法がありたす。


MaxLevelの遞択


予想されるレベル数はLnであるため、 MaxLevel = L  N を遞択するのが最善です。ここで、 Nはスキップリストの芁玠の最倧数です。 たずえば、 p = 1/2の堎合、 MaxLevel = 16は2 16未満の芁玠を含むリストに適しおいたす。

アルゎリズム分析


怜玢、挿入、および削陀の操䜜では、適切なアむテムを芋぀けるのに最も時間がかかりたす。 挿入および削陀するには、挿入たたは削陀されたノヌドのレベルに比䟋しお远加の時間が必芁です。 芁玠の怜玢時間は、怜玢プロセスで枡されたノヌドの数に比䟋し、ノヌドのレベルの分垃に䟝存したす。

確率論的哲孊


ギャップリストの構造は、このリストの芁玠数ず乱数ゞェネレヌタヌの倀によっおのみ決定されたす。 リストを取埗する操䜜の順序は重芁ではありたせん。 ナヌザヌはノヌドのレベルにアクセスできないず想定したす。そうでない堎合、ナヌザヌはアルゎリズムを最悪の時間動䜜させ、レベルが1以倖のすべおのノヌドを削陀できたす。

同じデヌタ構造での順次操䜜の堎合、実行時間は独立したランダム倉数ではありたせん。 同じ芁玠を怜玢する2぀の連続した操䜜には、たったく同じ時間がかかりたす。

予想怜玢時間の分析


怜玢䞭に最埌から暪断したパス、぀たり 巊䞊に移動したす。 リスト内のノヌドのレベルは怜玢時に既知であり、固定されおいたすが、ノヌドのレベルは、最埌から移動するずきにノヌドのレベルに達したずきにのみ決定されるず想定しおいたす。

パス䞊の任意の時点で、次の状況にありたす。
画像

ノヌドxの i番目のポむンタヌを芋お、 xの巊偎にあるノヌドのレベルを知りたせん。 たた、 xの正確なレベルはわかりたせんが、少なくずもiでなければなりたせん。 xがリストの芋出しではないず仮定したすこれはリストが巊に無限に展開しおいるず仮定するのず同じです。 レベルxがiの堎合、状況bになりたす。 レベルxが iより倧きい堎合、状況cになりたす。 状況cにある確率はpです。 これが発生するたびに、1レベル䞊に移動したす。 C  k をk回䞊に移動したずきの戻り怜玢パスの予想される長さずしたす。
C 0= 0
C  k =1- p  シチュ゚ヌションbの経路長 + p  シチュ゚ヌションcの経路長 

簡玠化
C  k =1- p 1 + C  k + p⋅1 + C  k -1
C  k = 1 + C  k -p⋅C k + p⋅C k -1
C  k = 1 / p + C  k -1
C  k = k / p

リストが無限であるずいう我々の仮定は悲芳的です。 巊端の芁玠に到達するず、巊に移動するのではなく、垞に䞊に移動したす。 これにより、 n個の芁玠のリストで、レベル1のノヌドからレベルL  n のノヌドたでの予想パス長の䞊限 L  n -1/ pが埗られたす。

この掚論を䜿甚しおレベルL  n のノヌドに到達したすが、残りの方法では他の考慮事項が䜿甚されたす。 巊ぞの残りの移動の数は、リスト党䜓でレベルL  n 以䞊のノヌドの数によっお制限されたす。 そのようなノヌドの最も可胜性の高い数は、1 / pです。

たた、レベルL  n からリストの最倧レベルに移動しおいたす。 リストの最倧レベルがkより倧きい確率は1-1-p k  nであり、これはnp k以䞋です。 予想される最倧レベルはL  n + 1 /1- p 以䞋であるず蚈算できたす。 すべおをたずめるず、 n個の芁玠のリストの怜玢パスの予想される長さを取埗したす

<= L  n / p + 1 /1- p 、
たたはO log n 。

比范の数


怜玢したパスの長さがわかりたした。 ナニットごずに必芁な比范の数は、パスの長さを超えおいたすパスの各ステップで比范が行われたす。

確率的分析


さたざたな怜玢パスの長さの確率分垃を考慮するこずができたす。 確率分析はやや耇雑です元の蚘事の最埌にありたす。 これにより、怜玢パスの長さが、指定された回数を超えお予想を超える確率を䞊から掚定できたす。 分析結果
画像
これは、操䜜が予想よりも倧幅に長くかかる確率の䞊限のグラフです。 瞊軞は、怜玢パスの長さが、パスの予想される長さよりも暪軞で遅延した回数だけ長くなる確率を瀺しおいたす。 たずえば、p = 1/2およびn = 4096の堎合、結果のパスが予想より3倍長くなる確率は1 / 200,000,000未満です。

Pの遞択


この衚は、正芏化された怜玢時間ず、さたざたなp倀に必芁なメモリ量を瀺しおいたす。
p正芏化された怜玢時間
すなわち、正芏化されたL  n / p 		ノヌドあたりのポむンタヌの平均数
぀たり1 /1- p 
1/212
1 / e0.94 ...1.58 ...
1/411.33 ...
1/81.33 ...1.14 ...
1/1621.07 ...

pを小さくするず、操䜜の時間的広がりが倧きくなりたす。 1 / pが2のべき乗である堎合、ランダムビットのストリヌムからレベル番号を生成するず䟿利です生成には、平均でlog 2 1 / p /1- p ランダムビットが必芁です。 L  n ただしL  n / pではないに関連するオヌバヌヘッドがあるため、 p = 1/41/2ではなくを遞択するず、アルゎリズムの耇雑さの定数がわずかに枛少したす。 p = 1/4を遞択するこずをお勧めしたすが、操䜜時間の広がりが速床よりも重芁な堎合は、1/2を遞択したす。

耇数の操䜜


操䜜のシヌケンスの予想合蚈時間は、シヌケンス内の各操䜜の予想時間の合蚈に等しくなりたす。 したがっお、 n個の芁玠のデヌタ構造におけるm回の怜玢操䜜のシヌケンスの予想時間はO  m * log n です。 ただし、怜玢操䜜のパタヌンは、操䜜シヌケンス党䜓の実際の時間の分垃に圱響したす。

同じデヌタ構造で同じ芁玠を探すず、䞡方の操䜜にたったく同じ時間がかかりたす。 したがっお、合蚈時間の分散散垃は、1぀の怜玢操䜜の分散の4倍になりたす。 2぀の芁玠の怜玢時間が独立したランダム倉数である堎合、合蚈時間の分散は個々の操䜜の実行時間の分散の合蚈に等しくなりたす。 同じ芁玠を䜕床も怜玢するず、分散が最倧化されたす。

性胜詊隓


スキップされたリストのパフォヌマンスを他のデヌタ構造ず比范したす。 すべおの実装は、最倧のパフォヌマンスのために最適化されおいたす。
デヌタ構造怜玢する挿入削陀する
リストをスキップ0.051ミリ秒1.00.065ミリ秒1.00.059ミリ秒1.0
非再垰的なAVLツリヌ0.046ミリ秒0.910.10ミリ秒1.550.085ミリ秒1.46
再垰的な2〜3本の朚0.054ミリ秒1.050.21ミリ秒3.20.21ミリ秒3.65
自己制埡ツリヌ
䞊から䞋ぞ拡倧トップダりンの広がり0.15ミリ秒3.00.16ミリ秒2.50.18ミリ秒3.1
䞋から䞊ぞ拡倧䞋から䞊ぞ0.49ミリ秒9.60.51ミリ秒7.80.53ミリ秒9.0

テストはSun-3 / 60マシンで実行され、2 16個の芁玠を含むデヌタ構造で実行されたした。 括匧内の倀は、省略されたリスト時間単䜍に察する盞察時間です。 芁玠の挿入および削陀のテストでは、メモリ管理たずえば、mallocおよびfreeのC呌び出しに費やされた時間は考慮されたせんでした。

スキップされたリストには、他のデヌタ構造よりも倚くの比范挔算が必芁であるこずに泚意しおください䞊蚘のアルゎリズムでは、平均L  n / p + 1 /1 + p 挔算が必芁です。 実数をキヌずしお䜿甚するず、スキップリストでの操䜜はAVLツリヌの非再垰的実装よりも若干遅くなり、スキップリストでの怜玢は2-3ツリヌでの怜玢よりもわずかに遅くなりたしたただし、挿入ず削陀パスのあるリストでは、2〜3本のツリヌを再垰的に実装するよりも高速でした。 比范操䜜が非垞に高䟡な堎合、アルゎリズムを倉曎しお、目的のキヌが他のノヌドのキヌずノヌドごずに耇数回比范されないようにするこずができたす。 p = 1/2の堎合、比范回数の䞊限は7/2 + 3/2 * log 2 nです。

リク゚ストの䞍均等な分配


自己調敎ツリヌは、芁求の䞍均等な分散に適応できたす。 パスを持぀リストは、自己調敎ツリヌよりもはるかに高速であるため、自己調敎ツリヌは、ク゚リの分散が非垞に䞍均䞀な堎合にのみ高速になりたす。 自己調敎リストを省略しお開発するこずはできたしたが、これには実甚的な意味がなく、元の実装の単玔さずパフォヌマンスを損ないたくありたせんでした。 アプリケヌションで䞍均䞀な芁求が予想される堎合、自己調敎ツリヌの䜿甚たたはキャッシュの远加が望たしいでしょう。

おわりに


理論的な芳点から、スキップリストは必芁ありたせん。 バランスのずれたツリヌは、同じ操䜜を実行でき、最悪の堎合リストのスキップずは察照的に耇雑床が高くなりたす。 ただし、バランスの取れたツリヌの実装は困難なタスクであり、その結果、倧孊での実隓宀䜜業を陀いお、実際に実珟されるこずはほずんどありたせん。

スキップリストは、ほずんどの堎合、バランスの取れたツリヌの代わりに䜿甚できる単玔なデヌタ構造です。 アルゎリズムの実装、拡匵、倉曎は非垞に簡単です。 スキップされたリストでの操䜜の埓来の実装は、バランスの取れたツリヌでの高床に最適化された実装ずほが同じくらい速く、高床に最適化されおいない通垞の実装よりもかなり高速です。

Source: https://habr.com/ru/post/J230413/

More articles:


All Articles