[HN Gopher] Algorithmic Complexity of Left-Pad (2016)
___________________________________________________________________
Algorithmic Complexity of Left-Pad (2016)
Author : pcr910303
Score : 54 points
Date : 2021-07-31 00:25 UTC (22 hours ago)
(HTM) web link (accidentallyquadratic.tumblr.com)
(TXT) w3m dump (accidentallyquadratic.tumblr.com)
| [deleted]
| throwanem wrote:
| An optimized implementation (as "padStart") is in the standard
| library now: https://developer.mozilla.org/en-
| US/docs/Web/JavaScript/Refe...
| pwdisswordfish8 wrote:
| The C-influenced nomenclature is not needed here. By the nature
| of what you're referring to, it is not a library. "In the
| standard" will do.
| bqa65 wrote:
| Er, C did not invent libraries by any measure whatsoever, and
| is completely appropriate to call a function available to
| code without imports "in the standard library". It is a
| library function. You did not write it. Simple as that.
|
| This is one of the more unnecessary pedantries I've ever
| seen, and that's saying something on HN.
| skrtskrt wrote:
| I always assumed just from how people used the terms that
| available without imports = "core language" and available
| via import without installing external packages = "standard
| library"
| throwanem wrote:
| That may indeed be a more useful distinction to draw
| here. In it, Node could be said to provide a "standard
| library" (although not actually standardized, and I'm not
| sure how much it overlaps with eg Deno), while padStart
| and such would be core language features inasmuch as a
| compliant JS implementation is guaranteed to include
| them.
|
| _edit:_ It is not, however, an _accurate_ distinction.
| https://news.ycombinator.com/item?id=28021135
| wk_end wrote:
| FWIW my intuition is that any functions, classes,
| constants, whatever - things that I could write myself if
| I had to - are "standard library". "Core language" refers
| to syntactic or semantic features of the language that
| would require modifying the compiler or interpreter to
| introduce.
| mbrubeck wrote:
| Okay, let's see what "the standard" has to say...
|
| "Clauses 18 through 28 define the ECMAScript standard
| library."
|
| --ECMA-262, 12th edition, June 2021, _ECMAScript(r) 2021
| Language Specification_ , SS4.5
| [deleted]
| venzlombardo wrote:
| This post is off-topic as this is Covid News, not Hacker News.
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
|
| covid covid covid covid covid covid
| kccqzy wrote:
| The fact that the Safari result appears to have two linear fits
| doesn't surprise me at all. Apple has a history of implementing
| multiple concrete classes for different sizes for the same
| abstract class. It has been known that NSArray and CFArray will
| switch the underlying data structure once it grows past a certain
| size: https://ridiculousfish.com/blog/posts/array.html Now I'm
| not saying this NSArray trick was what happened here: it clearly
| is not because otherwise we'd see a quadratic curve followed by a
| linear curve. I'm just saying the data structure seems to have
| changed at a certain size cutoff.
| brundolf wrote:
| > But the principle remains, that it was actually completely
| impossible for us to analyze left-pad's performance without a
| deep understanding of the specific underlying Javascript VM we
| cared about (or, in my case, resorting to brute experiment!).
|
| And this is why we benchmark before optimizing
| iamcreasy wrote:
| I am wondering if the graph that shows Safari performance is
| actually quadratic. I am referring to the the 2nd linear segment.
|
| On that graph, 400,000 length required 2500 in time. If it's
| quadratic, 800,000 would require 10,000 in time. If you imagine
| the plot goes all the way to 800,000 - it's not hard to see that
| the line/curve hitting at 10,000.
|
| Thoughts?
| keville wrote:
| (Circa 2016)
| jwlake wrote:
| where to i submit the issue to have it reposted to substack?
| jonathrg wrote:
| It had been optimized (and deprecated) since then. See
| https://github.com/left-pad/left-pad/blob/master/index.js
| [deleted]
___________________________________________________________________
(page generated 2021-07-31 23:01 UTC)