I'd say hashes aren't going to make everything faster, but they will always be faster than disk lookup. But more to the point that I understand you to be making - hashes are excellent when you have large amounts of _repeated_ calculations.
For instance, counting word occurrences in a large body of text. Rather than run through the body N times for N words, you run through it only once and increment a word's tally every time you come across an occurrence.
Do you mean that a cpu-bound process could improve on this?
To be fair, he refers to the strength of lookup time in the quote you cite, which is not exactly the property that improves the algorithm I just mentioned (which is that the use of a hash completely restructures the algorithm). I'm curious to know more about situations in which you find writing cpu bound code to work better. Including - what sort of N are you dealing with when you make this choice?
I can imagine that generating HTML on the fly is a simple enough computation to outweigh the benefits of caching every possible view - which is to say, the N of each rendering is small enough not to be truly cpu bound. But even then, that ignores the fact that we'd be reading from disk anyway, and so I don't see how that's worse than paging.
These are my thoughts. Not gotchas. I just want to know what I'm missing.
O(N) brute force algorithms (almost) never beat hashing. O(log(N)) tree-based algorithms sometimes do, because it’s easier to get good data locality out of them when the queries have some temporal relation.
I'd say hashes aren't going to make everything faster, but they will always be faster than disk lookup. But more to the point that I understand you to be making - hashes are excellent when you have large amounts of _repeated_ calculations.
For instance, counting word occurrences in a large body of text. Rather than run through the body N times for N words, you run through it only once and increment a word's tally every time you come across an occurrence.
Do you mean that a cpu-bound process could improve on this?
To be fair, he refers to the strength of lookup time in the quote you cite, which is not exactly the property that improves the algorithm I just mentioned (which is that the use of a hash completely restructures the algorithm). I'm curious to know more about situations in which you find writing cpu bound code to work better. Including - what sort of N are you dealing with when you make this choice?
I can imagine that generating HTML on the fly is a simple enough computation to outweigh the benefits of caching every possible view - which is to say, the N of each rendering is small enough not to be truly cpu bound. But even then, that ignores the fact that we'd be reading from disk anyway, and so I don't see how that's worse than paging.
These are my thoughts. Not gotchas. I just want to know what I'm missing.