Re:Never use a dependency that you could replace with an aft...
by Ajedi32 on Tuesday August 11, 2020 @05:24PM
(#24126154)
That would depend on the underlying implementation of the string object, no? (If the string is implemented as a linked list it's O(n))
Anyway, it makes no practical difference in this case, since the one they labeled "O(n)" is the naive implementation that most people would write if they implemented left-pad themselves.
Re:Never use a dependency that you could replace with an aft...
by ghj on Tuesday August 11, 2020 @05:28PM
(#24126183)
I highly doubt js engines would compile a string down to a linked list. But you're right they might compile it to a circular buffer or deque which can have O(1) prepends.
Quick googling shows that this optimization might exist but only for firefox and only if you use "unshift": https://lannonbr.com/blog/2020-01-27-shift-optimizations https://jandemooij.nl/blog/2017/12/06/some-spidermonkey-opti...
But it's very unlikely that the jit can optimize `str = ch + str;`
Re:Never use a dependency that you could replace with an aft...
by cogman10 on Tuesday August 11, 2020 @07:00PM
(#24126956)
Depends on the form that `str = ch + str` takes inside the loop. But yeah, the way they wrote the code makes it less likely to work well.
let padding = '';
for (let i = 0; i < len; ++i)
padding += ch;
return padding + str;
Re:Never use a dependency that you could replace with an aft...
by layoutIfNeeded on Tuesday August 11, 2020 @05:46PM
(#24126406)
String implemented as a linked list.
You’re a webdev aren’t you?
Re:Never use a dependency that you could replace with an aft...
by imtringued on Wednesday August 12, 2020 @06:24AM
(#24130377)
Well, Haskell did it...
https://stackoverflow.com/questions/13865420/why-is-haskells...
https://github.com/left-pad/left-pad/blob/master/perf/O(n).j...
They are repeatedly appending a single character to the front of a string. This is actually O(n^2) so of course they are winning against it.