This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

The GC is not collecting... my mistake?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-11-06 (14:46) From: Dominique Martinet Subject: Re: [Caml-list] The GC is not collecting... my mistake?
```Hello,
(It did pass, I typed all of what you see next, then though it wasn't
worth it since I didn't answer your question anyway. Well, since you
though that didn't work, I might as well send it :P)

I'm not used to your way of programming (with arrows and such), and
guessing you were the one subscribe as "loup", I assume you're
considering the first Banderole problem. (my answer not fitting the
second one, heh)

Here's what I did, and what seemed the most logical to me at that time
(a plain iterative "check everything" function ; the check being
tail-recursive and dropping as soon as there's a problem). The time
computation requirement was 1s, and I had at worst 0.23, so that's
still quite usable I guess. (Time complexity should be O(l*n) worst
case and space one would be O(n) as I write everything in an array.
(That's n and not l, which is much worse :P))

I had some time at the end and planned to try the second one, but with
l=100_000 and n=2_000_000 (worst possibe thing they could ask us to
do), my program took 30 seconds to compute, and I don't think it
respects the space one either :P (using ulimit -v 2000)

let scan_int () = Scanf.scanf " %d" (fun x->x)
let show_int x  = Printf.printf "%d\n" x

let _ =
let longueur,nb_pics=Scanf.scanf " %d %d" (fun x y -> x,y)
and compteur = ref 0 in
let tab_hauteurs = Array.make nb_pics 0 in
for i=0 to nb_pics - 1 do
tab_hauteurs.(i) <- scan_int ()
done;
let rec check i decallage =
if decallage < longueur
then if tab_hauteurs.(i+decallage) <= tab_hauteurs.(i)
then check i (decallage + 1)
else false
else tab_hauteurs.(i+decallage) = tab_hauteurs.(i)
in
for i=0 to nb_pics - longueur - 1 do
if check i 0 then incr compteur
done;
show_int !compteur

```