On Sun, Mar 9, 2014 at 1:27 AM, Marko Rauhamaa <ma...@pacujo.net> wrote: > Dan Stromberg <drsali...@gmail.com>: > >> On Sat, Mar 8, 2014 at 1:21 PM, Marko Rauhamaa <ma...@pacujo.net> wrote: >>> If I had to choose between a hash table and AVL (or RB) tree in the >>> standard library, it would definitely have to be the latter. It is more >>> generally usable, has fewer corner cases and probably has an equal >>> performance even in hash tables' sweet spot. >> >> Actually, in the performance comparison I mentioned previously, I >> compared Python dict's to a bunch of different balanced trees and one >> unbalanced tree. The dictionary was much faster, though granted, it >> was the only one in C. > > Yes, that is one major detail. There must be many more.
This is not just a detail: O(1) tends to be beat O(logn) pretty easily for large n. -- https://mail.python.org/mailman/listinfo/python-list