Character Repeat

[blaine]

I'm looking for an easy way to repeat a character.

For example in Perl if you want 5 "x"'s the code is
$str = "x" x 5; # result xxxxx

I've tried a few ways in javascript to accomplish this, but can not
come up with anything other then the lame old basic way which is
probably more processing then required...

var str = "";
for (var i = 0; 5 > i; i++){
str += "x";
}

Any better solutions?

 

[Joost Diepenmaat]

I'm looking for an easy way to repeat a character.

For example in Perl if you want 5 "x"'s the code is
$str = "x" x 5; # result xxxxx

I've tried a few ways in javascript to accomplish this, but can not
come up with anything other then the lame old basic way which is
probably more processing then required...

var str = "";
for (var i = 0; 5 > i; i++){
str += "x";
}

Any better solutions?

var a = [];
for (var i = 0; i < 5; i++) {
a.push("x");
}
var str = a.join("");

which won't work on quite a few browsers, and may or may not be slower.

Joost.

 

[Evertjan.]

Joost Diepenmaat wrote on 31 jan 2008 in comp.lang.javascript:

I'm looking for an easy way to repeat a character.

For example in Perl if you want 5 "x"'s the code is
$str = "x" x 5; # result xxxxx

I've tried a few ways in javascript to accomplish this, but can not
come up with anything other then the lame old basic way which is
probably more processing then required...

var str = "";
for (var i = 0; 5 > i; i++){
str += "x";
}

Any better solutions?

var a = [];
for (var i = 0; i < 5; i++) {
a.push("x");
}
var str = a.join("");

which won't work on quite a few browsers, and may or may not be slower.

function charstring(ch,n){
if (n<0||n>10) return 'error';
return '1234567890'.substr(0,n).replace(/(.)/g,ch);
};

alert( charstring('x',5) );

 

[RobG]

I'm looking for an easy way to repeat a character.

For example in Perl if you want 5 "x"'s the code is
$str = "x" x 5; # result xxxxx

I've tried a few ways in javascript to accomplish this, but can not
come up with anything other then the lame old basic way which is
probably more processing then required...

var str = "";
for (var i = 0; 5 > i; i++){
str += "x";
}

Essentially, that's it. It can be optimised though: the += compound
operator is notoriously slow in some browsers, an Array with push/join
is usually faster, it shouldn't be slower. A while or do..while loop
should be faster than a for loop, consider something like:

String.prototype.by = function(n){
var s = [];
if (n > 0) {
do {
s.push(this);
} while (--n);
}
return s.join('');
}

var a = 'a';

a.by(0) //==> empty string
a.by(5) //==> aaaaa

var f = 'fred';
f.by(5) //==> fredfredfredfredfred

 

[pr]

I'm looking for an easy way to repeat a character.

For example in Perl if you want 5 "x"'s the code is
$str = "x" x 5; # result xxxxx

I've tried a few ways in javascript to accomplish this, but can not
come up with anything other then the lame old basic way which is
probably more processing then required...

var str = "";
for (var i = 0; 5 > i; i++){
str += "x";
}

Any better solutions?

Here's a thought:

function stringOf(ch, len) {
var arr = [];
arr.length = len + 1;
return arr.join(ch);
}

alert(stringOf("x", 5));

where 'ch' may be any length of string; for example "pelican".

 

[Dr J R Stockton]

In comp.lang.javascript message <abc29a16-e0f3-43ac-9db3-9b7573a19db0@s3
7g2000prg.googlegroups.com>, Thu, 31 Jan 2008 15:16:43, RobG

Essentially, that's it.

It can be optimised though: the += compound
operator is notoriously slow in some browsers, an Array with push/join
is usually faster, it shouldn't be slower. A while or do..while loop
should be faster than a for loop, consider something like:

Google : +JavaScript +"Making a Long String" finds
<URL:http://www.merlyn.demon.co.uk/js-misc0.htm#MLS>.

That shows that EvertJan used to know a short, fast method; and I a
faster - that is especially so for big repeats.

function BigCat(L) {
if (!L) return ""
if (L&1) return BigCat(L-1) + "x"
var T = BigCat(L>>1) ; return T + T }

function EjHCat(L) { return new Array(L+1).join('*') }

It's a good idea to read the newsgroup c.l.j and its FAQ. See below.

 

[Jambalaya]

I'm looking for an easy way to repeat a character.
var str = "";
for (var i = 0; 5 > i; i++){
str += "x";
}

Here's a thought:

function stringOf(ch, len) {
var arr = [];
arr.length = len + 1;
return arr.join(ch);
}

alert(stringOf("x", 5));

where 'ch' may be any length of string; for example "pelican".

