30

不変のデータ構造としてdeque（つまり、両端キュー）を実装する方法については、しばらく考えていました。

これを行うにはさまざまな方法があるようです。AFAIK、不変のデータ構造は一般に階層的であるため、アイテムの挿入や削除などの操作を変更した後、その大部分を再利用できます。

Eric Lippertのブログには、このトピックに関する2つの 記事と、C＃でのサンプル実装があります。

彼の実装は両方とも、実際に必要なものよりも複雑であると私は思います。dequesは、ツリーの「左」（前面）と「右」（背面）でのみ要素を挿入または削除できるバイナリツリーとして単純に実装できませんでしたか？

                               o
                              / \
                             …   …
                            /     \
                           …       …
                          / \     / \
              front -->  L   …   …   R  <-- back

さらに、ツリーは回転と合理的にバランスが保たれます。

  • 前部への挿入時または後部からの取り外し時の右回転、および
  • 前面から取り外したり、背面に挿入したりすると、左に回転します。

エリック・リッパートは、私の意見では、私が深く尊敬している非常に賢い人ですが、彼は明らかにこのアプローチを考慮していませんでした。それで、それは正当な理由でしたか？dequesを実装するための私の提案された方法はナイーブですか？

4

4 に答える 4

46

ダニエルが指摘したように、AVLや赤黒木などのよく知られたバランスの取れた探索木で不変の両端キューを実装すると、Θ（lg n）の最悪の場合の複雑さが生じます。Lippertが説明する実装の一部は一見複雑に見えるかもしれませんが、バランスの取れたツリーと2つの単純なアイデアから構築された、o（lg n）の最悪、平均、または償却の複雑さを持つ不変の両端キューが多数あります。

  1. 棘を逆にする

    従来の平衡探索木で両端キュー操作を実行するには、端にアクセスする必要がありますが、中央にしかアクセスできません。左端に到達するには、最終的に行き止まりに到達するまで、左の子ポインターをナビゲートする必要があります。ナビゲーションの手間をかけずに、左端と右端へのポインタがあることが望ましいでしょう。実際、ルートノードに頻繁にアクセスする必要はありません。両端へのアクセスがO（1）になるように、バランスの取れた探索木を保存し​​ましょう。

    これは、通常AVLツリーを格納する方法のCの例です。

    struct AVLTree {
  const char * value;
  int height;
  struct AVLTree * leftChild;
  struct AVLTree * rightChild;
};

    エッジから開始してルートに向かって移動できるようにツリーを設定するには、ツリーを変更し、ルートから左端と右端の子へのパスに沿ってすべてのポインターを逆に格納します。（これらのパスは、それぞれ左スパインおよび右スパインと呼ばれます）。単一リンクリストを逆にするのと同じように、最後の要素が最初の要素になるため、左端の子に簡単にアクセスできるようになります。

    これを理解するのは少し難しいです。説明を助けるために、これを左脊椎に対してのみ行ったと想像してください。

    struct LeftSpine {
  const char * value;
  int height;
  struct AVLTree * rightChild;
  struct LeftSpine * parent;
};

    ある意味で、左端の子はツリーの「ルート」になります。このように木を描いた場合、それは非常に奇妙に見えますが、通常の木の描画を取り、左の背骨のすべての矢印を逆にすると、LeftSpine構造体の意味がより明確になるはずです。ツリーの左側にすぐにアクセスできるようになりました。右の背骨についても同じことができます。

    struct RightSpine {
  double value;
  int height;
  struct AVLTree * leftChild;
  struct RightSpine * parent;
};

    左右の背骨と中央の要素の両方を保存すると、両端にすぐにアクセスできます。リバランス操作では左または右のスパイン全体をトラバースする必要があるため、挿入と削除はまだΩ（lg n）である可能性がありますが、左端と右端の要素を表示するだけでO（1）になります。

    この戦略の例は、SMLおよびJavaでの実装で純粋関数型のtreapを作成するために使用されます（詳細なドキュメント）。これは、o（lg n）パフォーマンスを備えた他のいくつかの不変の両端キューでも重要なアイデアです。

  2. ラバレンシング作業を制限する

    上記のように、AVLツリーの左端または右端に挿入すると、スパインを通過するのにΩ（lg n）時間がかかる場合があります。これを示すAVLツリーの例を次に示します。

    完全な二分木は、誘導によって次のように定義されます。

    • 高さ0の完全な二分木は空のノードです。
    • 高さn+1の完全な二分木には、子として高さnの完全な二分木を持つルートノードがあります。

    完全な二分木の左側に要素をプッシュすると、必然的にツリーの最大の高さが増加します。上記のAVLツリーはその情報を各ノードに格納し、完全な二分木の左側のスパインに沿ったすべてのツリーも完全な二分木であるため、たまたま完全な二分木であるAVLdequeの左側に要素をプッシュします。左側のスパインに沿ってΩ（lgn）の高さの値をインクリメントする必要があります。

    （これに関する2つの注意事項：（a）ノードの高さを維持せずにAVLツリーを保存できます。代わりに、バランス情報（左背、右背、さらには）のみを保持します。これによってパフォーマンスが変わることはありません。上記の例（b）AVLツリーでは、Ω（lg n）バランスまたは高さ情報の更新だけでなく、Ω（lg n）リバランス操作も必要になる場合があります。これの詳細は思い出せません。挿入ではなく、削除のみを行ってください。）

    o（lg n）deque操作を実行するには、この作業を制限する必要があります。バランスの取れたツリーで表される不変の両端キューは、通常、次の戦略の少なくとも1つを使用します。

    • リバランスが必要になる場所を予測します。o（lg n）のリバランスが必要なツリーを使用しているが、そのリバランスが必要な場所がわかっていて、そこにすばやく到達できる場合は、o（lg n）時間で両端キュー操作を実行できます。これを戦略として使用する両端キューは、両端キューに2つのポインター（上記で説明したように、左右のスパインの端）だけでなく、スパインに沿ってより高い位置への少数のジャンプポインターを格納します。Deque操作は、O（1）時間でジャンプポインタが指すツリーのルートにアクセスできます。リバランス（またはノード情報の変更）が必要なすべての場所でo（lg n）ジャンプポインタが維持されている場合、両端キュー操作にo（lg n）時間がかかる可能性があります。

      （もちろん、ジャンプポインターによってポイントされるスパイン上のツリーは、スパイン上の子によってもポイントされるため、これにより、ツリーは実際にはダグになります。不変のデータ構造は、通常、非ツリーグラフとうまく調和しません。複数の他のノードが指すノードを置き換えるには、そのノードを指す他のすべてのノードを置き換える必要があります。これは、ジャンプしないポインタを削除し、dagをツリーに戻すだけで修正されるのを確認しました。その後、リストのリストとしてジャンプポインタを含む単一リンクリスト。各従属リストには、そのリストの先頭とそのジャンプポインタの間のすべてのノードが含まれます。これには、部分的に重複するジャンプポインタを処理するための注意が必要であり、完全な説明はおそらくこれはさておき、適切ではありません。）

      これは、Tsakalidisが彼の論文「ローカライズされた検索のためのAVLツリー」で使用したトリックの1つであり、リラックスしたバランス状態でAVLツリーに対してO（1）両端キュー操作を可能にします。これは、 KaplanとTarjanが論文「カテネーションを使用した純粋に機能的なリアルタイムの両端キュー」で使用した主なアイデアであり、MihaesauとTarjanによるその後の改良でもあります。Munro etal。の「DeterministicSkipLists」もここで言及する価値がありますが、ツリーを使用してスキップリストを不変の設定に変換すると、プロパティが変更され、終わり近くでこのような効率的な変更が可能になる場合があります。翻訳の例については、Messeguerの「スキップツリー、並行アプローチでリストをスキップするための代替データ構造」を参照してください。ディーンとジョーンズの「スキップリストと二分探索木の間の二重性の探求」、およびラムルーとニッカーソンの「Bツリーと決定論的スキップリストの同等性について」。

    • まとめて作業してください。上記の完全な二分木の例では、プッシュ時にリバランスは必要ありませんが、Ω（lg n）ノードの高さまたはバランス情報を更新する必要があります。実際にインクリメントを行う代わりに、端のスパインにインクリメントが必要であるとマークするだけで済みます。

      このプロセスを理解する1つの方法は、2進数にたとえることです。（2 ^ n）-1は、n1の文字列によってバイナリで表されます。この数値に1を加算する場合は、すべての1を0に変更してから、最後に1を加算する必要があります。次のHaskellは、2進数を空でないビットの文字列としてエンコードします。

      data Bit = Zero | One

