¿El método de conversión de base más rápido?
https://stackoverflow.com/questions/1235371
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
En este momento estoy trabajando en un proyecto que requiere que un entero se convierta en una cadena base 62 muchas veces por segundo. Cuanto más rápido se complete esta conversión, mejor.
El problema es que estoy teniendo dificultades para que mis propios métodos de conversión de base sean rápidos y confiables. Si uso cadenas, generalmente es confiable y funciona bien, pero es lento. Si uso matrices de caracteres, generalmente es mucho más rápido, pero también es muy desordenado y poco confiable. (Produce corrupción de 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 del modelo SIMD en mi aplicación, entonces, ¿esta operación es paralelizable?
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 ciclo, por lo que cuanto más rápido se ejecute, mejor. El 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';
}
Extraje esto de una clase que es parte de mi aplicación, y parte del código se modifica para que tenga sentido sin su propia clase.
Solución
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 previamente las conversiones en "bloques". Por lo tanto, puede calcular previamente un bloque de conversión de int a texto de tamaño 62 ^ 3 y luego hacer los dígitos 3 a la vez. Siempre que realice el diseño y la búsqueda de memoria de manera eficiente, esto puede ser un poco más rápido en tiempo de ejecución, pero incurre en una penalización de inicio.
Otros consejos
Me siento mal porque no puedo recordar dónde encontré esto originalmente, pero he estado usando esto en mi código y he encontrado que es bastante rápido. Podría modificar esto para que sea más eficiente en ciertos lugares, estoy seguro.
Ah, y me siento peor porque esto está escrito en Java, pero un rápido c & amp; p y refactor podría hacer que funcione 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;
}
}
Fuera de mi alcance, esperaría que una implementación se parezca 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 SIMD optimizable. No hay módulo SIMD.
Si hacemos Modulo nosotros mismos, a su vez podríamos reescribir el ciclo 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 SIMDAR si no fuera por esa búsqueda ...
Aunque todavía puede obtener una buena mejora de velocidad haciendo el módulo para varios valores simultáneamente. Probablemente incluso valga la pena desenrollar el bucle por segunda vez para que pueda procesar los próximos 4 o más módulos mientras se calcula el conjunto anterior (debido a la latencia de la instrucción). Debería poder ocultar latencias de manera bastante efectiva de esta manera. #
Volveré si puedo pensar en una forma de eliminar la búsqueda en la tabla ...
Editar: Dicho esto, dado que el número máximo de dígitos de 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 completamente seguro de que SIMD le otorgaría una gran victoria aquí. Sería un experimento interesante, pero realmente dudo que consigas tanta velocidad sobre el ciclo anterior. Sería interesante intentarlo si alguien no hubiera vertido té sobre el teclado de mi máquina de desarrollo :(
Editar 2: mientras lo pienso. Una constante / 62 puede ser optimizada astutamente por el compilador usando números mágicos de miedo ... así que ni siquiera creo que el bucle anterior haría una división.
hay problemas de inversión en lo anterior: los pedidos bajos son los primeros 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 al hacerlo en radix * radix chunks En su caso, se necesita un carácter [2] [62 * 62]. Esta matriz se puede construir en el momento de la inicialización (es constante).
Sin embargo, esto debe ser comparado. El costo de la división solía ser ENORME, por lo que ahorrar la mitad de las divisiones era una victoria segura. Depende de la capacidad de almacenar en caché esta tabla de 7000+ bytes y el costo de la división.
Si está teniendo corrupción de montón, tiene problemas más allá del código que está mostrando aquí.
Puede acelerar la clase de cadena reservando el espacio para la cadena antes de comenzar, con string :: reserve.
Su cadena sale en orden inverso, el dígito de 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 va a ser. 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 (dividir entre charsetLength ) puede haber estado causando sus problemas de comparación de cadenas. Con su código original (dividido por charsetLength + 1 ), puede haber diferentes valores de enteros 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 podría estar causando los problemas de corrupción de su montón, 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 cadena en orden inverso (pruébelo con 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)
Toda mi publicación 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 el resultado que esperaba. Sin embargo, esto está optimizado para facilitar la lectura, no para 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;
}
