[Python-Dev] binary trees. Review obmalloc.c
jcarlson at uci.edu
Wed May 3 10:25:35 CEST 2006
"Vladimir 'Yu' Stepanov" <vys at renet.ru> wrote:
> Comparison of functions of sorting and binary trees not absolutely
> correctly. I think that function sort will lose considerably on
> greater lists. Especially after an insert or removal of all one element.
Generally speaking, people who understand at least some of Python's
internals (list internals specifically), will not be *removing* entries
from lists one at a time (at least not using list.pop(0) ), because that
is slow. If they need to remove items one at a time from the smallest
to the largest, they will usually use list.reverse(), then repeatedly
list.pop(), as this is quite fast (in general).
However, as I just said, people usually don't remove items from
just-sorted lists, they tend to iterate over them via 'for i in list:' .
As an aside, I have personally implemented trees a few times for
different reasons. One of the issues I have with most tree
implementations is that it is generally difficult to do things like
"give me the kth smallest/largest item". Of course the standard
solution is what is generally called a "partial order" or "order
statistic" tree, but then you end up with yet another field in your
structure. One nice thing about Red-Black trees combined with
order-statistic trees, is that you can usually use the uppermost bit of
the order statistics for red/black information. Of course, this is
really only interesting from an "implement this in C" perspective;
because if one were implementing it in Python, one may as well be really
lazy and not bother implementing guaranteed balanced trees and be
satisfied with randomized-balancing via Treaps.
Of course all of this discussion about trees in Python is fine, though
there is one major problem. With minimal work, one can construct 3
values such that ((a < b < c) and (c < a)) is true.
More information about the Python-Dev