Ist es ineffizient, Zeichenfolgen einzeln zu verketten?

11

Ich erinnere mich aus meiner Zeit als Programmierer in C, dass das Betriebssystem beim Verbinden von zwei Zeichenfolgen Speicher für die verknüpfte Zeichenfolge zuweisen muss, dann kann das Programm den gesamten Zeichenfolgentext in den neuen Bereich im Speicher kopieren, dann muss der alte Speicher manuell veröffentlicht werden. Wenn dies also mehrmals erfolgt, wie im Fall des Beitritts zu einer Liste, muss das Betriebssystem ständig mehr und mehr Speicher zuweisen, um ihn nach der nächsten Verkettung freizugeben. Eine viel bessere Möglichkeit, dies in C zu tun, besteht darin, die Gesamtgröße der kombinierten Zeichenfolgen zu bestimmen und den erforderlichen Speicher für die gesamte verknüpfte Liste von Zeichenfolgen zuzuweisen.

In modernen Programmiersprachen (z. B. C #) werden die Inhalte von Sammlungen häufig zusammengefügt, indem die Sammlung durchlaufen und alle Zeichenfolgen einzeln zu einer einzelnen Zeichenfolgenreferenz hinzugefügt werden. Ist das nicht ineffizient, auch bei moderner Rechenleistung?

JSideris
quelle
Überlassen Sie es dem Compiler und Profiler, sie werden sich darum kümmern, Ihre Zeit ist viel teurer als die Zeit für die Verkettung von Strings.
OZ_
7
Hängt von der Implementierung ab - Sie sollten die Dokumentation für Ihre bestimmte Zeichenfolgenbibliothek wirklich überprüfen. Es ist möglich, Zeichenfolgen, die durch Referenz verkettet sind, in O (1) -Zeit zu implementieren. In jedem Fall sollten Sie Klassen oder Funktionen verwenden, die für diese Art von Dingen entwickelt wurden, wenn Sie eine beliebig lange Liste von Zeichenfolgen verketten müssen.
Comingstorm
Beachten Sie, dass Dinge wie die Verkettung von Zeichenfolgen im Allgemeinen von einer Bibliotheksfunktion und nicht vom Betriebssystem ausgeführt werden. Das Betriebssystem ist möglicherweise an der Speicherzuweisung beteiligt, jedoch wahrscheinlich nicht für relativ kleine Objekte wie Zeichenfolgen.
Caleb
@Caleb Das Betriebssystem ist an der ALL-Speicherzuweisung beteiligt. Die Nichtbeachtung dieser Regel ist eine Art Speicherverlust. Die Ausnahme ist, wenn die Anwendung fest codierte Zeichenfolgen enthält. Diese werden als Binärdaten innerhalb der generierten Assembly geschrieben. Sobald Sie jedoch eine Zeichenfolge bearbeiten (oder vielleicht sogar zuweisen), muss sie im Speicher gespeichert werden (dh der Speicher muss zugewiesen werden).
JSideris
4
@Bizorke In einem typischen Szenario wird ein Speicherzuweiser wie malloc () (der Teil der C-Standardbibliothek und nicht des Betriebssystems ist) verwendet, um verschiedene Speicherblöcke aus dem Speicher zuzuweisen, der dem Prozess bereits vom Betriebssystem zugewiesen wurde. Das Betriebssystem muss sich nicht einmischen, es sei denn, der Prozess hat wenig Arbeitsspeicher und muss mehr anfordern. Es kann auch auf einer niedrigeren Ebene teilnehmen, wenn eine Zuordnung einen Seitenfehler verursacht. Ja, das Betriebssystem stellt letztendlich den Speicher bereit, aber es ist nicht unbedingt an der schrittweisen Zuweisung von Zeichenfolgen und anderen Objekten innerhalb des Prozesses beteiligt.
Caleb

Antworten:

21

Ihre Erklärung, warum es ineffizient ist, ist korrekt, zumindest in den Sprachen, mit denen ich vertraut bin (C, Java, C #), obwohl ich nicht zustimmen würde, dass es allgemein üblich ist, massive Mengen an String-Verkettung durchzuführen. In dem C # -Code, an dem ich arbeite StringBuilder, String.Formatwird häufig usw. verwendet. Dies sind alles speichersparende Techniken, um eine Überzuweisung zu vermeiden.

Um zur Antwort auf Ihre Frage zu gelangen, müssen wir eine andere Frage stellen: Wenn es nie wirklich ein Problem ist, Zeichenfolgen zu verketten, warum möchten StringBuilderund StringBufferexistieren Klassen ? Warum ist die Verwendung solcher Klassen auch in Programmierbüchern und -klassen für Anfänger enthalten? Warum sollten scheinbar ausgereifte Optimierungsratschläge so wichtig sein?

Wenn die meisten Entwickler, die Zeichenfolgen verketten, ihre Antwort nur auf Erfahrung stützen würden, würden die meisten sagen, dass dies niemals einen Unterschied macht, und würden die Verwendung solcher Tools zugunsten der "besser lesbaren" vermeiden for (int i=0; i<1000; i++) { strA += strB; }. Aber sie haben es nie gemessen.

Die eigentliche Antwort auf diese Frage findet sich in dieser SO-Antwort , aus der hervorgeht, dass in einem Fall beim Verketten von 50.000 Zeichenfolgen (die je nach Anwendung häufig vorkommen) selbst kleine Zeichenfolgen zu einem 1000- fachen Leistungseinbruch führten .

Wenn Leistung buchstäblich überhaupt nichts bedeutet, verketten Sie sie auf jeden Fall. Aber ich würde nicht zustimmen , dass Alternativen (String) schwierig oder weniger lesbar mit , und daher wäre eine vernünftige Vorgehensweise zu programmieren sein , dass sollte nicht um die „vorzeitige Optimierung“ Verteidigung.

AKTUALISIEREN:

Ich denke, es kommt darauf an, Ihre Plattform zu kennen und ihre Best Practices zu befolgen, die leider nicht universell sind . Zwei Beispiele aus zwei verschiedenen "modernen Sprachen":

  1. In einer anderen SO-Antwort wurde festgestellt, dass die genau entgegengesetzten Leistungsmerkmale (array.join vs + =) in JavaScript manchmal zutreffen . In einigen Browsern scheint die Verkettung von Zeichenfolgen automatisch optimiert zu werden, in anderen Fällen jedoch nicht. Die Empfehlung (zumindest in dieser SO-Frage) lautet also, nur zu verketten und sich keine Sorgen zu machen.
  2. In einem anderen Fall ein Java - Compiler kann automatisch Verkettung mit einem effizienteren Konstrukt wie String ersetzen. Wie andere bereits betont haben, ist dies jedoch unbestimmt, nicht garantiert, und die Verwendung von StringBuilder beeinträchtigt die Lesbarkeit nicht. In diesem speziellen Fall würde ich eher davon abraten, die Verkettung für große Sammlungen zu verwenden oder mich auf ein unbestimmtes Verhalten des Java-Compilers zu verlassen. In ähnlicher Weise wird in .NET niemals eine Optimierung der Sortierung durchgeführt .

Es ist nicht gerade eine Hauptsünde, nicht jede Nuance jeder Plattform sofort zu kennen, aber wichtige Plattformprobleme wie diese zu ignorieren, wäre fast so, als würde man von Java zu C ++ wechseln und sich nicht um die Freigabe von Speicher kümmern.

Kevin McCormick
quelle
-1: enthält Haupt-BS. strA + strBist genau das gleiche wie mit einem StringBuilder. Es hat einen 1x Performance-Hit. Oder 0x, je nachdem, wie Sie messen. Für weitere Informationen
amara
5
@sparkleshy: Ich vermute, dass die SO-Antwort Java verwendet und Ihr verlinkter Artikel C # verwendet. Ich stimme denen zu, die sagen "hängt von der Implementierung ab" und "messen Sie es für Ihre spezielle Umgebung".
Kai Chan
1
@ KaiChan: String-Verkettung ist im Grunde die gleiche in Java und C #
Amara
3
@sparkleshy - Punkt genommen, aber die Verwendung von StringBuilder, String.Join usw., um genau zwei Zeichenfolgen zu verketten, ist selten eine Empfehlung. Ferner bezieht sich die Frage des OP speziell auf "den Inhalt von Sammlungen , die zusammengefügt werden", was nicht der Fall ist (wo StringBuilder usw. sehr zutreffend ist). Unabhängig davon werde ich mein Beispiel aktualisieren, um mehr auf den Punkt zu bringen.
Kevin McCormick
3
Für die Frage interessiert mich die Sprache nicht. Die Verwendung von Stringbuilder hinter den Kulissen in einigen Sprachen erklärt, warum es möglicherweise nicht ineffizient ist, eine ganze Liste von Strings zu verketten, was meine Frage beantwortet. Diese Antwort erklärte jedoch, dass das Beitreten zu einer Liste möglicherweise gefährlich sein kann, und empfahl den Stringbuilder als Alternative. Ich empfehle, Ihrer Antwort den Stringbuilder des Compilers hinter den Kulissen hinzuzufügen, um einen möglichen Reputationsverlust oder eine Fehlinterpretation zu vermeiden.
JSideris
2

Es ist ungefähr aus den von Ihnen beschriebenen Gründen nicht effizient. Zeichenfolgen in C # und Java sind unveränderlich. Operationen an Zeichenfolgen geben eine separate Instanz zurück, anstatt die ursprüngliche zu ändern, anders als in C. Wenn mehrere Zeichenfolgen verkettet werden, wird bei jedem Schritt eine separate Instanz erstellt. Das Zuweisen und spätere Sammeln dieser nicht verwendeten Instanzen durch Müll kann zu Leistungseinbußen führen. Nur dieses Mal wird die Speicherverwaltung für Sie vom Garbage Collector übernommen.

Sowohl C # als auch Java führen eine StringBuilder-Klasse als veränderbare Zeichenfolge speziell für diese Art von Aufgaben ein. Ein Äquivalent in C würde eine verknüpfte Liste verketteter Zeichenfolgen verwenden, anstatt sie in einem Array zu verbinden. C # bietet auch eine praktische Join-Methode für Strings zum Verbinden einer Sammlung von Strings.

scrwtp
quelle
1

Genau genommen ist die Nutzung von CPU-Zyklen weniger effizient, sodass Sie richtig liegen. Aber was ist mit Entwicklerzeit, Wartungskosten usw. Wenn Sie die Zeitkosten zur Gleichung hinzufügen, ist es fast immer effizienter, das zu tun, was am einfachsten ist, und bei Bedarf die langsamen Bits zu profilieren und zu optimieren.
"Die erste Regel der Programmoptimierung: Tun Sie es nicht. Die zweite Regel der Programmoptimierung (nur für Experten!): Tun Sie es noch nicht."

mattnz
quelle
3
keine sehr effektiven Regeln, denke ich.
OZ_
@OZ_: Dies ist ein weit verbreitetes Zitat (Michael A. Jackson) und ein anderes von Donald Knuth ... Dann gibt es dieses, das ich normalerweise nicht benutze. "Mehr Computersünden werden im Namen der Effizienz begangen ( ohne es unbedingt zu erreichen) als aus irgendeinem anderen Grund - einschließlich blinder Dummheit. "
Mattnz
2
Ich sollte darauf hinweisen, dass Michael A. Jackson ein Brite war, also ist es Optimierung, nicht Optimierung . Irgendwann sollte ich die Wikipedia-Seite wirklich korrigieren . * 8 ')
Mark Booth
Ich stimme vollkommen zu, Sie sollten diese Rechtschreibfehler korrigieren. Obwohl meine Muttersprache Queens English ist, fällt es mir leichter, US im Internet zu sprechen .......
mattnz
wird nicht jemand an die Benutzer denken. Sie können es für den Entwickler etwas schneller machen, aber dann leidet jeder einzelne Ihrer Kunden darunter. Schreiben Sie Ihren Code für sie, nicht für Sie.
Gbjbaanb
1

Ohne einen praktischen Test ist es sehr schwer, etwas über die Leistung zu sagen. Kürzlich war ich sehr überrascht, als ich herausfand, dass in JavaScript eine naive String-Verkettung normalerweise schneller war als die empfohlene Lösung "Liste erstellen und beitreten" ( hier testen , t1 mit t4 vergleichen). Ich bin immer noch verwirrt darüber, warum das passiert.

Einige Fragen, die Sie möglicherweise stellen, wenn Sie über die Leistung (insbesondere über die Speichernutzung) nachdenken, sind: 1) Wie groß ist meine Eingabe? 2) Wie schlau ist mein Compiler? 3) Wie verwaltet meine Laufzeit den Speicher? Dies ist nicht erschöpfend, aber es ist ein Ausgangspunkt.

  1. Wie groß ist mein Input?

    Eine komplexe Lösung hat häufig einen festen Overhead, möglicherweise in Form von zusätzlichen Operationen, die ausgeführt werden müssen, oder möglicherweise in Form von zusätzlichem Speicher, der benötigt wird. Da diese Lösungen für große Fälle ausgelegt sind, haben die Implementierer normalerweise kein Problem damit, diese zusätzlichen Kosten einzuführen, da der Nettogewinn wichtiger ist als die Mikrooptimierung des Codes. Wenn Ihre Eingabe ausreichend klein ist, hat eine naive Lösung möglicherweise eine bessere Leistung als die komplexe, wenn auch nur, um diesen Overhead zu vermeiden. (zu bestimmen, was "ausreichend klein" ist, ist jedoch der schwierige Teil)

  2. Wie schlau ist mein Compiler?

    Viele Compiler sind intelligent genug, um Variablen, die geschrieben, aber nie gelesen werden, zu "optimieren". Ebenso kann ein guter Compiler möglicherweise eine naive Zeichenfolgenverkettung in eine (Kern-) Bibliotheksverwendung konvertieren. Wenn viele von ihnen ohne Lesevorgänge ausgeführt werden, muss sie zwischen diesen Vorgängen nicht wieder in eine Zeichenfolge konvertiert werden (auch wenn Ihr Quellcode scheint genau das zu tun. Ich kann nicht sagen, ob oder in welchem ​​Umfang Compiler dies tun oder nicht (AFAIK Java ersetzt mindestens mehrere Concats im selben Ausdruck durch eine Folge von StringBuffer-Operationen), aber es ist eine Möglichkeit.

  3. Wie verwaltet meine Laufzeit den Speicher?

    In modernen CPUs ist der Engpass normalerweise nicht der Prozessor, sondern der Cache. Wenn Ihr Code in kurzer Zeit auf viele "entfernte" Speicheradressen zugreift, überwiegt die Zeit, die benötigt wird, um den gesamten Speicher zwischen den Cache-Ebenen zu verschieben, die meisten Optimierungen in den verwendeten Anweisungen. Dies ist besonders wichtig bei Laufzeiten mit Garbage Collectors der Generation, da sich die zuletzt erstellten Variablen (z. B. innerhalb desselben Funktionsumfangs) normalerweise in zusammenhängenden Speicheradressen befinden. Diese Laufzeiten verschieben den Speicher auch routinemäßig zwischen Methodenaufrufen hin und her.

    Eine Möglichkeit, die Verkettung von Zeichenfolgen zu beeinflussen (Haftungsausschluss: Dies ist eine wilde Vermutung, ich bin nicht sicher genug, um dies mit Sicherheit zu sagen), wäre, wenn der Speicher für die naive Person nahe dem Rest des Codes zugewiesen würde, der ihn verwendet (sogar) Wenn es mehrmals zugewiesen und freigegeben wird), während der Speicher für das Bibliotheksobjekt weit davon entfernt zugewiesen wurde (daher ändern sich die vielen Kontextänderungen, während Ihr Code berechnet, die Bibliothek verbraucht, Ihr Code mehr berechnet usw., und es entstehen viele Cache-Fehler). Natürlich werden bei großen Eingaben OTOH die Cache-Fehler trotzdem auftreten, so dass das Problem der Mehrfachzuweisungen stärker wird.

