Re: [Caml-list] What kind of sort do Array.sort ?

[artboreb@netscape.net]

Hi Martin,
Thanks for your sugestion, I've been lazy and didn't check the 
fast_sort,
the random numbers population take less than 10 secs, and the time
measurement is still high? Is fast_sort a quick-sort algorithm?

Ocaml fast-sort
real    0m51.602s
user    0m50.352s
sys     0m0.002s

Best regards

Arturo Borquez

-----Original Message-----
From: Martin Jambon <martin_jambon@emailuser.net>
To: artboreb@netscape.net
Cc: caml-list@inria.fr
Sent: Mon, 8 May 2006 15:23:56 -0700 (PDT)
Subject: Re: [Caml-list] What kind of sort do Array.sort ?

  You can try Array.fast_sort instead of Array.sort (see the docs).
  Also, check that the time is actually spent sorting the array, not 
generating random numbers.

 Martin

 On Mon, 8 May 2006, artboreb@netscape.net wrote:

 > Dear Calmers,
  > Toying with a compiler (builded in Ocaml of course) of a language I 
developed > which emits C code
  > I've written some bemchmarks to test it. For my surprise the same 
program > written in Ocaml lasts
  > almost 6 times. It's about sorting an integer array, the timings 
are:
 >
 > Ocaml (ocamlopt -unsafe unix.cmxa qc.ml -o qc)
 > real 1m10.727s
 > user 1m9.074s
 > sys 0m0.001s
 >
  > Mine (gcc -I /usr/local/include -O3 -s x12.ao.c -o x12 > 
/usr/local/lib/libgc.a -lpthread)
 > real 0m18.536s
 > user 0m18.018s
 > sys 0m0.002s
 >
 > times to take sorting 1000000 an array of 100 random ints
 > the Ocaml code is
 >
 > open Format
 >
 > let _ =
 > if Array.length Sys.argv = 2 then
 > begin
 > Random.init (Unix.getpid ());
 > let a = Array.make (int_of_string Sys.argv.(1)) 0 in
 > for i = 0 to 1000000 do
 > for j = 0 to Array.length a - 1 do a.(j) <- Random.bits () done;
  > Array.sort (fun x y -> if x > y then 1 else if x = y then 0 else -1) 
> a
 > done;
 > for i = 0 to 99 do printf "%010d\n" a.(i) done
 > end
 >
 > I dont attach the C code emitted because is about 280 lines long,
 > my language (for the courious)
 >
 > "ao.ao" INC
 >
 > [Array Int Int] # RAPIDO RECURSIVO > [(a l r) l r a l -> (hl hr p)
 > [l r] [l r >=] [l]
 > [ [r] [a r -> p >= l r < & !] [r] [r 1 -] TREC (r)
 > l l r =/= [a a r -> l <<- 1 +] IFTE (l)
 > [l] [a l -> p <= l r < & !] [l] [l 1 +] TREC (l) l
 > r l r =/= [a a l -> r <<- 1 -] IFTE] TREC (l)
  > a p l <- hl l < [hl l 1 - Qsort] IFTE hr l > [l 1 + hr Qsort] IFTE > 
] Qsort FUN
 >
 > ARGC 2 =
 > [ Getpid Srand [;Int] ARGV 1 -> Atoi MAKE Length 1 - (a n)
 > [[(i) a Rand i <<-] 0 n Upto a 0 n Qsort X-] 1000000 Times
 > a [?n] Fold
 > #[] [Rand "%010d" FMT] Rnd_strnum FUN > ] IFTE
 >
 > Best regards,
 >
 > Arturo Borquez
 > ___________________________________________________
 > Try the New Netscape Mail Today!
 > Virtually Spam-Free | More Storage | Import Your Contact List
 > http://mail.netscape.com
 >
 > _______________________________________________
 > Caml-list mailing list. Subscription management:
 > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
 > Archives: http://caml.inria.fr
 > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
 > Bug reports: http://caml.inria.fr/bin/caml-bugs
 >

 --
 Martin Jambon, PhD
 http://martin.jambon.free.fr

 Edit http://wikiomics.org, bioinformatics wiki


___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com