Algorithmic complexity of StringIO?

Discussion in 'Python' started by Roy Smith, Sep 13, 2003.

  1. Roy Smith

    Roy Smith Guest

    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.
    Roy Smith, Sep 13, 2003
    #1
    1. Advertising

  2. Roy Smith

    Paul Moore Guest

    Roy Smith <> 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
    Paul Moore, Sep 13, 2003
    #2
    1. Advertising

  3. Roy Smith

    anton muhin Guest

    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.
    anton muhin, Sep 13, 2003
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Skip Montanaro
    Replies:
    0
    Views:
    143
    Skip Montanaro
    May 30, 2013
  2. Cameron Simpson
    Replies:
    0
    Views:
    86
    Cameron Simpson
    May 31, 2013
  3. Göktuğ Kayaalp
    Replies:
    0
    Views:
    107
    Göktuğ Kayaalp
    May 31, 2013
  4. Skip Montanaro
    Replies:
    0
    Views:
    102
    Skip Montanaro
    May 31, 2013
  5. Serhiy Storchaka
    Replies:
    0
    Views:
    72
    Serhiy Storchaka
    May 31, 2013
Loading...

Share This Page