摘要：作者源地址最近一個(gè)事件搞得圈沸沸揚(yáng)揚(yáng)的我們暫且把這個(gè)事情放一邊來看看本身的實(shí)現(xiàn)的源碼如下這段程序的作用是給一個(gè)字符串或可以轉(zhuǎn)成的變量用字符在左邊補(bǔ)位將其補(bǔ)到長(zhǎng)度為當(dāng)然這個(gè)程序沒做充足的參數(shù)檢查這個(gè)就不細(xì)說了我們分析一下它的效率如果

作者: @flowmemo
源地址: http://flowmemo.github.io/2016/03/25/str...

最近一個(gè)left-pad事件搞得javascript圈沸沸揚(yáng)揚(yáng)的. 我們暫且把這個(gè)事情放一邊, 來看看left-pad本身的實(shí)現(xiàn).

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;
}

這段程序的作用是, 給一個(gè)字符串str(或可以轉(zhuǎn)成str的變量), 用字符ch在左邊補(bǔ)位, 將其補(bǔ)到長(zhǎng)度為len.
當(dāng)然這個(gè)程序沒做充足的參數(shù)檢查, 這個(gè)就不細(xì)說了. 我們分析一下它的效率:
如果要補(bǔ)n位, 字符串加法的執(zhí)行次數(shù)是n次, 也就是O(n).

我們來看一下如何用ES6的String.prototype.repeat來實(shí)現(xiàn)這個(gè)功能:
假定str是字符串, len是非負(fù)整數(shù), ch參數(shù)可選(如果有的話必須是長(zhǎng)度為1的字符串) 所以我更喜歡強(qiáng)類型語言.

function leftpadES6 (str, len, ch) {
  ch = ch||" "
  return ch.repeat(len - str.length) + str
}

當(dāng)然還沒完, 這么寫的效率怎么樣呢, 我們得看一下js引擎對(duì)String.prototype.repeat的實(shí)現(xiàn).

下面是Chrome/Chromuim的js引擎V8的實(shí)現(xiàn), 直接用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;
  }
}

忽略參數(shù)檢查, 我們來關(guān)注算法本身. 這個(gè)算法的核心是, 使用字符串重復(fù)次數(shù)count的二進(jìn)制表示, 通過字符串的自加來減少字符串加法的次數(shù). 這個(gè)算法和快速冪算法非常像. 詳細(xì)的算法解釋可以看這篇文章: http://www.2ality.com/2014/01/efficient-...

舉例個(gè)例子, 如果count = 6 , 那個(gè)它的二進(jìn)制表示就為110₂ = 4*1 + 2*1 + 1*0. 也就是說對(duì)于長(zhǎng)度為6的字符串s, 有
s.repeat(6) = s.repeat(4) + s.repeat(2)

注意到每次循環(huán)最多有兩次字符串加法的操作, 而循環(huán)次數(shù)約等于logn, 所以按字符串加法的次數(shù)來記它的復(fù)雜度為O(logn)

Firefox的實(shí)現(xiàn)類似, 地址在這里https://dxr.mozilla.org/mozilla-central/... .

好了, 我們來看看微軟的Edge瀏覽器所使用的js引擎, Chakra對(duì)String.prototype.repeat的實(shí)現(xiàn), 它是用的C++.
源碼地址: https://github.com/Microsoft/ChakraCore/...

Chakra中實(shí)現(xiàn)repeat分了兩個(gè)函數(shù), 一個(gè)是JavascriptString::EntryRepeat, 它的主要是做一些初始化工作, 參數(shù)檢查, 特殊情況的處理.核心算法是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] = "