Istanza di funzione poco ricorsiva non a coda

Question

Di seguito sono descritte due funzioni per trovare il valore massimo di un elenco di numeri.

mx :: (Ord a) => [a] -> a 
mx [] = error "Empty list" 
mx [x] = x 
mx (x:xs) 
    | x > (mx xs) = x 
    | otherwise = (mx xs) 

mx' (x:xs) = findMax x xs 
    where 
    findMax cmx [] = cmx 
    findMax cmx (x:xs) | x > cmx = findMax x xs 
       | otherwise = findMax cmx xs 

main = do 
    print $ mx [1..30] 

Timing il codice precedente, prima per mx'(tail-ricorsiva) e successivo per mx (non-tail-ricorsiva), abbiamo le seguenti temporizzazioni.

Lenovo-IdeaPad-Y510P:/tmp$ time ./t 
30 

real 0m0.002s 
user 0m0.000s 
sys 0m0.001s 
Lenovo-IdeaPad-Y510P:/tmp$ ghc -O2 t.hs 
[1 of 1] Compiling Main    (t.hs, t.o) 
Linking t ... 
Lenovo-IdeaPad-Y510P:/tmp$ time ./t 
30 

real 0m6.272s 
user 0m6.274s 
sys 0m0.000s 

Qualcuno può spiegare perché c'è una così grande differenza di prestazioni per un elenco di soli 30 elementi?

Answer 1

Come altri hanno sottolineato, GHC non fa eliminazione sottoespressione comune (CSE), causando il vostro primo frammento per l'esecuzione in tempo esponenziale.

Per capire perché, si consideri ad es.

test1 = length [1..1000] + sum [1..1000] 
test2 = let l = [1..1000] in length l + sum l 

I due esempi sono semanticamente equivalenti, ma test1 eseguito in spazio costante mentre test2 in spazio lineare (l'intero 1000 cellule vengono allocati). Fondamentalmente, in questo caso CSE nega i vantaggi della pigrizia.

Poiché CSE può portare a peggiore prestazione, GHC è piuttosto conservativo nell'applicarlo.

spiegazione più GHC FAQs:

https://www.haskell.org/haskellwiki/GHC/FAQ#Does_GHC_do_common_subexpression_elimination.3F

Answer 2

Calling mx [1..3] risultati in seguito ad inviti:

mx [1..3] 

    mx [2..3] -- x > (mx xs) in mx [1..3] 
     mx [3] -- x > (mx xs) in mx [1..2] 
     mx [3] -- otherwise = (mx xs) in mx [1..2] 

    mx [2..3] -- otherwise = (mx xs) in mx [1..3] 
     mx [3] -- x > (mx xs) in mx [1..2] 
     mx [3] -- otherwise = (mx xs) in mx [1..2] 

Il numero di chiamate mx per la ricerca di massima di [1..n] è O(2^n): 2^n - 1, esattamente.

mx' rende O(n) chiamate: n + 1, esattamente.

mx' [1..3] 
    findMax 1 [2, 3] 
     findMax 2 [3] 
      findMax 3 [] 

Per n = 30, come nel test, mx rende 1073741823 chiamate, e mx' solo 29.

Answer 3

Il tuo secondo algoritmo è lineare, finirà per fare un singolo passaggio nella tua lista. Il tuo primo algoritmo ha un runtime esponenziale in questo caso (che si verifica nel caso peggiore). Si finisce essenzialmente per controllare tutto nella lista per determinare che il primo elemento, 1, non è il massimo. Quindi consideri il secondo elemento, 2, e guardi l'intero resto dell'elenco per sapere che anche questo non è il massimo.

Se si esegue il programma utilizzando mx e valori come 22, 23, ..., 30 vedrete una crescita esponenziale chiaramente in fase di esecuzione.

In particolare, questo non è semplicemente un problema di ricorsione di coda o no, si tratta di un algoritmo ricorsivo inefficiente rispetto a uno efficiente. È possibile implementarli in una lingua senza ricorsione in coda e vedere ancora le prestazioni più rapide di mx' su mx.

Answer 4

Il problema non è tanto la coda-ricorsività, è il fatto che nel mx nel caso generale si calcola mx xs due volte: una volta per confrontarlo con x, e poi una seconda volta per restituirlo. Ognuna di queste chiamate chiama due volte lo mx xs, che quindi fa lo stesso, ecc., Risultando in un tempo di esecuzione esponenziale.

È possibile rimuovere questo problema semplicemente salvando il risultato della prima chiamata di usarlo per la seconda volta:

mx :: (Ord a) => [a] -> a 
mx [] = error "Empty list" 
mx [x] = x 
mx (x:xs) = 
    let mxxs = mx xs in 
    if x > mxxs then x else mxxs