Мне нужен эффективный способ добавления одной строки к другой в Python, отличный от следующего.
var1 = "foo"
var2 = "bar"
var3 = var1 + var2
Есть ли какой-нибудь хороший встроенный метод, который можно использовать?
Если у вас есть только одна ссылка на строку и вы конкатенируете другую строку в конец, 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: 16,8 юсека на цикл $ python -m timeit -s "s=''" "for i in xrange(1000):s+='a'" 10000 циклов, лучший из 3: 158 usec на цикл $ python -m timeit -s "s=''" "for i in xrange(10000):s+='a'" 1000 циклов, лучший из 3: 1,71 мс на цикл $ python -m timeit -s "s=''" "for i in xrange(100000):s+='a'" 10 циклов, лучший из 3: 14,6 мс на цикл $ python -m timeit -s "s=''" "for i in xrange(1000000):s+='a'" 10 циклов, лучший из 3: 173 мс на цикл
Важно отметить, что эта оптимизация не является частью спецификации Python. Насколько я знаю, она есть только в реализации cPython. То же самое эмпирическое тестирование на pypy или jython, например, может показать более старую производительность O(n**2).
$ pypy -m timeit -s "s=''" "for i in xrange(10):s+='a'" 10000 циклов, лучший из 3: 90.8 usec на цикл $ pypy -m timeit -s "s=''" "for i in xrange(100):s+='a'" 1000 циклов, лучший из 3: 896 usec на цикл $ pypy -m timeit -s "s=''" "for i in xrange(1000):s+='a'" 100 циклов, лучший из 3: 9,03 мс на цикл $ pypy -m timeit -s "s=''" "for i in xrange(10000):s+='a'" 10 циклов, лучший из 3: 89,5 мс на цикл
Пока все хорошо, но потом,
$ pypy -m timeit -s "s=''" "for i in xrange(100000):s+='a'" 10 циклов, лучший из трех: 12,8 секунды на цикл
ой, даже хуже, чем квадратичный. Таким образом, pypy делает что-то, что хорошо работает с короткими строками, но плохо работает с большими строками.
Не оптимизируйте преждевременно. Если у вас нет оснований полагать, что конкатенация строк вызывает узкое место в скорости, просто используйте +
и +=
:
s = 'foo'
s += 'bar'
s += 'baz'
Тем не менее, если вы стремитесь к чему-то вроде Java'StringBuilder, то каноническая идиома Python заключается в добавлении элементов в список и последующем использовании str.join
для объединения их всех в конце:
l = []
l.append('foo')
l.append('bar')
l.append('baz')
s = ''.join(l)
Не стоит.
То есть, в большинстве случаев лучше генерировать всю строку за один раз, а затем добавлять ее к существующей.
Например, не делайте: obj1.name + ":" + str(obj1.count)
.
Вместо этого используйте "%s:%d" % (obj1.name, obj1.count)
.
Это будет проще для чтения и эффективнее.
str1 = "Hello"
str2 = "World"
newstr = " ".join((str1, str2))
Это объединяет str1 и str2 с пробелом в качестве разделителя. Вы также можете сделать "".join(str1, str2, ...)
. Функция str.join()
принимает итерабельную переменную, поэтому вам придется поместить строки в список или кортеж.
Это примерно настолько эффективно, насколько это возможно для встроенного метода.
Если вам нужно выполнить много операций добавления для создания большой строки, вы можете использовать StringIO или cStringIO. Интерфейс похож на файл, т.е. вы пишете
, чтобы добавить в него текст.
Если вы просто добавляете две строки, то просто используйте +
.
Питон 3.6 дает нам Ф-строки, которые приводят в восторг:
var1 = "foo"
var2 = "bar"
var3 = f"{var1}{var2}"
print(var3) # prints foobar
Вы можете делать все, что угодно внутри фигурных скобок
print(f"1 + 1 == {1 + 1}") # prints 1 + 1 == 2
В принципе, никакой разницы. Единственная последовательная тенденция такова, что в Python, кажется, становится медленнее с каждой версией... :(
Списке #
%%timeit
x = []
for i in range(100000000): # xrange on Python 2.7
x.append('a')
x = ''.join(x)
Питон 2.7
1 петля, лучше 3: 7.34 с каждую петлю
В Python 3.4
1 петля, лучше 3: 7.99 с каждую петлю
Питон 3.5
1 петля, лучше 3: 8.48 с каждую петлю
Питон 3.6
1 петля, лучше 3: 9.93 с каждую петлю
Строка #
%%timeit
x = ''
for i in range(100000000): # xrange on Python 2.7
x += 'a'
Питон 2.7:
1 петля, лучше 3: 7.41 х в петле
В Python 3.4
1 петля, лучше 3: 9.08 с каждую петлю
Питон 3.5
1 петля, лучше 3: 8.82 с каждую петлю
Питон 3.6
1 петля, лучше 3: 9.24 с каждую петлю
a='foo'
b='baaz'
a.__add__(b)
out: 'foobaaz'
добавление строк с Добавить функция
str = "Hello"
str2 = " World"
st = str.__add__(str2)
print(st)
Выход
Hello World