Kurzschließ Art

Question

Ich verstehe, dass:

head (map (2**) [1..999999]) 

Wird nur bewerten tatsächlich 2 ** 1, und keiner der Rest, aber das Buch lese ich bin sagt, dass:

head (sort somelist) 

Will nur müssen das kleinste Element in der Liste finden, denn das ist alles, was verwendet wird. Wie funktioniert das? Soweit ich das beurteilen kann, wäre dies mit den mir bekannten Sortieralgorithmen (wie Blasensortierung) nicht möglich.

Der einzige Weg, ich könnte denken, dass dies funktionieren würde, wenn der Sortieralgorithmus durch die gesamte Liste auf der Suche nach dem kleinsten Element gehen würde, und dann auf der Liste ohne dieses Element recurse. Das hört sich für mich sehr langsam an.

Funktioniert die Sortierfunktion, oder gibt es einen anderen Sortieralgorithmus, den ich nicht kenne, der einen Kurzschluß ermöglichen würde?

Answer 1

:

brauchen nur das kleinste Element in der Liste zu finden, denn das ist alles, was verwendet wird.

... sollte wirklich sagen, dass die Funktion die minimale Menge an Arbeit tun muss, um nur , dass der Sortieralgorithmus erfordert das kleinste Element zu finden.

Zum Beispiel, wenn wir quicksort als unsere zugrunde liegenden Sortieralgorithmus verwendet werden, dann ist head . quicksort entspricht dem optimal (!) Auswahlalgorithmus als ‚quickselect‘ bekannt, die Worst-Case-linear ist. Darüber hinaus können wir implementieren k -quickselect nur durch take k . quicksort.

Wikipedia stellt in ihrem Artikel auf Auswahl-Algorithmen, die (Hervorhebung von mir):

Da Sprachunterstützung für die Sortierung mehr allgegenwärtig ist, der vereinfachenden Ansatz des durch Indizierung gefolgt Sortierung in vielen Umgebungen trotz ihres Nachteils ist bevorzugt in Geschwindigkeit. In der Tat, für faule Sprachen, kann diese vereinfachende Ansatz sogar Sie die bestmögliche Komplexität für die k kleinsten/größten sortierten (mit Maximum/Minimum als Sonderfall), wenn Ihre Sorte faul genug ist.

Quicksort funktioniert gut in diesem Szenario, während die Standardsortierung in Haskell (Mergesort) komponiert nicht ganz so gut, wie es mehr Arbeit als nötig macht jedes Element der sortierten Liste zurückzukehren. Als this post on the Haskell mailing list Anmerkungen:

lazy quicksort Lage ist, die Charge der ersten k kleinsten Elemente in

O (n + k log k) Gesamtzeit [1]

während lazy mergesort zu produzieren muss

O (n + k log n) Gesamtzeit [2]

weitere Sie 0 lesen vielleicht gefallen.

Answer 2

Der Algorithmus, den Sie gerade beschrieben haben, hat einen spezifischen Namen: "selection sort". Es ist O (n), also ist es nicht ganz das schnellste, was Sie tun könnten. Wenn Sie jedoch die ersten "k" -Elemente im sortierten Array haben möchten, wäre die Komplexität O (kn), was nett ist, wenn "k" klein genug ist (wie in Ihrem Beispiel).

Beachten Sie, dass Sie eine reine Funktion in einer funktionalen Sprache verwenden. Der Compiler ist wahrscheinlich in der Lage, in beiden Fällen optimierten Code für sort zu generieren, indem er die Art betrachtet, wie Funktionen zusammengesetzt werden. Wenn Sie head und sort erstellen, kann es leicht das minimale Element ableiten.

Answer 3

Wenn Sie eine Vergleichsfunktion erstellen, die ihre Argumente verfolgt, wie dies in GHCi der Befehlszeile ein:

> :module + Data.List Debug.Trace 
> let myCompare x y = trace ("\tCmp " ++ show x ++ " " ++ show y) $ compare x y 

dann können Sie das Verhalten sehen Sie selbst:

> sortBy myCompare "foobar" 

"  Cmp 'f' 'o' 
     Cmp 'o' 'b' 
     Cmp 'f' 'b' 
     Cmp 'a' 'r' 
     Cmp 'b' 'a' 
a  Cmp 'b' 'r' 
b  Cmp 'f' 'o' 
     Cmp 'f' 'r' 
f  Cmp 'o' 'o' 
     Cmp 'o' 'r' 
o  Cmp 'o' 'r' 
or" 

Haskell ist die Bewertung der Zeichenfolge lazily , ein Zeichen zu einer Zeit. Die linke Spalte wird gedruckt, während jedes Zeichen gefunden wird, wobei die rechte Spalte die erforderlichen Vergleiche aufzeichnet, wie durch "Trace" gedruckt.

Beachten Sie, dass Sie, wenn Sie dies kompilieren, insbesondere mit Optimierungen, möglicherweise ein anderes Ergebnis erhalten. Der Optimierer führt einen Striktheitsanalysator durch, der wahrscheinlich bemerkt, dass der gesamte String gedruckt wird, so dass es effizienter wäre, ihn eifrig zu bewerten.

versuchen Dann

> head $ sortBy myCompare "foobar" 

     Cmp 'f' 'o' 
     Cmp 'o' 'b' 
     Cmp 'f' 'b' 
     Cmp 'a' 'r' 
     Cmp 'b' 'a' 
'a' 

Wenn Sie verstehen wollen, wie dies funktioniert, den Quellcode für die Sortierfunktion nachschlagen und bewerten ‚sortieren‚foobar‘‘ manuell auf Papier.

qsort [] = [] 
qsort (x:xs) = qsort less ++ [x] ++ qsort greater 
    where (less, greater) = partition (< x) xs 

So

qsort ('f':"oobar") 
= qsort ('b':"a") ++ "f" ++ qsort ('o':"or") 
= ("a" ++ "b") ++ "f" ++ qsort ('o':"or") 

Und jetzt haben wir genug getan, um zu finden, dass ‚a‘ ist das erste Element in dem Ergebnis, ohne den anderen Aufruf zur „qsort“ zu bewerten. Ich habe den eigentlichen Vergleich weggelassen, weil er im Aufruf von "Partition" versteckt ist. Eigentlich ist "Partition" auch faul, also wurde das Argument zum anderen "qsort" nicht so weit ausgewertet, wie ich es gezeigt habe.Diese