Same but different:

function repeat(rptWhat, howManyTimes){
return new Array(howManyTimes+1).join(rptWhat);
}

Might have some issues in *old* UAs due to some non-standard handling
of using the array length in the constructor, but works fine in all /
current/ UAs.

J

 

[Lee]

(e-mail address removed) said:

I'm looking for an easy way to repeat a character.

For example in Perl if you want 5 "x"'s the code is
$str = "x" x 5; # result xxxxx

I've tried a few ways in javascript to accomplish this, but can not
come up with anything other then the lame old basic way which is
probably more processing then required...

var str = "";
for (var i = 0; 5 > i; i++){
str += "x";
}

Any better solutions?

If you're only doing this a few times, it probably doesn't matter.
If you're doing this a lot, it may be more efficient to have a few
built in advance:

exxes[0]="";
exxes[1]="x";
exxes[2]="xx";
....
exxes[10]="xxxxxxxxxx";

The range and frequency of values will determine whether you
also want to consider combining these to make the larger values
or just extend the array. If you do build some on the fly, you
also need to consider caching them in the exxes[] array.


--

 

[Thomas 'PointedEars' Lahn]

I'm looking for an easy way to repeat a character.

For example in Perl if you want 5 "x"'s the code is
$str = "x" x 5; # result xxxxx

I've tried a few ways in javascript to accomplish this, but can not
come up with anything other then the lame old basic way which is
probably more processing then required...

var str = "";
for (var i = 0; 5 > i; i++){
str += "x";
}

Any better solutions?

var a = [];
for (var i = 0; i < 5; i++) {
a.push("x");
}
var str = a.join("");

which won't work on quite a few browsers,

- The Array literal requires JavaScript 1.3, JScript 2.0, ECMAScript 3.
- Array.prototype.push() requires JavaScript 1.2, JScript 5.5, ECMAScript 3.
- Array.prototype.join() requires JavaScript 1.1, JScript 2.0, ECMAScript 1.

So yes, it is not going to work in Netscape Navigator before version 4.06
and Internet Explorer before version 5.5. However, if that is desired,
maximum compatibility (to JavaScript 1.1, JScript 2.0, ECMAScript 1) can be
achieved with slight modifications:

var a = new Array();

for (var i = 0; i < 5; i++)
{
a[a.length] = "x";
}

var str = a.join("");

See http://PointedEars.de/es-matrix

and may or may not be slower.

Efficiency can be increased with:

