Metodo di conversione base più veloce?
https://stackoverflow.com/questions/1235371
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
In questo momento sto lavorando a un progetto che richiede che un numero intero sia convertito in una stringa 62 di base più volte al secondo. Più veloce è questa conversione, meglio è.
Il problema è che non riesco a far sì che i miei metodi di conversione di base siano veloci e affidabili. Se uso le stringhe, è generalmente affidabile e funziona bene, ma è lento. Se utilizzo array di caratteri, è generalmente molto più veloce, ma è anche molto disordinato e inaffidabile. (Produce corruzione dell'heap, confronto di stringhe che dovrebbero corrispondere a restituire un negativo, ecc.)
Quindi qual è il modo più veloce e affidabile per convertire da un intero molto grande in una chiave 62 di base? In futuro, ho intenzione di utilizzare il codice modello SIMD nella mia applicazione, quindi questa operazione è assolutamente parallelizzabile?
EDIT: questa operazione viene eseguita diverse milioni di volte al secondo; non appena l'operazione termina, ricomincia come parte di un ciclo, quindi più veloce è, meglio è. L'intero da convertire ha dimensioni arbitrarie e può essere facilmente grande quanto un intero a 128 bit (o superiore).
EDIT: questa è la funzione che sto attualmente utilizzando.
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';
}
L'ho strappato da una classe che fa parte della mia applicazione e parte del codice viene modificato in modo che abbia senso senza la sua classe proprietaria.
Soluzione
Probabilmente quello che vuoi è una versione di itoa. Ecco un link che mostra varie versioni di itoa con test delle prestazioni: http://www.jb.man.ac.uk/~slowe /cpp/itoa.html
In generale, conosco due modi per farlo. Un modo per eseguire le divisioni successive per eliminare una cifra alla volta. Un altro modo è pre-calcolare le conversioni in "blocchi". Quindi potresti precompilare un blocco di int in una conversione di testo di dimensioni 62 ^ 3, quindi fare le cifre 3 alla volta. Se esegui il layout della memoria e la ricerca in modo efficiente, questo può essere leggermente più veloce in fase di esecuzione ma comporta una penalità all'avvio.
Altri suggerimenti
Mi sento male perché non ricordo dove l'ho trovato inizialmente, ma lo sto usando nel mio codice e l'ho trovato abbastanza veloce. Potresti modificarlo per renderlo più efficiente in certi posti, ne sono sicuro.
Oh e mi sento peggio perché questo è scritto in Java, ma un veloce c & amp; pe refactor potrebbero farlo funzionare in 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;
}
}
Dalla parte superiore della mia testa mi aspetto che un'implementazione assomiglierà molto a questa.
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 );
}
Al momento questo non è molto ottimizzabile per SIMD. Non esiste un modulo SIMD.
Se facciamo Modulo da soli, possiamo a nostra volta riscrivere il ciclo come segue.
while( leftOver )
{
const int newLeftOver = leftOver / 62;
int digit62 = leftOver - (62 * newLeftOver);
*pWritePos = lookUpTable[digit62];
pWritePos++;
leftOver = newLeftOver;
}
Ora abbiamo qualcosa che sarebbe facile da SIMD se non fosse per quella ricerca ...
Sebbene sia ancora possibile ottenere un buon miglioramento della velocità eseguendo il modulo per più valori contemporaneamente. Probabilmente varrebbe la pena srotolare il loop una seconda volta in modo da poter elaborare i 4 moduli successivi mentre il set precedente sta calcolando (a causa della latenza delle istruzioni). Dovresti essere in grado di nascondere le latenze in modo abbastanza efficace in questo modo. #
Tornerò se riesco a pensare a un modo per eliminare la ricerca della tabella ...
Modifica: Detto questo, poiché il numero massimo di cifre base62 che puoi ottenere da un numero intero a 32 bit è 6, dovresti essere in grado di svolgere completamente il ciclo ed elaborare tutte e 6 le cifre contemporaneamente. Non sono del tutto sicuro che SIMD ti darebbe molta vittoria qui. Sarebbe un esperimento interessante ma dubito davvero che avresti accelerato così tanto nel ciclo sopra. Sarebbe interessante provarlo se qualcuno non avesse versato il tè sulla tastiera della mia macchina di sviluppo :(
Modifica 2: mentre ci penso. Una costante / 62 può essere abilmente ottimizzata dal compilatore usando numeri magici spaventosi ... quindi non credo nemmeno che il ciclo sopra farebbe una divisione.
ci sono problemi di inversione in precedenza - gli ordini bassi vengono prima nella stringa generata - Non so se questo sia effettivamente un problema perché dipende dal successivo utilizzo della stringa generata.
In genere questo tipo di conversione radix può essere accelerato eseguendolo in blocchi radix * radix Nel tuo caso è necessario un carattere [2] [62 * 62]. Questo array può essere costruito al momento dell'inizializzazione (è const).
Tuttavia, questo deve essere confrontato. Il costo di divisione era ENORME, quindi risparmiare metà delle divisioni è stata una vittoria sicura. Dipende dalla capacità di memorizzare nella cache questa tabella di oltre 7000 byte e il costo della divisione.
Se stai riscontrando un danneggiamento dell'heap, hai problemi oltre il codice che stai mostrando qui.
Puoi rendere più veloce la classe stringa riservando lo spazio per la stringa prima di iniziare, con string :: reserve.
La stringa viene emessa in ordine inverso, la cifra base-62 di ordine inferiore è il primo carattere della stringa. Questo potrebbe spiegare i tuoi problemi di confronto.
L'implementazione è più veloce che sarà. Vorrei suggerire un paio di modifiche:
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
}
La prima modifica (divisa per charsetLength ) potrebbe aver causato problemi di confronto delle stringhe. Con il tuo codice originale (dividendo per charsetLength + 1 ), potrebbero esserci diversi valori di numero intero che erroneamente vengono convertiti nella stessa stringa. Per la base 62, sia 0 che 62 verrebbero codificati come " 0 " .
È difficile dire se una delle suddette modifiche causerebbe problemi di corruzione dell'heap segnalati, senza un po 'più di contesto (come il valore di maxChars ).
Inoltre, dovresti essere consapevole che il codice sopra scriverà le cifre della rappresentazione della stringa in ordine inverso (provalo con la base 10 e converti un numero come 12345 per vedere cosa intendo). Questo potrebbe non essere importante per la tua applicazione, tuttavia.
Ecco una soluzione che uso in php per Base 10 a N (62 in questo esempio)
Il mio intero post è qui: 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;
}
}
Sto accumulando un'altra risposta perché un paio di risposte che ho provato non hanno prodotto l'output che mi aspettavo. Tuttavia, questo è ottimizzato per la leggibilità, non per la velocità.
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;
}
