犬猿の仲

コンパイラの時なんかはほとんどListをSetのごとく使って処理してしまっていたし、オーダーに気を付ければ特に速度的な問題が起こることもなかった。が、最近はもっぱらHashtblである。なんでもガーガーhashにつっこんでしまうのが楽ちんだ。Hashtblモジュールにはhash関数という、どんなオブジェクトからも自由にハッシュ値を計算してくれる('a -> int)な便利な関数があるわけで、ここまで来ると何も考える必要はない。
それはさておき、最近どうしても速度が速くなってくれない部分があって、どうしたものかどうしたものかと思い悩んでいた。どうもとことん調べてみると、単にHashtbl.findしているだけなのだ。これはいったい？　他にもたくさんfindしているところはあるのだが、どうしたことかある特定の一カ所だけ遅い。すると、ふとHashtblにlistをつっこむと遅いという噂を思い出す。まさにそこでhashにつっこんでいるのはlistであった。

ひょっとして、これが問題なのか？　そこで、速度を調べることに。

let rec make_n_list n v =
  if n = 0 then []
  else v::make_n_list (n-1) v

let to_str l =
  String.concat "/" (List.map string_of_int l)

let timer f =
  let t = Sys.time () in
  f ();
  Printf.printf "%f sec\n" (Sys.time() -. t)

let main () =
  let l_hash = Hashtbl.create 100000 in
  let s_hash = Hashtbl.create 100000 in
  let lst = Hashtbl.create 100000 in
  for i = 0 to 10000 do
    let l = make_n_list 10 i in
    Hashtbl.add l_hash l i;
    Hashtbl.add s_hash (to_str l) i;
    Hashtbl.add lst l i;
  done;

  timer
    (fun () ->
       Hashtbl.iter (fun l _ -> let _ = Hashtbl.find l_hash l in ()) lst);
  timer
    (fun () ->
       Hashtbl.iter (fun l _ -> let _ = Hashtbl.find s_hash (to_str l) in ()) lst)
;;

main ()

ムダに長いな。なんてことはなくて、長さ10のint listをkeyに10000個つっこんで、読み直しているだけだ。そして、もう一方はint listをstring listにしてから、String.concatで1つのstringにして、それをkeyにhashを引いている。どこからどう見ても後者の方が遅い、様な気がする。気が。しかし、衝撃の事実。

% ./camlprog.exe
2.463000 sec
0.100000 sec

前者の方が20倍近く遅い。ひどい。なにこれ。
やはり、Hashtbl.hashをブラックボックスのままほっといたのがまずかったのだろうか。もしかして、listに対しては常に同じ値を返してたりしないだろうかとか思ったが、流石になかった。あー、なんだろなこれは。
とりあえず、Hashtblとlistは相性が悪いので、同時に使うなと。はい。