SpaceSaving и выбор сводки для частых элементов

Если ты опишешь замену в SpaceSaving, объяснишь, почему оценка завышена не больше чем на наименьший счётчик, и выберешь сводку под задачу с удалениями - листай до «Теперь сам».

Как думаешь, что делать с новым ключом, когда места нет

В сводке девять счётчиков, все заняты. Пришёл ключ, которого в ней нет. Сводка Мисры-Гриса в этом случае уменьшает все счётчики и отбрасывает новичка.

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

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

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

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

Механизм: наследование счётчика

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

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

Три свойства следуют прямо из правила.

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

Второе: наименьший счётчик не больше N / k. Сумма k счётчиков равна N, и наименьший из них не может превышать среднее.

Третье: счётчик ключа не меньше его частоты и завышен не больше чем на наименьший счётчик. Это пара утверждений, которые поддерживают друг друга: (а) счётчик хранимого ключа не меньше его частоты; (б) частота ключа, которого в сводке нет, не больше наименьшего счётчика. Когда новый ключ входит со значением m + 1, по (б) он до этого встречался не больше m раз, так что (а) для него выполнено. Выселенный ключ имел счётчик m, по (а) его частота не больше m, а наименьший счётчик сводки с этого момента не уменьшается - значит, для него выполнено (б). Завышение же целиком состоит из унаследованного m, а оно не больше нынешнего наименьшего счётчика.

частота  ≤  счётчик  ≤  частота + наименьший счётчик  ≤  частота + N/k

Следствие: любой ключ с частотой больше N / k в сводке есть. Если бы его не было, его частота не превышала бы наименьшего счётчика.

Реализации рядом со счётчиком хранят ещё одно число - унаследованное значение в момент входа. Разность «счётчик минус унаследованное» - гарантированная нижняя граница частоты, и по ней отделяют ключи, которые заведомо тяжёлые, от тех, чей счётчик почти целиком достался по наследству.

Правило

SpaceSaving с k счётчиками: свой ключ увеличивает счётчик; новый ключ занимает свободное место или место ключа с наименьшим счётчиком m, получая значение m + 1. Сумма счётчиков равна N. Счётчик не меньше частоты и превышает её не больше чем на наименьший счётчик сводки, который не больше N / k. Любой ключ с частотой больше N / k присутствует в сводке.

Разбор: тот же поток, девять счётчиков

Поток прежний - 6000 элементов, ключи 1, 2, 3, 4 занимают 20%, 12%, 8% и 5%. Наименьший счётчик ищется проходом по словарю; pop удаляет пару и возвращает её значение.

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 space_saving(potok, k):
    schetchiki = {}
    for x in potok:
        if x in schetchiki:
            schetchiki[x] = schetchiki[x] + 1
        elif len(schetchiki) < k:
            schetchiki[x] = 1
        else:
            slabyj = -1
            for klyuch in schetchiki:
                if slabyj == -1 or schetchiki[klyuch] < schetchiki[slabyj]:
                    slabyj = klyuch
            naimenshij = schetchiki.pop(slabyj)
            schetchiki[x] = naimenshij + 1
    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 = space_saving(potok, k)
pary = []
for klyuch in svodka:
    pary.append([svodka[klyuch], klyuch])
pary = sorted(pary)
print(pary[0][0], len(potok) // k)
for i in range(k - 1, -1, -1):
    klyuch = pary[i][1]
    print(klyuch, svodka[klyuch], tochno[klyuch], svodka[klyuch] - tochno[klyuch])

582 666
1 1208 1208 0
2 716 712 4
1661 583 2 581
3 583 461 122
1825 582 1 581
1618 582 2 580
1354 582 3 579
1221 582 4 578
194 582 3 579

Первая строка: наименьший счётчик 582, граница N / k = 666. Дальше - ключ, счётчик, истинная частота и завышение, по убыванию счётчика.

Ключ 1 посчитан точно: 1208. Ключ 2 завышен на 4. Оба тяжелее 666 и обязаны были остаться. Сумма всех девяти счётчиков - ровно 6000.

Остальные семь строк показывают оборотную сторону наследования. Ключ 1661 встретился дважды, а счётчик у него 583: почти всё унаследовано. Ключ 3 с настоящей частотой 461 имеет тот же счётчик 583 и по одному этому числу неотличим от ключа 1661. Счётчики, близкие к наименьшему, не говорят о ключе ничего: 583 значит «от 1 до 583». Отличить помогло бы второе число - унаследованное значение: оно ограничивает завышение сверху, и у ключа, набравшего вес самостоятельно, заметно меньше счётчика.

Разбор: три сводки и граница каждой

Мисры-Гриса на том же потоке дала ключам 1, 2 и 3 счётчики 699, 205 и 2; SpaceSaving - 1208, 716 и 583. Истинные частоты 1208, 712 и 461 лежат между ними: одна сводка занижает, другая завышает.

                        Мисры-Гриса        SpaceSaving          count-min
ошибка                  вниз, ≤ N/(k+1)    вверх, ≤ N/k         вверх, ≤ 2N/w с вер. 1 − 1/2ᵈ
память                  k пар              k пар                d · w счётчиков
хранит сами ключи       да                 да                   нет
случайность             нет                нет                  хеш-функции
удаление элементов      нет                нет                  да, вычитанием
объединение сводок      есть               есть                 сложение таблиц

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

Граница общая для всех трёх - ошибка измеряется в долях всего потока. Ни одна из сводок не скажет ничего полезного о ключах, чья доля меньше 1/k или 1/w.

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

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

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

Наименьший счётчик ищут проходом по всем. В разборе так и сделано, и каждая замена стоит k шагов. Настоящие реализации держат ключи в куче по счётчику или в списке групп с одинаковым счётчиком - тогда замена стоит log k или постоянное время.

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

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

Запросы «самые частые» в аналитических базах данных. Функция topK в ClickHouse возвращает приближённый список самых частых значений столбца и построена на разновидности SpaceSaving: точный ответ потребовал бы группировки по всем значениям.

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

Ограничение нагрузки. Чтобы найти клиентов, создающих больше процента запросов, достаточно сводки на сотню с небольшим счётчиков - на любом числе клиентов.

Теперь сам

1. Сводка на три счётчика содержит {A: 5, B: 2, C: 4}. Пришёл ключ D. Какой станет сводка?
2. После 900 элементов сводка на три счётчика содержит {A: 500, B: 250, C: ?}. Чему равен счётчик C?
3. В сводке на 100 счётчиков после миллиона элементов у ключа счётчик 30 000, наименьший счётчик в сводке - 9000. В каких пределах частота ключа?
4. Нужно отслеживать самые популярные товары в корзинах, причём товары из корзин удаляют. Какая из трёх сводок подходит?
5. На потоке из разбора Мисры-Гриса дала ключу 2 счётчик 205, SpaceSaving - 716. Что из этих двух чисел можно утверждать о частоте, не зная её?