Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Algorithmic complexity of StringIO?

Reply
Thread Tools

Algorithmic complexity of StringIO?

 
 
Roy Smith
Guest
Posts: n/a
 
      09-13-2003
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.
 
Reply With Quote
 
 
 
 
Paul Moore
Guest
Posts: n/a
 
      09-13-2003
Roy Smith <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
anton muhin
Guest
Posts: n/a
 
      09-13-2003
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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Algorithmic vs design complexity Vidar Hasfjord C++ 4 03-30-2011 02:11 AM
algorithmic mathematical art Xah Lee Java 4 05-07-2006 06:59 PM
Algorithmic complexity & STL Generic Usenet Account C++ 3 04-11-2005 07:52 AM
Algorithmic complexity & STL Generic Usenet Account Computer Information 3 04-11-2005 07:52 AM
Algorithmic complexity of len (list)? Roy Smith Python 8 07-06-2004 10:45 PM



Advertisments