前端与算法 - Githubissues

yesvods commented 8 years ago

前言

最近举行了一场盛大的前端算法大比拼，题目从真实业务场景中抽取出来，童鞋们纷纷摩拳擦掌展示自己算法基本功。题目如下：

真实场景里面，有7M左右的JSON数据需要统一更新费率，据说一开始处理这堆数据一次就得耗费20+秒。在浏览器场景下，这意味着这段时间UI渲染被阻塞，用户交互完全无响应。最后经过调整的算法，也需要1秒左右的执行时间，非常影响用户体验。

略懂浏览器动画的童鞋都知道，在浏览器一帧里面layout、合成、渲染占据了不少CPU时间，真实交给js进行运行的时间只有不到10ms。在如此大数据量处理的场景下要保持丝般顺滑的用户体验，算法必不可少，可见算法对于前端依旧非常重要。

鄙人也参加了大比拼，分享一下自己的小小心得，总结一下如何将7M数据处理从1000ms降到10ms以下。

基本思路

从题目的数据结构可以看到，这是一个多叉树，第一时间联想到的是树的遍历。借鉴函数式编程思想，树的处理只需要三个步骤：

函数递归遍历
使用processor处理每一个树节点
葛优躺...

Talk is cheap, show me the code.

树的遍历：

function trav(tree, processor){
  if(!tree.children) return;
  for(var i in tree.children){
    let node = tree.children[i];
    processor(node);
    if(item.children){
      trav(item, process)
    }
  }
}

处理器：

function processor(node){
    //...预处理
    let values = node.rate.split('_');
    values[0] = '3';
    values[1] = '5';
    node.rate = values.join('_');
}

好，大功告成，跑一下。。。43ms??!

不科学！这在浏览器特喵的已经卡了一会了。

优化思路

肯定哪里有问题，先看一下树遍历。

result: 3ms

唔..只用了3ms，对于大量数据遍历这个时间也说得过去，不是性能瓶颈。

那就只有处理器出问题了，细看一下：

// node.rate.split('_')
result 10ms+

// values[0] = '3';
// values[1] = '5';
result 10ms+

// values.join('_');
result 10ms+

出乎意料，在大量重复调用情况下，就算是一个普通的方法也会产生大量性能损耗。大家应该也听说过字符串处理是特别费性能的，处理不当就会产生不少问题。

从上面的运行可以看出，无论是字符串的分离或者合并，还是数组的赋值都会导致性能损耗。平时这么说早被人打死了，什么性能损耗，能跑就行。在真正性能瓶颈上，这些细节尤为关键。

字符串处理

实际上，我们只是需要根据现有费率+要修改费率组成出一个新费率。我们可以把这些操作做成

对原字符串的读取
对修改费率的读取
字符串合并

把多次写、赋值操作，改成一次低性能损耗的字符串合并。

好好好，你们要的code

//读取
function getValue(pos, raw, position, resMap){
  if(position.indexOf(pos) === -1) return raw.charAt(pos * 2);
  return resMap[pos];
}
//合并
function concat(raw, position, resMap){
  let str = '';
  str = str+getValue(0, raw, position, resMap)+'-'+getValue(1, raw, position, resMap)+'-'+getValue(2, raw, position, resMap);
  return str;
}

于是..最终的处理器代码应该是酱紫的：

trav(this.data, item => {
    if(!item.rate) item.rate = '0_0_0';
    item.rate = concat(item.rate, position, resMap);
});

最终的最佳跑分结果是：

result: 6.666..ms

题内话

在处理字符串合并时候依然需要注意的是，不同的合并方式，系统调度是不一样的。

//产生3次变量调度, tmpVal = 'hehe', tmpVal2 = val1 + 'hehe', tmpVal3 = tmpVal2 + val2;
let str = val1 + ' hehe ' + val2 ;

//产生1次变量调度, tmpVal = 'hehe', tmpVal +=val1, tmpVal +=val2
let str = ' hehe ' + val1 + val2

yantze commented 7 years ago

简练，好方法

关于测时间的方法应该用的是：

console.time('uniqueNums');
uniqueNums(31);
console.timeEnd('uniqueNums');

下面的方法更加准确一些

var t0 = performance.now();
uniqueNums(30);
var t1 = performance.now();
console.log("Call to doSomething took " + (t1 - t0) + " milliseconds.")

https://stackoverflow.com/questions/313893/how-to-measure-time-taken-by-a-function-to-execute

zzhenxiang commented 5 years ago

参数可以说一下吗

yesvods / Blog

前端与算法 #8

前言

基本思路

优化思路

字符串处理

题内话