Effiziente String-Implementierung in Haskell

Question

Ich lerne gerade selbst, Haskell, und ich frage mich, was die besten Praktiken sind, wenn man mit Strings in Haskell arbeitet.

Die Standard-String-Implementierung in Haskell ist eine Liste von Char. Dies ist ineffizient für Datei-Input-Output, nach Real World Haskell, da jedes Zeichen separat zugeordnet ist (ich nehme an, dass dies bedeutet, dass ein String ist im Grunde eine verkettete Liste in Haskell, aber ich bin mir nicht sicher.)

Aber wenn die Standard-String-Implementierung ist ineffizient für Datei-E/A, ist es auch ineffizient für die Arbeit mit Strings im Speicher? Warum oder warum nicht? C verwendet ein Array von Zeichen, um einen String darzustellen, und ich nahm an, dass dies die Standardmethode in den meisten Sprachen wäre.

Wie ich es sehe, wird die Listenimplementierung von String mehr Speicher belegen, da jedes Zeichen Overhead benötigt und auch mehr Zeit zum Iterieren benötigt, da ein Zeiger-Dereferenzieren erforderlich ist, um zum nächsten Zeichen zu gelangen. Aber ich habe bisher gerne mit Haskell gespielt, also möchte ich glauben, dass die Standardimplementierung effizient ist.

Answer 1

Best Practices für das performante Arbeiten mit Strings in Haskell sind im Wesentlichen: Verwenden Sie Data.ByteString/Data.ByteString.Lazy.

http://hackage.haskell.org/packages/archive/bytestring/latest/doc/html/

---

Was die Effizienz der Implementierung Standard-String in Haskell geht, ist es nicht. Jede Char stellt einen Unicode-Codepoint dar, was bedeutet, dass sie mindestens 21 Bit pro Char benötigt.

Da ein String nur [Char], das ist eine verbundene Liste von Char, bedeutet dies String s schlechte Referenzlokalität und wiederum bedeutet, dass String s im Speicher ziemlich groß sind, auf ein Minimum es N * (21bits + Mbits) ist, wobei N die ist Länge der Zeichenfolge und M ist die Größe eines Zeigers (32, 64, was hast du) und im Gegensatz zu vielen anderen Orten, wo Haskell Listen verwendet, wo andere Sprachen andere Strukturen verwenden können (ich denke hier speziell an Kontrollfluss), String Es ist viel weniger wahrscheinlich, dass s vom Compiler für Schleifen usw. optimiert werden können.

Und während ein Char einem Codepunkt entspricht, gibt der Haskell 98-Bericht nichts über die Codierung an, die beim Ausführen von Datei-IO verwendet wird, nicht einmal eine Vorgabe, viel weniger eine Möglichkeit, sie zu ändern. In der Praxis stellt GHC eine Erweiterung bereit, um z.B. binäre IO, aber Sie gehen sowieso an dieser Stelle aus der Reservierung.

Auch bei Vorgängen vor der Saite ist es unwahrscheinlich, dass ein String einen ByteString in der Praxis schlägt.

Answer 2

Die Antwort ist ein bisschen komplexer als nur "verwenden faulen Bytestrings".

Byte-Strings speichern nur 8 Bits pro Wert, während String echte Unicode-Zeichen enthält. Wenn Sie also mit Unicode arbeiten möchten, müssen Sie immer zu und von UTF-8 oder UTF-16 konvertieren, was teurer ist, als nur Zeichenfolgen zu verwenden. Machen Sie nicht den Fehler, anzunehmen, dass Ihr Programm nur ASCII benötigt. Es sei denn, es ist nur ein Wegwerfcode, dann muss jemand eines Tages ein Euro-Symbol (U + 20AC) oder Zeichen mit Akzent eingeben, und Ihre nette schnelle Bystring-Implementierung wird unwiederbringlich zerstört.

Byte-Strings machen einige Dinge, wie vor dem Start einer Zeichenfolge, teurer.

Das heißt, wenn Sie Leistung benötigen und Sie Ihre Daten rein in Bytestrings darstellen können, dann tun Sie dies.

Answer 3

Neben String/ByteString gibt es jetzt die Text-Bibliothek, die das Beste aus beiden Welten kombiniert - sie arbeitet mit Unicode, während sie intern ByteString-basiert ist, so dass Sie schnelle, korrekte Strings erhalten.

Answer 4

Die grundlegende Antwort gegeben, verwenden Sie ByteString, ist korrekt. Das heißt, alle drei Antworten vor mir haben Ungenauigkeiten.

In Bezug auf UTF-8: ob dies ein Problem sein wird oder nicht hängt ganz davon ab, welche Art von Verarbeitung Sie mit Ihren Strings tun. Wenn Sie sie einfach als einzelne Datenblöcke behandeln (z. B. Operationen wie Verkettung, jedoch nicht aufteilen) oder bestimmte beschränkte bytebasierte Operationen ausführen (z. B. die Länge der Zeichenfolge in Byte anstatt der Länge in Charaktere), haben Sie keine Probleme. Wenn Sie I18N verwenden, gibt es genug andere Probleme, die einfach String statt ByteString anfangen, nur ein paar der Probleme zu beheben, die auftreten werden.

Das Voranstellen von einzelnen Bytes an die Vorderseite eines ByteStrings ist wahrscheinlich teurer als das Gleiche für einen String. Wenn Sie jedoch eine Menge davon tun, ist es wahrscheinlich möglich, Wege zu finden, mit Ihrem speziellen Problem umzugehen, die billiger sind.

Aber das Endergebnis wäre, für das Plakat der ursprünglichen Frage: Ja, Strings sind in Haskell ineffizient, obwohl ziemlich praktisch. Wenn Sie sich Sorgen über die Effizienz machen, verwenden Sie ByteStrings, und sehen Sie sie als Arrays von Char8 oder Word8, je nach Ihrem Zweck (ASCII/ISO-8859-1 vs Unicode oder nur willkürliche Binärdaten). Im Allgemeinen verwenden Sie Lazy ByteStrings (wobei das Voranstellen an den Anfang eines Strings tatsächlich eine sehr schnelle Operation ist), es sei denn, Sie wissen, warum Sie nicht-faule wollen (was normalerweise in einer Wertschätzung der Leistungsaspekte der faulen Auswertung eingeschlossen ist).

Für was es wert ist, ich baue ein automatisiertes Handelssystem komplett in Haskell, und eines der Dinge, die wir tun müssen, ist sehr schnell analysieren einen Markt Daten-Feed erhalten wir über eine Netzwerkverbindung. Ich kann lesen und analysieren 300 Nachrichten pro Sekunde mit einer vernachlässigbaren Menge an CPU; Was den Umgang mit diesen Daten betrifft, so ist GHC-kompiliertes Haskell nahe genug an C, dass es nicht annähernd in meine Liste der bemerkenswerten Probleme eingeht.