Ich möchte eine unveränderliche begrenzte FIFO-Warteschlange unterhalten, aus der ich die ältesten Werte nach einer bestimmten Zeit entfernen kann. In Scala funktioniert die unveränderliche.Queue gut für größenbeschränkte Warteschlangen (.size scheint O (N) zu sein, da sie intern auf List basiert, aber ich kann die Größe getrennt verwalten), aber es scheint keine billige Möglichkeit sein, auf das Kopfelement zuzugreifen, um das Alter des ältesten Werts mit etwas billigerem als O (N) zu testen, so dass ich den Ablaufstatus des ältesten Eintrags nicht testen kann. Irgendwelche Hinweise auf eine rein funktionale (unveränderliche) Implementierung?
Dieser Artikel Haskell: Warteschlangen ohne Zeiger , beschreibt eine rein funktionale Queue mit O (1) amortized cost ( edit : zum Hinzufügen und Entfernen von Elementen). Ich denke, dass die Datenstruktur von Chris Okasaki stammt und mehr Details in seinem Buch sind.
Die Grundidee besteht darin, die Warteschlange in zwei Listen zu zerlegen, eine für die Vorderseite und eine für die Rückseite. Neue Elemente werden zu "front" hinzugefügt. "Zurück" wird in umgekehrter Reihenfolge gespeichert, um das Herausspringen von Elementen zu erleichtern. Wenn alle Elemente von "zurück" weg sind, wird "vorne" umgekehrt und wieder als "zurück" identifiziert. Diese Datenstruktur hat O (1) amortisierten Kosten für diese Operationen, aber anscheinend mit etwas Arbeit kann es auf O (1) reduziert werden, richtig.
Bearbeiten : Okasakis Papier beschreibt eine elegante, rein funktionale Implementierung von Warteschlangen und Double-ended Queues (Deques). Deques erlauben das Hinzufügen oder Entfernen von Elementen von jedem Ende. Alle diese Operationen sind O (1), worst case.
Der Standard immutable.Queue in Scala kann so angepasst werden, dass er für amortisierte Komplexität funktioniert. Beachten Sie jedoch, dass die Operation peek eine neue Queue zurückgibt, andernfalls können aufeinanderfolgende Aufrufe von peek in O (n) ausgeführt werden.
Sie können Queue entweder erweitern oder eine völlig neue Klasse erstellen, indem Sie sie anpassen. Hier ist eine Version, die es erweitert:
Wenn ich die Frage richtig verstanden habe, suchen Sie nach einer doppelendigen Warteschlange ( deque ). Es gibt Papiere von Okasaki, Kaplan und Tarjan über rein funktionale Deques. Was die Implementierungen betrifft, ist es am einfachsten, die Standardimplementierung von collection.immutable.IndexedSeq zu nehmen, die collection.immutable.Vector ist, nach diese Tabelle hat konstante Kosten für head und last geschätzt (es sagt tail , aber ich würde vermuten, dass last auch O (1) ist).
Der Okasaki / Kaplan / Tarjan wurde anscheinend von Henry Ware implementiert.
Die andere Implementierung, die mir in den Sinn kommt, ist der FingerTree von Hintze, für den verschiedene Implementierungen in scala existieren. Scalaz hat eines, das ich vor einiger Zeit in gestellt habe ein separates Paket , da ich es oft benutze. Laut einer Präsentation von Daniel Spiewak (ich kann mich nicht erinnern, wo ich das gesehen habe) ist der FingerTree in den konstanten Zeitfaktoren ziemlich langsam - und auch die Seite von Henry Ware sagt, dass sie langsamer ist als seine andere Implementierung.
Tags und Links scala queue functional-programming