ロックフリーの二重リンクスキップリスト

Question

ロックフリーの二重リンクリストに関する研究は数多く存在します。同様に、ロックフリーのスキップリストにはたくさんのリサーチがあります。しかし私が知る限り、ロックフリーの二重リンクスキップリストは管理していません。誰かが逆の研究を知っているのですか、それともなぜそうなのでしょうか？

編集： 具体的なシナリオは、高速分位数（50％、75％など）のアキュムレータを構築するためのシナリオです。サンプルはO（log n）時間内にスキップリストに挿入されます。イテレーターを現在の分位点に維持することによって、挿入された値をO（1）時間内の現在の分位点と比較することができ、挿入された値が分位子の左右にあるかどうか、結果として移動する必要があります。これは、前のポインタを必要とする左の動きです。

私が理解しているように、一度に複数のスレッドを挿入したり削除したりしても、以前のポインタを一貫して保つことは難しいでしょう。私は、このソリューションには、ポインターマーキングの巧妙な使用がほぼ確実に関わると思います。

Answer 1

しかし、なぜあなたはそのようなことをしますか？私は実際に座っていないし、リストをスキップする方法を厳密に計算しましたが、私のあいまいな理解から、あなたは以前のポインタを使うことはありません。では、なぜそれらを維持するオーバーヘッドがありますか？

しかし、あなたがしたい場合は、私はあなたがなぜできないのか分かりません。単一リンクリストを二重リンクリストに置き換えるだけです。二重にリンクされたリストは論理的に一貫しているので、すべて同じです。

Answer 2

私にはあなたの考えがあります。我々はスキップリスト内のアイテムを見つけるのに "カーソル"を使う。また、カーソルはアイテムに到達するために取られたトレイルを保持します。このトレイルを削除および挿入に使用します。これらの操作を実行するための2回目の検索を回避し、トラバーサルが行われたときに表示されたリストのバージョン番号を埋め込みます。カーソルを使用して前のアイテムをより迅速に見つけることができるかどうかは疑問です。

カーソルのレベルを上げて、アイテムよりもわずかに少ないアイテムを検索する必要があります。また、検索によってリンクされたリストの最下位レベルに達した場合は、トラバースするときにprev ptrを保存するだけです。最も低いレベルは、おそらくあなたのアイテムを見つけるのに時間の50％が使われるので、パフォーマンスはまともです。

うーん...今考えてみると、カーソルの50％が前のPTTを持つように見えます。25％の時間が1レベル上から再度検索する必要があります.12％まれなケースでは、ほぼ完全に検索を行う必要があります。

これは、ダブルロックされたスキップリストを「ロックフリー」にする方法を理解する必要がなく、大部分の場合、前のアイテムを見つけるコストを大幅に削減できるという利点があると思います。