作者leviliang (慕尼黑林志颖)
看板Soft_Job
标题Re: [讨论] 技术总监有可能不懂BFS吗??
时间Sun Apr 23 04:31:46 2023
来单纯技术讨论一下好了
其实 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 储存空间带来的限制，原理很简单，如果不太
清楚请中文维基就可以轻松看懂（一般大学的分散式系统课程也都会教到）。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 138.246.3.10 (德国)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1682195508.A.1B8.html
※ 编辑: leviliang (138.246.3.10 德国), 04/23/2023 04:36:07
1F：推 plsmaop: 通常效能的差异不在於 hash ，而是不需要一直分配新的记04/23 06:02
2F：→ plsmaop: 忆体04/23 06:02
感谢提醒 我居然忽略了这最重要的一环
3F：→ previa: 主要差异就是在整个解法能不能scale 而已04/23 08:11
这也是一个很棒的考量点！
4F：→ ku399999: 阵列如果资料一直往後放不排序 查询速度就是n 如果要排04/23 08:15
5F：→ ku399999: 序就要移动大量资料 即使不用分配也快不到哪吧04/23 08:17
等等 一般的做法是一个布林阵列然後 node tag 当做 index
因此找 visited node 就是 O(1)
我其实没很仔细看 Nic 怎麽实作
还是他的实作是你说的方式！？
※ 编辑: leviliang (138.246.3.10 德国), 04/23/2023 08:42:54
6F：推 s06yji3: 阵列是固定size的东西。如果纪录的东西是整数，可以直接04/23 08:44
7F：→ s06yji3: 把他当作阵列的index，搜寻就是O(1)04/23 08:44
8F：→ s06yji3: Nic作法是O(n) XD04/23 08:45
9F：→ s06yji3: 但是後来换成用Set了04/23 08:45
10F：嘘 peter98: 用hash不代表要一直分配新的记忆体04/23 11:43
11F：→ peter98: 一直动态分配记忆体的不是hash 两者关系并不大04/23 11:43
12F：推 s06yji3: 严格来说你要讲HashSet才对。04/23 12:38
13F：→ NTHUlagka: 楼上你hash不动态分配记忆体 那新的值进来你要怎办 你04/23 15:30
14F：→ NTHUlagka: 一开始不知道要开多大的Hash吧 04/23 15:30
15F：→ NTHUlagka: 还是其实C++hash背後也是vector 那就没事了04/23 15:43
16F：推 a1234567289: hashmap/set都会牵涉到Load factor 当现在容器里装 04/23 15:51
17F：→ a1234567289: 了超过一定比例的数量就会自动扩容 但确实hash与否 04/23 15:51
18F：→ a1234567289: 和是否动态配置记忆体是两回事 此外本文的方法一04/23 15:51
19F：→ a1234567289: 也可以视为是一种hashset 04/23 15:51
20F：→ a1234567289: 以上自动扩容我讲的是现今大多数语言的实作04/23 15:52
21F：→ peter98: 额 s06yji3 看来你真的不董hash用到的vector其动态配置 04/23 19:43
22F：→ peter98: 的做法&时机点 建议你找一本简单的演算法课本读一下 = = 04/23 19:43
23F：→ peter98: hash会用到动态配置 但是hash如果遇到效能问题 问题根04/23 19:44
24F：→ peter98: 源不是在动态配置 这是两回事 每次都用动态配置会造成04/23 19:45
25F：→ peter98: 效能问题没错 但问题是hash不会出现老是一直需要动态配04/23 19:45
26F：→ peter98: 置 去把大三演算法课本拿出来复习一下 = = 肯定有教04/23 19:45
27F：→ peter98: 靠 at错人 是NTHUlagka可以去读一下演算法04/23 19:47
28F：→ peter98: 两件事 loading factor + 类似exp backoff的作法04/23 19:48
29F：→ peter98: 并不会让hash有动态配置造成的效能问题04/23 19:48
30F：→ saladim: Hash还有一些簿记的overhead, 而且长的也有80分像array04/23 20:30
31F：→ saladim: 若是在都要traversal近乎全部的状况 或许考虑的是nodeId04/23 20:31
32F：→ saladim: 的分布状况 阿 话说回来 不连续也能弄成连续的 纯array04/23 20:32
33F：→ saladim: 还是有其优势在04/23 20:32
34F：推 NTHUlagka: 喔喔我知道啊 所以我想说如果hash背後是vector的那种04/23 20:40
35F：→ NTHUlagka: 方式扩充就没事了04/23 20:40
36F：→ NTHUlagka: 是你讲的好像没用到动态配置我才提出疑问怎可能没用到 04/23 20:42
37F：→ NTHUlagka: 实际上是有用到但瓶颈不是在那边你这样讲不就好了04/23 20:42
38F：推 NTHUlagka: 喔喔没有是我搞错少看到一直 当小丑了 抱歉 04/23 20:44
39F：→ peter98: hash背後即使不是vector 也不会有动态配置造成效能瓶颈 04/23 20:50
40F：→ peter98: 的问题 现在论文再解决hash效能时 可以看到从来不是在04/23 20:50
41F：→ peter98: 管记忆体配置 极大程度代表动态配置的影响根本微乎其微 04/23 20:51
42F：→ peter98: 真正的效能在於hash的设计 以及其查找的方法 最经典的04/23 20:51
43F：→ peter98: 例子就是bloom filter 04/23 20:51
44F：→ peter98: 看来NTHU大大是认真讨论 我道歉~对不起~刚推文太邱~ 04/23 20:52
45F：推 NTHUlagka: 我的错没看仔细 抱歉 所以瓶颈是在collision 那现在Ha04/23 20:58
46F：→ NTHUlagka: sh的Hash function都是以bloom filter吗？还是有更新04/23 20:58
47F：→ NTHUlagka: 的04/23 20:58
48F：→ peter98: 更正: "从来不是"在管记忆体配置 --> "很少"在管04/23 20:59
49F：→ NTHUlagka: 喔喔原来是另一种有别於hash table的资料结构 genius04/23 21:06
50F：→ NTHUlagka: 感谢04/23 21:06
感谢各位的讨论与分享
资讯量很大我一起整理到本文中
顺便把名词打清楚
※ 编辑: leviliang (138.246.3.10 德国), 04/23/2023 23:09:39
※ 编辑: leviliang (138.246.3.10 德国), 04/24/2023 03:48:50
52F：→ Lordaeron: 们讨论的东西的参考。他实作这麽多了，该做总统了.... 04/24 20:24
53F：→ superpandal: java的hash不是重点 重点它怎麽解决冲突 04/29 20:05
54F：→ superpandal: 这种东西有碰到再研究也不是不可以 04/29 20:06