for (var i = 5; i--
{
// ...
}

Here are the (for me rather surprising) benchmark results (10 * 50'000
iterations) from Firefox 2.0.0.11 on Windows XP SP 2 on a Pentium M 740:

Approach | avg | min | max (all in ms)
-----------------------------------+-----+-----+----------------
+= | 444 | 328 | 1297
+=/i-- | 372 | 265 | 1187
[]/push()/join() | 639 | 453 | 1297
[]/push()/join()/i-- | 617 | 391 | 1250
new Array()/a[a.length]/join() | 681 | 485 | 1375
new Array()/a[a.length]/join()/i-- | 605 | 421 | 1297

So it would appear optimized concatenation beats them after all.


PointedEars

 

[RobG]

On Feb 3, 4:35 am, Thomas 'PointedEars' Lahn <[email protected]>
wrote:
[...]

Here are the (for me rather surprising) benchmark results (10 * 50'000
iterations) from Firefox 2.0.0.11 on Windows XP SP 2 on a Pentium M 740:

Approach | avg | min | max (all in ms)
-----------------------------------+-----+-----+----------------
+= | 444 | 328 | 1297
+=/i-- | 372 | 265 | 1187
[]/push()/join() | 639 | 453 | 1297
[]/push()/join()/i-- | 617 | 391 | 1250
new Array()/a[a.length]/join() | 681 | 485 | 1375
new Array()/a[a.length]/join()/i-- | 605 | 421 | 1297

So it would appear optimized concatenation beats them after all.

Try it in IE, where += is comparatively very slow.

In any case, the function suggested by Dr J is hands-down fastest - it
employs a geometric progression using a factor of 2 rather than a
simple arithmetic progression. You will likely need at least 10,000
iterations to see anything more than 1ms if repeating a single
character. It is significantly slowed if multiple characters are in
the string, but it is still faster than other methods. Try:

function repeat(s, n) {
if (!n) return "";
if (n & 1) return repeat(s, n-1) + s;
var t = repeat(s, n>>1);
return t + t;
}

Where s is the string to repeat and n the number of repetitions.

To see what is happening a bit more clearly, the bit-wise expressions
can be re-written as:

if (n % 2) return repeat(s, --n) + s;

var t = repeat(s, Math.floor(n/2));


But that is much slower.

 

[Thomas 'PointedEars' Lahn]

Here are the (for me rather surprising) benchmark results (10 * 50'000
iterations) from Firefox 2.0.0.11 on Windows XP SP 2 on a Pentium M 740:
[...]
So it would appear optimized concatenation beats them after all.

Try it in IE, where += is comparatively very slow.

I will.

In any case, the function suggested by Dr J is hands-down fastest - it
employs a geometric progression using a factor of 2 rather than a
simple arithmetic progression. You will likely need at least 10,000
iterations to see anything more than 1ms if repeating a single
character. It is significantly slowed if multiple characters are in
the string, but it is still faster than other methods. Try:

function repeat(s, n) {
if (!n) return "";
if (n & 1) return repeat(s, n-1) + s;
var t = repeat(s, n>>1);
return t + t;
}

Where s is the string to repeat and n the number of repetitions.

However, the approach has the obvious drawback that one risks a stack
overflow with a sufficient number of repetitions. As often with one-sided
optimization, you would have to buy runtime efficiency with memory
efficiency and in this case even with reliability.


PointedEars

 

[Dr J R Stockton]

In comp.lang.javascript message <27f83f46-5ba5-40ff-8a90-b64aec3962d5@c4
g2000hsg.googlegroups.com>, Sun, 3 Feb 2008 00:57:59, RobG

In any case, the function suggested by Dr J is hands-down fastest - it
employs a geometric progression using a factor of 2 rather than a
simple arithmetic progression.

Of course, since it is necessary to emplace all n characters, the
individual steps get slower as the job nears completion. That way is
more interesting but not much faster than EvertJan's best.

You will likely need at least 10,000
iterations to see anything more than 1ms

and with JavaScript you'll need a less common OS to be able to detect
anything under about 10 ms - but (RSVP) I don't know about Vista timing.

if repeating a single
character. It is significantly slowed if multiple characters are in
the string, but it is still faster than other methods. Try:

function repeat(s, n) {
if (!n) return "";
if (n & 1) return repeat(s, n-1) + s;
var t = repeat(s, n>>1);
return t + t;
}

Where s is the string to repeat and n the number of repetitions.

To see what is happening a bit more clearly, the bit-wise expressions
can be re-written as:

if (n % 2) return repeat(s, --n) + s;

var t = repeat(s, Math.floor(n/2));


But that is much slower.

Try ((n/2)|0) instead of Math.floor(n/2) if n is not too big.

Note : there should be no realistic concern about stack depth, since for
it to be possible to halve n reliably we must have n <= 2^53, and we
ought to be able to go deeper than 53.

The method needs enough store for the result, plus 50% for the half-
result, plus up to about 53 recursions.

Testing the following pessimised algorithm in my P4 1GB XP sp2 IE6
<js-quick.htm>, I could use an argument of 1111 but not 1112. YMMV.

function reCURSE(n) { return n==0 ? "" : reCURSE(n-1)+"$" }
reCURSE(1111).length

 

[RobG]

RobG wrote: [...]

In any case, the function suggested by Dr J is hands-down fastest - it
employs a geometric progression using a factor of 2 rather than a
simple arithmetic progression. You will likely need at least 10,000
iterations to see anything more than 1ms if repeating a single
character. It is significantly slowed if multiple characters are in
the string, but it is still faster than other methods. Try:

function repeat(s, n) {
if (!n) return "";
if (n & 1) return repeat(s, n-1) + s;
var t = repeat(s, n>>1);
return t + t;
}

Where s is the string to repeat and n the number of repetitions.

However, the approach has the obvious drawback that one risks a stack
overflow with a sufficient number of repetitions. As often with one-sided
optimization, you would have to buy runtime efficiency with memory
efficiency and in this case even with reliability.

Which might explain why it is affected more than the others when the
initial string has more than one character. However, in only 50
recursions it can create a string of up to 2^48+1 repetitions, which
is a seriously large string even if the initial string is one
character. The largest number that javascript can hold exactly is
2^53, so it is unlikely that a stack overflow will result from a
single call.

I think that any script engine capable of recursion can manage at
least 100 recursions, I can't imagine a use for the size of string
that may produce so in practice it is unlikely that a stack overflow
caused by recursion will be an issue.

And the "get out of goal" card is: if someone really wants a string
that big, they can re-write the function to use iteration rather than
recursion, or they can use a factor of 4 or 8 to cut down the depth of
recursion.

 

[Dr J R Stockton]

In comp.lang.javascript message <8e3abb73-7964-4f3f-948b-ac60f2e6b238@e6
g2000prf.googlegroups.com>, Sun, 3 Feb 2008 15:59:54, RobG

On Feb 3, 7:23 pm, Thomas 'PointedEars' Lahn <[email protected]>
wrote:

The largest number that javascript can hold exactly is
2^53, so it is unlikely that a stack overflow will result from a
single call.

For most values if n, there's a way round even that, in principle.
Split n into two near-equal factors, p & q, and evaluate
repeat(repeat(s, p), q)

Approximately, the total number of recursions will be unchanged, but the
maximum depth will be halved.

That expression uses repeat in an essentially iterative manner, which
could no doubt be changed to recursing over all of the factors of n.
But watch out; if n = 2^k, the original depth is again attained; the
actors need to be grouped a bit.

 

[RobG]

In comp.lang.javascript message <27f83f46-5ba5-40ff-8a90-b64aec3962d5@c4
g2000hsg.googlegroups.com>, Sun, 3 Feb 2008 00:57:59, RobG
<[email protected]> posted:




Of course, since it is necessary to emplace all n characters, the
individual steps get slower as the job nears completion. That way is
more interesting but not much faster than EvertJan's best.


and with JavaScript you'll need a less common OS to be able to detect
anything under about 10 ms - but (RSVP) I don't know about Vista timing.

Sorry, can't help there - I don't have Vista but I guess I'll have to
get round to sooner or later if only for testing.

Try ((n/2)|0) instead of Math.floor(n/2) if n is not too big.

Note : there should be no realistic concern about stack depth, since for
it to be possible to halve n reliably we must have n <= 2^53, and we
ought to be able to go deeper than 53.

I decided as an exercise to write an iterative version to get a better
handle on bitwise operators - it took a while but finally the penny
dropped.

Testing in Firefox shows it's better than twice as fast as the
recursive method, in IE it's perhaps 50% faster - I'll test Opera and
Safari later.

A result string of about 10,000,000 characters is required to get
meaningful results, so I think at this point the value of further
optimisation is moot:


function repeat1(s, n) {
var r = '';
while (n) {
if (n & 1) r = r + s;
if (n == 1) break;
n = n >> 1;
s = s + s;
}
return r;
}

The extra (n==1) test is not necessary for the algorithm but it helps
greatly where n is large as it avoids the last (useless) doubling.
Conversion to a do..while loop may help, but most of my recent testing
shows very little difference between for, while and do..while loops in
modern browsers especially since the number of iterations will likely
never be more than about 50.

I originally use an array with push, but it was much slower in IE than
concatenating the string.

The method needs enough store for the result, plus 50% for the half-
result, plus up to about 53 recursions.

Which is why short-cutting the last doubling is very important.

 

[Dr J R Stockton]

In comp.lang.javascript message <b4f13742-aa0c-4de9-b846-9b5e58f8153a@c4
g2000hsg.googlegroups.com>, Mon, 4 Feb 2008 16:15:40, RobG

I decided as an exercise to write an iterative version to get a better
handle on bitwise operators - it took a while but finally the penny
dropped.

Testing in Firefox shows it's better than twice as fast as the
recursive method, in IE it's perhaps 50% faster - I'll test Opera and
Safari later.

Transferred to <js-misc0.htm#MLS> and adapted to fit test context. I
could not think of any Australian cats with 6-letter names, alas; so
close Wombat. In my XP sp2 IE6 it seems a little slower than my BigCat.

 

[lee.alan.burton]

In comp.lang.javascript message <abc29a16-e0f3-43ac-9db3-9b7573a19db0@s3
7g2000prg.googlegroups.com>, Thu, 31 Jan 2008 15:16:43, RobG
<[email protected]> posted:







Google : +JavaScript +"Making a Long String" finds
<URL:http://www.merlyn.demon.co.uk/js-misc0.htm#MLS>.

That shows that EvertJan used to know a short, fast method; and I a
faster - that is especially so for big repeats.

function BigCat(L) {
if (!L) return ""
if (L&1) return BigCat(L-1) + "x"
var T = BigCat(L>>1) ; return T + T }

function EjHCat(L) { return new Array(L+1).join('*') }

It's a good idea to read the newsgroup c.l.j and its FAQ. See below.

--
(c) John Stockton, nr London UK. [email protected] IE6 IE7 FF2 Op9 Sf3
FAQ <URL:http://www.jibbering.com/faq/index.html>.
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

And here is the modified version as a Javascript String prototype:

String.prototype.repeat = function(L) {
if (!L) return "";
if (L&1) return this + this.repeat(L-1);
var T = this.repeat(L>>1);
return T + T;
};

var s='Foo';
alert(s.repeat(6));