4 ms·
I can't resist mentioning a favorite algorithm of mine for solving a related problem. It generalizes the algorithm for the classic problem of finding the majori
by psykotic 14y ago
I can't resist mentioning a favorite algorithm of mine for solving a related problem. It generalizes the algorithm for the classic problem of finding the majority element (one which occurs at least 50% of the time) with a single pass over a stream, using a constant amount of space, and a second sieving pass. It's one of those simple gems you wonder why it took so long to discover.
http://www.cs.yale.edu/homes/el327/datamining2011aFiles/ASimpleAlgorithmForFindingFrequentElementsInStreamsAndBags.pdf http://www.cs.yale.edu/homes/el327/datamining2011aFiles/ASim...
- deleted 14y ago[deleted]
- nicksdjohnson 14y agoVery nice, thanks! It might be too similar for a post all of its own, but I think it'd be a worthy followup to this post.
- deleted 14y ago[deleted]
- lurker14 14y agoDirect link to the pre-generalized: https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html Note that this algorithms fails silently if there is not majority element, which limits the scope of its utility. I assume that the reason it took so long to discover is that no one needed the solution before. Are there applications that can benefit form this algorithm?
- beder 14y agoYou can do a second pass over the list to check that your solution is actually a majority element. This maintains the linear time and constant space properties.
- justincormack 14y agoUnfortunately single pass is usually the binding constraint eg real time data processing.