The GC is not collecting... my mistake?
 Loup Vaillant
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Loup Vaillant <loup.vaillant@g...> 
Subject:  The GC is not collecting... my mistake? 
Hello, I am trying to solve a problem with minimum space complexity, while still being as pure as I can. I rewrote streams (functional ones) for that matter. My problem is that I can't accurately guess the space and time complexity of my program. The program depend mainly on two parameters: "l" (rather small) and "n" (quite big). I though the time complexity of my program was O(l*n) at worst (I may be right), and the space complexity was O(l) (I was outright wrong). I thought the GC could collect the first values of my streams when the program don't need them any more, but it doesn't seem to be the case. Unfortunately, I was unable to reduce my problem to a proper minimum example, so I send it all. Note: I am confident that my program is semantically correct (given plenty of time and space). The problem it solves is taken from the last contest in: http://www.franceioi.org Thank you all, Loup Here is my program (the functions are not declared in the correct order, for readability reasons): (* MAIN PROGRAM *) let main () = let l = scan_int () in (* "l" is positive, rather small (100 at most) *) let n = scan_int () (* "n" is positive, quite big (100_000 at most) *) in (* big function composition, applied to "n" *) (sscan_n_int >>> ((listify >>> take (nl+2) >>> map (take l)) &&& drop l) >>> uncurry2 combine >>> filter (fun (l, e) > head l = e && not (exists ((<) e) l)) >>> length >>> show_int) n (* exec *) let _ = main () (* HELPER COMBINATORS (like Haskell's arrows) *) let (>>>) f g x = g (f x) let (&&&) f g x = (f x, g x) let uncurry2 f (x, y) = f x y (* SCAN & PRINT *) let scan_int () = Scanf.scanf " %d" (fun x > x) let show_int x = Printf.printf "%d\n" x let rec sscan_n_int = function  0 > empty  n > let i = scan_int() in lazy(Cons (i, sscan_n_int (n1))) (* STREAM DEFINITION *) type 'a cell =  Empty  Cons of 'a * 'a stream and 'a stream = 'a cell lazy_t let empty = lazy Empty let head: 'a stream > 'a = fun l > match Lazy.force l with  Empty > failwith "empty stream"  Cons(x, _) > x let tail: 'a stream > 'a stream = fun l > match Lazy.force l with  Empty > failwith "empty stream"  Cons(_, l) > l let is_empty: 'a stream > bool = fun l > match Lazy.force l with  Empty > true  Cons(_, _) > false (* STREAM LIBRARY *) let rec listify l = if is_empty l then empty else lazy (Cons (l, listify(tail l))) let rec take n l = match n with  n when n <= 0 > empty  n > if is_empty l then empty else lazy (Cons (head l, take (n1) (tail l))) let rec drop n l = match n with  0 > l  n > if is_empty l then empty else drop (n1) (tail l) let rec combine m l = if is_empty m  is_empty l then empty else lazy(Cons ((head m, head l), combine (tail m) (tail l))) let rec map f l = if is_empty l then empty else lazy(Cons (f (head l), map f (tail l))) let rec filter p l = if is_empty l then empty else let hd = head l in let tl = tail l in if p hd then lazy(Cons (hd, filter p tl)) else filter p tl let rec _length acc l = if is_empty l then acc else _length (1 + acc) (tail l) let length l = _length 0 l let rec exists p l = not (is_empty l) && (p (head l)  exists p (tail l))