3

キーのハッシュを計算する 16 のスレッドがあります。ハッシュを計算し、それが線形的に存在するかどうかを確認することは、CPU パワーの一部しか使用しないため、作業をスレッド間で分割しようとしています。現在、すべてのスレッドがミューテックス ロックを使用してアクセスできる単一のマップ コンテナーを使用しています。ただし、実際のハッシュにはほとんど時間がかからないため、スレッドはほとんどアイドル状態にあり、別のスレッドが map::count を使用してキーがマップに存在するかどうかを確認するのを待っています。

このプログラムの主な目的は、プロジェクトに追加する前に衝突がないことを確認する必要があるため、衝突を総当たりでチェックすることです。

すべてのスレッドが終了したら、各キーで各マップを直線的に検索するのではなく、個別のマップまたは他のコンテナーを使用して、そのキーが存在するかどうかを判断する方法はありますか? ある種の待ち行列システムはどうですか？

編集:これは、スレッド化しようとしている関数です:

int coll = 0;
map<long, bool> mymap;
string temp;
long myhash;
for (int i = 0; i < 256; i++)
  for (int j = 0; j < 256; j++)
    for (int k = 0; k < 256; k++)
    {
      temp = i;
      temp += j;
      temp += k;
      temp += temp;
      myhash = hash(temp.c_str());

      if (mymap.count(myhash))
      {
        coll++;
        cout << "Collision at " << i << " " << j << " " << k << endl;
      }
      else
      {
        mymap[myhash] = true;
      }
  }

cout << "Number of collisions: " << coll << endl;
cout << "Map size: " << mymap.size() << endl;
4

2 に答える 2

2

このアルゴリズムは、OpenMP で並列化するのがかなり簡単に思えます。

int coll = 0;
map<long, bool> mymap;

#pragma omp parallel for
for (int i = 0; i < 256; i++)
  for (int j = 0; j < 256; j++)
    for (int k = 0; k < 256; k++)
    {
      string temp = i;
      temp += j;
      temp += k;
      temp += temp;
      long myhash = hash(temp.c_str());

      if (mymap.count(myhash))
      {
        #pragma omp atomic
        coll++;
        cout << "Collision at " << i << " " << j << " " << k << endl;
      }
      else
      {
        #pragma omp critical
        mymap[myhash] = true;
      }
  }

いくつかの説明: 最初に、衝突が非常にまれであるという仮定から始めます (衝突が頻繁に発生した場合、ハッシュ テーブルの実装は非常に貧弱になります)。これを考えると、スレッドが特定のキーに挿入しているときに、別のスレッドがまったく同じキーにハッシュする別の値に偶然遭遇したため、まったく同じキーを同時に挿入する可能性はほとんどありません。さらに、このような場合でも、値を true に設定するだけで十分です。これは、false に戻ることができず、後続の「挿入」によって true が true で上書きされるだけだからです。したがって、私の意見では、インクリメントのほかに、collそれ以上の同期は必要ありません。

于 2012-05-15T17:01:28.013 に答える
0

これはすでに上で回答されていますが、 std::map::count() を置き換えてパフォーマンスを改善し、配列演算子を使用してより効率的なものに挿入できます。

std::map::insert() メソッドの 1 つは、要素がマップに既に存在する場合に bool メンバーが false になるペアを返します。このようなもの：

    int coll = 0;
typedef map<long, bool> MY_MAP_TYPE;
MY_MAP_TYPE mymap;
string temp;
long myhash;
for (int i = 0; i < 256; i++)
    for (int j = 0; j < 256; j++)
        for (int k = 0; k < 256; k++)
        {
            temp = i;
            temp += j;
            temp += k;
            temp += temp;
            myhash = hash(temp.c_str());
            if( mymap.insert( MY_MAP_TYPE::value_type( myhash, true ) ).second == false)
            {
                coll++;
                cout << "Collision at " << i << " " << j << " " << k << endl;
            }
        }
于 2012-05-15T18:05:39.737 に答える