爲什麼在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的發佈模式下進行測試（在調試模式下數組速度快了5倍）。

Answer 1

的主要區別是，陣列被分配爲連續的存儲器塊 - 的Array.map功能知道輸入數組的大小，並且可以執行只是一個單一的分配，以獲得所得的陣列中的所有存儲器。另一方面，List.map函數需要爲輸入數組的每個元素分別分配一個「cons單元」。

這個差別對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)) 

使用列表還有其他好處 - 因爲他們是不可變的，你可以安全地分享對列表的引用。此外，克隆一個列表並在前面添加一個元素是非常高效的（單個單元格分配），而對數組執行類似的操作會非常慢（複製整個數組）。