95

As a result of the comments in my answer on this thread, I wanted to know what the speed difference is between the += operator and ''.join()

So what is the speed comparison between the two?

2

7 Answers 7

134

From: Efficient String Concatenation

Method 1:

def method1():
  out_str = ''
  for num in xrange(loop_count):
    out_str += 'num'
  return out_str

Method 4:

def method4():
  str_list = []
  for num in xrange(loop_count):
    str_list.append('num')
  return ''.join(str_list)

Now I realise they are not strictly representative, and the 4th method appends to a list before iterating through and joining each item, but it's a fair indication.

String join is significantly faster then concatenation.

Why? Strings are immutable and can't be changed in place. To alter one, a new representation needs to be created (a concatenation of the two).

alt text

9
  • 3
    Well I was going to just answer this myself (hence the tag) but it looks like you beat me to the punch! +1, especially for the useful link! Jun 16, 2010 at 17:12
  • 2
    @Wayne: Useful link is copied from the question that you've linked to! Jun 16, 2010 at 17:17
  • 10
    -1. There is no fixed ratio for the speed difference between string.join and + concatenation, because they have completely different **growth rate**/big oh complexity. As the number of string to concatenate grows, string.join will have greater and greater margin compared to string concatenation.
    – Lie Ryan
    Jun 16, 2010 at 18:14
  • 1
    @nate c: Method 1 is now just a shade slower than method 6 (using Python 2.6), but that's only in CPython. I believe that in Jython, it hasn't been optimised like this, so ''.join(list) remains considerably faster - see the first point in "Programming Recommendations" in PEP 8. Nov 22, 2010 at 5:11
  • 12
    From PEP 8: “For example, do not rely on CPython's efficient implementation of in-place string concatenation for statements in the form a+=b or a=a+b. Those statements run more slowly in Jython. In performance sensitive parts of the library, the ''.join() form should be used instead. This will ensure that concatenation occurs in linear time across various implementations.”
    – Neil G
    Jul 2, 2011 at 8:41
12

Note: This benchmark was informal and is due to be redone because it doesn't show a full picture of how these methods will perform with more realistically long strings. As mentioned in the comments by @Mark Amery, += is not reliably as fast as using f-strings, and str#join isn't as dramatically slower in realistic use cases.

These metrics are also likely outdated by the significant performance improvements introduced by subsequent CPython versions, and most notably, 3.11.


The existing answers are very well-written and researched, but here's another answer for the Python 3.6 era, since now we have literal string interpolation (AKA, f-strings):

>>> import timeit
>>> timeit.timeit('f\'{"a"}{"b"}{"c"}\'', number=1000000)
0.14618930302094668
>>> timeit.timeit('"".join(["a", "b", "c"])', number=1000000)
0.23334730707574636
>>> timeit.timeit('a = "a"; a += "b"; a += "c"', number=1000000)
0.14985873899422586

Test performed using CPython 3.6.5 on a 2012 Retina MacBook Pro with an Intel Core i7 at 2.3 GHz.

6
  • 2
    Please see this answer to a similar question: stackoverflow.com/a/1350289/1202214 += should NOT be used, its performance gains is an illusion. Nov 6, 2018 at 18:45
  • @AndreasBergström nice find. re-running the informal benchmark on the same machine using a = "a"; a = a + "b"; a = a + "c" yields a slight slowdown of 0.1739.
    – Jules
    Nov 7, 2018 at 1:06
  • This is not a fair benchmark. You are not creating the list in a loop which is a significant performance optimization that is not applicable to the general case. Check Dominic's answer for how a fair benchmark should look. Mar 1, 2021 at 10:42
  • @StefanFabian Creating a list in a loop just to pass it to .join is suboptimal and timing such a process shouldn't be part of any benchmark; Dominc's answer is unfairly skewing things against .join by doing so. .join can take an arbitrary iterable of strings; it needn't be a list. As soon as you're joining a significant number of elements, using a generator as the iterable you pass to .join is going to be measurably faster than building a list and passing that to .join.
    – Mark Amery
    Jan 22 at 13:51
  • This answer gives the impression that .join is slower than other kinds of concatenation, but that's only the case because you're only joining three short strings together. Expand this to concatenating large numbers of strings (by either using .join, or using += in a loop) and the results will dramatically reverse, since given an iterable strings containing n strings, result = ''; for x in strings: result += x has O(n²) time complexity while result = ''.join(strings) has O(n) time complexity.
    – Mark Amery
    Jan 22 at 13:55
