[umvi]

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)

[w0utert]

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).

[oddity]

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]

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

[chillee]

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.

[rocqua]

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.

[mijoharas]

I was about to say "the example in the post is sorting so it's n * log(n)".

Upon thinking about it, the example is comparing the relative speed of hashing every item (O(n) * O(1)) == O(n) and sorting (O(n * log(n)).

That means the ratio of these two is a log n factor n * log(n) / n == log(n).

good point.

As a side point, I think the main point of the post is that the time taken for the hash solution, increases at a greater rate than the sort + unique solution. Now, that doesn't make sense with our big 0 notation.

This is because we don't have a simple hashmap, what we have is a dynamically resizing hashmap, which we don't set a capacity on, and the resize operations are order n. Now, how often can we expect to resize? I think most hashmaps double their capacity, so there will be log(n) resize operations that each take O(m) (where m is the size of the hashmap when it needs to be resized).

Now at this point, I can't be bothered to think further about it. That feels like it should be less than O(n * log(n)), but it's kinda close. Either way, it's definitely larger than the simpler O(n) case we're thinking about.

[jlokier]

Dynamic resizing a hash table by doubling its size when it reaches a threshold capacity is amortised O(1) per insert.

If there are deletions, both operations are amortised O(1) provided they have been sensible and made the deletion threshold a lower factor.

It's the same sort of pattern as dynamically resizing a growing string. As long as you resize by a constant > 1 factor, rather than an addition, the number of resizes is low enough that the O(n) cost of copying is amortised over prior appends.

> Either way, it's definitely larger than the simpler O(n) case we're thinking about.

It actually isn't larger than O(n), setting aside constant factors.

For a hash map's time to grow more than O(n) for n insertions starting from empty, suggests an implementation problem.

[mijoharas]

I should have thought about things more. I think this is a case of confirmation bias on my part.

I thought "what about dynamically resizing" and quickly googled complexity of rehashing a hash which confirmed my thought that it was n.

I guess I didn't think that since we must have inserted n values in at this point, we could just say "insertion is O(1)" and the constant factor would be "performing two hashes" if we are going to a point where it's resizing, i.e. pay the cost of hashing once and rehashing once.

that feels like it makes sense. I'm being a bit hand-wavy as I don't want to sit down with pen and paper.

I retract my incorrect statement above. (I can no longer edit it to add postscript retraction.)

[corysama]

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.

[unlinked_dll]

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]

Eh, the optimization you talk about is basically how hash tables are implemented in languages like Ruby and Crystal.

[temac]

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)

[bjoli]

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.

[lorenzhs]

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]

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.

[kragen]

Oh man. And Fibonacci heaps are a nightmare to write.

[bjoli]

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

[Waterluvian]

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.

[alecco]

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