On 2007-09-26, Mark Summerfield <[EMAIL PROTECTED]> wrote: > 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.
Well you should decide what you want. In a previous exchange one of the things that was wanted was that you could already seed a tree by using key word arguments so that you could do the following: t=Tree(a=15, b=30) which would be equivallent to: t=Tree() t.update(a=15,b=30) But with the above proposal t=Tree(cmp=cmp) is not equivallent to t=Tree() t.update(cmp=cmp) So it seems the API needs some more sorting out. -- Antoon Pardon -- http://mail.python.org/mailman/listinfo/python-list
