26

スキップ リスト(Pugh、1990 年) は、検索ツリーのような対数時間操作で並べ替えられた辞書を提供しますが、スキップ リストは同時更新にはるかに適しています。

効率的な純粋に機能的な同時スキップ リストを作成することは可能ですか? そうでない場合、効率的な純粋に機能的な同時ソート辞書を作成することは可能ですか?

4

4 に答える 4

39

同時更新に適したスキップ リストのプロパティ (つまり、ほとんどの加算と減算がローカルである) は、不変性にも不利です (つまり、リスト内の多くの前の項目が最終的に後の項目を指し、変更されます）。

具体的には、スキップ リストは次のような構造で構成されます。

NODE1 ---------------------> NODE2 ---------...
  |                           |
  V                           V
NODE1a --> NODE1b ---------> NODE2a --> NODE2b --> NODE2c --- ...

NODE2bここで、たとえば、またはを削除する更新がある場合、NODE1b非常にローカルに処理できます。それぞれまたはをポイント2aするだけで完了です。残念ながら、リーフ ノードはすべて互いにポイントしているため、機能的な (不変の) 更新には適した構造ではありません。2c1a2a

したがって、ツリー構造は不変性に適しています (損傷は常にローカルに制限されます。つまり、関心のあるノードと、ツリーのルートまでの直接の親だけです)。

同時更新は、不変のデータ構造ではうまく機能しません。考えてみれば、どの機能ソリューションにもAasの更新がありますf(A)。fで与えられた更新と で与えられた更新の 2 つが必要な場合はg、ほとんどまたはを実行する必要があります。f(g(A))または、要求をインターセプトして、すべてを一度に適用できるg(f(A))新しい操作を作成する必要があります (または、他のさまざまな操作を行う必要があります)。h = f,g非常に賢いもの）。

ただし、状態が変化しないことが保証されているため、同時読み取りは不変のデータ構造で非常にうまく機能します。他の書き込みが中断する前に解決される読み取り/書き込みループを持つことができると想定しない場合は、読み取りをロックする必要はありません。

したがって、書き込みの多いデータ構造は、おそらく可変的に実装する方が適切です (ローカルにロックするだけでよいスキップ リストのようなものを使用します)。一方、読み取りの多いデータ構造は、おそらく不変に実装する方が適切です (ツリーがより自然なデータ構造である場合)。 ）。

于 2010-08-15T23:53:42.480 に答える
6

スキップ リストではありませんが、問題の説明と一致しているようです: Clojure の永続的な赤黒ツリー ( PersistentTreeMap.javaを参照)。ソースには次の通知が含まれています。

/**
 * Persistent Red Black Tree
 * Note that instances of this class are constant values
 * i.e. add/remove etc return new values
 * <p/>
 * See Okasaki, Kahrs, Larsen et al
 */

これらのツリーは要素の順序を維持し、Rich Hickey がこの言葉を使用する意味で「永続的」です (不変であり、更新されたバージョンが構築されるときにパフォーマンスの保証を維持できます)。

それらを試してみたい場合は、Clojure コードで関数 を使用してインスタンスを作成できますsorted-map。

于 2010-08-15T23:18:58.463 に答える
4

スキップ リストの前にコンスのみが必要な場合は、永続的な不変バージョンを作成できるはずです。

この種のスキップ リストの利点は、「ランダムな」アクセスです。たとえば、通常の単一の連結リストよりも高速に n 番目の要素にアクセスできます。

于 2011-04-05T16:39:24.123 に答える