4 ms·

That is why I specified "General Purpose". The moment you know something more about the data there might exist an opportunity to exploit that information to imp

That is why I specified "General Purpose". The moment you know something more about the data there might exist an opportunity to exploit that information to improve the algorithm. Which is an interesting topic in itself. Many times I have met people who said with absolute authority "no, it is not possible to implement this" only to be confronted with a counterexample. And that is because real life is rarely about spherical cows in vacuum. I have once implemented a transactional, log-based database for credit card terminal (20MHz ARM, 2MB total unified memory). The read (get value for key) operation was O(n^3) which the reviewers decided is "ABSOLUTELY FUCKING UNACCEPTABLE" (their words). The fun started when I asked them to suggest better implementation. They could not come up with anything even remotely as fast. And the basic reason was that n was guaranteed to be small as there wasn't even much space on the device for any more data. Other than that it exploited fantastic read ahead capability of the device plus it was so simple (basically couple nested loops) that CPU cache could be used very effectively. I remember their O(nlog(n)) was never faster and actually about 50 times slower in most operations.

bartvk 5y ago
Amazing story, thanks for sharing!
_ea1k 5y ago
I'm consistently amazed at how willing people are to make assumptions about optimizations with problems that don't fit their assumptions. Nice job.
- lmilcin 5y ago
  I think main reason is our flawed education. The tasks you are being given at school are usually constructed so that they fit the idealized knowledge you just learned. What it teaches people is to short cut the critical path of reasoning which is to first make sure you actually understand the problem and then the problem actually fits the assumptions. People are not taught that even a small divergence from assumptions can have dramatic difference on the actual solution or applicability of what they think is a solution. They are also not taught the actual assumptions or spot how they look. They talk about CS algorithms as if they worked on idealized computers, but then run them on real ones. At school this is not taught because when it seems the problem fits the material it almost always is. People are actually rewarded for jumping to conclusions as this helps them go through material faster. If you don't learn anything about the world you bring your learning with you and try to apply it to real world and that's how a lot of developers operate. Especially in tech, you can usually look up solution to any problem easily. But for some reason this is the part everybody emphasizes rather than recognize knowing when to apply the solution is way more valuable. I also think it is part of the wisdom behind "premature optimization is root of all evil".
  - _tom_ 5y ago
    What is wrong with Leetcode and similar, in a nutshell.
IgorPartola 5y ago
I once watched someone implement a heap in PHP in order to sort 4 domain names in order of priority and be able to resort them. The idea was I guess that at some point there may be 5 or even 6 of these and then we would really need the heap…

bartvk 5y ago

Amazing story, thanks for sharing!

_ea1k 5y ago

I'm consistently amazed at how willing people are to make assumptions about optimizations with problems that don't fit their assumptions. Nice job.

lmilcin 5y ago
I think main reason is our flawed education. The tasks you are being given at school are usually constructed so that they fit the idealized knowledge you just learned. What it teaches people is to short cut the critical path of reasoning which is to first make sure you actually understand the problem and then the problem actually fits the assumptions. People are not taught that even a small divergence from assumptions can have dramatic difference on the actual solution or applicability of what they think is a solution. They are also not taught the actual assumptions or spot how they look. They talk about CS algorithms as if they worked on idealized computers, but then run them on real ones. At school this is not taught because when it seems the problem fits the material it almost always is. People are actually rewarded for jumping to conclusions as this helps them go through material faster. If you don't learn anything about the world you bring your learning with you and try to apply it to real world and that's how a lot of developers operate. Especially in tech, you can usually look up solution to any problem easily. But for some reason this is the part everybody emphasizes rather than recognize knowing when to apply the solution is way more valuable. I also think it is part of the wisdom behind "premature optimization is root of all evil".
- _tom_ 5y ago
  What is wrong with Leetcode and similar, in a nutshell.

IgorPartola 5y ago

I once watched someone implement a heap in PHP in order to sort 4 domain names in order of priority and be able to resort them. The idea was I guess that at some point there may be 5 or even 6 of these and then we would really need the heap…