Version française
Home     About     Download     Resources     Contact us    
Browse thread
What kind of sort do Array.sort ?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Martin Jambon <martin_jambon@e...>
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