[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: three-way comparison
| From: Sven.Hartrumpf@FernUni-Hagen.de
| Date: Mon, 23 Oct 2006 10:36:56 +0200 (CEST)
| 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.