Python-Äquivalent zu Java StringBuffer?

73

Gibt es in Python etwas wie Java StringBuffer? Da Zeichenfolgen auch in Python unveränderlich sind, wäre es ineffizient, sie in Schleifen zu bearbeiten.

user2902773
quelle
4
Sie können einen ähnlichen Effekt erzielen, indem Sie eine Liste von Zeichenfolgen erstellen und join()diese nach der Schleife verwenden. Aber ich bin mir sicher, dass es einen pythonischeren Weg gibt (wahrscheinlich mit Listenverständnis).
Joachim Sauer

Antworten:

88

Effiziente String-Verkettung in Python ist ein ziemlich alter Artikel und seine Hauptaussage, dass die naive Verkettung viel langsamer als das Beitreten ist, ist nicht mehr gültig, da dieser Teil seitdem in CPython optimiert wurde:

Details zur CPython-Implementierung: Wenn s und t beide Zeichenfolgen sind, können einige Python-Implementierungen wie CPython normalerweise eine direkte Optimierung für Zuweisungen der Form s = s + t oder s + = t durchführen. Wenn zutreffend, macht diese Optimierung die quadratische Laufzeit viel weniger wahrscheinlich. Diese Optimierung ist sowohl version- als auch implementierungsabhängig. Für leistungsempfindlichen Code wird vorzugsweise die Methode str.join () verwendet, die eine konsistente lineare Verkettungsleistung über Versionen und Implementierungen hinweg gewährleistet. @ http://docs.python.org/2/library/stdtypes.html

Ich habe ihren Code ein wenig angepasst und die folgenden Ergebnisse auf meinem Computer erhalten:

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)

Ergebnisse:

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

Schlussfolgerungen:

  • join gewinnt immer noch über concat, aber am Rande
  • Listenverständnis ist schneller als Schleifen ( beim Erstellen einer Liste )
  • Das Verbinden von Generatoren ist langsamer als das Verbinden von Listen
  • andere Methoden nützen nichts (es sei denn, Sie machen etwas Besonderes)

py3:

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))

Ergebnisse

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
Georg
quelle
2
Es kann nichts wert sein, dass die MutableString-Klasse in Python 2.6 veraltet und in Python 3 vollständig entfernt wurde. Siehe hier
Adam Oren
1
Warnung! Die Aussage, dass CPython dies optimiert, gilt in neueren Versionen (v3.5-v3.8 +) nicht mehr. Dies wurde durch eine Warnung ersetzt, dass die Konzentration von Unveränderlichen auf diese Weise immer quadratisch ist: docs.python.org/3/library/stdtypes.html
jtschoonhoven
@jtschoonhoven: Ich habe den Beitrag in CW umgewandelt, bitte bearbeiten Sie Ihren Kommentar in. Danke!
Georg
14

Kommt darauf an, was du machen willst. Wenn Sie eine veränderbare Sequenz wünschen, ist der eingebaute listTyp Ihr ​​Freund, und das Wechseln von str zu list und zurück ist so einfach wie:

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

Wenn Sie eine große Zeichenfolge mit einer for-Schleife erstellen möchten, besteht die pythonische Methode normalerweise darin, eine Liste von Zeichenfolgen zu erstellen und diese dann mit dem richtigen Trennzeichen (Zeilenumbruch oder was auch immer) zu verbinden.

Andernfalls können Sie auch ein Textvorlagensystem oder einen Parser oder ein für den Job am besten geeignetes Spezialwerkzeug verwenden.

bruno desthuilliers
quelle
Ist die Komplexität von "" .join (mylist) O (n)?
@ user2374515 Ja, die str.join()Methode ist O (n) Komplexität. In der offiziellen Dokumentation heißt es : "Für leistungsempfindlichen Code ist es vorzuziehen, die str.join()Methode zu verwenden , die eine konsistente lineare Verkettungsleistung über Versionen und Implementierungen hinweg gewährleistet ."
Cecil Curry
11

Verwenden Sie möglicherweise ein 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'

Der Reiz der Verwendung eines Bytearrays liegt in seiner Speichereffizienz und praktischen Syntax. Es kann auch schneller sein als die Verwendung einer temporären Liste:

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

