4 ms·
Typically you do not need to both randomly select one element and use them as keys in a map. If you do need both, the easy way to do it is to just keep the keys
by lacker 18y ago
Typically you do not need to both randomly select one element and use them as keys in a map. If you do need both, the easy way to do it is to just keep the keys in an array as well as in a hash table.
The algorithm the author uses is not a good example. A simpler way to find the approximate most common elements in a large collection is to use a heap to store the (object, count) pairs. Still O(1), and you can remove the element with the lowest count each time instead of getting an approximation.
- antirez 18y agolacker the example was just useful to explain how sometimes it can be useful to run randomized algorithms with hash tables. A real world example is a DNS cache that can't hold more than N elements, you can just remove one at random. Another one is a cache where elements can expire, and you want to perform a lazy cleanup.
- antirez 18y agoStill from this page: http://en.wikipedia.org/wiki/Heap_(data_structure) http://en.wikipedia.org/wiki/Heap_(data_structure) I can't see how it is possible using an heap to count most common elements in large collction, without approximation, and using constant memory. May you please argument better the original comment? Thanks
- abecedarius 18y agoHere's a Brian Hayes column on good algorithms for this problem: http://www.americanscientist.org/issues/id.3822,y.0,no.,content.true,page.1,css.print/issue.aspx http://www.americanscientist.org/issues/id.3822,y.0,no.,cont... I think lacker was probably thinking of a correct algorithm for finding the n largest values in a set, instead of the n most frequent values.
- antirez 18y agovery interesting, thanks. I could like to simulate the problem in order to check how my simple algorithm performs compared to others described in the article. EDIT: I analyzed a bit the differences between Yale University algorithm using M conters and my algorithm. It is interesting that while the Yale's algo gives you all the top elements with a given minimal frequency it is O(M) because you have to decrement M counters for every new element not matching any of elements in the M registers. My algorithm even if randomized (so you are not sure you track all the top M elements, but the output will be an approximation of that) can bring the M-probably-top-elements using O(1) time for element. The memory used is O(M) in both the algorithms. I wonder if the algorithm I proposed was described or not. Note how you can trade time for accuracy selecting more accurately what element to drop to add the next one. If you sample three elements dropping the minimum of the three the accuracy will be a given one, but if you sample ten elements it will be different. I wonder if somebody is able here to analyze this algorithm more in depth.
- antirez 18y agoUpdate: I wrote a simulation program, my algorithm appears to perform better compared to the majority-finding algorithm of Yale's university described in the american scientist article even if the algorithm I proposed is O(1) and the Yale's is O(M) (where M is the number of top-items to track). I'll post an article with more details and the source code on YN today.
- lacker 18y agoYou are using a randomized algorithm to approximate the smallest element in a collection of (object, count) pairs. Instead, use a min-heap to find the smallest element. You do need a hash table as well to keep track of items' locations in the heap. You don't have to do any pop operations - since you only need to remove something from the list when you have a new item with count = 1, you can just replace the item at the root of the heap. This is probably also not the simplest way to get a reasonable approximation. Certainly those Hayes algorithms are better. You could also try something like, read in 2N elements, sort them, and drop the least-frequent N of them. Then read in N more and repeat. Pretty hacky though. You could also try bloom filters.
- antirez 18y agolacker, there are infinite solutions to every problem, but if you want really to find a competitor to my algorithm that performs better you NEED to talk about algorithms not using more than O(1) for every new element processed. To sort the set from time to time is not valid under this assumptions for example. This is going to be M log M. Registers is O(M). p.s. M here is the number of top-elements tracked.
- lacker 18y agoYou asked for algorithms that use constant memory. So M is a constant and M log M is constant too.