How do I append one string to another in Python?

If you only have one reference to a string and you concatenate another string to the end, CPython now special cases this and tries to extend the string in place.

The end result is that the operation is amortized O(n).

e.g.

s = ""
for i in range(n):
    s+=str(i)

used to be O(n^2), but now it is O(n).

From the source (bytesobject.c):

void
PyBytes_ConcatAndDel(register PyObject **pv, register PyObject *w)
{
    PyBytes_Concat(pv, w);
    Py_XDECREF(w);
}


/* The following function breaks the notion that strings are immutable:
   it changes the size of a string.  We get away with this only if there
   is only one module referencing the object.  You can also think of it
   as creating a new string object and destroying the old one, only
   more efficiently.  In any case, don't use this if the string may
   already be known to some other part of the code...
   Note that if there's not enough memory to resize the string, the original
   string object at *pv is deallocated, *pv is set to NULL, an "out of
   memory" exception is set, and -1 is returned.  Else (on success) 0 is
   returned, and the value in *pv may or may not be the same as on input.
   As always, an extra byte is allocated for a trailing \0 byte (newsize
   does *not* include that), and a trailing \0 byte is stored.
*/

int
_PyBytes_Resize(PyObject **pv, Py_ssize_t newsize)
{
    register PyObject *v;
    register PyBytesObject *sv;
    v = *pv;
    if (!PyBytes_Check(v) || Py_REFCNT(v) != 1 || newsize < 0) {
        *pv = 0;
        Py_DECREF(v);
        PyErr_BadInternalCall();
        return -1;
    }
    /* XXX UNREF/NEWREF interface should be more symmetrical */
    _Py_DEC_REFTOTAL;
    _Py_ForgetReference(v);
    *pv = (PyObject *)
        PyObject_REALLOC((char *)v, PyBytesObject_SIZE + newsize);
    if (*pv == NULL) {
        PyObject_Del(v);
        PyErr_NoMemory();
        return -1;
    }
    _Py_NewReference(*pv);
    sv = (PyBytesObject *) *pv;
    Py_SIZE(sv) = newsize;
    sv->ob_sval[newsize] = '\0';
    sv->ob_shash = -1;          /* invalidate cached hash value */
    return 0;
}

It’s easy enough to verify empirically.

$ python -m timeit -s"s=''" "for i in xrange(10):s+='a'"
1000000 loops, best of 3: 1.85 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(100):s+='a'"
10000 loops, best of 3: 16.8 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(1000):s+='a'"
10000 loops, best of 3: 158 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(10000):s+='a'"
1000 loops, best of 3: 1.71 msec per loop
$ python -m timeit -s"s=''" "for i in xrange(100000):s+='a'"
10 loops, best of 3: 14.6 msec per loop
$ python -m timeit -s"s=''" "for i in xrange(1000000):s+='a'"
10 loops, best of 3: 173 msec per loop

It’s important however to note that this optimisation isn’t part of the Python spec. It’s only in the cPython implementation as far as I know. The same empirical testing on pypy or jython for example might show the older O(n**2) performance .

$ pypy -m timeit -s"s=''" "for i in xrange(10):s+='a'"
10000 loops, best of 3: 90.8 usec per loop
$ pypy -m timeit -s"s=''" "for i in xrange(100):s+='a'"
1000 loops, best of 3: 896 usec per loop
$ pypy -m timeit -s"s=''" "for i in xrange(1000):s+='a'"
100 loops, best of 3: 9.03 msec per loop
$ pypy -m timeit -s"s=''" "for i in xrange(10000):s+='a'"
10 loops, best of 3: 89.5 msec per loop

So far so good, but then,

$ pypy -m timeit -s"s=''" "for i in xrange(100000):s+='a'"
10 loops, best of 3: 12.8 sec per loop

ouch even worse than quadratic. So pypy is doing something that works well with short strings, but performs poorly for larger strings.

