js 中 indexOf 为什么比 Map 更快

This topic created in 1373 days ago, the information mentioned may be changed or developed.

https://leetcode.com/problems/first-unique-character-in-a-string/

LeetCode 上发现差别很大（我这里是 1532 ms VS 285 ms ），自己又测试了一下，发现结果一样：`indexOf` 比 `Map` 更快。

https://gist.github.com/zhyd1997/2ef651d8e0eeb55bb908be4dc3e7e01c

加 for loop：
```js
HashMap: 0.06787502765655518 ms
IndexOf: 0.025332987308502197 ms
```

不加 for loop:
```js
HashMap: 1214.1378329992294 ms
IndexOf: 158.00695902109146 ms
```

时间复杂度上 `indexOf` 解法应该是 O(n^2)，`Map` 解法是 O(n)？

是不是我的代码有问题，有没有办法让 `Map` 解法更快一点。

indexOf

map

快

比

13 replies • 2022-08-16 19:37:55 +08:00

otakustay

Aug 16, 2022

完全不等价的 2 个东西怎么比，你倒是拿个测试用例出来，数据量大不大。长度 10 的字符串找一个字段、长度 100 的字符串找一个子串、长度 10000 的字符串找子串，性能天差地别

zhyd1997

Aug 16, 2022

@otakustay #1

不好意思，点了一下 `显示 Gist 代码` 就发出来了。

renmu

Aug 16, 2022 via Android

indexof 是 O(N)，Map 是 O(1)

renmu

Aug 16, 2022 via Android

1. 你不能把写入时间算进去
2. map 获取数据是 map.get ，你那种写法把 map 转成了 array 重新计算有很大问题

zhyd1997

Aug 16, 2022

@renmu #3

我把外面那个 for 循环加进去得出来的时间复杂度。

falsemask

Aug 16, 2022

还有个可能，map 内存不是连续的，数组是连续的

zhyd1997

Aug 16, 2022

@renmu #4

L9 用的是 map.get

zhyd1997

Aug 16, 2022

我突然发现加个 1e6 的 for 循环没多大意义

weiwoxinyou

Aug 16, 2022

我觉得不是 map 和 indexOf 的问题，而是你这里两个测试不是一个标准。
对 map 的测试中，循环每次调用都进行了一次内存申请，而 indexOf 就是简单的 O(N)复杂度。
所以我认为这个测试结果实际上表示的是一次内存申请与一个 O(N)复杂度算法所消耗时间的差异。

otakustay

Aug 16, 2022

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

zhyd1997

Aug 16, 2022

确实，我搞错了，应该单独比较 map.get 和 indexOf 。

3282361

Aug 16, 2022

@YadongZhang #2

请问下「显示 Gist 代码」这个按钮是怎么发的

zhyd1997

Aug 16, 2022

@3282361

直接贴 Gist 链接即可