rev_append 与（追加或@）

Question

如果我们有两个列表l1并且l2我们想要连接它们，我们可以使用@or appendwhich is in O(n1)where n1is 的长度l1。或者我们可以rev_append根据文档使用：

equivalent to List.rev l1 @ l2, but rev_append is tail-recursive and more efficient.

那么是rev_append比 更有效@还是比 更有效List.rev + @？当我们不关心顺序时，使用它代替@and是否更好？append

Answer 1

OCaml 列表是不可变的。不需要更改第二个列表，但必须复制第一个列表，以便副本可以指向第二个列表。因此，您将不得不以某种方式遍历第一个列表。你所做的任何事情都不会改变追加的 big-O 时间复杂度。

由于只能在列表的开头添加新元素，因此如果希望结果保留第一个列表的顺序，则需要以相反的顺序遍历第一个列表。

最明显的方法是递归调用，直到到达第一个列表的末尾，然后在从每个递归调用返回时添加前缀。然而，这不是尾递归。即，它将消耗与第一个列表的长度成比例的堆栈空间。当第一个列表很长时，您可能会耗尽堆栈空间（也称为堆栈溢出）。

这就是有效的方法@。它花费的时间和堆栈空间与第一个列表的长度成正比。

另一个想法是放弃维护第一个列表的顺序。如果以相反的顺序为第一个列表添加前缀，则可以轻松地使操作尾部递归。这就是 的目的List.rev_append。它需要恒定的堆栈空间。

如果您想保持原始列表顺序，但也使用恒定的堆栈空间，您可以反转第一个列表（使用List.rev），然后使用List.rev_append。

PlainList.rev_append比它更快，@因为它不必进行内部函数调用——它可以只是一个循环。它也明显比List.revplus更快List.rev_append。

总之，如果您不关心最终订单，那么List.rev_append比 更快@，是的。而且它不会溢出堆栈。它不会快很多，因为时间复杂度基本相同。