From ... From: Erik Naggum Subject: Re: binary search? Date: 1999/03/10 Message-ID: <3130013677827179@naggum.no>#1/1 X-Deja-AN: 453183229 References: <36E31DBC.BC03C9E7@iname.com> <87vhgc6a44.fsf@pc-hrvoje.srce.hr> mail-copies-to: never Organization: Naggum Software; +47 8800 8879; http://www.naggum.no Newsgroups: comp.lang.lisp * Sam Steingold | 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