Wie vermeidet man unnötige Berechnungen?

Question

Ich muss false zurückgeben, wenn ein Test für mehr als 3 Elemente in einer Liste fehlschlägt. Kann ich irgendetwas optimieren?

isItemOk :: Integer -> Boolean 
isItemOk = (some costly opernation) 

Dies ist die Funktion, die ich zu optimieren versuchen,

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum ([ 1 | x <- [1.1000], isItemOk x ]) 

bei Optimierung Mein Versuch, unter der Annahme, nehmen, wenn es vier Elemente findet für mehr wird nicht aussehen.

isListOk :: [Integer] -> Boolean 
isListOk = 3 >= sum (take 4 [ 1 | x <- [1.1000], isItemOk x ]) 

Danke.

Answer 1

Sie können nur filter mit etwas verwenden, die für versagenden Elemente überprüft, dann take 4 und sehen, wie viele Elemente, die Sie mit length haben.

Faule Auswertung bedeutet, dass es nicht störend ist, nach dem Finden dieser vier etwas zu überprüfen, also sind Sie fertig. Wenn der Test für drei oder weniger Elemente fehlschlägt, überprüft er natürlich die gesamte Liste, aber Sie können nichts dagegen tun.

Die wichtige Sache zu Vermeiden Sie ist etwas wie "zählen Sie die Elemente, die den Test nicht bestanden", oder "filtern und dann die Länge des Ergebnisses" oder so etwas. Ohne zuerst take oder etwas Ähnliches zu verwenden, wird dadurch das Überprüfen der gesamten Liste erzwungen. Dies ist eine allgemeinere Version der "Verwenden null oder Mustererkennung, um für leere Listen zu überprüfen" Ratschläge, die oft Anfänger gegeben. Aber es sieht so aus, als ob du diesen Fehler bereits meidest!

Answer 2

Für eine niedrige Zahl wie 3 können Sie einfach Mustervergleich verwenden.

case filter isItemOk xs of 
    x1 : x2 : x3 : _ -> ... 
    _    -> ... 

Answer 3

Lassen Sie mich zunächst Ihre Funktion ein wenig umschreiben, als

isListOk :: Bool 
isListOk = length (filter isItemOk [1 .. 1000]) <= 3 

ist wohl mehr idiomatische als Ihre Version. (Beachten Sie, dass ich auch die Art Signatur geändert haben wie Sie falsch waren. Darüber hinaus sollten Sie 1 .. 1000 eher geschrieben haben, als 1.1000.)

Verzögerte Auswertung ist dein bester Freund hier, wie es in der Regel dafür sorgen, dass keine unnötigen Berechnungen werden durchgeführt.

Leider ist Ihre Verwendung von length (oder Zuordnung jedes Element aus einer Liste auf 1 und dann die resultierende Liste summieren, wie Sie) in den Weg kommt hier. Das heißt, length ist streng in der Wirbelsäule der Liste: es kann nur die Länge der Liste produzieren, wenn es bis zu seinem Ende auswertet, was in diesem Fall bedeutet, dass Ihr Programm Ihren Scheck tausend Mal ausführen muss .

Eine Lösung wäre, die Berechnung der Länge zu kombinieren (d. H.Die Traversierung der Wirbelsäule in der Liste) und der Test, ob die berechnete Länge in der Tat nicht eine bestimmte Schwelle in eine einzige Funktion überschreiten, die in der Wirbelsäule der Argumentliste lazy ist:

isNotLongerThan :: [a] -> Integer -> Bool 
isNotLongerThan []  n = n >= 0 
isNotLongerThan (_ : xs) n = n >= 1 && isNotLongerThan xs (n - 1) 

und dann schreiben

isListOk :: Bool 
isListOk = filter isItemOk [1 .. 1000] `isNotLongerThan` 3 

Für eine wiederverwendbare Lösung, Sie beide das Prädikat natürlich abstrakt über und der Schwelle:

forNoMoreThan :: (a -> Bool) -> Integer -> [a] -> Bool 
forNoMoreThan p n = (`isNotLongerThan` n) . filter p 

isListOk :: Bool 
isListOk = (isItemOk `forNoMoreThan` 3) [1 .. 1000] 

schließlich als hammar weist darauf hin, wenn Ihr dreschen alt ist klein genug und behoben, Sie können einfach Mustervergleich verwenden, um festzustellen, ob eine Liste kurz genug ist.

Answer 4

Ich möchte diese Gelegenheit zu einem Hype lazy natural numbers ein wenig nutzen. Mit Hilfe dieser Bibliothek und genericLength können wir

import Data.Number.Natural 
import Data.List 
isListOk = (3 :: Natural) >= genericLength (filter isItemOk [1..1000]) 

schreiben Sie einfach, und es wird keine Arbeit mehr tun, als es hat: Diese Funktion wird vor der Rückkehr höchstens vier in Ordnung anbietet. Zum Beispiel:

> (3 :: Natural) >= genericLength (filter even (2:4:6:8:undefined)) 
False