4 ms·
Isn't the last part of the Cuckoo hashing paper the part that documents it as slight less good compared to existing algorithms? I mean it never comes out and sa
by jws 16y ago
Isn't the last part of the Cuckoo hashing paper the part that documents it as slight less good compared to existing algorithms? I mean it never comes out and says it, but if you look at the pictures… I think Cuckoo's best point was the provability of its bounds, but it has been a while since I read that paper.
I like the example of Parsing Expression Grammars. The idea of memoized top down parsing drifted past back in the 60's and early 70's when the folks like Aho and Ullman were busy slaying wild streams of symbols with ever more clever algorithms but was dismissed because of its memory footprint. Then in 2002 or so Bryan Ford said "Oi! What do you mean too much memory? My PC has an L2 cache bigger than that."[1] Now PEGs are widely used and I must say (having built dynamic grammar LR systems back when my time shared vax had a main memory the size of the L2 cache in my iMac) especially useful for dynamic grammars.
[1] Being an entirely fabricated quote, there is no applicable reference for this quotation.
- davidst 16y ago> Isn't the last part of the Cuckoo hashing paper the > part that documents it as slight less good compared > to existing algorithms? No, Cuckoo hashing is a trade of a little run-time performance for better memory utilization. It's still O(1). The performance cost amortizes as a constant. If you have gobs of memory you don't need it. But if you're memory-constrained it's a big win.