Comment améliorer l'efficacité avec une programmation fonctionnelle?

J'ai récemment parcouru le guide Learn You a Haskell for Great Good et comme pratique, je voulais résoudre le problème 5 du projet Euler avec, qui spécifie:

Quel est le plus petit nombre positif divisible par tous les nombres de 1 à 20?

J'ai décidé d'écrire d'abord une fonction déterminant si un nombre donné est divisible par ces nombres:

divisable x = all (\y -> x `mod` y == 0)[1..20]

Ensuite, j'ai calculé le plus petit en utilisant head:

sm = head [x | x <- [1..], divisable x]

Et enfin écrit la ligne pour afficher le résultat:

main = putStrLn $ show $ sm

Malheureusement, cela a pris environ 30 secondes pour terminer. Faire la même chose avec les nombres 1 à 10 donne un résultat presque immédiatement, mais là encore, le résultat est beaucoup plus petit que la solution pour 1 à 20.

Je l'ai résolu plus tôt en C et là, le résultat pour 1 à 20 a également été calculé presque instantanément. Cela m'amène à croire que je ne comprends pas comment interpréter ce problème pour Haskell. J'ai regardé les solutions des autres et j'ai trouvé ceci:

main = putStrLn $ show $ foldl1 lcm [1..20]

Assez juste, cela utilise une fonction intégrée, mais pourquoi le résultat final est-il tellement plus lent lorsque vous le faites vous-même? Les didacticiels vous expliquent comment utiliser Haskell, mais je ne vois pas beaucoup d'aide pour transformer des algorithmes en code rapide.

Vous devez d'abord vous assurer d'avoir un binaire optimisé, avant de penser que la langue est le problème. Lisez le chapitre Profilage et optimisation dans Real Wolrd Haskell. Il convient de noter que dans la plupart des cas, la nature de haut niveau de la langue vous coûte au moins une partie de la performance.

Cependant, notez que l'autre solution n'est pas plus rapide car elle utilise une fonction intégrée, mais simplement parce qu'elle utilise un algorithme beaucoup plus rapide : pour trouver le multiple le moins commun d'un ensemble de nombres, vous devez trouver seulement quelques GCD. Comparez cela avec votre solution, qui parcourt tous les nombres de 1 à foldl lcm [1..20]. Si vous essayez avec 30, la différence entre les temps d'exécution sera encore plus grande.

Jetez un œil aux complexités: votre algorithme a un O(ans*N)runtime, où ansest la réponse et Nle nombre jusqu'à lequel vous vérifiez la divisibilité (20 dans votre cas).
L'autre algorithme exécute Nfois lcm, cependant lcm(a,b) = a*b/gcd(a,b), et GCD a la complexité O(log(max(a,b))). Le deuxième algorithme est donc complexe O(N*log(ans)). Vous pouvez juger par vous-même ce qui est plus rapide.

Donc, pour résumer:
votre problème est votre algorithme, pas la langue.

Notez qu'il existe des langages spécialisés qui sont à la fois fonctionnels et axés sur les programmes mathématiques, comme Mathematica, qui pour les problèmes mathématiques est probablement plus rapide que presque tout le reste. Il a une bibliothèque de fonctions très optimisée, et il prend en charge le paradigme fonctionnel (certes, il prend également en charge la programmation impérative).

Ma première pensée a été que seuls les nombres divisibles par tous les nombres premiers <= 20 seront divisibles par tous les nombres inférieurs à 20. Il vous suffit donc de considérer les nombres qui sont des multiples de 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 . Une telle solution vérifie 1/9 699 690 autant de nombres que l'approche par force brute. Mais votre solution rapide Haskell fait mieux que cela.

Si je comprends la solution "Haskell rapide", elle utilise foldl1 pour appliquer la fonction lcm (multiple le moins commun) à la liste des nombres de 1 à 20. Elle appliquerait donc lcm 1 2, donnant 2. Puis lcm 2 3 donnant 6 Puis lcm 6 4 donne 12, et ainsi de suite. De cette façon, la fonction lcm n'est appelée que 19 fois pour donner votre réponse. En notation Big O, il s'agit d'opérations O (n-1) pour arriver à une solution.

Votre solution lente Haskell passe par les numéros 1-20 pour chaque numéro de 1 à votre solution. Si nous appelons la solution s, alors la solution de Haskell lente effectue des opérations O (s * n). Nous savons déjà que s dépasse 9 millions, ce qui explique probablement la lenteur. Même si tous les raccourcis et obtient une moyenne de la moitié de la liste des numéros 1-20, ce n'est toujours que O (s * n / 2).

L'appel headne vous évite pas de faire ces calculs, ils doivent être effectués afin de calculer la première solution.

Merci, c'était une question intéressante. Cela a vraiment étiré mes connaissances Haskell. Je ne pourrais pas y répondre du tout si je n'avais pas étudié les algorithmes l'automne dernier.

Je n'avais pas prévu initialement d'écrire une réponse. Mais on m'a dit après qu'un autre utilisateur a fait l'étrange affirmation que la simple multiplication des premiers nombres premiers était plus coûteuse en calcul que l'application répétée lcm. Voici donc les deux algorithmes et quelques repères:

Mon algorithme:

Algorithme de première génération, me donnant une liste infinie de nombres premiers.

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

Maintenant, en utilisant cette liste principale pour calculer le résultat pour certains N:

solvePrime :: Integer -> Integer
solvePrime n = foldl' (*) 1 $ takeWhile (<= n) (fromIntegral <$> primes)

Maintenant, l'autre algorithme basé sur lcm, qui est certes assez concis, principalement parce que j'ai implémenté la génération principale à partir de zéro (et que je n'ai pas utilisé l'algorithme de compréhension de liste super concise en raison de ses performances médiocres) alors qu'il lcmétait simplement importé de Prelude.

solveLcm :: Integer -> Integer
solveLcm n = foldl' (flip lcm) 1 [2 .. n]
-- Much slower without `flip` on `lcm`

Maintenant pour les benchmarks, le code que j'ai utilisé pour chacun était simple: ( -prof -fprof-auto -O2alors +RTS -p)

main :: IO ()
main = print $ solvePrime n
-- OR
main = print $ solveLcm n

Pour 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

Pour 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

Pour 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

je pense que les résultats parlent d'eux-mêmes.

Le profileur indique que la génération principale occupe un pourcentage de plus en plus petit du temps d'exécution à mesure que les naugmentations. Ce n'est donc pas le goulot d'étranglement, nous pouvons donc l'ignorer pour l'instant.

Cela signifie que nous comparons vraiment l'appel lcmoù un argument va de 1 à n, et l'autre va géométriquement de 1 à ans. Pour appeler *avec la même situation et l'avantage supplémentaire de pouvoir sauter tous les numéros non premiers (asymptotiquement gratuitement, en raison de la nature plus coûteuse de *).

Et il est bien connu que *c'est plus rapide que lcm, comme cela lcmnécessite des applications répétées de mod, et modest asymptotiquement plus lent ( O(n^2)vs ~O(n^1.5)).

Ainsi, les résultats ci-dessus et la brève analyse de l'algorithme devraient rendre très évident quel algorithme est le plus rapide.