[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: strings draft
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