Compter le nombre de chiffres - quelle méthode est la plus efficace?
Il y a plus d'une solution 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 - ce qui est la méthode la plus efficace? Je sais que la méthode 2 est O(n)
mais que penser de la méthode 1 et la méthode-3? Comment puis-je trouver le temps d'exécution de la complexité des fonctions de la bibliothèque?
- Cela dépend de ce que tu veux dire par
O
.O
se réfère généralement à une complexité asymptotique, maislog10
, par exemple, ne peut traiter que d'un fixe d'entrée de gamme, donc c'est en faitO(1)
. - vous pouvez toujours tester pour le savoir, et de poster vos résultats...
- En écho à AShelly, la seule façon de le savoir est de code tous les trois versions et de comparer leurs performances.
- Si vous vous attendez à
num=0
de retour1
de la Méthode 1 est la seule solution qui fonctionne. Dans mon test, les trois méthodes retourné un nombre différent pour0
.
Vous devez vous connecter pour publier un commentaire.
La suite est encore plus efficace:
Vous pouvez optimiser encore plus loin en faisant une recherche binaire, mais ce serait exagéré.
O(n)
, non? Le nombre de comparaisons nécessaires augmente linéairement avec la taille de laint
; de même questrlen()
d'une itération dans un tableau à la recherche pour\0
int
est limitée. Comme c'est lestrlen()
variante. Ils sont en fait tous les O(1). Mais j'ai en quelque sorte que ce sera plus rapide.O(k)
, oùk
est le nombre de bits nécessaires pour représenter lesnum
comme un entier.O
notation s'applique uniquement aux valeurs que l'on peut obtenir (théoriquement) quasi-infinie. Depuisk
a un maximum (même si ce maximum est de 32 ou 64 ou 10000), il est encoreO(1)
.int
n'est pas nécessairement de 4 octets).O(k)
est une mesure utile, car il nous dit que l'ampleur de l'entrée combien de temps il faut pour exécuter, qui est ce que généralement vous voulez savoir à partir de gros-O.O(1)
.return
et la dernière, mais la machine abstraite dit que les deux conditions sont séparés par une séquence de points. Vous pourriez faire un O(1) fonction en supprimant la séquence des points comme ceci:return (n >= 0) + (n >= 10) + (n >= 100) + (n >= 1000) + (n >= 10000);
(il n'en est rien pour le négatifint
valeurs, d'ailleurs) mais alors, vous êtes à la modification de la constante. Certains O(1) les fonctions sont garantis pour être plus lent que ce que O(n) de fonctions.0
àINT_MAX
, il faut au plusnumber of characters in INT_MAX
étapes, donc il est limité par une constante (par opposition à calculer les factorielles d'un nombre entre0
àINT_MAX
, où les échelles de façon très différente). Je suis d'accord c'est un micro-optimisation, et que vous devriez aller pour readabilty, mais il répond toujours à la question. Le bord de cas négatifs peut être facilement résolu par un* -1
...SIZE-MAX
octets, de sorte questrlen
est limitée à l'inspection que le nombre d'octets. Est ce que cela implique questrlen
est O(1)?* -1
peut présenter un comportement indéterminé pour des valeurs négatives.SIZE_MAX
) d'un objet (c'est à dire une chaîne de caractères) est directement liée à la limitation de la taille d'unint
, et donc votre réponse questrlen
est O(n) contredit votre conviction que le code ci-dessus est O(1)? Déroulement d'une boucle pour la limite supérieure de ne pas réduire la complexité, sinon on pourrait dérouler la boucle destrlen
àSIZE_MAX
tests et cela permettrait de réduirestrlen
à O(1).SIZE_MAX
" qui est un petit nombre. 2. La complexité se réfère à la croissance du temps de calcul lié à la croissance de l'entrée fournie. Lorsque vous limitez la saisie, vous pouvez limiter la croissance en temps de calcul. Par définition, si le temps de calcul est lié (dans ce cas, le temps prendra le processus de la maximum entrée disponible), il est alors constante.return
suivi d'un autre chiffre (à partir de la même integer) avec une autre occasion pourreturn
, l'exécution pourrait ne pas atteindre la deuxième comparaison, afin que le deuxièmereturn
à se produire. Je suis surpris, je dois le signaler. Il y a une branche qui renvoie un (en fait plusieurs) séquence de point/s plus vite que les autres, de sorte que cette fonction ne peut pas être O(1) en temps constant de la complexité.return n < 10 ? 1 : n < 100 ? 2 : ...
l'alignement de la?
s au-dessous de lan
dereturn
. Bien sûr, la séquence de points sont toujours, de court-circuit d'évaluation s'applique toujours (c'est à dire où la première branche est prise, le reste ne sera pas évalué). On pourrait faire la même avecstrcpy
c'est à direif (!str[0]) { return 0; } if (!str[1]) { return 1; } ... if (!str[SIZE_MAX]) { return SIZE_MAX; }
ousize_t strlen(char const *str) { return !str[0] ? 0 : !str[1] ? 1 : !str[2] ? 2 : ... SIZE_MAX; }
... comment ça pourrait être rapide?Tel qu'il est actuellement reconnu et le plus fortement approuvé réponse est (encore) incorrect pour les nombres négatifs. Si le répondeur étaient de prendre le temps de le tester et de trouver que c'est cassé pour les nombres négatifs, il aurait probablement perdu plus de temps que la machine serait en utilisant simplement
snprintf
, c'est à direNous ne sommes pas dans les années 1980 plus; l'arrêt de codage que nous sommes. Je suis un C-standard zélote, et mon préféré réponse donnée ici a été Tao Feng répondre... mais même cela n'a pas aller dans pourquoi c'est le plus efficace de réponse à ce jour; dans cette réponse, j'ai l'intention de montrer que sa réponse peut être améliorée en tenant compte des éléments suivants:
snprintf
de retour dans le cache de toute façon.La section suivante décrit la micro-optimisation qui empêche votre productivité. En raison du manque d'informations que vous avez fournies dans votre réponse, personne ne répond à la question qu'il se présente actuellement, peut fournir des preuves sans faire d'hypothèses sur:
Vous pouvez éviter la micro-optimisation, par la mesure des goulets d'étranglement, c'est à dire par le profilage ("benchmarking") chacune de ces solutions sur votre système, en supposant qu'ils sont encore à résoudre votre problèmes correctement. Si une solution ne résout pas le problème, ce n'est pas une solution, donc il ne devrait pas être considéré comme... Quand il est fait correctement, cela devrait éliminer la micro-optimisation. Certains compilateurs même de fournir intelligent profil guidée optimisation couramment rase de 20 à 30% par la réorganisation des branches et des objets pour la localité de cache, et ce, de manière automatique.
Je l'ai déjà couvert de comptage des chiffres, je pense que la plupart certainement répondre à votre question, mais il ya des cas où vous pourriez pense vous besoin de compter les chiffres lorsque vous ne pas, et la possibilité de supprimer la surcharge de comptage chiffres pourraient présenter un très souhaitable d'optimisation, à la fois chez l'homme heures et en machine heures.
Par exemple, si vous souhaitez calculer le nombre d'octets à allouer pour stocker une chaîne de caractères contenant ces chiffres, vous ne devriez pas utiliser toute l'exécution, car un préprocesseur macro peut être utilisée pour calculer le nombre maximal de chiffres (ou de caractères, y compris le signe), et de précieux octets de stockage temporaire vous essayez d'enregistrer sera bien dépassés par la machine octets de code ajouté dans la logique, ce qui semble être un coût excessif pour moi. Il y a également un avantage pour le programmeur d'utiliser un préprocesseur macro; la même macro peut être utilisé pour tout type entier. Voir ma réponse à cette question pour une solution à ce problème; après tout, il n'y a pas de point de me répéter...
(arg < 0)
ne soustraire l'octet de signe lorsquearg
est inférieure à 0, et parce que je sais commentsnprintf
œuvres. Donc, je suis déjà plus probable miles d'avance de la réponse sommet, en temps de productivité et de temps PROCESSEUR en raison du manque de tests requis."log
version sans déclarer toutes les variables supplémentaires... peut-être alors vous comprendrez ce que je veux dire par "stockage intermédiaire", et pourquoisnprintf
est vraiment mieux quelog
à cette fin.log
version implique une conversion deint
àdouble
(qui est une variable de type point), voici ce que tout informaticien devez savoir à propos de l'arithmétique à virgule flottante. Comme il y a une conversion deint
àdouble
pour la conversion dex
danslog(x)
, il y a aussi une conversion dedouble
retour àint
pour la conversion enint y = log_x_expression;
. Pour deux de ces conversions, C11/6.3.1.4p2 les états suivants:int
valeur est dans les limites dedouble
ou pas? Aussi, comment voulez-vous gérer les nombres négatifs? Avez-vous testé? Avez-vous prévu pour cela? Je n'ai pas besoin de plan ou de test, parce que... je sais commentsnprintf
va les compter... se Sentir libre de perdre plusieurs heures de planification et de test. Dans l'intervalle, le goulot d'étranglement est de plus en plus par ceux de plusieurs heures, et ce sont ceux de l'homme d'heures de coûter encore plus d'argent que les cycles d'horloge du CPU... Convaincu, encore?snprintf
n'utilise pas de stockage intermédiaire" à l'interne? Je pense que vous êtes sur la pensée. Pourquoi auriez-vous besoin de plusieurs heures pour planifier et tester une telle fonction simple? Aussi, vous pouvez simplement ajouter un moment de la compilation vérifierint
peut être représenté par undouble
pour votre plate-forme cible.log10(0)
?log10(1)
?... Maintenant, comme je l'ai demandé plus tôt, veuillez écrire votre (travail)log10
version decount_digits
nous pouvons donc comparer les deux, de travail de travail, plutôt que de travailler pour buggy.unsigned
types. Gardez à l'esprit, c'est un site où des questions sont souvent posées au sujet invalide/morceaux de code. Vous ne pouvez pas assumer la validité de code en question, mais vous devez absolument être en mesure d'assumer la validité de code dans les réponses... Aussi garder à l'esprit, lorsque d'autres visiteurs viennent ici à la recherche d'une réponse à la question avec des valeurs négatives pris en charge, ils seraient déçus par toutes les réponses ci-dessus la mienne, ne seraient-ils pas?La GCC/Clang
__builtin_clozapine()
ou Microsoft Visual C_BitScanReverse()
fonctions intrinsèques de les compiler en une seule instruction machine sur de nombreuses machines. Vous pouvez l'utiliser comme base pour un O(1) solution. Voici une version 32 bits de mise en œuvre:maxdigits
table est[len(str(pow(2,b))) for b in range(0,MAX_BITS)]
. Étendre lapowers
table de sorte qu'il a entrées jusqu'à 10^19. Cela devrait le faire.int
. La question n'est pas explicitement état de savoir si ou de ne pas les nombres négatifs sont attendus, et en effet certains de ses alternatives à compter de la signer et d'autres n'ont pas. C'est agréable de voir une autre alternative, pour les téléspectateurs, mais je ne peux pas aider mais se sentir conforme à la norme, O(1) de la version pourrait être approprié: remplacer__builtin_clz(n)
avec les changements et les ajouts ou les comparaisons, c'est à dire quelque chose commeunsigned bits = sizeof n * CHAR_BIT - (n <= 0x7FFFFFFF) - (n <= 0x3FFFFFFF) - (n <= 0x1FFFFFFF) - ...
.if (!n) return 1
?Je pense que peut-être que vous pouvez écrire la première méthode que
parce que sprintf retourne le nombre de caractères écrits et vous pouvez économiser de l'appel à strlen.
Que pour l'efficacité, je pense que ça dépend de la mise en œuvre de sprintf, vous devrez peut-être trouver la source de sprintf et voir si c'est l'efficacité de le faire.
Essayer binaire de recherche. Par souci de clarté, supposons signé nombres entiers de 32 bits. Tout d'abord, vérifiez si
x < 10000
. Ensuite, en fonction de la réponse, six < 100
oux < 1000000
, et ainsi de suite.C'est
O(log n)
, oùn
est le nombre de chiffres.Ces fonctions donnent considérablement des résultats différents pour les non-positif numéros (le pire, c'est la méthode 3), de sorte que la comparaison de leurs temps de complexité est d'une valeur douteuse. Je voudrais utiliser celui qui donne la réponse dans tous les cas; sans contexte, on ne peut pas savoir ce que c'est (ce n'est probablement pas la méthode 3).
Pour la méthode 1,
findn(0) == 1
, etfindn(-n) == digits in n + 1
(à cause du signe négatif).Pour la méthode 2,
findn(0) == 0
, etfindn(-n) == digits in n
.Pour la méthode 3,
findn(0) == INT_MIN
, etfindn(-n) == INT_MIN
ainsi.Un liner:
for(digits = 0; num > 0; digits++) num /= 10;
for(digits = 1; num /= 10; digits++);
Je pense que
sprintf()
de l'utilisation de vos méthode 2 pour imprimer le nombre (pour déterminer la longueur de la chaîne à imprimer, puis à imprimer chaque caractère de la chaîne), de sorte qu'il sera plus lent de manière intrinsèque.Numéro 3 serait probablement impliquer une certaine approximation polynomiale de
ln()
qui sera plus que 1 de la division, donc je suppose que ce sera plus lent aussi (voici un rapide ln() de la mise en œuvre, impliquant encore flotter division... donc beaucoup plus lent).Donc ma première supposition, la méthode 2 est le chemin à parcourir.
Veuillez noter que ceci est un libéral façon d'aborder ce problème. Je suppose que le test d'un bon vieux chronométré millions d'itération à chaque fonction va vous raconter la suite. Mais il serait abeille trop bruteforce, ne serait-il pas?
Noter que seule la méthode 2 vous donnera les résultats réels, les autres ont des défauts qui doivent être ajustés afin d'être correct (voir Aaron réponse). Donc il suffit de choisir la méthode 2.
C'est ma solution...
il va compter jusqu'à 100 chiffres ou vous savez ce que vous voulez de compter jusqu'à.
pow()
pour la vitesse:int pow10[max_digits]; pow10[0] = 1; for (int i = 1; i < max_digits; i++) pow10[i] = 10 * pow10[i-1];
. 2. en Outre un gain de vitesse: recherche binaire.#include <math.h>
, droit?pow()
est une opération de virgule flottante, il est donc peu probable d'être plus rapide qu'un très petit nombre entier de table de recherche. Je ne peux pas être absolument certain de ce sans preuve, c'est simplement de bon sens de la logique, qui est faillible. Je n'ai jamais mis en œuvre IRL que j'ai proposé là.printf fonction retourne le nombre de chiffres réussi à imprimer.
De sortie:
898392
Nombre de chiffres:6
À l'aide de journal peut être une bonne option...
int
peut être jeté dansdouble
et à l'arrière, sans perte de précision.Exemple de mise en œuvre...
log10
nécessite undouble
argument. Il y a toujours une conversion implicite deint
àdouble
qui se passe ici, vous pouvez vous faire une conversion explicite par l'introduction d'un casting ici:return (int)log10((double)arg)+1;
et le problème avec ces deux conversions (en dehors de la surcharge qu'ils encourent), c'est que lorsqueint
a une portée qui s'étend au-delà dedouble
, comportement indéfini est possible. Ainsi, cette approche est, autant que je sache, pas de portable dans les domaines de la C.int
(ILP64 et SILP64) et IEEE754?snprintf
la solution la partout et qui est plus "multi-plateforme/l'épreuve de l'avenir" que d'utiliser log10 mais il ya des moments où vous n'êtes pas à la recherche de solution générale. Une plate-forme spécifique de la solution peut être plus optimal, même si elle n'est pas portable.