Ich brauchte eine effiziente Gleitfensterfunktion in Haskell, also schrieb ich folgendes:
%Vor% Mein Problem dabei ist, dass ich denke, dass die Komplexität O (n * m) ist, wobei m die Länge der Liste und n die Fenstergröße ist. Sie zählen die Liste einmal für take , ein anderes Mal für length , und Sie tun es in der Liste von im Wesentlichen m-n-mal. Es scheint, als könnte es effizienter sein, aber ich weiß nicht, wie ich es linearer machen soll. Irgendwelche Abnehmer?
Sie können Seq von Data.Sequence verwenden, das an beiden Enden eine Warteschlange von (1) Enqueue- und Dequeues hat:
Beachten Sie, dass Ihr Algorithmus notwendigerweise O (N * M) ist, wenn Sie das gesamte Ergebnis materialisieren, da dies die Größe Ihres Ergebnisses ist. Die Verwendung von Seq verbessert lediglich die Leistung um einen konstanten Faktor.
Beispiel Verwendung:
%Vor%Sie können nicht besser werden als O (m * n) , da dies die Größe der Ausgabedatenstruktur ist.
Sie können jedoch vermeiden, die Länge der Fenster zu überprüfen, wenn Sie die Reihenfolge der Operationen umkehren: Erstellen Sie zuerst n verschobene Listen und zippen Sie sie dann zusammen. Durch das Zippen werden diejenigen automatisch entfernt, die nicht genug Elemente haben.
%Vor% Das Zippen einer Liste von Listen ist nur eine Umsetzung , aber im Gegensatz zu transpose von Data.List werden Ausgaben verworfen das hätte weniger als n Elemente.
Nun ist es ganz einfach, die Fensterfunktion zu aktivieren: Nehmen Sie m Listen, die jeweils um 1 verschoben sind, und zippen Sie sie einfach:
%Vor%Funktioniert auch für unendliche Listen.
Wenn Sie eine Länge von O (1) haben wollen, dann verwenden Sie eine Struktur, die O (1) Länge liefert? Wenn Sie nicht nach Fenstern aus einer unendlichen Liste suchen, sollten Sie Folgendes in Betracht ziehen:
%Vor%Die Konversation jedes Fensters von einem Vektor zu einer Liste könnte Sie beißen, ich werde dort keine optimistische Vermutung riskieren, aber ich wette, dass die Leistung besser ist als die reine Listenversion.
Lassen Sie uns zuerst die Fenster öffnen, ohne sich um die kurzen am Ende zu kümmern:
%Vor%Nun wollen wir die kurzen loswerden, ohne die Länge jedes einzelnen zu überprüfen.
Da wir wissen, dass sie am Ende sind, könnten wir sie so verlieren:
%Vor%Aber das ist nicht gut, da wir noch eine extra Zeit durchmachen, um seine Länge zu bekommen. Es funktioniert auch nicht auf unendlichen Listen, die Ihre ursprüngliche Lösung getan hat.
Lassen Sie uns stattdessen eine Funktion schreiben, um eine Liste als Lineal zu verwenden, um die Menge zu messen, die von einem anderen genommen werden soll:
%Vor%Jetzt können wir das schreiben:
%Vor%Funktioniert auch auf unendlichen Listen:
%Vor% Wie Gabriel Gonzalez sagt, ist die zeitliche Komplexität nicht besser, wenn Sie das ganze Ergebnis nutzen wollen. Aber wenn Sie nur einige der Fenster verwenden, schaffen wir es jetzt, die Arbeit von take und length für diejenigen zu vermeiden, die Sie nicht verwenden.
Für das gleitende Fenster habe ich auch ungepackte Vetoren verwendet, wie Länge, Taking, Drop und SplitAt sind O (1) -Operationen.
Der Code von Thomas M. DuBuisson ist ein um n verschobenes Fenster, kein Gleiten, außer wenn n = 1 ist. Daher fehlt ein (++), aber das kostet O (n + m). Also vorsichtig, wo du es hingestellt hast.
%Vor% Ich habe es mit +RTS -sstderr und:
und bekam Realtime 1,051s und 96,9% Auslastung, wobei man bedenkt, dass nach dem gleitenden Fenster zwei O (m) -Operationen durchgeführt werden.
Tags und Links haskell time-complexity sliding-window