From: Clint Hyde
Subject: RE: Bin-Search Using LISP?
Date: 
Message-ID: <3ide8r$geu@info-server.bbn.com>
my experience with this stuff suggests that search efficiency is tightly
coupled to the structure of the data you want to search over. in a
typical Pascal intro class, you learn about B-trees and variants. this
is data structured a particular way which achieves good lookup times
(O(log(n)) as I recall it), but only under the right circumstances. a
list is simply a degenerate tree, in which the top node is also the
left-most node. 

in order to achieve best overall search times, you want to have a
balanced B-tree, which means that you spend time keepin the structure
itself efficiently organized.  a simple list is NOT efficiently
organized, which might lead one to the conclusion that LISP does a poor
job.

if you want good search time, you still have to use the more efficiently
structured data, which means creating data-structure types, creating and
using instances of them, etc., in exactly the same was as the Pascal
program.

what lisp DOES provide is some built-in behavior (i.e., lists) that make
it easy for you to bypass the more complex data-structures in return for
convenience. and a list that is reasonalby short is not going to be
detectably different than a B-tree in speed, and might even be faster as
it doesn't have to do the same less-than/greater-than comparisons to
decide which tree-branch to take.

lisp also provides built-in hash-tables. effectively, fixed lookup
times, O(k). this is a win. creating those other, more Pascal-like data
structures is easy enough...I've never had occasion to need them. I
wonder if I'd have used them if they were built in?

 -- clint