Re: No trees in the stdlib?

Aahz wrote:
In article <mailman.2170.1246042676.8015.python-list@xxxxxxxxxx>,
=?ISO-8859-1?Q?Jo=E3o_Valverde?= <backup95@xxxxxxxxxx> 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.
.

Relevant Pages

  • Re: hide python code !
    ... doors or installing burglar alarms, ... Compiling code to machine language isn't like locking your door. ... Compiling code doesn't prevent me from seeing your code or your algorithm, ... Would you argue that Python source code hides your ...
    (comp.lang.python)
  • String similarity
    ... The algorithm that I have chosen for the comparison between string was ... Python reducing the code from 1394 lines of "C" to 152 lines of Python ... Initially I have rearranged part of "C" code in one module "simil" ... Comparing string this is not possible and the only way that I have found ...
    (comp.lang.python)
  • Re: hide python code !
    ... Compiling code to machine language isn't like locking your door. ... Compiling code doesn't prevent me from seeing your code or your algorithm, ... Would you argue that Python source code hides your ... 'imperfect protection' with 'pointless protection'. ...
    (comp.lang.python)
  • Re: Singly Linked LIst and Objects Newbie Question
    ... Hm it seems that my algorithm and datastructure knowledge is really ... I had never even heard of red-black trees or 2-3-4 trees or any ... So for example you want to write an assertion that evaluates a complex ... boolean method1_checkAssert{ ...
    (comp.lang.java.programmer)
  • Re: Slowness!
    ... I am using the python profiler - and ... >>LOS algorithm for a simpler one that takes less time. ... >>I will stick with Python until I feel the code is as fast as I can make ...
    (rec.games.roguelike.development)