Beachten Sie, dass ein Großteil des Geschwindigkeitsunterschieds auf die Erstellung des Containers zurückzuführen ist:

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
unutbu
quelle
Welche Kodierung wird dies verwenden? In Java wären ähnliche Konstrukte sehr problematisch, da sie die Plattform-Standardcodierung verwenden, die alles sein kann ...
Joachim Sauer
@ JoachimSauer: Wie bei a strliegt die Kodierung bei Ihnen. Für das bytearrayist jeder Wert nur ein Byte.
Unutbu
Bytearray kann für wirklich einfache Dinge nützlich sein - wie der Name schon sagt, geht es wirklich um "Arrays von Bytes", nicht um "Zeichenketten".
Bruno Desthuilliers
"... aber es ist langsamer als die Verwendung einer temporären Liste." Was ist eine temporäre Liste? Ist es (Pythons Standard) Liste, wie ['s', 't', 'r', 'i', 'n', 'g']?
fikr4n
@BornToCode: Die temporäre Liste befindet sich mylistim Code von bruno desthuilliers .
Unutbu
6

Die zuvor gegebenen Antworten sind fast immer am besten. Manchmal wird die Zeichenfolge jedoch über viele Methodenaufrufe und / oder Schleifen hinweg aufgebaut, sodass es nicht unbedingt selbstverständlich ist, eine Liste von Zeilen zu erstellen und diese dann zu verbinden. Und da es keine Garantie gibt, dass Sie CPython verwenden oder dass die Optimierung von CPython angewendet wird, besteht ein alternativer Ansatz darin, nur zu verwenden print!

Hier ist ein Beispiel für eine Hilfsklasse, obwohl die Hilfsklasse trivial und wahrscheinlich unnötig ist, dient sie zur Veranschaulichung des Ansatzes (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'
rhaertel80
quelle
2

Dieser Link kann für die Verkettung in Python hilfreich sein

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

Beispiel von oben Link:

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

    return ''.join(sb)

print g()   

# abcdefgabcdefgabcdefgabcdefgab
Kamlesh Arya
quelle
Während dies theoretisch die Frage beantworten kann, wäre es vorzuziehen , die wesentlichen Teile der Antwort hier aufzunehmen und den Link als Referenz bereitzustellen.
Joachim Sauer
2

Nur ein Test, den ich auf Python 3.6.2 durchführe und der zeigt, dass "Join" immer noch BIG gewinnt!

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!")

Und die Ausgabe war:

with format done in 17.991968870162964s
with s done in 18.36879801750183s
with list and join done in 0.12142801284790039s
Roee Gavirel
quelle
1
Wie Sie festgestellt haben, ist die Verwendung von printf und .format zum Konzentrieren von Zeichenfolgen noch weniger effizient.
Gringo Suave
1

Ich habe Roee Gavirels Code 2 zusätzliche Tests hinzugefügt, die schlüssig zeigen, dass das Zusammenfügen von Listen zu Zeichenfolgen nicht schneller ist als s + = "etwas".

Ergebnisse:

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

Code:

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!")
Martlark
quelle
1
Hurra und danke aus der Abteilung "Manchmal ist der einfache Weg der beste Weg."
Lance Kind
-1

In der oberen Antwort verweist der Link von "Efficient String Concatenation in Python" nicht mehr auf die beabsichtigte Seite (leitet stattdessen zu tensorflow.org weiter). Diese Seite aus dem Jahr 2004 mit dem genauen angegebenen Code repräsentiert jedoch wahrscheinlich diese Seite https://waymoot.org/home/python_string/ .

Möglicherweise haben Sie es bereits gesehen, da es zuerst angezeigt wird, wenn Sie googeln:

         efficient python StringBuilder

Ich kann dies nicht in einem Kommentar hinterlassen, da ich nicht privilegiert bin.

Zeichen
quelle
1
Ich werde die ursprüngliche Antwort oben unbearbeitet lassen, um zu dokumentieren, wie dumme Leute im Stackoverflow eine Antwort ablehnen können, die einen nützlichen Link hinzufügt. Inzwischen hat die „Efficient String Concatenation in Python“ nicht mehr Umleitungen zu tensorflow.org, wie skymind.com crunchbase.com/organization/skymind erscheint umfirmiert zu haben welcome.ai/skymind
verkohlt