由NPM引发的关于left-pad的那些事儿

xman

最近NPM社区出了一件大事，一个开发者对NPM公司不满，unpublish了自己的所有模块。其中包括被广泛使用的left-pad，导致Babel、ReactNative、Ember等大量工具构建失败。


　　这件事件本身不是我们这篇文章要讨论的主要内容，关注事件的同学可以移步知乎参与相关讨论。


　　本文讨论的内容是关于 left-pad 这个函数的实现。


　　原作者的实现代码是这样的：


　　
function leftpad (str, len, ch) {

　　str = String(str);

　　var i = -1;

　　if (!ch && ch !== 0) ch = " ";

　　len = len - str.length;

　　while (++i < len) {

　　str = ch + str;

　　}

　　return str;

　　}



　　这个实现在微博上引起了广泛讨论并被吐槽。在这里我主要想讨论这段代码被吐槽的原因。


　　作为专业的程序员(码农)，我们应该知道代码主要是给人阅读的，只是偶尔让计算机执行一下，那么我们关注代码的两个方面：


　　代码风格


　　执行效率


　　前者是给人阅读，后者是执行效率。


　　可读性：


　　由于这段代码本身逻辑并不复杂，作者这个实现也是中规中矩的，因此说有什么大毛病，其实也还没有。吹毛求疵一点，那也不过是这段代码不符合JavaScript(或者说JS程序员)的风格。


　　这段代码，如果让月影按JS风格来写，可能会是这样的：


　　
function leftpad(str, len, ch){

　　str = "" + str;

　　var padlen = len - str.length;

　　if(padlen <= 0){

　　return str;

　　}else{

　　return (new Array(padlen + 1)).join((""+ch) || " ") + str;

　　}

　　}



　　在这里，我们利用Array的join方法来完成重复字符串的拼接，这是使用了JS语言本身的特性，消除了循环，让代码更简单(在JS程序员眼里更简单)，有点意思。


　　有同学可能会提出来，那么我们可以更简单，利用更多的JS特性完成这个工作：


　
　function leftpad(str,len,ch) {

　　return ((new Array(len)).join((ch+"")||" ") + str)

　　.slice(-Math.max(len, (""+str).length));

　　}



　　的确如此。如果考虑到ES6新的API，我们可以有更加“语义化”的写法(也更高效，后面会提到)：


　　
function leftpad(str, len, ch){

　　str = "" + str;

　　if (!ch && ch !== 0) ch = " ";

　　var padlen = len - str.length;

　　if(padlen <= 0){

　　return str;

　　}else{

　　return ch.repeat(padlen) + str;

　　}

　　}

　　或者

　　function leftpad(str,len,ch) {

　　return (((ch+"")||" ").repeat(len) + str)

　　.slice(-Math.max(len, (""+str).length));

　　}



　　但是，我们需要对不支持repeat的浏览器做降级处理，降级处理的实现在后面讨论。


　　以上是从代码风格，或者说从人书写和阅读的方便程度上去考虑如何写一个JS函数。那么还有另外一个角度，从机器的角度，在可读性允许的情况下，如何尽可能提高执行的效率。


　　我们回顾原作者的版本，如果要补n位字符, 字符串加法，也就是String.prototype.concat的执行次数是n次, 也就是O(n)，那么这个过程有没有更高效率的方法呢?我们仔细想，构造填补字符的时候没必要一个字符一个字符添加呀，我们可以用倍增的办法来添加，因此，这个构造算法可以用concat次数大约是O(logN)的复杂度来实现：


　　
function leftpad(str, len, ch){

　　str = "" + str;

　　if(!ch && ch !== 0) ch = " ";

　　ch = "" + ch;

　　var padlen = len - str.length;

　　if(padlen <= 0) return str;

　　var padch = padlen & 1 ? ch : "";

　　while(padlen >>= 1){

　　ch += ch;

　　if(padlen & 1){

　　padch += ch;

　　}

　　}

　　return padch + str;

　　}



　　注意到上面的代码每次循环最多有两次concat的操作, 而循环次数约等于logn, 所以按concat的次数来记它的复杂度为O(logn)。然后我们回到前面说的用repeat实现，为什么我说它性能更好?我们可以看一下repeat的实现：


　　
if (!String.prototype.repeat) {

　　String.prototype.repeat = function(count) {

　　"use strict";

　　if (this == null) {

　　throw new TypeError("can\"t convert " + this + " to object");

　　}

　　var str = "" + this;

　　count = +count;

　　if (count != count) {

　　count = 0;

　　}

　　if (count < 0) {

　　throw new RangeError("repeat count must be non-negative");

　　}

　　if (count == Infinity) {

　　throw new RangeError("repeat count must be less than infinity");

　　}

　　count = Math.floor(count);

　　if (str.length == 0 || count == 0) {

　　return "";

　　}

　　// Ensuring count is a 31-bit integer allows us to heavily optimize the

　　// main part. But anyway, most current (August 2014) browsers can"t handle

　　// strings 1 << 28 chars or longer, so:

　　if (str.length * count >= 1 << 28) {

　　throw new RangeError("repeat count must not overflow maximum string size");

　　}

　　var rpt = "";

　　for (;;) {

　　if ((count & 1) == 1) {

　　rpt += str;

　　}

　　count >>>= 1;

　　if (count == 0) {

　　break;

　　}

　　str += str;

　　}

　　// Could we try:

　　// return Array(count + 1).join(this);

　　return rpt;

　　}

　　}



