performance - zipper 在实践中的性能如何？何时使用？

Question

我认为zipper是个好主意；它优雅地提供了一种遍历列表或树并使功能看起来像本地更新的方法。

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

费用高昂吗？在什么情况下使用 zipper 合理？

Answer 1

我可以提供一个可靠的数据点:John Dias和我有一个paper in the 2005 ML Workshop，我们在其中比较了使用 zipper 来表示控制流图的成本和在Objective Caml中使用可变记录字段的成本。我们非常惊讶地发现我们的编译器具有基于 zipper 的控制流图的性能实际上比使用具有指针链接的可变记录的传统数据结构的性能稍好。我们找不到真正的分析工具来确切地说明为什么 zipper 速度更快，但是我怀疑原因是要维护的不变式较少，指针分配也相对较少。优化器也可能足够聪明，可以分摊 zipper 产生的一些分配成本。无论如何，zipt的都可以在优化的编译器中使用，实际上在性能上有一点好处。