function repeat(s, n) { var r=""; for (var a=0;a<n;a++) r+=s; return r;}

简单的递归连接

我只是想试一试，然后做了这个:

function ditto( s, r, c ) {
    return c-- ? ditto( s, r += s, c ) : r;
}

ditto( "foo", "", 128 );

我不能说我想得太多，它可能表明:-)

可以说这样更好

String.prototype.ditto = function( c ) {
    return --c ? this + this.ditto( c ) : this;
};

"foo".ditto( 128 );

这很像已经发布的答案-我知道。

但为什么要递归呢?

还有一点默认行为呢?

String.prototype.ditto = function() {
    var c = Number( arguments[ 0 ] ) || 2,
        r = this.valueOf();
    while ( --c ) {
        r += this;
    }
    return r;
}

"foo".ditto();

因为，尽管非递归方法将处理任意大的重复而不达到调用堆栈限制，但它要慢得多。

为什么我要费心添加更多的方法，而这些方法还不及已经发布的那些方法的一半聪明呢?

一部分是为了自娱自乐，一部分是为了用最简单的方式指出，我知道剥猫皮的方法有很多种，根据具体情况，显然最好的方法很可能并不理想。

一个相对快速和复杂的方法可能会在某些情况下有效地崩溃和烧毁，而一个更慢，更简单的方法可能最终会完成工作。

有些方法可能只是利用漏洞，因此很容易被修复而不复存在，而其他方法可能在所有条件下都工作得很好，但构造得太复杂，以至于人们根本不知道它是如何工作的。

“就算我不知道它是怎么工作的又怎样?!”

严重吗?

JavaScript有一个最大的优势;它对不良行为具有高度的容忍度，而且非常灵活，它会竭尽全力地返回结果，而如果它崩溃了，可能对每个人都更好!

“能力越大，责任越大”;-)

但更严肃和重要的是，尽管像这样的一般问题确实会以聪明的答案形式带来令人生畏的东西，如果没有其他的话，扩展了一个人的知识和视野，最终，手头的任务-使用结果方法的实际脚本-可能需要比建议的更少或更聪明一点。

这些“完美”的算法很有趣，但“一刀切”很少会比量身定制更好。

这篇布道是由于你睡眠不足和一时兴趣所致。 开始编码吧!

这个很有效

String.prototype.repeat = function(times){
    var result="";
    var pattern=this;
    while (times > 0) {
        if (times&1)
            result+=pattern;
        times>>=1;
        pattern+=pattern;
    }
    return result;
};

只是另一个重复函数:

function repeat(s, n) {
  var str = '';
  for (var i = 0; i < n; i++) {
    str += s;
  }
  return str;
}

这个问题是JavaScript的一个众所周知的/“经典”优化问题，原因是JavaScript字符串是“不可变的”，即使是将单个字符连接到字符串也需要创建一个完整的新字符串，包括内存分配和复制。

Unfortunately, the accepted answer on this page is wrong, where "wrong" means by a performance factor of 3x for simple one-character strings, and 8x-97x for short strings repeated more times, to 300x for repeating sentences, and infinitely wrong when taking the limit of the ratios of complexity of the algorithms as n goes to infinity. Also, there is another answer on this page which is almost right (based on one of the many generations and variations of the correct solution circulating throughout the Internet in the past 13 years). However, this "almost right" solution misses a key point of the correct algorithm causing a 50% performance degradation.

JS的性能结果为被接受的答案，表现最好的其他答案(基于这个答案中原始算法的降级版本)，以及这个答案使用了我13年前创建的算法

~ October 2000 I published an algorithm for this exact problem which was widely adapted, modified, then eventually poorly understood and forgotten. To remedy this issue, in August, 2008 I published an article http://www.webreference.com/programming/javascript/jkm3/3.html explaining the algorithm and using it as an example of simple of general-purpose JavaScript optimizations. By now, Web Reference has scrubbed my contact information and even my name from this article. And once again, the algorithm has been widely adapted, modified, then poorly understood and largely forgotten.

原始字符串重复/乘法JavaScript算法由 Joseph Myers，大约Y2K作为text .js中的文本相乘函数; 2008年8月由Web Reference发布: http://www.webreference.com/programming/javascript/jkm3/3.html ( 文章用这个函数作为JavaScript优化的例子， 这是唯一的奇怪的名字“stringFill3。”)

/*
 * Usage: stringFill3("abc", 2) == "abcabc"
 */

function stringFill3(x, n) {
    var s = '';
    for (;;) {
        if (n & 1) s += x;
        n >>= 1;
        if (n) x += x;
        else break;
    }
    return s;
}

