Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!snorkelwacker!husc6!m2c!umvlsi!dime!forster
From: forster@cs.umass.edu
Newsgroups: comp.lang.lisp
Subject: Re: optimizing array lookups - need help
Message-ID: <10892@dime.cs.umass.edu>
Date: 2 Mar 90 22:55:00 GMT
Sender: news@dime.cs.umass.edu
Organization: COINS, UMass, Amherst
Lines: 14

Two points:
1. there was a discussion about a year ago about trade-offs between hash tables
and a-lists (or property lists, I don't remember which), which eventually
arrived at the conclusion that the point at which it was more efficient to use
one scheme or the other was implementation-dependent, but around 30 for a
lispm.  This is the closest thing I can recall to what you're asking about.
2. You're essentially describing tries, and since you don't say how you're
going to access the data in the lists, it's not at all clear that you'd have
any savings at all, let alone save time.  The whole point of using a trie is
that you can use the character as an index, and get the data as quickly as
possible.  (How could you improve on an array reference for speed?)  Space is,
of course, an issue, and you might be able to save space this way, but it
seems like you're going to lose more than you gain.
- David Forster