Wenn Zeichenfolgen in .NET unveränderlich sind, warum benötigt Substring dann O (n) Zeit?

451

Angesichts der Tatsache, dass Zeichenfolgen in .NET unveränderlich sind, frage ich mich, warum sie so konzipiert wurden, dass stattdessen string.Substring()O ( substring.Length) Zeit benötigtO(1) ?

dh was waren die Kompromisse, wenn überhaupt?

user541686
quelle
3
@Mehrdad: Ich mag diese Frage. Können Sie mir bitte sagen, wie wir O () einer bestimmten Funktion in .Net bestimmen können? Ist es klar oder sollten wir es berechnen? Vielen Dank
odiseh
1
@odiseh: Manchmal (wie in diesem Fall) ist es klar, dass die Zeichenfolge kopiert wird. Wenn dies nicht der Fall ist, können Sie entweder in der Dokumentation nachsehen, Benchmarks durchführen oder im .NET Framework-Quellcode nachsehen, um herauszufinden, um was es sich handelt.
user541686

Antworten:

423

UPDATE: Diese Frage hat mir so gut gefallen, dass ich sie nur gebloggt habe. Siehe Saiten, Unveränderlichkeit und Ausdauer


Die kurze Antwort lautet: O (n) ist O (1), wenn n nicht groß wird. Die meisten Leute extrahieren winzige Teilzeichenfolgen aus winzigen Zeichenfolgen, daher ist es völlig irrelevant , wie die Komplexität asymptotisch wächst .

Die lange Antwort lautet:

Eine unveränderliche Datenstruktur, die so aufgebaut ist, dass Operationen an einer Instanz die Wiederverwendung des Speichers des Originals mit nur einer geringen Menge (typischerweise O (1) oder O (lg n)) des Kopierens oder der neuen Zuweisung ermöglichen, wird als "persistent" bezeichnet. unveränderliche Datenstruktur. Zeichenfolgen in .NET sind unveränderlich. Ihre Frage lautet im Wesentlichen: "Warum sind sie nicht hartnäckig?"

Denn wenn Sie sich Operationen ansehen, die normalerweise für Zeichenfolgen in .NET-Programmen ausgeführt werden, ist es in jeder relevanten Hinsicht kaum schlimmer , einfach eine völlig neue Zeichenfolge zu erstellen. Die Kosten und Schwierigkeiten beim Aufbau einer komplexen persistenten Datenstruktur machen sich nicht bezahlt.

Normalerweise verwenden die Leute "Teilzeichenfolge", um eine kurze Zeichenfolge - beispielsweise zehn oder zwanzig Zeichen - aus einer etwas längeren Zeichenfolge zu extrahieren - vielleicht ein paar hundert Zeichen. Sie haben eine Textzeile in einer durch Kommas getrennten Datei und möchten das dritte Feld extrahieren, bei dem es sich um einen Nachnamen handelt. Die Zeile wird vielleicht ein paar hundert Zeichen lang sein, der Name wird ein paar Dutzend sein. Die Zuweisung von Zeichenfolgen und das Kopieren von Speicher von fünfzig Bytes ist auf moderner Hardware erstaunlich schnell . Es ist auch irrelevant , eine neue Datenstruktur zu erstellen, die aus einem Zeiger auf die Mitte einer vorhandenen Zeichenfolge plus einer Länge besteht . "schnell genug" ist per Definition schnell genug.

Die extrahierten Teilzeichenfolgen sind typischerweise klein und von kurzer Lebensdauer; Der Müllsammler wird sie bald zurückfordern, und sie haben überhaupt nicht viel Platz auf dem Haufen eingenommen. Die Verwendung einer dauerhaften Strategie, die die Wiederverwendung des größten Teils des Speichers fördert, ist also auch kein Gewinn. Alles, was Sie getan haben, ist, dass Ihr Garbage Collector langsamer wird, da er sich jetzt um den Umgang mit Innenzeigern kümmern muss.

Wenn die Teilzeichenfolgenoperationen, die normalerweise für Zeichenfolgen ausgeführt werden, völlig unterschiedlich wären, wäre es sinnvoll, einen dauerhaften Ansatz zu wählen. Wenn Menschen normalerweise Zeichenfolgen mit Millionen Zeichen hatten und Tausende überlappender Teilzeichenfolgen mit Größen im Bereich von Hunderttausend Zeichen extrahierten und diese Teilzeichenfolgen lange Zeit auf dem Haufen lebten, wäre es absolut sinnvoll, eine dauerhafte Teilzeichenfolge zu verwenden Ansatz; es wäre verschwenderisch und dumm, es nicht zu tun. Aber die meisten Branchenprogrammierer machen nichts, was sie auch nur vage mögen. .NET ist keine Plattform, die auf die Bedürfnisse des Humangenomprojekts zugeschnitten ist. DNA-Analyseprogrammierer müssen jeden Tag Probleme mit diesen String-Verwendungsmerkmalen lösen. Die Chancen stehen gut, dass Sie nicht. Die wenigen, die ihre eigenen persistenten Datenstrukturen erstellen, die genau zu ihren Nutzungsszenarien passen .

