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

*To*: srfi-43@xxxxxxxxxxxxxxxxx*Subject*: Re: Fwd: vector-binary-search*From*: campbell@xxxxxxxxxxxxxxxxxxxxxxxxxxx*Date*: Tue, 30 Mar 2004 23:24:08 +0200 (DFT)*Delivered-to*: srfi-43@xxxxxxxxxxxxxxxxx*In-reply-to*: <1080622032.4068fbd04c822@xxxxxxxxxxxxxxxxxxxx>*Old-date*: Tue, 30 Mar 2004 13:24:05 -0800 (PST)*User-agent*: Gnus/5.110001 (No Gnus v0.1) XEmacs/21.5 (celeriac, berkeley-unix)

On Mon, 29 Mar 2004, David Van Horn wrote: > [ The following is forwarded on behalf of Sergei Egorov <esl@xxxxxxx>. > -- David ] > > I think that using "compare" procedure for vector-binary-search > is not very convenient. There are two main sources of inconvenience: > first, there are no ready-to-use procedures implementing the "compare" > interface; second, in most cases vector-binary-search will be used > on vectors sorted by vector-sort{!} and in 90% of implementations > sort using "less" predicates returning boolean. > > Binary search and sort procedures are closely related, so using the > same convention for ordering predicate will benefit both. Since SRFI-43 > does not include any sorting procedures (I support this decision), it > would be better either to drop vector-binary-search altogether I kinda like having VECTOR-BINARY-SEARCH... > or include a version which has a better chance to be compatible with > sorting procedures defined elsewhere: > > (vector-binary-search vec val less) => val position or #f ...but I'm not sure this is a good idea, either: it doesn't make much of a difference if you just use integers, but what if you, for example, use strings instead? You end up performing a _huge_ number of extra, unnecessary comparisons of the entire string. Instead, with a three- way comparator, for each iteration, there is only one entire string comparison (and a number of integer or symbol comparisons). Moreover, as Olin Shivers pointed out on the SRFI 32 mailing list, there _are_ some sorting algorithms that benefit from three-way comparators; my VECTOR-BINARY-SEARCH isn't alone with three-way comparators. So I'd like to stick with the interface as it is. (By the way, for searching vectors of integers, there _is_ a convenient comparator: -)

**References**:**Fwd: vector-binary-search***From:*David Van Horn

- Prev by Date:
**Re: VECTOR-UNFOLD and VECTOR-TABULATE** - Next by Date:
**Re: Fwd: vector-binary-search** - Previous by thread:
**Fwd: vector-binary-search** - Next by thread:
**Re: Fwd: vector-binary-search** - Index(es):