12

std::unordered_map を使用しています。ハッシュ値と、特定の候補キーが探しているキーであるかどうかを判断する方法はありますが、実際のキーはありません。ハッシュ値に対応するバケットを検索し、そのバケット内の各要素を調べて、探している要素であるかどうかを確認したいと考えています。残念ながら、関数 std::unordered_map::bucket(x) では x がキーである必要があります。最初にキーを構築せずにハッシュ値からバケットを取得する方法は本当にありませんか?

質問に答える必要のない詳細:キーを作成することはできますが、衝突がない一般的なケースでは、バケット内で見つけた単一の候補が正しいものであるかどうかを確認するだけよりも時間がかかります。私は負荷率が低いので衝突はほとんどなく、衝突の場合でも完全なハッシュ値が一致する可能性は低いため、一致しないものはすぐに一致しないと判断されます。キーの構築にかなりの時間がかかっていることをプロファイラーで判断したため、これを気にかけています。多くのルックアップがあり、各ルックアップにはキーの構築が必要です。

質問に答える必要のない詳細:キーは整数のベクトルであり、私のクエリは 2 つのベクトルの合計です。与えられたベクトル V が 2 つのベクトル A と B の合計であるかどうかを確認する方が、2 つのベクトルを合計して 3 番目のベクトル C=A+B にしてから、C と V を比較するよりも高速です。これらのベクトルのハッシュ値を保存し、ハッシュ関数 f には f(A+B)=f(A)+f(B) というプロパティがあるため、実際のベクトル A+B を計算せずに A+B を計算します。したがって、保存されている 2 つのハッシュ値を加算して、合計のハッシュ値を取得します。キーの構築にメモリ割り当てが不要になるように、予備のベクトルを保持するようにしましたが、ベクトルを追加するためのコードにはまだかなりの時間がかかっています。

4

1 に答える 1

10

キーの作成は避けられませんが、キー全体の作成は避けられます。

たとえば、VectorKeyをカプセル化しstd::vector、計算されたハッシュ コードをキャッシュするキー クラスがあるとします。さらに、キャッシュされたハッシュ コードにアクセスするHashとの実装を提供し、カプセル化されたベクトルが等しいかどうかを比較するとします。常に空の を構築し、キャッシュされたハッシュ コードをコンストラクタに渡される値に設定するコンストラクタを定義できます。KeyEqualVectorKeyVectorKeystd::vector

class VectorKey{
    int cached_hash;
    std::vector<int> key;
public:
    VectorKey(const std::vector<int>& _key)
    :    key(_key)
    ,    cached_hash(calc_hash(_key)) {
    }
    // *** This is the centerpiece of the solution: *** 
    // *** this constructor effectively lets you access *** 
    // *** a bucket with nothing more than a hash code. *** 
    VectorKey(int hash)
    :    cached_hash(hash) {
    }
    // More code goes here for getting cached_hash
    // and also for checking equality
private:
    int calc_hash(const std::vector<int>& _key) {
         // calculate the hash code based on the vector
    }
};

このようなキー クラスを使用すると、偽のキーを作成してバケットをすばやく見つけることができます。

size_type bucketIndex = myHashMap.bucket(VectorKey(precalculated_hash));
于 2012-10-15T16:34:27.060 に答える