¿El método de conversión de base más rápido?

En este momento estoy trabajando en un proyecto que requiere que un entero se convierta en una cadena base 62 varias veces por segundo. Cuanto más rápido se complete esta conversión, mejor.

El problema es que me cuesta mucho conseguir que mis propios métodos de conversión base sean rápidos y confiables. Si uso cadenas, generalmente es confiable y funciona bien, pero es lento. Si uso arrays de caracteres, generalmente es mucho más rápido, pero también es muy desordenado y poco confiable. (Produce corrupción en el montón, la comparación de cadenas que deben coincidir devuelve un negativo, etc.)

Entonces, ¿cuál es la forma más rápida y confiable de convertir de un entero muy grande a una clave base 62? En el futuro, planeo utilizar el código de modelo SIMD en mi aplicación, ¿es esta operación paralelizable en absoluto?

EDITAR: Esta operación se realiza varios millones de veces por segundo; tan pronto como finaliza la operación, comienza de nuevo como parte de un bucle, por lo que cuanto más rápido se ejecuta, mejor. El número entero que se está convirtiendo es de tamaño arbitrario y puede ser fácilmente tan grande como un entero de 128 bits (o más grande).

EDITAR: Esta es la función que estoy usando actualmente.

char* charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; int charsetLength = (int)(strlen(charset)); //maxChars is an integer specifying the maximum length of the key char* currentKey = new char[maxChars]; void integerToKey(unsigned long long location) { unsigned long long num = location; int i = 0; for(; num > 0; i++) { currentKey[i] = charset[num % (charsetLength)]; num /= charsetLength + 1; } currentKey[i + 1] = '\0'; } 

Saqué esto de una clase que forma parte de mi aplicación, y parte del código se modifica para que tenga sentido sin su clase propietaria.

Probablemente lo que quieres es alguna versión de itoa. Aquí hay un enlace que muestra varias versiones de itoa con pruebas de rendimiento: http://www.jb.man.ac.uk/~slowe/cpp/itoa.html

En general, sé de dos maneras de hacer esto. Una forma es realizar divisiones sucesivas para quitar un dígito a la vez. Otra forma es calcular las conversiones en “bloques”. Por lo tanto, podría calcular previamente un bloque de int a conversión de texto de tamaño 62 ^ 3 y luego hacer los dígitos 3 a la vez. Siempre que realice el diseño de la memoria y la búsqueda de manera eficiente, esto puede ser un poco más rápido en el tiempo de ejecución pero incurre en una penalización de inicio.

Fuera de mi cabeza, esperaría que una implementación se pareciera mucho a esto.

 const char lookUpTable[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' }; std::string ConvertToBase62( int integer ) { char res[MAX_BASE62_LENGTH]; char* pWritePos = res; int leftOver = integer; while( leftOver ) { int value62 = leftOver % 62; *pWritePos = lookUpTable[value62]; pWritePos++; leftOver /= value62; } *pWritePos = 0; return std::string( res ); } 

Por el momento esto no es muy optimizable SIMD. No hay módulo SIMD.

Si hacemos Modulo nosotros mismos, a su vez podríamos reescribir el bucle de la siguiente manera.

  while( leftOver ) { const int newLeftOver = leftOver / 62; int digit62 = leftOver - (62 * newLeftOver); *pWritePos = lookUpTable[digit62]; pWritePos++; leftOver = newLeftOver; } 

Ahora tenemos algo que sería fácil de SIMD si no fuera por esa búsqueda …

Aunque aún puede obtener una buena mejora de velocidad haciendo el módulo para varios valores simultáneamente. Probablemente valdría la pena desenrollar el bucle una segunda vez para que pueda procesar los próximos 4 o más módulos mientras se calculan los conjuntos anteriores (debido a la latencia de las instrucciones). Deberías poder ocultar las latencias de manera bastante efectiva de esta manera. #

Volveré si se me ocurre una manera de eliminar la búsqueda en la tabla …

Edición: Dicho esto, como el número máximo de dígitos base62 que puede obtener de un entero de 32 bits es 6, debería poder desenrollar completamente el bucle y procesar los 6 dígitos simultáneamente. No estoy del todo seguro de que SIMD te dé una gran victoria aquí. Sería un experimento interesante, pero realmente dudo que obtendrías tanta velocidad en el circuito de arriba. Sería interesante probarlo si alguien no hubiera echado té sobre el teclado de mi máquina dev 🙁

Edit 2: mientras lo pienso. Una constante / 62 puede ser optimizada astutamente por el comstackdor usando números mágicos de miedo … así que ni siquiera creo que el bucle anterior haría una división.

Me siento mal porque no recuerdo dónde lo encontré originalmente, pero lo he estado usando en mi código y lo he encontrado bastante rápido. Podría modificar esto para ser más eficiente en ciertos lugares, estoy seguro.

Ah, y me siento peor porque esto está escrito en Java, pero un c & p y un refactor rápidos podrían hacerlo funcionar en c ++

 public class BaseConverterUtil { private static final String baseDigits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; public static String toBase62( int decimalNumber ) { return fromDecimalToOtherBase( 62, decimalNumber ); } public static String toBase36( int decimalNumber ) { return fromDecimalToOtherBase( 36, decimalNumber ); } public static String toBase16( int decimalNumber ) { return fromDecimalToOtherBase( 16, decimalNumber ); } public static String toBase8( int decimalNumber ) { return fromDecimalToOtherBase( 8, decimalNumber ); } public static String toBase2( int decimalNumber ) { return fromDecimalToOtherBase( 2, decimalNumber ); } public static int fromBase62( String base62Number ) { return fromOtherBaseToDecimal( 62, base62Number ); } public static int fromBase36( String base36Number ) { return fromOtherBaseToDecimal( 36, base36Number ); } public static int fromBase16( String base16Number ) { return fromOtherBaseToDecimal( 16, base16Number ); } public static int fromBase8( String base8Number ) { return fromOtherBaseToDecimal( 8, base8Number ); } public static int fromBase2( String base2Number ) { return fromOtherBaseToDecimal( 2, base2Number ); } private static String fromDecimalToOtherBase ( int base, int decimalNumber ) { String tempVal = decimalNumber == 0 ? "0" : ""; int mod = 0; while( decimalNumber != 0 ) { mod = decimalNumber % base; tempVal = baseDigits.substring( mod, mod + 1 ) + tempVal; decimalNumber = decimalNumber / base; } return tempVal; } private static int fromOtherBaseToDecimal( int base, String number ) { int iterator = number.length(); int returnValue = 0; int multiplier = 1; while( iterator > 0 ) { returnValue = returnValue + ( baseDigits.indexOf( number.substring( iterator - 1, iterator ) ) * multiplier ); multiplier = multiplier * base; --iterator; } return returnValue; } } 

Hay problemas de inversión en lo anterior. Las órdenes bajas son lo primero en la cadena generada. No sé si eso es realmente un problema porque depende del uso posterior de la cadena generada.

Generalmente, este tipo de conversión de radix puede acelerarse haciéndolo en radix * radix chunks. En su caso, se necesita un char [2] [62 * 62]. Esta matriz se puede construir en el momento de la inicialización (es const).

Esto debe ser un punto de referencia sin embargo. El costo de la división solía ser ENORME por lo que ahorrar la mitad de las divisiones era una ganancia segura. Depende de la capacidad de almacenar en caché esta tabla de más de 7000 bytes y del costo de la división.

Si está sufriendo daños en el montón, tiene problemas más allá del código que se muestra aquí.

Puede hacer que la clase de cadena sea más rápida si reserva el espacio para la cadena antes de comenzar, con cadena :: reserve.

Su cadena sale en orden inverso, el dígito base-62 de orden inferior es el primer carácter de la cadena. Esto podría explicar sus problemas de comparación.

Su implementación es casi tan rápida como se va a obtener. Sin embargo, sugeriría un par de cambios:

 void integerToKey(unsigned long long location) { unsigned long long num = location; int i = 0; for(; num > 0; i++) { currentKey[i] = charset[num % (charsetLength)]; num /= charsetLength; // use charsetLength } currentKey[i] = '\0'; // put the null after the last written char } 

El primer cambio (divide por charsetLength ) puede haber estado causando problemas de comparación de cadenas. Con su código original (dividido por charsetLength + 1 ), puede haber diferentes valores de entero que se convierten incorrectamente a la misma cadena. Para la base 62, entonces 0 y 62 se codificarían como "0" .

Es difícil decir si alguno de los cambios anteriores causaría los problemas de corrupción del montón reportados, sin un poco más de contexto (como el valor de maxChars ).

Además, debe tener en cuenta que el código anterior escribirá los dígitos de la representación de la cadena en orden inverso (pruébelo con la base 10 y convierta un número como 12345 para ver a qué me refiero). Sin embargo, esto puede no importar para su aplicación.

Aquí hay una solución que uso en PHP para Base 10 a N (62 en este ejemplo)
Mi publicación completa está aquí: http://ken-soft.com/?p=544

 public class BNID { // Alphabet of Base N (This is a Base 62 Implementation) var $bN = array( '0','1','2','3','4','5','6','7','8','9', 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z', 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' ); var $baseN; function __construct() { $this->baseN = count($this->bN); } // convert base 10 to base N function base10ToN($b10num=0) { $bNnum = ""; do { $bNnum = $this->bN[$b10num % $this->baseN] . $bNnum; $b10num /= $this->baseN; } while($b10num >= 1); return $bNnum; } // convert base N to base 10 function baseNTo10($bNnum = "") { $b10num = 0; $len = strlen($bNnum); for($i = 0; $i < $len; $i++) { $val = array_keys($this->bN, substr($bNnum, $i, 1)); $b10num += $val[0] * pow($this->baseN, $len - $i - 1); } return $b10num; } } 

Estoy acumulando otra respuesta porque un par de respuestas que probé no produjeron la salida que esperaba. Sin embargo, esto está optimizado para facilitar la lectura, no la velocidad.

 string toStr62(unsigned long long num) { string charset = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; int base = charset.length(); string str = num ? "" : "0"; while (num) { str = charset.substr(num % base, 1) + str; num /= base; } return str; }