效率比STL內建好的hashmap

[aria0520 (紫)]

以前都是直接用stl的unordered_map
但最近發現他的速度很慢（理論上O(1) 但速度卻跟map差不多）
請問原因是什麼，並且有什麼能取代它的選擇？


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.99.96 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1559989412.A.4E7.html
推 yilanP: 速度跟map差不多是用感覺的嗎？
→ yilanP: 或是你的N已經超大了？
→ aria0520: 我知道理論上N很大時兩者會差不多 但奇怪的是我N沒很大
→ aria0520:   兩者一樣都比直接用矩陣存慢50ms左右
→ aria0520: 還是我不該期待hashmap能達到直接矩陣存的速度
→ Caesar08: 根據經驗，你的確不該
→ hsnuyi: O3開了嗎?
→ adrianshum: N 大才會有明顯分別吧？！
→ adxis: 試試先 reserve() 預期的大小
→ bibo9901: map 哪有 reserve... 難道樓上是指自訂Allocator
推 chchwy: N很大的時候hashmap的優勢才會出現阿
→ loveme00835: 先說說你的參數還有測量的方法
→ RishYang: 時間複雜度不等於執行時間啊
→ RishYang: unorderd map得到使用上的方便，必定會有犧牲
→ RishYang: 你可以去看看實作 https://reurl.cc/GYgOv
→ RishYang: 自己分析效能瓶頸或是https://youtu.be/M2fKMP47slQ
推 xavier13540: 如果你已經知道最後會有n個元素在std::unordered_map
→ xavier13540: 裡 傳入n當作constructor的argument可以避免rehash
推 xavier13540: 另外也可以用max_load_factor()改load factor 或者使
→ xavier13540: 用自己定義的hash 因為gcc的std::hash::operator()蠻
→ xavier13540: 爛的 吃什麼就吐什麼
→ aria0520: 也就是說我事先reserve足夠就能避免rehash了?
→ aria0520: 還是reserve完要自己rehash一次
→ aria0520: 所以stl的hashmap慢的原因是頻繁rehash
→ aria0520: 嗎
→ loveme00835: 你在示範怎麼抓藥嗎?
推 steve1012: 可以用abseil flat_hash_map
推 xavier13540: std::unordered_map<int> umi(10); // reserve at
→ xavier13540: least 10 buckets for umi
→ xavier13540: 如果只考慮不斷插入n個東西 由於rehash的緣故 跟
→ xavier13540: std::vector的效率一樣 大概會比事先預留慢個2~4倍
→ aria0520: 原來如此