首页   注册   登录
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 · 4 天前 · 1066 次点击

    某日。 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 性能差的原因和理由在哪。 谁来把我打清醒。

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

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

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

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

    注意我说的各种情况是指,你是否可以对你的代码有足够的控制力,或者知道什么是优秀的代码。
    jmc891205
        11
    jmc891205   4 天前
    看场景吧 如果只是一次性的查找 那用 array.find 也还行 性能的瓶颈也不太可能出现在这里
    但如果是需要重复查找 比如在一个循环里每次迭代都要到这个 array 里查找 那用 array.find 的总的时间复杂度可能就变成 O(n^2)甚至更高了
    wysnylc
        12
    wysnylc   4 天前
    @seenthewind #10 赞同,写东西时不考虑沉没成本和过度沉没成本都不可取
    NullData
        13
    NullData   4 天前 via Android
    应该是 Array.prototype.find(指正)
    wednesdayco
        14
    wednesdayco   4 天前
    @NullData 谢老哥指正
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3623 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 51ms · UTC 10:20 · PVG 18:20 · LAX 03:20 · JFK 06:20
    ♥ Do have faith in what you're doing.