[EMAIL PROTECTED] wrote: > Mark> With sorteddict you pay O(log N) for accessing, but you pay > Mark> nothing for sorting. > > Pay me now or pay me later, but maintaining a sorted sequence will always > cost something. > > Skip > Very frequently, however, I want frequent sorted access to a container. I.e. I will want something like "what's the next key bigger than nnn" (I said nnn because it often isn't a string). In such cases a B+Tree or B*Tree is a much better answer than a hash table. I'll grant that for the most common cases hash tables are superior...but not, by any means, for all cases.
There have been cases where I have maintained both a list and a dict for the same data. (Well, the list was an index into the dict, but you get the idea.) The dict was for fast access when I knew the key, and the list was for binary search when I knew things *about* the key. An important note here is that the key to the dict/list was generally NOT a string in these situations. If strings suffice, then I've generally found a hash table to work well enough, and frequently been superior. OTOH, if you don't need continual access while you are building the list, then I agree with you. The problem is that each time you sort a hash table you must pay for an entire sort, while adding a key or two to a B+Tree is relatively cheap. _______________________________________________ Python-3000 mailing list Python-3000@python.org http://mail.python.org/mailman/listinfo/python-3000 Unsubscribe: http://mail.python.org/mailman/options/python-3000/archive%40mail-archive.com
