V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
YadongZhang
V2EX  ›  生活

js 中 indexOf 为什么比 Map 更快

  •  
  •   YadongZhang · 103 天前 · 1873 次点击
    这是一个创建于 103 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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` 解法更快一点。
    13 条回复    2022-08-16 19:37:55 +08:00
    otakustay
        1
    otakustay  
       103 天前
    完全不等价的 2 个东西怎么比,你倒是拿个测试用例出来,数据量大不大。长度 10 的字符串找一个字段、长度 100 的字符串找一个子串、长度 10000 的字符串找子串,性能天差地别
    YadongZhang
        2
    YadongZhang  
    OP
       103 天前
    @otakustay #1

    不好意思,点了一下 `显示 Gist 代码` 就发出来了。
    renmu
        3
    renmu  
       103 天前 via Android
    indexof 是 O(N),Map 是 O(1)
    renmu
        4
    renmu  
       103 天前 via Android
    1. 你不能把写入时间算进去
    2. map 获取数据是 map.get ,你那种写法把 map 转成了 array 重新计算有很大问题
    YadongZhang
        5
    YadongZhang  
    OP
       103 天前
    @renmu #3

    我把外面那个 for 循环加进去得出来的时间复杂度。
    falsemask
        6
    falsemask  
       103 天前
    还有个可能,map 内存不是连续的,数组是连续的
    YadongZhang
        7
    YadongZhang  
    OP
       103 天前
    @renmu #4

    L9 用的是 map.get
    YadongZhang
        8
    YadongZhang  
    OP
       103 天前
    我突然发现加个 1e6 的 for 循环没多大意义
    weiwoxinyou
        9
    weiwoxinyou  
       103 天前   ❤️ 1
    我觉得不是 map 和 indexOf 的问题,而是你这里两个测试不是一个标准。
    对 map 的测试中,循环每次调用都进行了一次内存申请,而 indexOf 就是简单的 O(N)复杂度。
    所以我认为这个测试结果实际上表示的是一次内存申请与一个 O(N)复杂度算法所消耗时间的差异。
    otakustay
        10
    otakustay  
       103 天前   ❤️ 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
    YadongZhang
        11
    YadongZhang  
    OP
       103 天前
    确实,我搞错了,应该单独比较 map.get 和 indexOf 。
    3282361
        12
    3282361  
       103 天前
    @YadongZhang #2

    请问下「显示 Gist 代码」这个按钮是怎么发的
    YadongZhang
        13
    YadongZhang  
    OP
       103 天前
    @3282361

    直接贴 Gist 链接即可
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3066 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 41ms · UTC 14:27 · PVG 22:27 · LAX 06:27 · JFK 09:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.