Within two months after publication of that article, this same question was posted to Stack Overflow and flew under my radar until now, when apparently the original algorithm for this problem has once again been forgotten. The best solution available on this Stack Overflow page is a modified version of my solution, possibly separated by several generations. Unfortunately, the modifications ruined the solution's optimality. In fact, by changing the structure of the loop from my original, the modified solution performs a completely unneeded extra step of exponential duplicating (thus joining the largest string used in the proper answer with itself an extra time and then discarding it).

下面将讨论与此问题的所有答案相关的一些JavaScript优化，并使大家受益。

技巧:避免引用对象或对象属性

为了说明这种技术是如何工作的，我们使用一个实际的JavaScript函数来创建所需长度的字符串。正如我们将看到的，可以添加更多优化!

类似于这里使用的函数是创建填充来对齐文本列、格式化货币或填充块数据直到边界。文本生成函数还允许可变长度的输入，以测试对文本进行操作的任何其他函数。这个函数是JavaScript文本处理模块的重要组件之一。

接下来，我们将介绍另外两种最重要的优化技术，同时将原始代码开发为用于创建字符串的优化算法。最终的结果是一个工业强度、高性能的函数，我在任何地方都使用它——在JavaScript订单表单中对齐商品价格和总额、数据格式化和电子邮件/文本消息格式化以及许多其他用途。

创建字符串的原始代码stringFill1()

function stringFill1(x, n) { 
    var s = ''; 
    while (s.length < n) s += x; 
    return s; 
} 
/* Example of output: stringFill1('x', 3) == 'xxx' */ 

这里的语法很清楚。正如您所看到的，在进行更多优化之前，我们已经使用了局部函数变量。

请注意，代码中有一个对对象属性s.length的无辜引用会损害它的性能。更糟糕的是，这个object属性的使用假设读者知道JavaScript字符串对象的属性，从而降低了程序的简单性。

使用这个object属性破坏了计算机程序的通用性。程序假设x必须是一个长度为1的字符串。这限制了stringFill1()函数的应用，只能重复单个字符。即使单个字符也不能使用，如果它们包含多个字节，如HTML实体 

这种不必要的使用object属性所导致的最糟糕的问题是，如果在空输入字符串x上测试，该函数会创建一个无限循环。为了检查通用性，请将程序应用于尽可能少的输入。当程序被要求超过可用内存量时崩溃是有理由的。像这样的程序在被要求不生成任何东西时崩溃是不可接受的。有时候漂亮的代码是有毒的代码。

简单性可能是计算机编程的一个模糊目标，但通常不是。当一个程序缺乏任何合理程度的通用性时，说“这个程序就目前而言已经足够好了”是不成立的。如你所见，使用字符串。长度属性会阻止此程序在常规设置下工作，事实上，不正确的程序会导致浏览器或系统崩溃。

有没有办法在解决这两个严重问题的同时提高JavaScript的性能呢?

当然可以。只使用整数。

创建字符串的优化代码

function stringFill2(x, n) { 
    var s = ''; 
    while (n-- > 0) s += x; 
    return s; 
} 

比较stringFill1()和stringFill2()的计时代码

function testFill(functionToBeTested, outputSize) { 
    var i = 0, t0 = new Date(); 
    do { 
        functionToBeTested('x', outputSize); 
        t = new Date() - t0; 
        i++; 
    } while (t < 2000); 
    return t/i/1000; 
} 
seconds1 = testFill(stringFill1, 100); 
seconds2 = testFill(stringFill2, 100); 

到目前为止stringFill2()的成功

stringFill1()需要47.297微秒(百万分之一秒)来填充一个100字节的字符串，stringFill2()需要27.68微秒来完成同样的事情。通过避免对对象属性的引用，性能几乎提高了一倍。

技巧:避免在长字符串中添加短字符串

我们之前的结果看起来不错——实际上非常不错。由于使用了前两个优化，改进后的函数stringFill2()要快得多。如果我告诉你它可以比现在快很多倍，你会相信吗?

是的，我们可以实现这个目标。现在我们需要解释如何避免将短字符串附加到长字符串中。

与我们原来的函数相比，短期行为看起来很好。计算机科学家喜欢分析一个函数或计算机程序算法的“渐近行为”，这意味着通过用更大的输入测试它来研究它的长期行为。有时不做进一步的测试，人们永远不会意识到计算机程序可以改进的方法。为了看看会发生什么，我们将创建一个200字节的字符串。

stringFill2()出现的问题

Using our timing function, we find that the time increases to 62.54 microseconds for a 200-byte string, compared to 27.68 for a 100-byte string. It seems like the time should be doubled for doing twice as much work, but instead it's tripled or quadrupled. From programming experience, this result seems strange, because if anything, the function should be slightly faster since work is being done more efficiently (200 bytes per function call rather than 100 bytes per function call). This issue has to do with an insidious property of JavaScript strings: JavaScript strings are "immutable."

