c++ - 使用大型整数对数据集有效地初始化 unordered_map

Question

我有一个巨大的唯一整数数组(例如，ParticleId[])以随机顺序存储在内存中。我需要构建一个哈希表来将每个 ID 映射到它在数组中的位置，即从 ID 到索引。 ID 不一定是连续整数，因此简单的查找数组不是一个好的解决方案。

我目前正在使用 c++11 的 unordered_map 容器来实现这一点。 map 是用一个循环初始化的:

unordered_map <ParticleId_t, ParticleIndex_t> ParticleHash;
ParticleHash.rehash(NumberOfParticles);
ParticleHash.reserve(NumberOfParticles);
for(ParticleIndex_t i=0;i<NumberOfParticles;i++)
  ParticleHash[ParticleId[i]]=i;

ParticleId_t 和 ParticleIndex_t 只是类型定义的整数。NumberOfParticles 可能很大(例如，1e9)。就哈希表而言，ParticleId[] 数组和NumberOfParticles 是const。

目前构建unordered_map需要花费大量时间。我的问题是:

1. unordered_map 是这个问题的最佳选择吗？
   • map 是否可以更快地初始化，尽管它在查找方面可能效率不高？
2. 是否可以加快初始化速度？
   • 使用 ParticleHash.insert() 是否比使用 ParticleHash[]= 快得多？或任何其他功能？
   • 鉴于已知我的键是唯一 整数，是否有优化映射和插入的方法？

我正在考虑使用英特尔 concurrent_unordered_map 来并行化它。但是，这会引入对英特尔 TBB 库的依赖，我希望尽可能避免这种依赖。是否有使用 native STL 容器的简单解决方案？

更新:

现在我已经恢复到一个简单的排序索引表并依靠 bsearch 进行查找。至少表的初始化现在快了 20 倍，并且可以轻松并行化。

Answer 1

看起来构建查找表的应用程序是内存绑定(bind)的，而不是 cpu 绑定(bind)的。这可能可以通过分析应用程序的原型(prototype)来验证。此答案的其余部分假设这是真的。

构建查找表的过程正在对输入数据进行全局查看，这可能会导致大量内存换入/换出磁盘。

如果是这种情况，解决方案是另一种算法，一次处理较小的内存块。假设有 100 万个整数。当前进程此时可能正在向哈希表的低端插入接近 1 的位置，而在下一刻它可能正在向接近 100 万的高端插入。这会导致大量交换。

另一种方法是通过一次处理较小的数据集 block 来避免交换。我们可以借鉴桶/基数排序的想法。在这种方法中，构建查找表的步骤将被排序步骤所取代。桶/基数排序应该在线性时间内运行。数据集中的所有整数都是唯一的这一事实是使用这些排序算法的另一个原因。如果可以将线性时间排序和最小化交换结合起来，则可能会提高性能。