Zum Beispiel schreibt mein Team Programme, die C # - und VB-Code während der Eingabe im laufenden Betrieb analysieren. Einige dieser Codedateien sind riesig und daher können wir keine O (n) -String-Manipulation durchführen, um Teilzeichenfolgen zu extrahieren oder Zeichen einzufügen oder zu löschen. Wir haben eine Reihe von dauerhaften unveränderlichen Datenstrukturen für die Darstellung von Änderungen in einem Textpuffer erstellt, mit denen wir den Großteil der vorhandenen Zeichenfolgendaten und die vorhandenen lexikalischen und syntaktischen Analysen bei einer typischen Bearbeitung schnell und effizient wiederverwenden können . Dies war ein schwer zu lösendes Problem, und seine Lösung war eng auf die spezifische Domäne der C # - und VB-Codebearbeitung zugeschnitten. Es wäre unrealistisch zu erwarten, dass der integrierte Zeichenfolgentyp dieses Problem für uns löst.

Eric Lippert
quelle
47
Es wäre interessant zu kontrastieren, wie Java es macht (oder zumindest irgendwann in der Vergangenheit): Teilzeichenfolge gibt eine neue Zeichenfolge zurück, zeigt jedoch auf dasselbe Zeichen [] wie die größere Zeichenfolge - das bedeutet, dass das größere Zeichen [] Es kann kein Müll mehr gesammelt werden, bis der Teilstring den Gültigkeitsbereich verlässt. Ich bevorzuge bei weitem die Implementierung von .net.
Michael Stum
13
Ich habe diese Art von Code ziemlich oft gesehen: string contents = File.ReadAllText(filename); foreach (string line in content.Split("\n")) ...oder andere Versionen davon. Ich meine, eine ganze Datei lesen und dann die verschiedenen Teile verarbeiten. Diese Art von Code wäre erheblich schneller und würde weniger Speicher benötigen, wenn eine Zeichenfolge persistent wäre. Sie hätten immer genau eine Kopie der Datei im Speicher, anstatt jede Zeile zu kopieren, und dann die Teile jeder Zeile, während Sie sie verarbeiten. Wie Eric sagte - das ist jedoch nicht der typische Anwendungsfall.
Konfigurator
18
@configurator: In .NET 4 unterteilt die File.ReadLines-Methode eine Textdatei für Sie in Zeilen, ohne dass Sie alles zuerst in den Speicher lesen müssen.
Eric Lippert
8
@Michael: Java Stringist als persistente Datenstruktur implementiert (dies ist nicht in den Standards angegeben, aber alle mir bekannten Implementierungen tun dies).
Joachim Sauer
33
Kurze Antwort: Eine Kopie der Daten wird erstellt , um die Speicherbereinigung der ursprünglichen Zeichenfolge zu ermöglichen .
Qtax
121

Gerade weil Strings unveränderlich sind, .Substringmuss mindestens ein Teil des ursprünglichen Strings kopiert werden. Das Erstellen einer Kopie von n Bytes sollte O (n) Zeit dauern.

Wie würden Sie eine Reihe von Bytes in konstanter Zeit kopieren ?


BEARBEITEN: Mehrdad schlägt vor, die Zeichenfolge überhaupt nicht zu kopieren, sondern einen Verweis auf ein Stück davon beizubehalten.

Betrachten Sie in .Net eine Multi-Megabyte-Zeichenfolge, über die jemand anruft .SubString(n, n+3) (für jedes n in der Mitte der Zeichenfolge).

Jetzt kann die GESAMTE Zeichenfolge nicht durch Garbage Collected erfasst werden, nur weil eine Referenz 4 Zeichen enthält. Das scheint eine lächerliche Platzverschwendung zu sein.

Das Verfolgen von Verweisen auf Teilzeichenfolgen (die sich sogar innerhalb von Teilzeichenfolgen befinden können) und der Versuch, zu optimalen Zeiten zu kopieren, um zu vermeiden, dass der GC besiegt wird (wie oben beschrieben), macht das Konzept zu einem Albtraum. Das Kopieren .SubStringund Verwalten des einfachen unveränderlichen Modells ist viel einfacher und zuverlässiger .


EDIT: Hier ist ein gutes Stück über die Gefahr, Verweise auf Teilzeichenfolgen in größeren Zeichenfolgen zu halten.

abelenky
quelle
5
+1: Genau meine Gedanken. Intern wird wahrscheinlich verwendet, memcpywas immer noch O (n) ist.
Leppie
7
@abelenky: Ich denke, vielleicht indem ich es überhaupt nicht kopiere? Es ist schon da, warum solltest du es kopieren müssen?
user541686
2
@Mehrdad: WENN Sie nach Leistung sind. Gehen Sie in diesem Fall einfach unsicher. Dann können Sie einen char*Teilstring bekommen.
Leppie
9
@Mehrdad - Sie erwarten dort möglicherweise zu viel, es heißt StringBuilder und es ist gut , Strings zu erstellen . Es heißt nicht StringMultiPurposeManipulator
MattDavey
3
@SamuelNeff, @Mehrdad: Zeichenfolgen in .NET werden nicht NULL beendet. Wie in Lipperts Beitrag erläutert , enthalten die ersten 4 Bytes die Länge der Zeichenfolge. Deshalb können sie, wie Skeet betont, \0Zeichen enthalten .
Elideb
33

Java (im Gegensatz zu .NET) bietet zwei Möglichkeiten: Substring()Sie können überlegen, ob Sie nur eine Referenz behalten oder eine ganze Teilzeichenfolge an einen neuen Speicherort kopieren möchten.

Das Simple .substring(...)teilt das intern verwendete charArray mit dem ursprünglichen String-Objekt, das Sie dann bei new String(...)Bedarf in ein neues Array kopieren können (um die Speicherbereinigung des ursprünglichen Arrays nicht zu behindern).

Ich denke, diese Art von Flexibilität ist die beste Option für einen Entwickler.

sll
quelle
50
Sie nennen es "Flexibilität". Ich nenne es "Eine Möglichkeit, versehentlich einen schwer zu diagnostizierenden Fehler (oder ein Leistungsproblem) in die Software einzufügen, weil ich nicht wusste, dass ich anhalten und über alle Stellen nachdenken muss, an denen dieser Code möglicherweise sein kann aufgerufen von (einschließlich derer, die nur in der nächsten Version erfunden würden), nur um 4 Zeichen aus der Mitte einer Zeichenfolge zu erhalten "
Nir
3
Downvote zurückgezogen ... Nach etwas sorgfältigerem Durchsuchen des Codes sieht es so aus, als würde ein Teilstring in Java auf ein gemeinsam genutztes Array verweisen, zumindest in der openjdk-Version. Und wenn Sie eine neue Zeichenfolge sicherstellen möchten, gibt es eine Möglichkeit, dies zu tun.
Don Roby
11
@Nir: Ich nenne es "Status Quo Bias". Für Sie scheint die Java-Methode mit Risiken behaftet zu sein, und die .Net-Methode ist die einzig sinnvolle Wahl. Für Java-Programmierer ist das Gegenteil der Fall.
Michael Borgwardt
7
Ich bevorzuge stark .NET, aber das klingt nach einer Sache, die Java richtig gemacht hat. Es ist nützlich, dass ein Entwickler zugelassen wird den Zugang zu einer wirklich O (1) Substring Methode zu haben (ohne eigenen String - Typen Walzen, die mit jeder anderen Bibliothek Interoperabilität behindern würde und nicht so effizient sein wie eine Lösung in integrierten ). Die Lösung von Java ist jedoch wahrscheinlich ineffizient (mindestens zwei Heap-Objekte sind erforderlich, eines für die ursprüngliche Zeichenfolge und eines für den Teilstring). Sprachen, die Slices unterstützen, ersetzen das zweite Objekt effektiv durch ein Paar Zeiger auf dem Stapel.
Qwertie
10
Seit JDK 7u6 ist es nicht mehr wahr - jetzt kopiert Java immer String-Inhalte für jeden .substring(...).
Xaerxess
12

Java verwendet, um auf größere Zeichenfolgen zu verweisen, aber:

Java hat sein Verhalten ebenfalls auf Kopieren geändert , um Speicherverluste zu vermeiden.

Ich habe das Gefühl, dass es verbessert werden kann: Warum nicht einfach unter bestimmten Bedingungen kopieren?

Wenn der Teilstring mindestens halb so groß wie der übergeordnete Teil ist, kann auf den übergeordneten Teil verwiesen werden. Ansonsten kann man einfach eine Kopie machen. Dadurch wird vermieden, dass viel Speicher verloren geht, und es wird dennoch ein erheblicher Vorteil erzielt.

user541686
quelle
Durch ständiges Kopieren können Sie das interne Array entfernen. Halbiert die Anzahl der Heap-Zuweisungen und spart Speicher, wenn es häufig zu kurzen Zeichenfolgen kommt. Dies bedeutet auch, dass Sie nicht für jeden Zeichenzugriff durch eine zusätzliche Indirektion springen müssen.
CodesInChaos
2
Ich denke, das Wichtigste dabei ist, dass Java tatsächlich von der Verwendung derselben Basis char[](mit unterschiedlichen Zeigern auf Anfang und Ende) zur Erstellung einer neuen Basis gewechselt ist String. Dies zeigt deutlich, dass die Kosten-Nutzen-Analyse eine Präferenz für die Schaffung eines neuen zeigen muss String.
Phylogenesis
2

Keine der Antworten hier befasste sich mit "dem Klammerproblem", dh Zeichenfolgen in .NET werden als eine Kombination aus einer BStr (die im Speicher gespeicherte Länge "vor" dem Zeiger) und einer CStr (die Zeichenfolge endet mit a) dargestellt '\ 0').

Die Zeichenfolge "Hallo" wird somit als dargestellt

0B 00 00 00 48 00 65 00 6C 00 6F 00 20 00 74 00 68 00 65 00 72 00 65 00 00 00

(Wenn der Zeiger einer char*in einer fixedAnweisung zugewiesen wird, zeigt er auf 0x48.)

Diese Struktur ermöglicht eine schnelle Suche nach der Länge einer Zeichenfolge (in vielen Kontexten nützlich) und ermöglicht die Übergabe des Zeigers in einem P / Invoke an Win32- (oder andere) APIs, die eine nullterminierte Zeichenfolge erwarten.

Wenn Sie die Substring(0, 5)Regel "Oh, aber ich habe versprochen, dass nach dem letzten Zeichen ein Nullzeichen steht" ausführen, müssen Sie eine Kopie erstellen. Selbst wenn Sie den Teilstring am Ende hätten, gäbe es keinen Platz, um die Länge zu setzen, ohne die anderen Variablen zu beschädigen.


Manchmal möchten Sie jedoch wirklich über "die Mitte der Zeichenfolge" sprechen, und das P / Invoke-Verhalten ist Ihnen nicht unbedingt wichtig. Die kürzlich hinzugefügte ReadOnlySpan<T>Struktur kann verwendet werden, um einen Teilstring ohne Kopie zu erhalten:

string s = "Hello there";
ReadOnlySpan<char> hello = s.AsSpan(0, 5);
ReadOnlySpan<char> ell = hello.Slice(1, 3);

Der ReadOnlySpan<char>"Teilstring" speichert die Länge unabhängig und garantiert nicht, dass nach dem Ende des Werts ein '\ 0' steht. Es kann auf viele Arten "wie eine Zeichenfolge" verwendet werden, aber es ist keine "Zeichenfolge", da es weder BStr- noch CStr-Eigenschaften aufweist (geschweige denn beide). Wenn Sie niemals (direkt) P / Invoke verwenden, gibt es keinen großen Unterschied (es sei denn, die API, die Sie aufrufen möchten, weist keine ReadOnlySpan<char>Überlastung auf).

ReadOnlySpan<char>kann nicht als Feld eines Referenztyps verwendet werden, daher gibt es auch ReadOnlyMemory<char>( s.AsMemory(0, 5)), eine indirekte Methode, um a zu haben ReadOnlySpan<char>, sodass dieselben Unterschiede stringbestehen.

In einigen Antworten / Kommentaren zu früheren Antworten wurde davon gesprochen, dass es verschwenderisch ist, wenn der Garbage Collector eine Zeichenfolge mit einer Million Zeichen behalten muss, während Sie weiterhin über 5 Zeichen sprechen. Das ist genau das Verhalten, das Sie mit dem ReadOnlySpan<char>Ansatz erhalten können. Wenn Sie nur kurze Berechnungen durchführen, ist der ReadOnlySpan-Ansatz wahrscheinlich besser. Wenn Sie es für eine Weile beibehalten müssen und nur einen kleinen Prozentsatz der ursprünglichen Zeichenfolge behalten möchten, ist es wahrscheinlich besser, einen geeigneten Teilstring (um die überschüssigen Daten zu entfernen) durchzuführen. Irgendwo in der Mitte befindet sich ein Übergangspunkt, der jedoch von Ihrer spezifischen Verwendung abhängt.

Bartonjs
quelle