Email list hosting service & mailing list manager

strings draft Tom Lord (22 Jan 2004 05:11 UTC)
Re: strings draft Shiro Kawai (22 Jan 2004 09:46 UTC)
Re: strings draft Tom Lord (22 Jan 2004 17:45 UTC)
Re: strings draft Shiro Kawai (23 Jan 2004 05:03 UTC)
Re: strings draft Tom Lord (24 Jan 2004 00:45 UTC)
Re: strings draft Matthew Dempsky (23 Jan 2004 20:01 UTC)
Re: strings draft Shiro Kawai (24 Jan 2004 03:26 UTC)
Re: strings draft Tom Lord (24 Jan 2004 04:31 UTC)
Re: strings draft Shiro Kawai (24 Jan 2004 04:49 UTC)
Re: strings draft Tom Lord (24 Jan 2004 19:01 UTC)
Re: strings draft Shiro Kawai (24 Jan 2004 22:15 UTC)
Octet vs Char (Re: strings draft) Shiro Kawai (26 Jan 2004 09:58 UTC)
Strings, one last detail. bear (30 Jan 2004 21:12 UTC)
Re: Strings, one last detail. Shiro Kawai (30 Jan 2004 21:43 UTC)
Re: Strings, one last detail. Tom Lord (31 Jan 2004 00:27 UTC)
Re: Strings, one last detail. bear (31 Jan 2004 20:25 UTC)
Re: Strings, one last detail. Tom Lord (31 Jan 2004 20:56 UTC)
Re: Strings, one last detail. bear (01 Feb 2004 02:28 UTC)
Re: Strings, one last detail. Tom Lord (01 Feb 2004 02:58 UTC)
Re: Strings, one last detail. bear (01 Feb 2004 07:53 UTC)
Re: Octet vs Char (Re: strings draft) bear (26 Jan 2004 19:04 UTC)
Re: Octet vs Char (Re: strings draft) Matthew Dempsky (26 Jan 2004 13:13 UTC)
Re: Octet vs Char (Re: strings draft) Matthew Dempsky (26 Jan 2004 13:41 UTC)
Re: Octet vs Char Shiro Kawai (26 Jan 2004 23:38 UTC)
Re: Octet vs Char (Re: strings draft) Ken Dickey (26 Jan 2004 19:40 UTC)
Re: Octet vs Char Shiro Kawai (27 Jan 2004 05:10 UTC)
Re: Octet vs Char Tom Lord (27 Jan 2004 05:37 UTC)
Re: Octet vs Char bear (27 Jan 2004 08:35 UTC)
Re: Octet vs Char (Re: strings draft) bear (27 Jan 2004 08:32 UTC)
Re: Octet vs Char (Re: strings draft) Ken Dickey (27 Jan 2004 06:50 UTC)
Re: Octet vs Char (Re: strings draft) bear (27 Jan 2004 19:06 UTC)
Re: strings draft bear (22 Jan 2004 19:05 UTC)
Re: strings draft Tom Lord (23 Jan 2004 02:06 UTC)
READ-OCTET (Re: strings draft) Shiro Kawai (23 Jan 2004 06:00 UTC)
Re: strings draft bear (23 Jan 2004 07:04 UTC)
Re: strings draft bear (23 Jan 2004 07:20 UTC)
Re: strings draft Tom Lord (24 Jan 2004 00:15 UTC)
Re: strings draft Alex Shinn (26 Jan 2004 01:58 UTC)
Re: strings draft Tom Lord (26 Jan 2004 02:35 UTC)
Re: strings draft bear (26 Jan 2004 02:35 UTC)
Re: strings draft Tom Lord (26 Jan 2004 03:01 UTC)
Re: strings draft Alex Shinn (26 Jan 2004 03:00 UTC)
Re: strings draft Tom Lord (26 Jan 2004 03:27 UTC)
Re: strings draft Shiro Kawai (26 Jan 2004 04:57 UTC)
Re: strings draft Alex Shinn (26 Jan 2004 04:57 UTC)
Re: strings draft tb@xxxxxx (23 Jan 2004 18:48 UTC)
Re: strings draft bear (24 Jan 2004 02:21 UTC)
Re: strings draft tb@xxxxxx (23 Jan 2004 02:09 UTC)
Re: strings draft Tom Lord (23 Jan 2004 02:42 UTC)
Re: strings draft tb@xxxxxx (23 Jan 2004 02:44 UTC)
Re: strings draft Tom Lord (23 Jan 2004 03:07 UTC)
Re: strings draft tb@xxxxxx (23 Jan 2004 03:04 UTC)
Re: strings draft Tom Lord (23 Jan 2004 03:29 UTC)
Re: strings draft tb@xxxxxx (23 Jan 2004 03:42 UTC)
Re: strings draft Alex Shinn (23 Jan 2004 02:34 UTC)
Re: strings draft tb@xxxxxx (23 Jan 2004 02:42 UTC)
Re: strings draft Tom Lord (23 Jan 2004 03:02 UTC)
Re: strings draft Alex Shinn (23 Jan 2004 02:58 UTC)
Re: strings draft tb@xxxxxx (23 Jan 2004 03:13 UTC)
Re: strings draft Alex Shinn (23 Jan 2004 03:18 UTC)
Re: strings draft Bradd W. Szonye (23 Jan 2004 19:31 UTC)
Re: strings draft Alex Shinn (26 Jan 2004 02:21 UTC)
Re: strings draft Bradd W. Szonye (06 Feb 2004 23:30 UTC)
Re: strings draft Bradd W. Szonye (06 Feb 2004 23:33 UTC)
Re: strings draft Alex Shinn (09 Feb 2004 01:45 UTC)
specifying source encoding (Re: strings draft) Shiro Kawai (09 Feb 2004 02:51 UTC)
Re: strings draft Bradd W. Szonye (09 Feb 2004 03:39 UTC)
Re: strings draft tb@xxxxxx (23 Jan 2004 03:12 UTC)
Re: strings draft Alex Shinn (23 Jan 2004 03:28 UTC)
Re: strings draft tb@xxxxxx (23 Jan 2004 03:44 UTC)
Parsing Scheme [was Re: strings draft] Ken Dickey (23 Jan 2004 08:07 UTC)
Re: Parsing Scheme [was Re: strings draft] bear (23 Jan 2004 17:55 UTC)
Re: Parsing Scheme [was Re: strings draft] tb@xxxxxx (23 Jan 2004 18:50 UTC)
Re: Parsing Scheme [was Re: strings draft] Per Bothner (23 Jan 2004 18:56 UTC)
Re: Parsing Scheme [was Re: strings draft] Tom Lord (23 Jan 2004 20:39 UTC)
Re: Parsing Scheme [was Re: strings draft] Per Bothner (23 Jan 2004 20:57 UTC)
Re: Parsing Scheme [was Re: strings draft] Tom Lord (23 Jan 2004 21:57 UTC)
Re: Parsing Scheme [was Re: strings draft] Tom Lord (23 Jan 2004 20:20 UTC)
Re: Parsing Scheme [was Re: strings draft] tb@xxxxxx (23 Jan 2004 21:22 UTC)
Re: Parsing Scheme [was Re: strings draft] Tom Lord (23 Jan 2004 22:52 UTC)
Re: Parsing Scheme [was Re: strings draft] tb@xxxxxx (24 Jan 2004 06:48 UTC)
Re: Parsing Scheme [was Re: strings draft] Tom Lord (24 Jan 2004 18:55 UTC)
Re: Parsing Scheme [was Re: strings draft] tb@xxxxxx (24 Jan 2004 19:34 UTC)
Re: Parsing Scheme [was Re: strings draft] Tom Lord (24 Jan 2004 22:02 UTC)
Re: Parsing Scheme [was Re: strings draft] Ken Dickey (23 Jan 2004 12:53 UTC)
Re: Parsing Scheme [was Re: strings draft] Tom Lord (23 Jan 2004 23:35 UTC)
Re: Parsing Scheme [was Re: strings draft] Ken Dickey (24 Jan 2004 16:10 UTC)
Re: Parsing Scheme [was Re: strings draft] Tom Lord (25 Jan 2004 03:14 UTC)
Re: strings draft Matthew Dempsky (25 Jan 2004 00:00 UTC)
Re: strings draft Tom Lord (25 Jan 2004 07:29 UTC)
Re: strings draft Matthew Dempsky (26 Jan 2004 16:53 UTC)
Re: strings draft Tom Lord (27 Jan 2004 00:44 UTC)

Re: strings draft Alex Shinn 26 Jan 2004 01:58 UTC

At Fri, 23 Jan 2004 16:15:57 -0800 (PST), Tom Lord wrote:
>
>     > From: bear <xxxxxx@sonic.net>
>     > > 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