[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: strings draft

This page is part of the web mail archives of SRFI 50 from before July 7th, 2015. The new archives for SRFI 50 contain all messages, not just those from before July 7th, 2015.




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