今天的问题从排序算法入手,来讲解如何根据业务需求,结合金典的算法,来实现js高性能开发。
老板让小明给公司的20000+条数据排个序,但是由于排序的操作会频繁发生,如果操作执行的时间很慢,则会严重降低用户体验,听到这条噩耗后小明开始了代码。
小明根据需求,思考了一会,写下了如下算法:
/**
* 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,小明觉得还不错,放到项目中后,第一次操作还好,连续操作了几次后,页面明显卡顿。。。(求此时小明心里的阴影面积)。
小明不甘心,在网上查找相关资料后,写下了如下冒泡排序代码:
/**
* 置换函数
* @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,不错~
再次推荐大家有事多上上维基百科,总有一款适合你。####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,小明留下了没技术的泪水。
最后小明拿出了这个看家本领,查到了二分搜索,最后改造后代码入下:
/**
* 改造二分查找,查找小于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!小明激动的站了起来,还拍了下桌子,全然无视观众的眼光。
小明已经满足的不要不要的了,对86ms相当满意,老板也对他刮目想看。
难道就没有提升的余地了么?进过调查研究表明,是有更优的方案的:
/**
* 希尔排序
* 核心:通过动态定义的 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对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。
程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法
使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。
给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。
racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。
JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题
这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。
PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。
什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a
将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!