Come evitare il calcolo non necessario?

Question

Devo restituire false se un test fallisce per più di 3 elementi in un elenco. C'è qualcosa che posso fare per ottimizzare?

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

Questa è la funzione che sto cercando di ottimizzare,

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

Il mio tentativo di ottimizzazione, assumendo prendere se trova 4 elementi non cercare altro.

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

Grazie.

Answer 1

Si può semplicemente utilizzare filter con qualcosa che verifica la presenza di elementi in mancanza, poi take 4 e vedere quanti elementi avete con length.

valutazione pigra significa che non si preoccuperà di controllare nulla dopo aver trovato quei quattro, quindi hai finito. Ovviamente, se il test fallisce per tre o meno elementi, controllerà l'intera lista, ma non c'è niente che tu possa fare al riguardo.

La cosa importante per evitare è qualcosa come "contare gli elementi che non superano il test", o "filtro e quindi ottenere la lunghezza del risultato", o qualcosa del genere. Senza prima usare take o qualcosa di simile, farlo forzerà il controllo dell'intero elenco. Questa è una versione più generale dell '"uso null o pattern matching per controllare gli elenchi vuoti" consigli spesso dati ai principianti. Ma sembra che tu stia già evitando questo errore!

Answer 2

Per un numero basso come 3, è possibile utilizzare solo la corrispondenza del modello.

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

Answer 3

Permettetemi innanzitutto di riscrivere la funzione di un po ', come

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

è forse più idiomatica che la vostra versione. (Si noti che ho anche cambiato la firma tipo come il vostro è stato corretto. Inoltre, si dovrebbe avere scritto 1 .. 1000 piuttosto che 1.1000.)

valutazione pigro è il tuo migliore amico qui, come in genere assicurarsi che nessun calcoli inutili saranno eseguita.

Sfortunatamente, l'utilizzo di length (o il mapping di ciascun elemento da un elenco a 1 e quindi la somma dell'elenco risultante, come si fa) sta entrando in questo modo. Cioè, length è rigoroso nella colonna vertebrale dell'elenco: può solo produrre la lunghezza dell'elenco se lo valuta fino alla sua fine, il che, in questo caso, significa che il tuo programma dovrà eseguire l'assegno migliaia di volte .

Una soluzione sarebbe quella di combinare il calcolo della lunghezza (ad es., L'attraversamento della colonna della lista) e il test se la lunghezza calcolata non supera una certa soglia in una singola funzione che è in realtà artificiale nella spina dorsale della sua lista di argomenti:

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

e quindi scrivere

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

Per una soluzione riutilizzabile, è possibile ovviamente astratto su sia il predicato e la soglia:

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

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

Infine, come sottolinea Hammar, se la vostra trebbiatura vecchio è abbastanza piccolo e fisso, si può semplicemente usare la corrispondenza del modello per determinare se un elenco è abbastanza corto.

Answer 4

Vorrei cogliere l'occasione per pubblicizzare lo lazy natural numbers un po '. Usando questa biblioteca e genericLength, possiamo solo scrivere

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

e lo farà non più lavoro di quanto deve: questa funzione troverà al massimo quattro elementi va bene prima di tornare. Ad esempio:

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