C++ Google dense_hash_set 插入操作的性能表现

Question

我有一个C++程序，正在将大约1800万个类型为uint64_t的数字插入到谷歌的dense_hash_set中。

这些数字都是小于2^64的偶数，并且满足以下条件：

N >= radical(N)^4.

“插入操作的速度比如插入1800万个随机数或者1800万个连续数要慢一个数量级。

在执行插入操作时，代码似乎大部分时间都花费在执行该语句上。”

if ( test_empty(bucknum) )

“18百万个项目插入到dense_hash_set中是否合理？”

“有什么方法可以加快插入速度吗？”

“相关行是”

uint64_t N;
google::dense_hash_set<uint64_t> evencandidates;
evencandidates.set_empty_key(-1);
.....
evencandidates.insert(N);

- Arthur Vause

---

也许是因为你需要检查是否N>=radical(N)^4？你甚至没有提供任何代码。我们应该如何回答呢？ - DawidPi

性能差不与检查N>=radical(N)^4有关（我之前使用std::unordered_set进行插入，速度也快一个数量级）。由于完整代码较为复杂，因此我没有在帖子中包含它，仅添加了相关行。 - Arthur Vause

@Armchair：然后制作一个最小化、完整的示例来展示问题。作为奖励，当您删除不必要的代码以展示差效率时，您可能会发现问题是其他什么东西导致的！ - user1084944

Answer 1

通过用std::tr1::hash替换默认哈希函数来解决问题。密集哈希集的声明如下：

google::dense_hash_set<uint64_t, std::tr1::hash<uint64_t> > evencandidates;

选择要存储的数字的标准，

N >= radical(N)^4 and N even

结果是存储的数字有很多共同因子，特别是大多数数字都有几个2的幂。选择一个适用于这组数字的哈希函数可以解决性能问题。

- Arthur Vause