From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA16949; Tue, 27 Nov 2001 10:21:36 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA16945 for ; Tue, 27 Nov 2001 10:21:35 +0100 (MET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id fAR9LUn18206; Tue, 27 Nov 2001 10:21:30 +0100 (MET) Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA16940; Tue, 27 Nov 2001 10:21:30 +0100 (MET) Date: Tue, 27 Nov 2001 10:21:30 +0100 From: Xavier Leroy To: Mattias Waldau Cc: caml-list@inria.fr Subject: Re: [Caml-list] Beware of compare (and Ocaml beaten by Java) Message-ID: <20011127102130.A16765@pauillac.inria.fr> References: <20011127015149.A10358@earth.cs.mu.oz.au> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0i In-Reply-To: ; from mattias.waldau@abc.se on Mon, Nov 26, 2001 at 07:40:00PM +0100 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > Why isn't compare compiled as '-'? According to the definition > of compare this should be okay. 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. 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.) > 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 > [xy] *) > 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? > 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). - 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