[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.

At Fri, 23 Jan 2004 16:15:57 -0800 (PST), Tom Lord wrote:
>     > From: bear <bear@xxxxxxxxx>
>     > > And if you were to use self-balancing trees, it would be an
>     > > expected-case O(1) operation.
>     > ???  Balanced trees are still trees, and if the tree is exp(n) long
>     > there are still O(n) links to follow from the root to a leaf.  Can
>     > you explain what you mean?
> I mean that you should (maybe, don't know enough about your apps and
> environment) use splay trees so that string algorithms displaying a
> reasonable degree of locality will be able to locate indexes in
> expected-case O(1).

OK, in my reply on c.l.s. I had incorrectly assumed you meant keeping
some sort of reference to that last index in the tree, I should have
asked for clarification.

However, in either case you still have two problems:

  1) Both are very different from unconditional O(1) access.

  2) Both effectively prevent shared strings as subtrees.

> Of course if memory constraints and usage guarantee that your
> particular non-splay trees or guaranteed to be shallow -- that's just
> as good.

Probably not good enough if you want to work with strings the size Bear
is talking about.

The problem with recommending O(1) on STRING-REF/SET! is that it
encourages programming style that cannot be optimized in some string
implementations.  However, by the simple suggestion of Shiro's where you
use a string-pointer object you can achieve O(1) where you need it.

Also, the libraries that would need string-pointers will be relatively
few (most notably regexps).  In general code it is preferable to use
higher-level procedures such as those in SRFI-13, where the
implementation should be able to use the fastest possible method behind
the scenes.