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

Re: Fwd: vector-binary-search

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

On Tue, 30 Mar 2004, Sergei Egorov wrote:

> I agree on performance benefits of three-way comparators; in most
> situations calculating < automatically gives you the result of = and
> you may save on some calculations. In spite of this fact, all implementations 
> of "sort" amd "bsearch" I know of use boolean <. The very Olin Shivers
> retained two-way < convention for his sorting library because of
> this tradition; it is likely than other SRFIs will stick with it too.

It's not quite as clear-cut as you make it seem.  Olin Shivers stuck
with the convention because there were no inherent benefits _for_those_
sorting_algorithms_.  However, there _are_ inherent benefits for
_searching_ (and for a few sorting algorithms).

> My other problem with three-way comparators is the fact that there 
> is no three-way boolean to represent their results; symbols and
> -1, 0, 1 are equally bad in this respect, more so because of 
> lack of precedent (no standard Scheme function uses symbols
> as flags or enumerated options). 
> P.S. Symbols are actually worse than -1, 0, 1 because with
> the latter, one can use, say, * as a substitute for three-way 
> boolean operations; with symbols all operations have to be 
> written explicitly.

I'm sticking with negative, zero, and positive.  That convention is
used all over the place, it's efficient, and it's convenient.