Re: strings draft

[bear <bear@xxxxxxxxx>]

On Sun, 25 Jan 2004, Tom Lord wrote:

>    > However, in either case you still have two problems:
>
>    >   1) Both are very different from unconditional O(1) access.
>
>The language I recommend for R6RS says "expected case O(1)", not
>unconditional.
>
>It's not a requirement, just guidance -- so it doesn't prevent any
>implementation from conforming.


If it's guidance rather than a requirement, it would be better
to use the word "recommended" rather than "expected".  The latter
has a technical meaning when talking about algorithmic complexity,
which is the expected runtime of an algorithm for "normal" data.

For example, a non-balanced binary tree, while it has worst case
O(n) access time, is better than a list because it has expected
case O(log n) access time.

A balanced binary tree has both worst-case and expected-case
access time of O(log n).

I'm not going to be using a splay tree because it prevents
sharing of subtrees between different strings and reintroduces
all the copying overhead that makes a lot of other operations
O(n) rather than O(log n). O(1) lookups are nice, but the
expense of O(n) mutation/copying time makes them too expensive
for the kind of string operations I'm using it for, so the
point about it being "recommended" rather than "required" to
have expected-case O(1) lookups is important to me.

				Bear