这是一个创建于 842 天前的主题，其中的信息可能已经有所发展或是发生改变。
https://leetcode.com/problems/first-unique-character-in-a-string/
LeetCode 上发现差别很大（我这里是 1532 ms VS 285 ms ），自己又测试了一下，发现结果一样：`indexOf` 比 `Map` 更快。
加 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` 解法更快一点。
LeetCode 上发现差别很大（我这里是 1532 ms VS 285 ms ），自己又测试了一下，发现结果一样：`indexOf` 比 `Map` 更快。
加 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` 解法更快一点。
 |
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 |
Select Language