The Boyer–Moore majority algorithm, is a probabilistic algorithm that solves the majority problem for any data stream in a single pass using constant memory. Today, I’ll do an implementation in Clojure.
(defn boyer-moore [xs]
(loop [ys xs
count 0
candidate nil]
(cond (empty? ys) candidate
(zero? count) (recur (rest ys) 1 (first ys))
(= (first ys) candidate) (recur (rest ys) (inc count) candidate)
true (recur (rest ys) (dec count) candidate))))#'user/boyer-mooreLet us test
(boyer-moore [0 1 1 0 2 2 2 0 0 0 1 0 2 0])2There is an extension of the Boyer-Moore majority algorithm by Misra and Gries. I’ll implement that too.
(defn misra-gries [xs k]
(loop [ys xs
counts {}]
(if (empty? ys)
(keys counts)
(let [y (first ys)
zs (rest ys)]
(cond
(get counts y false) (recur zs (merge-with + counts {y 1}))
(< (count counts) k) (recur zs (merge counts {y 1}))
true (recur zs (->> (reduce-kv (fn [m k v] (assoc m k (dec v))) {} counts)
(filter (fn [[k v]] (> v 0)))
(into {}))))))))#'user/misra-griesLet us test
(misra-gries [0 1 1 0 2 2 2 0 0 0 1 0 2 0] 2)(0 2)