Browse thread
What kind of sort do Array.sort ?
- artboreb@n...
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
| Date: | -- (:) |
| From: | artboreb@n... |
| Subject: | What kind of sort do Array.sort ? |
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