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

[Alex Martelli]

"Tim Peters" <tim.one at home.com> wrote in message
news:mailman.990526353.5110.python-list at python.org...
> [Alex Martelli]
    ...
> > So, an array.array of characters turns out to be
> > systematically and repeatably 20% faster than a
> > list for this task on my box (an old clunky P3-266
    ...
> One reasonable conclusion to draw is that there are no generally
applicable
> conclusions <wink>.

...particularly given that cStringIO appears to be
almost twice as fast again as the array.array('c')
for this specific task... as per my followup post.

I think the generally applicable conclusion is:
*MEASURE* where the time is going, if/when speed
is a concern when your application is running.  And
if the bottleneck turns out to be a "one char at a
time" string building, try lists, arrays, cStringIO's,
AND powdered bat wings dried in the moonlight over
a hanged man's grave -- one never knows...


Alex