N**D
发帖数: 2885 | 1 要把百万数据load在map里。感觉数据先sort下会快一些。有朋友能帮忙证明一下吗？
balanced tree?
每过一段时间要加入新的数据，是简单的接在后面，还是一起sort一下再load map里好？速度有差别么？ |
l**t
发帖数: 64 | 2 这个不好证明吧，各个stl库的实现不同情况各异. map使用的RB tree，如果按顺序逐
个插入数据，也避免不了比较和树的旋转，算法复杂度是O(lgn)吧。map的迭代器的输
出是排好序的
建议试试hash_map，如果hash函数选得好，插入和查询的效率非常高，都是常数时间
另外数据load毕竟就一次，每次增加的数据直接插到map中，数据的查询操作才是重点
好？速度有差别么？
【在 N**D 的大作中提到】
: 要把百万数据load在map里。感觉数据先sort下会快一些。有朋友能帮忙证明一下吗？
: balanced tree?
: 每过一段时间要加入新的数据，是简单的接在后面，还是一起sort一下再load map里好？速度有差别么？
|
N**D
发帖数: 2885 | 3 用的是stdext::hash_multimap, 数据源会经常改动所以要重新load. 所以考虑在每次
整理数据源时候有无必要sort一下
【在 l**t 的大作中提到】
: 这个不好证明吧，各个stl库的实现不同情况各异. map使用的RB tree，如果按顺序逐
: 个插入数据，也避免不了比较和树的旋转，算法复杂度是O(lgn)吧。map的迭代器的输
: 出是排好序的
: 建议试试hash_map，如果hash函数选得好，插入和查询的效率非常高，都是常数时间
: 另外数据load毕竟就一次，每次增加的数据直接插到map中，数据的查询操作才是重点
:
: 好？速度有差别么？
|
t*********e
发帖数: 1136 | 4 为啥要load百万数据？hash multimap的performance难掌握。数据一多就得考虑连续性
。不然可能page faults很多。 |
