Subject: Re: efficiently accumulating values
From: (Rob Warnock)
Date: Sat, 08 Jul 2006 23:08:41 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
Ken Tilton  <> wrote:
| "subseq creates a sequence that is a copy of the subsequence of sequence 
| bounded by start and end. "
| Ouch. Just to store a prefix we first cons up an entire copy of the 
| prefix? Hello performance hit.

Yes, but... If the "word" is coming from a mutable place, say,
a fixed buffer or an array with a fill pointer that's being
repeatedly written into, then you *must* cons copies of the
"word" or any portion of it that's being used as a hash table
key, else run the risk of snot monkeys:

    18.1.2 Modifying Hash Table Keys
    If an object O1 is used as a key in a hash table H and is then
    visibly modified with regard to the equivalence test of H, then
    the consequences are unspecified if O1, or any object O2 equivalent
    to O1 under the equivalence test (either before or after the
    modification), is used as a key in further operations on H.

One approach that *might* buy a little performance is to (after
copying the initial "word" *once*, if needed for immutability)
make the prefixes be 1-, 2-, and 3-element arrays displaced to
the "word". Though note that with *most* implementations'
representations of displaced arrays, consing up a simple 1-, 2-,
or 3-char string with SUBSEQ is likely to be *far* less expensive
than consing up a displaced arrays. (*sigh*)


Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607