News for hackers. Stuff that matters.
Re:Searching 20 GB/sec: Systems Engineering Before Algorithms by hvidgaard on Monday May 12, 2014 @04:30AM (#7731670)
I wrote it in a hurry. O(n^4) is only for the size of the current chunk of data being operated on, usually measured in cache lines. I guess it should have been m, as n is usually used for the total input size. It's not unusual to see O(m^c * log n) algorithms or even O(m^c * log log n) if you can use vEB search structure, where m is the number of cache lines the algorithm works on, c is an algorithm specific constant, and n is the total input size.
Re:Searching 20 GB/sec: Systems Engineering Before Algorithms by dekhn on Monday May 12, 2014 @08:53AM (#7732398)
Ah, OK. So you meant space overhead in practical terms

I would think that a greater than constant time overhead would not be compatible with a real time streaming operation. just a guess, though.

Thanks for mentioning http://en.wikipedia.org/wiki/Van_Emde_Boas_tree as I hadn't heard of that. The last paragraph on the page gives some nice pointers (use a trie or randomized hash table).