On Mon, 1 Oct 2001 danielv@netvision.net.il wrote:
Well, I really cannot say who said what, or who I'm answering to, but - In Celeste, this could make recovery after image crashes faster. With SortedCollections re-adding the n logged actions done before the crash takes n^2 time, with SkipLists, presumably, n*log(n).
Or we could tweak Celeste to not update this list during recovery, and resort it once later. Still nicer to just have nice behaving data structures...
Anyone know what this thing eats in memory usage?
*hint* Just CC me this sort of request. I'm a CS theory weenie. :)
Skip lists use variable sized nodes (1-32 references), in most implementations, the expected number of references per node is two. Making them the same expected overhead as splay trees or doubly-linked lists. Given squeak header overhead, this means an expected 5 longwords/node (2 header, 2 for navigation, one for the data).
Given their extra size and complexity, they're probably not worth it unless you've got at least 20 nodes and a pretty high update rate.
Though, may I suggest refactoring skiplists so that they subclass OrderedCollection, and implement the same interface as SortedCollection so that they are a drop-in replacement.
SortedCollection is the right choice for what you're doing. Its not your fault that the implementation is not perfect. IE, don't fix your code, fix SortedCollection by making an alternate O(log n) implementation.
Scott