No trees in the stdlib?
backup95 at netcabo.pt
Sat Jun 27 07:42:21 CEST 2009
> In article <mailman.2170.1246042676.8015.python-list at python.org>,
> =?ISO-8859-1?Q?Jo=E3o_Valverde?= <backup95 at netcabo.pt> wrote:
>> What's lacking is an associative array that preserves ordering, doesn't
>> require a hash function and has fast insertions and deletions in
>> O(log(n)). The particular algorithm to achieve this is a secondary
>> issue. It's a BST for sure, AVL vs RBT vs something else. It's my fault
>> for having opened the topic with simply "trees" instead, it would have
>> avoided this vagueness problem, but I'm genuinely surprised to know
>> there are no data structures that efficiently support such a common need
>> in Python. And I really enjoy the using this language.
> Why AVL/RBT instead of B*? It's not that simple.... Another problem is
> that unless the tree is coded in C, the constant factors are going to
> swamp algorithmic complexity for many use cases -- that in turn makes it
> more difficult to deploy a PyPI library for real-world testing.
I wouldn't consider anything other than C for such a module on
efficiency alone, unless it was a prototype of course. But I have little
knowledge about the Python C API.
About B* trees, again not an expert but I don't see how the added
complexity brings any noticeable advantage to implement the associative
array data structure I mentioned. Simple is better.
> Anyway, I'm *not* trying to discourage you, just explain some of the
> roadblocks to acceptance that likely are why it hasn't already happened.
> If you're serious about pushing this through, you have two options:
> * Write the code and corresponding PEP yourself (which leads to the
> second option, anyway)
> * Lobby on the python-ideas mailing list
Currently I don't have a strong need for this. I just believe it would
be a benefit to a language I like a lot. Lobbying isn't my thing. I'd
rather write code, but neither am I the most qualified person for the
job. It would certainly be interesting and fun and challenging in a good
way and a great way to learn some new stuff. But I would definitely need
mentoring or asking some silly questions on the mailing list. Maybe I'll
seriously consider it some other time.
More information about the Python-list