Seit meiner allerersten Programmierstunde in der High School habe ich gehört, dass Saitenoperationen langsamer - dh teurer - sind als die mythische "durchschnittliche Operation". Warum macht sie so langsam? (Diese Frage ist absichtlich weit gefasst.)

"Die durchschnittliche Operation" findet auf Grundelementen statt. Aber selbst in Sprachen, in denen Zeichenfolgen als Primitive behandelt werden, sind sie immer noch Arrays unter der Haube, und alles, was die gesamte Zeichenfolge betrifft, benötigt O (N) Zeit, wobei N die Länge der Zeichenfolge ist.

Zum Beispiel erfordert das Hinzufügen von zwei Nummern im Allgemeinen 2-4 ASM-Anweisungen. Das Verketten ("Hinzufügen") zweier Zeichenfolgen erfordert eine neue Speicherzuordnung und entweder eine oder zwei Zeichenfolgenkopien, die die gesamte Zeichenfolge betreffen.

Bestimmte Sprachfaktoren können es noch schlimmer machen. In C beispielsweise ist eine Zeichenfolge einfach ein Zeiger auf ein nullterminiertes Zeichenarray. Das bedeutet, dass Sie nicht wissen, wie lange es dauert, und daher keine Möglichkeit besteht, eine Zeichenfolgen-Kopierschleife mit schnellen Verschiebevorgängen zu optimieren. Sie müssen jeweils ein Zeichen kopieren, damit Sie jedes Byte auf den Nullterminator testen können.

^{Dies ist ein alter Thread und ich denke, dass die anderen Antworten großartig sind, aber etwas übersehen, also hier sind meine (späten) 2 Cent.}

Syntaktische Zuckerbeschichtung verbirgt Komplexität

Das Problem mit Strings ist, dass sie in den meisten Sprachen Bürger zweiter Klasse sind und tatsächlich die meiste Zeit nicht wirklich Teil der Sprachspezifikation selbst sind: Sie sind ein in der Bibliothek implementiertes Konstrukt mit einigen gelegentlichen syntaktischen Zuckerbeschichtungen auf der Oberseite um sie weniger schmerzhaft zu machen.

Die direkte Folge davon ist, dass die Sprache einen großen Teil ihrer Komplexität vor Ihren Augen verbirgt und Sie für die versteckten Nebenwirkungen bezahlen, weil Sie sich angewöhnen, sie genau wie eine atomare Einheit auf niedriger Ebene zu betrachten andere primitive Typen (wie durch die Antwort mit den höchsten Bewertungen und andere erklärt).

Implementierungsdetails

Gute alte Reihe

Eines der Elemente dieser zugrunde liegenden "Komplexität" ist, dass die meisten String-Implementierungen auf die Verwendung einer einfachen Datenstruktur mit zusammenhängendem Speicherplatz zurückgreifen würden, um den String darzustellen: Ihr gutes altes Array.

Dies ist jedoch sinnvoll, da der Zugriff auf die gesamte Zeichenfolge schnell erfolgen soll. Dies bedeutet jedoch möglicherweise schreckliche Kosten, wenn Sie diese Zeichenfolge manipulieren möchten. Der Zugriff auf ein Element in der Mitte ist schnell, wenn Sie wissen, nach welchem ​​Index Sie suchen , aber wenn Sie nach einem Element suchen , das auf einer Bedingung basiert, ist dies nicht der Fall.

Das Zurückgeben der Zeichenfolge kann sogar kostspielig sein, wenn Ihre Sprache die Länge der Zeichenfolge nicht zwischenspeichert und sie zum Zählen von Zeichen durchlaufen muss.

Aus ähnlichen Gründen erweist sich das Hinzufügen von Elementen zu Ihrer Zeichenfolge als kostspielig, da Sie höchstwahrscheinlich Speicher neu zuweisen müssen, damit dieser Vorgang ausgeführt werden kann.

