std :: tr1 :: unordered_map :: operator []の時間効率

Question

Visual Studio 2008 SP1でコードを最適化しています。 unorder_mapが一定時間の挿入/削除/検索で素晴らしいことを知っているので、unordered_mapを主なデータ構造として使用してコードを最適化しました。次のコードを見てください。

.... 
    typedef std::tr1::unordered_map <__int64, int> umap_id; 
    const int text1_length = text1.GetLength(); 
    const int text2_length = text2.GetLength(); 
    const int max_d = text1_length + text2_length - 1; 
    const bool doubleEnd = (64 < max_d); 
    vector<set<pair<int, int> > > v_map1; 
    vector<set<pair<int, int> > > v_map2; 
    vector<int> v1(2 *max_d, 0); 
    vector<int> v2(2 *max_d, 0); 

    int x, y; 
    __int64 footstep; 
    umap_id footsteps(max_d * 2); 
    bool done = false; 
    const bool forward = ((text1_length + text2_length) % 2 == 1); 

    for (int d = 0; d < max_d; ++d) 
    { 
     // Walk forward path one step 
     v_map1.push_back(set<pair<int, int> >()); 
     for (int k = -d; k <= d; k += 2) 
     { 
      if (k == -d || (k != d && v1[k - 1 + max_d] < v1[k + 1 + max_d])) 
       x = v1[k + 1 + max_d]; 
      else 
       x = v1[k - 1 + max_d] + 1; 
      y = x - k; 

      if (doubleEnd) 
      { 
       footstep = (__int64) ((__int64)x << 32 | y); 
       if (!forward) 
        footsteps[footstep] = d; 
       else if (footsteps.find(footstep) != footsteps.end()) 
        done = true; 
      } 
      .... 
     } 
    } 
.... 

しかし、まだかなり遅いことがわかります。私の比較的小さい入力（max_d = 946）を考えると、それは20秒以上実行されます。

私はリリースビルドのプロファイラ分析を行った、とプロファイラは、その行を明らかにする：footsteps[footstep] = d;は447931回実行し、約20秒かかった主犯です。

同じループボディ内に別のコード行があります。else if (footsteps.find(footstep) != footsteps.end())は同じ回数（つまり447931回）実行されましたが、コストはずっと少なくなりました。

operator::[]のunordered_mapは私にとってはブラックボックスのようです。私はなぜそれが長くかかるのか理解できませんでした。 32ビットアプリケーションです。どんな助けもありがとうございます。

Answer 1

VS2008では、tr1::unordered_map<>のデフォルトのハッシュ関数は、キー値の下位32ビットのみを考慮します（ただし、TR1ライブラリを提供するFeature Packを使用）。少なくともそれは<functional>ヘッダーのtemplate<class _Kty> class hash::operator()実装の私の読書によるものです。

footstepの変数は、yの下位32ビットとして計算されたものを使用します.yは、それ自体が良いハッシュ値になるほどのバリエーションがあります（私は、 yを計算しています）？そうでない場合は、あなたが望むよりも多くのアイテムを特定のハッシュバケットに入れて、多すぎる衝突を生成している可能性があります。

この場合、独自のハッシュ関数を提供することを検討してください。

ちなみに、VS 2010には、64ビット整数で使用するとhash::operator()の特殊化がありますので、64ビットすべてをハッシュします - VS 2010を使用している場合は、私の回答の推測は適用しないでください。

---

更新：

いくつかのテストの後、私は（問題もVS 2008 SP1に存在する）、これは問題である確信。これを修正するには、コンパイラをVS 2010にアップグレードしてください。これは、64ビット型のハッシュ関数が優れているか、独自のハッシュ関数を使用してこれを処理します。以下は、私がVS2008で素早くテスト一つであり、動作しているようです：

class hash_int64 
    : public unary_function<__int64, size_t> 
{ 
public: 
    typedef __int64 key_t; 
    typedef unsigned int half_t; 

    size_t operator()(const key_t& key) const 
    { 
     // split the 64-bit key into 32-bit halfs, hash each 
     // then combine them 
     half_t x = (half_t) (key & 0xffffffffUL); 
     half_t y = (half_t) (((unsigned __int64) key) >> 32); 

     return (hash<half_t>()(x)^hash<half_t>()(y)); 
    } 
}; 

次に、あなたのtypedefに変更します。

typedef std::tr1::unordered_map <__int64, int, hash_int64> umap_id; 

Answer 2

デバッグビルドでは、Visual Studioに付属しているSTLはイテレータのチェックと小さなネストされた関数を大量に使用するため、リリースビルドですべてインライン化されます。そのため、STLを使用するデバッグコードはリリースコードに比べて非常に遅いのです。

Answer 3

おそらく、多くの衝突が発生しています。 unordered_mapがハッシュ関数で実装されてインデックスを作成していて、多くの衝突が発生した場合、リストをトラバースしてアイテムに到達する必要があります。これは1つの理由かもしれませんが、私はunordered_map実装を見たことがありません。

Answer 4

ハッシュマップはかなり高い一定のオーバーヘッドを有することが知られています。基本的に自由な比較演算子を持つ946要素だけが、おそらくstd::mapのO（log（n））ルックアップを使用する必要があります。しかし、実装のバグがない限り、operator[]はfind()より多くの時間を費やす必要はありません。

Answer 5

Visual Studio 2005および2008では、_SECURE_SCL=0を手動で設定する必要があります。リリースビルドでもデフォルトでは有効になっており、実行時のチェックが多くなり、場合によっては非常にコストがかかることがあります。

実際にリリースビルドを作成するようにVisual Studio 2010が修正しました。は、です。

これ以外にも、データ構造を平文old std::mapに置き換えることができます。もちろん、32ビットのビルドで64ビットの整数キーを使用する限り、最適ではありません。

ターゲットを絞ったx64は、物事を著しく改善する可能性がありますが、32ビットでスタックしている場合は、整数キーを2倍に置き換えることができるかどうかをCPUが考えることができますdouble型のデフォルトのハッシュ関数はどのように見えますか？それは全体的に遅くなる可能性がありますが、少なくともテストする価値があります）