检查16个容器中是否存在值 [英] Check if value exists across 16 containers

问题描述

我有16个线程计算密钥的哈希值。我试图划分线程之间的工作，因为计算哈希和检查它是否以线性方式存在只是利用我的cpu功率的一小部分。目前，我使用单个地图容器，所有线程都可以使用互斥锁进行访问。然而，由于实际的哈希没有任何时间，线程大多是空闲的，等待另一个线程完成其业务使用map :: count检查地图中是否存在键。

I have 16 threads that calculate the hash of a key. I'm trying to divide up the work between the threads, because calculating the hash and checking if it exists in a linear fashion is only utilizing a fraction of my cpu power. Currently, I am using a single map container that all threads can access using mutex locking. However, since the actual hashing takes next to no time at all, the threads are mostly sitting idle, waiting on another thread to finish its business using map::count to check if the key exists in the map.

这个程序的主要目的是强制检查碰撞，因为我需要确保没有，在我添加到我的项目之前。

The main goal of this program is brute force checking for collisions, as I need to be sure there are none before I add it to my project.

有没有办法使用单独的映射或其他容器，并确定是否存在所述关键字，而不是在所有线程完成后用每个关键字线性搜索每个映射？

Is there a way to use separate maps, or other containers, and determine if said key exists, rather than linearly searching through each map with each key once all the threads are finished? What about some sort of queuing system?

编辑：这是我要尝试线程的函数：

This is the function I'm trying to thread:

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;

推荐答案

此算法似乎很容易与OpenMP并行： / p>

This algorithm seems fairly easy to parallelize with 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;
      }
  }

一些解释：首先我们假设碰撞是非常罕见的（如果碰撞频繁，那将是非常差的哈希表实现）。鉴于此，当一个线程插入某个键时，另一个线程同时插入完全相同的键是不太可能的，因为它偶然发生在一个不同的值上，该值不同于完全相同的键。此外，即使是这种情况，只要其中一个设置值为真，这是足够的，因为它不能回到假，随后的插入只会用真实覆盖一个真。因此，在我看来，除了 coll 的增量，不需要进一步的同步。

Some explanation: first we start from the assumption that collisions are very rare (it would be a very poor hash table implementation if collisions were frequent). Given this, it's very unlikely that, as a thread is inserting to a certain key, another thread simultaneously inserts the exact same key because it happened to stumble upon a different value that hashes to the exact same key. Furthermore, even if this were the case, it is sufficient for only one of them to set the value true, since it cannot go back to false and subsequent "insertions" will only overwrite a true with true. Therefore, in my opinion, besides the increment of coll no further synchronization is needed.

这篇关于检查16个容器中是否存在值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！