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

Array.find 的性能问题讨论

  •  
  •   wednesdayco · 8 天前 · 1131 次点击

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

    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
    

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

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

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

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

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

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