Trotzdem befürworte ich nicht die Verwendung dieser oder jener Methode, sondern nur, dass Tests, Profilerstellung und Benchmarking jeder theoretischen Analyse der Leistung vorausgehen sollten, da die meisten Systeme heutzutage einfach zu komplex sind, um sie ohne tiefes Fachwissen zu verstehen.

mgibsonbr
quelle
Ja, ich stimme zu, dass dies definitiv ein Bereich ist, in dem ein Compiler theoretisch erkennen könnte, dass Sie versuchen, eine Reihe von Zeichenfolgen zusammenzufügen und dann zu optimieren, als ob Sie einen Zeichenfolgen-Builder verwenden würden. Dies ist jedoch kaum eine triviale Sache, und ich glaube nicht, dass sie in modernen Compilern implementiert ist. Sie haben mir gerade eine großartige Idee für ein Forschungsprojekt für Studenten gegeben: D.
JSideris
Überprüfen Sie diese Antwort , die der Java-Compiler bereits StringBuilderunter der Haube verwendet. Alles, was er tun müsste, ist, nicht aufzurufen, toStringbis die Variable tatsächlich benötigt wird. Wenn ich mich richtig erinnere, geschieht dies für einen einzelnen Ausdruck. Mein einziger Zweifel ist, ob er für mehrere Anweisungen in derselben Methode gilt oder nicht. Ich weiß nichts über .NET-Interna, aber ich glaube, dass der C # -Compiler auch eine ähnliche Strategie anwenden könnte.
mgibsonbr
0

Joel hat vor einiger Zeit einen großartigen Artikel zu diesem Thema geschrieben. Wie einige andere betont haben, ist es stark von der Sprache abhängig. Aufgrund der Art und Weise, wie Zeichenfolgen in C implementiert werden (nullterminiert, ohne Längenfeld), ist die Standardroutine der strcat-Bibliothek sehr ineffizient. Joel präsentiert eine Alternative mit nur einer kleinen Änderung, die viel effizienter ist.

tcrosley
quelle
-1

Ist es ineffizient, Zeichenfolgen einzeln zu verketten?

Nein.

Haben Sie "Die traurige Tragödie des Mikrooptimierungstheaters" gelesen ?

Jim G.
quelle
4
"Vorzeitige Optimierung ist die Wurzel allen Übels." - Knuth
Scott C Wilson
4
Die Wurzel allen Übels in der Optimierung liegt darin, diesen Satz ohne Kontext zu verwenden.
OZ_
Nur zu sagen, dass etwas wahr ist, ohne einige unterstützende Gründe anzugeben, ist in einem Forum wie diesem nicht nützlich.
Edward Strange
@ Crazy Eddie: Hast du gelesen, warum Jeff Atwood zu sagen hatte?
Jim G.