C++ map 插入和查找性能和存储开销

Question

我想在内存中存储 integer 键到 float 值的映射。

我有大约 1.3 亿个键(相应地，有 1.3 亿个值)。

我的重点是查找性能——我必须进行很多很多次的查找。

C++ STL 库有一个用于此类关联数组的 map 类。我有几个关于 map 的问题。

对于上述大小的数据集，map 的存储开销是多少？通常，map 的存储开销如何扩展？

看起来 map 的底层数据结构是一个红黑平衡的二叉树。听起来像真实世界 performance因为这是 O(log n) 用于插入和检索。

它提到 O(1) 用于暗示插入。我的输入是预先排序的，所以我相信我应该能够为插入事件提供提示。我将如何使用列出的方法提供此提示 here ?

是否有提供更好查找性能的 STL 容器？

是否有其他公开可用的开源框架，其关联数组类使用比 STL map 性能更好的底层数据结构？

如果编写自己的容器类可以提供更好的查找性能，我可以研究哪些数据结构？

我使用 GCC 4 来完成这项任务，在 Linux 或 Mac OS X 下运行。

如果这些是愚蠢的问题，我提前道歉。谢谢你的建议。

Answer 1

鉴于你所说的，我会非常努力地考虑使用 std::vector<pair<int, float> > , 并使用 std::lower_bound , std::upper_bound , 和/或 std::equal_range查找值。

而std::map 的精确 开销可以(并且确实)变化，几乎没有或没有问题的余地，它通常会消耗额外的内存并且查找值比 vector 中的二进制搜索更慢。正如您所注意到的，它通常(并且几乎不可避免地)实现为某种平衡树，这会增加指针和平衡信息的开销，并且通常意味着每个节点也是单独分配的。由于您的节点非常小(通常为 8 个字节)，因此额外数据可能至少与您实际存储的数据一样多(即至少 100% 的开销)。单独的分配通常意味着引用的局部性较差，从而导致缓存使用率低。

std::map 的大多数实现使用红黑树。如果您打算使用 std::map ，使用 AVL 树的实现可能更适合您的目的 - AVL 树对平衡的约束稍微更严格。这以稍慢的插入和删除为代价提供了稍快的查找(因为它必须更频繁地重新平衡以保持其对“平衡”的更严格解释)。但是，只要您的数据在使用期间保持不变，std::vector仍然几乎可以肯定更好。

另一个值得注意的可能性:如果您的 key 至少相当分布均匀，您可能想尝试使用插值而不是二分法进行查找。即不是总是从 vector 的中间开始，而是进行线性插值以猜测查找的最可能起点。当然，如果你的键遵循一些已知的非线性分布，你可以使用匹配插值代替。

假设键合理地均匀分布(或至少遵循一些可预测的可插值模式)，插值搜索的复杂度为 O(log log N)。对于 1.3 亿个 key ，大约需要 4 次探测才能找到一个项目。为了比使用(正常/非完美)散列做得更好，您需要一个好的算法，并且您需要将表中的负载因子保持在相当低的水平(通常约为 75% 左右 - 即您需要允许类似于表中的 3200 万个额外(空)点，以将预期的复杂性从四个探针提高到三个)。我可能只是过时了，但这让我觉得很多额外的存储空间可以用于如此小的速度提升。

OTOH，确实这几乎是完美散列的理想情况——集合是提前知道的，而且 key 非常小(很重要，因为散列通常在 key 大小上是线性的)。即便如此，除非 key 分布相当不均匀，否则我不会期望有任何巨大的改进——完美的哈希函数通常(通常？)相当复杂。