undefined | Better HN

0 pointsthaumasiotes2y ago0 comments

> Failing to even get the O(n log n) solution tells me that someone should never have graduated.

This is something I wonder about in my comment sidethread - to me, the natural solution is the O(n) one in O(n) space.

I see that the O(n log n) solution requires O(1) space to run. But it requires O(n) space to return a result! Is that actually better than O(n) time and O(n) space?

0 comments

xoranth2y ago

With the sorting solution, you can stream the result directly to a file _without_ holding the entire file in memory. So it can be better if you are memory constrained (e.g. if the files are bigger than what you can hold in memory), or if you want to hold the working set inside the CPU L3 cache as 'cperciva is alluding to.

cperciva2y ago

Either of those solutions is ok from a junior developer.

From a senior developer, I would expect a discussion of in-core vs. out-of-core operations, and the fact that hash tables (even if they fit into RAM) aren't really O(1) time per operation since random access to large address spaces runs into e.g. TLB misses.

xoranth2y ago

Given that the depth of the page table tree is fixed at 3/4/5 depending on the architecture and kernel, I think most people would be confused if asked whether the average complexity of a hash table lookup is always really O(1).

Even senior developers that understand the TLB would likely think of it as "O(1), but with a big constant factor".

On a side note, one thing that the article doesn't mention is the possibility of using a Bloom filter. It trades an extra scan of a file for smaller hash tables/smaller set to sort with external sort.

hughesjj2y ago

Yup, was surprised bloom filters weren't even mentioned in passing. I suck but still it's crazy to see some people genuinely would have a problem getting the O(n) solution when they've been in the industry for more than 5-10 years

seadan832y ago

O(1) = c * O(1) = c * O(n^0)

Whether you get a cache miss or hit is part of 'c', or whether those bytes are fetched over WAN. Big oh of one just means lookup time is a constant and is independent of data size. The big oh doesn't change if move from a SSD to a tape drive

Thus, those operations are really O(1)

Big oh is the infimum function such that for an arbitrarily large N, the runtime of the algorithm is then strictly larger than C times the big oh function. (Paraphrasing there a bit, and on a phone, apologies for not pasting the exact definition)

cperciva2y ago

In a formal sense, anything you can compute on a computer is O(1) since there's only a finite number of states. But we tend to hand-wave that away.

Hash table lookup is absolutely bounded by a constant, but going from L1 to L2 to L3 to RAM with anywhere between 0 and 5 TLB misses is far from constant.

2 more replies

8note2y ago

I'd expect talking about TLB misses as a junior engineer thing. That's stuff you learn in school.

Id expect senior engineers to talk about how they will monitor this system, and to bring up things like customers we know we don't trust.

A senior engineer might tell you that running into TLB issues makes a suggestion that your approach is wrong and it's about time to move the solution to your data warehouse

j / k navigate · click thread line to collapse

0 comments

xoranth2y ago

cperciva2y ago

Either of those solutions is ok from a junior developer.

xoranth2y ago

Even senior developers that understand the TLB would likely think of it as "O(1), but with a big constant factor".

hughesjj2y ago

seadan832y ago

O(1) = c * O(1) = c * O(n^0)

Thus, those operations are really O(1)

cperciva2y ago

In a formal sense, anything you can compute on a computer is O(1) since there's only a finite number of states. But we tend to hand-wave that away.

Hash table lookup is absolutely bounded by a constant, but going from L1 to L2 to L3 to RAM with anywhere between 0 and 5 TLB misses is far from constant.

2 more replies

8note2y ago

I'd expect talking about TLB misses as a junior engineer thing. That's stuff you learn in school.

Id expect senior engineers to talk about how they will monitor this system, and to bring up things like customers we know we don't trust.

A senior engineer might tell you that running into TLB issues makes a suggestion that your approach is wrong and it's about time to move the solution to your data warehouse

j / k navigate · click thread line to collapse