Ich bin verwirrt über die Implementierung der Funktion 'nub' (select unique values) in der Haskell-Standardbibliothek Data.List . Die GHC-Implementierung ist
%Vor%Soweit ich das beurteilen kann, hat dies eine Zeitkomplexität von 0 (n ^ 2) im ungünstigsten Fall, da es für eine Liste eindeutiger Werte alle einmal vergleichen muss, um zu sehen, dass sie tatsächlich einzigartig sind / p>
Wenn man eine Hash-Tabelle verwendet, kann die Komplexität auf O (n) für den Aufbau der Tabelle + O (1) reduziert werden, um jeden Wert mit vorherigen Werten in der Hash-Tabelle zu vergleichen. Zugegeben, dies würde keine geordnete Liste ergeben, aber das wäre auch in O (n log n) möglich, wenn GHC eine eigene geordnete Data.Map verwendet, falls dies notwendig ist.
Warum sollten Sie eine solche ineffiziente Implementierung für eine wichtige Bibliotheksfunktion wählen? Ich verstehe, dass Effizienz in Haskell kein Hauptanliegen ist, aber zumindest die Standardbibliothek könnte sich bemühen, die (asymptotisch) beste Datenstruktur für den Job zu wählen.
Effizienz ist in Haskell ein ziemliches Problem, schließlich ist die Sprache vergleichbar mit Java und schlägt sich in Bezug auf den Speicherverbrauch, aber natürlich ist es nicht C.
Die Antwort auf Ihre Frage ist ziemlich einfach: Das nub des Präludiums erfordert nur eine Eq Einschränkung, während jede Implementierung, die auf Map oder Set basiert, ebenfalls entweder Ord oder Hashable benötigt.
Sie sind absolut richtig - nub ist ein O (n ^ 2) -Algorithmus. Es gibt jedoch immer noch Gründe, warum Sie es verwenden möchten, anstatt eine Hashmap zu verwenden:
nub benötigt nur die Einschränkung Eq ; Zum Vergleich benötigt Data.Map eine Ord Einschränkung für Schlüssel und Data.HashMap erfordert einen Schlüsseltyp mit den Klassen Hashable und Ord type Bearbeiten: Leichte Korrektur am dritten Punkt - Sie müssen nicht die gesamte Liste bearbeiten, um Ergebnisse zu erhalten; Sie müssen immer noch jedes Element der Eingabeliste prüfen (so funktioniert nub nicht auf unendlichen Listen), aber Sie werden die Ergebnisse zurückgeben, sobald Sie ein eindeutiges Element finden.
Meiner Erfahrung nach ignoriert "Anfänger" Haskell (einschließlich Prelude und die schlechten Pakete) die Leistung in vielen Fällen zugunsten der Einfachheit.
Die Haskell-Leistung ist ein komplexes Problem, das Sie lösen müssen, wenn Sie nicht genug Erfahrung haben, um Platform oder Hackage nach Alternativen zum einfachen nub zu durchsuchen (und insbesondere, wenn Ihre Eingabe in einer Liste enthalten ist) über alternative Strukturen nachgedacht), dann ist Data.List.nub wahrscheinlich nicht dein einziges großes Leistungsproblem und du schreibst wahrscheinlich Code für ein Spielzeugprojekt, bei dem die Leistung keine Rolle spielt.
Sie müssen nur darauf vertrauen, dass Sie, wenn Sie ein großes (in Code oder Daten) Projekt erstellen, erfahrener sind und wissen, wie Sie Ihre Programme effizienter einrichten können.
Mit anderen Worten, machen Sie sich darüber keine Sorgen und nehmen Sie an, dass alles in Haskell 98, das von Prelude oder Basis stammt, wahrscheinlich nicht der effizienteste Weg ist, um ein Problem zu lösen.
Tags und Links algorithm haskell performance