4 ms·

O(1) hash vs O(N) array loop is a bit more complicated - for small N linear search can be faster - no need to compute a hash function, if data stored directly i

O(1) hash vs O(N) array loop is a bit more complicated - for small N linear search can be faster - no need to compute a hash function, if data stored directly in the array (instead of pointers) then there will be less CPU cache misses. Exact threshold can be determined in a benchmark but the key here here is that N should be bounded - if a user can manipulate N to be huge and you have O(N^2) somewhere in your code it is not only performance but also a potential security problem - a DoS vector. IMHO the key to not writing silly code is to have a good mental model of how your code works and how it fits into a bigger picture which includes OS, hardware, network and other services (like a DB). This model should be updated from time to time based on benchmarks and metrics from production services but once you have this knowledge it takes almost no additional time to apply this in practice and even if you'll be taking shortcuts to save development time you'll be better aware of this tradeoff.

magicalhippo 4y ago
Yeah I was thinking in a CRUD setting, where I live, where you won't be doing the operation too often. In that case the inefficiency for small N is a non-issue vs the pain of a O(N^2).
never_inline 4y ago
In this particular case, even if performance is not concern I would use the hash map. It just reads better.
- cratermoon 4y ago
  Interestingly, some of the folks who harp about performance would see your "reads better" as a problem. I'm completely in agreement with the idea that, until the code is proven to be a performance problem, readability and clarity matters most. But the performance-first mavens would say the choice should be determined by Big-O performance and memory usage, then by readability.
kevincox 4y ago
In my experience it is better to default to the lowest complexity algorithm. Even if linear search is faster for small N your app probably performs acceptably for small N either way. At some point being fast enough to be interactive is good enough and there isn't much point making your interactions take 2ms rather than 10ms. However n^2 algorithms will bite you. They may be outside of your everyday working set, and even dogfooding you may not have larger datasets than all of your users. At some point one user will hit a dimension that you "expected to always be small" and get bad performance. If one of these O(1)N algorithms ends up in the hot path you can always optimize it when profiling points it out. But O(N)N algorithms will leap off the cold path and become hot when some user starts using the "wrong" data patterns and the developers may never be aware, or at least not aware until it is too late.

magicalhippo 4y ago

Yeah I was thinking in a CRUD setting, where I live, where you won't be doing the operation too often. In that case the inefficiency for small N is a non-issue vs the pain of a O(N^2).

never_inline 4y ago

In this particular case, even if performance is not concern I would use the hash map. It just reads better.

cratermoon 4y ago
Interestingly, some of the folks who harp about performance would see your "reads better" as a problem. I'm completely in agreement with the idea that, until the code is proven to be a performance problem, readability and clarity matters most. But the performance-first mavens would say the choice should be determined by Big-O performance and memory usage, then by readability.

kevincox 4y ago

In my experience it is better to default to the lowest complexity algorithm. Even if linear search is faster for small N your app probably performs acceptably for small N either way. At some point being fast enough to be interactive is good enough and there isn't much point making your interactions take 2ms rather than 10ms. However n^2 algorithms will bite you. They may be outside of your everyday working set, and even dogfooding you may not have larger datasets than all of your users. At some point one user will hit a dimension that you "expected to always be small" and get bad performance. If one of these O(1)N algorithms ends up in the hot path you can always optimize it when profiling points it out. But O(N)N algorithms will leap off the cold path and become hot when some user starts using the "wrong" data patterns and the developers may never be aware, or at least not aware until it is too late.