How can I treat bits?
[
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:  20011127 (09:41) 
From:  Mattias Waldau <mattias.waldau@a...> 
Subject:  RE: [Camllist] Beware of compare (and Ocaml beaten by Java) 
> 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 Javacollegue 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/camlbugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr