Gibt es ein Szenario, in dem die Seildatenstruktur effizienter ist als ein String Builder

Question

Im Zusammenhang mit diese Frage, basierend auf einem Kommentar des Benutzers Eric Lippert.

Gibt es ein Szenario, in dem die Seil Die Datenstruktur ist effizienter als ein String -Builder? Es ist die Meinung einiger Leute, dass Seildatenstrukturen in typischen Fällen fast nie besser sind als die nativen String- oder String Builder -Operationen.

Answer 1

Die Dokumentation für die SGI C ++ Implementierung geht auf einige Details zu den großen O -Verhaltensweisen versehen die ständigen Faktoren, die aufschlussreich sind.

Ihre Dokumentation geht davon aus Sehr lange Saiten sind beteiligt, die Beispiele als Referenzgespräch 10 MB Saiten. Es werden nur sehr wenige Programme geschrieben, die sich mit solchen Dingen befassen, und für viele Klassen von Problemen mit solchen Anforderungen, die sie überarbeiten, um sie zu bearbeiten streambasiert Anstatt dass die vollständige Zeichenfolge nach Möglichkeit verfügbar sein muss, führt er zu deutlich überlegenen Ergebnissen. Als solche Seile sind Seile für die Nicht -Streaming -Manipulation von Multi -Megabyte -Zeichensequenzen bestimmt, wenn Sie das Seil angemessen als Abschnitte (sich selbst Seile) und nicht nur als Folge von Zeichen behandeln können.

Bedeutende Profis:

• Verkettung/Insertion werden nahezu konstante Zeitoperationen
• Bestimmte Operationen können die vorherigen Seilabschnitte wiederverwenden, um das Teilen im Speicher zu ermöglichen.
  • Beachten Sie, dass .NET -Saiten im Gegensatz zu Java -Zeichenfolgen den Charakterpuffer nicht auf Substrings teilen - eine Auswahl bei Vor- und Nachteilen in Bezug auf Speicherpflichtzdruck. Seile neigen dazu, diese Art von Problem zu vermeiden.
• Seile ermöglichen die aufgeschobene Belastung von Unterstrings bis erforderlich
  • Beachten Sie, dass dies schwierig ist, richtig zu werden, sehr einfach zu machen, da es übermäßige Zugriffsbereitschaft hat und Code konsumiert werden muss, um es als Seil zu behandeln, nicht als eine Abfolge von Zeichen.

Signifikante Nachteile:

• Zufälliger Lesezugriff wird zu O (log n)
• Die konstanten Faktoren für den sequentiellen Lesezugriff scheinen zwischen 5 und 10 zu liegen
• effiziente Verwendung der API erfordert Behandlung als Seil, nicht nur in einem Seil als Hintergrundimplementierung auf der "normalen" String -API fallen.

Dies führt zu einigen „offensichtlichen“ Verwendungen (die erste von SGI ausdrücklich erwähnt).

• Bearbeiten Sie Puffer in großen Dateien, die ein einfaches Rückgut/Wiederherstellen ermöglichen
  • Beachten Sie, dass Sie irgendwann möglicherweise die Änderungen an der Festplatte schreiben müssen, das das Streaming durch die gesamte Zeichenfolge einbezieht. Dies ist daher nur nützlich, wenn die meisten Änderungen in erster Linie im Gedächtnis liegen, anstatt häufige Persistenz zu benötigen (z. B. durch eine Autosave -Funktion)
• Manipulation von DNA -Segmenten, bei denen eine signifikante Manipulation auftritt
• Multi -Thread -Algorithmen, die lokale Unterabschnitte von String mutieren. Theoretisch können solche Fälle zu getrennten Fäden und Kernen abgelehnt werden, ohne lokale Kopien der Unterabschnitte aufzunehmen und dann neu zu rekombinieren, um beträchtliches Speicher zu sparen und am Ende einen kostspieligen seriellen Kombinationsoperation zu vermeiden.

Es gibt Fälle, in denen das domänenspezifische Verhalten in der Zeichenfolge mit relativ einfachen Augmentationen zur Seilimplementierung gekoppelt werden kann, um:

• Lesen Sie nur Zeichenfolgen mit einer erheblichen Anzahl gemeinsamer Substrings für einfache Einlagen für signifikante Speichereinsparungen.
• Saiten mit spärlichen Strukturen oder eine signifikante lokale Wiederholung sind für die Länge -Codierung zugänglich und ermöglichen dennoch eine angemessene Ebene des Zufallszugriffs.
• Wo die Sub -String -Grenzen selbst "Knoten" sind, bei denen Informationen gespeichert werden können, obwohl solche Strukturen durchaus besser gemacht werden als Radix Trie Wenn sie selten modifiziert sind, aber oft gelesen werden.

Wie Sie aus den aufgeführten Beispielen sehen können, fallen alle gut in die Kategorie "Nische". Darüber hinaus können mehrere überlegene Alternativen haben, wenn Sie bereit sind, den Algorithmus stattdessen als Stream -Verarbeitungsvorgang umzuschreiben.

