高效地初始化unordered_map整数对的大数据集

我有一个庞大的数组（ParticleId[]）唯一整数（代表粒子ID）以随机顺序存储在内存中。我需要构建一个哈希表来将每个ID映射到它在数组内的位置，即从ID到索引。 ID不一定是连续的整数，所以一个简单的查找数组不是一个好的解决方案。高效地初始化unordered_map整数对的大数据集

我目前使用C++ 11的unordered_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只是的typedef-ED整数。 NumberOfParticles可能很大（例如，1e9）。就散列表而言，ParticleId[]数组和NumberOfParticles是const。

目前需要相当多的时间来构建如上所述的unordered_map。我的问题是：

是unordered_map这个问题的最佳选择？
- 会map会更快初始化，虽然它可能不是在查找效率？
是否可以加快初始化？
- 使用ParticleHash.insert()比使用ParticleHash[]=快吗？或任何其他功能？
- 鉴于我的密钥已知为独特的整数，有没有一种方法来优化地图以及插入？

我正在考虑将英特尔concurrent_unordered_map并行它。但是，这会引起对英特尔TBB库的依赖，如果可能，我希望避免这种情况。有使用本地STL容器的简单解决方案吗？

更新：

现在我已经恢复到一个普通的分类索引表，并依靠bsearch进行查找。至少该表的初始化现在快20倍，并且可以很容易地并行化。

来源

2015-10-14 Kambrian

看看这个 - 包括有关在构造函数中指定bucket大小的注释：http://stackoverflow.com/questions/11614106/is-gcc-stdunordered-map-implementation-slow-if-so-why –

使用'std :: map'你可以传递一个提示迭代器来加速插入。如果你知道下一个键是地图上的最后一个键，你可以传递结束迭代器作为我相信的提示。我不知道这是否比无序地图更快。还要考虑boost提供的一些flat_map数据结构。 –

@JerryJeremiah：啊，我用的是gcc4.7.2。也许这是原因。在确认这个之前，我必须找到另一个编译器。 – Kambrian

我不认为有很多你可以用这个做，但这里有几件事要尝试。

首先，由于您打电话给realloc，您无需致电rehash。

insert可能比自operator[]operator[]快将调用insert的元素添加到使用默认值的地图，那么你的价值分配给新插入的元素，但优化也许能消除额外的工作。

只是因为键是唯一的，这些键的哈希值可能不会是因为我不认为语言规范要求整数散列返回该整数（描述散列模板的部分不无论如何说）。

'map'的初始化可能会比较慢，因为当你插入东西时，它必须不断重新平衡树，查找会更慢。如果您的ParticleID矢量可以重新排列，则可以使用map的一种替代方法，即对矢量进行排序，然后执行binary_search以查找ID的位置并计算索引。但它的性能与map类似，需要重新排列矢量。

如果您决定尝试concurrent_unordered_map由于线程之间的所有内存争用，在3或4个线程之后您可能看不到很多改进。

来源

2015-10-14 02:30:54 1201ProgramAlarm

我在'reserve'前面'rehash'显式设置了桶的数量，希望它能帮助减少碰撞到最小。很好地知道默认的哈希函数不需要返回相同的整数。也许我应该通过我自己的hasher。我的旧实现确实是一个在已分类ID上的'binary_search'。很遗憾，知道专用的散列表容器并没有做的更好。 – Kambrian

您可以简介应用程序以查看哪些部分花费最多时间？鉴于超级计算机的CPU，内存和其他资源，我想知道什么是瓶颈。在操作系统级别是否有任何配额，如果足够的CPU /内存已分配给这个应用程序？ –

看来构建查找表的应用程序似乎是内存绑定，而不是cpu绑定。这可能可以通过分析应用程序的原型来验证。这个答案的其余部分假定这是真实的。

构建查找表的过程是对输入数据进行全局视图，这可能会导致大量交换内存到/从磁盘进/出。

如果是这样，该解决方案是一种替代算法，一次处理较小的内存块。假设有一百万个整数。当前进程可能会在此时插入哈希表的低端，接近1，并且在下一时刻它可能插入到接近100万的高端。这导致了很多交换。

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

来源

2015-10-14 03:02:30

由于我在超级计算机上运行的记忆足够多，所以我的情况实际上并不受限于内存。 – Kambrian

鉴于“以随机顺序存储的大量唯一整数” - 是否有任何事情取决于该随机顺序？如果不是，只需对原始数组中的唯一整数进行排序，并将唯一整数映射到索引，则可以在数组中执行std::lower_bound。

如果需要保留巨大数组的前置顺序，但是在该数组填充后（如说明性代码所做的那样）将索引构建为一次性的步骤，则可以创建它们基于指向的元素（您需要定制的指向值的<比较）的ParticleId*和std::sort类似的巨大数组;之后您可以使用std::lower_bound与<进行比较，以便快速找到特定ParticleId的巨大阵列中的索引。

上述连续阵列方法在缓存友好的方式中使用连续内存，在性能和内存使用方面获益匪浅。

只有当您有大量新的ParticleId进入或在您需要搜索时才被删除，您需要考虑std::unordered_map。

来源

2015-10-14 11:00:47

对数据进行排序并不理想，因为有更多的数据与每个粒子以相同的顺序关联。创建另一个数组本质上是我在尝试unordered_map之前所做的。 – Kambrian

@Kambrian：*“创建另一个数组本质上是我在做什么”* - 是不是够快？你是否在第一个数组中使用指针？无论如何，如果你想追求一个哈希表，你会好得多 - 对于这个特定的使用模式，并且给定'sizeof（ParticleId）'很小 - 写或找到你自己的使用开放寻址/封闭哈希;我倾向于在我的硬件上发现类似用法的速度快于（unordered_map'），并且可以显着降低内存开销（尽管连续数组总是更高效）。 –

我创建一个（ID，索引）对的数组，然后通过ID对它进行排序。然后使用二进制搜索来搜索该数组，以查找每个ID查询的索引。我天真地期待一个专用的哈希表可能会做比这更聪明的事情。但发现它不适合这种特殊应用并不坏。谢谢！ – Kambrian

高效地初始化unordered_map整数对的大数据集

回答

相关问题