作者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/m.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