It Can Happen to You

#1

Post by mooreds » Thu, Mar 04, 2021, 12:37 AM UTC

Re: It Can Happen to You

#2

Post by rectang » Thu, Mar 04, 2021, 1:32 AM UTC

Pro tip: the classic recursive approach to implementing the Fibonacci sequence exhibits eye-wateringly poor performance.

Re: It Can Happen to You

#3

Post by jbluepolarbear » Thu, Mar 04, 2021, 1:42 AM UTC

This is really cool. I didn’t know about this until the GTA story came out. I wonder how many of many applications get this wrong.

Re: It Can Happen to You

#4

Post by jbluepolarbear » Thu, Mar 04, 2021, 1:43 AM UTC

rectang wrote: post #2

Pro tip: the classic recursive approach to implementing the Fibonacci sequence exhibits eye-wateringly poor performance.

Looped algorithms generally outperform recursive algorithms.

Re: It Can Happen to You

#5

Post by decasia » Thu, Mar 04, 2021, 1:43 AM UTC

It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation.

Absent that, of course we can potentially read the source code and find out, but I think for the most part we tend to operate based on an informed assumption about what we imagine the algorithmic complexity of a given operation would be. Inevitably, sometimes the assumption is incorrect.

There's no way to develop software without making assumptions, some of which inevitably turn out to be incorrect, so I don't think there is any great shame in having that happen, in itself. But better docs could help us make better assumptions with less effort, at least.

Re: It Can Happen to You

#6

Post by beaconstudios » Thu, Mar 04, 2021, 1:46 AM UTC

jbluepolarbear wrote: post #4

rectang wrote: post #2

Pro tip: the classic recursive approach to implementing the Fibonacci sequence exhibits eye-wateringly poor performance.

Looped algorithms generally outperform recursive algorithms.

does that hold for languages/compilers with tail call optimisation?

Re: It Can Happen to You

#7

Post by zachrip » Thu, Mar 04, 2021, 1:46 AM UTC

decasia wrote: post #5

It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation. Absent that, of course we can potentially read the source code and find out, but I think for the most part we tend to operate based on an informed assumption about what we imagine the algorithmic complexity of a given operation would be. Inevitably, sometimes the assumption i…

This is a cool idea..I'm sure it's been done before automatically in code, but I'd love to see this in my editor. It sounds similar to the bundle-size extension that you can use that will annotate how big a package that you're importing is in node.

Re: It Can Happen to You

#8

Post by jchw » Thu, Mar 04, 2021, 1:46 AM UTC

It is a good opportunity to mention that you should not use strtod/strtol either if you can help it, since they are impacted by locale. Exactly what to use instead is a bit of a tough nut to crack; you could extract musl’s floatscan code, or implement the Clinger algorithm yourself. Or, of course, use programming languages that have a more reasonable option in the standard library...

Re: It Can Happen to You

#9

Post by pid_0 » Thu, Mar 04, 2021, 1:46 AM UTC

8932hu09rueirhori3efw

Re: It Can Happen to You

#10

Post by tdeck » Thu, Mar 04, 2021, 1:46 AM UTC

This just makes me think that null-terminated strings are the bad gift that keeps on giving. If we were to design an OS, language, or standard library in 2021 (or even 1999) we probably wouldn't use them, but we're stuck with this relic of a former era.