copy-on-write機能を備えた純粋に機能的なデータ構造ですか？

Question

機能的なデータ構造（構造を共有できる複数のバージョンのデータ）を活用したいが、それを命令的なスタイルで変更できるようにしたい。

私が考えているのは、ゲームの履歴がすべて保存されているRPGゲームです（たとえば、時間通りに戻ることができるようにするため）。コピーオンライトを使用すると、ゲームの状態を保持している構造を単純に複製し、新しいターンを導入することで変更することができますが、以前のターン（必ずしもすべてではないかもしれません。毎回すべてをコピーしなければならないという不利益を被る。

---

たとえば、fooは地図です。

bar = foo.clone() 

fooの構造体（ツリーなど）はまだコピーされません。しかし、今から のbarはコピーとして扱われ、 を `foo 'に戻すことはできません。

baz = bar[someKey] 
baz.modifyInSomeWay() 

今

• 新しいオブジェクトが作成されます、それはbazの修正されたコピーです。
• barは、新しいbaz（おそらく の一部を保持し、fooの構造の一部）を保持する新しいマップに置き換えられます。
• fooは影響を受けません。

しかし、我々は、その後なければ...

baz.modifyAgain() 

我々はそれの最新バージョンを持っているので... bazだけで、変更することができます。 bar を変更する必要はありません。

このすべては がfoo.clone()にそれを増やし、fooとbarに関するいくつかのバージョン情報を保持し、何とかbazに渡す（それ プロキシオブジェクト行うことで？）が必要です。

また、複製された構造の一部は「履歴の一部」 になり、実行時に強制変更することはできません。

---

これでは、JavaScriptのプロトタイプを少し似ているが、変更 が上向きに伝播することができますように私はそれがより多くのです。私はバージョンコントロールシステムのようなものだと思う。

• これが行われていますか、どの程度ですか？
• これは良い考えですか？そうでない場合、それを保存する方法はありますか？
• どのように実装できますか？私はPythonのような高水準のGC-ed言語の上に構築することを考えていました。

Answer 1

Functional ("persistent") data structuresは通常、再帰的（不変のノードのうち、共通接尾辞は、ルートからの更新へのパス上にあるツリー構造の一部のみ探索木やヒープを共有している例えば単独リンクリストを構築していますアイテムはコピーが必要です）。

変更するたびにセット全体をコピーする必要があるものはすべて不良です。そのような場合は、以前のバージョンへの再帰で確認される小さな「差分」をオーバーレイする傾向があります（余分な時間がかかります）。たいていの場合、差分が大きすぎると、深いコピー/リビルドを行うことができます（償却コストはそれほど悪くはありません）。

永続的なデータ構造にはかなりのオーバーヘッドがありますが、小さなオブジェクト（JVM GCが適格）を効率的に割り当てることができれば、非常に実用的です。使用されるメモリを犠牲にしてください。これは、すべてのアップデートでフルコピーよりもずっと少なくなる可能性があります。

言語によっては、代入のための演算子のオーバーロードがなくても実現しにくい構文があると思います。 C++のLvalues（可変参照）では、非永続セマンティクスが必須です。

Answer 2

完全に不変なデータ構造を持っているだけでなく、それへの参照を保持しているラッパーを使用して、ラップされたバージョンを更新することによって動作する命令的インターフェースを公開するのと比べて、

Scalaで

class ImmutableData{ 
    def doStuff(blah : Blah) : ImmutableData = implementation 
} 

class MutableData(var wrapped : ImmutableData){ 
    def doStuff(blah : Blah) : Unit = { wrapped = wrapped.doStuff(blah); } 
} 

確かに、2つのバージョンのインターフェイスを作成する必要がありますが、セマンティクスは非常に面倒です。

Answer 3

1.これはどの程度まで行われていますか？

はい、たとえばqt5 implicit sharingを参照してください。

2.これは良い考えですか？そうでない場合、それを保存する方法はありますか？

はい、いい考えです。提案されている選択肢の1つは、完全な不変のデータ構造（命令的インタフェースで包まれている）を使用することですが、オブジェクトがデータを指す唯一のオブジェクトであっても、変更操作によってデータのコピーが作成されます（更新がない場合）、これは非効率的です。コピーオンライトアプローチを使用すると、コピーは最初の変更でのみ作成され、その後の変更によってコピーされたデータが変更されます（もちろん、同じデータへの別の参照が作成されていない場合）。

3.どのように実装できますか？私はPythonのような高水準のGC-ed言語の上に構築することを考えていました。

1つの方法は、qtのように参照カウントを使用することです（説明はhereを参照）。これを実装するには、代入演算子のオーバーロードまたは明示的なメソッド呼び出し（bar = foo.clone()など）が必要ですが、壊れやすいかもしれません。cloneに電話してbar = fooと忘れるとどうなりますか？

あなたが言ったように、他にもプロキシオブジェクトを作成する可能性があります。たとえば、pycow（Python実装）を参照してください。