On 26 Sep, 11:27, Hrvoje Niksic <[EMAIL PROTECTED]> wrote: > Mark Summerfield <[EMAIL PROTECTED]> writes: > > 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 [...] > > No argument here, as long as the limitation is understood to be a > consequence of the current implementation model. Seriously proposing > a sorteddict that is a mere syntactic sugar over dict dooms the PEP to > rejection.
On the Py3K list GvR made it clear that sorteddict wouldn't be in Python until an implementation had been in popular use for some time... so I will not put forward a PEP for it. > Major programming language libraries have included sorted mapping and > set types for a while now, making the performance and complexity > constraints generally well understood. We should make use of that > knowledge when designing sorteddict. I know! I use Python and C++ and Qt, so what with the STL and Qt's containers I'm used to having far more containers to choose from than Python offers. I think Python could do with both sorteddict and sortedset in the collections module, but to get decent performance will require a balanced tree (or a skiplist) implementation, and I don't have the time to do that. Apart from Antoon Pardon's AVL tree, there's also Chris Gonnerman's RBTree, also pure Python, with a dict API and that seems to accept a cmp function, but again, I don't know whether it could be adapted to the sorteddict((mapping | sequence | nothing), cmp=None, key=None, reverse=None) API that Paul Hankin described. -- http://mail.python.org/mailman/listinfo/python-list
