Re: [讨论] 技术总监有可能不懂BFS吗??

楼主: leviliang (levi)   2023-04-23 04:31:46
来单纯技术讨论一下好了
其实 Visit 也不用限制一定要用 HashMap/HashSet 做
Leetcode 上很多题目的 nodes tag 都是连续的数字或英文字母
这个时候用一般的 Array 效能就会比 HashMap/HashSet 好非常多:
1. 不需动态分配内存(感谢一楼提醒)
2. 不需进行 Hash 运算
但也正如同大多数大大所说
一般人的想像场景不会是连续的标签
在 nodes tag 都不连续的情况下
例如:1, 100, 10000, 1000000, 100000000
这个时候用 Array 就是低能儿了
个人浅见如上
如有错误还请各位大大指正
补充 peter98 与 NTHUlagka 底下关于 Hash 的讨论(小弟对于 C++ 只能算是略懂,如
果错误就再麻烦指正了):
1. 就 C++ Standard Library 对于 HashMap/HashSet 的实作,一开始会先分配一定数量
的 buckets,后续如果超过 loading factor(默认 1.0),再动态增加(std::vecotor
的实作上
一般是加倍)。
2. 关于 Exponential Backoff 与 Bloom Filters 等其他技术,目前尚未实作于 Standa
rd Library 里,所以有需求的话要自行实作。
3. Bloom Filters 可以解放传统 HashSet 储存空间带来的限制,原理很简单,如果不太
清楚请中文维基就可以轻松看懂(一般大学的分布式系统课程也都会教到)。
作者: plsmaop (plsmaop)   2023-04-23 06:02:00
通常效能的差异不在于 hash ,而是不需要一直分配新的内存
作者: previa (.)   2023-04-23 08:11:00
主要差异就是在整个解法能不能scale 而已
作者: ku399999   2023-04-23 08:15:00
阵列如果资料一直往后放不排序 查询速度就是n 如果要排序就要移动大量资料 即使不用分配也快不到哪吧
作者: s06yji3 (阿南)   2023-04-23 08:44:00
阵列是固定size的东西。如果纪录的东西是整数,可以直接把他当作阵列的index,搜寻就是O(1)Nic作法是O(n) XD但是后来换成用Set了
作者: peter98 (新兵)   2023-04-23 11:43:00
用hash不代表要一直分配新的内存一直动态分配内存的不是hash 两者关系并不大
作者: s06yji3 (阿南)   2023-04-23 12:38:00
严格来说你要讲HashSet才对。
作者: NTHUlagka (拉卡)   2023-04-23 15:30:00
楼上你hash不动态分配内存 那新的值进来你要怎办 你一开始不知道要开多大的Hash吧还是其实C++hash背后也是vector 那就没事了
作者: a1234567289 (蛋包饭)   2023-04-23 15:51:00
hashmap/set都会牵涉到Load factor 当现在容器里装了超过一定比例的数量就会自动扩容 但确实hash与否和是否动态配置内存是两回事 此外本文的方法一也可以视为是一种hashset以上自动扩容我讲的是现今大多数语言的实作
作者: peter98 (新兵)   2023-04-23 19:43:00
额 s06yji3 看来你真的不董hash用到的vector其动态配置的做法&时机点 建议你找一本简单的算法课本读一下 = =hash会用到动态配置 但是hash如果遇到效能问题 问题根源不是在动态配置 这是两回事 每次都用动态配置会造成效能问题没错 但问题是hash不会出现老是一直需要动态配置 去把大三算法课本拿出来复习一下 = = 肯定有教靠 at错人 是NTHUlagka可以去读一下算法两件事 loading factor + 类似exp backoff的作法并不会让hash有动态配置造成的效能问题
作者: saladim (杀拉顶)   2023-04-23 20:30:00
Hash还有一些簿记的overhead, 而且长的也有80分像array若是在都要traversal近乎全部的状况 或许考虑的是nodeId的分布状况 阿 话说回来 不连续也能弄成连续的 纯array还是有其优势在
作者: NTHUlagka (拉卡)   2023-04-23 20:40:00
喔喔我知道啊 所以我想说如果hash背后是vector的那种方式扩充就没事了是你讲的好像没用到动态配置我才提出疑问怎可能没用到实际上是有用到但瓶颈不是在那边你这样讲不就好了喔喔没有是我搞错少看到一直 当小丑了 抱歉
作者: peter98 (新兵)   2023-04-23 20:50:00
hash背后即使不是vector 也不会有动态配置造成效能瓶颈的问题 现在论文再解决hash效能时 可以看到从来不是在管内存配置 极大程度代表动态配置的影响根本微乎其微真正的效能在于hash的设计 以及其查找的方法 最经典的例子就是bloom filter看来NTHU大大是认真讨论 我道歉~对不起~刚推文太邱~
作者: NTHUlagka (拉卡)   2023-04-23 20:58:00
我的错没看仔细 抱歉 所以瓶颈是在collision 那现在Hash的Hash function都是以bloom filter吗?还是有更新的
作者: peter98 (新兵)   2023-04-23 20:59:00
更正: "从来不是"在管内存配置 --> "很少"在管
作者: NTHUlagka (拉卡)   2023-04-23 21:06:00
喔喔原来是另一种有别于hash table的资料结构 genius感谢
作者: Lordaeron (Terry)   2023-04-24 20:23:00
https://github.com/terrylao/PascalContainer 这有你们讨论的东西的参考。他实作这么多了,该做总统了....
作者: superpandal   2023-04-29 20:05:00
java的hash不是重点 重点它怎么解决冲突这种东西有碰到再研究也不是不可以

Links booklink

Contact Us: admin [ a t ] ucptt.com