ListとArrayの性能

http://d.hatena.ne.jp/mzp/20090511/suffixを見て気がついたのだけど、先日ちょっと書いてみたSuffix Arrayの練習 - komamitsu.logがArrayじゃなかったことに絶望した。

で、適当にArrayに置き換えてみたら、いつまでたっても処理が終わらなくなったので、簡単なサンプルを書いて調べてみることに。

open Printf

let max_count = 1000000
let seed = 12345678

let rec loop n f r =
  if n <= 0 then r
  else loop (n - 1) f (f r)

let log name f arg =
  let start = Unix.time () in
  let ret = f arg in
  let finish = Unix.time () in
  printf "%s: %f\n" name (finish -. start);
  ret

let create_list () =
  Random.init seed;
  loop max_count (fun r -> (Random.int max_int)::r) []

let create_array () =
  Random.init seed;
  Array.init max_count (fun i -> Random.int max_int)

let _ =
  let the_list = log "create_list" (fun x -> create_list x) () in
  let the_array = log "create_array" (fun x -> create_array x) () in
  ignore (log "sort_list" (fun x -> List.stable_sort compare x) the_list);
  ignore (log "sort_array" (fun x -> Array.stable_sort compare x) the_array)

実行させてみると

create_list: 1.000000
create_array: 2.000000
sort_list: 13.000000
sort_array: 10.000000

恥ずかしながら、最初Array.initを使わずに要素数分Array.appendを呼んでいたのだけど、劇的に遅かった。

多分、前述の
適当にArrayに置き換えてみたら、いつまでたっても処理が終わらなくなったのはそれが原因であろう。

それにしても、Arrayのほうが速いんだなぁ。