不可变意味着一旦创建了字符串就不能更改。通过一次增加一个字节，我们不会多消耗一个字节的精力。我们实际上是在重新创建整个字符串，再加上一个字节。

实际上，要向100字节的字符串中再添加一个字节，就需要101个字节的工作。让我们简单分析一下创建一个N字节的字符串的计算成本。添加第一个字节的代价是1单位的计算工作量。添加第二个字节的代价不是一个单位，而是两个单位(将第一个字节复制到新的字符串对象以及添加第二个字节)。第三个字节需要3个单位的成本，等等。

C(n) = 1 + 2 + 3 +…+ n = n (n +1)/2 = o (n²)符号O(N²)发音为大O(N²)，这意味着长期运行的计算成本与字符串长度的平方成正比。创造100个字符需要1万个单位的工作，创造200个字符需要4万个单位的工作。

这就是为什么创建200个字符所花费的时间是创建100个字符的两倍多。事实上，它应该花四倍的时间。我们的编程经验是正确的，因为对于更长的字符串，工作完成得稍微更有效率，因此只需要大约三倍的时间。一旦函数调用的开销对于我们所创建的字符串的长度变得可以忽略不计，那么创建一个两倍长的字符串实际上需要四倍的时间。

(Historical note: This analysis doesn't necessarily apply to strings in source code, such as html = 'abcd\n' + 'efgh\n' + ... + 'xyz.\n', since the JavaScript source code compiler can join the strings together before making them into a JavaScript string object. Just a few years ago, the KJS implementation of JavaScript would freeze or crash when loading long strings of source code joined by plus signs. Since the computational time was O(N^2) it wasn't difficult to make Web pages which overloaded the Konqueror Web browser or Safari, which used the KJS JavaScript engine core. I first came across this issue when I was developing a markup language and JavaScript markup language parser, and then I discovered what was causing the problem when I wrote my script for JavaScript Includes.)

显然，这种性能的快速下降是一个巨大的问题。既然我们不能改变JavaScript将字符串作为不可变对象处理的方式，我们该如何处理它呢?解决方案是使用一种算法，尽可能少地重新创建字符串。

澄清一下，我们的目标是避免将短字符串添加到长字符串中，因为为了添加短字符串，整个长字符串也必须被复制。

算法如何避免将短字符串添加到长字符串

这里有一个减少创建新字符串对象次数的好方法。将较长的字符串连接在一起，以便每次向输出中添加一个以上的字节。

例如，要创建一个长度为N = 9的字符串:

x = 'x'; 
s = ''; 
s += x; /* Now s = 'x' */ 
x += x; /* Now x = 'xx' */ 
x += x; /* Now x = 'xxxx' */ 
x += x; /* Now x = 'xxxxxxxx' */ 
s += x; /* Now s = 'xxxxxxxxx' as desired */

这样做需要创建一个长度为1的字符串，创建一个长度为2的字符串，创建一个长度为4的字符串，创建一个长度为8的字符串，最后，创建一个长度为9的字符串。我们节省了多少成本?

旧成本C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45。

新成本C(9) = 1 + 2 + 4 + 8 + 9 = 24。

注意，我们必须将一个长度为1的字符串添加到一个长度为0的字符串中，然后将一个长度为1的字符串添加到一个长度为1的字符串中，然后将一个长度为2的字符串添加到一个长度为2的字符串中，然后将一个长度为4的字符串添加到一个长度为4的字符串中，然后将一个长度为8的字符串添加到一个长度为1的字符串中，以便获得一个长度为9的字符串。我们所做的事情可以概括为避免将短字符串添加到长字符串中，换句话说，尝试将长度相等或几乎相等的字符串连接在一起。

对于旧的计算成本，我们发现了一个公式N(N+1)/2。新的成本有公式吗?是的，但是很复杂。重要的是它是O(N)，所以将字符串长度增加一倍将使工作量大约增加一倍，而不是四倍。

实现这个新想法的代码几乎和计算代价的公式一样复杂。当您读取它时，请记住>>= 1表示右移1个字节。如果n = 10011是一个二进制数，那么n >>= 1的结果是n = 1001。

您可能不认识的代码的另一部分是按位和操作符，写为&。如果n的最后一位二进制数字为1，表达式n & 1的值为真;如果n的最后一位二进制数字为0，表达式n & 1的值为假。

新的高效stringFill3()函数

function stringFill3(x, n) { 
    var s = ''; 
    for (;;) { 
        if (n & 1) s += x; 
        n >>= 1; 
        if (n) x += x; 
        else break; 
    } 
    return s; 
} 