11

My original code was wrong, it appears that + concatenation is usually faster (especially with newer versions of Python on newer hardware)

The times are as follows:

Iterations: 1,000,000       

Python 3.3 on Windows 7, Core i7

String of len:   1 took:     0.5710     0.2880 seconds
String of len:   4 took:     0.9480     0.5830 seconds
String of len:   6 took:     1.2770     0.8130 seconds
String of len:  12 took:     2.0610     1.5930 seconds
String of len:  80 took:    10.5140    37.8590 seconds
String of len: 222 took:    27.3400   134.7440 seconds
String of len: 443 took:    52.9640   170.6440 seconds

Python 2.7 on Windows 7, Core i7

String of len:   1 took:     0.7190     0.4960 seconds
String of len:   4 took:     1.0660     0.6920 seconds
String of len:   6 took:     1.3300     0.8560 seconds
String of len:  12 took:     1.9980     1.5330 seconds
String of len:  80 took:     9.0520    25.7190 seconds
String of len: 222 took:    23.1620    71.3620 seconds
String of len: 443 took:    44.3620   117.1510 seconds

On Linux Mint, Python 2.7, some slower processor

String of len:   1 took:     1.8840     1.2990 seconds
String of len:   4 took:     2.8394     1.9663 seconds
String of len:   6 took:     3.5177     2.4162 seconds
String of len:  12 took:     5.5456     4.1695 seconds
String of len:  80 took:    27.8813    19.2180 seconds
String of len: 222 took:    69.5679    55.7790 seconds
String of len: 443 took:   135.6101   153.8212 seconds

And here is the code:

from __future__ import print_function
import time

def strcat(string):
    newstr = ''
    for char in string:
        newstr += char
    return newstr

def listcat(string):
    chars = []
    for char in string:
        chars.append(char)
    return ''.join(chars)

def test(fn, times, *args):
    start = time.time()
    for x in range(times):
        fn(*args)
    return "{:>10.4f}".format(time.time() - start)

def testall():
    strings = ['a', 'long', 'longer', 'a bit longer', 
               '''adjkrsn widn fskejwoskemwkoskdfisdfasdfjiz  oijewf sdkjjka dsf sdk siasjk dfwijs''',
               '''this is a really long string that's so long
               it had to be triple quoted  and contains lots of
               superflous characters for kicks and gigles
               @!#(*_#)(*$(*!#@&)(*E\xc4\x32\xff\x92\x23\xDF\xDFk^%#$!)%#^(*#''',
              '''I needed another long string but this one won't have any new lines or crazy characters in it, I'm just going to type normal characters that I would usually write blah blah blah blah this is some more text hey cool what's crazy is that it looks that the str += is really close to the O(n^2) worst case performance, but it looks more like the other method increases in a perhaps linear scale? I don't know but I think this is enough text I hope.''']

    for string in strings:
        print("String of len:", len(string), "took:", test(listcat, 1000000, string), test(strcat, 1000000, string), "seconds")

testall()
10
  • 1
    Your test is wrong. Your strcat will return output as string * len(string) whereas your listcat will always return just the string. How can you compare them? Test with newstr += char or with chars.append(string). This actually proves the point of @bwawok that + is faster than list append. Oct 9, 2013 at 9:35
  • Good catch - that should be newstr += char. Whoops. Fixed, and updated. Oct 9, 2013 at 22:31
  • On my Win 10, desktop Haswell i5, Python 2.7.10 and 3.5.2 machine results are the opposite: strcat is slightly faster: pastebin.com/sVVuExBa
    – Dan M.
    Aug 28, 2016 at 14:11
  • 1
    @DanM.: Did you mean listcat is slightly faster? Because that's what it shows in the Pastebin. Dec 6, 2016 at 16:24
  • @ShadowRanger values in the second column are lower, isn't it supposed to represent strcat (according to print)?
    – Dan M.
    Dec 6, 2016 at 18:07
