O(n^2) is bad - can it be fixed?

[Carlos Ribeiro]

At 22:32 31/05/01 -0400, Tim Peters wrote:
>... Guido had more than enough of
>slowing down every case to cater to unreasonable cases when he worked on
>ABC.  As a result, Python's builtin types strive to be just as dumb as
>possible <0.9 wink>.

I can see the wisdom of Guido on this. Taken separately, each little such 
"optimization" slows down the most common case very little. Looking only at 
it it seems reasonable. But when you get hundreds of such optimizations, 
the resulting code is bloated and *much* slower that the simpler one would 
ever be.

Anyway, (as said before) Python nature makes it easy to solve it my means 
of extensions. A different list implementation could be done and exposed 
using some well known interfaces. Maybe it proves to be faster for every 
case; if it does so, nobody would mind patching The Source with it, dont 
you think?

Who's volunteer? :-)


Carlos Ribeiro