[解決済み] Pythonで文字列を別の文字列に追加するにはどうすればよいですか？

質問

Pythonで、ある文字列を別の文字列に追加する効率的な方法が欲しいのですが、以下のような方法はありますか？

var1 = "foo"
var2 = "bar"
var3 = var1 + var2

何か良いビルトインメソッドはないでしょうか？

どのように解決するのですか？

文字列への参照が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=''" "for i in xrange(10):s+='a'"
1000000ループ、ベスト3: 1.85ユーザック/ループ
$ python -m timeit -s"s=''" "for i in xrange(100):s+='a'"
10000ループ、ベスト3：1ループあたり16.8usec
$ python -m timeit -s"s=''" "for i in xrange(1000):s+='a'"
10000ループ、ベスト3：1ループあたり158usec
$ python -m timeit -s"s=''" "for i in xrange(10000):s+='a'"
1000ループ、ベスト3：1.71msec/ループ
$ python -m timeit -s"s=''" "for i in xrange(100000):s+='a'"
10ループ、ベスト3：1ループあたり14.6msec
$ python -m timeit -s"s=''" "for i in xrange(1000000):s+='a'"
10ループ、ベスト3：1ループあたり173ミリ秒

重要なことです しかし、この最適化はPythonの仕様には含まれていないことに注意してください。私の知る限りでは、cPythonの実装にしかありません。pypyやjythonで同じように経験的にテストすると、古いO(n**2)の性能を示すかもしれません。

$ pypy -m timeit -s"s=''" "for i in xrange(10):s+='a'".Pypy -m timeit -s"for i in xrange(10):s+='a'"
10000ループ、ベスト3: 90.8ユーザック/ループ
$ pypy -m timeit -s"s=''" "for i in xrange(100):s+='a'"
1000ループ、ベスト3: 1ループあたり896usec
$ pypy -m timeit -s"s=''" "for i in xrange(1000):s+='a'"
100ループ、ベスト3：1ループあたり9.03msec
$ pypy -m timeit -s"s=''" "for i in xrange(10000):s+='a'"
10ループ、ベスト3：1ループあたり89.5msec

ここまではいいのですが、その後。

$ pypy -m timeit -s"s=''" "for i in xrange(100000):s+='a'".Pypy -m timeit -s"for i in xrange(100000):s+='a'"
10ループ、ベスト3：1ループあたり12.8秒

うっそー、2次関数よりさらに悪い。つまり、pypyは短い文字列ではうまくいくが、大きな文字列ではうまくいかないということをやっているのです。