Частые элементы за один проход: большинство и сводка Мисры-Гриса

Если ты найдёшь элемент-большинство одним счётчиком, обобщишь приём на k счётчиков и докажешь, что ни один счётчик не занижен больше чем на N/(k + 1), - листай до «Теперь сам».

Как думаешь, можно ли найти большинство одной переменной

В потоке миллиард голосов. Известно, что один из кандидатов получил больше половины. Нужно назвать его, имея память на одно имя и одно число.

Попробуй угадать до чтения, возможно ли это. Считать голоса каждого кандидата - это словарь размером с число кандидатов. Оказывается, достаточно считать не голоса, а перевес: держать одного кандидата и число, которое растёт от его голосов и убывает от чужих.

На что это похоже

Зал, в котором сторонники разных кандидатов выходят парами: каждый, кто встретил сторонника другого кандидата, берёт его под руку, и оба уходят. В каждой ушедшей паре люди разные, поэтому сторонники одного кандидата не могут составить больше половины ушедших.

Если какой-то кандидат имел больше половины зала, всем его сторонникам пары не хватит: когда остальные разойдутся, в зале останутся только они. Счётчик в алгоритме - это число людей, которые пока стоят без пары.

Механизм: взаимное уничтожение и его обобщение

Алгоритм большинства. Хранятся кандидат и счётчик, сначала ноль.

пришёл элемент x:
    счётчик равен нулю:   кандидат = x, счётчик = 1
    x совпал с кандидатом:  счётчик + 1
    не совпал:              счётчик − 1

Уменьшение счётчика - это уход пары: пришедший элемент и один из накопленных голосов кандидата уничтожают друг друга. Если какой-то элемент занимает больше половины потока, его нельзя целиком разобрать на пары с другими, и в конце кандидатом окажется он. Если такого элемента нет, алгоритм всё равно назовёт какого-то кандидата: ответ нужно проверить вторым проходом, посчитав его голоса.

Сводка Мисры-Гриса. То же самое с k счётчиками вместо одного. Сводка - словарь не более чем из k пар «ключ, счётчик».

пришёл ключ x:
    x есть в сводке:           его счётчик + 1
    x нет, пар меньше k:       добавить пару (x, 1)
    x нет, пар уже k:          уменьшить все k счётчиков на 1, нулевые пары удалить;
                               x в сводку не попадает

Третий случай - уход группы: пришедший ключ и по одному голосу каждого из k хранимых ключей уничтожаются разом. Это k + 1 разный элемент потока.

Отсюда оценка. Каждое уменьшение убирает из учёта k + 1 элемент, а всего элементов N, значит уменьшений не больше N / (k + 1). Счётчик ключа отличается от его истинной частоты только на те уменьшения, в которых он участвовал, - либо как хранимый, либо как пришедший и отброшенный:

частота − N/(k + 1)  ≤  счётчик  ≤  частота

Ключ, которого в сводке нет, имеет «счётчик ноль», и для него неравенство тоже верно: его частота не больше N / (k + 1). Значит, всякий ключ с частотой больше N / (k + 1) в сводке есть.

При k = 1 это в точности алгоритм большинства: порог N / 2.

Правило

Сводка Мисры-Гриса с k счётчиками: свой ключ увеличивает счётчик, новый ключ занимает свободное место, а при заполненной сводке все счётчики уменьшаются на единицу и новый ключ отбрасывается. Счётчик ключа не больше его частоты и занижен не больше чем на N / (k + 1). Любой ключ с частотой больше N / (k + 1) присутствует в сводке; обратное неверно, и присутствие проверяют вторым проходом.

Разбор: большинство есть и большинства нет

def kandidat(potok):
    k = -1
    schet = 0
    for x in potok:
        if schet == 0:
            k = x
            schet = 1
        elif x == k:
            schet = schet + 1
        else:
            schet = schet - 1
    return [k, schet]

s_bolshinstvom = [7, 3, 7, 7, 2, 7, 5, 7, 7, 1, 7]
bez_bolshinstva = [7, 3, 7, 2, 7, 5, 1, 4, 6]
print(kandidat(s_bolshinstvom), s_bolshinstvom.count(7), len(s_bolshinstvom))
print(kandidat(bez_bolshinstva), bez_bolshinstva.count(6), len(bez_bolshinstva))

[7, 3] 7 11
[6, 1] 1 9

В первом потоке семёрка встречается 7 раз из 11 - больше половины; алгоритм назвал её, а счётчик 3 здесь равен перевесу: семь своих голосов минус четыре чужих. В общем случае счётчик - число голосов кандидата, оставшихся без пары: чужие голоса могут уничтожать и друг друга, и тогда он больше перевеса.

Во втором потоке большинства нет: семёрка встречается три раза из девяти. Алгоритм назвал шестёрку, которая встретилась один раз, - просто потому, что она пришла последней при нулевом счётчике. Сам по себе ответ алгоритма ничего не доказывает: он верен при условии, что большинство существует. Проверка - второй проход, в котором считаются голоса одного названного кандидата.

Разбор: девять счётчиков на шесть тысяч элементов

