如何處理可變性與性能之間的樹結構折衷

看來，當它涉及到實現樹結構庫時，我碰到了另一個問題，但這是一個至關重要的問題。如何處理可變性與性能之間的樹結構折衷

假設我有兩個核心構造函數：Tree和Node。
而Tree對象將具有管理樹的方法並獲取對Node對象的引用。

我似乎無法解決的問題是，似乎Node對象（和他們的孩子）必須是不可變的。我們不希望的是，該庫的用戶可以發生變異的內部結構：

var childNodes = Tree.findNode(5).children; 
var node = children[0]; 
node = "overwrite with something";

或

var parentNode = Tree.findNode(5).parent; 
parentNode.children = { text: "Doesn't realize this will change the original node's children" };

它會影響當前的樹和搞砸了的內部運作。

另外，如果我會假設使用不可變的對象/數組，它意味着連續的副本。
假設我想將10個隨機節點通過樹結構移動到（在）單個節點下。這意味着製作副本並重新分配整個數組以便改變它們。（我們不知道陣列會有多久！）。這對於可變數據結構沒有成本的東西似乎是巨大的矯枉過正。它感覺在我的脊椎上，它的編碼方式也會變得麻煩得多。

我已經嘗試了很多解決方法，但最終都面臨同樣的困境。
我該如何解決這個問題？

編輯：幾乎忘了提及我使用數組作爲節點子節點，因爲順序對我的用例很重要。

來源

2016-05-18 Trace

您是否嘗試過使用對象獲取器/設置器來創建一種不可變形式？這就是我通過[relational-json]（https://github.com/SebastienDaniel/relational-json）管理它的方式。看看錶格的方法，它們也覆蓋了數組。而性能。是相當體面的。沒有可變物體附近，但仍然足以用於生產。 –

@SebastienDaniel事情是，我不知道它如何改變這個問題。從某種意義上說，（我認爲）它在涉及對象時仍然會返回一個引用，並且不會使其不可變。我讀過getters/setters是非常昂貴的，我不確定這是一個很好的事情來處理很多節點... – Trace

當他們第一次出來時，他們「非常昂貴」，編譯器得到了很多更好。授予，如果你要返回對象，而不僅僅是基元，那麼你可能想看看[ImmutableJS]（https://facebook.github.io/immutable-js/） –

我決定去用不可變的節點對象;這是爲了禁止lib用戶意外地搞砸內部工作。

我的擔心是關於因製作太多副本而受到影響的性能。據我所知，有一種處理不可變對象的高性能方法，這就是Immutablejs提供的開箱即用功能。
看了幾個演示文稿並閱讀了文檔後，我對他們廣泛的API感到驚喜，它將提供所需的靈活性。

策略是爲用戶提供返回不可變對象或本機Javascript對象（當使用React時，Immutable看起來非常受歡迎的選擇）之間的選擇。但是內部庫將使用Immutable對象。

@SebstienDaniel感謝您的建議，它是現貨。

來源

2016-05-20 15:04:39 Trace

如何處理可變性與性能之間的樹結構折衷

回答

相關問題