1

Map.remove元のマップを同じままにして、新しいマップ構造を返すようです。

どうして複雑さはまだO（lg n）なのか？

4

2 に答える 2

6

以前のマップのほとんどは、新しいマップによって共有されます。小さな部分だけが異なります。不変のデータ構造が驚くほどうまく機能する理由については、ChrisOkasakiの論文PurelyFunctionalDataStructuresですべて読むことができます。

于 2013-02-16T04:10:38.367 に答える
6

これで直観が得られる場合は、O(1)Stack.pop を使用したスタックの実装を示します。これは、前の構造を変更せずに新しい構造を返します ( test2 回ポップする方法を参照してください)。

type 'a stack = Stack of 'a list
let empty = Stack []
let push x (Stack xs) = Stack (x :: xs)
let pop = function
  | Stack [] -> raise Not_found
  | Stack (x::xs) -> x, Stack xs


(* testing the structure in the toplevel *)

# let test = push 1 (push 2 (push 3 empty));;
val test : int stack = Stack [1; 2; 3]
# let (n, test2) = pop test;;
val n : int = 1
val test2 : int stack = Stack [2; 3]
# pop test2;;
- : int * int stack = (2, Stack [3])
# (* but the starting stack 'test' is still available *)
  pop test;;
- : int * int stack = (1, Stack [2; 3])

一部の構造が機能的であり、他の構造が必須であるのはなぜですか?

これはアルゴリズムの問​​題に要約されます。ほとんどのデータを構造の異なるコピー間で共有できるように、必要な操作を実装できるというプロパティを持つ、いわゆる「純粋に機能的なデータ構造」があります。これはエイリアシングに大きく依存していることに注意してください。 、これらの構造の要素が可変である場合、観察可能になります。

このlist例では、リストの末尾を取得すると、前のリストの一部でもある別のリストが得られるため、関連するデータのコピーはありません。for Map.remove(またはその他のマップ変更操作) では、通常、バランス ツリーのルートから関心のあるノードまでのパスを変更するため、このパス (対数の高さ) は 2 つの構造で異なりますが、ツリーの残りの部分、つまりそのパスに沿った左右のサブツリーは変更されず、両方の構造間で共有できるため、対数メモリ割り当てのみになります。

Jeffrey は、そのようなデータ構造に関する岡崎の優れた研究を指摘しました (この書籍は、このかなり高度なテーマに本当に興味がある場合にのみ、私が間違いなくお勧めする本として編集されています)。そこでは、これらのアイデアに基づく多くのデータ構造が実装されています。

しかし逆に、この方法で永続化するのが難しい構造もあります。通常、配列は多数の要素を含む非常にフラットな構造です。したがって、配列の変更されたバージョンを返したい場合は、基本的に、既存の配列をその場で変更する (以前のバージョンを失うため、永続的ではない) か、配列全体を新しいバージョンにコピーする必要があります (線形時間とメモリ コスト）。前の例が機能したのは、コピーなしで単独で使用できる独立したサブ構造 (バランス ツリーのサブツリー、リストの末尾) を持ついくつかの間接化があるためです。しかし、配列はそのような独立した部分構造を持たないフラットな構造にすぎません。しかし、これは興味深いパフォーマンスのトレードオフになる可能性があります。間接参照がないことが、まさに配列アクセスが一定時間である理由です (ここではキャッシュのことは忘れてください)。O(log n)O(1)小さいですが、実際には配列よりも賢明です)。

ハッシュテーブルが変更可能である理由は、それらが配列の上に実装されているためです。ハッシュテーブルは「バケット」の配列であり (リストとして実装されるか、賢い場合はツリー データ構造として実装されます)、各バケットには、配列内の同じキーにハッシュされるすべての要素が含まれます。ハッシュテーブルを更新するということは、バケットを更新することを意味します (これは永続的な方法で行うことができます) が、次に配列を更新する必要があり、これは上記と同じ理由で永続的ではありません。

すべてが失われるわけではないことに注意してください。そのようなデータ構造の永続的なバージョンを考え出すことができます。コストを支払うことでいつでもそれを行うことができO(log n)ます (可変メモリを整数からものへの永続的なバランスのとれたツリーとして表現することにより) が、ほとんどの場合、賢く、それよりも高速な永続的なデータ構造を使用することもできます。永続性に関係のない対応物よりも少し遅くなります。さまざまなトレードオフが関係していますが、アプリケーションに永続性が必要な場合(たとえば、状態を頻繁にスナップショットする必要があるシステムの状態を表しており、場合によっては以前のバージョンにバックトラックする必要がある場合) は、それらの代替手段があると便利です。 .

この流れで、永続配列に関するこの議論 と、Clojureコミュニティ (Clojure は並行性に焦点を当てた言語であるため、賢明に変更可能な状態は、永続的なデータ構造の領域でいくつかのかなり興味深い研究をもたらしました)。

于 2013-02-16T07:30:01.940 に答える