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.
Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s