作者aria0520 (紫)
看板C_and_CPP
标题效率比STL内建好的hashmap
时间Sat Jun 8 18:23:30 2019
以前都是直接用stl的unordered_map
但最近发现他的速度很慢（理论上O(1) 但速度却跟map差不多）
请问原因是什麽，并且有什麽能取代它的选择？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.136.99.96 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1559989412.A.4E7.html
1F：推 yilanP: 速度跟map差不多是用感觉的吗？ 06/08 18:40
2F：→ yilanP: 或是你的N已经超大了？ 06/08 18:40
3F：→ aria0520: 我知道理论上N很大时两者会差不多 但奇怪的是我N没很大 06/08 18:56
4F：→ aria0520: 两者一样都比直接用矩阵存慢50ms左右 06/08 18:56
5F：→ aria0520: 还是我不该期待hashmap能达到直接矩阵存的速度 06/08 18:59
6F：→ Caesar08: 根据经验，你的确不该 06/08 19:02
7F：→ hsnuyi: O3开了吗? 06/08 20:09
8F：→ adrianshum: N 大才会有明显分别吧？！ 06/08 20:50
9F：→ adxis: 试试先 reserve() 预期的大小 06/09 02:39
10F：→ bibo9901: map 哪有 reserve... 难道楼上是指自订Allocator 06/09 04:04
11F：推 chchwy: N很大的时候hashmap的优势才会出现阿 06/09 14:34
12F：→ loveme00835: 先说说你的参数还有测量的方法 06/09 16:20
13F：→ RishYang: 时间复杂度不等於执行时间啊 06/09 18:27
14F：→ RishYang: unorderd map得到使用上的方便，必定会有牺牲 06/09 18:30
17F：推 xavier13540: 如果你已经知道最後会有n个元素在std::unordered_map 06/09 20:12
18F：→ xavier13540: 里 传入n当作constructor的argument可以避免rehash 06/09 20:13
19F：推 xavier13540: 另外也可以用max_load_factor()改load factor 或者使 06/09 20:18
20F：→ xavier13540: 用自己定义的hash 因为gcc的std::hash::operator()蛮 06/09 20:19
21F：→ xavier13540: 烂的 吃什麽就吐什麽 06/09 20:19
22F：→ aria0520: 也就是说我事先reserve足够就能避免rehash了? 06/09 20:34
23F：→ aria0520: 还是reserve完要自己rehash一次 06/09 20:35
24F：→ aria0520: 所以stl的hashmap慢的原因是频繁rehash 06/09 20:35
25F：→ aria0520: 吗 06/09 20:35
26F：→ loveme00835: 你在示范怎麽抓药吗? 06/09 23:34
27F：推 steve1012: 可以用abseil flat_hash_map 06/10 00:47
28F：推 xavier13540: std::unordered_map<int> umi(10); // reserve at 06/10 16:27
29F：→ xavier13540: least 10 buckets for umi 06/10 16:27
30F：→ xavier13540: 如果只考虑不断插入n个东西 由於rehash的缘故 跟 06/10 16:28
31F：→ xavier13540: std::vector的效率一样 大概会比事先预留慢个2~4倍 06/10 16:28
32F：→ aria0520: 原来如此 06/10 17:26