unordered_map 查找数组的索引

Question

我想高效地查找集合的索引。我正在使用 unordered_map 并制作这样的逆向映射

std::unordered_map <int, int> myHash (size); 
Int i = 0;
for (it = someSet.begin(); it != someSet.end(); it++)
{
    myHash.insert({*it , i++});
 }

有效但效率不高。我这样做是为了在需要索引时随时访问它们 O(1)。性能分析告诉我这部分成为我代码的热点。

VTune 告诉我 new 运算符是我的热点。我猜 unordered_map 里面发生了什么事。在我看来，这个案子应该得到有效处理。我还没有找到好的方法。有更好的解决方案吗？一个正确的构造函数？也许我应该将更多信息传递给构造函数。我查找了初始化列表，但这并不是我想要的。

更新：让我补充一些信息。集合并不那么重要；我将集合保存到一个数组中（已排序）。稍后我需要找到唯一值的索引。我可以在 logn 中完成，但速度不够快。这就是我决定使用哈希的原因。集合的大小（子矩阵的列）在此之后不会改变。

它源于稀疏矩阵计算，我需要在更大的矩阵中找到子矩阵的索引。因此，查找的大小和模式取决于输入矩阵。它适用于较小的问题。我可以使用查找 table，但是当我计划并行执行它时，每个线程的查找 table 可能很昂贵。我在创建时有哈希的确切大小。我想通过将它发送给构造函数它会停止重新分配。我真的不明白为什么要重新分配这么多。

Answer 1

std::unordered_map 通常被实现为好像它是

std::vector<std::list<std::par<int, int>>>

这会导致每个节点的大量分配和释放，每个（释放）分配都使用导致争用的锁。

您可以通过使用 emplace 而不是 insert 来帮助它一点，或者您可以跳入 pmr 分配器的奇妙新世界。如果您对 pmr::unordered_map 的创建和销毁是单线程的，您应该能够从中获得很多额外的性能。参见 Jason Turners C++ Weekly - Ep 222 - 3.5x Faster Standard Containers With PMR!，他的示例有点小，但您可以了解总体思路。

Answer 2

问题是，std::unordered_map，主要实现为向量列表，非常 cache-unfriendly，并且在 keys/values（如 int,int在你的情况下），更不用说需要大量的（重新）分配。

作为替代方案，您可以尝试 third-party 哈希映射实现 open addressing with linear probing (a mouthful, but the underlying structure is simply a vector, i.e. much more cache-friendly). For example, Google's dense_hash_map or this: flat_hash_map。两者都可以用作 unordered_map 的 drop-in 替代品，并且只需要另外指定一个 int 值作为“空”键。

unordered_map 查找数组的索引

unordered_map to find indices of an array

c++

performance

unordered-map

set