《前端算法系列》如何让前端代码速度提高60倍

徐小夕 等级 775 0 0
标签: Javascript

《前端算法系列》如何让前端代码速度提高60倍 今天的问题从排序算法入手,来讲解如何根据业务需求,结合金典的算法,来实现js高性能开发。

情景

老板让小明给公司的20000+条数据排个序,但是由于排序的操作会频繁发生,如果操作执行的时间很慢,则会严重降低用户体验,听到这条噩耗后小明开始了代码。

1.毫无违和感的排序算法 小明根据需求,思考了一会,写下了如下算法:

/**
 * max排序
 * @param {*} arr 
 * 耗时:760ms
 */
 function maxSort(arr) {
     let result = [...arr];
     for(let i=0,len=result.length; i< len; i++) {
        let minV = Math.min(...result.slice(i))
        let pos = result.indexOf(minV,i)
        result.splice(pos, 1)
        result.unshift(minV)
     }
     return result.reverse()
 }

自信的小明陶醉在自己的算法中,准备测试一下性能,

/*
 * @Author: Mr Jiang.Xu 
 * @Date: 2019-06-11 10:25:23 
 * @Last Modified by: Mr Jiang.Xu
 * @Last Modified time: 2019-06-13 21:03:59
 * @desc 测试函数执行的时间
 */

const testArr = require('./testArr');
module.exports = async function getFnRunTime(fn) {
    let len = testArr.length;
    let startTime = Date.now(), endTime;
    let result = await fn(testArr);
    endTime = Date.now();
    console.log(result);
    console.log(`total time:${endTime-startTime}ms`,
                'test array\'length:' + len, 
                result.length
    );
}

运行该测试函数后,耗时760ms,小明觉得还不错,放到项目中后,第一次操作还好,连续操作了几次后,页面明显卡顿。。。(求此时小明心里的阴影面积)

2.冒泡排序

小明不甘心,在网上查找相关资料后,写下了如下冒泡排序代码:

/**
  * 置换函数
  * @param {源数组} arr 
  * @param {原数组的A项} indexA 
  * @param {原数组的B项} indexB 
  */
 function swap(arr, indexA, indexB) {
    [arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]];
 }

/**
 * 原始冒泡排序
 * @param {数组} arr 
 * 耗时:377ms
 */
 function bubbleSort1(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
      for (let j = 0; j < i; j++) {
        if (arr[j] > arr[j + 1]) {
          swap(arr, j, j + 1);
        }
      }
    }

    return arr;
  }

测试后耗时377ms,完美,小明放到项目中测试,频繁排序还是会有点卡顿,能不能再优化一下呢? 思考许久之后,小明完善了冒泡排序:

/**
 * 利用索引优化后的冒泡排序
 * @param {数组} arr 
 * 耗时:350ms
 */ 
function bubbleSort2(arr) {
    let i = arr.length - 1;

    while (i > 0) {
        let pos = 0;

        for (let j = 0; j < i; j++) {
        if (arr[j] > arr[j + 1]) {
            pos = j;
            swap(arr, j, j + 1);
        }
        }
        i = pos;
    }

    return arr;
}

根据缓存索引位置来提高排序性能,时间节约了20ms,但收益很小。小明开始和自己过不去了,在维基百科上继续查找,最后发现了一个方法:

/**
 * 在每趟排序中进行正向和反向两遍冒泡 ,
 * 一次可以得到两个最终值(最大和最小), 
 * 从而使外排序趟数大概减少了一半
 * @param {*} arr 
 * 耗时:312ms
 */
function bubbleSort3(arr) {
    let start = 0;
    let end = arr.length - 1;

    while (start < end) {
      let endPos = 0;
      let startPos = 0;
      for (let i = start; i < end; i++) {
        if (arr[i] > arr[i + 1]) {
            endPos = i;
            swap(arr, i, i + 1);
        }
      }
      end = endPos;
      for (let i = end; i > start; i--) {
        if (arr[i - 1] > arr[i]) {
          startPos = i;  
          swap(arr, i - 1, i);
        }
      }
      start = startPos;
    }

    return arr;
  }

通过在每趟排序中进行正向和反向两遍冒泡,小明把时间又降低了38ms,不错~ 《前端算法系列》如何让前端代码速度提高60倍 再次推荐大家有事多上上维基百科,总有一款适合你。 ####3.插入排序 在收入小规模胜利后,小明膨胀了,狂言要把排序时间降低到100ms一下,于是后又安利了如下算法:

