Ludovic Courtes quoting me:
> > The representations that appear most attractive for Larceny
> > are described at
> >
> > http://larceny.ccs.neu.edu/larceny-trac/wiki/StringRepresentations
>
> Thanks for the link. So for UTF-*, the O(1) amortized time for
> `string-ref' and `string-length' would stem from the use of memoization,
> while `string-set!' would remain O(n).
Yes, but the record2 and record1 representations are
O(1) amortized time for both, even without auxiliary
memoization.
For interpreters, various segmented representations
provide O(1) amortized time for both, while avoiding
the all-or-nothing space dichotomy of the record2
and record1 representations.
Those are examples of the variable-width representations
that I would recommend to implementors of Scheme. This
isn't rocket science; it's just data structures.
Will
Received on Wed Aug 29 2007 - 10:59:41 UTC