不可變資料結構性能

我不明白作為 Set 的東西怎麼可能是不可變的並且仍然具有可接受的性能。

從我在 F# Sets 中讀到的內容，內部使用紅黑樹作為它們的實現。如果每次我們想向紅黑樹添加新的東西，我們基本上都必須重新創建它，它怎麼會有好的性能呢？我在這裡想念什麼？

雖然我要求 F# 的集合，但我認為這與任何其他具有或使用不可變資料結構的語言一樣相關。

謝謝

幾乎所有不可變集合都是某種形式的平衡樹。要創建新樹，您必須重新分配從更改（插入、刪除、“更新”）到根的路徑上的節點。只要樹是平衡的，這需要對數時間。如果您有類似 2-3-4 樹（類似於紅黑樹）的預期外度為 3，則只需 10 次分配即可處理一百萬個元素。

在資料結構被期望為純的語言中，它們確保分配速度很快。分配一個四元素節點將花費一個比較、一個增量和四個儲存。在許多情況下，您可以將比較成本分攤到多個分配中。

如果您想了解更多關於這些結構如何工作的資訊，一個很好的來源是Chris Okasaki 的Purely Functional Data Structures。

引用自：https://stackoverflow.com/questions/3233473