Algorithmic complexity of StringIO?

[Roy Smith]

I want to build up a long string piece by piece without the quadratic
behavior of string concatenation. I'm looking at the {c,}StringIO
modules as a way around this, but I don't see anything in the docs which
talks about how they work. If I do

s = StringIO.StringIO()
while whatever:
s.write (stringFragment)
return s.getvalue()

will I see quadratic behavior? cStringIO claims to be more efficient,
but doesn't say how. Is it algorithmicly better, or just the same
algorithm recoded in C?

The context here is writing a __str__() method for a container class. I
could envision the containiner holding a couple thousand items, with
len(__str__()) being several 10's of kbytes.

[Paul Moore]

Roy Smith <ro*@panix.com> writes:

will I see quadratic behavior? cStringIO claims to be more efficient,
but doesn't say how. Is it algorithmicly better, or just the same
algorithm recoded in C?

A quick check of the write() method in StringIO shows that it
concatenates blocks of data onto a list (and presumably getvalue()
later does a ''.join()). So you don't get quadratic behaviour even
with StringIO.

Paul.
--
This signature intentionally left blank

[anton muhin]

Roy Smith wrote:

I want to build up a long string piece by piece without the quadratic
behavior of string concatenation. I'm looking at the {c,}StringIO
modules as a way around this, but I don't see anything in the docs which
talks about how they work. If I do

s = StringIO.StringIO()
while whatever:
s.write (stringFragment)
return s.getvalue()

will I see quadratic behavior? cStringIO claims to be more efficient,
but doesn't say how. Is it algorithmicly better, or just the same
algorithm recoded in C?

The context here is writing a __str__() method for a container class. I
could envision the containiner holding a couple thousand items, with
len(__str__()) being several 10's of kbytes.

Hello, Roy!

Common idiom is to use join method:

bunch_of_strings = ["aaa", ... "zzz"]

result = ''.join(bunch_of_strings)

If I'm correct, join preallocates needed space.

hth,
anton.