拉链在实践中的表现如何？何时应该使用它们？

StackOverflow https://stackoverflow.com/questions/2531753

题

我认为 拉链 是一个美好的主意；它优雅地提供了一种遍历列表或树的方法，并以功能性的方式进行看似本地的更新。

渐近地，成本似乎是合理的。但是遍历数据结构需要在每次迭代时分配内存，而普通的列表或树遍历只是指针追逐。这看起来很贵（如果我错了，请纠正我）。

成本是否令人望而却步？那么什么情况下使用拉链比较合理呢？

有帮助吗？

解决方案

我可以提供一个可靠的数据点：约翰·迪亚斯和我有一个 2005 年 ML 研讨会上的论文 我们将使用拉链表示控制流图的成本与在 Objective Caml 中使用可变记录字段的成本进行了比较。我们非常惊喜地发现，使用基于拉链的控制流图的编译器的性能实际上比使用具有通过指针链接的可变记录的传统数据结构的性能稍好。我们找不到严肃的分析工具来准确地告诉我们 为什么 拉链速度更快，但我怀疑原因是需要维护的不变量较少，因此指针分配相对较少。优化器也可能足够聪明，可以分摊拉链产生的一些分配成本。任何状况之下， 拉链可以用在优化编译器中，实际上有一点性能 益处.

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top