5 ms·

I've seen this before, where big-O obsessed co-workers love to make every algorithm and task O(1) by using hash maps, etc. but are then flabbergasted when "infe

by umvi 7y ago

I've seen this before, where big-O obsessed co-workers love to make every algorithm and task O(1) by using hash maps, etc. but are then flabbergasted when "inferior" O(n) code written by someone else outperforms their theoretical perfection by a long shot. I have to remind them that O(1) is just a rule of thumb for scaling and that technically a dictionary lookup + sleep(5) is still O(1)

oddity 7y ago
Big-O is a way to talk about scaling, but in general, the average CS program does a disservice by not talking more about the critical question: "of what?" Bright students will connect their algorithm course with their systems course and recognize that, maybe, ALU ops aren't a very useful measure in a real world context. Interested students may take a rigorous complexity theory class that will get into various computation models and their nuanced interaction with time/space/communication complexity. However, enough students seem to go through a CS program without learning this that I'm convinced this is a failing of the curriculum and not the students.
- agumonkey 7y ago
  the theoretical aspect is too "emphased", they really forget to root it in practical situations
Waterluvian 7y ago
I run into this case all the time with my React apps that handle huge amounts of mapping data. You know what's beautiful? Just keep it simple, measure it, and add the extra complexity (eg. Array to dict memoized selectors) where performance is actually an issue. I'm not saying all cases can be deferred until later. Sometimes you really need to address it up front. But I think most can be refactored later.
chillee 7y ago
I understand the sentiment, but O(n) vs O(1) and O(n^2) vs O(n log n) are huge jumps in complexity. Even with relatively small sizes like N=100, you're already starting with 2 orders of magnitude disadvantage. The example in this post is a log N factor. log N is a relatively small growth, you'd need 1000 elements to get 1 order of magnitude and you'll never run into 2 orders of magnitude. If you can come up with reasonable code where an order N complexity slower algorithm is faster in practice - I'd love to see it.
- unlinked_dll 7y ago
  Spitballing here, but I’d suspect a “hash table” implemented as a vector of tuples of key/value pairs with linear time search for the keys would outperform a canonical hashtable for simple JRPC APIs where the vast majority of your JSON objects have fewer than a dozen elements. Would be interesting to build a hashtable with an equivalent “small string optimization” approach where you have a fixed sized array that is replaced by a canonical hashtable once it grows past some threshold.
  - yxhuvud 7y ago
    Eh, the optimization you talk about is basically how hash tables are implemented in languages like Ruby and Crystal.
- corysama 7y ago
  Sure. But, in practice it’s never a debate between O(1) vs. a O(large n). It’s always either a heavy O(1) vs. a light O(small n) —-hash vs. linear search. Or, a heavy O(large n) vs. a light O(large n log n) —-hash everything vs. sort everything. In both cases, the second option usually wins.
- temac 7y ago
  It's not only about the constant factor, but also about the fact that O is only valid toward infinity, and potentially about how computer actually work (e.g. the extreme discrepancy between the latency of L1 vs RAM)
- rocqua 7y ago
  The issue here is mostly about what you are counting. Almost all instances I've seen of big O scaling not being realistic count every memory access as 1 operation. In reality, memory accesses have a huge variation in how much time they take. Moreover, this does have a dependence on the program. This is of course due to caches. As such, an O(n^2) algorithm that has very local memory accesses can actually beat an O(n) algorithm that spreads out its memory accesses randomly over the entire memory space. It has come to the point where I care more about the expected cache hits of an algorithm than the big O scaling.
bjoli 7y ago
I have met many that are generally bad at comparing constant factors and even worse at understanding what computers are fast at. At school I had a friend implement a Fibonacci heap (which is O(1) or amortized O(1) in every step) for a simple thing and didn't bother to benchmark it against a simple vector based binary heap. It was slower by one order or magnitude. Only twice have I had to use something else than a simple binary heap due to cache issues.
- kragen 7y ago
  Oh man. And Fibonacci heaps are a nightmare to write.
  - bjoli 7y ago
    Iirc he got an A for effort in exchange for the teacher using it as an example of speed in terms of asymptotic complexity Vs actual speed
- lorenzhs 7y ago
  Small correction: a Fibonacci heap has O(log n) amortised delete-min, otherwise you'd break the lower bound on comparison-based sorting (roughly: insert all elements, then delete the minimum n times, et voilà, you've sorted the input based solely on pairwise comparisons, therefore either insert or delete-min or both must take (amortised) logarithmic time). But yeah, they're one of the classical examples of "faster on paper, slower in practice" algorithms. Just use a binary (or d-ary) heap.
  - OskarS 7y ago
    I think of Fibonacci heaps as essentially just a academic exercise to lower the big-O complexity of Dijkstra's algorithm with very little actual practical use. It always seemed tailor made for that. Like, Fibonacci heaps guarantee an amortized O(1) "decrease key" operation, which is a stupendously obscure priority queue operation. Except, of course, in Dijkstra's algorithm, where the lowest runtime complexity bounds depends on it.
deleted 7y ago
[deleted]
w0utert 7y ago
Using hashmaps by default isn't usually about raw performance for some small N, but to ensure your algorithm doesn't blow up if someone decides to take it out of context some day and dramatically increases the N (this is especially fun if it is called from some loop that also scales with input size in some way or another, which is very common). Yes you trade some raw performance for small N, but very rarely this is relevant or even measurable, and you get scalability in return. Now what this article is showing is something else, which is that contrary to the claims in the spec, the benchmarked std::unordered_map implementation does not actually have amortized O(1) insertion time and that you can beat it with an O(N log N) sort if you want to deduplicate integers, for any input size. Which is interesting, but very specific, and not an observation that would carry over to other algorithms (or data types, for that matter. For example, it would be interesting to see what the graph would look like for types that have a more complicated/expensive way to calculate which one of two values is smaller).
alecco 7y ago
And never mind the problems of resizing and deletion. And each type of hashing has it's drawbacks.

