13

現在、私は整数を1秒間に何度も六十二進法の文字列に変換する必要があるプロジェクトに取り組んでいます。この変換が完了するのが早いほど、優れています。

問題は、自分の基本変換方法を高速で信頼できるものにするのに苦労していることです。文字列を使用する場合、一般的に信頼性が高く、うまく機能しますが、速度は遅くなります。char配列を使用すると、一般的にはるかに高速になりますが、非常に面倒で信頼性も低くなります。（ヒープの破損、一致するはずの文字列の比較は負の値を返すなどを生成します。）

では、非常に大きな整数から六十二進法のキーに変換する最も速くて信頼できる方法は何でしょうか。将来的には、アプリケーションでSIMDモデルコードを利用する予定ですが、この操作は並列化可能ですか？

編集：この操作は1秒間に数百万回実行されます。操作が終了するとすぐに、ループの一部として再開されるため、実行速度が速いほど良いです。変換される整数は任意のサイズであり、128ビット整数（またはそれ以上）まで簡単に大きくすることができます。

編集：これは私が現在使用している機能です。

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

アプリケーションの一部であるクラスからこれをリッピングし、コードの一部を変更して、所有するクラスが意味をなさないようにしました。

4

8 に答える 8

5

おそらく、あなたが望むのは itoa のいくつかのバージョンです。パフォーマンス テスト付きのさまざまなバージョンの itoa を示すリンクは次のとおりです: http://www.jb.man.ac.uk/~slowe/cpp/itoa.html

一般に、これを行うには 2 つの方法を知っています。連続した除算を実行して、一度に 1 つの桁を削除する方法の 1 つです。別の方法は、「ブロック」で変換を事前計算することです。したがって、int のブロックをサイズ 62^3 のテキスト変換に事前計算してから、一度に 3 桁ずつ変換できます。メモリ レイアウトとルックアップを効率的に行うと、実行時にわずかに速くなる可能性がありますが、起動時にペナルティが発生します。

于 2009-08-05T20:50:32.643 に答える
5

最初にこれを見つけた場所を思い出せないので気分が悪いですが、コードでこれを使用しており、かなり高速であることがわかりました。これを変更して、特定の場所でより効率的にすることができると確信しています。

ああ、これはJavaで書かれているので気分が悪くなりますが、簡単なc&pとリファクタリングで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;
     }

 }
于 2009-08-05T20:43:32.987 に答える
5

私の頭の上から、実装はこのように見えると思います。

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

現時点では、これはあまり SIMD 最適化可能ではありません。SIMD モジュロはありません。

Modulo を自分で実行すると、次のようにループを書き換えることができます。

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

      leftOver        = newLeftOver;
   }

これで、そのルックアップがなければ SIMD を簡単に実行できるものがあります...

ただし、いくつかの値のモジュロを同時に実行することで、速度を大幅に向上させることができます。前のセットが計算されている間に次の 4 つほどのモジュロを処理できるように、ループをもう一度アンロールする価値があるでしょう (命令の待ち時間のため)。このようにして、レイテンシをかなり効果的に隠すことができるはずです。#

テーブルルックアップをなくす方法が思いついたら戻ってきます...

編集：32ビット整数から取得できるbase62桁の最大数は6であるため、ループを完全に巻き戻し、6桁すべてを同時に処理できるはずです。ここで SIMD があなたに多くの勝利をもたらすかどうかは完全にはわかりません。これは興味深い実験ですが、上記のループでそれほど高速になるとは思えません。誰かが私の開発マシンのキーボードにお茶を注いでいなかったら、それを試すのは興味深いでしょう:(

編集2：考えている間。定数 / 62 は、恐ろしい魔法の数字を使用してコンパイラによって巧妙に最適化される可能性があります...したがって、上記のループで除算が行われるとは思いもしません。

于 2009-08-05T20:46:53.400 に答える
1

ヒープが破損している場合は、ここに示しているコード以外の問題があります。

string::reserve を使用して、開始する前に文字列用のスペースを予約することで、文字列クラスを高速化できます。

あなたの文字列は逆順で出てきます。下位のbase-62数字は文字列の最初の文字です。これにより、比較の問題が説明される場合があります。

于 2009-08-05T21:50:16.987 に答える
1

あなたの実装は、それが得ようとしているのと同じくらい迅速です。ただし、いくつかの変更をお勧めします。

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
}

最初の変更 ( で割るcharsetLength) が、文字列比較の問題を引き起こしている可能性があります。元のコード ( で割るcharsetLength + 1) では、異なる値の整数が誤って同じ文字列に変換される可能性があります。base 62 の場合、0 と 62 の両方が としてエンコードされ"0"ます。

上記の変更のいずれかが、報告されたヒープ破損の問題を引き起こしているかどうかを判断するのは、もう少しコンテキスト ( の値などmaxChars) がなければわかりません。

また、上記のコードでは、文字列表現の数字が逆順に書き込まれることに注意してください (基数 10 で試して、12345 などの数値に変換して、意味を確認してください)。ただし、これはアプリケーションにとって重要ではない場合があります。

于 2009-08-05T23:58:59.597 に答える
0

これが私がPHPでBase10からN（この例では62）に使用するソリューションです
。私の投稿全体はここにあります：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;
        }

}
于 2010-09-03T14:48:00.553 に答える