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

[Chris Tavares]

"Helen Dawson" <helend at accessone.com> wrote in message
news:3B09FBF9.8691EBFE at accessone.com...
> The following script tests appending to a list and to a string.
>
[... snipped offending code ...]
>
> So, why can't string do that?
>
> When we could only go string = string + " " then fixing this problem
> was probably impossible, but with += it seems like it should be quite
> possible - maybe even easy!
>

You're forgetting one thing - strings are IMMUTABLE. Doing s += " " doesn't
add anything to s, it creates a NEW string who's contents just happens to be
a space concatenated to the old s. And please don't ask for mutable
strings - immutability is the right answer here (just look at all the
complexities that the C++ std lib people went through to make
std::basic_string mutable, and it still doesn't work correctly in many
cases.)

> Right now if I am producing a text file a character at a time I have
> to do it to a list and then use string.join() to convert at the end.
> That works, but seems clunky.
>

This is one correct solution. Strings are not buffers, and should not be
used as such.

Another solution would be to use something that IS expected to act like a
buffer - the cStringIO module. The interface is a little different - this
one works like a file:

import cStringIO

def AppendTest2( io ):
    for i in range(100):
        for j in range(2000):
            io.write( " " )
        print i

This is visible faster on my box (Win2k, Python 2.1) than either the list or
string versions shown above.

--

Chris Tavares