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