具有寫入時複製功能的純功能數據結構？

我想要具有功能數據結構（可以共享結構的多個數據版本的數據）的優點，但是能夠以一種命令式樣對其進行修改。具有寫入時複製功能的純功能數據結構？

我在想什麼（以及可能的用途）：一個RPG遊戲，其中存儲了整個遊戲歷史記錄（例如，以便及時返回）。使用寫時複製，我可以簡單地克隆持有遊戲狀態的結構，並通過引入新的轉變來修改它 - 但是可以訪問較早的轉向（不一定全部都是這樣，也許只是選定的遊戲狀態快照），而沒有每次都必須複製一切的懲罰。

比方說foo是一張地圖。

bar = foo.clone()

沒有任何foo的結構（例如樹）被複制。然而，從現在開始bar被視爲一個副本，並且不允許更改傳播回到`foo'。

baz = bar[someKey] 
baz.modifyInSomeWay()

現在

一個新的對象被創建，那就是baz一個修改後的副本。
bar被替換爲新地圖，保存新的baz（可能保留一些foo的結構）。
foo不受影響。

但是，如果我們再這樣做......

baz.modifyAgain()

... baz可剛修改的，因爲我們有一個最近的版本，它。 bar 不需要更改。

所有這些都需要保持一些版本信息有關foo和bar，增加它foo.clone()，並將它傳遞給baz某種方式（通過使代理對象？）。

另外，已經被克隆的任何結構部分都成爲'歷史的一部分' 並且不能再被改變，這可以在運行時被強制執行。

這類似於JavaScript的原型了一點，但我它更因爲它允許更改向上傳播。我認爲它會像版本控制系統。

這樣做了，到了什麼程度？
這是個好主意嗎？如果沒有，是否有辦法保存它？
它如何實現？我正在考慮在Python等高級GC-ed語言之上構建它。

來源

2009-09-04 hmp

可能[pyrsistent]（https://github.com/tobgu/pyrsistent）是什麼你在尋找 – CAMOBAP

Functional ("persistent") data structures通常遞歸建立了不可變的節點（例如單鏈表其中共同後綴被共享，搜索樹或堆，其中僅所述樹結構是從根到經更新的路徑上的各部分項目需要複製）。

任何需要爲每次修改都要複製整個集合的東西都是不好的。在這些情況下，你會傾向於覆蓋較小的「差異」，這是通過遞歸到以前的版本來檢查（花費額外的時間）。每當差異變得過大時，您可以進行深度複製/重建（因此分期償還的成本不會太差）。

持久數據結構可能會產生很大的開銷，但是如果您有非常高效的小對象分配（JVM GC限定），它們可能非常實用 - 在最好的情況下，與可變等價物一樣快，只提供持久性這是以使用的內存爲代價的 - 在每次更新時，這可能遠遠小於完整副本。

根據您的語言，您可能會發現無需運算符重載進行賦值就很難實現的語法。 C++中的左值（可變引用）肯定需要非持久性語義。

來源

2009-09-04 21:36:12

與僅擁有完全不可變的數據結構，然後使用包含引用的包裝並暴露通過更新包裝版本工作的命令式接口相比，這聽起來非常複雜且容易出錯。

例如在斯卡拉

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

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

當然，這意味着你必須做出兩個版本的接口，但語義是非常好的。

來源

2009-09-05 10:06:15 DRMacIver

正確，但這意味着手動更新一切 - 我不能在任何其他不可變數據結構中使用這種MutableData 。 – hmp

我不關注。如果你想永久使用它，你可以通過解開它來獲得快照版本。 – DRMacIver

1.這是否已完成，並在多大程度上？

是的，例如參見qt5 implicit sharing。

2.這是個好主意嗎？如果沒有，是否有辦法保存它？

是的，這是一個好主意。建議的替代方案之一是使用完全不可變的數據結構（包裝在命令式界面中），但問題是，即使對象是唯一指向數據的對象，修改操作也會創建數據的副本（沒有就地更新），這是低效的。使用寫入時複製方法，僅在第一次修改中進行復制，隨後的修改會更改已複製的數據（如果未創建另一個對同一數據的引用，則偏離過程）。

3.如何實現？我正在考慮在Python等高級GC-ed語言之上構建它。

一種方法是使用引用計數，就像在qt中一樣（請參閱說明here）。要實現它將需要分配運算符超載或明確的方法調用（如bar = foo.clone()，但它可能是脆弱的，如果有人忘記調用clone而只是做bar = foo？），所以可以保持計數。

在你創建一個代理對象的其他可能性，就像你說的。參見例如pycow（一個python實現）。

來源

2016-05-10 16:08:28 malbarbo

具有寫入時複製功能的純功能數據結構？

回答

相關問題