On 2017-09-16 08:33, Stefan Behnel <python-de@behnel.de> wrote:
Peter J. Holzer schrieb am 16.09.2017 um 09:28:
(String-Konkatenation ist in Python(3) zumindest bei langen Strings auch schön linear)
Es gibt sowohl für bytes-Objekte als auch für Unicode-Strings eine Sonderbehandlung, die realloc() verwendet. Auf vielen Platformen ist realloc() effizient und führt im Durchschnitt zu einer linearen Laufzeit auch bei mehreren Konkatenierungen. Aber nicht auf allen.
Ineffiziente Plattformen sollte man meiden :-). Allerdings ist das eher eine Frage, wie Python damit umgeht als wie gut die Malloc- Implementation ist - obwohl eine gute Malloc-Implementation gewisse Schwächen im Interpreter gut übertünchen kann (wie eine Diskussion zum gleichen Thema in Perl vor ein paar Jahren gezeigt hat).
Außerdem greift die Optimierung nicht in allen Fällen. Beispielsweise hast du Pech, wenn über die Konkatenierungen hinweg der Zeichenraum erst von ASCII auf BMP und dann auf Astral wechselt. Dann muss beim Wechsel der komplette bisherige String doch wieder im Speicher herum kopiert werden.
Das dürfte weitgehend vernachlässigbar sein, weil es maximal 2 solche Übergänge geben kann. Also viel weniger als die Kopiervorgänge, die üblicherweise tatsächlich stattfinden, weil realloc nicht in-place expandieren kann.
Also kurz: join() ist in jedem Fall die bessere Variante bei vielen Strings. Konkatenierung ist ok bei einer überschaubaren Menge und da insbesondere bei kurzen Strings, sollte aber in Schleifen vermieden werden.
Du vergisst, dass Listen einen nicht zu vernachlässigbaren Memory-Overhead haben. Gerade bei langen Listen sollte man darauf verzichten, sie aufzubauen, wenn man sie nicht unbedingt braucht (habe damit erst kürzlich 8 GB eingespart - pro Prozess (das war Perl und nicht Python, aber die beiden Sprachen sind sich da sehr ähnlich)). Kleiner Test: ------------------------------------------------------------------------ #!/usr/bin/python3 import sys import time n = int(sys.argv[1]) t0 = time.clock_gettime(time.CLOCK_MONOTONIC) s = "" for i in range(n): s += str(i) t1 = time.clock_gettime(time.CLOCK_MONOTONIC) print(n, t1-t0, n / (t1 - t0)) ------------------------------------------------------------------------ ------------------------------------------------------------------------ #!/usr/bin/python3 import sys import time n = int(sys.argv[1]) tick_size = 1000000 t0 = time.clock_gettime(time.CLOCK_MONOTONIC) elems = [] for i in range(n): elems.append(str(i)) s = "".join(elems) t1 = time.clock_gettime(time.CLOCK_MONOTONIC) print(n, t1 - t0, n / (t1 - t0)) ------------------------------------------------------------------------ Ergebnis: Performance ist praktisch gleich, aber auf einer 32-Bit-Maschine kommt die Konkatenierungsversion gut 3 mal so weit, bevor sie am Memory-Limit anstößt. (Graphik auf <http://www.hjp.at/programming/python/concat-vs-join/>) hp -- _ | Peter J. Holzer | Fluch der elektronischen Textverarbeitung: |_|_) | | Man feilt solange an seinen Text um, bis | | | hjp@hjp.at | die Satzbestandteile des Satzes nicht mehr __/ | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel