Version franēaise
Home     About     Download     Resources     Contact us    
Browse thread
Help with simple ocaml memoization problem
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Evan Klitzke <evan@y...>
Subject: Help with simple ocaml memoization problem
Hi everyone,

I'm learning Ocaml and I'm trying to figure out why the code I've
written is so slow (and not working). I'm trying to learn Ocaml by
implementing the Project Euler problems in Ocaml, and I'm stuck on
problem 14 (http://projecteuler.net/index.php?section=problems&id=14).

Basically I'm doing the 3*n+1 problem and I need to memoize values
that I've already computed if the function is going to finish in a
reasonable amount of time. I wrote a really short prototype of what I
want to do in Python, and that code is really short and runs quickly
(11 seconds); if you're interested you can see the prototype at
http://static.eklitzke.org/collatz.py

You can see my Ocaml attempt at
http://static.eklitzke.org/problem14.ml . As you can see, it's a _lot_
more code, which alone leads me to think that I'm probably not doing
this idiomatically. When I run it (compiled with ocamlopt, ocaml 3.10
on Linux), the memory usage climbs and after it reaches about 128 MB
(after about 30 seconds) I get the error:

Fatal error: exception Stack_overflow

I think I could use some help with this problem. Maybe I just need to
increase the stack size (how do I do that?) -- the Python version gets
to about the same size right before finishing, so this seems like a
reasonable amount of memory to use -- but I'm concerned that maybe I'm
doing something else wrong, because I'd expect the Ocaml version to
run much more quickly given that it is compiled to native code.  I
would appreciate any pointers for things that I'm doing wrong or
awkwardly.

Thanks in advance!

I'm going to include the text of my ocaml version  inline below, but
due to the long lines in the program it will likely end up mangled :-/

module type INT = sig
  type t = int
  val compare : t -> t-> int
end;;

module Int : INT = struct
  type t = int
  let compare i j = if i < j then -1 else if i = j then 0 else 1
end;;

open Big_int
open Map

(* A hash table for ints *)
module IntMap = Map.Make(Int);;

(* This is where we're going to store memoized values for find_collatz_len *)
let ann = ref IntMap.empty;;

(* Find the length of the chain for the int n *)
let find_collatz_len (n:int) =

  (* This is the definition of the collatz map for big_ints *)
  let collatz (n:big_int) =
    let two_big_int = succ_big_int unit_big_int in
    if eq_big_int (mod_big_int n two_big_int) zero_big_int
    then
      div_big_int n two_big_int
    else
      succ_big_int(mult_int_big_int 3 n)

  (* Tries to find the value of key `k' in the map m, or 0 if not found *)
  and find_safe m k = try IntMap.find k m with Not_found -> 0 in

  (* Helper function that accepts big_ints; t is the term that we're
finding the length of *)
  let rec aux_collatz_len (t:big_int) =

    (* We use memoization for terms small enough to fit in an int *)
    if is_int_big_int t then
      let t_int = int_of_big_int t in
      let v = find_safe !ann t_int in
      if v <> 0 then
        v (* Cache hit -- we've already computed aux_collatz_len for
this value of t *)
      else
        if eq_big_int t unit_big_int then 1
        else
          let v' = 1 + aux_collatz_len (collatz t) in
          ann := IntMap.add t_int v' !ann ; v'
    else
      1 + aux_collatz_len (collatz t)
  in
  aux_collatz_len (big_int_of_int n);;

(* Makes the list [1..n] *)
let nats n =
  let rec rnats m = if m = 0 then [] else m :: (rnats (m - 1)) in
List.rev (rnats n) ;;

let biggest_int l =
  let rec aux l (num, len) =
    if l = [] then
      num
    else
      let (a, b) = List.hd l and t = List.tl l in if b > len then aux
t (a, b) else aux t (num, len)
  in
aux l (List.hd l) ;;

let solution = biggest_int (List.map (fun x -> (x, find_collatz_len
x)) (nats 999999)) ;;

print_endline (string_of_int solution)


-- 
Evan Klitzke <evan@yelp.com>