Discussion: Optimisation de code

  1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    juin 2016
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juin 2016
    Messages : 2
    Points : 3
    Points
    3

    Par défaut Optimisation de code

    Bonjour à tous,

    Je cherche à optimiser mon code pour un exercice en ligne. (sur le site www.codewars.com)
    Voici le sujet:
    Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square!

    Given two integers m, n (1 <= m <= n) we want to find all integers between m and n whose sum of squared divisors is itself a square. 42 is such a number.

    The result will be an array of arrays(in C an array of Pair), each subarray having two elements, first the number whose squared divisors is a square and then the sum of the squared divisors.

    #Examples:

    list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]
    list_squared(42, 250) --> [[42, 2500], [246, 84100]]
    Et voici le code que j'ai pour le moment:
    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
     
    <?php
    function listSquared($m, $n) {
        $response = [];
        //boucle principale de $m à $n
        for ($k=$m;$k<=$n;$k++) {
            //calcul de la somme des diviseurs au carré
            $sumSquareDiv = 0;
            for($j=1;$j<=$k;$j++) {
                if ($k%$j === 0) {
                    $sumSquareDiv += $j**2;
                }
            }
            //si la racine du diviseur est un nombre entier on ajoute
            //$k et $sumSquareDiv à la réponse
            $rac = sqrt($sumSquareDiv);
            if(strpos($rac, '.') === false) {
                $element = array($k, $sumSquareDiv);
                $response[] = $element;
            }
        }
        //on retourne la réponse sous forme d'un tableau de tableaux à 2 entrées
        return($response);
    }
    Ce code fonctionne, mais lorsque je valide ce dernier sur ma plateforme d'exercice j'ai une erreur me disant que le code met trop de temps à s'executer.

    Je cherche donc à optimiser mon code, mais je ne vois pas comment faire.

    Si quelqu'un à une idée je suis preneur.

    Merci à tous.

  2. #2
    Modérateur
    Avatar de rawsrc
    Homme Profil pro
    Dev indep
    Inscrit en
    mars 2004
    Messages
    4 385
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Dev indep

    Informations forums :
    Inscription : mars 2004
    Messages : 4 385
    Points : 10 876
    Points
    10 876

    Par défaut

    Salut,

    bon généralement je n'aime pas faire les devoirs des autres, m'enfin aujourd'hui c'est ton jour de chance

    Voici, ce que j'aurais proposé :
    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
    function list_squared($m, $n)
    {
        $sum_square = function($p) {
            $total = ($p === 1) ? 1 : 1 + $p * $p;
            for ($i = 2; $i * $i <= $p; ++$i) {
                if ($p % $i === 0) {
                    $total += $i * $i;
                    if ($i * $i !== $p) {
                        $total += ($p / $i) * ($p / $i);
                    }
                }
            }
     
            return $total;
        };
     
        $data = [];
     
        for ($i = $m; $i <= $n; ++$i) {
            $sum  = $sum_square($i);
            $sqrt = (int)sqrt($sum);
            if (($sqrt * $sqrt) === $sum) {
                $data[] = [$i, $sum];
            }
        }
     
        return $data;
    }
     
    $list_a = list_squared(1, 250);     // [[1, 1], [42, 2500], [246, 84100]]
    $list_b = list_squared(42, 250);    // [[42, 2500], [246, 84100]]
    Allez bonne continuation
    Dis moi si je suis reçu
    # Dans la Création, tout est permis mais tout n'est pas utile...

  3. #3
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    juin 2016
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juin 2016
    Messages : 2
    Points : 3
    Points
    3

    Par défaut Super optimisation !!!

    Salut à toi rawsrc,

    et bien sache que tu es reçu

    Ton code passe en environ 2.5s lors des test alors que le miens était recalé car il mettait plus de 12s!!!

    Tu as donc largement optimisé mon code.

    Encore merci pour ton aide et ta réactivité.

  4. #4
    Membre émérite

    Profil pro
    Inscrit en
    mai 2008
    Messages
    1 460
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mai 2008
    Messages : 1 460
    Points : 2 250
    Points
    2 250

    Par défaut

    Si tu veux grignoter quelques microsecondes de moins (mais la différence ne sera pas aussi flagrante qu'entre ta version et celle de rawsrc qui est stupéfiante), tu peux remplacer ses boucles for par do/while.

    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
    function list_squared_do_while($m, $n) {
    	$sum_square = function($p) {
    		$total = ($p === 1) ? 1 : 1 + $p * $p;
    		$i = 2;
    		do {
    			if ($p % $i === 0) {
    				$total += $i * $i;
    				if ($i * $i !== $p) {
    					$total += ($p / $i) * ($p / $i);
    				}
    			}
    		} while($i * $i <= $p && ++$i);
     
    		return $total;
    	};
     
    	$data = [];
     
    	do {
    		$sum  = $sum_square($m);
    		$sqrt = (int)sqrt($sum);
    		if (($sqrt * $sqrt) === $sum) {
    			$data[] = [$m, $sum];
    		}
    	} while($m < $n && $m++);
     
    	return $data;
    }
    Sur ma machine de test j'ai une différence d'environ 18%.

  5. #5
    Membre émérite

    Profil pro
    Inscrit en
    mai 2008
    Messages
    1 460
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mai 2008
    Messages : 1 460
    Points : 2 250
    Points
    2 250

    Par défaut

    Et il faudrait voir ce que ça donne avec goto :-D

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. optimiser le code d'une fonction
    Par yanis97 dans le forum MS SQL-Server
    Réponses: 1
    Dernier message: 15/07/2005, 09h41
  2. Optimiser mon code ASP/HTML
    Par ahage4x4 dans le forum ASP
    Réponses: 7
    Dernier message: 30/05/2005, 11h29
  3. optimiser le code
    Par bibi2607 dans le forum ASP
    Réponses: 3
    Dernier message: 03/02/2005, 15h30
  4. syntaxe et optimisation de codes
    Par elitol dans le forum Langage SQL
    Réponses: 18
    Dernier message: 12/08/2004, 12h54
  5. optimisation du code et var globales
    Par tigrou2405 dans le forum ASP
    Réponses: 2
    Dernier message: 23/01/2004, 11h59

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