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

Re: Fwd: vector-binary-search

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.