前端进阶: 总结几个常用的 JS 搜索算法和性能对比
前言
今天让我们来继续聊一聊 JS 算法，通过接下来的讲解，我们可以了解到搜索算法的基本实现以及各种实现方法的性能，进而发现 for 循环，forEach，While 的性能差异，我们还会了解到如何通过 Web Worker 做算法分片，极大的提高算法的性能。
同时我还会简单介绍一下经典的二分算法，哈希表查找算法，但这些不是本章的重点，之后我会推出相应的文章详细介绍这些高级算法，感兴趣的朋友可以关注我的专栏，或一起探讨。
对于算法性能，我们还是会采用上一章 《前端算法系列》如何让前端代码速度提高60倍 中的 getFnRunTime 函数，大家感兴趣的可以查看学习，这里我就不做过多说明。
在上一章 《前端算法系列》如何让前端代码速度提高60倍 我们模拟了 19000 条数据，这章中为了让效果更明显，我将伪造 170 万条数据来测试，不过相信我，对 js 来说这不算啥。。。
1. for 循环搜索
基本思路：通过 for 循环遍历数组，找出要搜索的值在数组中的索引，并将其推进新数组
代码实现如下：
const getFnRunTime = require('./getRuntime');
/**
* 普通算法-for循环版
* @param {*} arr
* 耗时：7-9ms
*/
function searchBy(arr, value) {
let result = [];
for(let i = 0, len = arr.length; i < len; i++) {
if(arr[i] === value) {
result.push(i);
}
}
return result
}
getFnRunTime(searchBy, 6)测试 n 次稳定后的结果如图：
2. forEach 循环
基本思路和 for 循环类似：
/**
* 普通算法-forEach循环版
* @param {*} arr
* 耗时：21-24ms
*/
function searchByForEach(arr, value) {
let result = [];
arr.forEach((item,i) => {
if(item === value) {
result.push(i);
}
})
return result
}耗时 21-24 毫秒，可见性能不如 for 循环（先暂且这么说哈，本质也是如此）。
3. while 循环
代码如下：
/**
* 普通算法-while循环版
* @param {*} arr
* 耗时：11ms
*/
function searchByWhile(arr, value) {
let i = arr.length,
result = [];
while(i) {
if(arr[i] === value) {
result.push(i);
}
i--;
}
return result
}可见 while 和 for 循环性能差不多，都很优秀，但也不是说 forEach 性能就不好，就不使用了。forEach 相对于 for 循环，代码减少了，但是 forEach 依赖 Enumerable。在运行时效率低于 for 循环。但是在处理不确定循环次数的循环，或者循环次数需要计算的情况下，使用 forEach 比较方便。而且 forEach 的代码经过编译系统的代码优化后，和 for 循环的循环类似。
4. 二分法搜索
二分法搜索更多的应用场景在数组中值唯一并且有序的数组中，这里就不比较它和 for/while/forEach 的性能了。
基本思路：从序列的中间位置开始比较，如果当前位置值等于要搜索的值，则查找成功；若要搜索的值小于当前位置值，则在数列的前半段中查找；若要搜索的值大于当前位置值则在数列的后半段中继续查找，直到找到为止
代码如下：
/**
* 二分算法
* @param {*} arr
* @param {*} value
*/
function binarySearch(arr, value) {
let min = 0;
let max = arr.length - 1;
while (min <= max) {
const mid = Math.floor((min + max) / 2);
if (arr[mid] === value) {
return mid;
} else if (arr[mid] > value) {
max = mid - 1;
} else {
min = mid + 1;
}
}
return 'Not Found';
}在数据量很大的场景下，二分法效率很高，但不稳定，这也是其在大数据查询下的一点小小的劣势。
5. 哈希表查找
哈希表查找又叫散列表查找，通过查找关键字不需要比较就可以获得需要记录的存储位置，它是通过在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f(key)
哈希表查找的使用场景：
- 哈希表最适合的求解问题是查找与给定值相等的记录
- 哈希查找不适合同样的关键字对应多条记录的情况
- 不适合范围查找，比如查找年龄 18~22 岁的同学
在这我先给出一个最简版的 hashTable，方便大家更容易的理解哈希散列：
/**
* 散列表
* 以下方法会出现数据覆盖的问题
*/
function HashTable() {
var table = [];
// 散列函数
var loseloseHashCode = function(key) {
var hash = 0;
for(var i=0; i<key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % 37
};
// put
this.put = function(key, value) {
var position = loseloseHashCode(key);
table[position] = value;
}
// get
this.get = function(key) {
return table[loseloseHashCode(key)]
}
// remove
this.remove = function(key) {
table[loseloseHashCode(key)] = undefined;
}
}该方法可能会出现数据冲突的问题，不过也有解决方案，由于这里涉及的知识点比较多，后期我会专门推出一篇文章来介绍：
- 开放定址法
- 二次探测法
- 随机探测法
使用 Web Worker 优化
通过以上的方法，我们已经知道各种算法的性能和应用场景了，我们在使用算法时，还可以通过 Web Worker 来优化，让程序并行处理，比如将一个大块数组拆分成多块，让 Web Worker 线程帮我们去处理计算结果，最后将结果合并，通过 Worker 的事件机制传给浏览器，效果十分显著。
总结
- 对于复杂数组查询，for/while 性能高于 forEach 等数组方法
- 二分查找法的 O(logn) 是一种十分高效的算法。不过它的缺陷也很明显：必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。数组读取效率是 O(1)，可是它的插入和删除某个元素的效率却是 O(n)。因而导致构建有序数组的时候会降低效率。
- 哈希表查找的基本用法及使用场景。
- 条件允许的话，我们可以用 Web Worker 来优化算法，让其在后台并行执行。
好啦，这篇文章虽然比较简单，但十分重要，希望大家对搜索算法有更加直观的认识，也希望大家有更好的方法，一起探讨交流。
作者：徐小夕，未经授权不可转载。
- 发表于:
- 本文为 InfoQ 中文站特供稿件
- 首发地址：https://www.infoq.cn/article/xDiio3hPZ2cYJEldKEW6
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
