最近一个left-pad事件 搞得javascript圈沸沸扬扬的. 我们暂且把这个事情放一边, 来看看left-pad本身的实现.
left-pad 的源码如下:module .exports = leftpad;
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;
}
这段程序的作用是, 给一个字符串str(或可以转成str的变量), 用字符ch在左边补位, 将其补到长度为len.
我们来看一下如何用ES6的String.prototype.repeat来实现这个功能:str是字符串, len是非负整数, ch参数可选(如果有的话必须是长度为1的字符串) 所以我更喜欢强类型语言 .
function leftpadES6 (str, len, ch )
ch = ch||' '
return ch.repeat(len - str.length) + str
}
当然还没完, 这么写的效率怎么样呢, 我们得看一下js引擎对String.prototype.repeat的实现.
V8 下面是Chrome/Chromuim的js引擎V8的实现, 直接用js写的https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/js/string.js&l=672
function StringRepeat (count )
CHECK_OBJECT_COERCIBLE(this , "String.prototype.repeat" );
var s = TO_STRING(this );
var n = TO_INTEGER(count);
if (n < 0 || n === INFINITY) throw MakeRangeError(kInvalidCountValue);
if (s.length === 0 ) return "" ;
if (n > %_MaxSmi()) throw MakeRangeError(kInvalidCountValue);
var r = "" ;
while (true ) {
if (n & 1 ) r += s;
n >>= 1 ;
if (n === 0 ) return r;
s += s;
}
}
忽略参数检查, 我们来关注算法本身. 这个算法的核心是, 使用字符串重复次数count的二进制表示, 通过字符串的自加来减少concat的次数. 这个算法和快速幂算法非常像. 详细的算法解释可以看这篇文章: http://www.2ality.com/2014/01/efficient-string-repeat.html
举例个例子, 如果count = 6 , 那个它的二进制表示就为1102 = 4*1 + 2*1 + 1*0. 也就是说对于长度为6的字符串s, 有
注意到每次循环最多有两次concat的操作, 而循环次数约等于logn, 所以按concat的次数来记它的复杂度为O(logn)
Firefox的实现类似, 地址在这里https://dxr.mozilla.org/mozilla-central/source/js/src/builtin/String.js#159 .
Chakra 好了, 我们来看看微软的Edge浏览器所使用的js引擎, Chakra对String.prototype.repeat的实现, 它是用的C++.https://github.com/Microsoft/ChakraCore/blob/master/lib/Runtime/Library/JavascriptString.cpp#L2395
Chakra中实现repeat分了两个函数, 一个是JavascriptString::EntryRepeat, 它的主要是做一些初始化工作, 参数检查, 特殊情况的处理. 核心算法是JavascriptString::RepeatCore, 代码如下
JavascriptString* JavascriptString::RepeatCore(JavascriptString* currentString, charcount_t count, ScriptContext* scriptContext)
{
Assert(currentString != nullptr );
Assert(currentString->GetLength() > 0 );
Assert(count > 0 );
const char16* currentRawString = currentString->GetString();
int currentLength = currentString->GetLength();
charcount_t finalBufferCount = UInt32Math::Add(UInt32Math::Mul(count, currentLength), 1 );
char16* buffer = RecyclerNewArrayLeaf(scriptContext->GetRecycler(), char16, finalBufferCount);
if (currentLength == 1 )
{
wmemset(buffer, currentRawString[0 ], finalBufferCount - 1 );
buffer[finalBufferCount - 1 ] = '\0' ;
}
else
{
char16* bufferDst = buffer;
size_t bufferDstSize = finalBufferCount;
for (charcount_t i = 0 ; i < count; i += 1 )
{
js_wmemcpy_s(bufferDst, bufferDstSize, currentRawString, currentLength);
bufferDst += currentLength;
bufferDstSize -= currentLength;
}
Assert(bufferDstSize == 1 );
*bufferDst = '\0' ;
}
return JavascriptString::NewWithBuffer(buffer, finalBufferCount - 1 , scriptContext);
}
看起来很长是吗? 不要被吓到了, 我们只关心核心算法, 其实就这一小段:
if (currentLength == 1 )
{
wmemset(buffer, currentRawString[0 ], finalBufferCount - 1 );
buffer[finalBufferCount - 1 ] = '\0' ;
}
else
{
char16* bufferDst = buffer;
size_t bufferDstSize = finalBufferCount;
for (charcount_t i = 0 ; i < count; i += 1 )
{
js_wmemcpy_s(bufferDst, bufferDstSize, currentRawString, currentLength);
bufferDst += currentLength;
bufferDstSize -= currentLength;
}
Assert(bufferDstSize == 1 );
*bufferDst = '\0' ;
}
大意是如果字符串长度本身为1, 也就是一个字符, 那就直接用wmemset(类似于memset)将一块内存全用这个字符填充; 如果不为字符串长度不为1, 就一次连接一个字符串. 忽略js_wmemcpy_s
结语 我们现在来考虑一下, 为什么V8使用了优化过的算法, 而Chakra使用了朴素/naive/trival的算法.
我们之前说了, V8实现的字符串加法的操作次数是O(logn)的, 但是, 我们要把一个字符串重复n次, 一定要得在要对O(n)的内存进行写操作 .update1: 经过@哦胖茶 巨巨的提醒(http://weibo.com/2451315930/DowQCo6wN ), V8、ChakraCore 和 Rhino 底层实现字符串拼接用的都是rope(tree) . 对于rope来说字符串连接不需要为新字符串开辟被内存并把内容写进去, 而是合并两个二叉树, 详见这里: https://en.wikipedia.org/wiki/Rope_%28data_structure%29#Concat .
这么看的话, 在不考虑rope摊平的情况下, 仅从算法复杂度的角度来看V8的rope连接和快速幂实现是比Chakra的要好. Chakra里字符串也用了rope, 但是对repeat的实现没有用rope, 直接就是复制内存. 字符串在内存是就是以连续内存的形式存储的话, 把一个字符串重复n次, 一定要得在要对O(n)的内存进行写操作, 所以快速幂优化意义不大.
至于V8的这种字符串加法用rope、js实现用快速幂的方法好, 还是Chakra这种直接复制内存的方法好, 我没有跑benchmark, 就不下结论了.
最后想说的是, 虽然这篇文章关注的是实现算法, 但是参数检查、边界条件的处理, 也非常的重要, 千万不能觉得无所谓. 可以说工具函数中edge case的处理经常比算法更为头疼…
P.S.1 我在知道V8, Chakra的字符串实现用了rope后对本文进行过修改https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/js/string.js&l=84