Answer 2

Die kurze Antwort auf diese Frage lautet Ja, und das erfordert wenig Erklärung. Natürlich gibt es Situationen, in denen die Seildatenstruktur effizienter ist als ein String -Builder. Sie arbeiten anders, daher sind sie für verschiedene Zwecke besser geeignet.

(Aus einer C# Perspektive)

Die Seildatenstruktur als binärer Baum ist in bestimmten Situationen besser. Wenn Sie sich mit extrem großen Stringwerten befassen (denken Sie an 100 MB XML aus SQL), kann die Seildatenstruktur den gesamten Vorgang vom großen Objekthaufen fernhalten, wobei das String -Objekt es trifft, wenn es 85000 Bytes übergeht.

Wenn Sie sich mit 5-1000 Zeichen ansehen, verbessert dies die Leistung wahrscheinlich nicht genug, um es wert zu sein. Dies ist ein weiterer Fall einer Datenstruktur, die für 5% der Menschen mit extremer Situation ausgelegt ist.

Answer 3

Das 10. ICFP -Programmierwettbewerb verlassen, Grundsätzlich bei Personen, die die Seildatenstruktur zur effizienten Lösung verwenden. Das war der große Trick, um eine VM zu bekommen, die in angemessener Zeit verlief.

Seil ist ausgezeichnet, wenn es viele Präfixen gibt (anscheinend wird das Wort "Vorbereitung" von IT -Leuten zusammengesetzt und ist kein richtiges Wort!) Und möglicherweise besser für Einfügungen. StringBuilders verwenden den kontinuierlichen Speicher, also arbeiten Sie nur effizient zum Anhängen.

Daher eignet sich StringBuilder hervorragend zum Erstellen von Strings, indem Fragmente angehängt sind - eine sehr normale Anwendungsfall. Da Entwickler dies viel tun müssen, sind Stringbuilders eine sehr Mainstream -Technologie.

Seile eignen sich hervorragend zum Bearbeiten von Puffern, z. B. der Datenstruktur dahinter, beispielsweise in einem Textbereich der Enterprise-Stärke. Also (eine Entspannung von Seilen, z. B. eine verknüpfte Liste von Linien anstelle eines binären Baums) ist in der UI -Kontrollwelt sehr häufig, aber das ist nicht oft den Entwicklern und Benutzern dieser Steuerelemente ausgesetzt.

Sie benötigen wirklich große Datenmengen und Abwanderungen, um die Seilauszahlung zu erzielen. Die Prozessoren sind sehr gut in Stream-Operationen. Wenn Sie den RAM haben, dann funktioniert einfach für das Präfixing für normale Anwendungsfälle akzeptabel. Dieser an der Spitze erwähnte Wettbewerb war das einzige Mal, dass ich ihn brauchte.

Answer 4

Die meisten fortschrittlichen Texteditoren stellen den Textkörper als "Art von Seil" dar (in der Implementierung sind Blätter normalerweise nicht einzelne Zeichen, sondern Text ausgeführt), hauptsächlich, um die häufigen Einfügungen und Löschungen in großen Texten zu verbessern.

Im Allgemeinen wird StringBuilder für das Anhängen optimiert und versucht, die zu minimieren Gesamtzahl der Reallokationen ohne viel zu viel zu tun. Die typische Garantie ist (log2 N -Zuordnungen und weniger als 2,5x der Speicher). Normalerweise wird die Saite einmal erstellt und kann dann eine ganze Weile verwendet werden, ohne geändert zu werden.

Das Seil ist für häufige Einsätze und Entfernungen optimiert und versucht, zu minimieren Datenmenge kopiert (durch eine größere Anzahl von Zuweisungen). In einer linearen Pufferimplementierung wird jeder Einsatz und Löschen zu O (n), und Sie müssen normalerweise einzelne Zeicheneinsätze darstellen.

Answer 5

JavaScript -VMs verwenden häufig Seile für Zeichenfolgen.

Maxime Chevalier-Boisvert, Entwickler des Higgs JavaScript VM, sagt:

In JavaScript können Sie Arrays von Strings und schließlich Array.Prototype.Join verwenden, um die String -Verkettung einigermaßen schnell zu machen, O (n), aber die "natürlichen" Weg -Programmierer neigen dazu, Strings zu erstellen Erstellen Sie sie schrittweise. JS -Saiten sind unveränderlich. Wenn dies also intern nicht optimiert wird, ist inkrementelles Anhängen O (N2). Ich denke, es ist wahrscheinlich, dass Seile in JS -Motoren speziell wegen der Sunspider -Benchmarks implementiert wurden, die eine Zeichenfolge anhängen. JS Engine -Implementierer verwendeten Seile, um einen Vorsprung gegenüber anderen zu gewinnen, indem sie etwas zuvor langsamer machten. Wenn es nicht um diese Benchmarks ging, denke ich, dass weint, dass die Community über String, die schlecht abschneiden, mit "Array.Prototype.Join, Dummy!"

Ebenfalls.