As per MDN,
The
repeat()
method constructs and returns a new string which contains the specified number of copies of the string on which it was called, concatenated together.
Now one might think that there is a really straightforward to implement this. Yes there is but if asked in an interview and you go with the straightforward way, they will be like :-
How do I know this ?
Because I got mehhhhd......
So that's why we are going to see few approaches to solve it. The real optimized approach was not intuitive to me and is still something I am trying to wrap my head around. But I came up with a middle-ground approach that works better than the meh!! one.
And once, again we will take a synonym for repeat
.
Google time !!!!
replicate
sounds cool.
Alright let's go implement String.prototype.replicate
now :-
The Meh Approach
String.prototype.replicate = function(count) {
let input = this;
let result = "";
for (let index = 0; index < count; index++) {
result += input;
}
return result;
}
Meh explanation :-
We initialize result
to ""
and start a for
loop in which we iterate till count
and simply keep appending the input
to the result
variable. Very straightforward but meh!!.
Meh benchmark :-
100% slower with 108 operations per second compared to 9202566.4 operations per second. Let me cry in the corner.
The Little Less Meh Approach
String.prototype.replicate = function(count) {
let input = this;
let result = this.valueOf();
for (var index = 2; index < count; index*=2) {
result += result;
}
let remainingCount = count - index/2;
return remainingCount > 0 ? result + input.replicate(remainingCount) : result;
}
Little Less Meh explanation :-
- Let's consider the case of
'hey'.replicate(10)
:-- We have
input
initialized tothis
andresult
initialized tothis.valueOf()
. ThevalueOf()
bit helps in decreasing the implicit conversion time that's happening whenever laterresult
will be concatenated to itself. - Now the
for
loop stuff --
index
is intialized to2
. -
index
should be less thancount
-
index
should be multiplied each time by2
-
result
will be appended to itself each time in the iteration:--
result
forindex = 2
will becomeheyhey
-
result
forindex = 4
will becomeheyheyheyhey
-
result
forindex = 8
will becomeheyheyheyheyheyheyheyhey
-
index
will become16
which is greater than10
and we exit the loop.
-
-
remainingCount
will be10
-16/2
=2
; - When
remainingCount
will be greater than0
, we will recurse by callinginput.replicate(remainingCount)
and add its result to currentresult
or simply returnresult
.
-
- We have
Little Less Meh benchmark :-
76.79% slower with 2109699.5 operations per second compared to 9091332.85 operations per second. That's still relatively slower than the native one but way way way faster than what we had initially.
Earlier performing the repetitions itself was O(count) but now the same is somewhere down the line of O(log(x)+log(y) +....+log(k)) but not completely O(log(count)).
In 'hey'.replicate(10)
scenario :-
- First time, O(log(8)) work is done and then in next recursive step O(log(2)) i.e
O(log(8) + log(2))
. And if I am doing maths correct,
log(a) + log(b) = log(ab)
That means O(log(8) + log(2))
is O(log(16))
which is greater than O(log(10))
(the optimal solution).
The legendary optimal solution I would have never landed upon without the internet
String.prototype.replicate = function(count) {
let result = ''
let pattern = this.valueOf();
while (count > 0) {
if (count & 1)
result += pattern;
count >>= 1
if (count) pattern += pattern;
}
return result;
};
Noob explanation :-
I am still trying to understand the intuition behind this solution but I think it's to do with the fact that every number can be represented in a binary form. So let's say count
is 5 then it can be represented as 101
in binary. So it's possible for us to repeat the string count
times by just resorting to binary calculations. If we try to differentiate between 4 and 5, we know there is an extra 1 in latter case. Now instead of seeing the above code as some binary work of art, replace count&1 by count%2!==0 and count>>=1 by count=Math.floor(count/2). What this means is that, whenever count
is odd, we would want to save the pattern
till now in result
variable. What is pattern
? pattern
is repeated concatenation of itself similar to our earlier algorithm so it will always repeat in powers of 2. It's necessary to take care of the situation when count
is not divisible by 2 and store the current pattern
in result
as we go until count
becomes 0.
Did you expect a better explanation ? I can't give it right now since I am a noob in binary land. But maybe somewhere in a parallel universe I invented this Algo and helped Brendan Eich get rid of typeof null
-> object
๐คทโโ๏ธ.
Best benchmark yet :-
Still 29% slower ? WTH. But hey, I ain't competing with JavaScript engines here.
The Bonus MDN polyfill
String.prototype.replicate = function(count) {
var str = '' + this;
count = +count;
count = Math.floor(count);
if (str.length == 0 || count == 0)
return '';
var maxCount = str.length * count;
count = Math.floor(Math.log(count) / Math.log(2));
while (count) {
str += str;
count--;
}
str += str.substring(0, maxCount - str.length);
return str;
}
Expected an explanation ? I don't care and you will see why ๐
The mandatory benchmark :-
99.94 % slower with 5211.6 operations per second compared to 8344361.29 operations per second. And there is definite reason why it is even slower than what I came up with. What I think is happening is that upto a power of 2 which is less than count
, we use the same ideology as in the optimal solution for concatenating and doubling length of str
every time. But after that for the remaining length, it uses substring
and appends that to str
again. It's the second step of substring
which makes it a costly operation. Though it does better than the initial Meh solution of 108 ops/s, it's still no where near around the best optimal solution I found online or even mine ๐.
MDN : 0
Lakshya : 1
JK. The site is and hopefully remains a gold mine โค๏ธ.
Here are the overall benchmarks :-
Have something to add on ? Feel free to
Top comments (0)