03月24, 2016

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

说明:之前关于算法复杂度的描述部分不严谨,引起某些同学的疑义,在这里特别声明了算法仅考虑循环次数,并不包括String的concat操作,由于v8引擎对字符串concat的时间复杂度接近于常量(测试代码),因此循环次数对算法效率的影响比较大,后面的benchmark测试也可以说明问题。最后,算法时间复杂度减小,并不一定快,不一样的指令耗费的时间不一样,所以实际工程中还需要以实际测试为准。特别感谢:@flowmemoString.prototype.repeat在V8和Chakra中的实现 —— 月影 2016-03-29

最近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 + 1)).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 + 1)).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)

本文链接:https://www.h5jun.com/post/left-pad.html

-- EOF --

Comments