这两天在看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,也就是源码实现的性能比前面两者的性能都要好。