2012-12-14

はてなダイアリーplusを使っているので、アクセス解析を見て、どんなところからこの辺境に辿りついているのかを見させてもらってますが、何でか医療職の面接についてのリンクから飛んできた方がいて驚きました。
いや、確かに面接についてとか書きましたが、どっからどう見たら医療職が出てくるのかと・・・。自動で生成されたリンクなのかどうかはぱっと見なのでわかりませんでしたが。ま、勘違いする方もいないとは思いますが。

それはそれで置いておいて、ふとOCamlでMapとHashtblってどれくらい速度が違うもんだべという疑問が湧いてきたので、とても簡単に試してみました。どれくらい簡単かというと

(* Hashtblの速度確認 *)
let _ =
  let t = Hashtbl.create 10000 in
  let rec loop m n v =
    if n = 0 then m
    else begin Hashtbl.add m n v; loop m (n - 1) v end in
  loop t 10000000 0;
  Hashtbl.iter (fun _ _ -> ()) t;

(* Mapの速度確認 *)
module M = Map.Make(
  struct
    type t = int
    let compare = compare
  end
)

let _ =
  let rec loop m n v =
    if n = 0 then m else loop (M.add n v m) (n - 1) v in

  M.iter (fun _ -> ()) (  loop M.empty 10000000 0)

このくらい簡単です。これで測れるのは、
1. 10,000,000個のintを突っ込む時間
2. 10,000,000個の要素すべてにアクセスする時間
くらいだと思います。まぁちょっと調べてもわざわざこんな基本的すぎる部分を調べる方もいないようなので、個人的なメモとして残しておきます。

ocamlopt -o test_hashtbl test_hashtbl.ml
ocamlopt -o test_map test_map.ml
for i in `seq 5`; do time test_hashtbl; done
for i in `seq 5`; do time test_map; done

それぞれ5回ずつ実行してみました。結果は以下の通りです。

# for i in `seq 5`; do time test_hashtbl; done
./test_hashtbl  2.61s user 0.18s system 99% cpu 2.795 total
./test_hashtbl  2.67s user 0.16s system 99% cpu 2.840 total
./test_hashtbl  2.59s user 0.17s system 99% cpu 2.769 total
./test_hashtbl  2.63s user 0.17s system 99% cpu 2.813 total
./test_hashtbl  2.61s user 0.17s system 99% cpu 2.796 total

# for i in `seq 5`; do time test_map; done
./test_map  8.21s user 0.24s system 99% cpu 8.475 total
./test_map  8.17s user 0.24s system 99% cpu 8.433 total
./test_map  8.14s user 0.23s system 99% cpu 8.394 total
./test_map  8.17s user 0.23s system 99% cpu 8.426 total
./test_map  8.16s user 0.24s system 99% cpu 8.431 total

大体Hashtblの方が1/3くらいでしょうか。これはどっちかというと、Mapが毎回全体を作り直しているのに対して、Hashtblは副作用で書き換えしているため、Hashtblについては、事前に十分な領域が用意されていさえすれば、ほぼO(1)で実行できることが大きそうです。
では試しに、Hashtbl.createの値を変えながら同じ処理を実行してみます。

// 1の場合
% for i in `seq 5` ; do time ./test_hashtbl; done
./test_hashtbl  4.54s user 0.21s system 99% cpu 4.758 total
./test_hashtbl  4.54s user 0.22s system 99% cpu 4.776 total
./test_hashtbl  4.57s user 0.24s system 99% cpu 4.817 total
./test_hashtbl  4.60s user 0.22s system 99% cpu 4.834 total
./test_hashtbl  4.57s user 0.21s system 99% cpu 4.793 total

// 10の場合
% for i in `seq 5` ; do time ./test_hashtbl; done
./test_hashtbl  3.02s user 0.17s system 99% cpu 3.203 total
./test_hashtbl  3.00s user 0.16s system 99% cpu 3.170 total
./test_hashtbl  2.98s user 0.18s system 99% cpu 3.173 total
./test_hashtbl  3.01s user 0.16s system 99% cpu 3.180 total
./test_hashtbl  2.98s user 0.18s system 99% cpu 3.169 total

// 100の場合
% for i in `seq 5` ; do time ./test_hashtbl; done
./test_hashtbl  3.22s user 0.21s system 99% cpu 3.440 total
./test_hashtbl  3.25s user 0.18s system 99% cpu 3.438 total
./test_hashtbl  3.22s user 0.18s system 99% cpu 3.406 total
./test_hashtbl  3.24s user 0.18s system 99% cpu 3.435 total
./test_hashtbl  3.25s user 0.18s system 99% cpu 3.445 total

// 1000の場合
% for i in `seq 5` ; do time ./test_hashtbl; done
./test_hashtbl  4.40s user 0.21s system 99% cpu 4.629 total
./test_hashtbl  4.37s user 0.20s system 99% cpu 4.584 total
./test_hashtbl  4.40s user 0.19s system 99% cpu 4.611 total
./test_hashtbl  4.39s user 0.20s system 99% cpu 4.608 total
./test_hashtbl  4.38s user 0.20s system 99% cpu 4.589 total

// 10000000の場合
% for i in `seq 5` ; do time ./test_hashtbl; done
./test_hashtbl  1.35s user 0.12s system 99% cpu 1.476 total
./test_hashtbl  1.34s user 0.12s system 99% cpu 1.468 total
./test_hashtbl  1.35s user 0.12s system 99% cpu 1.481 total
./test_hashtbl  1.33s user 0.13s system 99% cpu 1.470 total
./test_hashtbl  1.34s user 0.13s system 99% cpu 1.480 total

・・・あれ、10 < 100 < 1000 < 1 になりましたね。なお、最後のは追加する個数と、最初に用意した個数を一致させたものです。10000の約2倍ですね。ちなみにこれ以上増やすと、逆に時間が落ちます。

簡単な実験でしたが、結論としては
1. ある程度の数(10000個)くらいまでは、HashtblとMapではあまり差が無い(実際にアクセスしたりする場合は別ですよ？)
2. Hashtblは、create時に無駄に確保するとそれだけで結構時間がかかる。10000000くらいだと、0.02sくらいそれだけでかかる。
3. 必要十分だけ領域を確保したHashtblは、大抵同じ個数入れたMapより速い。
というありきたりなものになることがよくわかりました。話を聞くだけでも、「へーそーなんだー」で終わることもできますが、こんな風にしてやってみるのも、色々試すことができてよろしいかと思います。

なんでこんなことを調べたのかというと、あることをやるときに、HashtblとMapのどっちを使おうかなーと思い、要素数によってどんだけ変わるもんかを調べてみたかったためです。まぁ、現実的に10msレベルで時間がかかるには、万単位の要素が必要そうなので、まーどっちでもいいんかなぁ、というなんともはやな結論に到達しました。
このついでに、自分でAA木をベースに作ったMapについて、同じ要素数で試してみたところ、100,000では約1/2の時間でしたが、それ以上になったらStack overflowしたので、それの原因調べという作業が追加されました・・・。

まぁ、結果としてはありきたりでしたが、1,000,000とかいう数でも、Hashtblならかなりの速度でなんとかしてくれるということがわかったので収穫とします。

deruiの日記

MapとHashtblの個人的比較メモ