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