William D Clinger scripsit:
> Implementations of the R6RS may use variable-width
> representations while achieving O(1) amortized time for
> string-length, string-ref, and string-set!.
Indeed. What's more, there are four classes of programs:
a) those which need O(1) read/write access to characters in strings;
b) those which need O(1) read (but not write) access;
c) those which need amortized O(1) access;
d) those which do not need O(1) access at all.
Alas, there is no knowing a priori which Scheme implementations will be
used to execute which applications, so it's hard to make the appropriate
tradeoffs in advance.
--
John Cowan cowan at ccil.org http://ccil.org/~cowan
The penguin geeks is happy / As under the waves they lark
The closed-source geeks ain't happy / They sad cause they in the dark
But geeks in the dark is lucky / They in for a worser treat
One day when the Borg go belly-up / Guess who wind up on the street.
Received on Tue Aug 28 2007 - 15:22:33 UTC