On 9/26/07, Guido van Rossum <[EMAIL PROTECTED]> wrote: > On 9/26/07, Mark Summerfield <[EMAIL PROTECTED]> wrote:
> > Assuming you have a good sorteddict implementation ... > > you can gain significant performance benefits. > ... sorted dict implementation, the best performance you can get for > random access and random insertions is O(log N), which is always beat > by the O(1) of a hash table It is possible to keep two structures in parallel, so that lookup (using the hash) is still O(1) and traversal (using the tree) is still O(N); the penalty is that you pay for both methods when you do a mutation. (In big O notation, that doesn't matter, but the overhead may be important in practice.) -jJ _______________________________________________ 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
