Est-ce que GPars est vraiment si bien que ça ?

Depuis un moment, je vois apparaître GPars sur mon radar (ou plus exactement, dans des tweets envoyés par Guillaume Laforge).
Et comme les problèmes du project Euler sont souvent parallélisables, je me suis dit que c’était une bonne occasion de tester ça.
J’ai donc d’abord codé une version « standard » de la solution au problème 31, n’utilisant GPars que pour faire un bon gros collectParallel(…), avant d’écrire la version que voici qui fait non seulement du collectParallel, mais aussi du runForkJoin, ce qui est vraiment réjouissant.

 

 

Bon, j’aurais bien utilisé également Perf4J, pour remplacer mes bons vieux System.currentTimeMillis(), mais je n’ai pas trouvé comment. Et c’est bien dommage.
Cela dit GPars est de la belle ouvrage. Je me souviens encore avec émotion des ExecutorService et (encore longtemps avant), des infâmes Runnable à enquiller dans un Thread. A coté de ces horreurs, l’idée d’écrire GParsPool.withPool(2) {-> …} me remplit d’aise. Je dois toutefois légèrement nuancer mon propos. Comme cette question que j’ai posée sur StackOverflow le montre, l’API de GParsPool n’est pas totalement documentée sur le site de GPars (même si elle l’est en revanche sur le site de l’auteur, je dois d’ailleurs remercier encore ici sa réponse claire et rapide). Et ça, je dois bien l’avouer, c’est pénible.
Bon, arrétons-là.
J’ai quand même gagné un peu de temps d’exécution par rapport à la version initiale (particulièrement bourrine, je dois bien le reconnaître).
J’ai en revanche été nettement moins vite qu’une version totalement récursive du même code, ce qui est normal, puisqu’il y a bien plus de synchronisation. Ce que j’ai gagné, également, par rapport à la version récursive, c’est de l’empilement d’appel, puisque là, je fais beaucoup plus de passage de messages assynchrones, et beaucoup moins d’appels récursifs au même code.
La conclusion est quand même claire : GPars, au moins pour ce que j’en ai fait là (et ce que je vais en faire dans les problèmes suivants), c’est de la balle.
Publicités

pas si compliqué, tiens, …

Le problème 30, sous ses faux airs, n’est pas si compliqué que ça.
D’ailleurs, la solution est assez triviale :
[gist https://gist.github.com/829095]
Il faut d’abord disposer des puissances cinquièmes (histoire de ne pas les recalculer à chaque fois), puis penser à trouver une borne suffisamment grande. J’ai pris 1000000, mais c’est un pur hasard.
J’ai aussi essayé d’utiliser GPars pour optimiser un peu le temps de calcul, mais je dois bien reconnaître que ça n’a rien donné. D’ailleurs, si quelqu’un peut m’expliquer pourquoi mon code est aussi lent avec GPars que sans, je suis preneur (et oui, j’ai un double-coeur, donc théoriquement le temps de calcul de cette partie – la plus coûteuse – devrait être divisé par deux).
Je voulais aussi utiliser Perf4J (d’après la suggestion de Guillaume Laforge dans les castcodeurs), mais comme je n’ai trouvé aucun article n’expliquant comment l’intégrer dans mes scripts Groovy, j’ai préféré m’en passer.

Un peu de maths …

Bon, histoire de changer, je me suis dit (pendant que j’enquillais les longueurs de piscine) que le problème 28 était facilement abordable dés lors qu’on y réfléchissait un peu (comme c’est en fait le cas pour tous les problèmes, mais la plupart du temps je préfère ne pas y penser et coder comme un goret).
Regardons donc un peu les données dont nous disposons :
Si on extrait de la spirale initiale
21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

Les diagonales dans leur ordre d’écriture direct, on obtient ça (j’ai été un peu plus loin pour mieux valider mes hypothéses)

Ligne D1 D2 D3 D4 Somme
1 3 5 7 9 24
2 13 17 21 25 76
3 31 37 43 49 160
4 57 65 73 81 276
Est-ce qu’il y a là-dedans quoi que ce soit qui vous saute aux yeux ?

 

Personnellement, j’ai tout de suite remarqué deux choses
  1. A chaque ligne l’écart entre les différentes est constant. Il est égal à 2(n-1).
  2. Les valeurs de la dernière colonne sont des carrés de nombre impair. D’ailleurs, leurs valeurs correspondent précisément aux valeurs de la suite (2n-1). En passant, WolframAlpha, les jours on on veut faire un peu de maths facilement, c’est trop pratique.
Du coup, partant de ces deux constatations, je peux réécrire mes diagonales sous des formes plus comrpessées :

 

 

Du coup, la somme de ces diagonales peut s’écrire 4(2n-1)²-12(n-1). Enfin, la somme pour un n donné, hein. Une somme qui peut d’ailleurs se simplifier en 16n²-28n+16.
Ce qui me donne, vous l’admettrez, une façon rapide et efficace de calculer cette sommme : sum_(n=1)^3 (4(2n-1)²-12(n-1)))-3
Bon, je reconnais que l’écriture dans WolframAlpha est assez peu intuitive. Cela dit, ça vous donne une idée du total. Et le « -3 » à la fin permet de s’affranchir du fait que 1 est compté 4 fois dans la formule (une fois pour chaque diagonale).
Je pourrais donc faire tout ce calcul dans WolframAlpha, simplement en remplaçant ^3 par ^501. Mais je vais quand même poser le one-liner Groovy qui fait tout ça, toujours pour le fun.
Bon, c’est pas vraiment un one-liner (honte à moi), mais le code est quand même assez court :

 

 

 

