2 ms·

> There's no moral to the story, other than "xor is cool" The moral is knowledge is king and no matter how much iron you throw at a problem a well-designed alg

> There's no moral to the story, other than "xor is cool" The moral is knowledge is king and no matter how much iron you throw at a problem a well-designed algorithm will beat it.

mangamadaiyan 4y ago
Cache misses, TLB flushes, and pipeline stalls would beg to differ with you.
- MaxBarraclough 4y ago
  Not really, no. For plenty of problems, the most efficient known algorithms will easily outperform a naive algorithm, even if running on drastically inferior hardware. 'Drastically' in this context can mean the slower approach taking billions of times longer. Wikipedia gives an example. [0] Many courses on algorithms and/or complexity theory emphasise such examples in their introductions. That said I don't know why jhoechtl thought that was the moral of this blog post, which doesn't illustrate that point at all. [0] https://en.wikipedia.org/wiki/Computational_complexity#Use_in_algorithm_design https://en.wikipedia.org/wiki/Computational_complexity#Use_i...
  - CRConrad 4y ago
    > 'Drastically' in this context can mean the slower approach taking billions of times longer. Standupmaths - "Someone improved my code by 40,832,277,770%": https://www.youtube.com/watch?v=c33AZBnRHks https://www.youtube.com/watch?v=c33AZBnRHks (OK, 41 billion percent is only 0.41 billion times better, but still.)
  - mangamadaiyan 4y ago
    Mea culpa. All I was trying to say is that beyond a point, it's not _just_ the algorithm, you need to pay attention to mechanical sympathy. Do well-designed algorithms outperform naive algorithms? Almost always. Is designing the algorithm well sufficient? I'd think not.
deathanatos 4y ago
…a simple histogram (the second proposed solution in TFA) runs "instantly", for both parts. Part of the meta-game to AoC is knowing that you can limit your answer to only the requirements in the combination of the question and input given. If the naive solution runs fast enough, and is vastly quicker to implement, that's the one you want.

> There's no moral to the story, other than "xor is cool" The moral is knowledge is king and no matter how much iron you throw at a problem a well-designed algorithm will beat it.

mangamadaiyan 4y ago

Cache misses, TLB flushes, and pipeline stalls would beg to differ with you.

MaxBarraclough 4y ago
Not really, no. For plenty of problems, the most efficient known algorithms will easily outperform a naive algorithm, even if running on drastically inferior hardware. 'Drastically' in this context can mean the slower approach taking billions of times longer. Wikipedia gives an example. [0] Many courses on algorithms and/or complexity theory emphasise such examples in their introductions. That said I don't know why jhoechtl thought that was the moral of this blog post, which doesn't illustrate that point at all. [0] https://en.wikipedia.org/wiki/Computational_complexity#Use_in_algorithm_design https://en.wikipedia.org/wiki/Computational_complexity#Use_i...
- CRConrad 4y ago
  > 'Drastically' in this context can mean the slower approach taking billions of times longer. Standupmaths - "Someone improved my code by 40,832,277,770%": https://www.youtube.com/watch?v=c33AZBnRHks https://www.youtube.com/watch?v=c33AZBnRHks (OK, 41 billion percent is only 0.41 billion times better, but still.)
- mangamadaiyan 4y ago
  Mea culpa. All I was trying to say is that beyond a point, it's not _just_ the algorithm, you need to pay attention to mechanical sympathy. Do well-designed algorithms outperform naive algorithms? Almost always. Is designing the algorithm well sufficient? I'd think not.

deathanatos 4y ago

…a simple histogram (the second proposed solution in TFA) runs "instantly", for both parts. Part of the meta-game to AoC is knowing that you can limit your answer to only the requirements in the combination of the question and input given. If the naive solution runs fast enough, and is vastly quicker to implement, that's the one you want.