JS基本搜索算法实现与170万条数据下的性能测试

更新日期: 2022-04-29阅读: 888标签: 搜索

前言

今天让我们来继续聊一聊js算法,通过接下来的讲解,我们可以了解到搜索算法的基本实现以及各种实现方法的性能,进而发现for循环,forEach,While的性能差异,我们还会了解到如何通过web worker做算法分片,极大的提高算法的性能。

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依赖IEnumerable。在运行时效率低于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来优化算法,让其在后台并行执行。

来源: 趣谈前端

链接: https://fly63.com/article/detial/11422

好看css搜索框样式_分享8款纯CSS搜索框

最简单实用的CSS3搜索框样式,纯CSS效果无需任何javascript,其中部分搜索框在点击的时候有动画特效,搜索框的应用也是比较普通的,代码如下!

如何使用robots禁止各大搜索引擎爬虫爬取网站

都会有一句由于robots.txt文件存在限制指令无法提供内容描述,.原来一般来说搜索引擎爬取网站时都会,先读取下robots.txt文件,并依照里面所设定的规则去爬取网站。

Lucene全文检索入门使用

全文检索是计算机程序通过扫描文章中的每一个词,对每一个词建立一个索引,指明该词在文章中出现的次数和位置。当用户查询时根据建立的索引查找,类似于通过字典的检索字表查字的过程

程序员应该掌握的 10 个搜索技巧

在今天,用户可以通过搜索引擎轻松找出自己想要的信息,但还是难以避免结果不尽如人意的情况。实际上,用户仅需掌握几个常用技巧即可轻松化解这种尴尬。下面介绍 10 个在进行 Google 搜索时可以使用的便捷技巧

vue的mescroll搜索运用以及各种填坑处理

用户未输入搜索关键词时,mescroll不能就直接初始话,要在用户输入的时候才能初始化,所以子组件就接受了父组件的keyword,并用 v-if来判断加载子组件的条件,然后子组件通过监听keyword的变化

隐藏搜索框:CSS 动画正反向序列

顶部菜单栏中放置搜索框是一个常见的场景,但如果搜索功能使用的不那么频繁,同时菜单栏中内容本来就比较拥挤,再放一个完整的搜索框在那就显得不那么美观。因此也有一个挺常见的做法是,只放一个搜索图标,需要时再显示整个搜索框

程序员如何查资料(百度、谷歌搜索技巧汇总)

intitle——把搜索范围限定在网页标题中;inurl——把搜索范围限定在url链接中;site——把搜索范围限定在特定站点中;精确匹配、加减号、通配符精确匹配:可以用双引号和书名号

ECMAScript 提案:.findLast()和.findLastIndex()从尾到头搜索数组

今天来看一个 ECMAScript 提案:findLast() 和 findLastIndex()。提案原因:在 JavaScript 中,可以通过 find() 和 findIndex() 查找数组中的值。不过,这些方法从数组的开始进行遍历

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!