Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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 'Tseq 'T だったのに対して
List は 'Tlist<'T> の結合だったのでその影響もあるかもしれません。

mizutoki79
Microsoft と ネットワークとセキュリティが好きなサーバーサイドエンジニア
yumemi
みんなが知ってるあのサービス、実はゆめみが作ってます。スマホアプリ/Webサービスの企画・UX/UI設計、開発運用。Swift, Kotlin, PHP, Vue.js, React.js, Node.js, AWS等エンジニア・クリエイターの会社です。Twitterで情報配信中https://twitter.com/yumemiinc
http://www.yumemi.co.jp
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away