Algoritmo de conversión de enteros a cadenas un 34% más rápido

Algoritmo optimizado para convertir enteros a cadenas un 34% más rápido

¿Estamos imprimiendo enteros lo suficientemente rápido?

1. Introducción

En la programación informática, convertir un número entero dado a una cadena es una operación común, que se debe hacer por ejemplo antes de imprimir el entero en la pantalla, o imprimirlo en cualquier tipo de archivo de texto, como *.xml, *.json, *.csv, *.txt, etc…

Es bien sabido que los enteros (al igual que todo lo demás) se almacenan en la memoria de la computadora en formato binario, como secuencias de 0 y 1. Por ejemplo:

• el número 12 se representa en memoria como “1100”,
• y el número 29 se representa como “11101”.

Esta es la razón por la cual se necesita esta conversión cada vez que queremos llevarlo a un formato decimal legible por humanos.

• 9 formas en que la IA está mejorando la seguridad de los centros de datos
• Predicciones de rotación en evolución Navegando intervenciones y capacitación nuevamente
• Cómo Getir redujo la duración del entrenamiento de modelos en un 90% con Amazon SageMaker y AWS Batch

En esta historia voy a:

• hacer una descripción general del algoritmo estándar utilizado para esta conversión,
• observar sus optimizaciones existentes,
• proponer mi algoritmo, y
• presentar su comparación experimental.

Veremos que en promedio, mi algoritmo se ejecuta un 25–38% más rápido para enteros de 32 bits, y un 40–58% más rápido para enteros de 64 bits, en comparación con el algoritmo estándar optimizado. Su implementación en lenguaje C++ se puede encontrar en GitHub, como se referencia al final.

Por supuesto, si la aplicación imprime solo unos pocos enteros durante su tiempo de vida, el algoritmo encargado de convertirlos a cadenas nunca será el cuello de botella. Pero en casos en los que la aplicación imprime toneladas de datos en archivos de texto, la eficiencia del algoritmo de conversión comienza a jugar un papel importante. Cuando se trabaja en campos como Ciencia de Datos o Aprendizaje Automático, surge la necesidad de convertir muchos enteros en cadenas, por ejemplo, al exportar un conjunto de datos a un archivo de texto, como *.csv o *.json.

2. El algoritmo estándar de conversión

Dado que convertir enteros a cadenas es una operación común, un algoritmo para esto está implementado en cualquier lenguaje de programación moderno, ya sea como parte del propio lenguaje o como parte de su biblioteca estándar. Y el algoritmo es casi siempre el mismo: el que se basa en obtener y seleccionar repetidamente el último dígito del entero, y continuar con su parte restante.

Para obtener el último dígito del número entero N dado, simplemente calcula el resto de su división entre 10:

“dígito := N mod 10”,

y para seleccionarlo, realiza la división entera en sí:

“N := N / 10”.

Se debe tener en cuenta que, en esta historia, al dividir 2 enteros, asumiremos que solo se toma la parte entera del resultado.

Como ejemplo del algoritmo completo, al imprimir el número “N = 2’167”, se realizarán las siguientes operaciones:

Ten en cuenta que, cuando estamos tratando con enteros de 1 dígito (es decir, en el rango [0..9]), podemos enviar directamente para imprimir, ya que los caracteres correspondientes ya están fijos para cada uno de esos 10 dígitos. Y el resto de la división entre 10 siempre es un entero de 1 dígito.

También podemos observar que este algoritmo muestra los dígitos de N en orden inverso (aquí obtenemos la secuencia de dígitos ‘7’, ‘6’, ‘1’, ‘2’, en lugar de tener ‘2’, ‘1’, ‘6’, ‘7’), por lo que es necesario invertir la secuencia producida al final.

Resumiendo, su pseudocódigo sería así:

var result[0 .. 25] : Array of Characters  // Supongamos un máximo de 25 caracteres// El procedimiento toma un número entero 'N' a imprimir, y llena sus// dígitos decimales en el arreglo 'result'.procedimiento imprimir( N: Integer )    i := 0  // Índice sobre el arreglo 'result'    mientras N > 0        result[ i ] := '0' + (N mod 10)  // Tomar el último dígito        N := ⌊ N / 10 ⌋   // Quitar el último dígito        i := i+1    result[ i ] := '\0'  // Agregar el carácter de terminación 'nulo'    invertir arreglo result[0 .. i-1]

