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

Re: three-way comparison

This page is part of the web mail archives of SRFI 95 from before July 7th, 2015. The new archives for SRFI 95 contain all messages, not just those from before July 7th, 2015.

 | 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.