Daher verfolgen verschiedene Sprachen unterschiedliche Ansätze für diese Probleme. Java hat sich beispielsweise die Freiheit genommen, seine Zeichenfolgen aus bestimmten gültigen Gründen (Caching-Länge, Thread-Sicherheit) unveränderlich zu machen, und seine veränderlichen Gegenstücke (StringBuffer und StringBuilder) werden sich dafür entscheiden, Größe mithilfe größerer Blöcke zuzuweisen, die nicht zugeordnet werden müssen jedes Mal, sondern hoffen auf Best-Case-Szenarien. Es funktioniert im Allgemeinen gut, aber die Kehrseite ist, manchmal für Gedächtnisstörungen zu bezahlen.

Unicode-Unterstützung

Auch und gerade deshalb, weil die syntaktische Zuckerbeschichtung Ihrer Sprache dies vor Ihnen verbirgt, um gut zu spielen, halten Sie es oft nicht für Unicode-Unterstützung (insbesondere solange Sie es nicht wirklich brauchen) und gegen die Wand stoßen). Und einige Sprachen, die vorausschauend denken, implementieren keine Strings mit darunter liegenden Arrays von einfachen 8-Bit-Zeichenprimitiven. Sie wurden in UTF-8 oder UTF-16 gebacken oder was-hast-du-Unterstützung für Sie, und die Folge ist ein enorm höherer Speicherverbrauch, der oftmals nicht benötigt wird, und eine längere Verarbeitungszeit zum Zuweisen von Speicher, Verarbeiten der Zeichenfolgen. und implementieren Sie die gesamte Logik, die mit der Manipulation von Codepunkten einhergeht.

Das Ergebnis all dessen ist, dass, wenn Sie im Pseudocode etwas Äquivalentes tun zu:

hello = "hello,"
world = " world!"
str = hello + world

Es kann sein, dass es trotz aller Bemühungen der Sprachentwickler nicht so ist, wie Sie es möchten:

a = 1;
b = 2;
shouldBeThree = a + b

Im Anschluss möchten Sie vielleicht lesen:

• Ist es ineffizient, Zeichenfolgen einzeln zu verketten?

Der Ausdruck "durchschnittliche Operation" ist wahrscheinlich eine Abkürzung für eine einzelne Operation einer theoretischen Maschine mit wahlfreiem Zugriff und gespeichertem Programm . Dies ist die theoretische Maschine, mit der üblicherweise die Laufzeit verschiedener Algorithmen analysiert wird.

Die generischen Operationen sind normalerweise Laden, Addieren, Subtrahieren, Speichern und Verzweigen. Vielleicht auch lesen, drucken und anhalten.

Die meisten Zeichenfolgenoperationen erfordern jedoch mehrere dieser grundlegenden Operationen. Beispielsweise erfordert das Duplizieren einer Zeichenfolge normalerweise einen Kopiervorgang und daher eine Anzahl von Vorgängen, die proportional zur Länge einer Zeichenfolge sind (dh, sie ist "linear"). Das Suchen eines Teilstrings in einem anderen String ist ebenfalls linear komplex.

Es hängt ganz von der Operation ab, wie Zeichenfolgen dargestellt werden und welche Optimierungen vorhanden sind. Wenn Strings 4 oder 8 Bytes lang (und ausgerichtet) sind, wären sie nicht unbedingt langsamer - viele Operationen wären genauso schnell wie Primitive. Wenn alle Zeichenfolgen über einen 32-Bit- oder 64-Bit-Hash verfügen, sind viele Operationen ebenfalls genauso schnell (obwohl Sie die Hashing-Kosten im Voraus bezahlen).

Es kommt auch darauf an, was Sie mit "langsam" meinen. Die meisten Programme verarbeiten Zeichenfolgen sehr schnell für das, was benötigt wird. Zeichenfolgenvergleiche sind möglicherweise nicht so schnell wie der Vergleich von zwei Ints, aber nur die Profilerstellung zeigt, was "langsam" für Ihr Programm bedeutet.

Lassen Sie mich Ihre Frage mit einer Frage beantworten. Warum dauert das Sprechen einer Wortfolge länger als das Sprechen eines einzelnen Wortes?