Balanced trees

[Marko Rauhamaa]

Joshua Landau <joshua at landau.ws>:

> The thing we really need is for the blist containers to become stdlib
> (but not to replace the current list implementation).

Very interesting. Downloaded blist but didn't compile it yet. It *could*
be the missing link.

I would *love* to see some comparative performance results between
blist.sorteddict and an AVL tree. A B+ tree could be nicer to the CPU
cache, but then again, the cache line is only a few pointers wide and
there appears to be a lot of shoving stuff left and right -- based on a
10-second "analysis" of the code:

        while (src >= stop)
                *dst-- = *src--;

Personally, I find it a bit odd to place lists at the center of the
proposal and have trees come out as a side effect. I would rather see it
the other way round: sorteddict -> sortedset et al.

> * It reduces demand for trees:

I would hope it would satisfy the demand for trees.

> nobody jumps at blists because they're rarely the obvious solution.

I haven't jumped at them because they were nowhere to be found on <URL:
http://docs.python.org/3/genindex-B.html>.


Marko