¿Cómo puedo emular una cadena mutable en Python (como StringBuffer en Java o StringBuilder en C#)?

Dado que las cadenas de Python son inmutables, no es eficiente editarlas repetidamente en bucles. ¿Cómo puedo usar una estructura de datos mutable para implementar operaciones de cadena, a fin de evitar crear muchas cadenas temporales?

Pitón 3

Desde el documentos:

La concatenación de secuencias inmutables siempre da como resultado un nuevo objeto. Esto significa que construir una secuencia por concatenación repetida tendrá un costo de tiempo de ejecución cuadrático en la longitud total de la secuencia. Para obtener un costo de tiempo de ejecución lineal, debe cambiar a una de las siguientes alternativas: si concatena objetos str, puede crear una lista y usar str.join() al final o escribir en una instancia io.StringIO y recuperar su valor cuando esté completo

Experimente para comparar el tiempo de ejecución de varias opciones:

import sys
import timeit
from io import StringIO
from array import array


def test_concat():
    out_str=""
    for _ in range(loop_count):
        out_str += 'abc'
    return out_str


def test_join_list_loop():
    str_list = []
    for _ in range(loop_count):
        str_list.append('abc')
    return ''.join(str_list)


def test_array():
    char_array = array('b')
    for _ in range(loop_count):
        char_array.frombytes(b'abc')
    return str(char_array.tostring())


def test_string_io():
    file_str = StringIO()
    for _ in range(loop_count):
        file_str.write('abc')
    return file_str.getvalue()


def test_join_list_compr():
    return ''.join(['abc' for _ in range(loop_count)])


def test_join_gen_compr():
    return ''.join('abc' for _ in range(loop_count))


loop_count = 80000

print(sys.version)

res = {}

for k, v in dict(globals()).items():
    if k.startswith('test_'):
        res[k] = timeit.timeit(v, number=10)

for k, v in sorted(res.items(), key=lambda x: x[1]):
    print('{:.5f} {}'.format(v, k))

resultados

3.7.5 (default, Nov  1 2019, 02:16:32) 
[Clang 11.0.0 (clang-1100.0.33.8)]
0.03738 test_join_list_compr
0.05681 test_join_gen_compr
0.09425 test_string_io
0.09636 test_join_list_loop
0.11976 test_concat
0.19267 test_array

Pitón 2

Concatenación eficiente de cadenas en Python es un artículo bastante antiguo y su declaración principal de que la concatenación ingenua es mucho más lenta que la unión ya no es válida, porque esta parte se ha optimizado en CPython desde entonces. Desde el documentos:

Detalle de implementación de CPython: si s y t son cadenas, algunas implementaciones de Python, como CPython, generalmente pueden realizar una optimización en el lugar para las asignaciones de la forma s = s + t o s += t. Cuando corresponde, esta optimización hace que el tiempo de ejecución cuadrático sea mucho menos probable. Esta optimización depende tanto de la versión como de la implementación. Para el código sensible al rendimiento, es preferible utilizar el método str.join() que garantiza un rendimiento de concatenación lineal coherente entre versiones e implementaciones.

He adaptado un poco su código y obtuve los siguientes resultados en mi máquina:

from cStringIO import StringIO
from UserString import MutableString
from array import array

import sys, timeit

def method1():
    out_str=""
    for num in xrange(loop_count):
        out_str += `num`
    return out_str

def method2():
    out_str = MutableString()
    for num in xrange(loop_count):
        out_str += `num`
    return out_str

def method3():
    char_array = array('c')
    for num in xrange(loop_count):
        char_array.fromstring(`num`)
    return char_array.tostring()

def method4():
    str_list = []
    for num in xrange(loop_count):
        str_list.append(`num`)
    out_str="".join(str_list)
    return out_str

def method5():
    file_str = StringIO()
    for num in xrange(loop_count):
        file_str.write(`num`)
    out_str = file_str.getvalue()
    return out_str

def method6():
    out_str="".join([`num` for num in xrange(loop_count)])
    return out_str

def method7():
    out_str="".join(`num` for num in xrange(loop_count))
    return out_str


loop_count = 80000

print sys.version

print 'method1=', timeit.timeit(method1, number=10)
print 'method2=', timeit.timeit(method2, number=10)
print 'method3=', timeit.timeit(method3, number=10)
print 'method4=', timeit.timeit(method4, number=10)
print 'method5=', timeit.timeit(method5, number=10)
print 'method6=', timeit.timeit(method6, number=10)
print 'method7=', timeit.timeit(method7, number=10)

Resultados:

2.7.1 (r271:86832, Jul 31 2011, 19:30:53) 
[GCC 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2335.15.00)]
method1= 0.171155929565
method2= 16.7158739567
method3= 0.420584917068
method4= 0.231794118881
method5= 0.323612928391
method6= 0.120429992676
method7= 0.145267963409

Conclusiones:

• join todavía gana sobre concat, pero marginalmente
• las listas de comprensión son más rápidas que los bucles (al crear una lista)
• unir generadores es más lento que unir listas
• otros métodos no sirven (a menos que estés haciendo algo especial)

Depende de lo que quieras hacer. Si desea una secuencia mutable, el incorporado list type es tu amigo, y pasar de str a list y viceversa es tan simple como:

 mystring = "abcdef"
 mylist = list(mystring)
 mystring = "".join(mylist)

Si desea construir una cadena grande usando un bucle for, la forma pitónica generalmente es construir una lista de cadenas y luego unirlas con el separador adecuado (salto de línea o lo que sea).

De lo contrario, también puede usar algún sistema de plantillas de texto, un analizador o cualquier herramienta especializada que sea más apropiada para el trabajo.

