Inizialmente non avevo intenzione di scrivere una risposta. Ma mi è stato detto dopo che un altro utente ha fatto la strana affermazione che semplicemente moltiplicando i primi numeri primi era più dispendioso dal punto di vista computazionale, quindi si applicava ripetutamente lcm . Quindi ecco i due algoritmi e alcuni benchmark:
Il mio algoritmo:
Algoritmo di prima generazione, che mi dà una lista infinita di numeri primi.
isPrime :: Int -> Bool
isPrime 1 = False
isPrime n = all ((/= 0) . mod n) (takeWhile ((<= n) . (^ 2)) primes)
toPrime :: Int -> Int
toPrime n
| isPrime n = n
| otherwise = toPrime (n + 1)
primes :: [Int]
primes = 2 : map (toPrime . (+ 1)) primes
Ora usando quell'elenco principale per calcolare il risultato per un po 'di N :
solvePrime :: Integer -> Integer
solvePrime n = foldl' (*) 1 $ takeWhile (<= n) (fromIntegral <$> primes)
Ora l'altro algoritmo basato su lcm, che è certamente abbastanza conciso, principalmente perché ho implementato la generazione primaria da zero (e non ho usato l'algoritmo di comprensione degli elenchi super conciso a causa delle sue scarse prestazioni) mentre lcm è stato semplicemente importato dal Prelude .
solveLcm :: Integer -> Integer
solveLcm n = foldl' (flip lcm) 1 [2 .. n]
-- Much slower without 'flip' on 'lcm'
Ora per i benchmark, il codice che ho usato per ciascuno era semplice: ( -prof -fprof-auto -O2 poi +RTS -p )
main :: IO ()
main = print $ solvePrime n
-- OR
main = print $ solveLcm n
Per n = 100,000 , solvePrime :
total time = 0.04 secs
total alloc = 108,327,328 bytes
vs solveLcm :
total time = 0.12 secs
total alloc = 117,842,152 bytes
Per n = 1,000,000 , solvePrime :
total time = 1.21 secs
total alloc = 8,846,768,456 bytes
vs solveLcm :
total time = 9.10 secs
total alloc = 8,963,508,416 bytes
Per n = 3,000,000 , solvePrime :
total time = 8.99 secs
total alloc = 74,790,070,088 bytes
vs solveLcm :
total time = 86.42 secs
total alloc = 75,145,302,416 bytes
Penso che i risultati parlano da soli.
Il profiler indica che la prima generazione occupa una percentuale sempre più piccola del tempo di esecuzione con incrementi di n . Quindi non è il collo di bottiglia, quindi possiamo ignorarlo per ora.
Questo significa che stiamo davvero confrontando chiamando lcm dove un argomento va da 1 a n , e l'altro va geometricamente da 1 a ans . Chiamare * con la stessa situazione e il vantaggio aggiuntivo di saltare tutti i numeri non primi (asintoticamente gratis, a causa della natura più costosa di * ).
Ed è risaputo che * è più veloce di lcm , in quanto lcm richiede applicazioni ripetute di mod e mod è asintoticamente più lento ( O(n^2) rispetto a ~O(n^1.5) ).
Quindi i risultati sopra riportati e la breve analisi dell'algoritmo dovrebbero rendere molto evidente quale algoritmo è più veloce.