In vielen Systemen benötigt head.reverse Speicherplatz proportional zur Größe der Liste, während last konstanten Speicherplatz erfordert.Raumkomplexität von head.reverse vs. last
Gibt es Systeme, die eine solche Transformation durchführen? Ähnlich für reverse.take n.reverse?
Edit: Ich möchte meine Frage erweitern: Ich bin nicht nach einer konkreten Transformation — Ich bin eher nach keine Optimierung zu diesem Zweck.
Sie können eine einfache Rewrite-Regel dafür schreiben.
http://www.haskell.org/haskellwiki/Playing_by_the_rules
Fusion Regeln kann es fangen, auch, je nachdem, wie umgekehrt kodiert wird.
Sie schlagen vor, 'head.reverse = last' zu deklarieren. Recht? – false
Wenn wir Tropfen vergleichen und letzte
>>> last [1..10^5]
100000
(0.01 secs, 10496736 bytes)
>>> last [1..10^6]
1000000
(0.05 secs, 81968856 bytes)
>>> last [1..10^7]
10000000
(0.32 secs, 802137928 bytes)
>>> drop (10^5-1) [1..10^5]
[100000]
(0.01 secs, 10483312 bytes)
>>> drop (10^6-1) [1..10^6]
[1000000]
(0.05 secs, 82525384 bytes)
>>> drop (10^7-1) [1..10^7]
[10000000]
(0.32 secs, 802142096 bytes)
erhalten wir eine ähnliche Leistung in Raum und Zeit, ich muss zugeben, dass ich ein wenig betrogen, weil wir hier nicht über die Länge der Liste berechnen müssen. Jedenfalls glaube ich, dass es kein Problem im Weltraum sein sollte. Dann kehrt Ihr um. nimm n. Revers könnte mit Tropfen und Länge ausgedrückt werden.
Als Randnotiz habe ich andere Abhilfe und das Ergebnis ist getestet schlecht.
takeLastN = foldl' (.) id . flip replicate tail
lastN = foldl' (.) last . flip replicate init
Die Berechnung der Länge erfordert effektiv Platz proportional zur Länge, da die Liste nur dann per Drop verwendet werden kann. Recht? – false
Nicht so sehr, wenn Sie die Länge der Liste berechnen, müssen Sie nur das Ergebnis akkumulieren (addieren Sie eins), also wird nur ein "Schlitz" des Gedächtnisses während des ganzen Prozesses benötigt, umgekehrt als die Menge des Gedächtnisses wachsend mehr und mehr, während wir die Liste durchqueren, konstruieren wir eine neue Liste der gleichen Länge. – zurgl
Jedenfalls, wie Sie allgemein über "System" sprechen, habe ich irgendwo gelesen, als für eine spezielle Codierung des Datentyps Liste können wir die Länge der Liste durch Konstruktion enthalten, dann, wenn Sie nach der Länge der Liste fragen, ist die Antwort Rückkehr in konstanter Zeit und Raum. Die Liste enthält diese zusätzlichen Informationen. Aber ich denke, es hängt vom abhängigen Typ ab, und ich bin mir nicht sicher, ob wir es in Haskell tun können, wie es ist. – zurgl
können Sie reverse . take n . reverse verwandeln Sie Ihre Liste als besonders stumpfe faul natürliche Zahl durch Behandlung: leere Listen sind Null, und conses succ sind. Für faule Naturals als Listen codiert, Subtraktion drop:
type LazyNat a = [a]
lengthLazy :: [a] -> LazyNat a
lengthLazy = id
dropLazy :: LazyNat a -> [b] -> [b]
dropLazy [] xs = xs
dropLazy (_:n) (_:xs) = dropLazy n xs
dropLazy _ _ = []
-- like Prelude.subtract, this is flip (-)
subtractLazy :: Int -> LazyNat a -> LazyNat a
subtractLazy = drop
Jetzt können wir leicht die „nehmen letzte n“ Funktion implementieren:
takeLast n xs = dropLazy (subtractLazy n (lengthLazy xs)) xs
... und Sie werden erfreut sein zu wissen, dass Nur n Conse müssen zu jeder Zeit im Speicher sein. Insbesondere kann takeLast 1 (oder auch takeLast N für jedes Literal N) in konstantem Speicher ausgeführt werden. Sie können dies überprüfen, indem Sie vergleichen, was passiert, wenn Sie takeLast 5 [1..] mit dem ausführen, was passiert, wenn Sie in ghci ausführen.
Natürlich, ich habe versucht, über sehr suggestiv Namen zu verwenden, aber in einer realen Implementierung könnte man den ganzen Unsinn über Inline:
takeLast n xs = go xs (drop n xs) where
go lastn [] = lastn
go (_:xs) (_:n) = go xs n
go _ _ = []
nicht sicher, was Sie nach. Eine Rewrite-Regel könnte es tun, wenn dies ausreichend nahe an dem ist, was Sie wollen. –
@DanielFischer: Ich bin eher an einer allgemeinen Methode interessiert, um das zu lösen. Denken Sie an das zweite Beispiel. – false
Wenn Sie das immer noch interessiert, hängt die Antwort davon ab, wie viele Verbraucher die Liste hat; Wenn "last" der einzige ist, sollte es in konstantem Raum und O (n) -Zeit laufen; aber wenn ein anderer Verbraucher einen Verweis auf diese Liste hat, wird er ganz entstehen, wenn "letzter" über ihn bis zu seiner letzten Zelle zählt. Also O (n) Raum und Zeit. Ähnlich für das 'takeLast' in Daniel Wagners Antwort. - Oder wir können die * tatsächliche Implementierung * von Listen ändern, als selbstabgleichende Bäume mit Index als Schlüssel, mit offensichtlichen Konsequenzen.Clojure verwendet sogar klügere Bäume mit hohem Verzweigungsfaktor (32?). –