7 ms·
What do you mean? Modulo is not a perfect hash function... What if your hash table had size 11 and you hash two keys of 22 and 33? I also don't understand your
by b52_ 1y ago
What do you mean? Modulo is not a perfect hash function... What if your hash table had size 11 and you hash two keys of 22 and 33?
I also don't understand your first point. We can run n^2 algorithms on massive inputs given its just a polynomial. Are you thinking of 2^n perhaps?
- LPisGood 1y agon^2 algorithms on _massive_ inputs seems a little far fetched, no? Around one to one hundred billion things start getting difficult.
- vlovich123 1y agoThe challenge with big-O is you don’t know how many elements results in what kind of processing time because you don’t have a baseline of performance on 1 element. So if processing 1 element takes 10 seconds, then 10 elements would take 16 minutes. In practice, n^2 sees surprising slowdowns way before that, in the 10k-100k range you could be spending minutes of processing time (10ms for an element would only need ~77 elements to take 1 minute).
- b52_ 1y agoI'd argue that one billion is fairly large for what most people work on. But yes, point taken.
- Panzer04 1y agon^2 is probably the worst offender of these algorithms - it's fast enough to get into production and slow enough to blow up once you start using it. Rockstar infamously wasted five minutes loading GTAV because they had an n^2 algorithm in the startup sequence.
- svara 1y ago> What do you mean? Modulo is not a perfect hash function It's a perfect hash function for the case where you work with ints and know the maximal min-max range beforehand; then you can modulo by the size of the range as long as it's not too large. In your example 33-21 --> mod 12 This comes up for me surprisingly often but obviously depends a lot on what you work on. It is often tempting to reach for a hashtable, but it's a lot less efficient in this case.