Ich lerne Haskell und lese einige Artikel über Leistungsunterschiede bei Haskell-Listen und (fügen Sie Ihre Sprache ein) Arrays.

Als Lernender benutze ich natürlich nur Listen, ohne über Leistungsunterschiede nachzudenken. Ich habe kürzlich mit der Untersuchung begonnen und zahlreiche Datenstrukturbibliotheken in Haskell gefunden.

Kann jemand bitte den Unterschied zwischen Listen, Arrays, Vektoren, Sequenzen erklären, ohne sich eingehend mit der Theorie der Datenstrukturen in der Informatik zu befassen?

Gibt es auch einige gängige Muster, bei denen Sie eine Datenstruktur anstelle einer anderen verwenden würden?

Gibt es andere Formen von Datenstrukturen, die mir fehlen und die nützlich sein könnten?

Listet Rock auf

Die mit Abstand freundlichste Datenstruktur für sequentielle Daten in Haskell ist die Liste

 data [a] = a:[a] | []

Listen geben Ihnen ϴ (1) Nachteile und Mustervergleich. Die Standardbibliothek, und dass das Vorspiel Materie, ist voll von nützlichen Liste Funktionen , die sollte Streu Code ( foldr, map, filter). Listen sind persistent , auch bekannt als rein funktional, was sehr schön ist. Haskell-Listen sind nicht wirklich "Listen", weil sie koinduktiv sind (andere Sprachen nennen diese Streams)

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

wunderbar arbeiten. Unendliche Datenstrukturen rocken.

Listen in Haskell bieten eine Schnittstelle ähnlich wie Iteratoren in imperativen Sprachen (wegen Faulheit). Es macht also Sinn, dass sie weit verbreitet sind.

Andererseits

Das erste Problem bei Listen ist, dass das Indizieren in Listen (!!)ϴ (k) Zeit benötigt, was ärgerlich ist. Anhänge können auch langsam sein ++, aber das faule Bewertungsmodell von Haskell bedeutet, dass diese als vollständig amortisiert behandelt werden können, wenn sie überhaupt auftreten.

Das zweite Problem bei Listen besteht darin, dass sie eine schlechte Datenlokalität aufweisen. Bei realen Prozessoren treten hohe Konstanten auf, wenn Objekte im Speicher nicht nebeneinander angeordnet sind. In C ++ std::vectorgibt es also einen schnelleren "Snoc" (Objekte am Ende setzen) als jede mir bekannte reine verknüpfte Listendatenstruktur, obwohl dies keine persistente Datenstruktur ist, die so weniger freundlich ist als Haskells Listen.

Das dritte Problem bei Listen ist, dass sie eine schlechte Raumeffizienz aufweisen. Bündel zusätzlicher Zeiger erhöhen Ihren Speicher (um einen konstanten Faktor).

Sequenzen sind funktionsfähig

Data.Sequencebasiert intern auf Fingerbäumen (ich weiß, das wollen Sie nicht wissen), was bedeutet, dass sie einige schöne Eigenschaften haben

1. Rein funktional. Data.Sequenceist eine vollständig persistente Datenstruktur.
2. Verdammt schneller Zugang zum Anfang und Ende des Baumes. ϴ (1) (amortisiert), um das erste oder letzte Element zu erhalten oder Bäume anzuhängen. An der Sache sind Listen am schnellsten, Data.Sequenceist höchstens eine Konstante langsamer.
3. ϴ (log n) Zugriff auf die Mitte der Sequenz. Dies umfasst das Einfügen von Werten, um neue Sequenzen zu erstellen
4. Hochwertige API

Auf der anderen Seite Data.Sequencewird nicht viel für das Problem der Datenlokalität getan und funktioniert nur für endliche Sammlungen (es ist weniger faul als Listen).

Arrays sind nichts für schwache Nerven

Arrays sind eine der wichtigsten Datenstrukturen in CS, passen aber nicht sehr gut in die faule reine Funktionswelt. Arrays bieten ϴ (1) Zugriff auf die Mitte der Sammlung und außergewöhnlich gute Datenlokalität / konstante Faktoren. Aber da sie nicht sehr gut in Haskell passen, sind sie ein Schmerz zu benutzen. In der aktuellen Standardbibliothek gibt es tatsächlich eine Vielzahl verschiedener Array-Typen. Dazu gehören vollständig persistente Arrays, veränderbare Arrays für die E / A-Monade, veränderbare Arrays für die ST-Monade und nicht verpackte Versionen der oben genannten. Weitere Informationen finden Sie im Haskell-Wiki

Vektor ist ein "besseres" Array

