Re: Sieve of Eratosthenes Performance: various languages (Re: [Caml-list] productivity improvement)

["Anton E. Moscal" <msk@mail.tepkom.ru>]

11 Июль 2002 00:48, Markus Mottl wrote:

> Compiled to native code (-unsafe -noassert):
>
>   real    0m0.207s
>   user    0m0.100s
>   sys     0m0.020s

Really the main part of the time spent in console output: with redirection 
stdout to /dev/null on PIII-630:

real    0m0.128s
user    0m0.080s
sys     0m0.000s

Without any output:

real    0m0.049s
user    0m0.050s
sys     0m0.000s

The more intersing point is that  the straightforward version of this 
algorithm works only slightly slower than yours:

let prime_n' n = 
  let rec gen cnt primes buffer = function 
    | _ when cnt = n -> primes @ List.rev buffer
    | n' -> 
	let rec test primes buffer = function
	  | p::_ when p*p > n' -> (primes, buffer, true)
	  | p::_ when n' mod p = 0 -> (primes, buffer, false)
	  | _::tl -> test primes buffer tl
	  | [] -> 
	      let nxt = List.rev buffer in 
	      test (primes @ nxt) [] nxt
	in
	let (primes, buffer, res) = test primes buffer primes in
	if res 
	then gen (cnt + 1) primes (n'::buffer) (n'+ 2)
	else gen cnt primes buffer (n'+2)
  in
  gen 1 [2] [] 3

without any output and count=200000 on PIII/630 timings is the following: 
yours -  2'83"  my - 3'38".

Regards, Anton
-------------------
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