Pour le temps de faire une petite pause dans ma journée, je vous propose une solution à un problème simple. Il s’agit de programmer une méthode qui prend un entier N en entrée. Si N est un multiple de 3, ça renvoie « blanc ». Si N est un multiple de 5, ça renvoie « noir ». Si N est un multiple de 3 et de 5, ça renvoie « gris ». Enfin, dans tous les autres cas, ça renvoie trois petits points.
Pour faire bien, je commence par faire des tests unitaires en prennant des cas simples, pour la jouer à la 3T :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | public class BlancNoirGrisTest { private BlancNoirGris bng; @Before public void before() { bng = new BlancNoirGris(); } // @Test // public void testTrue() { // Assert.assertTrue(true); // } @Test public void testMultiple3() { // final int number = 3; final String expected = "noir"; doTest(number, expected); } @Test public void testMultiple6() { // final int number = 6; final String expected = "noir"; doTest(number, expected); } @Test public void testMultiple5() { // final int number = 5; final String expected = "blanc"; doTest(number, expected); } @Test public void testMultiple10() { // final int number = 10; final String expected = "blanc"; doTest(number, expected); } @Test public void testMultiple15() { // final int number = 15; final String expected = "gris"; doTest(number, expected); } @Test public void testMultiple45() { // final int number = 45; final String expected = "gris"; doTest(number, expected); } @Test public void testMultiple1() { // final int number = 1; final String expected = "..."; doTest(number, expected); } @Test public void testMultiple7() { // final int number = 7; final String expected = "..."; doTest(number, expected); } private void doTest(final int number, final String expected) { // final String color = bng.calcul(number); // Assert.assertEquals(expected, color); } } |
Et puis je code ma fonction. Au passage, pour qu’un entier soit à la fois un multiple des nombres premiers 3 et de 5, il faut donc que ce soit aussi un multiple de 15. Voici donc à quoi j’arrive, après quatre itérations triviales :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | public class BlancNoirGris { public String calcul(final int number) { if (number % 15 == 0) { return "gris"; } if (number % 3 == 0) { return "noir"; } if (number % 5 == 0) { return "blanc"; } return "..."; } } |
Reste à trouver comment optimiser ce code.
Je me suis dis, pour commencer, qu’il faut garder les conditions de sortie en premier. Ensuite, il y aura plus souvent des multiples de 3 que des multiples de 5, pour des tirs uniformes. Du coup, il vaut mieux tester 3 en premier. Pour autant, il faut encore tester 15 avant de tester 5, sinon on sort trop tôt. Et là je vais mettre le test de 15 dans le test de 3 et ne tester finallement que le modulo de 5, qui sera plus rapide que celui de 15. Et je fais ça en if simplifié :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | public class BlancNoirGris { public String calcul(final int number) { // if (number % 15 == 0) { // return "gris"; // } if (number % 3 == 0) { // return "noir"; return (number % 5 != 0) ? "noir" : "gris"; } if (number % 5 == 0) { return "blanc"; } return "..."; } } |
Est ce que ça permet de gagner quelque chose ? de significatif ?… Notez au passage que je teste la différence avec zéro, et non l’égalité.
Je reprend, ici, je vais donc toujours lancer un modulo de 3 et un de 5, quoi s’il arrive. Est ce que ça coûte plus cher de mettre le résultat du module de 5 dans une variable que de le calculer. En gros, est ce que c’est plus rapide de faire le code suivant :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | package com.ice.fun; public class BlancNoirGris { public String calcul(final int number) { final boolean mult5 = number % 5 == 0; if (number % 3 == 0) { // return (number % 5 != 0) ? "noir" : "gris"; return (!mult5) ? "noir" : "gris"; } // if (number % 5 == 0) { if (mult5) { return "blanc"; } return "..."; } } |
Pour savoir sans ambiguité quelle version est la plus rapide, j’ai pris des mesures sur les N premiers entiers à l’aide du Stop Watch de Guava.
Voici ce que ça donne. Les valeurs sont exprimées en nano secondes :
N = 100
t1 = 10 694ns
t2 = 8 127ns
t3 = 8 982ns
Les résultats sont donc très proches. Notez au passage que je fais une première passe à vide, faute de quoi le temps (t1) est biaisé. Est ce que Java garde en mémoire le résultat des modulos utilisés ? Je ne sais pas trop… Je crois qu’il y a effectivement une piste.
N = 10 000
t1 = 988 489ns
t2 = 714 313ns
t3 = 916 203ns
N = 1 000 000
t1 = 2 713 535ns
t2 = 2 388 459ns
t3 = 2 957 343ns
N = 1 000 000 000
t1 = 755 045 318ns, soit 755ms
t2 = 738 176 833ns, soit 738ms
t3 = 746 127 952ns, soit 746ms
J’ai bien entendu lancé la moulinette plusieurs fois, en utilisant les différents algo dans des ordres différents, pour vérifier mes résultats. On constate que la méthode deux, est finallement plus rapide que la troisième. L’utilisation d’une variable intermédiaire n’est donc pas intéressante, dans ce cas, en Java 6. Dans tous les cas, pour un milliard de passes, on gagne au mieux 17 millisecondes par rapport à l’algo naïf, soit bien plus qu’il en aura fallu pour lire ou écrire ce billet…