F# のコレクションを結合していった時の速度比較

fsi にて実行

open System
let max = 100000
let inline showTime name start = printfn "%s: %d" name (DateTime.UtcNow.Ticks - start)

let mutable start = DateTime.UtcNow.Ticks
let arrm = Array.zeroCreate<int> max
for i in 0..max - 1 do arrm.[i] <- i
showTime "array mutable" start

start = DateTime.UtcNow.Ticks
let mutable arra = [||]
for i in 0..max - 1 do arra <- Array.append arra [| i |]
showTime "array append" start

start = DateTime.UtcNow.Ticks
let mutable arrc = [||]
for i in 0..max - 1 do arrc <- Array.concat [| arrc; [| i |] |]
showTime "array concat" start

start <- DateTime.UtcNow.Ticks
let mutable lst = List.Empty
for i in 0..max - 1 do lst <- i :: lst
showTime "list" start

start <- DateTime.UtcNow.Ticks
let mutable S = seq { yield 0 }
for i in 0..max - 1 do S <- Seq.append S (seq { yield i })
showTime "sequence" start
;;

array mutable: 0
array append: 115221834
array concat: 195307635
list: 9977
sequence: 99732

とりあえず Array を結合するのはすっごい遅いことが分かった。

ちょっと max を大きくしてみて

open System
let max = 10000000
let inline showTime name start = printfn "%s: %d" name (DateTime.UtcNow.Ticks - start)

let mutable start = DateTime.UtcNow.Ticks
let arrm = Array.zeroCreate<int> max
for i in 0..max - 1 do arrm.[i] <- i
showTime "array mutable" start

start <- DateTime.UtcNow.Ticks
let mutable lst = List.Empty
for i in 0..max - 1 do lst <- i :: lst
showTime "list" start

start <- DateTime.UtcNow.Ticks
let mutable S = seq { yield 0 }
for i in 0..max - 1 do S <- Seq.append S (seq { yield i })
showTime "sequence" start
;;

type	time
Array	249332
List	8128251
Seq	50744520

Seq はyieldして生成するものであって繰り返し結合する使い方をするものじゃないんだなという感じ

当たり前ですが、毎回新しいオブジェクトを作る必要が無いようにArrayにサイズ指定して作ってそのアイテムを編集していくのが一番早いですね。

複数のコレクションを繰り返し結合する必要があるときはListが有利かもしれません。

ただ、Array は 'T array と 'T array
Seq は seq 'T と seq 'T だったのに対して
List は 'T と list<'T> の結合だったのでその影響もあるかもしれません。