Array.find 的性能问题讨论

[wednesdayco]

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

[bnm965321]

有可能不是说 find 性能差。而是说在那个算法场景下，可能用 hashmap 空间换时间会更好.

[wysnylc]

精确查找不用 hash 的十有八九是傻

[wednesdayco]

@wysnylc 就一般说来不会超过 20 个值的数组里匹配一个值。。。。。上啥 hash 表……

[newmlp]

其实在 JS 引擎里面，数组和 map 都是哈希表实现的，没啥区别

[reus]

@newmlp 键不同，性质就不同，区别大了

[maggch]

不用 find 是因为有更好的实现，不是说你要自己写一个循环做 find 。每个地方都这样慢一点，整个系统就快不起来。

[vanton]

hashmap 明显更好，为什么不用？

[morethansean]

@newmlp #4
...区别大了，v8 第一节课不就告诉你要避免数组退化到字典模式。

[optional]

看规模的，小数组，直接遍历反而更快，因为 hash 的 O1 是有系数的。
其实各个语言的字符串 indexOf/contains 也不用 kmp 实现，一样的道理。

[seenthewind]

如果你是想证明 find 比 hash 性能强，在某些场景下是可以，我觉得不需要贴这么多代码。

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

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

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

注意我说的各种情况是指，你是否可以对你的代码有足够的控制力，或者知道什么是优秀的代码。

[jmc891205]

看场景吧 如果只是一次性的查找 那用 array.find 也还行 性能的瓶颈也不太可能出现在这里
但如果是需要重复查找 比如在一个循环里每次迭代都要到这个 array 里查找 那用 array.find 的总的时间复杂度可能就变成 O(n^2)甚至更高了

[wysnylc]

@seenthewind #10 赞同,写东西时不考虑沉没成本和过度沉没成本都不可取

[NullData]

应该是 Array.prototype.find(指正)

[wednesdayco]

@NullData 谢老哥指正

[xcstream]

起个名字 quickfind，然后注释优化 find 性能。
具体快不快就不重要了