IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Java Discussion :

Est-ce possible d'optimiser davantage cet algorithme?


Sujet :

Langage Java

  1. #21
    Membre averti
    Profil pro
    Développeur Java
    Inscrit en
    Novembre 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Novembre 2007
    Messages : 301
    Points : 368
    Points
    368
    Par défaut
    Si si ça marche, c'est juste que tu as fait une erreur.

    Quand j'ai mis : Si b0(i) > 10^5, il était pour moi évidement que le 5 correspondait à la longeur du nombre. Il fallait donc utiliser qtyChar (quoi doit évidement être modifier pour chaque chaque puissance de 10)*.

    De plus, il y a plein d'optimisation possible au lieu d'utiliser les strings pour enlever le 1er chiffre, il serait peut être mieux de simplement enlever 10^qtyChar.

    * Je pense que le mieux pour gérer cela serait deux faire deux boucles imbriqués pour éviter le recalcul de qtyChar à chaque fois.

  2. #22
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    27
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 27
    Points : 7
    Points
    7
    Par défaut
    Je te ferai remarquer que ce n'est pas moi qui ai fait une erreur, mais toi en réalité! Si tes variables avaient été claires depuis le début moi j'aurais bien retranscrit l'algorithme... et par conséquent, déplacer la création de la variable qtyChar dans la boucle.

    Que dirais-tu de me montrer le code qui fonctionne?

  3. #23
    Membre averti
    Profil pro
    Développeur Java
    Inscrit en
    Novembre 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Novembre 2007
    Messages : 301
    Points : 368
    Points
    368
    Par défaut
    Ce n'est pas moi qui cherche à optimiser cet algorithme. Je t'ai donné rapidement (je te le concède) un nouvel algorithme qui pourrait être plus rapide. Après, c'est à toi de le comprendre et de non pas simplement le recopier. De plus, cela te permettra de l'optimiser.

    Si tu as des questions sur celui-ci, je serai heureux d'y répondre.

    Bonne chance. Tiens moi au courant.

  4. #24
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    27
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 27
    Points : 7
    Points
    7
    Par défaut
    D'accord, en voilà une. Qu'est-ce qui te semble être différent entre l'algorithme que j'ai implanté et le tien, à part le fameux qtyChar(que de toute manière j'ai retesté)?

  5. #25
    Membre averti
    Profil pro
    Développeur Java
    Inscrit en
    Novembre 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Novembre 2007
    Messages : 301
    Points : 368
    Points
    368
    Par défaut
    C'est pas vraiment une question sur l'algo., c'est une question sur ton implémentation ça. Je l'ai quand même lu et il ne semble pas qu'il y ait d'erreur mais il n'est pas facile à lire.

    Si ça ne marche pas essaie pour voir sur une plage du style : 10000 à 99999.

    EDIT : Comme je m'en doutais avec ma phrase précédente, l'algorithme ne marche plus lorsque le nombre change de dizaine. J'y est remédié en refaisant le calcul de R(i) à chaque nouvelle dizaine.

    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
    public void test() {
    	long lMin = 10;
    	int iLongeurMax = 5;
     
    	int ilongeur = (int) Math.log10(lMin) + 1;
     
    	long lNombre = lMin;
    	for(int i = ilongeur; i <= iLongeurMax; i ++) {
    		long lNombreAuCarre = lNombre * lNombre;
    		String strNombreAuCarre = String.valueOf(lNombreAuCarre);
    		ilongeur = (int) Math.log10(lNombre) + 1;
     
    		long lb1 = Long.parseLong(strNombreAuCarre.substring(0, ilongeur));
    		long lb0 = Long.parseLong(strNombreAuCarre.substring(ilongeur));
     
    		long lResultat = lb1 - lb0;
     
    		long lMax = (long) Math.pow(10, i);
    		long val = (long) Math.pow(10, i-1);
    		lNombre++;
    		while(lNombre < lMax) {
    			long lTmp = 2 * lNombre - 1;
    			String strTmp = String.valueOf(lTmp);
     
    			lb0 = lb0 + Long.parseLong(strTmp.substring(1));
    			lb1 = lb1 + Long.parseLong(strTmp.substring(0, 1));
     
    			if (lb0 > val) {
    				lb0 = lb0 - val;
    				lb1++;
    			}
     
    			lResultat = lb1 - lb0;
     
    			if(lResultat == lNombre) {
    				System.out.println(lNombre);
    			}
     
    			lNombre++;
    		}
    	}
    }

  6. #26
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    27
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 27
    Points : 7
    Points
    7
    Par défaut
    Bonjour!

    Merci bien pour cette implémentation de ton algorithme. Maintenant, il y a une énorme différence dans la rapidité des calculs! À peu près 100 millions de calculs par minutes avec mon ordinateur double coeurs.

    J'ai dû retravailler un peu le code pour obtenir quelque chose d'un peu plus approprié à mes besoins, mais ce ne fût pas un gros changement! Par exemple, je dois absolument être capable de spécifier un nombre de départ et un nombre final. Cela me permet de découper les calculs et de séparer la tâche sur plusieurs ordinateurs. Aussi, j'ai remarqué qu'il y avait un problème avec ton algorithme. Si le premier nombre de ta boucle est valide, l'algorithme ne le recensera pas. Et d'autres modifications... C'est encore un peu difficile à lire par contre...


    Voici ce que cela donne :
    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
            long nbrStart = 2000000;//valeur d'exemple
            long nbrFinish = 4000000;//valeur d'exemple
     
            int nbrDigits = (int) Math.log10(nbrStart) + 1;
            int nbrDigitsMax = (int) Math.log10(nbrFinish) + 1;
     
            long number = nbrStart;
            for (int i = nbrDigits; i <= nbrDigitsMax; i++) {
                long nbrSquared = number * number;
                String nbrSquaredStr = String.valueOf(nbrSquared);
                nbrDigits = (int) Math.log10(number) + 1;
     
                long b1 = Long.parseLong(nbrSquaredStr.substring(0, nbrDigits));
                long b0 = Long.parseLong(nbrSquaredStr.substring(nbrDigits));
     
                long result = b1 - b0;
     
                long nbrMaxE = (long) Math.pow(10, i);
                long adjust = (long) Math.pow(10, i - 1);
     
                number++;
     
                while (number < nbrMaxE && number <= nbrFinish + 1) {
                    if(result == number - 1 && b0 != 0) {
                        System.out.println(number - 1);
                    }
     
                    long newCalc = 2 * number - 1;
                    String newCalcStr = String.valueOf(newCalc);
     
                    b0 = b0 + Long.parseLong(newCalcStr.substring(1));
                    b1 = b1 + Long.parseLong(newCalcStr.substring(0, 1));
     
                    if(b0 > adjust) {
                        b0 = b0 - adjust;
                        b1++;
                    }
     
                    result = b1 - b0;
     
                    number++;
                }
            }

  7. #27
    Membre averti
    Profil pro
    Développeur Java
    Inscrit en
    Novembre 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Novembre 2007
    Messages : 301
    Points : 368
    Points
    368
    Par défaut
    C'est vrai, j'avais eu un peu la flemme de faire une version parfaite.

    Pour ta deuxième boucle, je n'aurais pas géré cela comme ça en faite. J'aurais fais un min entre le nbrFinish et nbrMaxE avant le while, cela évite de faire deux tests pour chaque boucle.

    Par contre, j'avais oublié de précisé que pour qu'elle marche avec les grands nombre, il faut évidement changer le calcul qui se fait à chaque dizaine et mettre un BigInteger au lieu d'un long. Sinon tu vas dépasser le plus grand long.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    long nbrSquared = number * number;
    Sinon ça me semble bien.

  8. #28
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    27
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 27
    Points : 7
    Points
    7
    Par défaut
    Faire un min (minimum j'imagine) avec nbrMaxE et nbrFinish ?

    Pour ce qui est du BigInteger, je l'ai remis. Cependant, je ne crois pas calculer autant de nombres finalement... C'est un peu démesuré comme quête avec les seuls ordinateurs que je possède.

    J'ai remarqué qu'après un certain nombre d'heures les performances diminuent. Je passe de 200 millions de calculs à 104 millions. À quoi pensez-vous que cela peut-être dû? Généralement, je résous le problème en killan mes thread et en les repartant. Une autre question. Est-ce qu'un stringBuilder pourrait être envisageable pour réduire le nombre d'objets string?

    J'ai plutôt hâte de commencer mon programme en génie logiciel en septembre... Être autodidacte c'est parfois dur. Le manque de certitudes et d'encadrement ! Une chance qu'il existe de belles communautés comme celle-ci .

  9. #29
    Membre expert
    Avatar de ®om
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    2 815
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 2 815
    Points : 3 080
    Points
    3 080
    Par défaut
    À partir de ton post #26, j'ai modifié un peu, et j'obtiens un gain de 76% (donc 4 fois plus rapide).

    Celui du post 26 est l'algo1.
    Le mien est l'algo2.

    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
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    public class LaCroix {
    	public static void main(String[] args) {
    		final long START = 1000000;
    		final long END = 8000000;
     
    		long t = System.nanoTime();
    		algo1(START, END);
    		long algo1Time = System.nanoTime() - t;
    		System.out.println("t1 = " + algo1Time);
     
    		t = System.nanoTime();
    		algo2(START, END);
    		long algo2Time = System.nanoTime() - t;
    		System.out.println("t2 = " + algo2Time);
     
    		System.out.println("ratio = " + (double)algo2Time / algo1Time);
    	}
     
    	public static void algo1(long nbrStart, long nbrFinish) {
    		int nbrDigits = (int) Math.log10(nbrStart) + 1;
    		int nbrDigitsMax = (int) Math.log10(nbrFinish) + 1;
     
    		long number = nbrStart;
    		for (int i = nbrDigits; i <= nbrDigitsMax; i++) {
    			long nbrSquared = number * number;
    			String nbrSquaredStr = String.valueOf(nbrSquared);
    			nbrDigits = (int) Math.log10(number) + 1;
     
    			long b1 = Long.parseLong(nbrSquaredStr.substring(0, nbrDigits));
    			long b0 = Long.parseLong(nbrSquaredStr.substring(nbrDigits));
     
    			long result = b1 - b0;
     
    			long nbrMaxE = (long) Math.pow(10, i);
    			long adjust = (long) Math.pow(10, i - 1);
     
    			number++;
     
    			while (number < nbrMaxE && number <= nbrFinish + 1) {
    				if (result == number - 1 && b0 != 0) {
    					 System.out.println(number - 1);
    				}
     
    				long newCalc = 2 * number - 1;
    				String newCalcStr = String.valueOf(newCalc);
     
    				b0 = b0 + Long.parseLong(newCalcStr.substring(1));
    				b1 = b1 + Long.parseLong(newCalcStr.substring(0, 1));
     
    				if (b0 > adjust) {
    					b0 = b0 - adjust;
    					b1++;
    				}
     
    				result = b1 - b0;
     
    				number++;
    			}
    		}
    	}
     
    	public static void algo2(long nbrStart, long nbrFinish) {
    		final long[] powers10 = powers10();
     
    		int nbrDigits = (int) Math.log10(nbrStart) + 1;
    		int nbrDigitsMax = (int) Math.log10(nbrFinish) + 1;
    		long divisor;
    		long number = nbrStart;
    		for (int i = nbrDigits; i <= nbrDigitsMax; i++) {
    			long nbrSquared = number * number;
    			nbrDigits = (int) Math.log10(number) + 1;
    			divisor = powers10[nbrDigits-1];
     
    			long b1 = nbrSquared / divisor;
    			long b0 = nbrSquared % divisor;
    			long result = b1 - b0;
     
    			long nbrMaxE = powers10[i];
    			long adjust = powers10[i];
     
    			number++;
     
    			while (number < nbrMaxE && number <= nbrFinish + 1) {
    				if (result == number - 1 && b0 != 0) {
    					 System.out.println(number - 1);
    				}
     
    				long newCalc = 2 * number - 1;
     
    				nbrDigits = (int) Math.log10(newCalc) + 1;
    				divisor = powers10[nbrDigits-1];
    				b0 += newCalc % divisor;
    				b1 += newCalc /divisor;
     
    				if (b0 > adjust) {
    					b0 = b0 - adjust;
    					b1++;
    				}
     
    				result = b1 - b0;
     
    				number++;
    			}
    		}
    	}
     
    	private static long[] powers10() {
    		long[] powers10 = new long[64];
    		long l = 1;
    		for(int i = 0; i < 64;i++ ) {
    			powers10[i] = l;
    			l *= 10;
    		}
    		return powers10;	
    	}
     
    }

  10. #30
    Membre averti
    Profil pro
    Développeur Java
    Inscrit en
    Novembre 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Novembre 2007
    Messages : 301
    Points : 368
    Points
    368
    Par défaut
    J'avoue je suis un peu étonné que la division soit plus rapide que le travail sur les String. Ça doit se comprendre par le fait que l'on divise par des puissances de 10.

    Nice job.

    On peut faire encore un petit mieux sur l'algorithme car en faite, on recalcul le nombre au carré pour rien car on connait déjà le résultat par les puissances de 10. Je donnerais l'algorithme un peu plus tard.

  11. #31
    Membre expert
    Avatar de ®om
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    2 815
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 2 815
    Points : 3 080
    Points
    3 080
    Par défaut
    Citation Envoyé par darkxan Voir le message
    J'avoue je suis un peu étonné que la division soit plus rapide que le travail sur les String. Ça doit se comprendre par le fait que l'on divise par des puissances de 10.

    Nice job.
    Bah non, c'est normal.
    Car en passant par des Strings, (avec n = nombre de digits) il faut que tu convertisses de long à String (n multiplications par 10 en interne, avec concaténation dans un buffer), puis que tu découpes (instanciation de plusieurs Strings), puis que tu reparses (n divisions par 10).

    Autant faire soi-même uniquement les divisions utiles et ne pas créer des instances de Strings qui ne servent à rien.
    (une division ça ne fait que quelques instructinos assembleur, pareil pour le modulo)

    Donc ça c'était une grosse partie de l'optimisation. La 2e partie concerne le calcul des puissances de 10 avec Math.pow à chaque itération, là je les fait une fois pour toutes.

  12. #32
    Membre averti
    Profil pro
    Développeur Java
    Inscrit en
    Novembre 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Novembre 2007
    Messages : 301
    Points : 368
    Points
    368
    Par défaut
    Je viens de tester l'algorithme. Il est buggué. Il suffit de tester avec une plage où il y a un changement de dizaine.

    EDIT: Le bug n'aura pas tenu longtemps :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    long adjust = powers10[i-1];

  13. #33
    Membre expert
    Avatar de ®om
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    2 815
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 2 815
    Points : 3 080
    Points
    3 080
    Par défaut
    Citation Envoyé par darkxan Voir le message
    Je viens de tester l'algorithme. Il est buggué. Il suffit de tester avec une plage où il y a un changement de dizaine.

    EDIT: Le bug n'aura pas tenu longtemps :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    long adjust = powers10[i-1];
    Ah oui, j'avais rajouté les -1, mais pas partout
    Merci de la correction

  14. #34
    Membre averti
    Profil pro
    Développeur Java
    Inscrit en
    Novembre 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Novembre 2007
    Messages : 301
    Points : 368
    Points
    368
    Par défaut
    Voilà ma version encore plus rapide :

    J'ai enlevé la recherche de divisor et le recalcul de nbrDigits et j'ai aussi supprimé adjust. J'ai mis en place le min au lieu de la double vérification sur le while et j'ai enlevé le calcul inutile du nombre au carré.

    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
    public static void algo3(final long nbrStart, long nbrFinish) {
    	final long[] powers10 = NombreLacroix.powers10();
    	final int nbrDigitsMax = (int) Math.log10(nbrFinish) + 1;
    	nbrFinish = nbrFinish++;
     
    	// Calcul de la première valeur
    	long number = nbrStart;
    	final long nbrSquared = number * number;
    	int nbrDigits = (int) Math.log10(number) + 1;
    	long divisor = powers10[nbrDigits - 1];
     
    	long b1 = nbrSquared / divisor;
    	long b0 = nbrSquared % divisor;
    	long result = b1 - b0;
    	if (result == number) {
    		System.out.println(number);
    	}
     
    	number++;
    	for (int i = nbrDigits; i <= nbrDigitsMax; i++, number++) {
    		final long nbrMaxE = powers10[i];
    		divisor = powers10[i - 1];
     
    		final long endBoucle = Math.min(nbrMaxE, nbrFinish);
    		while (number < endBoucle) {
    			final long newCalc = 2 * number - 1;
     
    			b0 += newCalc % divisor;
    			b1 += newCalc / divisor;
     
    			if (b0 > divisor) {
    				b0 = b0 - divisor;
    				b1++;
    			}
     
    			result = b1 - b0;
     
    			if (result == number) {
    				System.out.println(number);
    			}
     
    			number++;
    		}
     
    		b1 = number;
    		b0 = 0;
    		result = number;
    	}
    }
     
    private static long[] powers10() {
    	final long[] powers10 = new long[19];
    	long l = 1;
    	for (int i = 0; i < 19; i++) {
    		powers10[i] = l;
    		System.out.println(powers10[i]);
    		l *= 10;
    	}
    	return powers10;
    }
    Note : Si on veut partir d'un nombre important, il faut changer le calcul du carré est passé en BigInteger (pour éviter de dépasser le nombre maximal que peut contenir un long).

    L'avantage de cet algo, c'est que l'on ne recalcul même plus le carré à chaque dizaine et donc plus de problème de BigInteger ici.

  15. #35
    Membre expert
    Avatar de ®om
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    2 815
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 2 815
    Points : 3 080
    Points
    3 080
    Par défaut
    Citation Envoyé par ®om Voir le message
    Ah oui, j'avais rajouté les -1, mais pas partout
    Merci de la correction
    En fait c'est encore buggé...
    EDIT: ah non, il ne fait pas de -1 sur nbrMaxE


    EDIT2: par contre, ton algo3 donne 1000001, alors que les autres, non ! Seul le 3 est correct alors

  16. #36
    Membre averti
    Profil pro
    Développeur Java
    Inscrit en
    Novembre 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Novembre 2007
    Messages : 301
    Points : 368
    Points
    368
    Par défaut
    Ah ? Pourtant, je viens de tester et même avec ton algorithme, j'obtiens 1000001.

    Sinon j'ai fait une version spéciale si on commence avec un nombre qui est une puissance de 10 et le résultat est encore meilleur. Je pense que ça vient de la disposition de la boucle qui doit être plus facilement optimisable et peut être aussi du fait que certaines variables sont en final.

  17. #37
    Membre expert
    Avatar de ®om
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    2 815
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 2 815
    Points : 3 080
    Points
    3 080
    Par défaut
    Vu que dans tous les algorithmes proposés jusqu'ici, la limitation est que le carré des nombres que l'on teste soit un long (et non un BigInteger), on est sûr que la racine est un int, donc autant utiliser des int, on gagne encore un sacré gain de perfs (55% par rapport à ton algo 3, sur un système 32 bits).

    Au final, entre l'algo 1 et l'algo 4, on a 96% de gain de perfs (donc le 4 est 25 fois plus rapide).

    Voici la classe complète des tests :
    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
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    public class Lacroix {
     
    	interface LacroixAlgorithm {
    		void execute(long start, long end);
    	}
     
    	static class Algo1 implements LacroixAlgorithm {
     
    		@Override
    		public void execute(long start, long end) {
    			int nbrDigits = (int) Math.log10(start) + 1;
    			int nbrDigitsMax = (int) Math.log10(end) + 1;
     
    			long number = start;
    			for (int i = nbrDigits; i <= nbrDigitsMax; i++) {
    				long nbrSquared = number * number;
    				String nbrSquaredStr = String.valueOf(nbrSquared);
    				nbrDigits = (int) Math.log10(number) + 1;
     
    				long b1 = Long.parseLong(nbrSquaredStr.substring(0, nbrDigits));
    				long b0 = Long.parseLong(nbrSquaredStr.substring(nbrDigits));
     
    				long result = b1 - b0;
     
    				long nbrMaxE = (long) Math.pow(10, i);
    				long adjust = (long) Math.pow(10, i - 1);
     
    				number++;
     
    				while (number < nbrMaxE && number <= end + 1) {
    					if (result == number - 1 && b0 != 0) {
    						System.out.println(number - 1);
    					}
     
    					long newCalc = 2 * number - 1;
    					String newCalcStr = String.valueOf(newCalc);
     
    					b0 = b0 + Long.parseLong(newCalcStr.substring(1));
    					b1 = b1 + Long.parseLong(newCalcStr.substring(0, 1));
     
    					if (b0 > adjust) {
    						b0 = b0 - adjust;
    						b1++;
    					}
     
    					result = b1 - b0;
     
    					number++;
    				}
    			}
    		}
     
    	}
     
    	static class Algo2 implements LacroixAlgorithm {
     
    		@Override
    		public void execute(long start, long end) {
    			final long[] powers10 = powers10Long();
     
    			int nbrDigits = (int) Math.log10(start) + 1;
    			int nbrDigitsMax = (int) Math.log10(end) + 1;
    			long divisor;
    			long number = start;
    			for (int i = nbrDigits; i <= nbrDigitsMax; i++) {
    				long nbrSquared = number * number;
    				nbrDigits = (int) Math.log10(number) + 1;
    				divisor = powers10[nbrDigits - 1];
     
    				long b1 = nbrSquared / divisor;
    				long b0 = nbrSquared % divisor;
    				long result = b1 - b0;
     
    				long nbrMaxE = powers10[i];
    				long adjust = powers10[i - 1];
     
    				number++;
     
    				while (number < nbrMaxE && number <= end + 1) {
    					if (result == number - 1 && b0 != 0) {
    						System.out.println(number - 1);
    					}
     
    					long newCalc = 2 * number - 1;
     
    					nbrDigits = (int) Math.log10(newCalc) + 1;
    					divisor = powers10[nbrDigits - 1];
    					b0 += newCalc % divisor;
    					b1 += newCalc / divisor;
     
    					if (b0 > adjust) {
    						b0 = b0 - adjust;
    						b1++;
    					}
     
    					result = b1 - b0;
     
    					number++;
    				}
    			}
     
    		}
     
    	}
     
    	static class Algo3 implements LacroixAlgorithm {
    		@Override
    		public void execute(long start, long end) {
    			final long[] powers10 = powers10Long();
    			final int nbrDigitsMax = (int) Math.log10(end) + 1;
    			end = end++;
     
    			// Calcul de la première valeur
    			long number = start;
    			final long nbrSquared = number * number;
    			int nbrDigits = (int) Math.log10(number) + 1;
    			long divisor = powers10[nbrDigits - 1];
     
    			long b1 = nbrSquared / divisor;
    			long b0 = nbrSquared % divisor;
    			long result = b1 - b0;
    			if (result == number) {
    				System.out.println(number);
    			}
     
    			number++;
    			for (int i = nbrDigits; i <= nbrDigitsMax; i++, number++) {
    				final long nbrMaxE = powers10[i];
    				divisor = powers10[i - 1];
     
    				final long endBoucle = Math.min(nbrMaxE, end);
    				while (number < endBoucle) {
    					final long newCalc = 2 * number - 1;
     
    					b0 += newCalc % divisor;
    					b1 += newCalc / divisor;
     
    					if (b0 > divisor) {
    						b0 = b0 - divisor;
    						b1++;
    					}
     
    					result = b1 - b0;
     
    					if (result == number) {
    						System.out.println(number);
    					}
     
    					number++;
    				}
     
    				b1 = number;
    				b0 = 0;
    				result = number;
    			}
     
    		}
    	}
     
    	static class Algo4 implements LacroixAlgorithm {
    		@Override
    		public void execute(long start, long end) {
    			final int[] powers10 = powers10Int();
    			final int nbrDigitsMax = (int) Math.log10(end) + 1;
    			end = end++;
     
    			// Calcul de la première valeur
    			int number = (int)start;
    			final long nbrSquared = start*start;//number * number;
    			int nbrDigits = (int) Math.log10(number) + 1;
    			int divisor = powers10[nbrDigits - 1];
     
    			int b1 = (int)(nbrSquared / divisor);
    			int b0 = (int)(nbrSquared % divisor);
    			int result = b1 - b0;
    			if (result == number) {
    				System.out.println(number);
    			}
     
    			number++;
    			for (int i = nbrDigits; i <= nbrDigitsMax; i++, number++) {
    				final int nbrMaxE = powers10[i];
    				divisor = powers10[i - 1];
     
    				final int endBoucle = Math.min(nbrMaxE, (int)end);
    				while (number < endBoucle) {
    					final int newCalc = 2 * number - 1;
     
    					b0 += newCalc % divisor;
    					b1 += newCalc / divisor;
     
    					if (b0 > divisor) {
    						b0 -= divisor;
    						b1++;
    					}
     
    					result = b1 - b0;
     
    					if (result == number) {
    						System.out.println(number);
    					}
     
    					number++;
    				}
     
    				b1 = number;
    				b0 = 0;
    				result = number;
    			}
     
    		}
    	}
     
    	public static void main(String[] args) {
    		final long START = 1000000;
    		final long END = 8000000;
     
    		final LacroixAlgorithm[] strategies = { new Algo1(), new Algo2(), new Algo3(), new Algo4() };
     
    		for (LacroixAlgorithm strategy : strategies) {
    			long t = System.nanoTime();
    			strategy.execute(START, END);
    			System.out.println(strategy.getClass().getSimpleName() + " : " + (System.nanoTime() - t));
    		}
     
    	}
     
    	private static long[] powers10Long() {
    		long[] powers10 = new long[19];
    		long l = 1;
    		for (int i = 0; i < 19; i++) {
    			powers10[i] = l;
    			l *= 10;
    		}
    		return powers10;
    	}
     
    	private static int[] powers10Int() {
    		int[] powers10 = new int[10];
    		int l = 1;
    		for (int i = 0; i < 10; i++) {
    			powers10[i] = l;
    			l *= 10;
    		}
    		return powers10;
    	}
     
    }

  18. #38
    Membre averti
    Profil pro
    Développeur Java
    Inscrit en
    Novembre 2007
    Messages
    301
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Novembre 2007
    Messages : 301
    Points : 368
    Points
    368
    Par défaut
    Non, tu n'as pas le droit de faire ça.

    Il faut différencier le fait que dans mon algorithme j'ai supposé que le carré du nombre initial n'allait jamais dépassé 2^63-1 et le fait de travailler avec des int. Les nombres sur lesquels on travaille peuvent dépasser la taille maximal d'un int.

    En effet, mon algorithme 3 marche jusqu'à la valeur 2^63-1. Par contre, on doit l'initialiser avec un nombre inférieur à la racine de 2^63-1.

    On en avait déjà discuté auparavant et Exoss travaille déjà sur des nombres plus grand que les int. Par contre, effectivement si on travaille sur des nombres qui ne peuvent pas dépasser la taille maximale d'un int alors oui ton algorithme est correct.

  19. #39
    Membre expert
    Avatar de ®om
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    2 815
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 2 815
    Points : 3 080
    Points
    3 080
    Par défaut
    Citation Envoyé par darkxan Voir le message
    En effet, mon algorithme 3 marche jusqu'à la valeur 2^63-1. Par contre, on doit l'initialiser avec un nombre inférieur à la racine de 2^63-1.
    Ah oui, j'ai un peu trop généralisé en voyant cette contrainte dans le code, c'est juste à l'initialisation

  20. #40
    Membre expert
    Avatar de ®om
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    2 815
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 2 815
    Points : 3 080
    Points
    3 080
    Par défaut
    Mwarf, alors là je suis surpris, j'ai repris exactement ton algo 3, que j'ai fait en C++ (compilé avec g++ -O3 !!!) :
    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
    #include <math.h>
    #include <iostream>
    #include <algorithm>
    #include <time.h>
    using namespace std;
     
    long long * powers10() {
        long long * tab = (long long *)malloc(10*sizeof(long long));
        long long l = 1;
        for(int i = 0; i < 10; i++) {
            tab[i] = l;
            l *= 10;
        }
        return tab;
    }
     
    void algo3(long long start, long long end) {
        long long * pow = powers10();
        int nbrDigitsMax = (int) log10(end) + 1;
        end ++;
        long long number = start;
        long long nbrSquared = start * start;
        int nbrDigits = (int) log10(number) + 1;
        long long divisor = pow[nbrDigits -1 ];
     
     
        long long b1 = nbrSquared / divisor;
        long long b0 = nbrSquared % divisor;
        long long result = b1 - b0;
     
        if(result == number) {
            cout << number << '\n';
        }
     
        number++;
        for(int i = nbrDigits; i <= nbrDigitsMax; i++, number++) {
            long long nbrMaxE = pow[i];
            divisor = pow[i-1];
            long endBoucle = min(nbrMaxE, end);
            while(number < endBoucle) {
                long long newCalc = 2 * number - 1;
                b0 += newCalc % divisor;
                b1 += newCalc / divisor;
     
                if(b0 > divisor) {
                    b0 -= divisor;
                    b1++;
                }
     
                result = b1 - b0;
     
                if(result == number) {
                    cout << number << '\n';            
                }
     
                number++;
            }
     
            b1 = number;
            b0 = 0;
            result = number;
        }
    }
     
    int main() {
        algo3(1000000,8000000);
        return 0;
    }
    Il s'exécute en 320 ms, contre 254 en java !

    EDIT: Ah par contre c'est quand c'est lancé avec OpenJDK.
    J'ai essayé avec JDK Sun, et là c'est 390ms…
    Ça c'est pour le runtime.

    Pour la compile, le runtime est plus rapide (254ms) quand compilé avec eclipse que quand compilé avec openjdk (283ms)…
    (ne pas généraliser, c'est que sur ce cas-là, sur une machine 32bits)

Discussions similaires

  1. [XL-2007] Est-ce possible d'optimiser ses macros.
    Par Biker_45 dans le forum Macros et VBA Excel
    Réponses: 6
    Dernier message: 15/08/2012, 15h44
  2. Est-il possible d'optimiser cette requête ?
    Par kraiggy dans le forum Développement
    Réponses: 6
    Dernier message: 20/03/2009, 16h49
  3. Est-il possible d'optimiser cette requête ?
    Par Katachana dans le forum Requêtes
    Réponses: 2
    Dernier message: 25/06/2008, 15h50
  4. Réponses: 5
    Dernier message: 20/08/2006, 03h55
  5. Optimiser une requête..est-ce possible ?
    Par Thierry8 dans le forum Langage SQL
    Réponses: 9
    Dernier message: 27/09/2005, 12h31

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo