PTT數位生活區 / C_and_CPP (C/C++)

[討論] 效率比STL內建好的hashmap

看板C_and_CPP (C/C++)作者 (紫)時間6年前 (2019/06/08 18:23), 編輯推噓6(6推 0噓 26→)
留言32則, 12人參與, 6年前最新討論串1/1
以前都是直接用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
推
06/08 18:40, 6年前 , 1F
速度跟map差不多是用感覺的嗎？
06/08 18:40, 1F
→
06/08 18:40, 6年前 , 2F
或是你的N已經超大了？
06/08 18:40, 2F
→
06/08 18:56, 6年前 , 3F
我知道理論上N很大時兩者會差不多 但奇怪的是我N沒很大
06/08 18:56, 3F
→
06/08 18:56, 6年前 , 4F
兩者一樣都比直接用矩陣存慢50ms左右
06/08 18:56, 4F
→
06/08 18:59, 6年前 , 5F
還是我不該期待hashmap能達到直接矩陣存的速度
06/08 18:59, 5F
→
06/08 19:02, 6年前 , 6F
根據經驗，你的確不該
06/08 19:02, 6F
→
06/08 20:09, 6年前 , 7F
O3開了嗎?
06/08 20:09, 7F
→
06/08 20:50, 6年前 , 8F
N 大才會有明顯分別吧？！
06/08 20:50, 8F
→
06/09 02:39, 6年前 , 9F
試試先 reserve() 預期的大小
06/09 02:39, 9F
→
06/09 04:04, 6年前 , 10F
map 哪有 reserve... 難道樓上是指自訂Allocator
06/09 04:04, 10F
推
06/09 14:34, 6年前 , 11F
N很大的時候hashmap的優勢才會出現阿
06/09 14:34, 11F
→
06/09 16:20, 6年前 , 12F
先說說你的參數還有測量的方法
06/09 16:20, 12F
→
06/09 18:27, 6年前 , 13F
時間複雜度不等於執行時間啊
06/09 18:27, 13F
→
06/09 18:30, 6年前 , 14F
unorderd map得到使用上的方便，必定會有犧牲
06/09 18:30, 14F
→
06/09 18:34, 6年前 , 15F
你可以去看看實作 https://reurl.cc/GYgOv
06/09 18:34, 15F
→
06/09 18:36, 6年前 , 16F
自己分析效能瓶頸或是https://youtu.be/M2fKMP47slQ
06/09 18:36, 16F
推
06/09 20:12, 6年前 , 17F
如果你已經知道最後會有n個元素在std::unordered_map
06/09 20:12, 17F
→
06/09 20:13, 6年前 , 18F
裡 傳入n當作constructor的argument可以避免rehash
06/09 20:13, 18F
推
06/09 20:18, 6年前 , 19F
另外也可以用max_load_factor()改load factor 或者使
06/09 20:18, 19F
→
06/09 20:19, 6年前 , 20F
用自己定義的hash 因為gcc的std::hash::operator()蠻
06/09 20:19, 20F
→
06/09 20:19, 6年前 , 21F
爛的 吃什麼就吐什麼
06/09 20:19, 21F
→
06/09 20:34, 6年前 , 22F
也就是說我事先reserve足夠就能避免rehash了?
06/09 20:34, 22F
→
06/09 20:35, 6年前 , 23F
還是reserve完要自己rehash一次
06/09 20:35, 23F
→
06/09 20:35, 6年前 , 24F
所以stl的hashmap慢的原因是頻繁rehash
06/09 20:35, 24F
→
06/09 20:35, 6年前 , 25F
嗎
06/09 20:35, 25F
→
06/09 23:34, 6年前 , 26F
你在示範怎麼抓藥嗎?
06/09 23:34, 26F
推
06/10 00:47, 6年前 , 27F
可以用abseil flat_hash_map
06/10 00:47, 27F
推
06/10 16:27, 6年前 , 28F
std::unordered_map<int> umi(10); // reserve at
06/10 16:27, 28F
→
06/10 16:27, 6年前 , 29F
least 10 buckets for umi
06/10 16:27, 29F
→
06/10 16:28, 6年前 , 30F
如果只考慮不斷插入n個東西 由於rehash的緣故 跟
06/10 16:28, 30F
→
06/10 16:28, 6年前 , 31F
std::vector的效率一樣 大概會比事先預留慢個2~4倍
06/10 16:28, 31F
→
06/10 17:26, 6年前 , 32F
原來如此
06/10 17:26, 32F
‣ 更多 aria0520 的文章
文章代碼(AID): #1S-uoaJd (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 aria0520 的文章
文章代碼(AID): #1S-uoaJd (C_and_CPP)