在Scheme I中递归地构建列表时,会看到分散在Internet上的两种类型的示例.append每次迭代都附加一个新值的一个.另一个在cons列表完成后每次迭代前置新值的另一个reverse调用一次.
我的直觉是后者更快,但如果Scheme解释器缓存了列表指针的末尾或正在进行其他优化,那么前者将同样快速且可读性更高.如果解释器正在进行此优化,是否保证在所有解释器中都可用？
使用cons始终是首选.使用append非常低效,因为它总是遍历列表到最后只是为了在那里添加一个新元素,而cons在开头添加元素.没有指向列表末尾的指针,因此您建议的优化根本不会执行.
当元素构建大型列表元素这是相当重要的,因为cons是一个O(1)操作,而append为O(n) 每一个新加入的元素,以降低O(n^2)复杂性!(有一个很好的类比,请参阅:Schlemiel the Painter的算法).最后,简单地在开始时添加元素并且如果必要reverse的话在最后添加列表要便宜得多,从而实现O(n)复杂性.