Ich habe versucht, Problem 1330 von acm zu lösen .timus.ru in Haskell. Grundsätzlich läuft es darauf hinaus: 1) lese von stdin ein Array A der Länge N (N & lt; 10 ^ 4) und M Paare von ganzen Zahlen (M & lt; 10 ^ 5) ab; 2) für jedes (von, bis) Paar, drucke die Summe von Unterfeld A [von..to] nach stdout.
Da SO mich nicht mehr als zwei URLs als Teil dieser Frage veröffentlichen lässt, werde ich auf Dateien in meinem Github-Repository unten.
Ich habe zwei Lösungen gefunden, die den größten Teil des Codes teilen. Die erste (1330_slow.hs) verwendet Prelude-Funktionen (getLine / read / words) und ist etwas langsam:
%Vor%Die andere Lösung (1330.hs) verteilt diese Funktionen, ersetzt sie durch ihre Data.ByteString.Char8-Entsprechungen (B.getLine / B.readInt / B.words) und verhält sich gut:
%Vor%Das Zeitlimit für dieses Problem liegt bei 500 ms, also sind 270 ms schnell genug (und vergleichbar mit meinen Lösungen in anderen Sprachen wie C ++ und Go), 2180 ms schneiden nicht ab. Warum ist meine erste Lösung so lächerlich langsam? Selbst wenn ich die Profiling-Tipps von Real World Haskell befolge, kann ich immer noch keinen Sinn daraus ziehen (alles was ich herausfinden konnte war, dass die meiste Zeit in der readIntPair-Funktion verbracht wurde, was nicht viel half).
Wenn Sie eigene Tests durchführen möchten, habe ich einen Python-Input-Generator (gen_test.py) und eine vorgenerierte Eingabedatei (input.txt) für den Fall, dass Sie Python nicht installiert haben. Und ein Unterschied (slow_fast_diff.txt) zwischen den beiden Lösungen.
Wie andere bereits gesagt haben, ist ByteString nicht schnell, sondern String ist sehr, sehr langsam.
A ByteString speichert ein Byte pro Zeichen, zuzüglich einiger Buchhaltungskosten. A String speichert etwa 12 Bytes pro Zeichen (abhängig davon, ob Sie im 32-Bit- oder 64-Bit-Modus arbeiten). Es speichert auch jedes Zeichen in einem nicht zusammenhängenden Speicher, so dass jedem Zeichen individuell zugewiesener Speicherplatz zugewiesen werden muss, der vom Speicherbereiniger einzeln gescannt und schließlich wieder einzeln freigegeben werden muss. Dies bedeutet eine schlechte Cache-Lokalität, viel Zuteilungszeit und viel Zeit für die Speicherbereinigung. Kurz gesagt, es ist höllisch ineffizient.
Grundsätzlich macht ByteString was C tut, was Java macht, was C ++ macht, was C # macht, was VB tut und was jede andere Programmiersprache mit Strings macht. Keine andere Sprache, die mir bekannt ist, hat einen Standard-String-Typ, der so ineffizient ist wie Haskell. (Auch Frege, ein Haskell-Dialekt, verwendet einen effizienteren Stringtyp.)
Ich sollte darauf hinweisen, dass ByteString.Char8 nur Latin-1-Zeichen verarbeitet. Es kommt überhaupt nicht mit zufälligen Unicode-Zeichen zurecht. Für eine Programmieraufgabe wie diese ist das wahrscheinlich kein Problem, aber für ein "echtes System" könnte es gut sein. ByteString befasst sich nicht wirklich mit exotischen Zeichen oder anderen Zeichenkodierungen oder irgendetwas; es nimmt nur an, dass Sie einfaches ASCII wollen. Das war früher eine sichere Annahme; heute, nicht so sehr.
Bytestring IO beinhaltet das Lesen von Daten in gepackte Puffer, genau wie Sie es in C. String s gewohnt sind, auf der anderen Seite sind verkettete Listen von Zeichen, die IO nicht nur komplizieren, sondern für die Verarbeitung bedeuten können höhere Nutzung von Speicher, Verarbeitung, Cache, möglicherweise Verzweigung und GC.
Eine andere Möglichkeit, um es auszudrücken: ByteString ist aus den gleichen Gründen schnell unsigned char *
ist schnell in C .
Tags und Links haskell bytestring