William D Clinger <[EMAIL PROTECTED]> writes:
> Ludovic Courtes quoting me:
>> 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.
Right, but these look more complex IMO, whereas memoization is really
orthogonal to the implementation of the "real" `string-{ref,length}'
(one could implement memoization and `string-set!' on top of an
immutable string implementation with O(n) `string-{ref,length}'.)
Thanks,
Ludovic.
_______________________________________________
r6rs-discuss mailing list
[email protected]
http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
