最近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; ch = ("" + 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函数。那么还有另外一个角度,从 机器的角度 ,在可读性允许的情况下,如何尽可能提高执行的效率。
我们回顾原作者的版本,它显然使用的是一个O(N)复杂度的算法来构造填补字符,那么这个过程有没有更高效率的方法呢?我们仔细想,构造填补字符的时候没必要一个字符一个字符添加呀,我们可以用倍增的办法来添加,因此,这个构造算法可以用O(logN)的复杂度来实现:
function leftpad(str, len, ch){ str = "" + str; if(!ch && ch !== 0) 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; }
然后我们回到前面说的用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; ch = ("" + 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; ch = ("" + 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 = " "; 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)