71–80 of 108 posts
Earlier quoted context omitted.
Is this blog post a dig on Rich Hickey's talk 'Simple Made Easy'?
Just speaking for myself, it seemed like a pretty good-natured mix of thoughtful musing on the nature of universal computation, and gentle mockery of the idea that universal computation means there's one right answer for anything. I'd be surprised if it's meant to skewer any one viewpoint in particular.
Earlier quoted context omitted.
>Maybe, once you've found a location to read, insert, or write to. The author neglects the runtime cost required for the hash algorithm itself, which may not be trivial; computing the hash of a string key is typically an O(n) operation. Yeah, I know, it always came off to me as BS to repeat that hashes are O(1) lookup, like we're making a special exception. Anywhere else, you can look up the algorithm and derive its…
This is mostly an issue with terms. Most (all?) of the operations we call constant-time, say, comparison, are technically logarithmic in the number of bits on real computers. Since that's usually not relevant to big-O analysis, we can sidestep the issue by specifying what we're counting: rather than say that mergesort is in O((log n) log (log n)) time, we say it takes O(n log n) comparisons. Whether you think of that…
But for hashtables, what exactly are we studying that doesn't care about hash time? The whole reason that a hashtable is supposed to save time is that you locate the desired key's value by computing the location from the key itself. To whatever extent that computation requires more steps, that cannot itself be abstract away -- if only because a limitation on key size is a limitation on table size.
This had me worried: "God-given axioms, which is academic lingo for a truth we accept purely by our God-given logic, like: if something is not true then it is false, something cannot exist in an empty set, something logical is logical." But then I saw this and started laughing: "Remember when everyone used tables to lay out their HTML? Well, that proved to be a horrible way to do things, because tables are inherently…
Why did the axioms bit have you worried? OP is pretty much exactly right, except for the part where we accept it by our "logic". Axioms are simply true, end of story; logic does not apply to axioms themselves, only how they can be used in relation to other axioms.
Many axioms maybe picked because they seem 'obviously true', (or more likely, because they are useful) but that doesn't make their truth simple or make them the result of logic. (For an example take a look at the existence of infinity).
Additionally, the 'axioms' he lists are all what I would generally consider tautologies. (Although you might argue that the first one is actually an axiom of bivalent logic systems).
"Hashes are always O(1) reads, inserts and writes." Maybe, once you've found a location to read, insert, or write to. The author neglects the runtime cost required for the hash algorithm itself, which may not be trivial; computing the hash of a string key is typically an O(n) operation. Furthermore, unless a suitable table size is selected, integer keys (should one use a map like an array) will eventually hash to the…
It's even tagged "bad-theory." I think it's pretty clearly a joke! A really good one!
"Hashes are always O(1) reads, inserts and writes." Maybe, once you've found a location to read, insert, or write to. The author neglects the runtime cost required for the hash algorithm itself, which may not be trivial; computing the hash of a string key is typically an O(n) operation. Furthermore, unless a suitable table size is selected, integer keys (should one use a map like an array) will eventually hash to the…
Consider that the universe enforces both a maximum information density per cubic meter, and a maximum speed at accessing a given physical location.
Earlier quoted context omitted.
It's even tagged "bad-theory." I think it's pretty clearly a joke! A really good one!
I think I came around to that realization when he starts comparing Postgres to HTML tables.
ok, the last paragraphs kind of give it away... but there are good points in terms of keeping the data flat
"Hashes are always O(1) reads, inserts and writes." Maybe, once you've found a location to read, insert, or write to. The author neglects the runtime cost required for the hash algorithm itself, which may not be trivial; computing the hash of a string key is typically an O(n) operation. Furthermore, unless a suitable table size is selected, integer keys (should one use a map like an array) will eventually hash to the…
Earlier quoted context omitted.
I don't know why the complexity estimates I find for Hashes are always so bad. They never account for growth (or depending on the implementation shrinking on delete), never account for the hash function, etc. By the time you hash a key, you could have likely already inserted it into a trie. Lookups on hashes are also not O(1) for similar reasons. You have to hash the search string, then compare the value at whatever…
When you say O(something), the something has a unit. Hash table lookups and insertions take time O(1), when talking about number of items already in the hash table - and that 'when talking about' is implicit and doesn't have to be said as anyone talking about the complexity of a hash table knows that, or would state otherwise as it would be an exception. Talking about the length of strings used as keys in the hash ta…
I'm fairly positive that a unit of measure should _never_ be variable, otherwise it's fairly pointless. And if you don't think hashing a 1TB string takes significantly longer than a 100byte string ...
Futher more, big O notation is supposed to be a wide upper bound, but I don't think that works well if it's not actually an upper bound. If you were to tell your bosses something took constant time, and it took an hour for string A (1TB) and 100ms for string B (10B), I'm pretty sure your opinion wouldn't mean much after that.
The hashmap should absolutely be considered in terms of the hash function, because it's the longest running part of the algorighthm. To do otherwise is disingenous.
Using that logic, I could call any iterative algorithm O(1) since the top level function only gets called once.
Earlier quoted context omitted.
I don't know why the complexity estimates I find for Hashes are always so bad. They never account for growth (or depending on the implementation shrinking on delete), never account for the hash function, etc. By the time you hash a key, you could have likely already inserted it into a trie. Lookups on hashes are also not O(1) for similar reasons. You have to hash the search string, then compare the value at whatever…
When you say O(something), the something has a unit. Hash table lookups and insertions take time O(1), when talking about number of items already in the hash table - and that 'when talking about' is implicit and doesn't have to be said as anyone talking about the complexity of a hash table knows that, or would state otherwise as it would be an exception. Talking about the length of strings used as keys in the hash ta…
However, this is absolutely dominated by complexity of the hashing function, growth (which can be amortized, but is not O(1)) deletion (also not O(1)) and comparison functions (which are usually O(mn) or O(n) (or some similar depending)).
We end up measuring the things that are the most minimal in hashing and pretending like the expensive operations, which aren't O(1), don't exist. This is wrong and dishonest when considering algorithms. We know for example that string comparison is not O(1), and it's usually a part of most hash table algorithms, and yet it magically disappears when analyzing hash table complexity and everything is somehow supposed to be considered as a mem+offset which is stupid.
Hash-tables also usually have exponential memory growth complexity which nobody ever pays attention to. Of course there are versions which don't do this and/or have fixed memory sizes, but the random kind you find in most languages grow O(n^2) or similar. And this is also ignored and we pretend it doesn't happen and resizing magically becomes part of the "1" in O(1)....even though copying arrays isn't free and as resizes happen arrays get bigger and big-O should get worse.
Hash-table operations can be pretty expensive and faulty big-O analysis doesn't help. So sure, for a static, fixed size, hash table, with no growth, instantaneous hash functions that use temporal oracles, don't need to deal with collisions, O(1) is correct. But these hash functions pretty much don't exit in nature, and most programmers won't be working with them. The standard libraries for most languages sure as hell don't implement such ideal hash tables.
O(n) is at least an honest approximation. I honestly have never seen a well considered analysis of hash function complexity but I know it grows super-linearly from just using them a lot. This kind of fanciful analysis doesn't help anybody.
So yes, O(something) where something has a unit. But the unit sure as heck isn't whatever "1" is supposed to represent. It's probably closer to string length or array length (or some combination of the two), but a single "add" it is most definitely not.