建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
如何讓前端代碼速度提高60倍
情景
老板讓小明給公司的20000+條數(shù)據(jù)排個序，但是由于排序的操作會頻繁發(fā)生，如果操作執(zhí)行的時間很慢，則會嚴(yán)重降低用戶體驗(yàn)，聽到這條噩耗后小明開始了代碼。
1.毫無違和感的排序算法
小明根據(jù)需求，思考了一會，寫下了如下算法：
/**
* 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()
}
自信的小明陶醉在自己的算法中，準(zhǔn)備測試一下性能。
/*
* @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 測試函數(shù)執(zhí)行的時間
*/
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
);
}
運(yùn)行該測試函數(shù)后，耗時760ms，小明覺得還不錯，放到項(xiàng)目中后，第一次操作還好，連續(xù)操作了幾次后，頁面明顯卡頓。。。(求此時小明心里的陰影面積)。
2.冒泡排序
小明不甘心，在網(wǎng)上查找相關(guān)資料后，寫下了如下冒泡排序代碼：
/**
* 置換函數(shù)
* @param {源數(shù)組} arr
* @param {原數(shù)組的A項(xiàng)} indexA
* @param {原數(shù)組的B項(xiàng)} indexB
*/
function swap(arr, indexA, indexB) {
[arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]];
}
/**
* 原始冒泡排序
* @param {數(shù)組} 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，完美，小明放到項(xiàng)目中測試，頻繁排序還是會有點(diǎn)卡頓，能不能再優(yōu)化一下呢?思考許久之后，小明完善了冒泡排序：
/**
* 利用索引優(yōu)化后的冒泡排序
* @param {數(shù)組} 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;
}
根據(jù)緩存索引位置來提高排序性能，時間節(jié)約了20ms，但收益很小。小明開始和自己過不去了，在維基百科上繼續(xù)查找，最后發(fā)現(xiàn)了一個方法：
/**
* 在每趟排序中進(jìn)行正向和反向兩遍冒泡 ,
* 一次可以得到兩個最終值（最大和最小）,
* 從而使外排序趟數(shù)大概減少了一半
* @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;
}
通過在每趟排序中進(jìn)行正向和反向兩遍冒泡，小明把時間又降低了38ms，不錯～
再次推薦大家有事多上上維基百科，總有一款適合你。
3.插入排序
在收入小規(guī)模勝利后，小明膨脹了，狂言要把排序時間降低到100ms一下，于是后又安利了如下算法：
/**
* 插入排序 -- 基礎(chǔ)版
* @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,小明留下了沒技術(shù)的淚水。
最后小明拿出了這個看家本領(lǐng)，查到了二分搜索，最后改造后代碼入下：
/**
* 改造二分查找,查找小于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;
}
/**
* 使用二分法來優(yōu)化插入排序
* @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!小明激動的站了起來，還拍了下桌子，全然無視觀眾的眼光。
小明已經(jīng)滿足的不要不要的了，對86ms相當(dāng)滿意，老板也對他刮目想看。
4.希爾排序
難道就沒有提升的余地了么?進(jìn)過調(diào)查研究表明，是有更優(yōu)的方案的：
/**
* 希爾排序
* 核心：通過動態(tài)定義的 gap 來排序，先排序距離較遠(yuǎn)的元素，再逐漸遞進(jìn)
* @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，也想當(dāng)優(yōu)秀。還有沒有更快的方法呢?答案是有的，但是會涉及到比較高僧的數(shù)學(xué)知識，放棄吧，孩子......
標(biāo)題名稱：如何讓前端代碼速度提高60倍
網(wǎng)頁路徑：http://fisionsoft.com.cn/article/dpodghi.html
