[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: Sven.Hartrumpf@FernUni-Hagen.de*Subject*: Re: three-way comparison*From*: Aubrey Jaffer <agj@alum.mit.edu>*Date*: Thu, 2 Nov 2006 16:24:45 -0500 (EST)*Cc*: srfi-95@srfi.schemers.org, srfi-67@srfi.schemers.org*Delivered-to*: srfi-95@srfi.schemers.org*In-reply-to*: <20061102191150.CB92451D72E@home.voluntocracy.org> (Sven.Hartrumpf@FernUni-Hagen.de)*References*: <20061102191150.CB92451D72E@home.voluntocracy.org>

| From: Sven.Hartrumpf@FernUni-Hagen.de | Date: Mon, 23 Oct 2006 10:36:56 +0200 (CEST) | | Hello. | | Thanks Aubrey for drafting a sorting SRFI. Maybe this time (after | the withdrawn SRFI-32) we will see such a beast :-) | | Three-valued comparison function are more efficient for some data | types if many duplicates are present. I often sort lists of some | million strings of average length 20 and many duplicates. I | remember that some sort algorithms will test (< a b) and (< b a) in | certain constellations for one setting of a and b. But SRFI-95 mandates stable sort algorithms. I traced the predicate while (merge-) sorting various lists. (sort '(7 6 9 5 4) (lambda (x y) (< (quotient x 4) (quotient y 4)))) (sort '(7 6 9 5 4) (lambda (x y) (<= (quotient x 4) (quotient y 4)))) There were no extra reversed comparisons. So 3-way branching offers no improvement in merge-sort; and there is little reason to use a sorting algorithm with poorer performance. | A three-valued comparison function also speeds up other algorithms, | e.g. vector-binary-search. It is also good for sequence comparison.

- Prev by Date:
**Two minor corrections** - Next by Date:
**Re: Two minor corrections** - Previous by thread:
**three-way comparison** - Next by thread:
**Two minor corrections** - Index(es):