Ich suche nach einer Datenstruktur in Haskell, die sowohl schnelles Indizieren als auch schnelles Anhängen unterstützt. Dies ist für ein Memo-Problem, das sich aus der Rekursion ergibt.
Aus der Art, wie Vektoren in C ++ arbeiten (die veränderbar sind, aber das sollte in diesem Fall keine Rolle spielen), scheinen unveränderliche Vektoren mit beiden (amortisierten) O (1) -Anhängen und O (1) -Indizieren möglich zu sein (ok ist es nicht, siehe Kommentare zu dieser Frage). Ist das in Haskell möglich oder sollte ich mit Data.Sequence gehen, die (AFAICT sowieso) O (1) append und O (log (min (i, n-i))) Indizierung?
Als Haskell-Neuling sehne ich mich nach einer praktischen, prägnanten Anleitung für Haskell-Datenstrukturen. Im Idealfall würde dies einen ziemlich umfassenden Überblick über die praktischsten Datenstrukturen geben, zusammen mit Leistungsmerkmalen und Hinweisen auf Haskell-Bibliotheken, in denen sie implementiert sind. Es scheint, dass es eine Menge Informationen gibt, aber ich habe festgestellt, dass es etwas verstreut ist. Frage ich zu viel?
Wenn Speicher dient, werden C ++ Vektoren als ein Array mit Begrenzungen und Größeninformationen implementiert. Wenn eine Einfügung die Grenzen über die Größe hinaus erhöhen würde, wird die Größe verdoppelt. Dies ist amortisierte O (1) -Zeiteinfügung (nicht O (1) wie Sie behaupten) und kann in Haskell mit dem Array -Typ gut emuliert werden, vielleicht mit passendem IO oder ST vorangestellt.
Bei einfachen Memoisierungsproblemen möchten Sie die Tabelle normalerweise einmal erstellen und später nicht mehr ändern. In diesem Fall können Sie vermeiden, dass Sie sich um das Anhängen kümmern müssen, indem Sie stattdessen an die Konstruktion der Memoisierungstabelle als eine Operation denken.
Eine Methode besteht darin, den Vorteil der verzögerten Auswertung zu nutzen und auf die Tabelle zu verweisen, während wir sie konstruieren.
%Vor%Diese Methode ist besonders nützlich, wenn die Abhängigkeiten zwischen den Elementen der Tabelle es schwierig machen, eine einfache Reihenfolge zu finden, um sie im Voraus zu bewerten. Es erfordert jedoch die Verwendung von umhüllten Arrays oder Vektoren, was diesen Ansatz aufgrund des zusätzlichen Overheads für große Tabellen ungeeignet macht.
Für nicht verpackte Vektoren haben Sie Operationen wie constructN , mit denen Sie eine Tabelle auf eine reine Art und Weise erstellen können, während Sie die darunter liegende Mutation verwenden, um sie effizient zu machen. Dazu übergibt man der Funktion eine unveränderliche Ansicht des Präfixes des bisher konstruierten Vektors, mit dem man dann das nächste Element berechnen kann.
Sehen Sie sich dies an, um eine fundiertere Auswahl zu treffen, was Sie verwenden sollten.
Aber die einfache Sache ist, wenn Sie das Äquivalent eines C ++ - Vektors wollen, verwenden Sie Data.Vector .
Tags und Links haskell vector data-structures