Частые слова за один проход
Нужно найти самые частые слова длинного потока, но памяти — на k счётчиков. Алгоритм Мисры — Гриса делает это так. Счётчики — пары «слово, число». Для очередного слова:
- если у слова уже есть счётчик, увеличить его на 1;
- иначе, если занято меньше k счётчиков, завести для слова счётчик со значением 1;
- иначе уменьшить на 1 все k счётчиков, а те, что стали нулём, удалить; само слово при этом никуда не записывается.
Пропустите поток через алгоритм и выведите, что осталось в счётчиках. Среди тестов — «Война и мир».
Вход
В первой строке n и k (1 ≤ n ≤ 2·105, 1 ≤ k ≤ 1000). Во второй — n слов через пробел, каждое из строчных латинских или русских букв и цифр, длиной до 20 символов.
Выход
В первой строке — число оставшихся счётчиков c. Дальше c строк «слово число»: по убыванию числа, при равенстве — по слову (в порядке байтов UTF-8).
Примеры
Пример 1
7 2 мир война мир труд мир май мир
2 мир 3 май 1
Пример 2
11 3 a b c a b c d a b e a
2 a 2 b 1
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Уменьшение всех счётчиков стоит O(k). Сколько раз оно может случиться за поток из n слов?
2Идея
Каждое уменьшение «съедает» k + 1 появлений сразу: по одному у каждого из k слов в счётчиках и само пришедшее слово. Всего появлений n, поэтому уменьшений не больше n/(k + 1), и на них уходит O(n) суммарно. Значит, хватает прямой реализации: словарь «слово → число» и проход по нему при уменьшении.
3Разбор
Из того же подсчёта следует главное свойство. Счётчик слова занижен ровно на число уменьшений, пока оно было в счётчиках, и на число его появлений, которые съели уменьшения, — а всех уменьшений не больше n/(k + 1). Значит, для каждого слова с частотой f итоговый счётчик не меньше f − n/(k + 1). Всякое слово, которое встречается больше n/(k + 1) раз, обязательно останется в счётчиках. Обратное неверно: в счётчиках может оказаться и редкое слово, если оно пришло в конце. Поэтому кандидатов проверяют вторым проходом, если он возможен.
На «Войне и мире» с 30 счётчиками порог — 120 000/31 ≈ 3871. Выше него только «и» — 5781 раз, — и оно выживает со счётчиком 1974, как и обещано: 1974 ≥ 5781 − 3871. Остальные девять мест занимают случайные слова со счётчиком 1. С одним счётчиком алгоритм превращается в голосование Бойера — Мура: он находит слово, встречающееся больше половины раз, если такое есть, — в романе такого нет, и пятый тест заканчивается пустым ответом. Набросок Count-Min из статьи отвечает на другой вопрос — частоту любого слова с ошибкой сверху, — а Мисра — Грис хранит только кандидатов, зато детерминирован и даёт ошибку снизу.
3+Решение
4Сложность
O(n) времени и O(k) памяти.
5Типичные ошибки
- Вытеснить наименьший счётчик. Новое слово получает счётчик вытесненного плюс один — так устроен алгоритм Space-Saving, у него другие числа и другие гарантии. Уже первый пример это показывает.
- Записать слово после уменьшения. Пришедшее слово само «съедается» уменьшением и в счётчики не попадает, даже если какой-то счётчик освободился.
- Порядок вывода. По убыванию числа, а при равенстве — по слову.
Алгоритмы задачи
O(d) на элемент и на запрос
2 задачи
SRT
Алгоритм
Top-k: k лучших
Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением.
O(n log k)
2 задачи