El algoritmo descrito es simple, y podemos implementarlo fácilmente en 3-4 líneas de código. Pero su cuello de botella es que utiliza 2 operaciones relativamente costosas: la división entera y el cálculo del resto, para cada dígito de la notación decimal de N. Es bien sabido que la división entera y el cálculo del resto toman de 4 a 5 veces más tiempo en promedio que la suma, la resta o incluso la multiplicación de 2 enteros. Aquí podemos observar la comparación de tiempo de las operaciones aritméticas mencionadas:

Los experimentos se realizaron con Google Benchmark, en el siguiente sistema:

CPU: Intel Core i7–11800H @ 2.30GHzRAM: 16.0 GBOS: Windows 11 Home, 64 bitsCompiler: MSVC 2022 ( /O2 /Ob2 /MD /GR /Gd )

Veamos si existen métodos más rápidos para imprimir enteros…

3. Optimizaciones existentes

Optimización 1

Una optimización común para el algoritmo descrito consiste en eliminar el último paso de invertir la secuencia de dígitos producida. El truco se presenta bien por ejemplo en [1]. Dentro de esta optimización, escribiremos los dígitos en el búfer directamente en su orden correcto. Y como el propio algoritmo muestra los dígitos del entero N dado de derecha a izquierda, también los escribiremos en el búfer de derecha a izquierda.

El pseudocódigo con esta optimización se verá así:

var result[0 .. 25] : Array of Characters  // Supongamos un máximo de 25 caracteres// La función toma un número entero 'N' para imprimir y devuelve la posición // de su primer carácter convertido en el arreglo 'result'.función imprimir( N: Integer ) : Integer    result[ 25 ] := '\0'  // Colocamos el terminador 'null' al final    i := 25  // Índice sobre el arreglo 'result'    mientras N > 0        i := i-1  // Aquí vamos hacia la izquierda, para colocar el siguiente dígito        result[ i ] := '0' + (N mod 10)  // Tomar el último dígito        N := ⌊ N / 10 ⌋  // Quitar el último dígito    devolver i  // Posición desde donde comienza el entero convertido

Tenga en cuenta que, en este y en todos los demás pseudo-códigos dentro de esta historia, no estamos manejando el caso de imprimir el número “0”. Según todos los algoritmos escritos, “0” se mostrará como una secuencia sin ningún dígito, y es por eso que en casi todos los algoritmos de impresión, la impresión de “0” se realiza en una rama separada. Aquí simplemente omitiremos esa rama por razones de simplicidad.

Otra pequeña ventaja de esta optimización es que no es necesario escribir el carácter nulo de terminación después de cada conversión. En su lugar, podemos escribirlo una sola vez en la última posición del búfer, ya que la posición física del último dígito de N está fija de antemano, y siempre será la penúltima posición en el búfer.

La desventaja de esta optimización es que la posición del primer carácter se vuelve variable, ya que depende del número de dígitos que tiene el número entero N.

Sin embargo, en la práctica, esto no se convierte en un problema, porque los enteros convertidos a menudo se envían rápidamente a un archivo de texto o a la pantalla, por lo que no permanecen en memoria durante mucho tiempo. Y para tales propósitos, no es necesario que los dígitos convertidos se escriban a partir de alguna posición específica de la memoria.

Optimización 2

La siguiente optimización consiste en utilizar la división entera y el cálculo del resto para obtener 2 dígitos de N en un solo paso. Este truco también está bien documentado en [1] y [2]. Para esto, en lugar de calcular repetidamente

“dígito := N mod 10”, seguido por “N := N / 10”,

calcularemos:

“digits := N mod 100”, seguido por “N := N / 100”,

lo cual nos dará los últimos 2 dígitos de N, y luego los eliminaremos.

