par exemple,
n = 3432, result 4
n = 45, result 2
n = 33215, result 5
n = -357, result 3
Je suppose que je pourrais simplement le transformer en chaîne puis obtenir la longueur de la chaîne mais cela semble compliqué et bidouillé.
par exemple,
n = 3432, result 4
n = 45, result 2
n = 33215, result 5
n = -357, result 3
Je suppose que je pourrais simplement le transformer en chaîne puis obtenir la longueur de la chaîne mais cela semble compliqué et bidouillé.
L'approche récursive :-)
int numPlaces (int n) {
if (n < 0) return numPlaces ((n == MININT) ? MAXINT : -n);
if (n < 10) return 1;
return 1 + numPlaces (n / 10);
}
Ou itératif:
int numPlaces (int n) {
int r = 1;
if (n < 0) n = (n == MININT) ? MAXINT : -n;
while (n > 9) {
n /= 10;
r++;
}
return r;
}
Ou vitesse brute:
int numPlaces (int n) {
if (n < 0) n = (n == MININT) ? MAXINT : -n;
if (n < 10) return 1;
if (n < 100) return 2;
if (n < 1000) return 3;
if (n < 10000) return 4;
if (n < 100000) return 5;
if (n < 1000000) return 6;
if (n < 10000000) return 7;
if (n < 100000000) return 8;
if (n < 1000000000) return 9;
/* 2147483647 is 2^31-1 - add more ifs as needed
and adjust this final return as well. */
return 10;
}
Ceux ci-dessus ont été modifiées afin de mieux les processus de MININT. Sur tout bizarre systèmes qui ne suivent pas sensée 2n complément à deux règles pour les entiers, ils peuvent avoir besoin d'ajustement.
La vitesse brute version surpasse la virgule flottante version, modifiée ci-dessous:
int numPlaces (int n) {
if (n == 0) return 1;
return floor (log10 (abs (n))) + 1;
}
Avec une centaine de millions d'itérations, j'obtiens les résultats suivants:
Raw speed with 0: 0 seconds
Raw speed with 2^31-1: 1 second
Iterative with 2^31-1: 5 seconds
Recursive with 2^31-1: 6 seconds
Floating point with 1: 6 seconds
Floating point with 2^31-1: 7 seconds
Qui en fait m'a surpris un peu - j'ai pensé que les puces d'Intel a fait une bonne FPU mais je suppose général FP opérations ne peut toujours pas rivaliser avec la main optimisée code entier.
Mise à jour suite à stormsoul suggestions:
Test de les multiplier-solution itérative par stormsoul donne un résultat de 4 secondes, alors qu'il est bien plus rapide que la fracture itérative solution, elle n'est pas toujours correspondre à l'optimisation de la si-déclaration de la solution.
Choisir les arguments à partir d'un pool de 1000 numéros générés au hasard poussé la vitesse brute le temps de 2 secondes, alors qu'il semble y avoir un certain avantage à avoir le même argument à chaque fois, c'est toujours le plus rapide approche répertoriés.
Compilation avec -O2 amélioration de la vitesse, mais pas les positions relatives (j'ai augmenté le nombre d'itérations par un facteur de dix pour vérifier cela).
Toute analyse va avoir à faire sérieusement dans les rouages de l'efficacité de l'UC (les différents types d'optimisation, l'utilisation de caches, direction de la prévision, de PROCESSEUR dont vous avez réellement, la température ambiante dans la pièce et ainsi de suite) qui va obtenir de la manière de mon travail rémunéré :-). C'est un détournement intéressant mais, à un certain point, le retour sur investissement pour l'optimisation devient trop petite à la matière. Je pense que nous avons assez de solutions pour avoir répondu à la question (qui n'était, après tout, pas une question de vitesse).
Mise à jour:
Ce sera ma dernière mise à jour de cette réponse de limitation des grossières erreurs qui ne sont pas dépendantes de l'architecture. Inspiré par stormsoul de vaillants efforts pour mesurer, je poste mon programme de test (modifié que par stormsoul propre programme de test) ainsi que quelques exemples de chiffres pour toutes les méthodes indiquées dans les réponses ici. Gardez à l'esprit que c'est sur une machine en particulier, votre kilométrage peut varier selon l'endroit où vous l'exécuter (c'est pourquoi je poste le code de test).
Faire avec elle comme vous le souhaitez:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#define numof(a) (sizeof(a) / sizeof(a[0]))
/* Random numbers and accuracy checks. */
static int rndnum[10000];
static int rt[numof(rndnum)];
/* All digit counting functions here. */
static int count_recur (int n) {
if (n < 0) return count_recur ((n == INT_MIN) ? INT_MAX : -n);
if (n < 10) return 1;
return 1 + count_recur (n / 10);
}
static int count_diviter (int n) {
int r = 1;
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
while (n > 9) {
n /= 10;
r++;
}
return r;
}
static int count_multiter (int n) {
unsigned int num = abs(n);
unsigned int x, i;
for (x=10, i=1; ; x*=10, i++) {
if (num < x)
return i;
if (x > INT_MAX/10)
return i+1;
}
}
static int count_ifs (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n < 10) return 1;
if (n < 100) return 2;
if (n < 1000) return 3;
if (n < 10000) return 4;
if (n < 100000) return 5;
if (n < 1000000) return 6;
if (n < 10000000) return 7;
if (n < 100000000) return 8;
if (n < 1000000000) return 9;
/* 2147483647 is 2^31-1 - add more ifs as needed
and adjust this final return as well. */
return 10;
}
static int count_revifs (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n > 999999999) return 10;
if (n > 99999999) return 9;
if (n > 9999999) return 8;
if (n > 999999) return 7;
if (n > 99999) return 6;
if (n > 9999) return 5;
if (n > 999) return 4;
if (n > 99) return 3;
if (n > 9) return 2;
return 1;
}
static int count_log10 (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n == 0) return 1;
return floor (log10 (n)) + 1;
}
static int count_bchop (int n) {
int r = 1;
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n >= 100000000) {
r += 8;
n /= 100000000;
}
if (n >= 10000) {
r += 4;
n /= 10000;
}
if (n >= 100) {
r += 2;
n /= 100;
}
if (n >= 10)
r++;
return r;
}
/* Structure to control calling of functions. */
typedef struct {
int (*fnptr)(int);
char *desc;
} tFn;
static tFn fn[] = {
NULL, NULL,
count_recur, " recursive",
count_diviter, " divide-iterative",
count_multiter, " multiply-iterative",
count_ifs, " if-statements",
count_revifs, "reverse-if-statements",
count_log10, " log-10",
count_bchop, " binary chop",
};
static clock_t clk[numof (fn)];
int main (int c, char *v[]) {
int i, j, k, r;
int s = 1;
/* Test code:
printf ("%11d %d\n", INT_MIN, count_recur(INT_MIN));
for (i = -1000000000; i != 0; i /= 10)
printf ("%11d %d\n", i, count_recur(i));
printf ("%11d %d\n", 0, count_recur(0));
for (i = 1; i != 1000000000; i *= 10)
printf ("%11d %d\n", i, count_recur(i));
printf ("%11d %d\n", 1000000000, count_recur(1000000000));
printf ("%11d %d\n", INT_MAX, count_recur(INT_MAX));
/* */
/* Randomize and create random pool of numbers. */
srand (time (NULL));
for (j = 0; j < numof (rndnum); j++) {
rndnum[j] = s * rand();
s = -s;
}
rndnum[0] = INT_MAX;
rndnum[1] = INT_MIN;
/* For testing. */
for (k = 0; k < numof (rndnum); k++) {
rt[k] = (fn[1].fnptr)(rndnum[k]);
}
/* Test each of the functions in turn. */
clk[0] = clock();
for (i = 1; i < numof (fn); i++) {
for (j = 0; j < 10000; j++) {
for (k = 0; k < numof (rndnum); k++) {
r = (fn[i].fnptr)(rndnum[k]);
/* Test code:
if (r != rt[k]) {
printf ("Mismatch error [%s] %d %d %d %d\n",
fn[i].desc, k, rndnum[k], rt[k], r);
return 1;
}
/* */
}
}
clk[i] = clock();
}
/* Print out results. */
for (i = 1; i < numof (fn); i++) {
printf ("Time for %s: %10d\n", fn[i].desc, (int)(clk[i] - clk[i-1]));
}
return 0;
}
Et voici le classement de mon environnement:
Optimisation du niveau 0:
Time for reverse-if-statements: 1704
Time for if-statements: 2296
Time for binary chop: 2515
Time for multiply-iterative: 5141
Time for divide-iterative: 7375
Time for recursive: 10469
Time for log-10: 26953
Optimisation de niveau 3:
Time for if-statements: 1047
Time for binary chop: 1156
Time for reverse-if-statements: 1500
Time for multiply-iterative: 2937
Time for divide-iterative: 5391
Time for recursive: 8875
Time for log-10: 25438
Divisez par 10 en boucle jusqu'à ce que le résultat atteigne zéro. Le nombre d'itérations correspondra au nombre de chiffres décimaux.
En supposant que vous vous attendiez à obtenir 0 chiffre dans une valeur zéro:
int countDigits( int value )
{
int result = 0;
while( value != 0 ) {
value /= 10;
result++;
}
return result;
}
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.