我有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;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?
Edit: 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并行化：
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的增量之外，不需要进一步的同步。
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; } }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.
更多推荐
发布评论