<img "17"),="" "40"),="" "5="" "5"."="" "92"),="" %="" (almacenando="" (continuando="" 100="5" 100",="" 1:="" 2:="" 3:="" 4:="" 5),paso="" 517="" 517),paso="" 51740="" 51740),paso="" 5174092="" 5174092"=""

Tenga en cuenta que, para imprimir eficientemente esos 2 dígitos obtenidos, aquí deberíamos haber preparado un array de longitud 100 (con índices del 0 al 99, correspondientes a todos los posibles restos “N mod 100”), donde los valores serán pares de caracteres, desde “00”, “01”, “02”, … hasta “98”, “99”.

Dentro de esta optimización, la cantidad de divisiones enteras y cálculos de restos se reduce casi a la mitad.

Finalizando esta parte, quiero llamar su atención sobre el hecho de que incluso con ambas optimizaciones descritas activadas, todavía realizamos un número de divisiones enteras y cálculos de restos proporcional a la cantidad de dígitos en el número entero N proporcionado.

4. Mi algoritmo

Voy a proponer otro algoritmo que acelerará la impresión de enteros en alrededor de 25–38% para enteros de 32 bits y alrededor de 40–58% para enteros de 64 bits. La idea es ¿qué pasa si seleccionamos los dígitos del número entero N no de derecha a izquierda, sino de izquierda a derecha? Entonces, al principio obtendremos su dígito más significativo, luego el siguiente dígito más significativo, y así sucesivamente, hasta que solo quede el dígito menos significativo. Hacer esto se vuelve un poco difícil si no conocemos de antemano la cantidad de dígitos de N, pero dejemos esa pregunta de lado por ahora y asumamos que ya sabemos que hay L dígitos en N.

¿Cómo vamos a obtener el dígito más significativo entonces? Nuevamente, usando la división entera, pero esta vez como:

“dígito := N / 10^(L-1)”

Y ¿cómo vamos a seleccionarlo de N, para poder continuar con la parte restante? Después de saber que el valor del dígito más significativo es ‘d’, podemos hacer la siguiente resta:

“N := N – d*10^(L-1)”

Más tarde repetiremos las operaciones de división y resta, hasta que N se convierta en un número entero de 1 dígito (es decir, en el rango [0..9]), y finalmente también imprimiremos ese dígito. Veamos cómo funcionará el algoritmo para el caso “N = 6’129”. Observa que tiene 4 dígitos, así que aquí comenzamos con “L = 4”:

Puede argumentarse que calcular diferentes potencias de 10 es más consumidor de tiempo que hacer división entera o cálculo de residuos. Y eso sería absolutamente correcto, excepto por un detalle: podemos precalcular todas las potencias de 10 necesarias y usarlas durante toda la ejecución del programa. Para enteros de 32 bits, solo hay 10 potencias diferentes de 10, y para enteros de 64 bits, hay 20 potencias de 10. Entonces, mantenerlas todas precalculadas en la memoria no será un problema.

Entonces, ¿qué tenemos en general? Para imprimir un dígito de N con mi algoritmo, hacemos lo siguiente:

1 división entera, 1 multiplicación y 1 resta,

en comparación con el algoritmo estándar:

1 cálculo de resto y 1 división entera.

En la siguiente sección veremos que mi enfoque es mejor en realidad, porque la multiplicación y la resta juntas requieren menos tiempo de CPU que el cálculo de resto. La comparación experimental de consumo de tiempo de estas operaciones aritméticas se presentó en el capítulo 2.

El pseudocódigo de la parte principal de mi algoritmo podría ser algo así:

var powers_of_10[0 .. 10]: Array of Integers = { 1, 10, 100, 1'000, ..., 100'000'000, 1'000'000'000 }  // Potencias de 10 precalculadas, que se usarán durante la impresiónvar result[0 .. 25]: Array of Characters  // Supongamos un máximo de 25 caracteres// El procedimiento toma un entero 'N' para imprimir y llena sus// caracteres decimales en el array 'result'.procedure print(N: Integer)    L := calculate_digits_count(N)    i := 0  // Índice del array 'result'    while L > 0        digit := ⌊ N / powers_of_10[ L-1 ] ⌋  // Obtener el dígito más a la izquierda        result[i] := '0' + digit   // Escribirlo en el array 'result'        N := N – digit * powers_of_10[ L-1 ]  // Calcular la parte restante        L := L-1  // Ajustar la cantidad de dígitos        i := i+1    result[i] := '\0'  // Agregar el carácter de terminación 'null'

Como mi algoritmo imprime los dígitos de N de izquierda a derecha, quiero llamarlo “Impresora de izquierda a derecha” o simplemente “Impresora LR”.

Lo único que falta es encontrar eficientemente L, la cantidad de dígitos decimales de N. Y por suerte para nosotros, el array precalculado de potencias de 10 también nos ayudará aquí. Podemos simplemente iterar sobre ese array desde las potencias pequeñas hasta las más grandes, hasta encontrar una potencia 10^L que sea mayor que N. Entonces, el exponente L en sí mismo representará la cantidad de dígitos en N.

Por ejemplo, obtener la cantidad de dígitos para “N = 23’504” se verá así:

El pseudocódigo de esa función podría ser así:

// La función toma un entero 'N' y devuelve la cantidad de dígitos.function calculate_digits_count(N: Integer): Integer    // Verificar el caso de números con la máxima cantidad de dígitos    if N >= powers_of_10[9]  // Comparar con la potencia máxima de 10        return 10  // Cantidad de dígitos para esos números    // Caso regular    L := 0    while N >= powers_of_10[L]         L := L+1    return L

Con estas 2 partes, proporcionamos un algoritmo completo para convertir enteros en cadenas.

Nota, como la “Impresora LR” muestra los dígitos de N de izquierda a derecha, no es necesario invertirlos al final. Además, a diferencia de la optimización existente 1, aquí mantenemos la capacidad de especificar dónde en la memoria debe colocarse el primer dígito de N convertido.

La “Impresora LR” se puede utilizar para imprimir números en cualquier base (no solo en base 10). Para hacerlo, solo necesitaremos reemplazar las potencias de 10 precalculadas con las potencias precalculadas de la nueva base.

La implementación de la “Impresora LR” en lenguaje C++ se puede encontrar en GitHub en [3].

Optimización 2 para la “Impresora LR”

Mi algoritmo se puede mejorar con la segunda optimización descrita en la sección “Optimizaciones existentes”, y documentada en [1] y [2]. Si se realiza, en lugar de imprimir el número dado por 1 dígito en cada paso, lo imprimiré por 2 dígitos en un solo paso.

Veamos cómo se ejecutará, por ejemplo, con el número “N = 4’610’937”. Aquí L=7, y comenzamos dividiendo N entre 10^(L-2)=10’000 esta vez:

Al habilitar esto, gastaremos:

1 división entera, 1 multiplicación y 1 resta,

por cada 2 dígitos del número de entrada.

Aquí nuevamente, los dígitos se obtendrán en su orden natural, de izquierda a derecha, por lo que no es necesario invertirlos al final.

La implementación de “Impresora LR” con la segunda optimización habilitada también se puede encontrar en GitHub en [3].

5. Comparación experimental con algoritmos existentes

Hacer una comparación experimental es esencial para este tipo de trabajo, por lo que en este capítulo presentaré los resultados de la comparación entre los siguientes algoritmos de impresión de enteros:

• el algoritmo estándar con la primera optimización (etiquetado como “Std”),
• mi algoritmo “Impresora LR” (etiquetado como “LR”),
• el algoritmo estándar con la segunda optimización también (etiquetado como “Std [2-dig]”), y
• “Impresora LR” con la segunda optimización (etiquetado como “LR [2-dig]”).

Cada uno de estos algoritmos se prueba tanto en enteros de 32 bits como de 64 bits, con diferentes cantidades de dígitos de los números de entrada.

Impresión de números en base=10:

Los resultados al imprimir en base=10 (el caso ordinario) son:

Para enteros de 32 bits, podemos ver que la ganancia de “LR printer” en comparación con la impresora estándar es de aproximadamente 30-38%. La ganancia al imprimir con la segunda optimización (imprimiendo 2 dígitos en un solo paso) es menor, alrededor del 13-28%. Esto es totalmente esperado, ya que en general solo realizamos 2 o 4 pasos en ese caso.

Cuando se trata de imprimir enteros de 64 bits, el rendimiento de mi algoritmo es aún mejor. “LR printer” funciona alrededor de 40-50% más rápido que el algoritmo estándar. Y con la segunda optimización habilitada para ambos, “LR printer” funciona 47-58% más rápido.

El porcentaje en el título de esta historia se eligió abordando el caso más común: cuando estamos en base=10, trabajando con enteros de 32 bits y asumiendo que tienen muchos dígitos. Para ese caso, la ganancia en rendimiento de “LR printer” sobre el algoritmo estándar fue del 30-38%, por lo que tomando el promedio sería alrededor del 34%.

Imprimir números en base=3:

También veamos si los resultados difieren significativamente al imprimir enteros en otra base. Observaremos la impresión en base=3:

Como podemos ver aquí, para enteros de 32 bits la ganancia de rendimiento de “LR-printer” sobre el algoritmo estándar es de alrededor del 25-33%, lo cual generalmente corresponde a la diferencia en el rendimiento de las operaciones aritméticas utilizadas.

Y para enteros de 64 bits, la ganancia de rendimiento de “LR-printer” es de alrededor del 50-55% para números cortos (8 dígitos) y del 27-30% para números largos (36 dígitos).

Observaciones generales

En general, la base en la que se imprimen los enteros no afecta mucho la ganancia de rendimiento relativa, ya que la cantidad de operaciones a realizar durante la impresión es proporcional a la cantidad de dígitos que tienen los números de entrada, no al número de posibles valores que esos dígitos puedan tener.

Casi siempre ocurre que a mayor cantidad de dígitos, más “LR-printer” (o su variación “LR-printer [2-dig]”) superará al algoritmo de impresión estándar (o su variación “2-dig”). Esto también es claro, porque cuanto más dígitos tengamos, menos impacto tendrán las instrucciones fuera del bucle (como llamar una función desde otra, o colocar el carácter de terminación nulo).

Y en general, al imprimir enteros de 64 bits, los resultados son más impresionantes tanto para “LR-printer” como para la variación “LR-printer [2-dig]”.

Personalmente, estos resultados son bastante notables para mí.

6. Conclusión

Hemos presentado un nuevo algoritmo para convertir enteros en cadenas, y lo hemos llamado “LR printer”. Funciona alrededor del 25-38% más rápido para enteros de 32 bits y alrededor del 40-58% más rápido para enteros de 64 bits, en comparación con el algoritmo de conversión estándar optimizado. Nuestro algoritmo puede funcionar en cualquier base numérica (no solo en la base 10 ordinaria).

El algoritmo que convierte enteros en cadenas nunca es un cuello de botella para aplicaciones que solo imprimen unos pocos números durante su vida útil. Pero para otros tipos de aplicaciones, que generan automáticamente archivos de texto como *.csv, *xml o *.json, la eficiencia del algoritmo de conversión es importante. Esto es especialmente cierto si esos archivos de texto van a contener muchos números, como ocurre al exportar conjuntos de datos grandes.

¡Muchas gracias por leer hasta el final! ¡Estaré encantado de leer cualquier comentario a continuación!

Expreso mi gratitud a David Ayrapetyan (https://www.linkedin.com/in/davidayrapetyan/), por revisar cuidadosamente el borrador de esta historia y proponer múltiples mejoras contextuales y correcciones gramaticales.

Agradezco a Hayk Aslanyan (https://www.linkedin.com/in/haykaslanyan/), por realizar la revisión técnica del borrador y proponer otras mejoras.

Diseño de ilustraciones por Asya Papyan: https://www.behance.net/asyapapyan

Si disfrutaste leyendo esta historia, puedes encontrarme en LinkedIn en: https://www.linkedin.com/in/tigran-hayrapetyan-88989b12/

Referencias

[1]: “Conversión de entero a cadena” — https://tia.mat.br/posts/2014/06/23/integer_to_string_conversion.html

[2]: “Tres consejos de optimización para C++” — https://www.facebook.com/notes/10158791579037200/

[3]: “Implementación del impresor LR en lenguaje C++” — https://github.com/tigranh/lr_printer

We will continue to update Zepes; if you have any questions or suggestions, please contact us!