Avec, je trouve, une utilisation sympa de Collection#sum(Object, Closure).

Same method shoot again !

On peut dire que j’ai fait preuve d’une vertu cardinale du développeur : la fainéantise. En effet, dans le code du problème 27, je me suis contenté de réutiliser ma méthode de calcul de nombres premiers, et le coup de Map#max(closure). Bon, le reste, c’est juste une grosse boucle.

 

 

Juste pour la postérité, vous vous rendez compte qu’avec cette formule, les 61 premiers résultats sont des nombres premiers ?
C’est fort, quand même non ?

Vous avez un problème ? …

Je ne vais pas reprendre encore une fois la fameuse phrase attribuée à Jamie Zawinsky, mais vous voyez l’idée.
Dans le problème 26, on doit trouver le plus long cycle dans l’écriture décimale de 1/n.
Et ça, c’est typiquement un boulot pour une expression régulière.
Pour ça, j’ai donc dégainé mon testeur d’expressions régulières Java préféré, j’ai forgé mon expression régulière (vous avez vu comme ça s’écrit bien en groovy une expression régulière ?)
Et pouf :

Bon, au passage, vous remarquerez l’appel à Map#max(Closure) qui est super méga cool et le for louche.

Le tout pour un temps d’exécution de … de … de 14.523 s
Court, hein !

Ah ben du coup ça défile

Vous croyez quoi, vous, que je vais rester sur un succès comme ça ?
Ce serait mal connaître la biochimie du cerveau, et surtout oublier que quoi qu’on en dise, l’esprit est un jouet pour le corps.
Donc, suite au problème 12, je me suis attaqué, muni de mes nouvelles connaissances, au problème 23, qui lui ressemble curieusement.
En effet, dès qu’on aborde les problèmes de diviseurs, on s’amuse à comapre le produit des diviseurs et leurs sommes, et on tombe sur les nombres parfaits, abondants et autres.
Et le sujet du problème 23, c’est pile poil ça. Heureusement, la solution est assez simple :

