Email list hosting service & mailing list manager


three-way comparison Sven.Hartrumpf@xxxxxx 23 Oct 2006 08:36 UTC
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.  A three-valued comparison function also speeds up other
algorithms, e.g. vector-binary-search.

SRFI-67 provides a solid base of comparison functions:
http://srfi.schemers.org/srfi-67/srfi-67.html
A short quote:
"Moreover, in case Scheme users and implementors find this mechanism useful
and adopt it, the benefit of having a uniform interface to total orders to
be used in data structures will manifest itself. Most concretely, a new
sorting procedure in the spirit of this SRFI would have the interface
(my-sort [ compare ] xs), using default-compare if the optional compare was
not provided. Then my-sort could be defined using the entire infrastructure
of this SRFI: Efficient 2- and 3-way branching, testing for chains and
pairwise inequality, min/max, and general order statistics."

See also:
http://srfi.schemers.org/srfi-32/mail-archive/msg00023.html
http://srfi.schemers.org/srfi-32/mail-archive/msg00024.html

Greetings
Sven