/**
   * 插入排序 -- 基础版
   * @param {*} arr 
   * 耗时:897ms
   */
  function insertionSort(arr) {
    for (let i = 1, len = arr.length; i < len; i++) {
      const temp = arr[i];
      let preIndex = i - 1;

      while (arr[preIndex] > temp) {
        arr[preIndex + 1] = arr[preIndex];
        preIndex -= 1;
      }
      arr[preIndex + 1] = temp;
    }

    return arr;
  }

897ms,小明留下了没技术的泪水。 《前端算法系列》如何让前端代码速度提高60倍 最后小明拿出了这个看家本领,查到了二分搜索,最后改造后代码入下:

/**
   * 改造二分查找,查找小于value且离value最近的值的索引
   * @param {*} arr 
   * @param {*} maxIndex 
   * @param {*} value 
   */
  function binarySearch1(arr, maxIndex, value) {
    let min = 0;
    let max = maxIndex;

    while (min <= max) {
      const m = Math.floor((min + max) / 2);

      if (arr[m] <= value) {
        min = m + 1;
      } else {
        max = m - 1;
      }
    }

    return min;
  }

/**
 * 使用二分法来优化插入排序
 * @param {*} arr 
 * 耗时:86ms
 */
function insertionSort1(arr) {
    for (let i = 1, len = arr.length; i < len; i++) {
        const temp = arr[i];
        const insertIndex = binarySearch1(arr, i - 1, arr[i]);

        for (let preIndex = i - 1; preIndex >= insertIndex; preIndex--) {
        arr[preIndex + 1] = arr[preIndex];
        }
        arr[insertIndex] = temp;
    }

    return arr;
}

完美,只用了86ms!小明激动的站了起来,还拍了下桌子,全然无视观众的眼光。 《前端算法系列》如何让前端代码速度提高60倍 小明已经满足的不要不要的了,对86ms相当满意,老板也对他刮目想看。

4.希尔排序

难道就没有提升的余地了么?进过调查研究表明,是有更优的方案的:

/**
 * 希尔排序
 * 核心:通过动态定义的 gap 来排序,先排序距离较远的元素,再逐渐递进
 * @param {*} arr 
 * 耗时:15ms
 */
function shellSort(arr) {
    const len = arr.length;
    let gap = Math.floor(len / 2);

    while (gap > 0) {
      // gap距离
      for (let i = gap; i < len; i++) {
        const temp = arr[i];
        let preIndex = i - gap;

        while (arr[preIndex] > temp) {
          arr[preIndex + gap] = arr[preIndex];
          preIndex -= gap;
        }
        arr[preIndex + gap] = temp;
      }
      gap = Math.floor(gap / 2);
    }

    return arr;
  }

耗时15ms,膜拜。 ####5.归并排序

/**
 * 归并排序
 * @param {*} arr 
 * 耗时 30ms
 */
