3 ms·
But could we create a hash table that would be truly constant-time? No. As the size of your data structure grows, it requires progressively slower memory. At a
by brudgers 17d ago
But could we create a hash table that would be truly constant-time? No. As the size of your data structure grows, it requires progressively slower memory.
At a large enough size to be interesting, everything is dominated by IO and because IO is slow, at any interesting size performance is a matter of tailoring the implementation to the details of the data {0}.
Engineering is hard work, not naive math.
[0] Data might be arbitrary but it is never random. Not being random is what makes it data.
- streetfighter64 16d ago> Data might be arbitrary but it is never random. Not being random is what makes it data. Counterexamples: crypto keys, stock price history, weather observations, radio telescope recordings
- marcta 15d agoI think the point is that once it becomes a crypto key, stock price, weather observation, whatever, the datum ceases to be random and becomes arbitrary.
- streetfighter64 10d agoThat is a nonsensical definition of random. If I roll a dice it's random, but if I write down the result it's not? Arbitrary is also quite different from random. Bad passwords are arbitrary, good passwords are random. If you ask a human to give an arbitrary number between 1 and 10, the answer will be 7 way more often than a random number between 1 and 10.
- d0mine 14d agoNote: weather observations being truly random data has been proved just recently (Navier-Stokes equations)