脚本宝典收集整理的这篇文章主要介绍了String.prototype.repeat在V8和Chakra中的实现,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
作者: @flowmemo
源地址: http://flowmemo.github.io/2016/03/25/str...
最近一个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.
当然这个程序没做充足的参数检查, 这个就不细说了. 我们分析一下它的效率:
如果要补n位, 字符串加法的执行次数是n次, 也就是O(n).
我们来看一下如何用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/codes...
// ES6, section 21.1.3.13
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);
// Early return to allow an arbitrarily-large repeat of the empty string.
if (s.length === 0) return "";
// The maximum string length is Stored in a smi, so a longer repeat
// must result in a range error.
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的二进制表示, 通过字符串的自加来减少字符串加法的次数. 这个算法和快速幂算法非常像. 详细的算法解释可以看这篇文章: http://www.2ality.com/2014/01/efficient-...
举例个例子, 如果count = 6 , 那个它的二进制表示就为1102 = 4*1 + 2*1 + 1*0. 也就是说对于长度为6的字符串s, 有
s.repeat(6) = s.repeat(4) + s.repeat(2)
注意到每次循环最多有两次字符串加法的操作, 而循环次数约等于LOGn, 所以按字符串加法的次数来记它的复杂度为O(logn)
Firefox的实现类似, 地址在这里https://dxr.mozilla.org/mozilla-central/... .
Chakra
好了, 我们来看看微软的Edge浏览器所使用的js引擎, Chakra对String.prototype.repeat的实现, 它是用的C++.
源码地址: https://github.com/Microsoft/ChakraCore/...
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] = ' ';
}
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 = ' ';
}
return JavascriptString::NewWithBuffer(buffer, finalBufferCount - 1, scriptContext);
}
看起来很长是吗? 不要被吓到了, 我们只关心核心算法, 其实就这一小段: