F＃中的cons运算符（：:)性能

Question

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

一旦所有列表在F＃中都是不变的，为什么会有区别？无论如何，都应复制原始列表。但是如果::有的话我们会在前面加上，如果有的话我们会在后面加上@。它应该是相同的复杂性。

有什么不同？

Answer 1

您的假设是不正确的。

当您以开头时::，实际上不会复制原始列表。原始列表将保留在内存中的确切位置，而新列表现在由新元素和指向原始列表的指针（即它的尾部）组成。

考虑一下：

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

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

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

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

这种安排通常称为“ 持久数据结构 ”。单链列表只是这种结构中最简单的一种。

When appending with @, on the other hand, you do indeed have to copy the whole original list. You cannot reuse any part of it.

This is why prepending is faster.