No trees in the stdlib?
steve at REMOVE-THIS-cybersource.com.au
Fri Jul 3 10:39:19 CEST 2009
On Fri, 03 Jul 2009 20:08:20 +1200, Lawrence D'Oliveiro wrote:
> In message <mailman.2446.1246491262.8015.python-list at python.org>, João
> Valverde wrote:
>> Lawrence D'Oliveiro wrote:
>>> Want sorted order?
>>> What could be simpler?
>> Try putting that inside a loop with thousands of iterations and you'll
>> see what the problem is.
> You could apply the same argument to anything. E.g. why create a tree
> structure with a million elements? Try putting that inside a loop with
> thousands of iterations and you'll see what the problem is.
The difference is, it's vanishingly rare to want to build a tree with
millions of elements thousands of times over and over again, but it is
not unreasonable to want to access sorted data thousands of times.
Needing to re-sort it over and over and over again is wasteful, slow and
stupid. Binary trees were invented, in part, specifically to solve this
More information about the Python-list