Paul Hankin <[EMAIL PROTECTED]> writes: >> An implementation of sorted dict using a balanced tree as the >> underlying data structure would give decent performance in all the >> mentioned use cases. For example, red-black trees search, insert, >> and delete in O(log n) time. > > But dicts do search, insert and delete in O(1) time, so using some > variety of balanced tree will give you much worse performance when > you're doing regular dict operations.
I wouldn't call it "much worse"; while O(log(n)) is worse than O(1), it's still very fast, which is why popular programming language libraries have an ordered mapping type based on balanced trees. Also note that dict performance can degrade with hash collisions, while trees can maintain complexity guarantees on all operations. In the end, it's a tradeoff. Hash tables offer O(1) access, but lack ordering. Balanced trees offer ordering at the price of O(log n) access. Both have their uses, but neither is syntactic sugar for the other. -- http://mail.python.org/mailman/listinfo/python-list
