2011-08-21 25 views
5

Sto cercando di imitare il Sieve per trovare tutti i numeri primi meno di un numero usando Haskell. Ho trovato altri programmi Haskell che usano il metodo Sieve con grande velocità. Tuttavia la seguente funzione ricorsiva che ho scritto è molto lenta. Il codice è il seguentePerché questa funzione ricorsiva in Haskell è così lenta?

sieve' :: Integer -> Integer -> [Integer] 

sieve' n 1 = [2 .. n] 

sieve' n (k + 1) | [x | x <- sieve' n k, x == k + 1] == [] = sieve' n k 

    |otherwise = [x | x <- sieve' n k, x == k + 1 || not (mod x (k + 1) == 0)] 



sieve :: Integer -> [Integer] 

sieve n = sieve' n n 

Setaccio 20 impiega circa 2 minuti. Sieve 30 non ha ancora finito mentre sto scrivendo questa domanda.

Qualcuno può spiegare perché questa funzione ricorsiva sia così lenta. Grazie per tutto l'aiuto che potete fornire.

+0

Come massima autorità sul setaccio di Eratostene in Haskell dovresti dare un'occhiata all'articolo di Melissa O'Neill (http://lambda-the-ultimate.org/node/3127) nel Journal of Functional Programming (2009). Ci dovrebbero essere alcuni altri trucchi in esso. – ShiDoiSi

risposta

14

La seconda clausola della funzione sieve' sta effettuando la chiamata ricorsiva (sieve' n k) due volte, rendendo così l'algoritmo eseguito in tempo esponenziale.

Per risolvere questo problema è possibile associare il termine per qualche nome, garantendo in tal modo è valutata una volta:

sieve' n (k + 1) | [x | x <- rec, x == k + 1] == [] = rec 
    |otherwise = [x | x <- rec, x == k + 1 || not (mod x (k + 1) == 0)] 
    where 
    rec = sieve' n k 

Aggiornamento in risposta ad un commento chiedendo perché il compilatore non lo fa automaticamente:

Questo tipo di trasformazione, denominata CSE (eliminazione di sottoespressione comune), non è un'ottimizzazione in generale, ma piuttosto un compromesso tra l'utilizzo di tempo e spazio, quindi è meglio lasciare la decisione a un programmatore.

Googling per "CSE" rivela alcune discussioni interessanti, uno dei quali rappresenta il riferimento this very good example dal libro del 1987 di Simon Peyton Jones chiama "L'attuazione della programmazione funzionale lingue" (Oh mio, questo libro è quasi vecchia quanto me)

+1

Grazie, questo era esattamente il problema. Funziona molto più veloce ora. – user898033

+1

Trovo strano che il compilatore abbia perso questa ottimizzazione. –

+0

@ Jon, ho aggiornato la risposta per risolvere questo problema. – Rotsor

Problemi correlati