Compter le nombre de chiffres – quelle méthode est la plus efficace?

Il existe plusieurs solutions pour trouver le nombre de chiffres dans un nombre donné.

Par exemple:

Méthode 1:

int findn(int num) { char snum[100]; sprintf(snum, "%d", num); return strlen(snum); } 

Méthode 2:

 int findn(int num) { if (num == 0) return 1; int n = 0; while(num) { num /= 10; n++; } return n; } 

Méthode 3:

 int findn(int num) { /* math.h included */ return (int) log10(num) + 1; } 

La question est la suivante: quelle est la méthode la plus efficace? Je sais que la méthode 2 est O(n) mais qu’en est-il des méthodes 1 et 3? Comment trouver la complexité d’exécution des fonctions de la bibliothèque?

    Ce qui suit est encore plus efficace:

     int findn(int num) { if ( num < 10 ) return 1; if ( num < 100 ) return 2; //continue until max int } 

    Vous pouvez optimiser cela encore davantage en effectuant une recherche binary, mais ce serait excessif.

    Les fonctions insortingnsèques GCC / Clang __builtin_clz() ou Microsoft Visual C _BitScanReverse() en une seule instruction d’ordinateur sur plusieurs ordinateurs. Vous pouvez vous en servir comme base d’une solution O (1). Voici une implémentation 32 bits:

     #include  #include  /* Return the number of digits in the decimal representation of n. */ unsigned digits(uint32_t n) { static uint32_t powers[10] = { 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, }; static unsigned maxdigits[33] = { 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, }; unsigned bits = sizeof(n) * CHAR_BIT - __builtin_clz(n); unsigned digits = maxdigits[bits]; if (n < powers[digits - 1]) { -- digits; } return digits; } 

    Dans l’état actuel des choses, la réponse acceptée et la plus approuvée est ( toujours ) incorrecte pour les nombres négatifs. Si le répondeur prenait le temps de le tester et de découvrir qu’il était cassé pour les nombres négatifs, il aurait probablement perdu plus de temps que la machine ne l’aurait jamais fait en utilisant simplement snprintf , c’est-à-dire

     int count_digits(int arg) { return snprintf(NULL, 0, "%d", arg) - (arg < 0); } 

    Nous ne sums plus dans les années 1980; arrêtez de coder comme si nous étions. Je suis un fanatique du C-standard et ma réponse préférée donnée ici était la réponse de Tao Feng ... mais même cela n'a pas expliqué pourquoi c'est la réponse la plus efficace jusqu'à présent; Dans cette réponse, j'ai l'intention de montrer que sa réponse peut encore être améliorée en considérant ce qui suit:

    • La productivité du programmeur est plus importante que l’efficacité du code, car il faudra certainement beaucoup plus de temps pour écrire et tester de nouvelles fonctions que pour quelques microsecondes d’exécution.
    • La réutilisation des mêmes fonctions de bibliothèque standard que d’autres programmes utilisent (probablement) conserve ces bibliothèques standard dans le cache de la CPU. Un cache cache (par exemple, lorsque votre code doit être copié de la RAM dans la CPU) peut coûter jusqu'à 50 instructions de processeur, sans oublier que l'autre code peut finir par amener un autre cache à replacer snprintf dans le cache.
    • L'élimination des exigences de stockage peut exposer des optimisations supplémentaires.

    Ce qui suit décrit la micro-optimisation qui entrave votre productivité. En raison du manque d'informations que vous avez fournies dans votre réponse, personne qui répond actuellement à la question ne peut en fournir la preuve sans formuler d'hypothèses sur:

    • Lorsque nous optimisons, nous devons trouver le goulot d'étranglement le plus important dans la solution complète (le problème que votre programme est conçu pour résoudre) . Il y a deux possibilités ici: A) Vous voulez calculer le nombre d'octets à allouer pour stocker une chaîne contenant ces chiffres; B) Vous voulez juste compter le nombre de chiffres ou quoi que ce soit pour les coups de pied. Plus sur ces plus tard. Pour l'instant, il est important de réaliser que vous parlez probablement d'une partie de la solution et que cette partie n'est peut-être pas le goulot d'étranglement le plus important .
    • Le compilateur que vous utilisez, le système d'exploitation que vous utilisez et la machine que vous utilisez (y compris la vitesse de la mémoire vive, car certains d'entre nous introduisent des erreurs de cache potentielles qui sont davantage affectées par la mémoire lente que par la mémoire rapide) pourrait affecter le plus goulot d'étranglement important. Certains compilateurs sont différents des autres et optimisent certains éléments de code pour certains systèmes d’exploitation, processeurs, etc. que d’autres.

    Vous pouvez éviter la micro-optimisation en mesurant les goulets d'étranglement, c'est-à-dire en établissant un profil ( "parsing comparative" ) de chacune de ces solutions sur votre système , en supposant qu'elles résolvent même vos problèmes correctement. Si une solution ne résout pas le problème, ce n'est pas une solution, il ne faut donc pas en tenir compte ... Une fois cela fait, cela devrait éliminer la micro-optimisation. Certains compilateurs fournissent même une optimisation intelligente guidée par le profil qui réduit généralement de 20% à 30% la réorganisation des twigs et des objects pour la localisation du cache, et ce, automatiquement .

    J'ai déjà couvert le comptage des chiffres, ce qui, je pense, répond très certainement à votre question, mais il y a des cas où vous pourriez penser que vous devez compter les chiffres lorsque vous ne le faites pas , et la possibilité de supprimer la surcharge liée au comptage des chiffres peut présenter une très grande difficulté. optimisation souhaitable, à la fois en heures-personnes et en heures-machines.

    Par exemple, si vous souhaitez calculer le nombre d'octets à allouer afin de stocker une chaîne contenant ces chiffres, vous ne devez utiliser aucun runtime, car une macro de pré-traitement peut être utilisée pour calculer le nombre maximal de chiffres (ou de caractères, y compris le signe), et tous les précieux octets de stockage temporaire que vous essayez de sauvegarder seront largement dépassés en nombre par les octets de code machine ajoutés dans la logique, ce qui me semble très coûteux. Il est également avantageux pour le programmeur d’utiliser une macro de préprocesseur; la même macro peut être utilisée pour tout type entier. Voir ma réponse à cette question pour une solution à ce problème ; après tout, il est inutile de me répéter ...

    Je pense que vous pouvez peut-être écrire la première méthode

     int findn(int num) { char snum[100]; return sprintf(snum, "%d", num); } 

    car sprintf renverra le nombre de caractères écrits et vous pourrez sauvegarder l’appel dans strlen.

    Pour ce qui est de l’efficacité, je pense que cela dépend de la mise en œuvre de sprintf. Vous devrez peut-être trouver la source de sprintf et voir si c’est efficace.

    Essayez la recherche binary. Par souci de clarté, supposons des entiers 32 bits signés. Tout d’abord, vérifiez si x < 10000 . Ensuite, selon la réponse, si x < 100 ou x < 1000000 , etc.

    C'est O(log n) , où n est le nombre de chiffres.

    Ces fonctions donnent des résultats radicalement différents pour les nombres non positifs (la plus mauvaise est la méthode 3), de sorte que la comparaison de leur complexité temporelle a une valeur douteuse. J’utiliserais celui qui donne la réponse requirejse dans tous les cas; sans contexte, nous ne pouvons pas savoir ce que c’est (ce n’est probablement pas la méthode 3).

    Pour la méthode 1, findn(0) == 1 et findn(-n) == digits in n + 1 (en raison du signe négatif).

    Pour la méthode 2, findn(0) == 0 et findn(-n) == digits in n .

    Pour la méthode 3, findn(0) == INT_MIN et findn(-n) == INT_MIN également.

    Une ligne: for(digits = 0; num > 0; digits++) num /= 10;

    Je pense que sprintf() utilisera votre méthode 2 pour imprimer le nombre (pour déterminer la longueur de la chaîne à imprimer, puis pour imprimer chaque caractère de la chaîne), ce qui le rendra par nature plus lent.

    Le numéro 3 impliquerait probablement une approximation polynomiale de ln() qui impliquerait plus d’une division, donc je suppose qu’il sera également plus lent ( voici une implémentation rapide de ln (), impliquant toujours une division de float … donc beaucoup plus lente).

    Donc, je suppose que la méthode 2 est la voie à suivre.

    Veuillez noter qu’il s’agit d’une manière assez libérale d’aborder ce problème. J’imagine que tester un bon vieux million d’itérations avec chaque fonction vous indiquera le résultat. Mais ce serait trop brutal , n’est-ce pas?

    Notez que seule la méthode 2 vous donnera les résultats réels, les autres ont des défauts qui doivent être ajustés pour être corrects (voir la réponse d’Aaron). Alors, choisissez simplement la méthode 2.

    C’est ma solution … ça comptera jusqu’à 100 chiffres ou vous saurez ce que vous voulez.

     max_digits = 100 int numdigits(int x) { for (int i = 1; i < max_digits; i++) { if (x < pow(10, i)) { return i; } } return 0; } 

    La fonction printf renverra le nombre de chiffres imprimés avec succès.

     int digits,n=898392; digits=printf("%d",n); printf("Number of digits:%d",digits); 

    Sortie:

    898392

    Nombre de chiffres: 6

    Utiliser le journal peut être une bonne option …

    1. Si la machine cible prend en charge le matériel
    2. Si vous êtes sûr que int peut être converti en double et retour sans aucune perte de précision.

    Exemple de mise en oeuvre …

     int num_digits(int arg) { if (arg == 0) { return 1; } arg = abs(arg); return (int)log10(arg)+1; }