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

Chris Tavares ctavares at develop.com
Tue May 22 08:44:22 CEST 2001

"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

> 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

More information about the Python-list mailing list