by umvi 7y ago

oddity 7y ago

Big-O is a way to talk about scaling, but in general, the average CS program does a disservice by not talking more about the critical question: "of what?" Bright students will connect their algorithm course with their systems course and recognize that, maybe, ALU ops aren't a very useful measure in a real world context. Interested students may take a rigorous complexity theory class that will get into various computation models and their nuanced interaction with time/space/communication complexity. However, enough students seem to go through a CS program without learning this that I'm convinced this is a failing of the curriculum and not the students.

agumonkey 7y ago
the theoretical aspect is too "emphased", they really forget to root it in practical situations

Waterluvian 7y ago

I run into this case all the time with my React apps that handle huge amounts of mapping data. You know what's beautiful? Just keep it simple, measure it, and add the extra complexity (eg. Array to dict memoized selectors) where performance is actually an issue. I'm not saying all cases can be deferred until later. Sometimes you really need to address it up front. But I think most can be refactored later.

chillee 7y ago

I understand the sentiment, but O(n) vs O(1) and O(n^2) vs O(n log n) are huge jumps in complexity. Even with relatively small sizes like N=100, you're already starting with 2 orders of magnitude disadvantage. The example in this post is a log N factor. log N is a relatively small growth, you'd need 1000 elements to get 1 order of magnitude and you'll never run into 2 orders of magnitude. If you can come up with reasonable code where an order N complexity slower algorithm is faster in practice - I'd love to see it.

unlinked_dll 7y ago
Spitballing here, but I’d suspect a “hash table” implemented as a vector of tuples of key/value pairs with linear time search for the keys would outperform a canonical hashtable for simple JRPC APIs where the vast majority of your JSON objects have fewer than a dozen elements. Would be interesting to build a hashtable with an equivalent “small string optimization” approach where you have a fixed sized array that is replaced by a canonical hashtable once it grows past some threshold.
- yxhuvud 7y ago
  Eh, the optimization you talk about is basically how hash tables are implemented in languages like Ruby and Crystal.
corysama 7y ago
Sure. But, in practice it’s never a debate between O(1) vs. a O(large n). It’s always either a heavy O(1) vs. a light O(small n) —-hash vs. linear search. Or, a heavy O(large n) vs. a light O(large n log n) —-hash everything vs. sort everything. In both cases, the second option usually wins.
temac 7y ago
It's not only about the constant factor, but also about the fact that O is only valid toward infinity, and potentially about how computer actually work (e.g. the extreme discrepancy between the latency of L1 vs RAM)
rocqua 7y ago
The issue here is mostly about what you are counting. Almost all instances I've seen of big O scaling not being realistic count every memory access as 1 operation. In reality, memory accesses have a huge variation in how much time they take. Moreover, this does have a dependence on the program. This is of course due to caches. As such, an O(n^2) algorithm that has very local memory accesses can actually beat an O(n) algorithm that spreads out its memory accesses randomly over the entire memory space. It has come to the point where I care more about the expected cache hits of an algorithm than the big O scaling.

bjoli 7y ago

I have met many that are generally bad at comparing constant factors and even worse at understanding what computers are fast at. At school I had a friend implement a Fibonacci heap (which is O(1) or amortized O(1) in every step) for a simple thing and didn't bother to benchmark it against a simple vector based binary heap. It was slower by one order or magnitude. Only twice have I had to use something else than a simple binary heap due to cache issues.

kragen 7y ago
Oh man. And Fibonacci heaps are a nightmare to write.
- bjoli 7y ago
  Iirc he got an A for effort in exchange for the teacher using it as an example of speed in terms of asymptotic complexity Vs actual speed
lorenzhs 7y ago
Small correction: a Fibonacci heap has O(log n) amortised delete-min, otherwise you'd break the lower bound on comparison-based sorting (roughly: insert all elements, then delete the minimum n times, et voilà, you've sorted the input based solely on pairwise comparisons, therefore either insert or delete-min or both must take (amortised) logarithmic time). But yeah, they're one of the classical examples of "faster on paper, slower in practice" algorithms. Just use a binary (or d-ary) heap.
- OskarS 7y ago
  I think of Fibonacci heaps as essentially just a academic exercise to lower the big-O complexity of Dijkstra's algorithm with very little actual practical use. It always seemed tailor made for that. Like, Fibonacci heaps guarantee an amortized O(1) "decrease key" operation, which is a stupendously obscure priority queue operation. Except, of course, in Dijkstra's algorithm, where the lowest runtime complexity bounds depends on it.

deleted 7y ago

[deleted]

w0utert 7y ago

Using hashmaps by default isn't usually about raw performance for some small N, but to ensure your algorithm doesn't blow up if someone decides to take it out of context some day and dramatically increases the N (this is especially fun if it is called from some loop that also scales with input size in some way or another, which is very common). Yes you trade some raw performance for small N, but very rarely this is relevant or even measurable, and you get scalability in return. Now what this article is showing is something else, which is that contrary to the claims in the spec, the benchmarked std::unordered_map implementation does not actually have amortized O(1) insertion time and that you can beat it with an O(N log N) sort if you want to deduplicate integers, for any input size. Which is interesting, but very specific, and not an observation that would carry over to other algorithms (or data types, for that matter. For example, it would be interesting to see what the graph would look like for types that have a more complicated/expensive way to calculate which one of two values is smaller).

alecco 7y ago

And never mind the problems of resizing and deletion. And each type of hashing has it's drawbacks.