Tal vez use un bytearray:

In [1]: s = bytearray('Hello World')

In [2]: s[:5] = 'Bye'

In [3]: s
Out[3]: bytearray(b'Bye World')

In [4]: str(s)
Out[4]: 'Bye World'

El atractivo de usar un bytearray es su eficiencia de memoria y su sintaxis conveniente. También puede ser más rápido que usar una lista temporal:

In [36]: %timeit s = list('Hello World'*1000); s[5500:6000] = 'Bye'; s="".join(s)
1000 loops, best of 3: 256 µs per loop

In [37]: %timeit s = bytearray('Hello World'*1000); s[5500:6000] = 'Bye'; str(s)
100000 loops, best of 3: 2.39 µs per loop

Tenga en cuenta que gran parte de la diferencia de velocidad se atribuye a la creación del contenedor:

In [32]: %timeit s = list('Hello World'*1000)
10000 loops, best of 3: 115 µs per loop

In [33]: %timeit s = bytearray('Hello World'*1000)
1000000 loops, best of 3: 1.13 µs per loop

Las respuestas proporcionadas anteriormente son casi siempre las mejores. Sin embargo, a veces la cadena se crea a través de muchas llamadas a métodos y/o bucles, por lo que no es necesariamente natural crear una lista de líneas y luego unirlas. Y dado que no hay garantía de que esté utilizando CPython, o de que se aplicará la optimización de CPython, un enfoque alternativo es simplemente usar print!

Aquí hay una clase auxiliar de ejemplo, aunque la clase auxiliar es trivial y probablemente innecesaria, sirve para ilustrar el enfoque (Python 3):

import io

class StringBuilder(object):

    def __init__(self):
        self._stringio = io.StringIO()
    
    def __str__(self):
        return self._stringio.getvalue()
    
    def append(self, *objects, sep=' ', end=''):
        print(*objects, sep=sep, end=end, file=self._stringio)

sb = StringBuilder()
sb.append('a')
sb.append('b', end='\n')
sb.append('c', 'd', sep=',', end='\n')
print(sb)  # 'ab\nc,d\n'

He agregado al código de Roee Gavirel 2 pruebas adicionales que muestran de manera concluyente que unir listas en cadenas no es más rápido que s += “algo”, hasta Python 3.6. Las versiones posteriores tienen resultados diferentes.

Resultados:

Python 2.7.15rc1    

Iterations: 100000
format    done in 0.317540168762s
%s        done in 0.151262044907s
list+join done in 0.0055148601532s
str cat   done in 0.00391721725464s
    
Python 3.6.7

Iterations: 100000
format    done in 0.35594654083251953s
%s        done in 0.2868080139160156s
list+join done in 0.005924701690673828s
str cat   done in 0.0054128170013427734s
f str     done in 0.12870001792907715s

Python 3.8.5

Iterations: 100000
format    done in 0.1859891414642334s
%s        done in 0.17499303817749023s
list+join done in 0.008001089096069336s
str cat   done in 0.014998912811279297s
f str     done in 0.1600024700164795s

Código:

from time import time


def _with_cat(i):
    _st=""
    for i in range(0, i):
        _st += "0"
    return _st


def _with_f_str(i):
    _st=""
    for i in range(0, i):
        _st = f"{_st}0"
    return _st


def _with_format(i):
    _st=""
    for i in range(0, i):
        _st = "{}{}".format(_st, "0")
    return _st


def _with_s(i):
    _st=""
    for i in range(0, i):
        _st = "%s%s" % (_st, "0")
    return _st


def _with_list(i):
    l = []
    for i in range(0, i):
        l.append("0")
    return "".join(l)


def _count_time(name, i, func):
    start = time()
    r = func(i)
    total = time() - start
    print("%s done in %ss" % (name, total))
    return r


iteration_count = 100000

print('Iterations: {}'.format(iteration_count))
r1 = _count_time("format   ", iteration_count, _with_format)
r2 = _count_time("%s       ", iteration_count, _with_s)
r3 = _count_time("list+join", iteration_count, _with_list)
r4 = _count_time("str cat  ", iteration_count, _with_cat)
r5 = _count_time("f str    ", iteration_count, _with_f_str)

if len(set([r1, r2, r3, r4, r5])) != 1:
    print("Not all results are the same!")

este enlace podría ser útil para la concatenación en python

http://pythonadventures.wordpress.com/2010/09/27/stringbuilder/

ejemplo del enlace de arriba:

def g():
    sb = []
    for i in range(30):
        sb.append("abcdefg"[i%7])

    return ''.join(sb)

print g()   

# abcdefgabcdefgabcdefgabcdefgab

¡Solo una prueba que ejecuté en python 3.6.2 que muestra que “unirse” todavía gana GRANDE!

from time import time


def _with_format(i):
    _st=""
    for i in range(0, i):
        _st = "{}{}".format(_st, "0")
    return _st


def _with_s(i):
    _st=""
    for i in range(0, i):
        _st = "%s%s" % (_st, "0")
    return _st


def _with_list(i):
    l = []
    for i in range(0, i):
        l.append("0")
    return "".join(l)


def _count_time(name, i, func):
    start = time()
    r = func(i)
    total = time() - start
    print("%s done in %ss" % (name, total))
    return r

iterationCount = 1000000

r1 = _count_time("with format", iterationCount, _with_format)
r2 = _count_time("with s", iterationCount, _with_s)
r3 = _count_time("with list and join", iterationCount, _with_list)

if r1 != r2 or r2 != r3:
    print("Not all results are the same!")

Y la salida fue:

with format done in 17.991968870162964s
with s done in 18.36879801750183s
with list and join done in 0.12142801284790039s