On 26 Sep, 09:51, Hrvoje Niksic <[EMAIL PROTECTED]> wrote: > Duncan Booth <[EMAIL PROTECTED]> writes: > > I that's the point though: you can't write one implementation that has good > > performance for all patterns of use > > 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.
Basically, as implemented, I have to invalidate if there is any change to a key _or_ to a value because if cmp or key functions are specified they could be using the key, the value, or even both. (If key and cmp were both None and reverse was False, I could use the bisect module and maintain the keys in sorted order at all times in that case, but then performance would vary considerably depending on use which I think would be v. confusing for users.) You are quite right that using a balanced tree (red-black, AVL, or b*tree) would provide decent performance in all the use cases. There appear to be two on PyPI (rbtree and pyavl), but both seem to be C extensions. Antoon Pardon has a pure Python AVL tree, but whether he could or would produce a version that had the sorteddict API, I don't know. -- http://mail.python.org/mailman/listinfo/python-list