type Binary = (Bit,[Bit])

incr :: Binary -> Binary
incr (Zero,x) = (One,x)
incr (One,[]) = (Zero,[One])
incr (One,(x:xs)) = 
    let (y,ys) = incr (x,xs)
    in (Zero,y:ys)

      incrは再帰関数であり、形式の数の場合(One,replicate k One)、incrはそれ自体をΩ（k）回呼び出します。

      代わりに、等しいビットのグループをグループ内のビット数だけで表す場合があります。隣接するビットまたはビットのグループは、等しい場合（数ではなく値で）、1つのグループに結合されます。O（1）時間で増分できます。

      data Bits = Zeros Int | Ones Int

type SegmentedBinary = (Bits,[Bits])

segIncr :: SegmentedBinary -> SegmentedBinary
segIncr (Zeros 1,[]) = (Ones 1,[])
segIncr (Zeros 1,(Ones n:rest)) = (Ones (n+1),rest)
segIncr (Zeros n,rest) = (Ones 1,Zeros (n-1):rest)
segIncr (Ones n,[]) = (Zeros n,[Ones 1])
segIncr (Ones n,(Zeros 1:Ones m:rest)) = (Zeros n,Ones (m+1):rest)
segIncr (Ones n,(Zeros p:rest)) = (Zeros n,Ones 1:Zeros (p-1):rest)

      segIncrは再帰的ではなく、Intでプラスとマイナス以外の関数を呼び出さないため、O（1）時間がかかることがわかります。

      上記の「リバランスが必要になる場所を予測する」というタイトルのセクションで言及されている両端キューの一部は、実際には「冗長番号システム」と呼ばれる別の数値に着想を得た手法を使用して、リバランス作業をO（1）に制限し、すばやく見つけます。冗長な数値表現は魅力的ですが、おそらくこの議論には遠すぎます。Elmasry et al。の「厳密に規則的な記数法とデータ構造」は、そのトピックについて読み始めるのに悪い場所ではありません。Hinzeの「片側フレキシブルアレイのブートストラップ」も役立つかもしれません。

      「データ構造を永続化する」では、Driscolletal。彼らがTsakalidisに起因する怠惰な色の変更について説明します。彼らはそれを赤黒木に適用し、挿入または削除後にO（1）回転でバランスを取り直すことができます（ただし、Ω（lg n）の色を変更します）（Tarjanの「O（1）回転でのバランスの取れたツリーの更新」を参照）。アイデアの核心は、色を変更する必要があるが回転しないノードの大きなパスをマークすることです。同様のアイデアが、Brown＆Tarjanの「高速マージアルゴリズム」の古いバージョンのAVLツリーで使用されています。（同じ作品の新しいバージョンは2〜3ツリーを使用しています。新しいバージョンを読んだことがなく、怠惰な色の変更などの手法を使用しているかどうかもわかりません。）

    • ランダム化します。上記のTreapは、機能的な設定で実装できるため、平均してO（1）時間で両端キュー操作を実行できます。dequesは要素を検査する必要がないため、平均入力が高速な単純な（リバランスなしの）二分探索木とは異なり、この平均は悪意のある入力劣化パフォーマンスの影響を受けません。Treapは、データのランダム性に依存するのではなく、ランダムビットの独立したソースを使用します。

      永続的な設定では、treapは、（a）古いバージョンのデータ構造を使用し、（b）操作のパフォーマンスを測定できる、悪意のある入力によるパフォーマンスの低下の影響を受けやすい可能性があります。最悪の場合のバランス保証がないため、まれに発生するはずですが、treapはかなり不均衡になる可能性があります。攻撃者が長時間かかる両端キュー操作を待機している場合、不均衡な可能性のあるツリーを測定して利用するために、同じ操作を繰り返し開始できます。

      これが問題にならない場合、treapは魅力的に単純なデータ構造です。それらは、上記のAVLスパインツリーに非常に近いものです。

      上記のスキップリストは、O（1）平均時間deque操作を使用した機能実装にも適している可能性があります。

      リバランス作業を制限するための最初の2つの手法では、データ構造に複雑な変更を加える必要がありますが、通常は、両端キュー操作の複雑さを簡単に分析できます。ランダム化は、次の手法とともに、データ構造は単純ですが、分析はより複雑です。SeidelとAragonによる元の分析は簡単ではなく、上記の論文にあるよりも高度な数学を使用した正確な確率の複雑な分析があります。Flajoletetal。の「ランダム二分探索木のパターン」を参照してください。

    • 償却します。根元から見たときに（上記の「棘を逆にする」で説明したように）、O（1）の償却された挿入および削除時間を提供するバランスの取れたツリーがいくつかあります。個々の操作にはΩ（lg n）の時間がかかる場合がありますが、ツリーは非常に良好な状態になり、高価な操作に続く多数の操作が安価になります。

      残念ながら、この種の分析は、古いバージョンのツリーがまだ存在している場合は機能しません。ユーザーは、安価な操作を介入することなく、古い、ほぼ不均衡なツリーに対して何度も操作を実行できます。

      永続的な設定で償却範囲を取得する1つの方法は、ChrisOkasakiによって発明されました。償却がデータ構造の任意の古いバージョンを使用する機能をどのように生き残るかを説明するのは簡単ではありませんが、私が正しく覚えていれば、この主題に関する岡崎の最初の（私が知る限り）論文にはかなり明確な説明があります。より包括的な説明については、彼の論文または彼の本を参照してください。

      私が理解しているように、2つの重要な成分があります。まず、各高価な操作の前に特定の数の安価な操作が発生することを保証するのではなく（通常の償却アプローチ）、実際にその特定の高価な操作を前に指定して設定しますそれを支払う安価な操作を実行します。場合によっては、多くの安価なステップが介在した後にのみ、操作が開始（および終了）されるようにスケジュールされます。その他の場合、操作は実際には将来O（1）ステップのみでスケジュールされますが、安価な操作が高価な操作の一部を実行し、後でさらにスケジュールを変更する場合があります。高価な操作を何度も繰り返しようとしている敵が、実際には毎回同じスケジュールされた操作を再利用している場合。この共有は、2番目の要素が出てくるところです。

      計算は怠惰を使用して設定されます。遅延値はすぐには計算されませんが、実行されると、その結果が保存されます。クライアントが最初に遅延値を検査する必要があるとき、その値が計算されます。後でクライアントは、キャッシュされた値を再計算せずに直接使用できます。

      #include <stdlib.h>

