3 ms·
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 prac
by Ajedi32 6y ago
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.
- ghj 6y agoI 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://lannonbr.com/blog/2020-01-27-shift-optimizations https://jandemooij.nl/blog/2017/12/06/some-spidermonkey-optimizations-in-firefox-quantum/ https://jandemooij.nl/blog/2017/12/06/some-spidermonkey-opti... But it's very unlikely that the jit can optimize `str = ch + str;`
- cogman10 6y agoDepends 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; The above would probably get caught by the JIT and would essentially be optimized to what `ch.repeat(len) + str;` would do.
- layoutIfNeeded 6y agoString implemented as a linked list. You’re a webdev aren’t you?
- imtringued 6y agoWell, Haskell did it... https://stackoverflow.com/questions/13865420/why-is-haskells-default-string-implementation-a-linked-list-of-chars https://stackoverflow.com/questions/13865420/why-is-haskells...
- Domenic_S 6y agoHaskell's default String implementation is a linked list; no need for the snark