文字列を別の文字列に効率的に追加するにはどうすればよいでしょうか? 以下の方法よりも高速な代替手段はありますか?
var1 = "foo"
var2 = "bar"
var3 = var1 + var2
リスト内の複数の文字列の処理については、リスト内の項目を連結（結合）して 1 つの文字列にする方法。
見る変数の値を文字列内に入れる（文字列内に挿入する）にはどうすればよいでしょうか?一部の入力が文字列ではない場合でも、結果は文字列になるはずです。
ベストアンサー1
文字列への参照が 1 つしかなく、その末尾に別の文字列を連結する場合、CPython はこれを特別なケースとして扱い、文字列をその場で拡張しようとします。
最終結果として、この操作は償却 O(n) になります。
例えば
s = ""
for i in range(n):
s += str(i)
以前はO(n^2)でしたが、現在はO(n)です。
詳しくは
ソース (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;
}
経験的に検証するのは簡単です。
$ python -m timeit -s"s=''" "i が xrange(10):s+='a' の場合" 1000000 ループ、ベスト 3: ループあたり 1.85 マイクロ秒 $ python -m timeit -s"s=''" "i が xrange(100):s+='a' の場合" 10000 ループ、ベスト 3: ループあたり 16.8 マイクロ秒 $ python -m timeit -s"s=''" "i が xrange(1000):s+='a' の場合" 10000 ループ、ベスト 3: ループあたり 158 マイクロ秒 $ python -m timeit -s"s=''" "i が xrange(10000) 内にある場合:s+='a'" 1000 ループ、ベスト 3: ループあたり 1.71 ミリ秒 $ python -m timeit -s"s=''" "i が xrange(100000) 内にある場合:s+='a'" 10 ループ、ベスト 3: ループあたり 14.6 ミリ秒 $ python -m timeit -s"s=''" "i が xrange(1000000) 内にある場合:s+='a'" 10 ループ、ベスト 3: ループあたり 173 ミリ秒
ただし、この最適化は Python 仕様の一部ではないことに注意することが重要です。私の知る限り、これは cPython 実装にのみ存在します。たとえば、pypy または jython での同じ実験テストでは、古い O(n**2) パフォーマンスが示される可能性があります。
$ pypy -m timeit -s"s=''" "i が xrange(10):s+='a' の場合" 10000 ループ、ベスト 3: ループあたり 90.8 マイクロ秒 $ pypy -m timeit -s"s=''" "i が xrange(100):s+='a' の場合" 1000 ループ、ベスト 3: ループあたり 896 マイクロ秒 $ pypy -m timeit -s"s=''" "i が xrange(1000):s+='a' の場合" 100 ループ、ベスト 3: ループあたり 9.03 ミリ秒 $ pypy -m timeit -s"s=''" "i が xrange(10000) 内にある場合:s+='a'" 10 ループ、ベスト 3: ループあたり 89.5 ミリ秒
ここまでは順調だったが、
$ pypy -m timeit -s"s=''" "i が xrange(100000) 内にある場合:s+='a'" 10 ループ、ベスト 3: 1 ループあたり 12.8 秒
痛い、二次関数よりもさらにひどい。つまり、pypy は短い文字列ではうまく機能しますが、長い文字列ではパフォーマンスが低下します。