拉链在实践中的表现如何？何时应该使用它们？
我认为 拉链 是个好主意；它优雅地提供了一种遍历列表或树的方法，并以功能性的方式进行看似本地的更新。
渐近地，成本似乎是合理的。但是遍历数据结构需要在每次迭代时分配内存，而普通的列表或树遍历只是指针追逐。这看起来很贵（如果我错了，请纠正我）。
成本是否令人望而却步？那么什么情况下使用拉链比较合理呢？
I think that the zipper is a beautiful idea; it elegantly provides a way to walk a list or tree and make what appear to be local updates in a functional way.
Asymptotically, the costs appear to be reasonable. But traversing the data structure requires memory allocation at each iteration, where a normal list or tree traversal is just pointer chasing. This seems expensive (please correct me if I am wrong).
Are the costs prohibitive? And what under what circumstances would it be reasonable to use a zipper?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我可以提供一个可靠的数据点：John Dias 和我有一篇论文2005 年 ML 研讨会，我们将使用拉链表示控制流图的成本与在 Objective Caml 中使用可变记录字段的成本进行了比较。我们非常惊喜地发现，使用基于拉链的控制流图的编译器的性能实际上比使用具有通过指针链接的可变记录的传统数据结构的性能稍好。我们找不到认真的分析工具来准确地告诉我们为什么拉链更快，但我怀疑原因是需要维护的不变量较少，因此指针分配相对较少。优化器也可能足够聪明，可以分摊拉链产生的一些分配成本。无论如何，拉链可以在优化编译器中使用，并且实际上有一点性能好处。
I can provide one solid data point: John Dias and I had a paper in the 2005 ML Workshop where we compared the cost of using a zipper to represent control-flow graphs with the cost of using mutable record fields in Objective Caml. We were very pleasantly surprised to find that the performance of our compiler with the zipper-based control-flow graphs was actually slightly better than the performance using a traditional data structure with mutable records linked by pointers. We couldn't find serious analysis tools to tell us exactly why the zipper was faster, but I suspect the reason was that there were fewer invariants to maintain and so relatively fewer pointer assignments. It's also possible that the optimizer was smart enough to amortize some of the allocation costs incurred by the zipper. In any case, the zipper can be used in an optimizing compiler, and there is actually a slight performance benefit.