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 bear 26 Jan 2004 02:35 UTC


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