Copyright | (c) 2011 National Institute of Aerospace / Galois Inc. |
---|---|
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
This is an implementation of the Boyer-Moore Majority Vote Algorithm for
Copilot, which solves the majority vote problem in linear time and constant
memory in two passes. majority
implements the first pass, and aMajority
the second pass. For details of the Boyer-Moore Majority Vote Algorithm see
the following papers:
- Wim H. Hesselink, "The Boyer-Moore Majority Vote Algorithm", 2005
- Robert S. Boyer and J Strother Moore, "MJRTY - A Fast Majority Vote Algorithm", 1981
In addition, An Introduction to Copilot and copilot-discussion explain a form of this code in section 4.
For instance, with four streams passed to majority
, and the candidate stream
then passed to aMajority
:
vote1: vote2: vote3: vote4: majority: aMajority: 0 0 0 0 0 true 1 0 0 0 0 true 1 1 0 0 1 false 1 1 1 0 1 true 1 1 1 1 1 true
For other examples, see examples/Voting.hs
in the
Copilot repository.
Documentation
Majority vote first pass: choosing a candidate.