Méthode de conversion de base la plus rapide?

Ce que vous voulez probablement, c’est une version d’itoa. Voici un lien qui montre différentes versions d’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 en “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 utilisez la disposition de la mémoire et effectuez une recherche efficace, cela peut être légèrement plus rapide au moment de l’exécution, mais entraîne une pénalité de démarrage.

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::ssortingng 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::ssortingng( res ); } 

Pour le moment, ce n’est pas très optimable pour SIMD. Il n’y a pas de modulo SIMD.

Si nous faisons Modulo nous-mêmes, nous pourrions réécrire la boucle comme suit.

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

Maintenant, nous avons quelque chose qui serait facile à SIMD s’il n’y avait pas 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 vaudrait probablement la peine 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 …

Edit: Cela étant dit, étant donné que le nombre maximal de chiffres en base62 que vous pouvez obtenir à partir d’un entier de 32 bits est de 6, vous devriez être en mesure 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éveloppement 🙁

Edit 2: pendant que j’y pense. Une constante / 62 peut être astucieusement optimisée par le compilateur en utilisant des nombres magiques effrayants … donc je ne pense même pas que la boucle ci-dessus ferait une division.

Je me sens mal parce que je ne me souviens pas de l’endroit où j’ai trouvé ceci à l’origine, mais je l’utilise dans mon code et le trouve assez rapide. Vous pourriez modifier cela pour être plus efficace dans certains endroits, j’en suis sûr.

Oh, et je me sens plus mal parce que cela est écrit en Java, mais un rapide C & P et un refactor pourraient le faire fonctionner en c ++.

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

il y a des problèmes inverses 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 comme suit: 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).

Cela doit cependant être comparé. Auparavant, le coût de la fracture était énorme, donc économiser 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 massive, vous avez des problèmes qui vont au-delà du code que vous affichez ici.

Vous pouvez rendre la classe ssortingng plus rapide en réservant l’espace pour la chaîne avant de commencer, avec ssortingng :: 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 (divide by 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 en la même chaîne. Pour la base 62, 0 et 62 seraient alors codés comme "0" .

Il est difficile de dire si l’une ou l’autre des modifications ci-dessus entraînerait les problèmes de corruption de maxChars de maxChars signalés, sans un peu plus de contexte (tel 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 de continuer avec une autre réponse parce que quelques réponses que j’ai essayées n’ont pas produit le résultat escompté. Bien que ceci soit optimisé pour la lisibilité, pas pour la vitesse.

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