4 ms·

Here'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.asp

Here'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 ago
very 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 ago
Update: 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.

antirez 18y ago

very 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 ago

Update: 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.