Lazy Evaluation und Zeitkomplexität

Ich war auf der Suche um Stackoverflow nicht-triviale Lazy Evaluation , die Keegan McAllister Präsentation führte mich: Warum Haskell lernen . In Folie 8 zeigt er die minimale Funktion, definiert als:

minimum = head . sort

und gibt an, dass seine Komplexität O (n) ist. Ich verstehe nicht, warum die Komplexität als linear bezeichnet wird, wenn die Sortierung nach Ersetzung O (nlog n) ist. Die in der Veröffentlichung angegebene Sortierung kann nicht linear sein, da sie nichts über die Daten annimmt, wie dies für lineare Sortiermethoden wie das Zählen der Sortierung erforderlich wäre.

Spielt die faule Bewertung hier eine mysteriöse Rolle? Wenn ja, welche Erklärung steckt dahinter?

In minimum = head . sortwird das sortnicht vollständig erledigt, weil es nicht im Voraus erledigt wird . Das sortwird nur so viel getan, wie nötig ist, um das allererste Element zu produzieren, das von verlangt wird head.

Bei z. B. Mergesort werden zunächst die nNummern der Liste paarweise verglichen, dann werden die Gewinner gepaart und verglichen ( n/2Zahlen), dann die neuen Gewinner ( n/4) usw. Insgesamt werden O(n)Vergleiche durchgeführt, um das minimale Element zu erhalten.

mergesortBy less [] = []
mergesortBy less xs = head $ until (null.tail) pairs [[x] | x <- xs]
  where
    pairs (x:y:t) = merge x y : pairs t
    pairs xs      = xs
    merge (x:xs) (y:ys) | less y x  = y : merge (x:xs) ys
                        | otherwise = x : merge  xs (y:ys)
    merge  xs     []                = xs
    merge  []     ys                = ys

Der obige Code kann erweitert werden, um jede von ihm produzierte Nummer mit einer Reihe von Vergleichen zu kennzeichnen, die in seine Produktion eingeflossen sind:

mgsort xs = go $ map ((,) 0) xs  where
  go [] = []
  go xs = head $ until (null.tail) pairs [[x] | x <- xs]   where
    ....
    merge ((a,b):xs) ((c,d):ys) 
            | (d < b)   = (a+c+1,d) : merge ((a+1,b):xs) ys    -- cumulative
            | otherwise = (a+c+1,b) : merge  xs ((c+1,d):ys)   --   cost
    ....

g n = concat [[a,b] | (a,b) <- zip [1,3..n] [n,n-2..1]]   -- a little scrambler

Wenn wir es für mehrere Listenlängen ausführen, sehen wir, dass es tatsächlich so ist~ n :

*Main> map (fst . head . mgsort . g) [10, 20, 40, 80, 160, 1600]
[9,19,39,79,159,1599]

Um zu sehen, ob der Sortiercode selbst ist ~ n log n, ändern wir ihn so, dass jede produzierte Nummer nur ihre eigenen Kosten trägt. Die Gesamtkosten werden dann durch Summierung über die gesamte sortierte Liste ermittelt:

    merge ((a,b):xs) ((c,d):ys) 
            | (d < b)   = (c+1,d) : merge ((a+1,b):xs) ys      -- individual
            | otherwise = (a+1,b) : merge  xs ((c+1,d):ys)     --   cost

Hier sind die Ergebnisse für Listen unterschiedlicher Länge,

*Main> let xs = map (sum . map fst . mgsort . g) [20, 40, 80, 160, 320, 640]
[138,342,810,1866,4218,9402]

*Main> map (logBase 2) $ zipWith (/) (tail xs) xs
[1.309328,1.2439256,1.2039552,1.1766101,1.1564085]

Das Obige zeigt empirische Wachstumsordnungen für zunehmende Listenlängen n, die schnell abnehmen, wie dies typischerweise durch ~ n log nBerechnungen gezeigt wird. Siehe auch diesen Blog-Beitrag . Hier ist eine kurze Korrelationsprüfung:

