list - F# 中的 cons 运算符 (::) 性能

Question

在官方文档中指出 :: 比 @ 快。

一旦所有列表在 F# 中都是不可变的，为什么会有区别？在任何情况下都应复制原始列表。但如果是 :: 我们将在前面，而在 @ 的情况下我们将追加。它应该是相同的复杂性。

有什么区别？

Answer 1

你的假设是不正确的。

当您添加 :: 时，实际上不会复制原始列表。原始列表保留在内存中的原处，与原来的位置完全相同，新列表现在包含新元素和指向原始列表的指针，即它的尾部。

考虑一下:

let x = [1;2;3]
let y = 4 :: x

该程序将产生以下内存布局:

 y -> 4
       \
        v
        1 -> 2 -> 3 -> (END)
        ^
       /
      x

这是唯一可能的，因为列表是不可变的:因为我们知道原始列表永远不会改变，我们可以将它征召为新列表的尾部。

这种安排通常被称为“persistent data structure”。单向链表只是此类结构中最简单的一种。

另一方面，当附加 @ 时，您确实必须复制整个原始列表。你不能重复使用它的任何部分。

这就是为什么前置更快。