Поток из 6000 элементов: ключ 1 занимает около 20%, ключ 2 - 12%, ключ 3 - 8%, ключ 4 - 5%, остальное размазано по ключам от 5 до 2000. Сводка - 9 счётчиков. В программе уменьшение сделано пересборкой словаря: в новый попадают пары, у которых после вычитания остаётся больше нуля.

import random

def potok_s_tyazhelymi(n):
    potok = []
    for i in range(n):
        u = random.random()
        if u < 0.20:
            potok.append(1)
        elif u < 0.32:
            potok.append(2)
        elif u < 0.40:
            potok.append(3)
        elif u < 0.45:
            potok.append(4)
        else:
            potok.append(random.randint(5, 2000))
    return potok

def misra_gries(potok, k):
    schetchiki = {}
    for x in potok:
        if x in schetchiki:
            schetchiki[x] = schetchiki[x] + 1
        elif len(schetchiki) < k:
            schetchiki[x] = 1
        else:
            ostalis = {}
            for klyuch in schetchiki:
                if schetchiki[klyuch] > 1:
                    ostalis[klyuch] = schetchiki[klyuch] - 1
            schetchiki = ostalis
    return schetchiki

random.seed(61)
potok = potok_s_tyazhelymi(6000)
tochno = {}
for x in potok:
    tochno[x] = tochno.get(x, 0) + 1

k = 9
svodka = misra_gries(potok, k)
print(len(tochno), len(potok) // (k + 1))
for klyuch in sorted(svodka):
    print(klyuch, svodka[klyuch], tochno[klyuch], tochno[klyuch] - svodka[klyuch])

1622 600
1 699 1208 509
2 205 712 507
3 2 461 459
194 1 3 2
1354 1 3 2
1618 1 2 1
1661 1 2 1

Первая строка: в потоке 1622 разных ключа, порог N / (k + 1) = 600. Дальше - содержимое сводки: ключ, счётчик, истинная частота и занижение.

Ключи 1 и 2 с частотами 1208 и 712 выше порога и, как обещано, остались. Их счётчики занижены на 509 и 507 - меньше шестисот. Ключ 3 с частотой 461 ниже порога; он остался в сводке, но мог и не остаться, и счётчик у него всего 2. Ключ 4, встретившийся около трёхсот раз, в сводку не попал. Последние четыре строки - случайные ключи, пришедшие в самом конце потока.

Как читать такую сводку. Счётчик - нижняя граница частоты, а «счётчик плюс 600» - верхняя. Про ключ 1 известно: от 699 до 1299. Про ключ 194: от 1 до 601 - то есть ничего. Сводка сама не отличает тяжёлый ключ от только что пришедшего; отличает порог. Чтобы гарантированно получить все ключи с частотой больше 10% потока, берут k так, чтобы N / (k + 1) было не больше этой доли, а потом вторым проходом считают точные частоты кандидатов из сводки - их всего k.

Граница: сводка работает, когда тяжёлые ключи есть. Если поток ровный и ни один ключ не превышает порога, в сводке окажутся последние пришедшие ключи с малыми счётчиками - это не список «самых частых», и чтобы утверждать, что тяжёлых нет вовсе, кандидатов всё равно проверяют вторым проходом. И второе: удалений сводка не поддерживает - отменить событие нельзя.

Что ломается без этого

Кандидата в большинство не проверяют. Алгоритм назовёт кандидата всегда; он прав, только если большинство есть.

Счётчик читают как частоту. 699 в сводке - это «не меньше 699», а на деле 1208. Сравнивать по счётчикам два ключа можно, только если разница превышает допуск.

При переполнении выбрасывают ключ с наименьшим счётчиком, а остальные не трогают. Гарантия пропадает: тяжёлый ключ, пришедший поздно и вперемежку с новыми, каждый раз оказывается наименьшим и выбрасывается.

Порог не связан с k. Девять счётчиков гарантируют ключи с долей больше 10%. Искать по ним ключи с долей 1% - значит получить случайный набор.

Зачем это в работе

Поиск «горячих» ключей. В распределённом кеше или базе данных один ключ, на который приходится заметная доля запросов, перегружает свой узел; сводка на несколько десятков счётчиков на каждом узле находит такие ключи без учёта всех остальных.

Сетевая статистика: адреса и соединения, занимающие больше процента трафика. Счётчиков нужно около ста, а разных адресов в потоке - миллионы.

В отличие от count-min, эта сводка хранит сами ключи: на вопрос «кто самые частые» она отвечает списком, а таблице count-min пришлось бы задавать вопрос про каждый ключ отдельно. И её гарантия не опирается ни на случайность, ни на качество хеш-функций: она выполняется всегда, а не с вероятностью.

Теперь сам

1. Пройди алгоритмом большинства поток A, B, A, C, A. Какими будут кандидат и счётчик в конце?
2. В потоке 10 000 элементов, сводка на 4 счётчика. Насколько, самое большее, занижен счётчик?
3. Сколько счётчиков нужно, чтобы гарантированно сохранить все ключи с долей больше 2% потока?
4. Сводка на два счётчика содержит {A: 3, B: 1}. Пришёл ключ C. Что станет со сводкой?
5. В сводке для потока из 6000 элементов с девятью счётчиками у ключа счётчик 150. В каких пределах лежит его частота?