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のほうが速いんだなぁ。