a wandering wolf

Does a wandering wolf dreams of a wondering, sometimes programming sheep?

このエントリーをはてなブックマークに追加

list と array、生成はどちらが速い?

TL;DR

性能が欲しけりゃ配列を使え。ただし、コレクションの使い方次第。あと、内包表記は安易に使うな。

はじめに

きっかけは、ふとした疑問からでした。

ちょうど速度的な性能についてあれこれ企てているところで、このツイートもそうした背景からのものでした。

測定せよ

性能の話は、やはり測定して見るところから始めるべきだと思います。なので、次のような測定関数を書いてみました。

let timer f =
    let sw = System.Diagnostics.Stopwatch()
    sw.Start()
    let xs = f()
    sw.Stop()
    printfn "Finish initializing %s" <| xs.GetType().Name
    printfn "elapsed time: %s" <| sw.Elapsed.ToString()

これで、配列とリストで次のような処理を5回ずつ流してみます。

// 生成限界値
let limit = 100000
// 配列
timer (fun _ -> [| for i in 1 .. limit do yield (i, i * 2) |])
// リスト
timer (fun _ -> [ for i in 1 .. limit do yield (i, i * 2) ])

経過時間の平均が配列: 0.02438[s] に対し、リスト: 0.03447[s] で、気持ち配列の方が早いかなー、というくらい。

しかし、生成限界値を 100,000 から 10,000,000 にすると、結果は歴然でした。配列が 2.45560[s] であるのに対し、リストは 4.47843[s] となり、差が広がったのです。

再計測

と、ここでキャミバ先生から教育的指導が入りました。

はい、すみませんでした…。ということで、内包表記を使わない方法で再計測してみます(結果は測定5回分の平均)。

// 生成限界値
let limit = 10000000
// 配列
timer (fun _ -> Array.init limit (fun i -> (i, i * 2)))
// リスト
timer (fun _ -> List.init limit (fun i -> (i, i * 2)))

配列: 1.10177[s]

リスト: 2.17026[s]

速い、速過ぎる。内包表記とは一体何だったのか(糖衣構文です)。とは言え、こっちでも配列の方が2倍速いですし、速度が要求されるような場合は配列の使用を検討した方がいいでしょう。

本当に?

しかし、配列って要素数固定のコレクションなので、要素の追加・削除が頻繁にあるような操作には向いていません。そういう場合にまで配列を使うべきか、という議論もありますし、.NET のコレクションたちを使うという場合もあるかもしれません。コードの読みやすさ・書きやすさと、パフォーマンスその他、トレードオフをよく検討して選びたいものです。

最後に

ILer こわい(しろめ