Schnellste Basisumwandlungsmethode?

Question

Im Moment arbeite ich an einem Projekt, das eine ganze Zahl erfordert eine zweite mehrmals an einer Basis 62 String umgewandelt werden. Je schneller diese Konvertierung abgeschlossen ist, desto besser.

Das Problem ist, dass ich eine harte Zeit habe meine eigenen Basis Konvertierungsmethoden immer schnell sein und zuverlässig. Wenn ich Strings verwenden, ist es im Allgemeinen zuverlässig und funktioniert gut, aber es ist langsam. Wenn ich char-Arrays verwenden, ist es im Allgemeinen viel schneller, aber es ist auch sehr chaotisch und unzuverlässig. (Es produziert Heapbeschädigung, Vergleich von Zeichenketten, die eine negative Rück sollten übereinstimmen, etc.)

So

Was ist die schnellste und zuverlässigste Möglichkeit, aus einer sehr großen Zahl von Umwandlung in eine Basis 62 Schlüssel? In Zukunft plane ich auf der Nutzung von SIMD-Modell-Code in meiner Anwendung, so ist dieser Vorgang parallelizable überhaupt?

EDIT: Diese Operation wird durchgeführt, mehrere Millionen Mal pro Sekunde; sobald der Vorgang abgeschlossen ist, beginnt sie wieder als Teil einer Schleife, so desto schneller läuft, desto besser. Die Ganzzahl umgewandelt wird, ist von beliebiger Größe, und kann leicht so groß wie eine 128-Bit-Ganzzahl (oder größer).

sein

EDIT:. Dies ist die Funktion, die ich bin derzeit mit

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';
}

Ich riss diese aus einer Klasse, die einen Teil meiner Anwendung ist, und ein Teil des Codes ist so modifiziert, dass es Sinn sans seine besitzende Klasse.

Answer 1

Wahrscheinlich, was Sie wollen, ist eine Version von itoa. Hier ist ein Link, die verschiedenen Versionen von itoa mit Performance-Tests zeigt: http://www.jb.man.ac.uk/~slowe /cpp/itoa.html

Im Allgemeinen ich kenne zwei Möglichkeiten, dies zu tun. Ein Weg, um es aufeinanderfolgende Unterteilungen durchzuführen um eine Stelle zu einer Zeit abzustreifen. Eine andere Möglichkeit ist Umwandlungen in „Blöcke“ vorauszuberechnen. So könnte man einen Block von int zu Text Umwandlung von Größe 62 ^ 3 dann precompute die Ziffern 3 zu einem Zeitpunkt tun. Sofern Sie das Speicherlayout und Lookup effizient kann dies zur Laufzeit etwas schneller sein, aber verursacht eine Start Strafe.

Answer 2

Ich fühle mich schlecht, weil ich erinnere mich kippe, wo ich dies ursprünglich gefunden, aber ich habe dies in meinem Code benutze und fand es ziemlich schnell zu sein. Sie könnten dies ändern effizienter an bestimmten Orten zu sein, ich bin sicher.

Oh, und ich fühle mich schlimmer, weil dies in Java geschrieben ist, aber ein schneller c & p und refactor bekommen konnten es in c ++ arbeitet

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;
     }

 }

Answer 3

Aus der Spitze von mir Kopf würde ich eine Implementierung erwarten viel wie folgt aussehen.

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 );
}

Im Moment ist dies nicht sehr SIMD optimierbar. Es gibt keine SIMD Modulo.

Wenn wir Modulo tun wir uns wiederum könnte die Schleife wie folgt umschreiben.

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

      leftOver        = newLeftOver;
   }

Jetzt haben wir etwas, das einfach sein würde, um SIMD, wenn es nicht für diese Lookup ist ...

Auch wenn Sie noch eine gute Verbesserung der Geschwindigkeit, indem Sie die Modulo für mehrere Werte gleichzeitig erhalten können. Es würde wahrscheinlich sogar lohnt die Schleife ein zweites Mal entrollt, so dass Sie den nächsten 4 oder so modulos, während der vorherige Satz (Aufgrund Anweisung Latenz) ist die Berechnung verarbeiten können. Sie sollten in der Lage sein Latenzen ziemlich effektiv auf diese Weise zu verstecken. #