struct lazy {
  int (*oper)(const char *);
  char * arg;
  int* ans;
};

typedef struct lazy * lazyop;

lazyop suspend(int (*oper)(const char *), char * arg) {
  lazyop ans = (lazyop)malloc(sizeof(struct lazy));
  ans->oper = oper;
  ans->arg = arg;
  return ans;
}

void force(lazyop susp) {
  if (0 == susp) return;
  if (0 != susp->ans) return;
  susp->ans = (int*)malloc(sizeof(int));
  *susp->ans = susp->oper(susp->arg);
}

int get(lazyop susp) {
  force(susp);
  return *susp->ans;
}

      一部のMLにはLazinessコンストラクトが含まれており、Haskellはデフォルトで怠惰です。内部的には、怠惰は突然変異であり、一部の著者はそれを「副作用」と呼んでいます。そもそも不変のデータ構造を選択した理由が何であれ、そのような副作用がうまく機能しない場合、それは悪いと見なされるかもしれませんが、一方で、怠惰を副作用として考えると、Kaplan、Okasaki、Tarjanによる「SimpleConfluently Persistent Catenable Lists」というタイトルの論文で言及されているように、永続データ構造に対する従来の償却分析手法。

      高価な操作の計算を繰り返し強制しようとしている上からの敵をもう一度考えてみてください。怠惰な価値の最初の力の後、残りのすべての力は安いです。

      彼の著書の中で、岡崎は、各操作に必要なO（1）償却時間で両端キューを作成する方法を説明しています。これは本質的にB+ツリーであり、すべての要素が葉に格納され、ノードの子の数が異なる場合があり、すべての葉が同じ深さにあるツリーです。岡崎は、前述の背骨反転法を使用し、葉の要素の上に背骨を吊るします（つまり、レイジー値として保存します）。

      「フィンガーツリー：単純な汎用データ構造」と呼ばれるHinzeとPatersonによる構造は、Okasakiによって設計された両端キューと、KaplanおよびTarjanの「catablesortedlistの純粋関数型表現」の中間にあります。HinzeandPatersonの構造は非常に人気があります。

      償却分析を理解するのがいかに難しいかの証拠として、HinzeとPatersonのフィンガーツリーは怠惰なしに実装されることが多く 、時間境界はO（1）ではなくO（lg n）になります。怠惰を使用しているように見える1つの実装は、functional-dotnetの実装です。このプロジェクトには、C＃でのレイジー値の実装も含まれています。これは、上記の説明が不足している場合に説明に役立つ可能性があります。

