侃侃无极
如果你只有一个字符串的引用，并且你将另一个字符串连接到结尾，CPython现在特殊情况，并尝试扩展字符串。最终结果是操作是摊销O（n）。例如s = ""for i in range(n): s+=str(i)曾经是O（n ^ 2），但现在是O（n）。从源代码（bytesobject.c）：voidPyBytes_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;}通过经验验证很容易。$ python -m timeit -s“s =''”“for for in xrange（10）：s + ='a'”1000000循环，最佳3：1.85每循环usec$ python -m timeit -s“s =''”“for for in xrange（100）：s + ='a'”10000循环，最佳3：每循环使用16.8次$ python -m timeit -s“s =''”“for x in xrange（1000）：s + ='a'”10000循环，最佳3：158每循环usec$ python -m timeit -s“s =''”“for for in xrange（10000）：s + ='a'”1000个循环，最佳3：每循环1.71毫秒$ python -m timeit -s“s =''”“for x in xrange（100000）：s + ='a'”10个循环，最佳3：每循环14.6毫秒$ python -m timeit -s“s =''”“for x in xrange（1000000）：s + ='a'”10个循环，每个循环最好为3：173毫秒这一点很重要要注意的是这种优化是不是Python的规范的一部分。但是。据我所知，这只是在cPython实现中。例如，对于pypy或jython的相同经验测试可能会显示较旧的O（n ** 2）性能。$ pypy -m timeit -s“s =''”“for x in xrange（10）：s + ='a'”10000循环，最佳3：90.8 usec每循环$ pypy -m timeit -s“s =''”“for for in xrange（100）：s + ='a'”1000循环，最佳3：896 usec每循环$ pypy -m timeit -s“s =''”“for for in xrange（1000）：s + ='a'”100个循环，最佳3：每循环9.03毫秒$ pypy -m timeit -s“s =''”“for for in xrange（10000）：s + ='a'”10个循环，最佳3：每循环89.5毫秒到目前为止很好，但是，$ pypy -m timeit -s“s =''”“for x in xrange（100000）：s + ='a'”10个循环，每个循环最佳3：12.8秒哎哟比二次更糟糕。因此pypy正在做一些适用于短字符串的东西，但对于较大的字符串表现不佳。