Fonction Haskell prenant beaucoup de temps à traiter

Question

Je fais la question 12 du projet euler où je dois trouver le premier numéro de triangle avec 501 diviseurs. Donc j'ai fouetté cela avec Haskell:

divS n = [ x | x <- [1..(n)], n `rem` x == 0 ] 
tri n = (n* (n+1)) `div` 2 
divL n = length (divS (tri n)) 
answer = [ x | x <- [100..] , 501 == (divL x)] 

La première fonction trouve les diviseurs d'un nombre.

La deuxième fonction calcule le nombre n-ième triangle

La troisième fonction trouve la longueur de la liste qui sont des diviseurs du nombre de triangle

La quatrième fonction doit renvoyer la valeur du numéro de triangle qui a 501 diviseurs.

Mais jusqu'à présent, cela fonctionne pendant un certain temps sans retourner un résultat. La réponse est-elle très grande ou ai-je besoin d'une sérieuse optimisation pour que cela fonctionne dans un délai réaliste?

Answer 1

Vous devez utiliser les propriétés de la fonction diviseur: http://en.wikipedia.org/wiki/Divisor_function

Notez que n et n + 1 sont toujours coprime, de sorte que vous pouvez obtenir d (n * (n + 1)/2) en multipliant valeurs précédemment calculées.

Answer 2

Quelques conseils d'optimisation:

• cocher pour entre 1 et diviseurs sqrt (n). Je vous promets que vous ne trouverez pas au-dessus de cette limite (sauf pour le numéro lui-même).
• ne pas créer une liste de diviseurs et de compter la liste, mais les compter directement.

Answer 3

Il est probablement plus rapide de factoriser le nombre, puis d'utiliser la factorisation pour trouver les diviseurs, que d'utiliser la division d'essai avec tous les nombres < = sqrt (n).

Le Sieve of Eratosthenes est un moyen classique de trouver des nombres premiers, qui peuvent être légèrement modifiés pour trouver le nombre de diviseurs de chaque nombre naturel. Au lieu de simplement marquer chaque non-premier comme "non premier", vous pouvez faire une liste de tous les nombres premiers divisant chaque nombre. Vous pouvez ensuite utiliser ces nombres premiers pour calculer l'ensemble complet des diviseurs, ou simplement le nombre d'entre eux, puisque c'est tout ce dont vous avez besoin. Une autre variante consisterait à marquer non seulement des multiples de nombres premiers, mais des multiples de tous les nombres naturels. Ensuite, vous pouvez simplement utiliser un compteur pour garder une trace du nombre de diviseurs pour chaque numéro.

Vous pouvez également vouloir vérifier The Genuine Sieve of Eratosthenes, ce qui explique pourquoi la division d'essai est beaucoup plus lente que le vrai tamis. Enfin, vous devriez examiner attentivement les différents types de réseaux dans Haskell. Je pense qu'il est probablement plus facile d'utiliser la monade ST pour implémenter le tamis, mais il peut être possible d'atteindre la complexité correcte en utilisant accumArray, si vous pouvez vous assurer que votre fonction de mise à jour est stricte. Je n'ai jamais réussi à faire fonctionner cela, alors vous êtes seul ici.

Answer 4

Si vous utilisiez C à la place de Haskell, votre fonction prendrait beaucoup de temps. Pour le rendre plus rapide, vous devrez améliorer l'algorithme en utilisant les suggestions des réponses ci-dessus.Je suggère de changer le titre et la description de la question en conséquence. Après cela, je vais supprimer ce commentaire.

Si vous le souhaitez, je peux gâcher le problème en partageant ma solution.

Pour l'instant, je vais vous donner mon code de niveau supérieur:

main = 
    print . 
    head . filter ((> 500) . length . divisors) . 
    map (figureNum 3) $ [1..] 

L'amélioration algorithmiques réside dans la fonction divisors. Vous pouvez encore l'améliorer en utilisant la suggestion de rawicki, mais cela prend déjà moins de 100ms.