método de conversão de base mais rápida?
https://stackoverflow.com/questions/1235371
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Agora eu estou trabalhando em um projeto que requer um número inteiro a ser convertido para uma string base 62 muitas vezes por segundo. O mais rápido desta conversão for concluída, o melhor.
O problema é que eu estou tendo dificuldade em obter os meus próprios métodos de conversão de base para ser rápido e confiável. Se eu usar cordas, é geralmente de confiança e funciona bem, mas é lento. Se eu usar matrizes de caracteres, é geralmente muito mais rápido, mas também é muito confuso e não confiável. (Produz corrupção de pilha, a comparação de strings que deve corresponder retornar um negativo, etc.)
Então, qual é a maneira mais rápida e mais confiável de conversão de um grande número inteiro a uma chave de base 62? No futuro, pretendo utilizar código do modelo SIMD no meu aplicativo, assim é esta paralelizável operação em tudo?
EDIT: Esta operação é realizada vários milhões de vezes por segundo; assim que os acabamentos de operação, ele começa novamente como parte de um ciclo, de modo mais rápido ele é executado, o melhor. O número inteiro ser convertido é de tamanho arbitrário, e pode facilmente ser tão grande quanto um bit inteiro 128 (ou maior).
EDIT:. Esta é a função que estou usando atualmente
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';
}
Eu rasguei isto fora de uma classe que faz parte da minha candidatura, e parte do código é modificado para que ele faz sans sentido sua classe proprietária.
Solução
Provavelmente o que você quer é alguma versão do itoa. Aqui está um link que mostra várias versões do itoa com testes de desempenho: http://www.jb.man.ac.uk/~slowe /cpp/itoa.html
Em geral, eu sei de duas maneiras de fazer isso. Uma forma para realizar divisões sucessivas a tira fora um dígito de cada vez. Outra maneira é conversões precompute em "blocos". Então, você poderia precompute um bloco de int para conversão de texto de tamanho 62 ^ 3, em seguida, fazer os dígitos 3 de cada vez. Desde que você faça o layout memória e pesquisa de forma eficiente este pode ser um pouco mais rápido em tempo de execução, mas incorre na penalidade de inicialização.
Outras dicas
Eu me sinto mal porque eu não consigo lembrar onde eu originalmente encontrada isso, mas eu tenho usado isso no meu código e tê-lo encontrado para ser muito rápido. Você poderia modificar isso para ser mais eficiente em certos lugares, estou certo.
Oh e eu me sinto pior, porque este é escrito em Java, mas uma rápida c & p e refatorar poderia fazê-lo funcionar no 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;
}
}
Em cima da cabeça me eu esperaria uma implementação a olhar muito como esta.
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 );
}
No momento, isso não é muito SIMD optimisable. Não há modulo SIMD.
Se fizermos Modulo nós mesmos, por sua vez poderia reescrever o loop da seguinte forma.
while( leftOver )
{
const int newLeftOver = leftOver / 62;
int digit62 = leftOver - (62 * newLeftOver);
*pWritePos = lookUpTable[digit62];
pWritePos++;
leftOver = newLeftOver;
}
Agora temos algo que seria fácil de SIMD, se não fosse por essa pesquisa ...
Embora você ainda pode obter uma melhoria boa velocidade, fazendo o modulo para vários valores simultaneamente. Ele provavelmente até valer a pena desenrolar o loop de uma segunda vez para que você possa processar os próximos 4 ou mais modulos enquanto o conjunto anterior são cálculo (devido à latência de instrução). Você deve ser capaz de esconder latências bastante eficaz desta forma. #
Eu vou voltar se eu posso pensar em uma maneira de eliminar a tabela de pesquisa ...
Edit: Dito isto como o número máximo de dígitos base62 que você pode obter de um inteiro de 32 bits é de 6 você deve apenas ser capaz de totalmente desanuviar o loop e processar todos os 6 dígitos simultaneamente. Eu não sou inteiramente certo SIMD lhe daria muito de uma vitória aqui. Seria uma experiência interessante, mas eu realmente duvido que você deseja obter tudo o que muita velocidade ao longo do loop acima. Seria interessante experimentá-lo se alguém não tivesse derramado chá sobre o teclado da minha máquina dev: (
Edit 2: enquanto eu penso sobre isso. Uma constante / 62 pode ser habilmente otimizado pelo compilador usando números mágicos assustadores ... então eu nem sequer contar o loop acima faria uma divisão.
Há reverter problemas no exemplo acima - as ordens baixas vir em primeiro lugar na cadeia gerada -. Eu não sei se isso é realmente um problema, porque depende da utilização posterior da cadeia gerada
Geralmente este tipo de conversão de raiz pode ser acelerado por fazê-lo na raiz * pedaços Radix No seu caso, é necessário um char [2] [62 * 62]. Esta matriz pode ser construída em tempo de inicialização (isto é const).
Isto deve ser aferido embora. O custo divisão costumava ser enorme para salvar metade das divisões era uma vitória certa. Depende da capacidade de armazenar em cache esta tabela 7000+ byte eo custo da divisão.
Se você está recebendo corrupção de pilha, você tem problemas para além do código que você está mostrando aqui.
Você pode fazer a classe string mais rápido, reservando o espaço para a cadeia antes de começar, com a corda :: reserva.
A seqüência está saindo em ordem inversa, a ordem inferior base-62 dígitos é o primeiro caractere na cadeia. Isso pode explicar os seus problemas de comparação.
A sua implementação é praticamente tão rápido quanto ele vai ficar. Gostaria de sugerir algumas mudanças no entanto:
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
}
A primeira mudança (dividir por charsetLength) podem ter sido causando seus problemas de comparação de string. Com o seu código original (dividindo por charsetLength + 1), pode haver diferentes valores de número inteiro que incorretamente são convertidos para a mesma cadeia. Para a base 62, então ambos 0 e 62 seria codificado como "0".
É difícil dizer se uma das alterações acima seria causando seus problemas pilha corrupção denunciados, sem mais contexto bit (tais como o valor de maxChars).
Além disso, você deve estar ciente de que o código acima irá escrever os dígitos da representação de seqüência em ordem inversa (experimentá-lo com base 10 e converter um número como 12345 para ver o que quero dizer). Isto pode não importa para a sua aplicação, no entanto.
Aqui está uma solução que eu uso em php para Base de Dados de 10 a N (62 neste exemplo)
Todo o meu post é aqui: 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;
}
}
Eu estou acumulando com outra resposta, porque um par de respostas Tentei não produzir o resultado que eu esperava. Embora, este é otimizada para facilitar a leitura, não a velocidade.
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;
}
