せっかくなので

OCaml

1回目はずいぶんベタだったが、2回目もなんかあんまり違いの出なさそうなお題がでるなぁと。
まだ、OCaml な回答を書いている人がすくなさそうなので。というほど気の利いたプログラムを書いたわけじゃありませんが。それにしても、巷の Haskell ブームがスゴイですね。


ふつうの人なら、ふつうに書いて memo 化して終わりだろうなぁ。

let memo = Hashtbl.create 100000
;;
let rec g n =
  if Hashtbl.mem memo n then
    Hashtbl.find memo n
  else
    let v =
      if n = 1 then 0
      else if n mod 2 = 0 then g (n / 2) + 1
      else g (3 * n + 1) + 1 in
    Hashtbl.add memo n v;
    v
;;

let h n =
  let max_i = ref (-1) in
  let max_v = ref (-1) in
  for i = 1 to n do
    let v = g i in
    if !max_v < v then (max_i := i; max_v := v)
  done;
  !max_i
;;

Arg.parse []
  (fun s -> print_int (h (int_of_string s)); print_newline ())
  ""

ベタだ。ベタベタすぎて、気持ち悪い。なんだかんだ、やっぱり標準ライブラリは関数少ないよねぇと思った。変な for 文が入ってる。fold_left の index 付き版が欲しいよねぇとか。

そんなこといっても、Hashtbl がメモリ食いつぶすかもしれないじゃんという人のための、direct map 実装。

let size = ref 100000
let cache = ref (Array.create 0 None)

let load n =
  match !cache.(n mod !size) with
  | Some (i, v) when i = n -> Some v
  | _ -> None
;;
let memo n v =
  !cache.(n mod !size) <- Some (n, v)
;;

let rec g n =
  match load n with
  | Some v -> v
  | None ->
      let v =
        if n = 1 then 0
        else if n mod 2 = 0 then g (n / 2) + 1
        else g (3 * n + 1) + 1 in
      memo n v;
      v
;;

let h n =
  cache := Array.create !size None;

  let max_i = ref (-1) in
  let max_v = ref (-1) in
  for i = 1 to n do
    let v = g i in
    if !max_v < v then (max_i := i; max_v := v)
  done;
  !max_i
;;

Arg.parse
  ["-c", Arg.Set_int size, "cache size"]
  (fun s -> print_int (h (int_of_string s)); print_newline ())
  ""

ベタだ。引数オプションは Set_XXX で。Arg module は便利だ。

OCaml の何が悲しいって、32 bit マシンでも整数型は 32 bit もないところ。最近は実験環境が 64 bit なので、とくに困ることがあるわけでもないが。上のプログラムは、ocamlopt @ Opteron 2.4 GHz で a.out 1000000 が Hashtbl 版は 3.5 sec、Array 版は 2.6 sec くらい。Array 版は、キャッシュのサイズに依るけどねぇ。

追記

あれ、よく見たらこれ DP にならないじゃん。何やってんだオレ。そしたら、なおさらどこが「関数型的」なのか分からない。

let rec g i n =
  if n = 1 then i
  else if n mod 2 = 0 then g (i + 1) (n / 2)
  else g (i + 1) (3 * n + 1)
;;

let h n =
  let max_i = ref (-1) in
  let max_v = ref (-1) in
  for i = 1 to n do
    let v = g 0 i in
    if !max_v < v then (max_i := i; max_v := v)
  done;
  !max_i
;;

Arg.parse []
  (fun s -> print_int (h (int_of_string s)); print_newline ())
  ""

ただの tail recursive にして、1000000 が 1 sec くらい。これじゃ、ただのループでも簡単に書けるし。うーん、空しい。