dequesはバイナリツリーとして実装できますか？はい。永続的に使用した場合の最悪の場合の複雑さは、EricLippertによって提示されたものよりも悪くはありません。ただし、Ericのツリーは、実際には、永続的な設定でO（1）deque操作を取得するほど複雑ではありませんが、償却されたパフォーマンスを受け入れる場合は、複雑さのマージンがわずかです（中心が怠惰になります）。Treapの別の、しかし単純なビューは、あまりトリッキーではない敵を想定して、機能的な設定でO（1）の期待されるパフォーマンスを得ることができます。機能的な設定でツリーのような構造を使用してO（1）の最悪の場合の両端キュー操作を取得するには、Ericの実装よりもかなり複雑にする必要があります。

最後の2つのメモ（これは非常に興味深いトピックであり、後で追加する権利を留保します）:-)

  1. 上記のほとんどすべての両端キューは、指探索木でもあります。機能設定では、これは、O（lg（min（i、ni）））時間でi番目の要素で分割でき、サイズnとmの2つのツリーをO（lg（min（n、m））で連結できることを意味します。 ）） 時間。

  2. ツリーを使用しない両端キューを実装する2つの方法を知っています。岡崎は、彼の本と論文、そして私が上でリンクした論文の中でそれを提示しています。もう1つは、「グローバル再構築」と呼ばれる手法を使用しており、ChuangとGoldbergの「リアルタイムデキュー、マルチヘッドチューリングマシン、および純粋関数型プログラミング」で紹介されています。

