1

64ビット整数から62進文字列に変換するために作成した関数があります。もともと、私は次のようにこれを達成しました：

char* charset = " 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int charsetLength = strlen(charset);

std::string integerToKey(unsigned long long input)
{
    unsigned long long num = input;
    string key = "";

    while(num)
    {
        key += charset[num % charsetLength];
        num /= charsetLength;
    }

    return key;
}

しかし、これは遅すぎました。

ルックアップテーブルを生成するオプションを提供することで、速度を向上させました。テーブルのサイズは約624文字列で、次のように生成されます。

// Create the integer to key conversion lookup table
int lookupChars;

if(lookupDisabled)
    lookupChars = 1;
else
    largeLookup ? lookupChars = 4 : lookupChars = 2;

lookupSize = pow(charsetLength, lookupChars);
integerToKeyLookup = new char*[lookupSize];

for(unsigned long i = 0; i < lookupSize; i++)
{
    unsigned long num = i;
    int j = 0;

    integerToKeyLookup[i] = new char[lookupChars];

    while(num)
    {
        integerToKeyLookup[i][j] = charset[num % charsetLength];
        num /= charsetLength;

        j++;
    }

    // Null terminate the string
    integerToKeyLookup[i][j] = '\0';
}

実際の変換は次のようになります。

std::string integerToKey(unsigned long long input)
{
    unsigned long long num = input;
    string key = "";

    while(num)
    {
        key += integerToKeyLookup[num % lookupSize];
        num /= lookupSize;
    }

    return key;
}

これにより速度が大幅に向上しましたが、それでも改善できると思います。32ビットシステムのメモリ使用量は約300MBで、64ビットシステムのメモリ使用量は400MBを超えます。メモリを減らしたり、速度を上げたりできるはずですが、どうすればよいかわかりません。

このテーブルをさらに最適化する方法を誰かが理解するのを手伝ってくれるなら、私はそれを大いに感謝します。

4

8 に答える 8

6

'key'への連結を繰り返すのではなく、ある種の文字列ビルダーを使用すると、速度が大幅に向上します。

于 2009-11-09T22:07:59.860 に答える
6

のために事前にメモリを予約することをお勧めしますstring key。これにより、適切なパフォーマンスの向上と、メモリ使用率の向上が得られる可能性があります。でappend演算子を呼び出すと、std::string再割り当てが必要な場合に内部バッファのサイズが2倍になることがあります。これは、各文字列が文字を格納するために必要なメモリよりもかなり多くのメモリを消費している可能性があることを意味します。文字列用のメモリを事前に予約することで、これを回避できます。

于 2009-11-09T22:08:44.417 に答える
5

私はRobWalkerに同意します-あなたは間違った領域でパフォーマンスを改善することに集中しています。文字列は最も遅い部分です。

私はコードの時間を計りました（あなたのオリジナルは壊れています、ところで）そしてあなたのオリジナル（修正されたとき）は100000ルックアップに対して44982140サイクルでした、そして次のコードは約13113670です。

const char* charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
#define CHARSET_LENGTH 62

// maximum size = 11 chars
void integerToKey(char result[13], unsigned long long input)
{
    char* p = result;
    while(input > 0)
    {
        *p++ = charset[input % CHARSET_LENGTH];
        input /= CHARSET_LENGTH;
    }

    // null termination
    *p = '\0';
    // need to reverse the output
    char* o = result;
    while(o + 1 < p)
        swap(*++o, *--p);
}
于 2009-11-09T22:26:45.287 に答える
2

これは、これを行わない方法のほとんど教科書のケースです。ループ内で文字列を連結することは、追加が特に高速ではないことと、常にメモリを割り当てていることの両方から、悪い考えです。

注：質問には、base-62に変換していると記載されていますが、コードには63個の記号が含まれているようです。どちらをしようとしていますか？

64ビット整数が与えられた場合、結果に11桁を超える必要はないと計算できるため、静的な12文字のバッファーを使用すると確実に速度が向上します。一方、C ++ライブラリにはultoaと同等のlong-longが含まれている可能性があり、これはかなり最適です。

編集：これが私が作り上げたものです。これにより、任意のベースを指定することもできます。

std::string ullToString(unsigned long long v, int base = 64) {
    assert(base < 65);
    assert(base > 1);
    static const char digits[]="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+/";
    const int max_length=65;
    static char buffer[max_length];

    buffer[max_length-1]=0;
    char *d = buffer + max_length-1;
    do {
        d--;
        int remainder = v % base;
        v /= base;
        *d = digits[remainder];
    } while(v>0);

    return d;
}

これにより、std :: stringオブジェクトが1つだけ作成され、メモリが不必要に移動することはありません。現在、出力をゼロパディングしていませんが、必要な数桁の出力に変更するのは簡単です。

于 2009-11-09T22:30:26.430 に答える
1

base64ライブラリを使用しないのはなぜですか？63が「11」に等しく、長い文字列ではないことは本当に重要ですか？

size_t base64_encode(char* outbuffer, size_t maxoutbuflen, const char* inbuffer, size_t inbuflen);

std::string integerToKey(unsigned long long input) {
    char buffer[14];
    size_t len = base64_encode(buffer, sizeof buffer, (const char*)&input, sizeof input);
    return std::string(buffer, len);
}

はい、すべての文字列は同じサイズで終わります。望まない場合は、等号を削除してください。（番号をデコードする必要がある場合は、忘れずに追加してください。）

もちろん、私の本当の質問は、なぜ固定幅の8バイト値を変換し、可変長の文字列値の代わりにそれを「キー」として直接使用しないのかということです。

脚注：私はこれに関するエンディアンの問題をよく知っています。彼はキーが何に使用されるかについては述べていなかったので、異なるエンディアンのマシン間のネットワーク通信では使用されていないと思います。

于 2009-11-09T22:48:59.357 に答える
1

入力を値で渡すため、入力をnumにコピーする必要はありません。コンパイル時に文字セットの長さを計算することもできます。関数を呼び出すたびに実行時に文字セットを計算する必要はありません。

しかし、これらは非常に小さなパフォーマンスの問題です。あなたが得ることができる最も重要な助けは、ループ内の文字列の連結を回避することだと思います。キー文字列を作成するときは、文字列コンストラクターに結果文字列の長さを渡して、文字列の割り当てが1つだけになるようにします。次に、ループ内で文字列に連結すると、再割り当てされません。

ターゲット文字列を参照パラメータとして使用するか、標準アルゴリズムのように2つのイテレータを使用する場合でも、処理を少し効率的にすることができます。しかし、それは間違いなく一歩遠すぎます。

ちなみに、入力に渡された値がゼロの場合はどうなりますか？ループに入ることさえありません。キーを「0」にするべきではありませんか？

入力に渡される値を負にすることはできませんが、注意してください。C剰余演算子はモジュロ演算子ではありません。

于 2009-11-09T22:25:38.017 に答える
1

さらに2つのシンボルを追加して、base-64に変換できる場合、モジュラスと除算の演算はビットマスクとシフトに変わります。分割よりもはるかに高速です。

于 2009-11-10T14:53:13.133 に答える
1

必要なのが短い文字列キーだけの場合、div / mod 64は非常に安価（shift / mask）であるため、base-64の数値に変換すると処理が大幅に高速化されます。

于 2009-11-19T16:51:34.210 に答える