Discussion :

[Exoss]

Bonjour! Je ne suis pas débutant en Java, mais je ne connais pas très bien les structures de données et l'algorithmie.

Je me demandais s'il est possible de faire quelques optimisations sur le bout de code qui suivra plus tard. Je dois d'abord vous expliquer ce que fait mon algorithme.

Il s'agit d'une classe qui me permet de tester une particularité mathématique. Le test est simple. Prenez n'importe quel nombre positif et mettez-le au carré. Ex. : 1078 au carré = 1162084. Prenez les quatre premiers chiffres et soustrayez-les par les trois derniers. Ex. : 1162 - 084. Cela vous donne le nombre de départ, 1078. Il existe plusieurs autres nombres qui ont cette particularité.

Mon code maintenant. La fonction isNombreLacroix() me permet de trouver mes nombres (appelés Lacroix, du nom de son découvreur). J'y ai inclus un exemple d'utilisation de la fonction dans le Main. Comme vous pouvez le voir j'utilise intensivement les string. Y aurait-il une manière d'optimiser le code pour le rendre plus rapide?

Dans mon application générale je suis maintenant rendu à calculer dans les 13 chiffres, et cela prend pas mal de temps . Je me suis fait une plateforme de calculs distribués. Comme cela je peux utiliser mes quatre ordinateurs pour aller plus vite, mais c'est insuffisant. Je fais à peu près 27 millions de calculs par minutes avec mon parc informatique.

J'espère que ma question est claire .

Merci de votre aide!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
package utilitaire;
 
import java.math.BigInteger;
 
/**
 * @author Philippe Bourdages
 */
public class NombreLacroix {
 
    private static BigInteger number;
    private static String numberSquared;
    private static Integer qtyChar;
    private static Integer qtyCharSquared;
    private static BigInteger nbrToSubtract;
    private static BigInteger nbrSubtracting;
    private static BigInteger result;
    private static Boolean valid;
 
    /**
     * Validation d'un nombre Lacroix.
     *
     * @return Boolean
     * @param arg BigInteger
     */
    public static synchronized boolean isNombreLacroix(final BigInteger arg) {
        number = arg;
        valid = false;
 
        numberSquared = number.pow(2).toString();
        qtyChar = number.toString().length();
        qtyCharSquared = numberSquared.length();
 
        nbrToSubtract = new BigInteger(numberSquared.substring(0, qtyChar));
        nbrSubtracting = new BigInteger(numberSquared.substring(qtyChar));
 
        /*Élimination des nombres lacroix qui résultent d'une
        soustractions par zéro et un. Ex: 1001 et 1000*/
        if (nbrSubtracting.compareTo(BigInteger.ONE) > 0) {
 
            result = nbrToSubtract.subtract(nbrSubtracting);
 
            /*Comparaison du nombre de départ et du nombre soustrait.
            S'ils sont égaux, alors c'est un nombe lacroix*/
            if (number.compareTo(result) == 0) {
                valid = true;
            }
 
        }
 
        return valid;
    }
 
    /*
     * Exemple d'utilisation de la classe...
     */
    public static void main(final String[] args) {
        long start = System.nanoTime();
 
        BigInteger i, iAdd, iMax;
        iAdd = new BigInteger("1");
        iMax = new BigInteger("2000000");
 
        for (i = new BigInteger("4"); i.compareTo(iMax) <= 0; i = i.add(iAdd)) {
 
            if (NombreLacroix.isNombreLacroix(i)) {
                System.out.println(i);
            }
        }
 
        long end = System.nanoTime();
        long elapsedNanoSeconds = end - start;
        System.out.println("time elapsed:" + elapsedNanoSeconds);
    }
}

[darkxan]

L'algorithme en lui même semble optimisé par contre après on descendre aux optimisations du point de vue langage.

Déjà, retire moi cet horrible synchronized, il te fait perdre pas mal de temps pour strictement rien. De plus, tu travailles avec des BigInteger or il serait préférable de travailler soit entièrement avec des long ou avec une combinaison entre des long et des int.

L'avantage aussi de travailler avec des types primitifs, c'est que tu ne perds pas de temps pour créer les objets et que les opérations sont bien plus rapides. Surtout que dans ton cas la précision des long et largement suffisant pour contenir le carré de ton nombre de départ.

Ou alors travailler avec Long et Integer. Peut être que les opérations sur les objets sont plus optimisés que ce que tu pourrais faire en Java sur les types primitifs.

