0

現在、シーケンシャル テキスト キーの生成が必要なプロジェクトに取り組んでいます。コンストラクターがキーに変換する特定のキーに対応する整数をキー ジェネレーターにシードする必要があります。

私のキー ジェネレーターはインクリメント演算子をオーバーロードして、文字列が直接インクリメントされるようにします。これは、インデックス値をインクリメントしてから、インデックスを生成したいすべてのキーのキーに変換するという以前に行っていたことではありません。

私の問題は、キーを生成するときに使用したい文字セットが限られていることです。インクリメントしたいキー内の文字を見つけ、それが文字セット内のどこにあるかを調べ、セット内の次の文字を見つけてから、キー内の文字をセット内の次の文字に置き換える必要があります。

これが私のコードです：

// Not the full charset
std::string charset = "abcdefghijklmnopqrstuvwxyz0123456789"; 
std::string key;

key.push_back(charset[0]);

for(unsigned int place = 0; place < key.length(); place++)
{
    if(key[place] == charset[charset.length() - 1])
    {
        // Overflow, reset char at place
        key[place] = charset[0];

        if((key.length() - 1) < (place + 1))
        {
            // Carry, no space, insert char
            key.insert(key.begin(), charset[0]);
            break;
        }
        else
        {
            // Space available, increment next char
            continue;
        }
    }
    else
    {
        // Increment char at place
        key[place] = charset[charset.find(key[place]) + 1];
        break;
    }
}

プロファイリングでは、検索操作が実際に速度を低下させていることがわかりました。これを行うより速い方法はありますか？文字セットからリンクされたリストを作成することを考えましたが、その前に、これについていくつかの入力が必要です。

4

5 に答える 5

3

検索を行うのではなく、逆変換配列を用意してみませんか? 配列インデックスは文字であり、配列内の値はその数値 (または他の配列へのインデックス) になります。

key[place] = charset[reverse_charset[key[place]] + 1];
于 2010-01-14T20:50:32.540 に答える
2

これは、一般化された基数変換問題の別のバージョンで、n=36 です。

あなたがしたいのは、キーを符号なし整数として表示し、そのキーのベース 36 (az + 0-9) 表現として配っている「文字列」を表示することです。

キーを渡すと、「次のキー」の値が base36 文字列に変換され、次のキーの値がインクリメントされます。

変換するには、任意の整数を 16 進表現に変換するのと同じことを行いますが、モジュロ演算で 16 ではなく 36 を交換します。これは読者の演習として残しておきます。:)

于 2010-01-14T20:58:50.633 に答える
1

キーと同じ長さのベクトルを格納できます。ベクトル内の各要素は、キー内の対応する文字の文字セット内のインデックスでした。

たとえば、「c」が文字セットの3番目の文字であるため、「c」の場合key[0]は2になります。thisVector[0]

次に、すべての操作がその整数ベクトルに対して実行さfindれ、文字列に対する操作の必要性がなくなります。

于 2010-01-14T20:53:06.260 に答える
1

あなたが何をしたいのか正確に理解できたかどうかはわかりませんが、文字セットを数字として使用して、base 36 で 36*36*36 の 3 桁のキーのシーケンスを出力する小さなコンソール プログラムを次に示します。つまり、aaa で始まり、999 で終わります。

#include <stdio.h>
typedef int Number;
const size_t N = 3;
size_t B = 36;
Number key[N] = {0};
bool carry = false;
char A[] = "abcdefghifjlmnopqrstuvwxyz0123456789";

void incr(size_t i)
{
    if(!carry)
    {
        return;
    }
    ++key[i];
    if(key[i] == B)
    {
        key[i] = 0;
    }
    else
    {
        carry = false;
    }
}

void Incr()
{
    carry = true;
    size_t i = 0;
    while(carry)
    {
        incr(i++);
    }
}

void Print()
{
    for(int i = N - 1; i >= 0; --i)
    {
        printf("%c", A[key[i]]);
    }
    printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    for(int i = 0; i < B * B * B; ++i)
    {
        Print();
        Incr();

    }
    return 0;
}
于 2010-01-15T11:35:43.527 に答える
0

おそらく、インデックスを文字セットに変換し、必要に応じて実際の文字に変換したほうがよいでしょうか。

これにより、文字セット内の文字を検索するオーバーヘッドを節約できます。また、文字セットインデックスを文字に変換することは、逆とは異なり、定数時間の操作になります。

キーを整数0〜N-1のベクトルとして格納します。ここで、Nは文字セットの長さです。これらの整数を実際の文字に変換するのは、必要な場合、つまり増分後のみです。

于 2010-01-14T20:54:07.883 に答える