Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] productivity improvement
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: sebastien FURIC <sebastien.furic@t...>
Subject: Re: [Caml-list] productivity improvement
 Hello,

 I've tested your O'Caml program on my PC:

time ./findprimes_modcount 10000

real    1m26.089s
user    0m0.010s
sys     0m0.040s

 To my surprise, this naive lazy version in Clean (5 lines of code!)
outperforms your version:

<clean>

   module sieve

   import StdEnv

   primes =: sieve [2, 3 ..]
   where sieve [p : xs] = [p : sieve [x \\ x <- xs | x mod p <> 0]]

   Start = take 10000 primes

</clean>

time ./sieve

real    1m17.460s
user    0m0.010s
sys     0m0.020s

 The corresponding version in O'Caml (using a lazy list module) is far
from being as efficient:

<caml>

   type 'a stream = Empty | Cons of 'a * 'a stream Lazy.t

   let rec iter f = function
       | Empty -> ()
       | Cons (x, xs) -> f x; iter f (Lazy.force xs)

   let rec filter p = function
       | Empty -> Empty
       | Cons (x, xs) ->
           if (p x) then Cons (x, lazy (filter p (Lazy.force xs))) else
filter p (Lazy.force xs)

   let rec take n s = match (n, s) with
       | _, Empty -> Empty
       | 0, _ -> Empty
       | n, Cons (x, xs) -> Cons (x, lazy (take (n - 1) (Lazy.force
xs)))


   let rec from n = Cons (n, lazy (from (n + 1)))

   let print_int_stream = iter (function x -> print_int x; print_string
"; ")

   let primes =
       let rec sieve = function
           | Empty -> Empty
           | Cons (p, xs) -> Cons (p, lazy (sieve (filter (function n ->
n mod p <> 0) (Lazy.force xs))))
       in sieve (from 2);;

   print_int_stream (take 10000 primes)

</caml>

real    11m9.021s
user    0m0.020s
sys     0m0.030s

 Sebastien.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners