0

その文字列をキーにマッピングすることにより、特定の文字列に「ID」を与えるハッシュ関数に取り組んでいます。使用する必要があるアルゴリズムを以下に示します。

  • string が与えられNOTEた場合、各文字に値を割り当てます。次に例を示します。

    N = 14, O =15, T = 20, E = 5

  • 次に、乗算して追加します。

    14 * 32^3 + 15 * 32^2 + 20 * 32^1 + 5 * 32^0

  • この式を因数分解すると、次のようになります。

    ((14 * 32 + 15) * 32 + 20) * 32 + 5

  • しかし、その値は大きくなりすぎる可能性があるため、括弧の各セットの後に mod 除算を次のように使用します。

    ((14 * 32 + 15)%tableSize *32 + 20)%tableSize * 32 + 5

これを達成するためのアルゴリズムを作成するにはどうすればよいですか? 私はそれをやろうとしましたが、私の実装は非常に非効率的です。私の教授は、それは 7 行より長くすべきではないと言いました。上記のアルゴリズムを効率的に実装する方法について誰か提案できますか?

誰かが気になる場合の私のアルゴリズムは次のとおりです。

int HashDictionary::getKey(string word) const{
    int wordLength = word.length();
    int* values = new int[wordLength];
    for ( int i = 0; i < wordLength; i++ ) {
        values[i] = int(word[i]);
    }

    int productSoFar = 0;
    for(int i = 0; i < wordLength;i++){
        productSoFar *= 32;

        if(i == 0){
            productSoFar = values[i] * 32;
            productSoFar = productSoFar + values[i+1];
            productSoFar %= tableSize;
            i++;
        }
        else{
            productSoFar += values[i];
            productSoFar %= tableSize;
        }

    }
    delete [] values;
    return productSoFar;
}
4

2 に答える 2

1

2 つのループは必要ありません。最初に行うことは文字を整数に変換することだけなので、必要に応じてそれぞれを変換し、values 配列を完全に避けることができます。これにより、処理が高速化され、行数が削減されます。

于 2012-05-01T01:35:40.727 に答える
0

これを試して：

int HashDictionary::getKey(string word) const{
    int wordLength = word.length();
    int* values = new int[wordLength];
    values[0] = int(word[0]);
    values[1] = int(word[1]);

    int productSoFar = 0;
    productSoFar = values[0] * 32;
    productSoFar = productSoFar + values[1];
    productSoFar %= tableSize;

    for(int i = 1; i < wordLength;i++){
        productSoFar *= 32;
        productSoFar += values[i];
        productSoFar %= tableSize;
        values[i] = int(word[i]);
        }
    delete [] values;
    return productSoFar;
}
于 2012-05-01T01:41:57.410 に答える