function concatSort(arr) {
  const len = arr.length;

  if (len < 2) { return arr; }

  const mid = Math.floor(len / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return concat(concatSort(left), concatSort(right));
}

function concat(left, right) {
  const result = [];

  while (left.length > 0 && right.length > 0) {
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
  }

  return result.concat(left, right);
}

耗时30ms,也想当优秀。还有没有更快的方法呢?答案是有的,但是会涉及到比较高僧的数学知识,放弃吧,孩子。。。《前端算法系列》如何让前端代码速度提高60倍

接下来会推出更多优秀的算法,敬请期待哦~ 最后,欢迎加入前端技术群,一起探讨前端的魅力

更多推荐

收藏
评论区

相关推荐

JS排序算法
引子 有句话怎么说来着: 雷锋推倒雷峰塔,Java implements JavaScript. 当年,想凭借抱Java大腿火一把而不惜把自己名字给改了的JavaScript(原名LiveScript),如今早已光芒万丈。node JS的出现更是让JavaScript可以前后端通吃。虽然Java依然制霸企业级软件开发领域(C/C 的大神们不要打
这些 JavaScript函数让你的工作更加 So Easy!
作者: YoussefZidan 译者:前端小智 来源:dev 点赞再看,养成习惯 本文 GitHub https://github.com/qq44924588...(https://github.com/qq449245884/xiaozhi) 上已经收录,更多往期高赞文章的分类,也整理了很多我的文档,和教程资料。欢迎Star和
JS弹出对话框的三种方式
JS弹出对话框的三种方式 ------------ 我们用到了alert()方法、prompt()方法、prompt()方法,都是在网页有一个弹出框,那么就让我们探究一下他们之间的区别: 一、第一种:alert()方法 <html> <head> <title>编写html页面</title>
10 个非常有用的 SVG 动画的 JavaScript 库
SVG 通常可以用作跨分辨率视频。这意味着在一块高分屏幕上不会降低图片的锐度。此外,你甚至可以让SVG动起来,通过使用一些javascript类库。下面,我们分享一些javascript类库,这些类库会帮助我们将SVG动画提高一个等级。 1\. Vivus --------- [Vivus](https://www.oschina.net/action/
Babel的使用
##### 本文参考文献([https://zhuanlan.zhihu.com/p/43249121](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fzhuanlan.zhihu.com%2Fp%2F43249121)) babel 到底做了什么?怎么做的? -------------
ES2020 中 Javascript 10 个你应该知道的新功能
好消息 - ES2020 新功能已经落地!这就意味着,现在对 ES2020 中 Javascript 的新增和改进要有一个完整的了解。让我们来看看都有哪些改变。 **1、BigInt** ------------ BigInt,Javascript 中最期待的新功能终于落地。它允许开发者在 JS 中使用更大的整数进行数据处理。 之前,Javas
JavaScript 性能优化技巧分享
JavaScript 作为当前最为常见的直译式脚本语言,已经广泛应用于 Web 应用开发中。为了提高Web应用的性能,从 JavaScript 的性能优化方向入手,会是一个很好的选择。 本文从加载、上下文、解析、编译、执行和捆绑等多个方面来讲解 JavaScript 的性能优化技巧,以便让更多的前端开发人员掌握这方面知识。 什么是高性能的 JavaScr
JavaScript 核心原理精讲【朋友圈已刷屏】
作为一名前端工程师,JavaScript 你一定每天都在用。但是,即便工作 5 年以上的前端也不一定用得非常熟,甚至很多前端对 JavaScript 的掌握程度仅仅停留在会用的层面。 而且 Vue/React 等框架的便利,更是让前端人无需苦学 JavaScript 原生,就可以快速构建一个网页。它解决了开发者短期的痛点,却为依赖框架开发的程序员埋下长期隐
JavaScript
### Javascript简介 web前端有三层: * HTML:从语义的角度,描述页面的结构 * CSS:从审美的角度,描述样式(美化页面) * Javascript:从交互的角度,描述行为(提升用户体验) ### JavaScript的组成 * ECMAScript5.0:定义了js的语法标准:包含变量、表达式、元素符、函数、i
JavaScript中8个常见的陷阱
**译者按:** 漫漫编程路,总有一些坑让你泪流满面。 原文: [Who said javascript was easy ?](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fhackernoon.com%2Fwho-said-javascript-easy-f4a1d5b399b8)
JavaScript基础入门05
\[toc\] JavaScript 基础入门05 ================= 严格模式 ---- 运行js代码的过程中,除了正常的代码运行模式以外,还存在`严格模式(strict mode)`。意义在于让代码采用更加严格的JavaScript语法。 > 需要注意的是,相同的代码,在不同的模式下可能会有不同的结果。很多时候在正常模式下能够运行
JavaScript学习总结(十七)——Javascript原型链的原理
一、JavaScript原型链 --------------- ECMAScript中描述了原型链的概念,并将原型链作为实现继承的主要方法。其基本思想是利用原型让一个引用类型继承另一个引用类型的属性和方法。在JavaScript中,用 `__proto__` 属性来表示一个对象的原型链。当查找一个对象的属性时,JavaScript 会**向上**遍历原型
JavaScript常见的10个错误
10 种最常见的 Javascript 错误 ---------------------- **以下是 JavaScript 错误 Top 10:** 为了便于阅读,我们将每个错误描述都缩短了。接下来,让我们深入到每一个错误,来确定什么会导致它,以及如何避免创建它。 **1\. Uncaught TypeError: Cannot read prope
Javascript开发人员偏爱Deno而不是Node的5大原因
![](https://oscimg.oschina.net/oscnet/2f078ca0f30b400261bf865253aa28f0a40.jpg) NodeJS的作者Ryan Dahl发布了一个新的运行时,旨在解决Node的许多缺点。你最初的反应可能是“哦,太棒了,另一个Javascript框架?正是我所需
Node.js
1.Node来历 --------     2009年,正是推出基于Javascript语言和V8引擎的开源Web服务项目,命名为Node.js,Node.js是第一次把Javascript带到后端开发。全很很多开发人员都熟悉Javascript,所以Node.js一下子就火了。     Javascript语言本身是完善的函数式语言,在前端开发时,开发