返回一个重复任意次数的字符串的最佳或最简洁的方法是什么？
以下是我迄今为止的最佳镜头:
function repeat(s, n){
var a = [];
while(a.length < n){
a.push(s);
}
return a.join('');
}
Peter Bailey.. 401
新读者注意:这个答案很老,而且不太实用 - 它只是"聪明",因为它使用数组的东西来完成String的事情.当我写"较少的过程"时,我绝对意味着"更少的代码",因为正如其他人在后续的答案中所指出的那样,它就像猪一样.因此,如果速度对您很重要,请不要使用它.
我将此函数直接放在String对象上.而不是创建一个数组,填充它,并用空char连接它,只需创建一个适当长度的数组,并将其与您想要的字符串连接.结果相同,流程少!
String.prototype.repeat = function( num )
{
return new Array( num + 1 ).join( this );
}
alert( "string to repeat\n".repeat( 4 ) );
我尽量不扩展本机对象,但这是一个很好的解决方案.谢谢! (36认同)
@ brad - 为什么不呢？您宁愿使用具有相当明确定义的主页(String对象)的函数污染全局命名空间？ (34认同)
如果你不希望延长本机对象,你可以把函数的字符串对象,而不是像这样:`String.repeat =功能(字符串,NUM){返回新阵列(parseInt函数(NUM)+ 1).加入(串); };`.这样称呼:`String.repeat('/ \',20)` (19认同)
实际上,您的两个参数也适用于全局命名空间.如果我要扩展命名空间并且有潜在的冲突,我宁愿这样做1)不是在全局2)中相关的,3)很容易重构.这意味着将它放在String原型上,而不是全局. (16认同)
我对这个函数做的一个改变是将parseInt()放在"num"周围,因为如果你有一个数字字符串,你可能会因JS的类型杂耍而得到奇怪的行为.例如:"my string".repeat("6")=="61" (11认同)
@nickf:人们不应该将字符串传递给期望数字的函数. (11认同)
如果你要使用`parseInt`,请使用基数(`parseInt(num,10)`); 否则,如果`num`碰巧有一个前导0(它将被解析为八进制),你会得到一个令人讨厌的惊喜.理想情况下,只需使用+ num(`new Array(+ num + 1)`). (6认同)
disfated.. 201
我已经测试了所有提议方法的性能.
这是我得到的最快的变种.
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)方法相比越快.
我只改变了两件事:
替换pattern = this为pattern = this.valueOf()(清除一个明显的类型转换);
将prototypejsif (count < 1)检查添加到函数顶部以排除不必要的操作.
来自Dennis的 应用优化答案(加速5-7%)
UPD
在这里为感兴趣的人创建了一个小型的性能测试操场.
变量count〜0 .. 100:
测试String.repeat()的不同变体的性能http://tinyurl.com/kb3raxr
constant count= 1024:
测试String.repeat()http://tinyurl.com/k527auo的不同变体的性能
如果可以的话,使用它并使其更快:)
新读者注意:这个答案很老,而且不太实用 - 它只是"聪明",因为它使用数组的东西来完成String的事情.当我写"较少的过程"时,我绝对意味着"更少的代码",因为正如其他人在后续的答案中所指出的那样,它就像猪一样.因此,如果速度对您很重要,请不要使用它.
我将此函数直接放在String对象上.而不是创建一个数组,填充它,并用空char连接它,只需创建一个适当长度的数组,并将其与您想要的字符串连接.结果相同,流程少!
String.prototype.repeat = function( num )
{
return new Array( num + 1 ).join( this );
}
alert( "string to repeat\n".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)方法相比越快.
我只改变了两件事:
替换pattern = this为pattern = this.valueOf()(清除一个明显的类型转换);
将prototypejsif (count < 1)检查添加到函数顶部以排除不必要的操作.
来自Dennis的 应用优化答案(加速5-7%)
UPD
在这里为感兴趣的人创建了一个小型的性能测试操场.
变量count〜0 .. 100:
测试String.repeat()的不同变体的性能http://tinyurl.com/kb3raxr
constant count= 1024:
测试String.repeat()http://tinyurl.com/k527auo的不同变体的性能
如果可以的话,使用它并使其更快:)
This problem is a well-known/"classic" optimization issue for JavaScript, caused by the fact that JavaScript strings are "immutable" and addition by concatenation of even a single character to a string requires creation of, including memory allocation for and copying to, an entire new string.
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 Performance Results for the accepted answer, the top-performing other answer (based on a degraded version of the original algorithm in this answer), and this answer using my algorithm created 13 years ago
~ 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.
Original string repetition/multiplication JavaScript algorithm by Joseph Myers, circa Y2K as a text multiplying function within Text.js; published August, 2008 in this form by Web Reference: http://www.webreference.com/programming/javascript/jkm3/3.html (The article used the function as an example of JavaScript optimizations, which is the only for the strange name "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).
Below ensues a discussion of some JavaScript optimizations related to all of the answers to this problem and for the benefit of all.
为了说明这种技术是如何工作的,我们使用了一个真实的JavaScript函数来创建所需长度的字符串.正如我们所看到的,可以添加更多优化!
像这里使用的函数的功能是创建填充以对齐文本列,格式化钱,或填充块数据到边界.文本生成功能还允许可变长度输入,用于测试对文本进行操作的任何其他功能.此函数是JavaScript文本处理模块的重要组件之一.
As we proceed, we will be covering two more of the most important optimization techniques while developing the original code into an optimized algorithm for creating strings. The final result is an industrial-strength, high-performance function that I've used everywhere--aligning item prices and totals in JavaScript order forms, data formatting and email/text message formatting and many other uses.
Original code for creating strings stringFill1()
function stringFill1(x, n) {
var s = '';
while (s.length < n) s += x;
return s;
}
/* Example of output: stringFill1('x', 3) == 'xxx' */
The syntax is here is clear. As you can see, we've used local function variables already, before going on to more optimizations.
请注意,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() takes 47.297 microseconds (millionths of a second) to fill a 100-byte string, and stringFill2() takes 27.68 microseconds to do the same thing. That's almost a doubling in performance by avoiding a reference to an object property.
Our previous result looked good--very good, in fact. The improved function stringFill2() is much faster due to the use of our first two optimizations. Would you believe it if I told you that it can be improved to be many times faster than it is now?
Yes, we can accomplish that goal. Right now we need to explain how we avoid appending short strings to long strings.
The short-term behavior appears to be quite good, in comparison to our original function. Computer scientists like to analyze the "asymptotic behavior" of a function or computer program algorithm, which means to study its long-term behavior by testing it with larger inputs. Sometimes without doing further tests, one never becomes aware of ways that a computer program could be improved. To see what will happen, we're going to create a 200-byte string.
The problem that shows up with 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."
Immutable means that you cannot change a string once it's created. By adding on one byte at a time, we're not using up one more byte of effort. We're actually recreating the entire string plus one more byte.
In effect, to add one more byte to a 100-byte string, it takes 101 bytes worth of work. Let's briefly analyze the computational cost for creating a string of N bytes. The cost of adding the first byte is 1 unit of computational effort. The cost of adding the second byte isn't one unit but 2 units (copying the first byte to a new string object as well as adding the second byte). The third byte requires a cost of 3 units, etc.
C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2). The symbol O(N^2) is pronounced Big O of N squared, and it means that the computational cost in the long run is proportional to the square of the string length. To create 100 characters takes 10,000 units of work, and to create 200 characters takes 40,000 units of work.
This is why it took more than twice as long to create 200 characters than 100 characters. In fact, it should have taken four times as long. Our programming experience was correct in that the work is being done slightly more efficiently for longer strings, and hence it took only about three times as long. Once the overhead of the function call becomes negligible as to how long of a string we're creating, it will actually take four times as much time to create a string twice as long.
(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.)
Clearly this rapid degradation of performance is a huge problem. How can we deal with it, given that we cannot change JavaScript's way of handling strings as immutable objects? The solution is to use an algorithm which recreates the string as few times as possible.
To clarify, our goal is to avoid adding short strings to long strings, since in order to add the short string, the entire long string also must be duplicated.
How the algorithm works to avoid adding short strings to long strings
Here's a good way to reduce the number of times new string objects are created. Concatenate longer lengths of string together so that more than one byte at a time is added to the output.
For instance, to make a string of length 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 */
Doing this required creating a string of length 1, creating a string of length 2, creating a string of length 4, creating a string of length 8, and finally, creating a string of length 9. How much cost have we saved?
Old cost C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45.
New cost C(9) = 1 + 2 + 4 + 8 + 9 = 24.
Note that we had to add a string of length 1 to a string of length 0, then a string of length 1 to a string of length 1, then a string of length 2 to a string of length 2, then a string of length 4 to a string of length 4, then a string of length 8 to a string of length 1, in order to obtain a string of length 9. What we're doing can be summarized as avoiding adding short strings to long strings, or in other words, trying to concatenate strings together that are of equal or nearly equal length.
For the old computational cost we found a formula N(N+1)/2. Is there a formula for the new cost? Yes, but it's complicated. The important thing is that it is O(N), and so doubling the string length will approximately double the amount of work rather than quadrupling it.
The code that implements this new idea is nearly as complicated as the formula for the computational cost. When you read it, remember that >>= 1 means to shift right by 1 byte. So if n = 10011 is a binary number, then n >>= 1 results in the value n = 1001.
The other part of the code you might not recognize is the bitwise and operator, written &. The expression n & 1 evaluates true if the last binary digit of n is 1, and false if the last binary digit of n is 0.
New highly-efficient stringFill3() function
function stringFill3(x, n) {
var s = '';
for (;;) {
if (n & 1) s += x;
n >>= 1;
if (n) x += x;
else break;
}
return s;
}
It looks ugly to the untrained eye, but it's performance is nothing less than lovely.
Let's see just how well this function performs. After seeing the results, it's likely that you'll never forget the difference between an O(N^2) algorithm and an O(N) algorithm.
stringFill1() takes 88.7 microseconds (millionths of a second) to create a 200-byte string, stringFill2() takes 62.54, and stringFill3() takes only 4.608. What made this algorithm so much better? All of the functions took advantage of using local function variables, but taking advantage of the second and third optimization techniques added a twenty-fold improvement to performance of stringFill3().
Deeper analysis
What makes this particular function blow the competition out of the water?
As I've mentioned, the reason that both of these functions, stringFill1() and stringFill2(), run so slowly is that JavaScript strings are immutable. Memory cannot be reallocated to allow one more byte at a time to be appended to the string data stored by JavaScript. Every time one more byte is added to the end of the string, the entire string is regenerated from beginning to end.
Thus, in order to improve the script's performance, one must precompute longer length strings by concatenating two strings together ahead of time, and then recursively building up the desired string length.
For instance, to create a 16-letter byte string, first a two byte string would be precomputed. Then the two byte string would be reused to precompute a four-byte string. Then the four-byte string would be reused to precompute an eight byte string. Finally, two eight-byte strings would be reused to create the desired new string of 16 bytes. Altogether four new strings had to be created, one of length 2, one of length 4, one of length 8 and one of length 16. The total cost is 2 + 4 + 8 + 16 = 30.
In the long run this efficiency can be computed by adding in reverse order and using a geometric series starting with a first term a1 = N and having a common ratio of r = 1/2. The sum of a geometric series is given by a_1 / (1-r) = 2N.
This is more efficient than adding one character to create a new string of length 2, creating a new string of length 3, 4, 5, and so on, until 16. The previous algorithm used that process of adding a single byte at a time, and the total cost of it would be n (n + 1) / 2 = 16 (17) / 2 = 8 (17) = 136.
Obviously, 136 is a much greater number than 30, and so the previous algorithm takes much, much more time to build up a string.
To compare the two methods you can see how much faster the recursive algorithm (also called "divide and conquer") is on a string of length 123,457. On my FreeBSD computer this algorithm, implemented in the stringFill3() function, creates the string in 0.001058 seconds, while the original stringFill1() function creates the string in 0.0808 seconds. The new function is 76 times faster.
The difference in performance grows as the length of the string becomes larger. In the limit as larger and larger strings are created, the original function behaves roughly like C1 (constant) times N^2, and the new function behaves like C2 (constant) times N.
From our experiment we can determine the value of C1 to be C1 = 0.0808 / (123457)2 = .00000000000530126997, and the value of C2 to be C2 = 0.001058 / 123457 = .00000000856978543136. In 10 seconds, the new function could create a string containing 1,166,890,359 characters. In order to create this same string, the old function would need 7,218,384 seconds of time.
This is almost three months compared to ten seconds!
I'm only answering (several years late) because my original solution to this problem has been floating around the Internet for more than 10 years, and apparently is still poorly-understood by the few who do remember it. I thought that by writing an article about it here I would help:
Performance Optimizations for High Speed JavaScript/Page 3
Unfortunately, some of the other solutions presented here are still some of those that would take three months to produce the same amount of output that a proper solution creates in 10 seconds.
I want to take the time to reproduce part of the article here as a canonical answer on 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.
这个很有效率
String.prototype.repeat = function(times){
var result="";
var pattern=this;
while (times > 0) {
if (times&1)
result+=pattern;
times>>=1;
pattern+=pattern;
}
return result;
};
好消息!String.prototype.repeat被接受为Harmony(ECMAScript 6).
"yo".repeat(2); // returns: "yoyo"
该方法适用于最新版本的V8,由Node.js,Chrome(String.prototype.repeat自版本41支持)和Opera使用.较新版本的Safari和Firefox似乎也有支持,但Internet Explorer却没有.有关最新列表,请参阅MDN:String.prototype.repeat>浏览器兼容性.
MDN提出以下polyfill:
"yo".repeat(2); // returns: "yoyo"
String.prototype.repeat现在是ES6 Standard.
'abc'.repeat(3); //abcabcabc
扩展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!
使用 Array(N+1).join("string_to_repeat")
/**
@desc: repeat string
@param: n - times
@param: d - delimiter
*/
String.prototype.repeat = function (n, d) {
return --n ? this + (d || '') + this.repeat(n, d) : '' + this
};
这是使用分隔符多次重复字符串的方法.
京公网安备 11010802040832号 | 京ICP备19059560号-6 