于 2010-07-18T04:48:18.703 に答える
5

平衡二分木を使用する場合、両端の挿入と削除はO（lg N）です（平均と最悪の場合の両方）。Eric Lippertの実装で使用されるアプローチはより効率的で、平均的なケースでは一定時間で実行されます（最悪のケースは依然としてO（lg N）です）。

不変ツリーの変更には、変更するノードのすべての親の書き換えが含まれることに注意してください。したがって、両端キューの場合、ツリーのバランスをとる必要はありません。代わりに、LノードとRノードをできるだけルートに近づけ、ツリーの中央にあるノードをさらに遠ざけることができます。

于 2010-07-17T12:27:38.560 に答える
5

他の答えはすべて素晴らしいです。ジェネリック型システムを珍しく興味深い方法で使用しているため、dequeのフィンガーツリー実装を選択したことを追加します。ほとんどのデータ構造はその構造が再帰的ですが、この手法では、これまで見たことのない型システムにも再帰が適用されます。私はそれが一般的な興味があるかもしれないと思いました。

于 2010-07-18T15:38:22.290 に答える
2

dequesは、ツリーの「左」（前面）と「右」（背面）でのみ要素を挿入または削除できるバイナリツリーとして単純に実装できませんでしたか？

絶対。高さバランスの取れたツリー、特にAVLツリーの修正バージョンは、実装が非常に簡単です。ただし、ツリーベースのキューをn要素で満たすにはO(n lg n)時間がかかることを意味します。可変の対応するものと同様のパフォーマンス特性を持つ両端キューを撮影する必要があります。

左スタックと右スタックの2つのスタックを使用して、すべての主要な操作に対して償却された定数時間操作を使用して、単純な不変の両端キューを作成できます。PushLeftとPushRightは、それぞれ左スタックと右スタックのプッシュ値に対応します。Deque.HdとDeque.Tlは、LeftStack.HdとLeftStack.Tlから取得できます。LeftStackが空の場合は、LeftStack=RightStack.ReverseおよびRightStack=空のスタックに設定します。

type 'a deque = Node of 'a list * 'a list    // '

let peekFront = function
    | Node([], []) -> failwith "Empty queue"
    | Node(x::xs, ys) -> x
    | Node([], ys) -> ys |> List.rev |> List.head
let peekRear = function
    | Node([], []) -> failwith "Empty queue"
    | Node(xs, y::ys) -> y
    | Node(xs, []) -> xs |> List.rev |> List.head
let pushFront v = function
    | Node(xs, ys) -> Node(v::xs, ys)
let pushRear v = function
    | Node(xs, ys) -> Node(xs, v::ys)
let tl = function
    | Node([], []) -> failwith "Empty queue"
    | Node([], ys) -> Node(ys |> List.rev |> List.tail, [])
    | Node(x::xs, ys) -> Node(xs, ys)

これは非常に一般的な実装であり、パフォーマンスを向上させるために最適化するのは非常に簡単です。

于 2010-07-18T22:33:13.117 に答える