ロックフリーの二重連結リストに関する研究は数多くあります。同様に、ロックフリー スキップ リストについても多くの研究があります。しかし、私が知る限り、ロックフリーの二重リンクスキップリストを管理した人は誰もいません。反対の研究、またはその理由を知っている人はいますか?
編集: 特定のシナリオは、高速分位数 (50%、75% など) アキュムレータを構築するためのものです。サンプルは O(log n) 時間でスキップ リストに挿入されます。イテレータを現在の分位数に維持することで、挿入された値を現在の分位数と O(1) 時間で比較でき、挿入された値が分位点の左または右にあるかどうか、および分位点がどのくらい離れているかを簡単に判断できます。その結果、移動する必要があります。前のポインターを必要とするのは左の移動です。
私が理解しているように、一度に挿入および削除する複数のスレッドに直面して、以前のポインターの一貫性を保つことから問題が発生します。解決策には、ポインター マーキングの巧妙な使用がほぼ確実に含まれると思います。
I have an idea for you. We use a "cursor" to find the item in a skiplist. The cursor also maintains the trail that was taken to get to the item. We use this trail for delete and insert - it avoids a second search to perform those operations, and it embeds the version # of the list that was seen when the traversal was made. I am wondering if you could use the cursor to more quickly find the previous item.
You would have to go up a level on the cursor and then search for the item that is just barely less than your item. Alternatively, if the search made it to the lowest level of the linked list, just save the prev ptr as you traverse. The lowest level is probably used 50% of the time to find your item, so performance would be decent.
Hmm... thinking about it now, it seems that the cursor would 50% of the time have the prev ptr, 25% of the time need to search again from 1 level up, 12.% 2 levels up, etc. So in infrequent cases, you have to almost do the search entirely again.
I think the advantage to this would be that you don't have to figure out how to "lock free" maintain a double linked skip list, and for the majority of cases you dramatically decrease the cost of locating the previous item.
バックリンクを維持する代わりに、変位値を更新する必要がある場合、別の検索を実行して、現在のキーよりも小さいキーを持つノードを見つけることができます。johnnycrash へのコメントでも述べたように、各レベルで見つかった右端のノードの配列を構築することが可能であり、そこから 2 番目の検索を高速化することができます。(フォミチェフの論文では、これが可能な最適化として言及されています。)
しかし、なぜそのようなことをするのでしょうか？私は実際に座って、スキップ リストがどのように機能するかを正確に理解していませんが、私の漠然とした理解からすると、以前のポインターを使用することはありません。では、なぜそれらを維持するオーバーヘッドがあるのでしょうか?
しかし、あなたがそうしたかったのなら、なぜできないのかわかりません。一重連結リストを二重連結リストに置き換えるだけです。双方向連結リストは論理的に一貫しているため、すべて同じです。