Ich komme wieder, wenn ich einen Weg finden kann die Lookup-Tabelle zu beseitigen ...

Edit: Das heißt, wie die maximale Anzahl von Base62 Stellen Sie von einer 32-Bit-Integer bekommen 6 ist, sollten Sie nur in der Lage sein, vollständig die Schleife und verarbeiten alle 6 Stellen gleichzeitig zu entspannen. Ich bin mir nicht ganz sicher, SIMD würden Sie viel von einem hier zu gewinnen. Es wäre ein interessantes Experiment, aber ich zweifle wirklich Sie, dass all viel über eine Geschwindigkeit bis über die Schleife bekommen würde. Wäre interessant, es zu versuchen, wenn jemand Tee nicht gegossen hatte über meine dev Maschine Tastatur: (

Edit 2: während ich darüber nachdenken. Eine Konstante / 62 kann listig durch den Compiler mit unheimlich magischen Zahlen optimiert werden ... so dass ich nicht einmal die Schleife rechnet oben würde eine Spaltung tun.

Answer 4

gibt es Wende Probleme in der oben - die niedrigen Aufträge kommen erst in der generierten Zeichenfolge -. Ich weiß nicht, ob das wirklich ein Problem ist, weil es auf der späteren Nutzung der erzeugten Zeichenfolge abhängt

Im Allgemeinen wird diese Art von Radix Umwandlung kann, indem Sie es in radix * Radix Brocken beschleunigt werden In Ihrem Fall ein Zeichen [2] [62 * 62] benötigt. Diese Anordnung kann bei der Initialisierung konstruiert werden (es ist const).

Dies muss allerdings verglichen werden. Die Kluft Kosten verwendet werden riesig so Spar Hälfte der Gräben war ein sicherer Sieg. Es hängt von der Fähigkeit, diese 7000+ Byte-Tabelle und die Kosten für die Kluft cachen.

Answer 5

Wenn Sie Heapbeschädigung bekommen, haben Sie Fragen über den Code, den Sie hier sind zeigt.

Sie können die String-Klasse schneller machen, indem der Raum für die Zeichenfolge zu reservieren, bevor Sie beginnen, mit string :: Reserve.

Ihre Zeichenkette in umgekehrter Reihenfolge herauskommt, desto niedrige Ordnung basen 62 Ziffer ist das erste Zeichen in der Zeichenfolge. Dies könnte Ihr Vergleich Probleme erklären.

Answer 6

Ihre Implementierung ist so ziemlich so schnell wie es geht zu erhalten. Ich würde allerdings ein paar Änderungen vorschlagen:

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
}

Die erste Änderung (Division durch charsetLength) Probleme verursacht Ihre String-Vergleich wurden. Mit Ihrem ursprünglichen Code (Division durch charsetLength + 1) können unterschiedliche Werte von Ganzzahl sein, die fälschlicherweise auf die gleiche Zeichenfolge konvertieren erhalten. Für Basis 62, dann würden beide 0 und 62 als "0" codiert werden.

Es ist schwer zu sagen, ob eine der beiden oben genannten Änderungen Ihrer berichteten Heapbeschädigung Probleme würde verursachen, ohne ein bisschen mehr Kontext (wie der Wert von maxChars).

Auch Sie sollten sich bewusst sein, dass der obige Code werden die Ziffern der String-Darstellung in umgekehrter Reihenfolge (versuchen Sie es mit der Basis 10 und konvertieren eine Zahl wie 12345, um zu sehen, was ich meine) schreiben. Dies kann nicht für Ihre Anwendung wichtig, though.

Answer 7

Hier ist eine Lösung, die ich in php für Base 10 bis N (62 in diesem Beispiel)
Mein ganzer Beitrag ist hier: 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;
        }

}

Answer 8

Ich bin Ramm mit einer anderen Antwort auf, weil ein paar Antworten, die ich versucht habe die Ausgabe nicht produzieren ich erwartet hatte. Obwohl, ist dies für die Lesbarkeit optimiert, nicht Geschwindigkeit.

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;
}