重复字符串
什么是最好或最简洁的方法返回一个字符串重复任意次的时间？
以下是迄今为止我的最佳射门：
function repeat(s, n){
var a = [];
while(a.length < n){
a.push(s);
}
return a.join('');
}
新读者请注意：这个答案是旧的，而且不是非常实用 - 它只是“聪明”，因为它使用Array的东西来完成String事情。 当我写下“较少过程”时，我的意思是“较少代码”，因为正如其他人在随后的答案中指出的那样，它表现得像猪一样。 所以，如果速度对您来说很重要，请不要使用它。
我会直接把这个函数放到String对象上。 不要创建一个数组，填充它，并将它与一个空字符结合起来，只需创建一个合适长度的数组，然后将它与所需的字符串结合起来。 同样的结果，更少的过程！
String.prototype.repeat = function( num )
{
return new Array( num + 1 ).join( this );
}
alert( "string to repeatn".repeat( 4 ) );
我测试了所有建议的方法的性能。
这是我得到的最快的变体 。
String.prototype.repeat = function(count) {
if (count < 1) return '';
var result = '', pattern = this.valueOf();
while (count > 1) {
if (count & 1) result += pattern;
count >>= 1, pattern += pattern;
}
return result + pattern;
};
或作为独立功能：
function repeat(pattern, count) {
if (count < 1) return '';
var result = '';
while (count > 1) {
if (count & 1) result += pattern;
count >>= 1, pattern += pattern;
}
return result + pattern;
}
它基于artistoex算法。 它真的很快。 count越大，与传统的new Array(count + 1).join(string)方法相比， count速度就越快。
我只改变了两件事：
pattern = this.valueOf()替换pattern = this （清除一个明显的类型转换）; if (count < 1)从prototypejs检查到函数的顶部以便排除不必要的操作，则添加。 UPD
在这里为感兴趣的人创造一个性能测试的小场地。
变量count 〜0 .. 100：
测试String.repeat（）的不同变体的性能http://tinyurl.com/kb3raxr
恒定count = 1024：
测试String.repeat（）的不同变体的性能http://tinyurl.com/k527auo
如果可以的话，使用它并且使它更快）
这个问题是JavaScript的一个众所周知的/“经典”的优化问题，其原因是JavaScript字符串是“不可变的”，而且即使是单个字符串连接也需要创建，包括内存分配和复制，一个完整的新字符串。
不幸的是，这个网页上接受的答案是错误的，其中“错误”的意思是对于简单的单字符串的性能因子为3x，对于短串重复多次的8x-97x，对于重复的句子为300x，以及当在n趋于无穷大时，将算法的复杂度比率限制在一个范围内。 另外，在这个页面上还有另外一个答案，这个答案几乎是正确的（基于过去13年在整个互联网上传播的正确解决方案的许多代和变化之一）。 然而，这种“几乎正确”的解决方案错过了正确算法的关键点，导致50％的性能下降。
JS性能结果为接受的答案，表现最佳的其他答案（基于此答案中原始算法的降级版本）以及使用我的算法在13年前创建的答案
〜2000年10月我发表了一个针对这个确切问题的算法，该算法被广泛适用，修改，然后最终被理解和忘记。 为了解决这个问题，2008年8月，我发布了一篇文章http://www.webreference.com/programming/javascript/jkm3/3.html，解释算法并将其用作简单的通用JavaScript优化的示例。 到目前为止，Web Reference已经清除了我的联系信息，甚至是本文中的我的名字。 再一次地，该算法已经被广泛地适应，修改，然后被很少理解并被很大程度地遗忘。
原始字符串重复/乘法JavaScript算法由Joseph Myers，作为Text.js中的文本乘法函数在Y2K左右; 发表于2008年8月的Web表单：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;
}
在该文章发表后的两个月内，这个相同的问题被发布到Stack Overflow，直到现在，我的雷达一直在飞行，显然这个问题的原始算法再次被遗忘。 此堆栈溢出页面上提供的最佳解决方案是我的解决方案的一个修改版本，可能分隔几代。 不幸的是，这些修改破坏了解决方案的最优性。 事实上，通过改变原来的循环结构，修改后的解决方案执行完全不需要的指数复制的额外步骤（从而将正确答案中使用的最大字符串与其自身的额外时间相加，然后丢弃它）。
下面接着讨论一些与所有这个问题的答案有关的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有一个无辜的引用会影响其性能。 更糟的是，使用这个对象属性通过假设读者知道JavaScript字符串对象的属性来降低程序的简单性。
这个对象属性的使用破坏了计算机程序的通用性。 该程序假定x必须是长度为1的字符串。 这限制了stringFill1()函数的应用，除了单个字符的重复之外。 即使单个字符包含像HTML实体那样的多个字节，也不能使用 。
由于不必要地使用对象属性而导致的最糟糕的问题是，如果在空的输入字符串x上测试，该函数会创建一个无限循环。 要检查一般性，请将程序应用于尽可能最小的输入量。 当被要求超过可用内存量时，崩溃的程序有一个借口。 像这样的一个程序，当被要求产生任何东西时崩溃是不可接受的。 有时候漂亮的代码是有毒的代码。
简单化可能是计算机编程的模糊目标，但通常不是。 当一个程序缺乏任何合理的通用性时，说“这个程序足够好，只要它已经足够了”就是无效的。 正如你所看到的，使用string.length属性可以防止该程序在一般设置下工作，事实上，不正确的程序已经准备好导致浏览器或系统崩溃。
有没有办法提高这个JavaScript的性能，以及照顾这两个严重的问题？
当然。 只需使用整数。
用于创建字符串的优化代码stringFill2()
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()显示的问题
使用我们的定时功能，我们发现200字节字符串的时间增加到62.54微秒，而100字节字符串的时间增加到27.68。 看起来时间应该增加一倍，因为做了两倍的工作，而是增加了三倍或四倍。 从编程经验来看，这个结果似乎很奇怪，因为如果有的话，函数应该稍微快一点，因为工作的效率更高（每个函数调用200字节，而不是每个函数调用100字节）。 这个问题与JavaScript字符串的阴险属性有关：JavaScript字符串是“不可变的”。
不可变意味着一旦创建它就不能更改字符串。 通过一次添加一个字节，我们就不会再使用一个字节的工作。 实际上我们重新创建了整个字符串再加上一个字节。
实际上，要向100字节的字符串添加一个字节，则需要101个字节的工作量。 让我们简要分析一下创建一个N字节的字符串的计算成本。 添加第一个字节的成本是1个计算单位。 添加第二个字节的成本不是一个单位，而是两个单位（将第一个字节复制到一个新的字符串对象以及添加第二个字节）。 第三个字节需要3个单位的成本等。
C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2) 。 符号O(N^2)发音为N的平方大O，这意味着长期计算成本与字符串长度的平方成正比。 要创建100个字符需要10,000个工作单元，创建200个字符需要40,000个工作单元。
这就是为什么创建超过100个字符的200个字符需要两倍多的时间。 实际上，它应该花费四倍的时间。 我们的编程经验是正确的，因为对于较长的字符串，这项工作的效率稍高一些，因此只需要三倍左右的时间。 一旦函数调用的开销变得可以忽略，我们正在创建一个字符串多长时间，它实际上需要四倍的时间来创建一个字符串两倍的长度。
（历史记录：此分析不一定适用于源代码中的字符串，例如html = 'abcdn' + 'efghn' + ... + 'xyz.n' ，因为JavaScript源代码编译器可以在将字符串合并为一个JavaScript字符串对象之前将它们连接在一起。就在几年前，当加载由加号连接的长字符串源代码时，JavaScript的KJS实现会冻结或崩溃，因为计算时间为O(N^2)使网页重载Konqueror Web浏览器或使用KJS JavaScript引擎核心的Safari并不困难，当我开发标记语言和JavaScript标记语言解析器时，首先遇到了这个问题，然后我发现了当我为JavaScript包含脚本编写脚本时导致问题的原因。）
显然，这种性能的急剧下降是一个巨大的问题。 我们如何处理它，因为我们无法改变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。
新的高效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^2)算法和O(N)算法之间的差异。
stringFill1()需要88.7微秒（百万分之一秒）来创建一个200字节的字符串， stringFill2()需要62.54，而stringFill3()只需要4.608。 是什么让这个算法变得更好？ 所有这些函数都利用了局部函数变量，但利用第二个和第三个优化技术为stringFill3()性能增加了20倍的改进。
更深入的分析
是什么让这个特殊的功能将比赛从水中排出？
正如我所提到的，这两个函数stringFill1()和stringFill2()运行得非常缓慢的原因是JavaScript字符串是不可变的。 内存不能被重新分配，以允许一次将多一个字节附加到JavaScript存储的字符串数据中。 每次在字符串末尾添加一个字节时，整个字符串将从头到尾重新生成。
因此，为了提高脚本的性能，必须提前计算长度较长的字符串，方法是提前连接两个字符串，然后递归构建所需的字符串长度。
例如，要创建一个16个字母的字节字符串，首先需要预先计算一个两字节的字符串。 然后，这两个字节的字符串将被重用来预先计算一个四字节的字符串。 然后四字节字符串将被重新使用以预先计算八字节字符串。 最后，将重新使用两个八字节字符串来创建所需的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^2 ，并且新函数的行为与C2 （常量）时间N 。
根据我们的实验，我们可以确定C1的值为C1 = 0.0808 / (123457)2 = .00000000000530126997 ，并且C2的值为C2 = 0.001058 / 123457 = .00000000856978543136 。 在10秒内，新函数可以创建一个包含1,166,890,359个字符的字符串。 为了创建相同的字符串，旧功能需要7,218,384秒的时间。
这差不多是三个月而非十秒！
我只是回答（几年后），因为我对这个问题的最初解决方案已经在互联网上浮动了10多年，显然还是很少有人记得它。 我想通过写一篇关于它的文章，我会帮助：
针对高速JavaScript的性能优化/页面3
不幸的是，这里提出的其他一些解决方案仍然是一些需要三个月的时间才能产生相同数量的输出，以便在10秒内产生适当的解决方案。
我想花时间在这里重现这篇文章的一部分，作为堆栈溢出的规范答案。
请注意，这里性能最好的算法显然是基于我的算法，可能是继承自其他人的第3代或第4代适应。 不幸的是，这些修改导致其性能下降。 这里提出的解决方案的变体可能不理解我for (;;)表达式的困惑for (;;)这个表达式看起来像用C语言编写的服务器的主要无限循环，而且它被设计为允许仔细定位循环控制的break语句，避免指数级复制字符串一个额外不必要的时间的最紧凑的方法。
上一篇: Repeat String