Related Posts:

  1. How do I append one string to another in Python?
  2. How do I append one string to another in Python?
  3. How do I lowercase a string in Python?
  4. What is the difference between Python’s list methods append and extend?
  5. How do I get a substring of a string in Python?
  6. How to read a file line-by-line into a list?
  7. strip(char) on a string
  8. How to convert list to string [duplicate]
  9. TypeError: a bytes-like object is required, not ‘str’ when writing to a file in Python3
  10. Print string to text file
  11. Best way to convert string to bytes in Python 3?
  12. Pythonic way to create a long multi-line string
  13. Best way to convert string to bytes in Python 3?
  14. Does Python have a string ‘contains’ substring method?
  15. TypeError: not all arguments converted during string formatting python
  16. Append values to a set in Python
  17. Random string generation with upper case letters and digits
  18. How can I split and parse a string in Python?
  19. How do you append to a file?
  20. Create a Pandas Dataframe by appending one row at a time
  21. How to read a text file into a string variable and strip newlines?
  22. How to read a text file into a string variable and strip newlines?
  23. Python convert tuple to string
  24. write() versus writelines() and concatenated strings
  25. Why is it string.join(list) instead of list.join(string)?
  26. Why is it string.join(list) instead of list.join(string)?
  27. Split a string into 2 in Python
  28. Best way to strip punctuation from a string
  29. Split string with multiple delimiters in Python [duplicate]
  30. How to check if the string is empty?
  31. ValueError: all the input arrays must have same number of dimensions
  32. How do I convert a list of ascii values to a string in python?
  33. How to check whether a str(variable) is empty or not?
  34. What does the ‘b’ character do in front of a string literal?
  35. Append integer to beginning of list in Python
  36. How to add a string in a certain position?
  37. Remove all special characters, punctuation and spaces from string
  38. This can be done without regex:
  39. How can I concatenate str and int objects?
  40. Convert columns to string in Pandas
  41. How to delete a character from a string using Python
  42. Remove the first character of a string
  43. Convert hex to binary
  44. Quoting backslashes in Python string literals
  45. Python string class like StringBuilder in C#?
  46. AttributeError: ‘list’ object has no attribute ‘replace’ when trying to remove character
  47. How to check if a string is a substring of items in a list of strings?
  48. Best way to replace multiple characters in a string?
  49. How do I remove a substring from the end of a string?
  50. How can I splice a string?
  51. Detect whether a Python string is a number or a letter
  52. Finding all possible permutations of a given string in python
  53. AttributeError: ‘list’ object has no attribute ‘replace’ when trying to remove character
  54. AttributeError: ‘list’ object has no attribute ‘replace’ when trying to remove character
  55. How to convert string to binary?
  56. Converting from a string to boolean in Python?
  57. How to check if type of a variable is string?
  58. Count the number of occurrences of a character in a string
  59. How do I check if there are duplicates in a flat list?
  60. How can I print variable and string on same line in Python?
  61. Append a tuple to a list – what’s the difference between two ways?
  62. Remove quotes from String in Python
  63. Convert hex string to int in Python
  64. How can I check if character in a string is a letter? (Python)
  65. How can I find the first occurrence of a sub-string in a python string?
  66. append new row to old csv file python
  67. How to concatenate items in a list to a single string?
  68. Replacing a character from a certain index
  69. AttributeError: ‘list’ object has no attribute ‘lower’ gensim
  70. Find the nth occurrence of substring in a string
  71. How to convert ‘binary string’ to normal string in Python3?
  72. Properly formatted multiplication table
  73. How to get a function name as a string?
  74. Pandas error “Can only use .str accessor with string values”
  75. How to compare individual characters in two strings in Python 3
  76. Convert a Unicode string to a string in Python (containing extra symbols)python string unicode type-conversion
  77. Create nice column output in python
  78. TypeError: only integer arrays with one element can be converted to an index 3
  79. How to repeat a string with spaces?
  80. TypeError: decoding str is not supported
  81. AttributeError: ‘str’ object has no attribute ‘items’
  82. How to pad zeroes to a string?
  83. How does str(list) work?
  84. What is the difference between a string and a byte string?
  85. How do I convert a string to a double in Python?
  86. How can I copy a Python string?
  87. How to strip a specific word from a string?
  88. List append() in for loop
  89. Checking if a string can be converted to float in Python
  90. How to get ° character in a string in python?
  91. Python cant convert ‘list’ object to str error [closed]
  92. Using strip() to clean up a string
  93. How to append new data onto a new line
  94. Mutable strings in Python
  95. Python code to remove HTML tags from a string 
  96. Cannot concatenate ‘str’ and ‘float’ objects?
  97. How to repeat individual characters in strings in Python
  98. When to use %r instead of %s in Python? [duplicate]
  99. Python – difference between two strings
  100. TypeError: coercing to Unicode: need string or buffer

Leave a Comment

tech