前段时间,left-pad 事件在前端圈火了一把,大致就是其作者不满 npm 公司的行为,怒删其 npm 上发布的一个 left-pad 包,结果不删不要紧,一删这个包,许多 npm 上重量级的包都不能用了,包括 Babel、ReactNative、Ember 等大量工具。一下子这件事情就被顶到了风口浪尖。

那么,问题来了!这个 left-pad 包是何方神圣,居然这么多明星级工具都去引用它。

其实,left-pad 包做的事情很简单,以至于它的代码只有十来行。说白了,就像这个包名所表达的:给定输入字符串和长度,如果字符串长度不足给定长度,就以固定字符左填充。

是不是觉得这个包做的事情太 naive 了?我们可能两分钟就能撸一个了!

1
2
3
4
5
6
7
8
9
10
11
function leftpad (str, len, ch) {
var i = -1;
len = len - str.length;
ch = ch || '';
while (++i < len) {
str = ch + str;
}
return str;
}

有效代码才不足十行,被这么多包引用?也太不值了吧!瞬间我们觉得自信心大增了,毕竟这代码,是个程序员都能写出来啊!不过,这个包最原始的代码就是类似这么来做的,没啥特别牛逼的地方。

BUT,我们能否对它进行优化?比如,现在的时间复杂度是 O(n),能否再进行性能的提升?

说实话,一开始思考这个问题的时候,我确实有点懵逼,毕竟这代码太简单了,感觉也没啥特别的地方,除了字符串的拼接可能可以优化一下,但这还是免不了 O(n) 的一个复杂度。

考虑到我们要填充的字符个数其实等于 len - str.length,我们可以不在循环中每次都加一个字符,而是将待填充数字转为二进制编码,如待填充 10 个字符,即 1010,于是我们可以通过从 1 个字符开始,每次翻倍字符数,将最终填充的字符数变为 10 个。

比如说,要填充 10 个字符 ch:

第一位为 0,所以实际不填充,但 ch 变为 ch + ch,即 2 个 ch;
第二位为 1,填充 2 个 ch 字符,ch 再次翻倍扩充,即为 4 个 ch;
第三位为 0,实际不填充,但 ch 翻倍扩充,变为 8 个 ch;
第四位为 1,再填充 8 个 ch 字符,由于这是最高位,所以算法结束,总体填充了 10 个字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function leftpad (str, len, ch) {
str = str +'';
len = len - str.length;
if (len <= 0) return str;
ch = ch || ' ';
var pad = '';
while (true) {
if (len & 1) pad += ch;
len >>= 1;
if (len) ch += ch;
else break;
}
return pad + str;
}

那么,性能提升有多少呢?可以看出,算法由于变成了对数复杂度,所以 n 越大,提升是越明显的,具体的性能对比,可以参考 https://github.com/stevemao/left-pad/pull/11

注:String.repeat 的实现就是这么做的,可以参考 https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/repeat

参考