arrays - 为什么在 F# 中处理数组比列表更快

Question

我正在检查 F# 列表和数组的性能。给定代码:

let list = [ 1.. 100000 ]
for i in 1 .. 100 do ignore ( list|>List.map(fun n -> n))

let array = [| 1.. 100000 |]
for i in 1 .. 100 do ignore ( array|>Array.map(fun n -> n))

我怀疑两者的运行时间非常相似。实际上，数组的速度要快 10 倍以上:数组需要 28 毫秒，而列表需要 346 毫秒!
这是为什么？我了解 F# 中列表的概念，并且例如将值附加到列表或获取子序列非常耗时，但在此代码中它只是迭代所有元素，因此我认为时间将非常可比。

在 Visual Studio 2012 中的 Release模式下进行测试(在 Debug模式下，数组的速度大约快 5 倍)。

Answer 1

主要区别在于数组被分配为连续的内存块 - Array.map函数知道输入数组的大小，并且可以只执行一次分配来获取结果数组的所有内存。另一方面，List.map函数需要为输入数组的每个元素单独分配一个“cons cell”。
map 的差异尤其明显。功能，因为这可以真正受益于预先分配。但是，对于较大的数据集，数组通常更快。如果您将代码更改为使用过滤(在构造过程中需要重新分配数组)，那么数组版本的速度会快 2 倍:

for i in 1 .. 100 do ignore ( list|>List.filter(fun n -> n%5=1))
for i in 1 .. 100 do ignore ( array|>Array.map(fun n -> n%5=1))

使用列表还有其他好处——因为它们是不可变的，您可以安全地共享对列表的引用。此外，克隆一个列表并在前面添加一个元素非常有效(单个单元格分配)，而对数组进行类似操作会非常慢(复制整个数组)。