Lorsque nous codons n'importe quel type de programme sur n'importe quel langage, nous créons ou utilisons des algorithmes en permanence. Chaque fonction, méthode ou classe est un algorithme dans le sens où des paramètres sont donnés en entrée (input) dans l'expectative d'un retour (output) différent.

 

Il est toujours important de mesurer la complexité d'un algorithme afin d'être sûr d'utiliser les ressources à disposition de la manière la plus efficiente. Cette complexité se mesure avec deux indicateurs appelés Big O :

J'essaye d'aller régulièrement sur des sites comme leetcode ou hackerrank pour pratiquer. Je vous propose dans cet article d'analyser ensemble l'algorithme "Reverse Integer" (Entier renversé) dont le but est d'inverser les caractères d'un input donné. 

Pour un intégral de 32bits donné, renverser l'ordre des chiffres puis renvoyer un intégral.

 

Input -> 123

Output -> 321

 

Input -> -123

Output -> -321

 

Input -> 120

Output -> 21

 

La description précise enfin que dans le cas où notre output n'est pas dans un scope de 32bits, notre fonction doit retourner 0.

La plupart des sites d’algorithmes vous mettent à disposition une `sandbox` qui tourne avec les inputs des exemples. Cela permet d'itérer facilement pour arriver à une première version fonctionnelle :

const reverse = x => {
    /*la valeur 0 ne peut pas être renversé avec cette méthode et
    fait donc l'objet d'une exception */
    if(x === 0) return 0;
    
    /*Javascript ne permet pas d'itérer à travers un nombre (entier  
    ou décimal et nous devons donc le convertir en une chaîne de caractères*/
    const xString = x+'';

    let result = '';

    /*Nous allons passer sur chaque chiffre (ou caractère) de notre input */
    for(let i = 0; i < xString.length; i++ ){
        /* Nous procédons au "reverse", chaque caractère est ajouté 
        au début de notre résultat */
        result = xString[i] + result;
    }
    
    /* Nous devons retransformer notre chaîne en un intégral et le
     "retransformer" en une valeur négative si notre input était négatif */
    result =  x > 0 ? parseInt(result,10) : -parseInt(result,10)

    //Nous vérifions que notre résultat est bien dans un scope de 32bit
    if(result < -Math.pow(2,31) || (result > Math.pow(2,31) - 1)) return 0;

    return result;
};

Pas forcément l'algorithme le plus élégant mais la complexité est acceptable :

En cherchant comment convertir 2e31 en javascript `Math.pow(2,31)` j'ai trouvé cet article StackOverflow qui présente d'autres solutions intéressantes :

const reverse = x => {
    // Array#reverse method takes no argument.
    // You can use `Math.abs()` instead of changing the sign if negative.
    // Conversion of string to number can be done with unary plus operator.
   
    var reverseX = +String(Math.abs(x)).split('').reverse().join('');
    
    // Use a number constant instead of calculating the power
    if (reverseX > 0x7FFFFFFF) return 0;
    
    // As we did not change the sign, you can do without the
    //boolean isNegative.
    // Don't multiply with -1, just use the unary minus operator.
    // The ternary operator might interest you as well (you could 
    //even use it to combine the above return into one return statement)
    return x < 0 ? -reverseX : reverseX;
}

C'est beaucoup plus élégant et lisible mais la complexité en temps est plus élevée :

Une seconde solution est intéressante car elle permet d'obtenir le même résultat sans altérer le type (Int) de notre input :

const reverse = x => {
    //Obtention de la valeur absolue de l'input
    let num = Math.abs(x);

    let result = 0;
    let rem;
    
    while(num>0){
      /*Nous prenons les unités (soit le dernier chiffre de notre
      intégral) en demandant le modulo de notre input divisé par 10
      (Ex: 123/10 = 12 et reste 3);
      rem = num % 10;
      */
      /**Nous ajoutons ces unités en les multipliant par 10 pour    
        obtenir la "bonne tranche décimale" :
       * 12 % 10 = 2 puis 0*10 + 2 = 2
       * 1 % 10 = 1 puis 2 * 10 + 1 = 21 (Bingo!)
      */
      result = result * 10 + rem;
      
      /*Nous arrondissons vers le bas le restant divisé par 10 afin 
      de répéter le même processus avec un input ôté des unités 
      que nous venons de traiter*/
      num = Math.floor(num/10);
    }

    /*Puisque nous travaillons avec une valeur absolue, il n'y a plus
     que le côté positif de notre échelle de 32bits à tester */
    if(0x7FFFFFFF < result) return 0

    //Si notre input était négatif, notre output doit être négatif.
    if(x < 0) return result * -1;

    return result;
};

La complexité est optimale, O(log(x)) en temps et O(1) en espace car nous n'avons plus besoin de dupliquer l'input au format chaîne . Vous pouvez aussi vous intéresser à Math.floor, lire les spécifications permet de voir que la complexité de cette fonction est négligeable.

Nous pouvons noter la présence d'une valeur hexadécimale dans les deux précédents exemples. Voici une bonne occasion de s'intéresser à cette écriture.

Nous pouvons découper la valeur `0x7FFFFFFF` en deux parties :

Ce site expliquera mieux que moi comment cela fonctionne mais pour schématiser :

7FFFFFFF = 7 + F + F + F + F +F + F + F
7FFFFFFF = (7*16e7) + (15*16e6) + (15*16e5) + (15*16e4) + (15*16e3) + (15*16e2) + (15*16e1) + (15*16e0);
7FFFFFFF = 1879048192 + 251658240 + 15728640 + 983040 + 61440 + 3840 + 240 + 15
7FFFFFFF = 2147483647

Soit exactement `< Math.pow(2,31)` ! L'intérêt de l'hexadecimal est que vous épargnez un peu de travail au moteur JS en lui fournissant une information plus bas niveau qu'une décimale qu'il aurait dû convertir. EDIT: Après le retour de @Jonathan Antoine, il s'avère que fournir une valeur décimale ou hexadecimal ne change rien ici. Le seul intérêt est d'avoir une valeur statique au lieu de la fonction `Math.pow(x,y)`.

Si langage bas niveau et Javascript vous intéressent, découvrez WebAssembly avec Jérôme Giacomini.

Si vous avez essayé le premier snippet, vous aurez constaté qu'il fonctionne. Il devrait pourtant échouer dans d'autres langages, et ne doit ce succès qu'à la tolérance d'une méthode Javascript <3

Si vous avez trouvé le "problème", marquez-le en commentaire !

 

A bientôt pour un nouvel algorithme :)