V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
wednesdayco
V2EX  ›  JavaScript

Array.find 的性能问题讨论

  •  
  •   wednesdayco · 2020-03-26 11:29:59 +08:00 · 3439 次点击
    这是一个创建于 1463 天前的主题,其中的信息可能已经有所发展或是发生改变。

    某日。 Code Review 。 某老大:你这个不能用 find 啊,这函数性能太差了。 我:性能差?

    let arr=[];
    for(let i=0;i<=1000000;i++){
    	arr.push('abcdefghigk'+i);
    }
    let v0='abcdefghigk'+parseInt(Math.random()*1000000,10);//比较随机值
    let v1='abcdefghigk1000000';//比较最后一个
    console.warn('get random value:',v0);
    console.log('for in :');//for in 方式查询
    console.time('arr');
    let find =false;
    for(let i in arr){
    	if(arr[i]===v0){
    		find=true;
    		break;
    	}
    }
    console.timeEnd('arr');
    console.log('for i++:');//for i++方式查询
    console.time('arr');
    find =false;
    for(let i=0,len=arr.length;i<len;i++){
    	if(arr[i]===v0){
    		find=true;
    		break;
    	}
    }
    console.timeEnd('arr');
    console.log('Array.find:');//join 方式查询
    console.time('arr');
    find = arr.find(item=>item===v0)
    console.timeEnd('arr');
    
    console.warn('get max value:',v1);
    console.log('for in :');//for in 方式查询
    console.time('arr');
    find =false;
    for(let i in arr){
    	if(arr[i]===v1){
    		find=true;
    		break;
    	}
    }
    console.timeEnd('arr');
    console.log('for i++:');//for i++方式查询
    console.time('arr');
    find =false;
    for(let i=0,len=arr.length;i<len;i++){
    	if(arr[i]===v1){
    		find=true;
    		break;
    	}
    }
    console.timeEnd('arr');
    console.log('Array.find:');//join 方式查询
    console.time('arr');
    find = arr.find(item=>item===v1)
    console.timeEnd('arr');
    
    get random value: abcdefghigk275952
    for in :
    arr: 157.901123046875ms
    for i++:
    arr: 7.884033203125ms
    Array.find:
    arr: 7.52099609375ms
    get max value: abcdefghigk1000000
    for in :
    arr: 223.169921875ms
    for i++:
    arr: 7.137939453125ms
    Array.find:
    arr: 18.552001953125ms
    

    我实在是不太清楚大佬说的 find 性能差的原因和理由在哪。 谁来把我打清醒。

    15 条回复    2020-04-11 11:50:32 +08:00
    bnm965321
        1
    bnm965321  
       2020-03-26 11:40:36 +08:00
    有可能不是说 find 性能差。而是说在那个算法场景下,可能用 hashmap 空间换时间会更好.
    wysnylc
        2
    wysnylc  
       2020-03-26 11:43:45 +08:00
    精确查找不用 hash 的十有八九是傻
    wednesdayco
        3
    wednesdayco  
    OP
       2020-03-26 11:53:20 +08:00
    @wysnylc 就一般说来不会超过 20 个值的数组里匹配一个值。。。。。上啥 hash 表……
    newmlp
        4
    newmlp  
       2020-03-26 11:56:56 +08:00
    其实在 JS 引擎里面,数组和 map 都是哈希表实现的,没啥区别
    reus
        5
    reus  
       2020-03-26 12:06:37 +08:00
    @newmlp 键不同,性质就不同,区别大了
    maggch
        6
    maggch  
       2020-03-26 12:25:18 +08:00
    不用 find 是因为有更好的实现,不是说你要自己写一个循环做 find 。每个地方都这样慢一点,整个系统就快不起来。
    vanton
        7
    vanton  
       2020-03-26 12:27:59 +08:00
    hashmap 明显更好,为什么不用?
    morethansean
        8
    morethansean  
       2020-03-26 12:59:30 +08:00
    @newmlp #4
    ...区别大了,v8 第一节课不就告诉你要避免数组退化到字典模式。
    optional
        9
    optional  
       2020-03-26 13:07:29 +08:00
    看规模的,小数组,直接遍历反而更快,因为 hash 的 O1 是有系数的。
    其实各个语言的字符串 indexOf/contains 也不用 kmp 实现,一样的道理。
    seenthewind
        10
    seenthewind  
       2020-03-26 13:14:35 +08:00
    如果你是想证明 find 比 hash 性能强,在某些场景下是可以,我觉得不需要贴这么多代码。

    如果你想讨论 find 和 hash 的优劣,我建议直接讨论到算法或者汇编指令的程度,贴代码和耗时是比较,怎么说,简单的想法。

    我还以为 v 站难的出现了精彩的技术讨论帖,看来还是对 leader 有意见找个地方吐槽嘛。。

    顺带一提,我是会建议用 hash,理由很简单,O(1)的常量开销是固定的,但 find 是会波动的,如果你的代码要长时间运行,就要考虑各种情况。

    注意我说的各种情况是指,你是否可以对你的代码有足够的控制力,或者知道什么是优秀的代码。
    jmc891205
        11
    jmc891205  
       2020-03-26 13:25:42 +08:00
    看场景吧 如果只是一次性的查找 那用 array.find 也还行 性能的瓶颈也不太可能出现在这里
    但如果是需要重复查找 比如在一个循环里每次迭代都要到这个 array 里查找 那用 array.find 的总的时间复杂度可能就变成 O(n^2)甚至更高了
    wysnylc
        12
    wysnylc  
       2020-03-26 14:43:06 +08:00
    @seenthewind #10 赞同,写东西时不考虑沉没成本和过度沉没成本都不可取
    NullData
        13
    NullData  
       2020-03-26 15:29:30 +08:00 via Android
    应该是 Array.prototype.find(指正)
    wednesdayco
        14
    wednesdayco  
    OP
       2020-03-26 16:42:34 +08:00
    @NullData 谢老哥指正
    xcstream
        15
    xcstream  
       2020-04-11 11:50:32 +08:00
    起个名字 quickfind,然后注释优化 find 性能。
    具体快不快就不重要了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5239 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 01:24 · PVG 09:24 · LAX 18:24 · JFK 21:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.