Das Data.VectorPaket bietet alle Array-Vorteile in einer übergeordneten und saubereren API. Sofern Sie nicht wirklich wissen, was Sie tun, sollten Sie diese verwenden, wenn Sie eine Array-ähnliche Leistung benötigen. Natürlich gelten immer noch einige Einschränkungen - veränderbare Array-ähnliche Datenstrukturen spielen in reinen faulen Sprachen einfach nicht gut. Trotzdem möchten Sie manchmal diese O (1) -Leistung und Data.Vectorgeben sie Ihnen in einem verwendbaren Paket.

Sie haben andere Möglichkeiten

Wenn Sie nur Listen möchten, die am Ende effizient eingefügt werden können, können Sie eine Differenzliste verwenden . Das beste Beispiel für Listen, die die Leistung [Char]beeinträchtigen , stammt in der Regel, als die der Vorspiel als Alias ​​gilt String. CharListen sind praktisch, laufen jedoch in der Regel 20-mal langsamer als C-Zeichenfolgen. Sie können sie also gerne Data.Textoder sehr schnell verwenden Data.ByteString. Ich bin mir sicher, dass es andere sequenzorientierte Bibliotheken gibt, an die ich momentan nicht denke.

Fazit

90 +% der Zeit, in der ich eine sequentielle Sammlung in Haskell-Listen benötige, sind die richtige Datenstruktur. Listen sind wie Iteratoren. Funktionen, die Listen verwenden, können mit den mitgelieferten Funktionen problemlos mit jeder dieser anderen Datenstrukturen verwendet werden toList. In einer besseren Welt wäre das Vorspiel vollständig parametrisch, welchen Containertyp es verwendet, aber derzeit wird []die Standardbibliothek verschmutzt. Es ist also definitiv in Ordnung, Listen (fast) überall zu verwenden.
Sie können vollständig parametrische Versionen der meisten Listenfunktionen erhalten (und sind gut geeignet, sie zu verwenden).

Prelude.map                --->  Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc    --->  Data.Foldable.foldr/foldl/etc
Prelude.sequence           --->  Data.Traversable.sequence
etc

Definiert in der Tat Data.Traversableeine API, die mehr oder weniger universell für alle "Listen wie" ist.

Obwohl Sie gut sein und nur vollständig parametrischen Code schreiben können, sind die meisten von uns dies nicht und verwenden die Liste überall. Wenn Sie lernen, empfehle ich Ihnen dringend, dies auch zu tun.

EDIT: Aufgrund von Kommentaren wurde mir klar, dass ich nie erklärt habe, wann ich Data.Vectorvs verwenden soll Data.Sequence. Arrays und Vektoren bieten extrem schnelle Indizierungs- und Slicing-Operationen, sind jedoch grundsätzlich vorübergehende (zwingende) Datenstrukturen. Reine funktionale Datenstrukturen mögen Data.Sequenceund []lassen neue Werte aus alten Werten effizient erzeugen , als hätten Sie die alten Werte geändert.

  newList oldList = 7 : drop 5 oldList

ändert die alte Liste nicht und muss sie nicht kopieren. Selbst wenn oldListes unglaublich lang ist, wird diese "Modifikation" sehr schnell sein. Ähnlich

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

wird newValueanstelle seines 3000-Elements eine neue Sequenz mit einem for erzeugen . Auch hier wird die alte Sequenz nicht zerstört, sondern nur eine neue erstellt. Dies geschieht jedoch sehr effizient, indem O (log (min (k, kn)) verwendet wird, wobei n die Länge der Sequenz und k der von Ihnen geänderte Index ist.

Sie können dies nicht einfach mit Vectorsund tun Arrays. Sie können geändert werden, aber das ist eine wirklich zwingende Änderung, und kann daher nicht im regulären Haskell-Code durchgeführt werden. Das bedeutet, dass Operationen im VectorPaket, die Änderungen vornehmen snocund consden gesamten Vektor kopieren müssen, also O(n)Zeit brauchen . Die einzige Ausnahme ist, dass Sie die veränderbare Version ( Vector.Mutable) innerhalb der STMonade (oder IO) verwenden und alle Ihre Änderungen so vornehmen können, wie Sie es in einer imperativen Sprache tun würden. Wenn Sie fertig sind, "frieren" Sie Ihren Vektor ein, um sich in die unveränderliche Struktur zu verwandeln, die Sie mit reinem Code verwenden möchten.

Meiner Meinung nach sollten Sie standardmäßig verwenden, Data.Sequencewenn eine Liste nicht geeignet ist. Verwenden Data.VectorSie diese Option nur, wenn Sie in Ihrem Verwendungsmuster nicht viele Änderungen vornehmen müssen oder wenn Sie eine extrem hohe Leistung innerhalb der ST / IO-Monaden benötigen.

Wenn all das Gerede über die STMonade Sie verwirrt: umso mehr Grund, sich an schnell und schön zu halten Data.Sequence.