Efficient String Concatenation in Python • Hacker News Board

Re: Efficient String Concatenation in Python

#11

Post by pdonis » Sat, Sep 07, 2013, 9:13 PM UTC

gamegoblin wrote: post #6

I believe that the current most efficient way of doing this is ''.join(map(str, range(n)))

In Python 2, itertools.imap will be faster since it doesn't realize a list. Also, if you are memory constrained, xrange doesn't realize a list either, whereas range does (but the article notes that range was slightly faster than xrange in his tests--I don't know if that's still true in Python 2, the article is 9 years old).

In Python 3, the map builtin is basically equivalent what itertools.imap was in Python 2, so it is the best choice. (Also, the range builtin in Python 3 no longer realizes a list.)

Re: Efficient String Concatenation in Python

#12

Post by pdonis » Sat, Sep 07, 2013, 9:15 PM UTC

zeeboo wrote: post #3

Note these tests were run on Python 2.2 which makes the results old enough to almost certainly be invalid. Last time I checked, straight string concatenation was faster than everything else for the types of inputs I was dealing with.

straight string concatenation was faster than everything else

As I understand it, this is implementation dependent. CPython has gone to some lengths to optimize its string concatenation code to do things behind the scenes that are basically equivalent to some of the faster methods given in the article. Other Python implementations have not necessarily done that, so string concatenation can be a lot slower.

Re: Efficient String Concatenation in Python

#13

Post by pdonis » Sat, Sep 07, 2013, 9:16 PM UTC

idank wrote: post #7

kstrauser wrote: post #2

How would a method 7 using generator expressions fare on the same system, like: return ''.join(`num` for num in xrange(loop_count)) On one hand, it avoids creating a temporary list in memory. On the other, it can't know in advance how long the final output of the loop will be and so couldn't use tricks like preallocating enough RAM.

Does join scan the entire input to know the exact size and allocate that at the start? Doesn't it do the usual thing for resizing and that is to double the capacity? A generator will save a temporary list, it will however result in a lot of overhead for the generator switches. It might be beneficial if the input is really big.

Does join scan the entire input to know the exact size and allocate that at the start?

No, because that would make the algorithm quadratic again (one loop for the scan, second loop for the concatenation), and the whole point of the join idiom, as recommended by the Python documentation, is to avoid a quadratic algorithm.

Re: Efficient String Concatenation in Python

#14

Post by thomasahle » Sat, Sep 07, 2013, 9:21 PM UTC

pdonis wrote: post #13

idank wrote: post #7

Earlier quoted context omitted.

Does join scan the entire input to know the exact size and allocate that at the start? Doesn't it do the usual thing for resizing and that is to double the capacity? A generator will save a temporary list, it will however result in a lot of overhead for the generator switches. It might be beneficial if the input is really big.

Does join scan the entire input to know the exact size and allocate that at the start? No, because that would make the algorithm quadratic again (one loop for the scan, second loop for the concatenation), and the whole point of the join idiom, as recommended by the Python documentation, is to avoid a quadratic algorithm.

Two loops are still linear as long as they are not nested ;-)

Re: Efficient String Concatenation in Python

#15

Post by dbarlett » Sat, Sep 07, 2013, 9:34 PM UTC

gamegoblin wrote: post #5

kstrauser wrote: post #2

How would a method 7 using generator expressions fare on the same system, like: return ''.join(`num` for num in xrange(loop_count)) On one hand, it avoids creating a temporary list in memory. On the other, it can't know in advance how long the final output of the loop will be and so couldn't use tricks like preallocating enough RAM.

Interestingly enough, this is pretty much the example given for the timemit module: http://docs.python.org/2/library/timeit.html Results: $ python -m timeit '"-".join(str(n) for n in range(100))' 10000 loops, best of 3: 40.3 usec per loop $ python -m timeit '"-".join([str(n) for n in range(100)])' 10000 loops, best of 3: 33.4 usec per loop $ python -m timeit '"-".join(map(str, range(100)))' 10000 loops, best of 3: 25…

I just ran those with Python 2.7 (ASCII and Unicode) and Python 3.2 (Unicode). "-".join(map(str, range(100))) was always the fastest, with ASCII (2.7) Full results: https://gist.github.com/dbarlett/6479378

Re: Efficient String Concatenation in Python

#16

Post by kingkilr » Sat, Sep 07, 2013, 9:58 PM UTC

zokier wrote: post #10

anaphor wrote: post #9

Earlier quoted context omitted.

Does PyPy have the same heuristic? If not, I wouldn't recommend relying on it.

If not, I would recommend submitting a bug to PyPy.

No it doesn't, and that heuristic isn't possible. It's based on looking at the reference counting and mutating an immutable object. It's pretty awful.

Re: Efficient String Concatenation in Python

#17

Post by kingkilr » Sat, Sep 07, 2013, 9:59 PM UTC

If you really care about efficiency (and are using PyPy), an actually efficient way to concat strings:

    from __pypy__.builders import StringBuilder
    builder = StringBuilder()
    for i in xrange(10000):
        builder.append(str(i))
    return builder.build()

Re: Efficient String Concatenation in Python

#18

Post by pdonis » Sat, Sep 07, 2013, 11:01 PM UTC

thomasahle wrote: post #14

pdonis wrote: post #13

Earlier quoted context omitted.

Does join scan the entire input to know the exact size and allocate that at the start? No, because that would make the algorithm quadratic again (one loop for the scan, second loop for the concatenation), and the whole point of the join idiom, as recommended by the Python documentation, is to avoid a quadratic algorithm.

Two loops are still linear as long as they are not nested ;-)

Oops, yes, good point. :)

Re: Efficient String Concatenation in Python

#19

Post by mappu » Sat, Sep 07, 2013, 11:37 PM UTC

For comparison, PHP has mutable strings. Some totally unscientific averaged benchmarks (Atom D2700, PHP 5.4.4-14 amd64):

    $buff = '';
    for ($i = 0; $i != 100000; ++$i) {
            $buff .= $i;
    }

Runs in about 0.06s

    $buff = array();
    for ($i = 0; $i != 100000; ++$i) {
            $buff[] = $i;
    }
    $ret = implode('', $buff);

Runs slower, in about 0.10s

    $ret = implode('', range(0, 100000));

Takes roughly the same time, 0.10s

Re: Efficient String Concatenation in Python

#20

Post by dbecker » Sat, Sep 07, 2013, 11:38 PM UTC

Doing stuff efficiently is great when there's some benefit from efficiency. But I've seen a lot of fragile code (and implementation specific hacks) created based on benchmarks, when the time savings were meaningless in practice.