C++与整数密钥

Question

我有200套约50,000唯一整数0至500,000我需要映射到另一个小的值的范围的高效且紧凑的地图（整数的一对，的值是不相关的，从而没有点播计算）。

我试过使用std :: unordered_maps，并使用了大约50MB（在VS2015堆诊断工具中测量），而性能很好Id想要得到这种内存使用下来（打算成为一些小的后台服务500MB云服务器）。

切实我最初的版本是200独立std::unordered_map<int, std::pair<int, int>>。

一个选项似乎是一个排序数组，并使用二分搜索，但还有什么？

Answer 1

我认为排序的向量应该工作，如果你不会改变它的排序向量。它非常节省空间，即无指针开销。

如果您需要更好的性能，并且不介意一些第三方库。你可以尝试sparse_hash_map，它实现了非常小的空间开销哈希映射。

Answer 2

我想这是最有效的记忆将是一个std::vector<std::pair<int, std::set<Something>>>，就像你已经建议。

在这种情况下，你只会有内存开销的结果：

• 从性病::向量（非常有限）
• 有时在“成长”更高的内存使用的固定开销作为旧数据和新的必须是活在那一刻
• 性病未使用的空间:: vector的

你还挺表明，后集结你不再延长载体，所以要么你可以reserve或shrink_to_fit摆脱未使用的空间。 （请注意，储备还修复了增长期间内存使用率的上涨）

如果您的密码使用率更高，则可以考虑将存储更改为std::vector<std::set<Something>>或std::vector<std::unique_ptr<std::set<Something>>>。在这种结构中，索引是隐含的，但只有在每个索引都有值时才会显示内存增益。

使用矢量的缺点是你必须编写一些自定义代码。在这种情况下，std::unordered_map和std::map并不坏，如果你不介意少的标准实现处理器缓存（L1 ...）更多高速缓存未命中，一个可以检查出Googles sparsehash，Googles cpp-btree或Facebooks AtomicHashMap from Folly，虽然我不没有任何经验。

最后，我们可以知道为什么你都在存储器中的数据，但我没有看到一个方法来防止这种情况，如果你需要的最佳性能。

Answer 3

高效的存储，这取决于精确值范围内，您可能需要使用位操作的键/值对存储在一个单一的值：例如，如果值是非常小的，你甚至可以使用24位的键和8位的值，导致一个单一的32位条目。我相信现在大多数编译器现在都使用32位或64位对齐方式，因此存储例如32位密钥和16位值可能仍然需要每个条目64位。如果瓶颈是内存总线和高速缓存未命中，使用简单压缩对性能也有好处，而不是CPU本身。

然后它取决于您想要执行的操作类型。存储密钥的最简单的方法将是一个有序结构数组或者我上面提出的组合的ley/value条目。这是快速且非常节省空间的，但需要O（log n）查找。

如果你想变得更有趣，你可以使用perfect hashing，这个想法是找到一个散列函数，它为每个键产生唯一的散列值。这允许hashmap是一个简单的数组，它只需要比我上面提出的排序后的数组稍微大一些。找到一个好的散列函数应该是相对较快的，你可以通过将数组放大一点，并允许数组中的一些未使用的字段来使它更容易。 Here是一个完美哈希的实现，但我没有使用它自己。

在这两种情况下，内存消耗将为：（对数）*（每个条目的位数）位，以及在使用第二种方法时存储散列函数。

**编辑**

从@FireLancer评论后更新。另外，增加了一些关于压缩数组性能的文字。