Ale*_*lds 22 c++ stl map data-structures
我想将integer键的映射存储到float内存中的值.
我有大约1.3亿个键(因此,有1.3亿个键).
我的重点是查找性能 - 我必须进行许多,数百万次查找.
C++ STL库有一个map用于此类关联数组的类.我有几个问题map.
map上述大小的数据集的存储开销是多少？一般来说,存储开销如何扩展map？
看起来底层数据结构map是红黑,平衡的二叉树.听起来真实世界的表现就是O(log n)插入和检索.
它提到O(1)了一个暗示插入.我的输入是预先排序的,所以我相信我应该能够提供插入事件的提示.我如何使用此处列出的方法提供此提示？
是否有一个提供更好查找性能的STL容器？
是否有其他公开可用的开源框架,其关联数组类使用的底层数据结构的性能优于STL map？
如果编写我自己的容器类可以提供更好的查找性能,我可以研究哪些数据结构？
我正在使用GCC 4执行此任务,在Linux或Mac OS X下运行.
如果这些都是愚蠢的问题,我会提前道歉.感谢您的意见.
Jer*_*fin 24
鉴于你说什么,我会很努力想使用std::vector<pair<int, float> >,以及使用std::lower_bound,std::upper_bound和/或std::equal_range查找值.
虽然can(和确实)的确切开销std::map会有所不同,但很少或根本没有问题,它通常会消耗额外的内存并且比向量中的二进制搜索更慢地查找值.正如您所指出的,它通常(并且几乎不可避免地)实现为某种平衡树,这会对指针和平衡信息施加开销,并且通常意味着每个节点也单独分配.由于您的节点非常小(通常为8个字节),因此额外数据可能至少与您实际存储的数据一样多(即至少100%的开销).单独分配通常意味着参考的局部性较差,这导致缓存使用率较低.
编辑:只看实现std::map,可能值得注意的是大多数使用红黑树.如果您打算使用a std::map,使用AVL树的实现可能更适合您的目的 - AVL树对平衡的约束稍微严格.这样可以稍微加快查找速度,但代价是插入和删除稍慢(因为它必须更频繁地重新平衡以保持对"平衡"的更严格的解释).但是,只要您的数据在使用过程中保持不变,std::vector几乎肯定会更好.
还有一个值得注意的可能性:如果你的密钥至少是相当均匀分布的,你可能想尝试使用插值而不是二分法进行查找.即,不是始终从向量的中间开始,而是进行线性插值以猜测查找的最可能起点.当然,如果您的键遵循一些已知的非线性分布,则可以使用匹配插值.
编辑2:假设密钥合理均匀分布,插值搜索的复杂度为O(log log N).对于1.3亿个密钥,可以使用大约4个探针来查找项目.要做得比使用(正常/非完美)散列要好得多,你需要一个好的算法,你需要将表中的负载因子保持在75%左右 - 即你需要允许3200万左右的东西表中的额外(空)点可以将预期的复杂性从四个探针提高到三个.我可能只是老式的,但这让我感觉很多额外的存储空间可用于如此小的速度提升.
OTOH,确实这几乎是完美散列的理想情况 - 该集合是提前知道的,并且密钥非常小(重要的是,因为散列在密钥大小上通常是线性的).即便如此,除非密钥分布相当不均匀,否则我不会指望任何巨大的改进 - 完美的哈希函数通常(通常是？)相当复杂.