7

機能的なデータ構造 (構造を共有できる複数のバージョンのデータ) の利点を生かしながら、命令型のスタイルで変更できるようにしたい。

私が考えていること (および考えられる用途): ゲーム履歴全体が保存される RPG ゲーム (たとえば、時間をさかのぼることができるようにするため)。コピー オン ライトを使用して、ゲームの状態を保持する構造を単純に複製し、新しいターンを導入することでそれを変更することができました。毎回すべてをコピーしなければならないというペナルティ。

foo地図だとしましょう。

bar = foo.clone()

fooの構造 (ツリーなど) はまだコピーされていません。ただし、bar今後はコピーとして扱われ、変更が「foo」に伝播することは許可されません。

baz = bar[someKey]
baz.modifyInSomeWay()

今

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

しかし、もしそうなら...

baz.modifyAgain()

...baz最新バージョンがあるため、変更するだけです。bar 変更する必要はありません。

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

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

これは JavaScript のプロトタイプに少し似ていますが、変更が上方に伝播できるため、より似ています。バージョン管理システムのようなものになると思います。

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

3 に答える 3

8

機能的な (「永続的な」) データ構造は、通常、不変のノードから再帰的に構築されます (たとえば、共通の接尾辞が共有される単一リンク リスト、検索ツリーまたはヒープ (ルートから更新された項目はコピーする必要があります)。

変更ごとにセット全体をコピーする必要があるものはすべて悪いです。そのような場合、以前のバージョンへの再帰でチェックされる (余分な時間がかかる) 小さな「差分」をオーバーレイする傾向があります。ときどき、差分が大きくなりすぎたときに、ディープ コピー/再構築を行うことができます (そのため、償却コストはそれほど悪くありません)。

永続的なデータ構造にはかなりのオーバーヘッドが生じる可能性がありますが、小さなオブジェクトを非常に効率的に割り当てている場合 (JVM GC が適している場合)、それらは非常に実用的です。使用されるメモリ - これは、更新ごとに完全なコピーよりもはるかに少なくなる可能性があります。

言語によっては、代入のために演算子をオーバーロードしないと、目的の構文を実現するのが難しい場合があります。C++ の左辺値 (変更可能な参照) には、確実に非永続的なセマンティクスが必要です。

于 2009-09-04T21:36:12.077 に答える
0

これは、完全に不変のデータ構造を持ち、それへの参照を保持し、ラップされたバージョンを更新することによって機能する命令型インターフェイスを公開するラッパーを使用することに比べて、非常に複雑でエラーが発生しやすいように思えます。

例えばScalaで

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

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

確かに、インターフェイスの 2 つのバージョンを作成する必要があることを意味しますが、セマンティクスははるかに正気です。

于 2009-09-05T10:06:15.613 に答える