What kind of sort do Array.sort ?

What kind of sort do Array.sort ?

[artboreb]

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

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

[Martin Jambon]

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

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

[artboreb]

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

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

[Erick Tryzelaar]

artboreb@netscape.net wrote:
> Is fast_sort a quick-sort algorithm?
According to the docs, Array.sort uses a heap sort, and 
Array.stable_sort uses a merge sort. Array.fast_sort uses either one or 
the other.

http://caml.inria.fr/pub/docs/manual-ocaml/libref/Array.html

-e