*Main> let xs = [n*log n | n<- [20, 40, 80, 160, 320, 640]] in 
                                    map (logBase 2) $ zipWith (/) (tail xs) xs
[1.3002739,1.2484156,1.211859,1.1846942,1.1637106]

edit: Lazy Evaluation kann metaphorisch als eine Art Produzenten- / Konsumentensprache ^{1 angesehen werden} , mit unabhängigem Memoizing-Speicher als Vermittler. Jede produktive Definition, die wir schreiben, definiert einen Produzenten, der seine Produktion Stück für Stück produziert, wie und wann es von seinen Verbrauchern verlangt wird - aber nicht früher. Was auch immer produziert wird, wird gespeichert, sodass ein anderer Verbraucher, wenn er dieselbe Ausgabe in unterschiedlichem Tempo verbraucht, auf denselben zuvor gefüllten Speicher zugreift.

Wenn keine Verbraucher mehr übrig sind, die sich auf ein Lager beziehen, wird Müll gesammelt. Manchmal ist der Compiler mit Optimierungen in der Lage, den Zwischenspeicher vollständig zu beseitigen und den Mittelsmann auszuschalten.

¹ siehe auch: Einfache Generatoren gegen Lazy Evaluation von Oleg Kiselyov, Simon Peyton-Jones und Amr Sabry.

Angenommen, es minimum' :: (Ord a) => [a] -> (a, [a])handelt sich um eine Funktion, die das kleinste Element in einer Liste zusammen mit der Liste mit diesem entfernten Element zurückgibt. Dies kann natürlich in O (n) Zeit erfolgen. Wenn Sie dann definieren sortals

sort :: (Ord a) => [a] -> [a]
sort xs = xmin:(sort xs')
    where
      (xmin, xs') = minimum' xs

dann bedeutet faule Auswertung, dass (head . sort) xsnur in dem ersten Element jemals berechnet wird. Dieses Element ist, wie Sie sehen, einfach (das erste Element) des Paares minimum' xs, das in O (n) -Zeit berechnet wird.

Wie Delnan betont, hängt die Komplexität natürlich von der Implementierung von ab sort.

Sie haben eine gute Anzahl von Antworten erhalten, die sich mit den Besonderheiten von befassen head . sort. Ich werde nur ein paar allgemeinere Aussagen hinzufügen.

Bei eifriger Auswertung wird die rechnerische Komplexität verschiedener Algorithmen auf einfache Weise zusammengesetzt. Beispielsweise muss die kleinste Obergrenze (LUB) für f . gdie Summe der LUBs für fund sein g. So können Sie fund gals Black Boxes und Vernunft ausschließlich in Bezug auf ihre LUBs behandeln.

Bei verzögerter Auswertung f . gkann jedoch eine LUB besser sein als die Summe der LUBs von fund g. Sie können keine Black-Box-Argumentation verwenden, um die LUB zu beweisen. Sie müssen die Implementierungen und ihre Interaktion analysieren.

Daher ist die oft zitierte Tatsache, dass die Komplexität der verzögerten Bewertung viel schwerer zu begründen ist als die eifrige Bewertung. Denken Sie nur an Folgendes. Angenommen, Sie versuchen, die asymptotische Leistung eines Codeteils zu verbessern, dessen Form ist f . g. In einer eifrigen Sprache gibt es eine offensichtliche Strategie, der Sie folgen können: Wählen Sie die komplexere von fund aus gund verbessern Sie diese zuerst. Wenn Ihnen das gelingt, gelingt Ihnen die f . gAufgabe.

In einer faulen Sprache können Sie dagegen folgende Situationen haben:

• Sie verbessern die Komplexität von fund g, f . gverbessern sich aber nicht (oder werden noch schlimmer ).
• Sie können sich f . gauf eine Weise verbessern , die nicht hilft (oder sich sogar verschlechtert ) foder g.

Die Erklärung hängt von der Implementierung ab sort, und für einige Implementierungen ist dies nicht der Fall. Beispielsweise hilft bei einer Einfügesortierung, die am Ende der Liste eingefügt wird, eine verzögerte Auswertung nicht. Wählen Sie also eine Implementierung aus, die Sie betrachten möchten, und verwenden Sie der Einfachheit halber die Auswahlsortierung:

sort [] = []
sort (x:xs) = m : sort (delete m (x:xs)) 
  where m = foldl (\x y -> if x < y then x else y) x xs

Die Funktion verwendet eindeutig die Zeit O (n ^ 2), um die Liste zu sortieren. Da sie jedoch headnur das erste Element der Liste benötigt, sort (delete x xs)wird sie niemals ausgewertet!

Es ist nicht so mysteriös. Wie viel von einer Liste müssen Sie sortieren, um das erste Element zu liefern? Sie müssen das minimale Element finden, was leicht in linearer Zeit erfolgen kann. Wie es passiert, wird dies bei einigen Implementierungen der sortverzögerten Evaluierung für Sie erledigt.

Eine interessante Möglichkeit, dies in der Praxis zu sehen, besteht darin, die Vergleichsfunktion zu verfolgen.

import Debug.Trace
import Data.List

myCmp x y = trace (" myCmp " ++ show x ++ " " ++ show y) $ compare x y

xs = [5,8,1,3,0,54,2,5,2,98,7]

main = do
    print "Sorting entire list"
    print $ sortBy myCmp xs

    print "Head of sorted list"
    print $ head $ sortBy myCmp xs

Beachten Sie zunächst die Art und Weise, in der die Ausgabe der gesamten Liste mit den Ablaufverfolgungsnachrichten verschachtelt ist. Beachten Sie zweitens, wie ähnlich die Ablaufverfolgungsnachrichten sind, wenn Sie lediglich den Kopf berechnen.

Ich habe dies gerade durch Ghci geführt, und es ist nicht genau O (n): Es sind 15 Vergleiche erforderlich, um das erste Element zu finden, nicht die 10, die erforderlich sein sollten. Aber es ist immer noch kleiner als O (n log n).

Bearbeiten: Wie Vitus weiter unten ausführt, ist 15 Vergleiche anstelle von 10 nicht dasselbe wie zu sagen, dass es nicht O (n) ist. Ich habe nur gemeint, dass es mehr als das theoretische Minimum braucht.

Inspiriert von Paul Johnsons Antwort habe ich die Wachstumsraten für die beiden Funktionen aufgezeichnet. Zuerst habe ich seinen Code geändert, um ein Zeichen pro Vergleich zu drucken:

import System.Random
import Debug.Trace
import Data.List
import System.Environment

rs n = do
    gen <- newStdGen
    let ns = randoms gen :: [Int]
    return $ take n ns

cmp1 x y = trace "*" $ compare x y
cmp2 x y = trace "#" $ compare x y

main = do
    n <- fmap (read . (!!0)) getArgs
    xs <- rs n
    print "Sorting entire list"
    print $ sortBy cmp1 xs

    print "Head of sorted list"
    print $ head $ sortBy cmp2 xs

Wenn wir die *und #Zeichen zählen, können wir die Vergleichszahlen an gleichmäßig verteilten Punkten abtasten (entschuldigen Sie meine Python):

import matplotlib.pyplot as plt
import numpy as np
import envoy

res = []
x = range(10,500000,10000)
for i in x:
    r = envoy.run('./sortCount %i' % i)
    res.append((r.std_err.count('*'), r.std_err.count('#')))

plt.plot(x, map(lambda x:x[0], res), label="sort")
plt.plot(x, map(lambda x:x[1], res), label="minimum")
plt.plot(x, x*np.log2(x), label="n*log(n)")
plt.plot(x, x, label="n")
plt.legend()
plt.show()

Wenn Sie das Skript ausführen, erhalten Sie die folgende Grafik:

Die Steigung der unteren Linie ist ..

>>> import numpy as np
>>> np.polyfit(x, map(lambda x:x[1], res), deg=1)
array([  1.41324057, -17.7512292 ])

..1.41324057 (vorausgesetzt, es ist eine lineare Funktion)