1
otakustay 2022-08-16 10:11:08 +08:00
完全不等价的 2 个东西怎么比,你倒是拿个测试用例出来,数据量大不大。长度 10 的字符串找一个字段、长度 100 的字符串找一个子串、长度 10000 的字符串找子串,性能天差地别
|
2
YadongZhang OP |
3
renmu 2022-08-16 10:23:31 +08:00 via Android
indexof 是 O(N),Map 是 O(1)
|
4
renmu 2022-08-16 10:27:12 +08:00 via Android
1. 你不能把写入时间算进去
2. map 获取数据是 map.get ,你那种写法把 map 转成了 array 重新计算有很大问题 |
5
YadongZhang OP |
6
falsemask 2022-08-16 10:29:53 +08:00
还有个可能,map 内存不是连续的,数组是连续的
|
7
YadongZhang OP |
8
YadongZhang OP 我突然发现加个 1e6 的 for 循环没多大意义
|
9
weiwoxinyou 2022-08-16 11:08:36 +08:00 1
我觉得不是 map 和 indexOf 的问题,而是你这里两个测试不是一个标准。
对 map 的测试中,循环每次调用都进行了一次内存申请,而 indexOf 就是简单的 O(N)复杂度。 所以我认为这个测试结果实际上表示的是一次内存申请与一个 O(N)复杂度算法所消耗时间的差异。 |
10
otakustay 2022-08-16 11:49:42 +08:00 1
1. 你把 new Map 和 map.set 的逻辑放到外面来只初始化一次,每次查找的性能只是 map.get
2. 因为你的测试用例的设计问题,相当于每一次 Map 的测试也包含了一个 str 的遍历,那显然比“只有一次遍历”的 indexOf 慢,明摆着的嘛 3. str.split('')理论上是有特殊优化的,因为 string 本质是 char[],.split('')只要把 char[]返回回来就行,不用真正的做 split 的逻辑 4. 这个测试慢的应该就是 new Map + map.set VS 优化过的 str.split(''),而不是 map.get VS array.indexOf |
11
YadongZhang OP 确实,我搞错了,应该单独比较 map.get 和 indexOf 。
|
12
3282361 2022-08-16 12:07:17 +08:00
|
13
YadongZhang OP |