[gist https://gist.github.com/Riduidel/816638]

Vous remarquerez juste que, pour obtenir seulement les diviseurs propres, j’ai deux sales conditions dans le calcul des diviseurs. Il doit sans doute y avoir moyen d’améliorer ce point-là …

A part ça, rien de très groovyesque à signaler, je le crains.
Ah, au fait, le temps d’exécution est de 40 secondes à peu près. Je suis toujours aussi médiocre, pas de problème de ce côté-là.

You will be assimilated

Il suffisait évidement que j’en parle pour trouver la solution (certains ont appelé ça la technique du balayeur).
Bon, en fait, quand j’avais tenté ma première approche brute-force, j’avais utilisé des BigInteger (choix conservateur lié au fait que je ne savais pas quelle serait la taille du nombre) aux performances …. limitées. Depuis peu, comme je sais que les Long vont à peu prés jusqu’à beaucoup, je rechigne nettement moins à m’en servir. Et les calculs sont nettement plus rapides. Du coup, mon algorithme qui semblait ne pas converger en BigInteger met maintenant 4 minutes 30 pour terminer.
Vous allez évidement me dire que 4 minutes 30, c’est beaucoup.
C’est vrai. Surtout en comparaison de cet exemple qui met, lui, 54 secondes pour faire le même boulot. Seulement, si vous regardez mon code, là :

 

 

Vous constaterez que je stocke dans un TreeSet les diviseurs de mon nombre. C’est évidement beaucoup plus long. Seulement ça m’apporte un peu de confort au debug; Et personnellement, je préfère un programme 3 fois plus lent, mais 3 fois plus debuggable.

 

Vous constaterez également que j’ai essayé de créer un cache dans une TreeMap, mais aucun des essais que j’ai fait ne m’a montré d’amélioration des performances. Donc j’ai abandonné. Et si vous vous demandez pourquoi les performances n’ont pas été améliorées, c’est bien simple : ajouter une entrée dans un TreeSet ou une TreeMap prend un temps important, qui peut manger le gain de performance (qui dans ce cas est, il faut le reconnaître, assez faible). Si par exemple on remplace le TreeSet par un ArrayList (je laisse l’exercice à votre sagacité), on arrive à un temps d’exécution de … 4 minutes. Non significatif donc. Curieux quand même, en fait.

Resistance is futile !

Depuis deux jours, et après un bien long hiatus (et surtout suite à une discussion avec un collègue), j'ai replongé dans l'enfer de Project Euler. Un enfer, parce qu'il promet à mon cerveau assoiffé de récompenses la garantie de récompenses bien plus immédiates que celles que peut procurer le travail. En l'occurence, j'ai décidé de m'attaquer au problème 12. le problème 12, c'est le seul des 25 premiers qui me résiste. Et ça m'énerve.
Vous voulez savoir ce que ma dernière tentative (que je ne montrerai pas) a donné comme résultat ?

Oui, c'est décevant.
Surtout quand le programme a été lancé avec un JAVA_OPTS="-Xmx1200M" (la méthode recommandée pour changer la quantité de mémoire disponible dans du code Groovy).
Surtout quand je vois qu'ailleurs sur internet, d'autres ont trouvé la solution – en groovy – en moins d'une minute.
Surtout (enfin) quand je sais (toujours grâce à ce collègue) que la solution est 76576500. Et là, je ne ferais pas comme pour le Dropquest 2011, je n'irais pas aligner les réponses les unes derrière les autres.
Reprenons donc.
Le but est de trouver le premier nombre triangulaire ayant 500 diviseurs. Pour trouver ces diviseurs, je m'étais dit que la solution la plus simple était de décomposer le nombre en facteurs premiers. Seulement, pour ça, il me faut des gros paquets de nombres premiers, qui doivent être calculés dés le début. Donc, pas forcément une bonne idée.
Cela dit, je crois que je devrais réessayer la méthode initiale (qui consiste à faire de bêtes divisions par des nombres de 1 à racine de n) … en y ajoutant peut-être un peu de GPars pour rire … ou pas.

Vite fait

Bon, je crois que je vais me calmer un peu sur les problèmes d’Euler, parce que le problème 29 a vraiment été trivial à résoudre (et voilà que me revient le vocabulaire typique des prépas).

 

 

Pour le coup, je peux vraiment dire merci aux extensions mathématiques que Groovy amené à Java, et en particulier à la méthode pow, qui me retourne un BigDecimal que je retransforme aussi sec en BigInteger, parce que je sais ce que je veux 🙂
Cela dit, me voilà maintenant niveau 1, ce qui ne change rien à ma vie 🙂 mais me vaut les félicitations d’un ordinateur, quelque part dans le monde :

 

Bravo, Riduidel! Now that you have solved 25 problems you have achieved what 79.94% of members have failed to do and have advanced to level 1. Good luck as you continue.

Fibonacci, c’est trop facile

Les problèmes de fibonacci, c’est un peu comme les permutations : en Groovy, avec les BigInteger, les collections, et les bibliothèques dont on dispose, c’est un peu de la tarte à coder ! Du coup, le problème 25 ne me prend pas plus de 10 minutes à résoudre ! Enfin, 10 minutes de conception, et 1.57 s. d’exécution !

 

 

 

Et du coup, il ne me reste plus qu’un problème à résoudre avant de passer « niveau 1 » !