On 14 Sep, 12:46, Antoon Pardon <[EMAIL PROTECTED]> wrote:
> On 2007-09-14, Mark Summerfield <[EMAIL PROTECTED]> wrote:
>
>
>
> > On 14 Sep, 10:49, Antoon Pardon <[EMAIL PROTECTED]> wrote:
> >> > # some time later
> >> > d["e"] = 15
> >> > # later still
> >> > d["b"] = 70
> >> > d.keys() # returns ['a', 'b', 'e', 'm', 'x']
> >> > d.values() # returns [1, 70, 15, 4, 20]
>
> >> which seems to be exactly what my avltree module mentioned earlier
> >> provides.
>
> >> >>> from avltree import Tree
> >> >>> d=Tree(a=1, x=20, b=35, m=4)
> >> >>> d["e"] = 15
> >> >>> d["b"] = 70
> >> >>> d.keys()
>
> >> ['a', 'b', 'e', 'm', 'x']>>> d.values()
>
> >> [1, 70, 15, 4, 20]
>
> > Antoon,
>
> > Your AVL tree looks impressive (although it has five times the lines
> > of my ordereddict), but it does not appear to support dict.update()'s
> > API (which was extended in 2.4), so you can't do: avl.update({'g':
> > 20}, a=9, b=22).
>
> It is true that I didn't follow up the API difference made to dict
> since I wrote the module, but I think these are rather minor.
> I don't think it would take a lot of work to correct these.I'm sure you're right. > > Also, it does not provide the key(), value(), and item() methods that > > the API I proposed can support (because in an ordereddict, index > > positions make sense). > > At the time I wrote my module I never had a need for these. Do you have > a use case or is it a consideration of completeness that makes you want > these? Maybe I can take a look in how to implement this, but at this > moment it doesn't sound that usefull to me. I put them in for completeness, although in some contexts I have found the ability to ask for the n-th item to be v. useful. > On the other hand your API doesn't seem to allow for iterating over only > a part of the keys. Supposing all keys are strings, I can easily iterate > over all keys that start with an 'n' or with any arbitrary prefix. > That IMO seems more usefull. That is an appealing feature---but I don't want to make any assumption about keys (they could be ints, id()s, strs, or anything that is acceptable to a dict. There's nothing to stop you creating a PEP for your AVL tree---I'd certainly be glad for one to be in the collections module. I'm not advocating "only one" ordered data structure, but rather one particular one---and I certainly hope the collections module will have several eventually, and that other people will propose PEPs for other data structures, such as AVL trees, B*Trees, skiplists, etc., since all have something to offer. > > If there was consensus on an API and you, me, and others had different > > implementations, we could always come up with some tests to compare > > their relative performance, and put the fastest one(s) forward in a > > PEP. (I don't care if my own code is used or not, it is the > > functionality in Python's standard library that I want, whoever's code > > it is.) > > Good luck on finding that consensus. If you really want this I fear you > will have to start writing that PEP before a consensus is reached and > hope to find a proposal that will be acceptable to the majority and > especially the BDFL. I don't expect my API to satisfy everyone, but by making it as close to what exists already, i.e., a dict, yet with keys that "happen" to be ordered (and offering a few extra methods to help users exploit that if they want), I am hoping this will make it more likely to be acceptable. -- http://mail.python.org/mailman/listinfo/python-list
