data-structures - 永続的なデータ構造と不変のデータ構造

Question

永続的で不変のデータ構造に違いはありますか? ウィキペディアは永続性について議論する際に不変のデータ構造に言及していますが、私はこの 2 つの間に微妙な違いがあるのではないかと感じています。

Answer 1

不変性は実装手法です。とりわけ、インターフェイスである永続性を提供します。永続化 API は次のようなものです。

• version update(operation o, version v)oversionに対して操作を実行しv、新しいバージョンを返します。データ構造が不変の場合、新しいバージョンは新しい構造です (古い構造の不変部分を共有している可能性があります)。データ構造が不変でない場合、返されるバージョンは単なるバージョン番号である可能性があります。このバージョンvは有効なバージョンのままでありobserve、この更新により変更されることはありません。更新は、返されたバージョンでのみ表示され、 では表示されませんv。
• data observe(query q, version v)データ構造vを変更したり、新しいバージョンを作成したりせずに、バージョンでデータ構造を監視します。

これらの違いの詳細については、次を参照してください。

• データ構造とアプリケーションに関するハンドブックのハイム・カプランによる「永続的なデータ構造」の章
• Driscoll らによる「Making Data Structures Persistent」。
• MIT の 6.851 の 2012 年春の化身の最初の講義: 高度なデータ構造

Answer 2

はい、違いがあります。不変データ構造は、作成後に変更することはできません。それを効果的に変更する唯一の方法は、変更可能なコピーまたは類似のものを作成することです（たとえば、新しいもののコンストラクターに渡すパラメーターをわずかに変更します）。一方、永続的なデータ構造は、公開された API がデータ構造の変更を許可しているように見えるという意味で変更可能です。ただし、実際には、どのような変更も既存のデータ構造 (したがって、先行するすべての構造) へのポインターを保持します。公開された API が以前のデータ構造のサブセットへのポインターを含む可能性がある新しいポインターを返すため、それらはデータ構造を変更しているように見えます (たとえば、ツリーでは、サブツリーが変更されていないノードを指します。操作）。