Note : qtyCharSquared n'est jamais utilisé.

Peut être que quelque chose comme ça serait plus efficace. A voir si ce n'est pas encore avec number comme int avec des cast :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
long numberSquared;
int nbChar;
long nbrToSubtract;
long nbrSubtracting;
long result;
 
long number = 4;
while(true) {
	numberSquared = number * number;
	nbChar = number.toString().length();
 
	nbrToSubtract = Long.parseLong(numberSquared.substring(0, nbChar));
	nbrSubtracting = Long.parseLong(numberSquared.substring(nbChar));
 
	result = nbrToSubtract - nbrSubtracting;
 
	if (number == result) {
		System.out.println(number);
	}
 
	number++;
}

[Exoss]

Quelques précisions :

• Je dois utiliser les BigInteger, car j'ai déjà dépassé la limite des Long. Le maximum des Long est 2^63, soit un nombre à 19 chiffres. Actuellement, je suis dans les nombres à 13 chiffres. Au carré, cela donne 25 chiffres. Je crois donc que l'utilisation des BigInteger est justifiée.
• J'ai mis la classe en synchronized, car je pensais créer plusieurs unités de calculs avec chacun un thread. Cependant, je ne suis pas sûr que cela m'apporte un gain quelconque. Oui, non?

Que puis-je faire pour améliorer les performances au niveau du langage?

Edit :
C'est vrai que qtyCharSquared ne sert à rien. J'ai supprimé deux structures if , avant de publier mon algorithme, qui utilisaient cette variable.

[darkxan]

Peut être que tes nombres font 25 chiffres au carré mais vu qu'ensuite tu travailles sur la moitié du nombre, rien ne t'empêche de travailler avec des long.

L'utilisation de synchronized ici est stupide. Si il y a avait plusieurs thread alors il serait bloqué à cause du synchronized, de plus rien n'empêcherait des threads de travailler sur la vérification de deux nombres distincts et donc probablement deux instances différentes de la classe. Si tu fais le travail sur des machines distinctes, il suffit de découper l'espace des données et dans un attribuer un à chaque machine. L'utilisation du mot clé synchronized est très couteux pour l'appel d'une méthode.

Pour les autres améliorations, regarde le code que j'ai proposé. J'ai enlevé l'appel de méthode, j'ai enlevé la comparaison dans le for pour le remplacer par un while, j'ai supprimé la variable inutile et remplacer tous par des long. Au vu de ton message précédent, il te suffit simplement de mettre le nombre au carré en BigInteger et laisser le reste en long.

[Exoss]

Je suis bien d'accord pour changer mon nombre de départ en long. De toute manière, quand j'aurai un nombre à 19 chiffres au carré, ça va prendre des lustres avant d'arriver à calculer les nombres à 20 chiffres.

J'ai des doutes pour ce qui est de l'appel d'une fonction avec le mot clé synchronized. Je n'ai pas vu d'amélioration notable. Selon les moyennes que j'ai calculées, il y avait une différence de 0.005 %. Pourtant, en théorie c'est bien évident que cela consomme plus...

Est-ce possible d'avoir de meilleures performances avec diverses unités de calculs en thread? Comment implanterais-tu ceci? J'ai une certaine idée, mais j'aimerais savoir la tienne.

Pour ce qui est du découpage des données, c'est déjà fait. C'est dans une autre classe cependant. Dans mon application serveur pour être plus précis...

P.S. Je ne suis pas sûr que le while est approprié si je veux découper mes données... C'est à dire se donner une zone de calcul ex. : calculer de 2 000 000 à 4 000 000 pour un ordinateur, et distribuer à un autre la zone de 4 000 000 à 6 000 000.

[darkxan]

Ce qui est important pour les long, c'est de travailler avec eux lorsque tu as découpé ton nombre en deux. En faite, tu ne travailles avec le BigInteger uniquement pour mettre le nombre au carré.

Le synchronized ne consomme pas énormément je crois que c'est 4 cycles pour un appel de méthode contre 700 pour un appel en synchronized. Sur nos machines ça ne donne pas un changement immense.

Pour les threads, la seule chose possible serait de lancer plusieurs fois le calcul avec des nombres distincts dans chaque Thread. Si ton pc est multi coeur alors peut être que ça améliorera les performances mais ce n'est pas dit. Tu peux faire le test en découpant la plage en deux avec deux Threads.