Vor- und Nachteile von unveränderlichen Zeichenketten

Question

Einige Sprachen (C# oder Java) haben unveränderliche Zeichenfolgen, während andere (z.B. Ruby) veränderliche haben. Was sind die Gründe hinter diesen Designentscheidungen?

Answer 1

Ein Grund, warum unveränderbare Zeichenfolgen gut sind, ist, dass dies die Unicode-Unterstützung erleichtert. Modernes Unicode passt nicht mehr effizient in eine festgelegte Datenzelle, was die Eins-zu-Eins-Korrespondenz zwischen Zeichenfolgenindex und Speicheradresse aufhebt, die veränderbare Zeichenfolgen so vorteilhaft macht.

---

In der Vergangenheit haben die meisten westlichen Anwendungen einzelbyte-Zeichen verwendet (verschiedene auf ASCII basierende Codierungen oder EBCDIC...), sodass Sie sie effizient behandeln konnten, indem Sie Zeichenfolgen als Bytepuffer behandeln (wie in traditionellen C-Anwendungen).

Als Unicode noch recht neu war, gab es nicht viel Anforderung an etwas außerhalb der ersten 16 Bits, daher verwendete Java doppelbyte-Zeichen für seine Strings (und StringBuffers). Dies hat doppelt so viel Speicher verwendet und ignorierte mögliche Probleme von Unicode-Erweiterungen über 16 Bits hinaus, aber es war damals bequem.

Jetzt ist Unicode nicht mehr so neu, und obwohl die am häufigsten verwendeten Zeichen immer noch in 16 Bits passen, können Sie sich nicht wirklich damit herausreden, dass das Basic Multilingual Plane alles ist, was existiert. Wenn Sie ehrlich behaupten wollen, Unicode-Unterstützung zu haben, benötigen Sie entweder Zeichen mit variabler Länge oder sogar größere (32-Bit?) Zeichenzellen.

Bei Zeichen mit variabler Länge können Sie nicht mehr in O(1) Zeit in einen Zeichenfolgen beliebiger Länge zugreifen - ohne zusätzliche Informationen müssen Sie sich vom Anfang an bis zum N-ten Zeichen durchzählen. Dies tötet auch den Hauptvorteil der veränderbaren Zeichenpuffer: die Fähigkeit, Teile von Zeichenfolgen nahtlos an Ort und Stelle zu ändern.

Zum Glück benötigt die meisten Zeichenfolgenmanipulation diese Möglichkeit zur Änderung vor Ort tatsächlich nicht. Das Lesen, Parsen und Suchen erfolgt alle auf sequentieller, iterativer Basis, von Anfang bis Ende. Die allgemeine Suchen-und-Ersetzen war nie vor Ort, da die Ersetzungszeichenfolge nicht die gleiche Länge wie das Original haben muss.

---

Das Konkatenieren großer Mengen von Teilzeichenfolgen benötigt tatsächlich keine Änderung vor Ort, um effizient zu sein. Sie müssen jedoch vorsichtiger damit umgehen, da ein einfacher Konkatenationsloop (wie andere bereits angemerkt haben) leicht in O(N^2) werden kann, indem für jeden der N Teile Teilzeichenfolgen eine neue Zeichenfolge allokiert wird...

Ein Weg, um eine einfache Konkatenation zu vermeiden, besteht darin, ein veränderbares StringBuffer oder ConcatBuffer-Objekt bereitzustellen, das für effiziente Konkatenation ausgelegt ist. Ein anderer Weg wäre, einen unveränderbaren Zeichenfolgenkonstruktor einzuschließen, der einen Iterator in eine Sequenz von Zeichenfolgen enthält, die (effizient) konkateniert werden sollen.

Aber generell ist es möglich, eine unveränderbare Zeichenfolgenbibliothek zu schreiben, die durch Referenz effizient konkateniert. Diese Art von Zeichenfolge wird oft als "rope" oder "Schnur" bezeichnet, um anzudeuten, dass sie etwas schwerwiegender ist als die grundlegenden Zeichenfolgen, aus denen sie besteht, aber für Konkatenationszwecke ist sie viel effizienter, da sie die Daten überhaupt nicht neu kopieren muss!

Der obige Wikipedia-Link besagt, dass "rope"-Datenstrukturen O(log N) zum Konkatenieren sind, aber das wegweisende Papier "Purely Functional Data Structures" von Okasaki zeigt, wie man Konkatenation in O(1) Zeit durchführt.

Answer 2

Zumindest im Fall von Java lag ein Teil des Grundes für die Unveränderlichkeit von Strings in der Sicherheit und der Thread-Sicherheit. Java legt großen Wert auf Laufzeitsicherheit (ursprünglich wurde es entwickelt, um Set-Top-Boxen und Webbrowsern das Herunterladen und Ausführen von Remote-Inhalten ohne Beeinträchtigung des Host-Systems zu ermöglichen). Um die Sicherheit zu erhöhen, sind Strings unveränderlich und können nicht untergeordnet werden. Das bedeutet, dass die Java-Laufzeit Umgebungen und Benutzern Strings übergeben oder von ihnen empfangen kann, während sichergestellt wird, dass der Wert des Strings konstant bleibt (d. h., ein Angreifer kann den String nicht unterordnen, einen anscheinend gültigen String in eine Funktion übergeben und dann später den Wert ändern, um Zugriff auf falsche Daten zu erhalten, oder alternativ mehrere Threads verwenden, damit ein String zu einem Zeitpunkt korrekt erscheint, der dann jedoch später mutiert wird).

Zusätzlich bieten Unveränderlichkeit Effizienzvorteile in Multithread-Systemen, da keine Sperrung des Strings erforderlich ist. Außerdem ermöglicht es die einfache Implementierung von Teilzeichenfolgenoperationen, da viele Zeichenfolgen das gleiche zugrunde liegende Array von Zeichen teilen können, jedoch mit unterschiedlichen Start- und Endpunkten.

Answer 3

Wenn man darüber nachdenkt, sind alle grundlegenden Datentypen in einem Computer unveränderlich. Du änderst die Ganzzahl 10 nicht in 11, sondern ersetzt 10 durch 11. Indem Zeichenketten grundlegend und unveränderlich sind, ermöglicht das Pooling und andere Optimierungen, die sonst nicht möglich wären.

Answer 4

Was die Nachteile betrifft, erfordern unveränderliche Zeichenfolgen ergänzende veränderbare Datenstrukturen (d.h. String-Puffers), um wirtschaftliches Anfügen, Neuanordnen und andere ähnliche Operationen zu ermöglichen.

Solche Operationen, die über unveränderlichen Strukturen durchgeführt werden, würden unvernünftige Mengen an Ressourcen erfordern.

Programmieren in Lua hat eine brillante Erklärung zum Thema.

---

Um weiter zu reflektieren, haben einige Sprachen (wie Common Lisp) sowohl nicht-destruktive als auch destruktive Funktionen, andere - sowohl unveränderliche als auch veränderliche Listen (Python).

Um ein Buch über Common Lisp zu zitieren:

Wenn Zuweisung so problembehaftet ist, warum sollte man sie dann nicht einfach aus der Sprache weglassen? Es gibt zwei Gründe: Ausdruckskraft und Effizienz. Zuweisung ist der klarste Weg, gemeinsame Daten zu ändern. Und Zuweisung ist effizienter als Bindung. Die Bindung erstellt einen neuen Speicherort, was Speicher zuweist, der zusätzlichen Speicher verbraucht (wenn die Bindung niemals den Gültigkeitsbereich verlässt) oder den Garbage Collector belastet (wenn die Bindung schließlich den Gültigkeitsbereich verlässt).

---

Allerdings verwenden viele JavaScript-Interpreten (die unveränderliche Zeichenfolgen besitzen) Strings auf der Implementierungsebene als veränderliche Arrays.

In ähnlicher Weise hat Clojure Transient, die wie elegante reine Funktionen über unveränderlichen Datenstrukturen aussehen, aber intern mutable Zustände für Effizienz verwenden.