RE: [Caml-list] Beware of compare (and Ocaml beaten by Java)

["Mattias Waldau" <mattias.waldau@abc.se>]

> I assume you mean "compare at type int -> int -> int", because for
> types represented as pointers, pointer subtraction wouldn't give
> reliable results -- for one thing, the GC can move blocks around.

Yes.

> 
> Even on integer arguments, "-" cannot be used due to arithmetic
> overflow:
> 
>   compare min_int max_int = -1    (* correct *)
>   min_int - max_int = 1           (* incorrect *)
> 
> So, replacing "compare" by "-" is only valid for small integer types
> such as "char" and enumerated datatypes, and I felt this wasn't
> important enough to implement.  (Given your example, you'll disagree,
> of course.)

Yes, you are right, overflow is a problem. Maybe using "-" instead of 
compare should just be a tip instead next to the documentation of compare.

> 
> > The core of the slow program is
> > 
> > (* compare two substrings of the SAME text 
> >    [compare x y] returns [0] if [x=y], a negative integer if
> >    [x<y], and a positive integer if [x>y] *)
> > let rec same_substr_compare str idx1 idx2 : int =
> >   let length = String.length str in
> >   (* shortest string is smaller *)
> >   if idx1 = length then -1 else
> >   if idx2 = length then 1 else 
> >   (* compare one char *)
> >   let res = compare str.[idx1] str.[idx2] in
> >   (* char was equal, recurse *)
> >   if res = 0 then same_substr_compare str (idx1+1) (idx2+1)
> >   (* char was different, finished *)
> >   else res ;;
> 
> I get the impression that same_substr_compare never returns 0; is this
> intentional?

Since I compare substrings of the same string from different positions 
to the end of the string, there will never be any identical 
substrings (one of them will always be shorter).

> 
> > 3. Mergesort (=Array.stable_sort) is faster than 
> > heapsort (=Array.sort). (runtime down from 60s to 40s).
> > (I also tried quicksort (=Sort.array), but after 8 hours
> > it still hadn't finished.)
> 
> This is a bit surprising: you might have hit one of those cases where
> Quicksort is O(n^2), but it could also be the case that Sort.array
> malfunctions because your comparison function is not a proper
> comparison function (it doesn't return 0 for equal things).

It worked on smaller datasets, so I think I found an O(n^2)-case.
My Java-collegue had the same problem and had to implement merge sort.
I didn't look into it a lot.

> 
> - Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr