函数式编程：不可变数据结构的效率

Question

16

我不明白函数式编译器如何让处理不可变数据结构的代码运行更快，而且不会导致堆栈溢出等问题。

例如，在树中进行插入操作时，必须在添加新节点之前复制整个树并返回已复制的树，而命令式语言只需要在新节点上添加指针即可。如果插入操作运行了数百万次，它将占用大量内存，并且当树越来越大时，复制过程会变得越来越慢。那么函数式编译器是如何进行优化的呢？

- romerun

4个回答

7

编译器不会真正优化这个，这是编码时需要专门进行编程的事情。如何做到这一点的技巧在优秀的纯函数数据结构（书籍、论文）中有所解释。请参考：书籍，论文。

- Adam Goode

1

- Todd Stout

-5

如果垃圾回收器在工作，那么当旧的数据结构副本不再被使用时，它们将被回收。

- Barry Brown

我可以问一下为什么要对这个答案进行投票吗？假设我想通过一些修改来移动相同的集合并保持其功能，了解 GC 将收集不再使用的部分是否有帮助？ - Ashkan Kh. Nazary

1

它完全没有回答问题。 - devoured elysium

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Brian · Accepted Answer

您不需要复制整个树来进行更改；您可以共享大部分结构。例如，请参见此博客中的图表，或者Rich Hickey在关于Clojure的这个演讲中（在演讲的一半左右有关哈希尝试的讨论）。