On 26 Sep, 13:22, Antoon Pardon <[EMAIL PROTECTED]> wrote: > 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.
I think you missed some of the previous postings. The sorteddict API that has emerged so far is (1) apart from the constructor, everything is identical to dict, (2) the constructor takes the same args as sorted(), so if you want to seed with a dict or with keywords you write sorteddict(dict(a=1,b=2), ...), (or you could create a sorteddict and use update() since that takes the same args as dict's constructor). Could your AVLTree support cmp and keys and reverse? -- http://mail.python.org/mailman/listinfo/python-list
