Existe-t-il un moyen d'optimiser ce programme dans Haskell?

Question

Je fais le projet euler question 224. Et fouetté cette compréhension de liste dans Haskell:

prob39 = length [ d | d <- [1..75000000], c <- [1..37500000], b <-[1..c], a <- [1..b], a+b+c == d, a^2 + b^2 == (c^2 -1)] 

Je l'ai compilé avec GHC et il a été en cours d'exécution avec la priorité du noyau supérieur à la moyenne pendant plus d'une heure sans retourner un résultat. Que puis-je faire pour optimiser cette solution? Il semble que je m'améliore à trouver des solutions de force brute d'une manière naïve. Y a-t-il quelque chose que je puisse faire à ce sujet?

EDIT: Je ne comprends pas non plus la définition de 'longueur intégrale', cela signifie-t-il simplement que la longueur du côté a une grandeur qui tombe dans l'ensemble positif d'entiers, ie: 1,2,3,4,5. ..?

Answer 1

Mon Haskell n'est pas génial, mais je pense que ça va être n^5 comme écrit.

On dirait que vous dites pour chaque n de 1 à 75 millions, vérifiez chaque triangle "à peine obtus" avec un périmètre inférieur ou égal à 75 millions pour voir s'il a le périmètre n.

De même, je ne suis pas certain si la compréhension des listes est assez intelligente pour arrêter de regarder lorsque la valeur actuelle de c^2 -1 est supérieure à^2 + b^2.

Un refactoring simple devrait être

prob39 = length [ (a, b, c) | c <- [1..37500000], b <-[1..c], a <- [1..b], a^2 + b^2 == (c^2 -1), (a + b + c) <= 75000000] 

Vous pouvez faire mieux, mais cela devrait être littéralement 75 millions de fois plus rapide.

Moins sûr de ce refactoring, mais il devrait aussi accélérer les choses considérablement:

prob39 = length [ (a, b, c) | a <- [1..25000000], b <-[a..(75000000 - 2*a)], c <- [b..(75000000 - a - b)], a^2 + b^2 == (c^2 -1)] 

Syntaxe ne peut pas être 100% là-bas. L'idée est que a ne peut être que de 1 à 25 millions (puisque < = b= c et a + b + c= 75 millions). b peut seulement être compris entre a et mi-chemin de a à 75 millions (puisque b < = c) et c ne peut être que de b à 75 millions - (a + b), sinon le périmètre dépasserait 75 millions.

Modifier: mise à jour des extraits de code, il y avait quelques bugs là-dedans.

Une autre suggestion rapide, vous pouvez remplacer c < - [b .. (75000000 - a - b)] avec quelque chose le long des lignes de c < - [b..min ((75000000 - a - b), sqrt (a a + b b) + 1)]. Il n'est pas nécessaire de vérifier les valeurs de c supérieures au plafond de la racine carrée de (a^2 + b^2). Je ne me souviens pas si ce sont les noms des fonctions min/sqrt correctes dans haskell cependant.

Obtenir OCD sur celui-ci, j'ai quelques autres suggestions.

1) vous pouvez définir la borne supérieure sur b comme étant la borne minimale actuelle et un^2 * 2 + 1. Ceci est basé sur le principe que (x + 1)^2 - x^2 = 2x + 1. b ne peut pas être plus grand que a que l'on puisse garantir que (a^2) + (b^2) < (b + 1)^2.

2) fixer la borne inférieure de c comme étant au maximum b + 1 et plancher (sqrt (a^2 + b^2) - 1). Tout comme la limite supérieure sur C, pas besoin de tester des valeurs qui ne pourraient pas être correctes.