在外行人看来，它很丑，但它的表演却非常可爱。

让我们看看这个函数的性能如何。在看到结果后，您可能永远不会忘记O(N²)算法和O(N)算法之间的区别。

stringFill1()需要88.7微秒(百万分之一秒)来创建一个200字节的字符串，stringFill2()需要62.54，而stringFill3()只需要4.608。是什么让这个算法这么好?所有函数都利用了局部函数变量，但是利用第二种和第三种优化技术，stringFill3()的性能提高了20倍。

深入的分析

是什么让这个特殊的功能在竞争中脱颖而出呢?

正如我所提到的，这两个函数stringFill1()和stringFill2()运行如此缓慢的原因是JavaScript字符串是不可变的。不能重新分配内存，以允许每次多一个字节追加到JavaScript存储的字符串数据中。每当一个字节被添加到字符串的末尾，整个字符串就从头到尾重新生成。

因此，为了提高脚本的性能，必须预先通过将两个字符串连接在一起来计算更长的字符串长度，然后递归地构建所需的字符串长度。

例如，要创建一个16个字母的字节字符串，首先要预先计算两个字节的字符串。然后，两个字节的字符串将被重用，以预计算一个四字节的字符串。然后，4字节的字符串将被重用以预计算8字节的字符串。最后，两个8字节的字符串将被重用，以创建所需的16字节的新字符串。总共要创建四个新的字符串，一个长度为2，一个长度为4，一个长度为8，一个长度为16。总成本是2 + 4 + 8 + 16 = 30。

从长远来看，这种效率可以通过反向加法和使用一个几何级数来计算，该级数的第一项为a1 = N，公比为r = 1/2。等比级数的和由a_1 / (1-r) = 2N给出。

这比添加一个字符创建一个长度为2的新字符串，再创建一个长度为3、4、5的新字符串，直到16更有效。之前的算法使用了每次添加一个字节的过程，它的总代价将是n (n + 1) / 2 = 16(17) / 2 = 8(17) = 136。

显然，136比30大得多，所以之前的算法要花很多很多的时间来构建一个字符串。

为了比较这两种方法，您可以看到递归算法(也称为“分治”)在长度为123,457的字符串上的速度有多快。在我的FreeBSD计算机上，这个算法在stringFill3()函数中实现，在0.001058秒内创建字符串，而原始的stringFill1()函数在0.0808秒内创建字符串。新功能要快76倍。

性能上的差异随着字符串长度的增大而增大。在创建越来越大的字符串的极限中，原始函数的行为大致像C1(常数)乘以N²，而新函数的行为像C2(常数)乘以N。

从我们的实验可以确定C1的值为C1 = 0.0808 / (123457)2 = .00000000000530126997, C2的值为C2 = 0.001058 / 123457 = .00000000856978543136。在10秒内，新函数可以创建一个包含1,166,890,359个字符的字符串。为了创建相同的字符串，旧函数将需要7,218,384秒的时间。

这几乎是3个月，而不是10秒钟!

我之所以回答这个问题(晚了几年)，是因为我对这个问题的最初解决方案已经在互联网上流传了10多年，显然仍然没有被少数记得它的人理解。我想在这里写一篇关于它的文章会有所帮助:

高速JavaScript的性能优化/ Page 3

不幸的是，这里介绍的其他一些解决方案仍然需要花费3个月才能产生与正确的解决方案在10秒内生成的相同数量的输出。

我想花点时间在这里重现这篇文章的一部分，作为关于Stack Overflow的规范答案。

Note that the best-performing algorithm here is clearly based on my algorithm and was probably inherited from someone else's 3rd or 4th generation adaptation. Unfortunately, the modifications resulted in reducing its performance. The variation of my solution presented here perhaps did not understand my confusing for (;;) expression which looks like the main infinite loop of a server written in C, and which was simply designed to allow a carefully-positioned break statement for loop control, the most compact way to avoid exponentially replicating the string one extra unnecessary time.

扩展P.Bailey的解决方案:

String.prototype.repeat = function(num) {
    return new Array(isNaN(num)? 1 : ++num).join(this);
    }

这样你就可以避免意外的参数类型:

var foo = 'bar';
alert(foo.repeat(3));              // Will work, "barbarbar"
alert(foo.repeat('3'));            // Same as above
alert(foo.repeat(true));           // Same as foo.repeat(1)

alert(foo.repeat(0));              // This and all the following return an empty
alert(foo.repeat(false));          // string while not causing an exception
alert(foo.repeat(null));
alert(foo.repeat(undefined));
alert(foo.repeat({}));             // Object
alert(foo.repeat(function () {})); // Function

编辑:感谢jerone为他优雅的++num想法!