Méthode de conversion de base la plus rapide?
https://stackoverflow.com/questions/1235371
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je travaille actuellement sur un projet qui nécessite la conversion d’un nombre entier en chaîne 62 plusieurs fois par seconde. Plus cette conversion sera rapide, mieux ce sera.
Le problème, c’est que j’ai du mal à faire en sorte que mes propres méthodes de conversion de base soient rapides et . Si j'utilise des chaînes, c'est généralement fiable et fonctionne bien, mais c'est lent. Si j'utilise des tableaux de caractères, c'est généralement beaucoup plus rapide, mais c'est aussi très compliqué et peu fiable. (Cela produit une corruption de tas, la comparaison de chaînes qui doivent correspondre renvoie un négatif, etc.)
Quel est donc le moyen le plus rapide et le plus fiable de convertir un nombre entier très important en clé de base 62? À l'avenir, je prévois d'utiliser le code de modèle SIMD dans mon application. Cette opération est-elle donc parallélisable?
EDIT: Cette opération est effectuée plusieurs millions de fois par seconde. dès que l'opération est terminée, elle recommence sous la forme d'une boucle. Plus elle fonctionne vite, mieux c'est. Le nombre entier à convertir est de taille arbitraire et peut facilement atteindre un nombre entier de 128 bits (ou plus grand).
EDIT: C’est la fonction que j’utilise actuellement.
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';
}
Je l'ai extraite d'une classe qui fait partie de mon application, et une partie du code est modifiée pour qu'elle ait un sens sans sa classe propriétaire.
La solution
Ce que vous voulez probablement, c'est une version d’itoa. Voici un lien qui montre différentes versions de itoa avec des tests de performance: http://www.jb.man.ac.uk/~slowe /cpp/itoa.html
En général, je connais deux façons de procéder. Une façon d’effectuer des divisions successives consiste à éliminer un chiffre à la fois. Une autre méthode consiste à précalculer les conversions dans des "blocs". Ainsi, vous pouvez précalculer un bloc de conversion int en texte de taille 62 ^ 3 puis faire les chiffres 3 à la fois. Si vous agissez de manière efficace sur la mémoire et la structure de la mémoire, cette opération peut être légèrement plus rapide au moment de l'exécution, mais entraîne une pénalité de démarrage.
Autres conseils
Je me sens mal parce que je ne me souviens plus du lieu où j'ai trouvé cela, mais je l'utilise dans mon code et le trouve assez rapide. Vous pouvez modifier cela pour être plus efficace à certains endroits, j'en suis sûr.
Oh, je me sens plus mal parce que cela est écrit en Java, mais un rapide c & amp; p et un refactor pourraient le faire fonctionner 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;
}
}
De prime abord, je m'attendrais à ce qu'une implémentation ressemble beaucoup à ceci.
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 );
}
Pour le moment, cela n’est pas très optimisé par SIMD. Il n’existe pas de module SIMD.
Si nous modulons nous-mêmes, nous pourrons réécrire la boucle comme suit.
while( leftOver )
{
const int newLeftOver = leftOver / 62;
int digit62 = leftOver - (62 * newLeftOver);
*pWritePos = lookUpTable[digit62];
pWritePos++;
leftOver = newLeftOver;
}
Nous avons maintenant quelque chose qui serait facile à simuler s'il n'y avait pas eu cette recherche ...
Bien que vous puissiez toujours obtenir une bonne amélioration de la vitesse en faisant le modulo pour plusieurs valeurs simultanément. Il serait peut-être même intéressant de dérouler la boucle une seconde fois pour pouvoir traiter les 4 modulos suivants pendant le calcul de l'ensemble précédent (en raison de la latence des instructions). Vous devriez être capable de cacher les latences assez efficacement de cette façon. #
Je reviendrai si je peux trouver un moyen d'éliminer la recherche de table ...
Éditer: Cela dit, étant donné que le nombre maximal de chiffres en base62 que vous pouvez obtenir d’un entier 32 bits est de 6, vous devriez être capable de dérouler complètement la boucle et de traiter les 6 chiffres simultanément. Je ne suis pas tout à fait sûr que SIMD vous donnerait une grande victoire ici. Ce serait une expérience intéressante, mais je doute fort que vous obteniez une telle vitesse sur la boucle ci-dessus. Ce serait intéressant d'essayer si quelqu'un n'avait pas versé de thé sur le clavier de ma machine à développer: (
Edit 2: pendant que j'y pense. Une constante / 62 peut être astucieusement optimisée par le compilateur en utilisant des nombres magiques effrayants ... je ne pense donc même pas que la boucle ci-dessus ferait une division.
il y a des problèmes inversants dans ce qui précède - les ordres bas viennent en premier dans la chaîne générée - je ne sais pas s'il s'agit réellement d'un problème, car cela dépend de l'utilisation ultérieure de la chaîne générée.
Généralement, ce type de conversion de base peut être accéléré en procédant de la manière suivante: radix * radix chunks Dans votre cas, un caractère [2] [62 * 62] est nécessaire. Ce tableau peut être construit au moment de l’initialisation (c’est const).
Cependant, cela doit être comparé. Auparavant, le coût de la fracture était énorme, donc gagner la moitié de la fracture était un gain certain. Cela dépend de la possibilité de mettre en cache cette table de plus de 7 000 octets et du coût de la division.
Si vous obtenez une corruption de tas, vous avez des problèmes dépassant le code que vous affichez ici.
Vous pouvez rendre la classe string plus rapide en réservant l'espace pour la chaîne avant de commencer, avec string :: reserve.
Votre chaîne sort dans l'ordre inverse, le chiffre de la base 62 de l'ordre inférieur est le premier caractère de la chaîne. Cela pourrait expliquer vos problèmes de comparaison.
Votre mise en œuvre est à peu près aussi rapide que possible. Je suggérerais cependant quelques modifications:
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 première modification (division par charsetLength ) a peut-être causé des problèmes de comparaison de chaînes. Avec votre code d'origine (en divisant par charsetLength + 1 ), il peut exister différentes valeurs d'entier qui sont incorrectement converties dans la même chaîne. Pour la base 62, 0 et 62 sont alors codés sous la forme "0" .
Il est difficile de dire si l'une ou l'autre des modifications ci-dessus causerait les problèmes de corruption de segment de mémoire signalés, sans ajouter un peu plus de contexte (telle que la valeur de maxChars ).
En outre, vous devez savoir que le code ci-dessus écrit les chiffres de la représentation de chaîne dans l'ordre inverse (essayez-le avec la base 10 et convertissez un nombre tel que 12345 pour voir ce que je veux dire). Cela n’a peut-être pas d'importance pour votre application.
Voici une solution que j'utilise en php pour les bases 10 à n (62 dans cet exemple)
Mon article entier est ici: 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;
}
}
Je suis entrain d’entraîner une autre réponse parce que quelques réponses que j’ai essayées n’ont pas produit le résultat escompté. Bien que cela soit optimisé pour la lisibilité et non pour la vitesse.
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;
}
