Problem14(4) -Numモジュール-

jijixiさんのアドバイスも試してみた。

jijixi 2008/04/05 00:12
『Hashtbl.hash は big_int の値に対して常に同じ値を返してしまうので、こいつをhash 関数の実装として使ってしまうと全くハッシュテーブルを使う意味がありません。

かと言って、じゃあどのようなハッシュ関数を作れば良いかという案があるわけでもないですが、そんな話もあるよということで。』

jijixi 2008/04/05 00:14
『あと、ちゃんと比較したわけじゃないですけど、int で収まる領域を軽くしたいなら Big_int じゃなく Num モジュールを使う方が良いかもしれません。』

前回のコード(id:mzp:20080404)のBigIntをNumに置き換えてみたけれども、それほど高速化はしなかった。同じくNumモジュールを使っているjijixiさんのコードはそこそこ高速なので、奇数だけ調べているところや、intの範囲は(+/)でなく(+)を用いているところが効いているんだろうなぁ。

ソースコード

open Num

(* util *)
let ($) f g x = f (g x)
let (@@) f g = f g

(* sub function *)
let (%/) = mod_num
let even n = (n %/ (Int 2)) =/ (Int 0)

(* BigInt Hash *)
module HT = Hashtbl.Make( struct
			    type t = Num.num
			    let equal = eq_num
			    let hash = Hashtbl.hash
			  end )
let table = HT.create 10

let collatz n = 
  let rec loop n r =
    if HT.mem table n then begin
      (HT.find table n) + r
    end else if n =/ (Int 1) then
      1+r
    else if n < (Int 0) then
      failwith "overflow"
    else if even n then
      loop (n // (Int 2)) @@ 1+r
    else
      loop ((Int 3) */ n +/ (Int 1)) @@ 1+r
  in 
  let n' = Int n in
  let r = loop n' 0 in
    Printf.printf "%d\n" n;
    HT.replace table n' r;
    r

let range a b =
  let rec f r a b = 
    if a = b 
      then r
      else f (a::r) (a+1) b
  in
    f [] a b

let solve _ =
  let f ((_,count) as x) m = 
    let count' = collatz m in
      if count < count' then
	(m,count')
      else
	x
  in
    List.fold_left f (0,0) @@ range 500_000 1_000_000;;

let _ = 
  if not !Sys.interactive then begin
    let (x,y) =  solve () in
      Printf.printf "%d,%d\n" x y
  end