这两天在看leftPad的源码，我觉得这代码写得真真是极好的，短短的几十行代码，我从中学到了不少好东西，所以迫不及待的想跟大家分享一下。leftPad一直被很多程序员不停的重构，不断的寻找提升性能的办法（这帮较真儿的程序员。。）。现在我们就直接看这段神秘的代码干了啥。
其实leftPad只是封装了一个这样的函数：
const leftPad = require('left-pad')
leftPad('foo', 5)
// => " foo"
leftPad('foobar', 6)
// => "foobar"
leftPad(1, 2, '0')
// => "01"
leftPad(17, 5, 0)
// => "00017"
好了看到这里你肯定想说：“擦，这么简单？这代码还需要解读？坑我了吧！”
不要着急，听我慢慢说。我们先来想一下，如果我们不看他的源码，我们自己会怎么实现这个函数呢？首先，我们会去获取需要填充在左侧的pad的length是多少，然后去循环，将规定的填充字符一个一个的填充在左侧。按照这个思路，我们实现的代码是这样的：
function leftPad(str, len, ch){
//将str转成string
str = str + '';
//获取左侧需要填充部分长度
len = len - str.length;
//如果len为负数则直接返回str
if(len <= 0) return str;
//如果我们没有给出ch参数，ch默认为一个空格
if(!ch && ch !== 0) ch = ' ';
//将ch转为字符串类型，因为有可能参数一个数值
ch = ch + '';
//开始循环len，将ch一个一个的添加到str的前面
while(len--){
str = ch + str;
}
return str;
}
因为要讨论这段代码的性能问题，所以不得不提一下，这里的循环时间复杂度是O(n)，一次简单的循环嘛。
好了，看到这里，都跟我们平时实现一个函数的思路是一样的。但是精彩的就在他的源码的实现思路。
首先，leftPad的作者并没有从一开始就循环添加pad。而是将len<10的部分缓存在了一个数组里边，这里考虑到用户在使用时取10以下的len比较多，当len小于10的时候，就直接从这个cache数组中取值，那时间复杂度这里就是O(1)。代码如下：
var cache = [
'',
' ',
' ',
' ',
' ',
' ',
' ',
' ',
' ',
' '
];
//函数中
function leftPad (str, len, ch) {
//......前面部分和一般实现思路一样
if (ch === ' ' && len < 10) return cache[len] + str;
}
那么大于10的呢？难道就开始原始的循环了么？没这么简单。想要提升性能，很容易想到的就是减少循环的次数，如果，我们不去改变len，那么，len的长度是多少，我们就得循环多少次，相应的ch就添加多少个pad。这里源码的实现思路是这样的，每次循环，len除以2，len变成了原来的一半，那么循环次数相应减少到原来的一半，那么ch相应应该增加到原来的两倍的长度ch=ch+ch，这样每次循环都将len减少到原来的一半。这样就将原本O(n)的复杂度减少到了O(log(n))。好了，直接看loop部分的代码：
while (true) {
if (len & 1) pad += ch;
len >>= 1;
if (len) ch += ch;
else break;
}
其实这里实现跟我说的是一样的，只是一般同学不怎么喜欢按位与和移位运算符这种操作。不管怎么说，直接去操作二进制数，都会比我们使用一般运算符号操作十进制性能快。这里是啥意思呢？if (len & 1)是用来判断是否是奇数，如果为奇数len & 1将返回1，如果是偶数则返回0。我们来验证一下是否如我所说。
假如现在的len=5，5转为二进制后是00000101，这个和00000001按位与。
再来个偶数，len=12，12转为二进制后为00001100，和1按位与后得0。
这里判断len如果是奇数，就先给pad一个ch的字符，为什么这里要判断len是否是奇数呢？我们先往下看，len >>= 1这又是什么意思，每次循环都向右移动一位，要知道这是用来做什么的，最简单的方法就是把移位后的得到的数字转为10进制看一下，以len=10为例
可以看出右移一位之后，其实就是相对原来的数除以了2。10向右移一位之后得到的是5。但是需要注意，与一般js里的/符号不同的是，移位的这个方法，会直接保留整数部分，截取掉小数部分。回过来看上一句，当len为奇数的时候，后面除以2就会把小数截取掉，所以先添加一个pad。len除以2之后，ch就要变成原来的两倍长度的字符串。直到len最后为0的时候跳出循环。最后返回pad+str。
完整的代码直接看这里：https://github.com/stevemao/left-pad/blob/master/index.js
最后来比较一下性能，下图比较了使用我最开始说得额原始方法，和使用es6的repeat，以及源码实现的性能比较：
可以看出Current，也就是源码实现的性能比前面两者的性能都要好。
网友评论