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

three-way comparison


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


Attachment: pgplj9gk5o7gx.pgp
Description: PGP signature