CONS运算符(::) f＃中的性能

Question

在官方文档中，::比@更快。

一旦所有列表都在f＃中不变，为什么会有差异？在任何情况下，都应复制原始列表。但是，如果使用::，我们将预先准备，而如果使用@，我们将附加。它应该是相同的复杂性。

有什么区别？

Answer 1

您的假设不正确。

当您使用::进行预先准备时，原始列表实际上是不是，实际上是复制的。原始列表保留在记忆中，确切的位置，而新列表现在由新元素和指向原始列表的指针组成，即它的尾巴。

考虑一下：

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

此程序将产生以下内存布局：

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

这仅是可能的，因为列表是不变的：由于我们知道原始列表将永远不会改变，因此我们可以将其征召入伍是我们新列表的尾巴。

这种布置通常称为"持久数据结构"。单连接的列表只是此类结构中最简单的列表。

---

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

这就是为什么准备更快的原因。