"Vladimir 'Yu' Stepanov" <[EMAIL PROTECTED]> 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:' . - Josiah 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. _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
