Re: binary search? - Naggum cll archive

Subject: Re: binary search?
From: Erik Naggum <erik@naggum.no>
Date: 1999/03/10
Newsgroups: comp.lang.lisp
Message-ID: <3130013677827179@naggum.no>

* Sam Steingold <sds@goems.com>
| True in this particular case (list of integers), not quite true in
| general.  If accessing the key (:key) and key comparison (:test) are
| expensive compared to the list traversal, it does make sense to do binary
| search on lists [at least I got a 10% overall speedup out of this on ACL
| and CMUCL].  Please note the usual stuff about premature optimizations.
| It would be wise to use metering.lsp first to make sure this is a
| bottleneck (I did for my case).

  how much would it cost or save to cons up a vector first?  and which
  other valuable features of list make lists win over vectors in the first
  place?

#:Erik