1

If I expect well, for a list with k string, with n characters in total, time complexity of join should be O(nlogk) while time complexity of classic concatenation should be O(nk).

That would be the same relative costs as merging k sorted list (efficient method is O(nlkg), while the simple one, akin to concatenation is O(nk) ).

0

I rewrote the last answer, could jou please share your opinion on the way i tested?

import time

start1 = time.clock()
for x in range (10000000):
    dog1 = ' and '.join(['spam', 'eggs', 'spam', 'spam', 'eggs', 'spam','spam', 'eggs', 'spam', 'spam', 'eggs', 'spam'])

end1 = time.clock()
print("Time to run Joiner = ", end1 - start1, "seconds")


start2 = time.clock()
for x in range (10000000):
    dog2 = 'spam'+' and '+'eggs'+' and '+'spam'+' and '+'spam'+' and '+'eggs'+' and '+'spam'+' and '+'spam'+' and '+'eggs'+' and '+'spam'+' and '+'spam'+' and '+'eggs'+' and '+'spam'

end2 = time.clock()
print("Time to run + = ", end2 - start2, "seconds")

NOTE: This example is written in Python 3.5, where range() acts like the former xrange()

The output i got:

Time to run Joiner =  27.086106206103153 seconds
Time to run + =  69.79100515996426 seconds

Personally i prefer ''.join([]) over the 'Plusser way' because it's cleaner and more readable.

0

If I say it algorithmically, if you choose [ += ] then it generates a new object and it will be O(n)**2. But if you use [ .join ] then it will be O(n).

0
-3

This is what silly programs are designed to test :)

Use plus

import time

if __name__ == '__main__':
    start = time.clock()
    for x in range (1, 10000000):
        dog = "a" + "b"

    end = time.clock()
    print "Time to run Plusser = ", end - start, "seconds"

Output of:

Time to run Plusser =  1.16350010965 seconds

Now with join....

import time
if __name__ == '__main__':
    start = time.clock()
    for x in range (1, 10000000):
        dog = "a".join("b")

    end = time.clock()
    print "Time to run Joiner = ", end - start, "seconds"

Output Of:

Time to run Joiner =  21.3877386651 seconds

So on python 2.6 on windows, I would say + is about 18 times faster than join :)

5
  • 3
    Your test only uses small string - which gives misleading output, because once you try with longer strings (see my answer) you'll probably see some different results. Also you should use xrange which is cheaper on memory, and you can also omit the 1 in your call to range. Jun 16, 2010 at 17:20
  • Thanks for the tips :) I am still learning Python, more of a side hobby when I need a break from Java.
    – bwawok
    Jun 16, 2010 at 17:28
  • 6
    this is broken on more than one place. check how much is 'a'.join('b') - it is 'b'. What you meant is ''.join(['a', 'b']). Also, 'a'+'b' will likely be optimized to constant during compilation, so what are you testing then, assignment?
    – Nas Banov
    Jun 17, 2010 at 4:42
  • Adding to @NasBanov, even if you fixed it, testing very short concatenations isn't going to test the strengths of join. join wins when it reduces N concatenations (1 allocate, 2 memcpy ops for each concatenation) to a 1 allocation followed by N memcpy operations. Because it involves (expensive) method calls, it will never win in the two operands case. But at least on Python 3.5, you can actually get a win with (in my test case) as little as 4 operands. Dec 6, 2016 at 16:33
  • Also, as a weird consequence of how CPython works, it's actually faster (at least on CPython 3.5) to do mylist += (a,) than to do mylist.append(a). Creating an anonymous tuple (small tuples are cached in a free list, so no allocation occurs) and invoking operator +=, both syntax based with direct support in the bytecode interpreter, is cheaper than calling a method (generic, without special optimizations). For small concatenations, the overhead of stuff like this exceeds the asymptotic expense of the actual concatenations. Dec 6, 2016 at 16:38

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.