scheme - 在 Scheme 中使用 append vs cons 和 reverse 是否更快/传统？

Question

在 Scheme 中递归构建列表时，我看到两种类型的示例散布在互联网上。其中一个新值附加了 append每一次迭代。另一个在每次迭代前都添加一个新值 cons然后列表完成后reverse被调用一次。

我的直觉是后者更快，但如果 Scheme 解释器缓存了列表指针的结尾或正在做一些其他优化，那么前者将同样快速且更具可读性。如果解释器正在做这个优化，它是否保证在所有解释器中都可用？

Answer 1

使用 cons总是首选。使用 append效率非常低，因为它总是遍历列表到最后只是为了在那里添加一个新元素，而 cons在开头添加元素。没有指向列表末尾的指针，因此您建议的优化根本没有执行。

当逐个元素构建大型列表时，这很重要，如 cons是 O(1)操作，而 append是 O(n)对于添加的每个新元素，降级为 O(n^2)复杂! (有关一个很好的类比，请参阅: Schlemiel the Painter's algorithm )。最后，在开始时简单地添加元素要便宜得多，如有必要 reverse列表最后，实现O(n)复杂。