algorithm - suma - contar los dígitos de un número entero positivo
Encontrar la cantidad de dígitos de un entero (16)
¿Cuál es el mejor método para encontrar la cantidad de dígitos de un entero positivo?
Encontré estos 3 métodos básicos:
conversión a cadena
String s = new Integer(t).toString(); int len = s.length();en bucle
for(long long int temp = number; temp >= 1;) { temp/=10; decimalPlaces++; }cálculo logarítmico
digits = floor( log10( number ) ) + 1;
donde puede calcular log10 (x) = ln (x) / ln (10) en la mayoría de los idiomas.
Primero pensé que el método de cuerda era el más sucio, pero cuanto más lo pienso, más pienso que es la manera más rápida. ¿O es eso?
Aquí está la medida en Swift 4.
Código de algoritmos:
extension Int {
var numberOfDigits0: Int {
var currentNumber = self
var n = 1
if (currentNumber >= 100000000) {
n += 8
currentNumber /= 100000000
}
if (currentNumber >= 10000) {
n += 4
currentNumber /= 10000
}
if (currentNumber >= 100) {
n += 2
currentNumber /= 100
}
if (currentNumber >= 10) {
n += 1
}
return n
}
var numberOfDigits1: Int {
return String(self).count
}
var numberOfDigits2: Int {
var n = 1
var currentNumber = self
while currentNumber > 9 {
n += 1
currentNumber /= 10
}
return n
}
}
Código de medición:
var timeInterval0 = Date()
for i in 0...10000 {
i.numberOfDigits0
}
print("timeInterval0: /(Date().timeIntervalSince(timeInterval0))")
var timeInterval1 = Date()
for i in 0...10000 {
i.numberOfDigits1
}
print("timeInterval1: /(Date().timeIntervalSince(timeInterval1))")
var timeInterval2 = Date()
for i in 0...10000 {
i.numberOfDigits2
}
print("timeInterval2: /(Date().timeIntervalSince(timeInterval2))")
Salida
timeInterval0: 1.92149806022644
timeInterval1: 0.557608008384705
timeInterval2: 2.83262193202972
Sobre esta base de medición, la conversión de cadenas es la mejor opción para el lenguaje Swift.
Bueno, la respuesta correcta sería medirlo, pero debería poder adivinar la cantidad de pasos de la CPU implicados en la conversión de cadenas y atravesarlas buscando un marcador final
Luego, piense cuántas operaciones de FPU puede hacer su procesador y qué tan fácil es calcular un solo registro.
editar: perder un poco más de tiempo un lunes por la mañana :-)
String s = new Integer(t).toString();
int len = s.length();
Uno de los problemas con los lenguajes de alto nivel es adivinar cuánto trabajo está haciendo el sistema detrás de escena de una declaración aparentemente simple. Enlace obligatorio de Joel
Esta afirmación implica la asignación de memoria para una cadena, y posiblemente un par de copias temporales de una cadena. Debe analizar el número entero y copiar los dígitos en una cadena, posiblemente tenga que reasignar y mover la memoria existente si el número es grande. Puede que tenga que verificar una serie de configuraciones regionales para decidir si su país usa "," o ".", Podría tener que hacer un montón de conversiones Unicode.
Luego, al buscar la longitud tiene que escanear toda la cadena, una vez más teniendo en cuenta el Unicode y cualquier configuración local específica, como - ¿está en un idioma de la derecha a la izquierda?
Alternativamente:
digits = floor( log10( number ) ) + 1;
El hecho de que esto sea más difícil de hacer en papel no significa que sea difícil para una computadora. De hecho, una buena regla en computación de alto rendimiento parece haber sido: si algo es difícil para un ser humano (dinámica de fluidos, representación en 3D) es fácil para una computadora y si es fácil para un ser humano (reconocimiento facial, detectar una voz en un habitación ruidosa) ¡es difícil para una computadora!
En general, puede suponer que las funciones matemáticas compiladas log / sin / cos, etc. han sido una parte importante del diseño de la computadora durante 50 años. Entonces, incluso si no se asignan directamente a una función de hardware en la FPU, puede apostar que la implementación alternativa es bastante eficiente.
En cuanto a los tres métodos que propone para "determinar el número de dígitos necesarios para representar un número dado en una base determinada", en realidad no me gustan ninguno de ellos; Prefiero el método que doy a continuación en su lugar.
Re su método n. ° 1 (cadenas): cualquier cosa que implique la conversión de ida y vuelta entre cadenas y números suele ser muy lenta.
Re su método # 2 (temp / = 10): Esto es fatalmente defectuoso porque asume que x / 10 siempre significa "x dividido por 10". Pero en muchos lenguajes de programación (p. Ej .: C, C ++), si "x" es un tipo entero, entonces "x / 10" significa "división entera", que no es lo mismo que división de coma flotante, y presenta redondee los errores en cada iteración, y se acumulan en una fórmula recursiva, como su solución # 2 usa.
Re su método # 3 (registros): es un error para grandes números (al menos en C, y probablemente también en otros idiomas), porque los tipos de datos de coma flotante tienden a no ser tan precisos como los enteros de 64 bits.
Por lo tanto, me desagradan los 3 de esos métodos: # 1 funciona pero es lento, # 2 está roto, y # 3 es defectuoso para números grandes. En cambio, prefiero esto:
unsigned NumberOfDigits (uint64_t Number, unsigned Base)
{
unsigned Digits = 1;
uint64_t Power = 1;
while ( Number / Power >= Base )
{
++Digits;
Power *= Base;
}
return Digits;
}
Este algoritmo también podría ser bueno, suponiendo que:
- El número es entero y codificado en binario (<< la operación es barata)
No conocemos los límites numéricos
var num = 123456789L; var len = 0; var tmp = 1L; while(tmp < num) { len++; tmp = (tmp << 3) + (tmp << 1); }
Este algoritmo debería tener una velocidad comparable a for-loop (2), pero un poco más rápida debido a (2 bit-shift, sumar y restar, en lugar de división).
En cuanto al algoritmo Log10, le dará solo una respuesta aproximada (que es casi real, pero aún así), ya que la fórmula analítica para calcular la función Log tiene un ciclo infinito y no se puede calcular con precisión Wiki .
Mantenlo simple:
long long int a = 223452355415634664;
int x;
for (x = 1; a >= 10; x++)
{
a = a / 10;
}
printf("%d", x);
No lo sé, y la respuesta puede ser diferente dependiendo de cómo se implemente su idioma individual.
Entonces, ¡prueba de estrés! Implementa las tres soluciones. Ejecútelos de 1 a 1,000,000 (u otro conjunto enorme de números que sea representativo de los números con los que se ejecutará la solución) y tiempo de duración de cada uno de ellos.
Ponga sus soluciones una contra la otra y déjelos pelear. Como gladiadores intelectuales. Tres algoritmos entran! ¡Un algoritmo se va!
Obviamente, puede eliminar el método 1 de la competencia, porque el algoritmo atoi / toString que utiliza sería similar al método 2.
La velocidad del Método 3 depende de si el código se está compilando para un sistema cuyo conjunto de instrucciones incluye la base de registro 10.
Para enteros muy grandes, el método de registro es mucho más rápido. Por ejemplo, con un número de 2491327 dígitos (el 11920928. ° número de Fibonacci, si le importa), Python tarda varios minutos en ejecutar el algoritmo de división por 10, y milisegundos en ejecutar 1+floor(log(n,10)) .
Puede usar una solución recursiva en lugar de un bucle, pero de alguna manera similar:
@tailrec
def digits (i: Long, carry: Int=1) : Int = if (i < 10) carry else digits (i/10, carry+1)
digits (8345012978643L)
Con los largos, la imagen puede cambiar: mida los números pequeños y largos independientemente contra diferentes algoritmos, y elija el apropiado, dependiendo de su entrada típica. :)
Por supuesto, nada es mejor que un interruptor:
switch (x) {
case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: return 1;
case 10: case 11: // ...
case 99: return 2;
case 100: // you get the point :)
default: return 10; // switch only over int
}
excepto un plain-o-array:
int [] size = {1,1,1,1,1,1,1,1,1,2,2,2,2,2,... };
int x = 234561798;
return size [x];
Algunas personas te dirán que optimices el tamaño del código, pero ya sabes, optimización prematura ...
Siempre hay este método:
n = 1;
if ( i >= 100000000 ) { n += 8; i /= 100000000; }
if ( i >= 10000 ) { n += 4; i /= 10000; }
if ( i >= 100 ) { n += 2; i /= 100; }
if ( i >= 10 ) { n += 1; }
Tenía curiosidad después de ver los resultados de @ daniel.sedlacek, así que realicé algunas pruebas utilizando Swift para números que tenían más de 10 dígitos. Ejecuté el siguiente script en el patio de recreo.
let base = [Double(100090000000), Double(100050000), Double(100050000), Double(100000200)]
var rar = [Double]()
for i in 1...10 {
for d in base {
let v = d*Double(arc4random_uniform(UInt32(1000000000)))
rar.append(v*Double(arc4random_uniform(UInt32(1000000000))))
rar.append(Double(1)*pow(1,Double(i)))
}
}
print(rar)
var timeInterval = NSDate().timeIntervalSince1970
for d in rar {
floor(log10(d))
}
var newTimeInterval = NSDate().timeIntervalSince1970
print(newTimeInterval-timeInterval)
timeInterval = NSDate().timeIntervalSince1970
for d in rar {
var c = d
while c > 10 {
c = c/10
}
}
newTimeInterval = NSDate().timeIntervalSince1970
print(newTimeInterval-timeInterval)
Resultados de 80 elementos
0.105069875717163 para piso (log10 (x))
0.867973804473877 para div 10 iteraciones
Use la solución más simple en cualquier lenguaje de programación que esté usando. No puedo pensar en un caso donde contar dígitos en un entero sería el cuello de botella en cualquier programa (útil).
C, C ++:
char buffer[32];
int length = sprintf(buffer, "%ld", (long)123456789);
Haskell:
len = (length . show) 123456789
JavaScript:
length = String(123456789).length;
PHP:
$length = strlen(123456789);
Visual Basic (no probado):
length = Len(str(123456789)) - 1
log(x,n)-mod(log(x,n),1)+1
Donde x es la base yn es el número.
Condiciónes de la prueba
- Sistema de numeración decimal
- Enteros positivos
- Hasta 10 dígitos
- Idioma: ActionScript 3
Resultados
dígitos: [1,10],
no. de carreras: 1,000,000
muestra al azar: 8777509,40442298,477894,329950,513,91751410,313,3159,131309,2
resultado: 7,8,6,6,3,8,3,4,6,1
CONVERSIÓN A STRING: 724ms
CÁLCULO LOGARITMICO: 349ms
DIV 10 ITERACIÓN: 229ms
ACONDICIONAMIENTO MANUAL: 136ms
Nota: el autor se abstiene de hacer conclusiones para números con más de 10 dígitos.
Guión
package {
import flash.display.MovieClip;
import flash.utils.getTimer;
/**
* @author Daniel
*/
public class Digits extends MovieClip {
private const NUMBERS : uint = 1000000;
private const DIGITS : uint = 10;
private var numbers : Array;
private var digits : Array;
public function Digits() {
// ************* NUMBERS *************
numbers = [];
for (var i : int = 0; i < NUMBERS; i++) {
var number : Number = Math.floor(Math.pow(10, Math.random()*DIGITS));
numbers.push(number);
}
trace(''Max digits: '' + DIGITS + '', count of numbers: '' + NUMBERS);
trace(''sample: '' + numbers.slice(0, 10));
// ************* CONVERSION TO STRING *************
digits = [];
var time : Number = getTimer();
for (var i : int = 0; i < numbers.length; i++) {
digits.push(String(numbers[i]).length);
}
trace(''/nCONVERSION TO STRING - time: '' + (getTimer() - time));
trace(''sample: '' + digits.slice(0, 10));
// ************* LOGARITMIC CALCULATION *************
digits = [];
time = getTimer();
for (var i : int = 0; i < numbers.length; i++) {
digits.push(Math.floor( Math.log( numbers[i] ) / Math.log(10) ) + 1);
}
trace(''/nLOGARITMIC CALCULATION - time: '' + (getTimer() - time));
trace(''sample: '' + digits.slice(0, 10));
// ************* DIV 10 ITERATION *************
digits = [];
time = getTimer();
var digit : uint = 0;
for (var i : int = 0; i < numbers.length; i++) {
digit = 0;
for(var temp : Number = numbers[i]; temp >= 1;)
{
temp/=10;
digit++;
}
digits.push(digit);
}
trace(''/nDIV 10 ITERATION - time: '' + (getTimer() - time));
trace(''sample: '' + digits.slice(0, 10));
// ************* MANUAL CONDITIONING *************
digits = [];
time = getTimer();
var digit : uint;
for (var i : int = 0; i < numbers.length; i++) {
var number : Number = numbers[i];
if (number < 10) digit = 1;
else if (number < 100) digit = 2;
else if (number < 1000) digit = 3;
else if (number < 10000) digit = 4;
else if (number < 100000) digit = 5;
else if (number < 1000000) digit = 6;
else if (number < 10000000) digit = 7;
else if (number < 100000000) digit = 8;
else if (number < 1000000000) digit = 9;
else if (number < 10000000000) digit = 10;
digits.push(digit);
}
trace(''/nMANUAL CONDITIONING: '' + (getTimer() - time));
trace(''sample: '' + digits.slice(0, 10));
}
}
}
import math
def numdigits(n):
return ( int(math.floor(math.log10(n))) + 1 )
conversión a cadena: Esto tendrá que iterar a través de cada dígito, encontrar el carácter que se asigna al dígito actual, agregar un carácter a una colección de caracteres. A continuación, obtenga la longitud del objeto String resultante. Se ejecutará en O (n) para n = # dígitos.
for-loop: realizará 2 operaciones matemáticas: dividiendo el número por 10 e incrementando un contador. Se ejecutará en O (n) para n = # dígitos.
logarítmico: Llamará a log10 y floor, y add 1. Se ve como O (1) pero no estoy seguro de qué tan rápido son las funciones log10 o floor. Mi conocimiento de este tipo de cosas se ha atrofiado con la falta de uso, por lo que podría haber complejidad oculta en estas funciones.
Así que supongo que todo se reduce a: ¿está buscando asignaciones de dígitos más rápido que múltiples operaciones matemáticas o lo que está sucediendo en log10 ? La respuesta probablemente variará. Podría haber plataformas donde el mapeo de caracteres es más rápido, y otros donde hacer los cálculos es más rápido. También hay que tener en cuenta que el primer método creará un nuevo objeto String que solo existe con el fin de obtener la longitud. Probablemente use más memoria que los otros dos métodos, pero puede o no ser importante.