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

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.



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

Attachment: pgpG3jzKDTyN5.pgp
Description: PGP signature