　　从官方推荐的polyfill实现来看，它使用的就是O(logN)的算法。


　　所以，如果结合代码风格和执行效率，我们可以得到一个比较好的版本——


　　
if (!String.prototype.repeat) {

　　String.prototype.repeat = function(count) {

　　"use strict";

　　if (this == null) {

　　throw new TypeError("can\"t convert " + this + " to object");

　　}

　　var str = "" + this;

　　count = +count;

　　if (count != count) {

　　count = 0;

　　}

　　if (count < 0) {

　　throw new RangeError("repeat count must be non-negative");

　　}

　　if (count == Infinity) {

　　throw new RangeError("repeat count must be less than infinity");

　　}

　　count = Math.floor(count);

　　if (str.length == 0 || count == 0) {

　　return "";

　　}

　　// Ensuring count is a 31-bit integer allows us to heavily optimize the

　　// main part. But anyway, most current (August 2014) browsers can"t handle

　　// strings 1 << 28 chars or longer, so:

　　if (str.length * count >= 1 << 28) {

　　throw new RangeError("repeat count must not overflow maximum string size");

　　}

　　var rpt = "";

　　for (;;) {

　　if ((count & 1) == 1) {

　　rpt += str;

　　}

　　count >>>= 1;

　　if (count == 0) {

　　break;

　　}

　　str += str;

　　}

　　// Could we try:

　　// return Array(count + 1).join(this);

　　return rpt;

　　}

　　}

　　function leftpad(str, len, ch){

　　str = "" + str;

　　if (!ch && ch !== 0) ch = " ";

　　var padlen = len - str.length;

　　if(padlen <= 0){

　　return str;

　　}else{

　　return ch.repeat(padlen) + str;

　　}

　　}



　　最后，我们跑一下Benchmark


　　
var Benchmark = require("benchmark");

　　var suite = new Benchmark.Suite;

　　function leftpad_azer (str, len, ch) {

　　str = String(str);

　　var i = -1;

　　if (!ch && ch !== 0) ch = " ";

　　len = len - str.length;

　　while (++i < len) {

　　str = ch + str;

　　}

　　return str;

　　}

　　function leftpad_array1 (str, len, ch){

　　str = "" + str;

　　var padlen = len - str.length;

　　if(padlen <= 0){

　　return str;

　　}else{

　　return (new Array(padlen + 1)).join((""+ch) || " ") + str;

　　}

　　}

　　function leftpad_array2 (str,len,ch) {

　　return ((new Array(len)).join((ch+"")||" ") + str)

　　.slice(-Math.max(len, (""+str).length));

　　}

　　function leftpad_repeat(str, len, ch){

　　str = "" + str;

　　if (!ch && ch !== 0) ch = " ";

　　var padlen = len - str.length;

　　if(padlen <= 0){

　　return str;

　　}else{

　　return ch.repeat(padlen) + str;

　　}

　　}

　　function leftpad_binary(str, len, ch){

　　str = "" + str;

　　if(!ch && ch !== 0) ch = " ";

　　ch = "" + ch;

　　var padlen = len - str.length;

　　if(padlen <= 0) return str;

　　var padch = padlen & 1 ? ch : "";

　　while(padlen >>= 1){

　　ch += ch;

　　if(padlen & 1){

　　padch += ch;

　　}

　　}

　　return padch + str;

　　}

　　// add tests

　　suite.add("leftpad#azer", function() {

　　leftpad_azer("10",1000,"0")

　　})

　　.add("leftpad#array1", function() {

　　leftpad_array1("10",1000,"0")

　　})

　　.add("leftpad#array2", function() {

　　leftpad_array2("10",1000,"0")

　　})

　　.add("leftpad#repeat", function() {

　　leftpad_repeat("10",1000,"0")

　　})

　　.add("leftpad#binary", function() {

　　leftpad_binary("10",1000,"0")

　　})

　　// add listeners

　　.on("cycle", function(event) {

　　console.log(String(event.target));

　　})

　　.on("complete", function() {

　　console.log("Fastest is " + this.filter("fastest").map("name"));

　　})

　　// run async

　　.run({ "async": true });



　　可以看到 Node.js 下性能最高的版本是我们自己实现的O(logN)版


　　
leftpad#azer x 82,459 ops/sec ±3.11% (74 runs sampled)

　　leftpad#array1 x 24,252 ops/sec ±2.17% (72 runs sampled)

　　leftpad#array2 x 60,480 ops/sec ±3.56% (74 runs sampled)

　　leftpad#repeat x 5,668,275 ops/sec ±4.67% (77 runs sampled)

　　leftpad#binary x 6,488,969 ops/sec ±1.14% (89 runs sampled)