потоковая обработка

Статьи

SRT Алгоритм Top-k: k лучших Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением. O(n log k) 2 задачи STR Алгоритм Префикс-функция и КМП Все вхождения образца за O(n + m) без шагов назад по тексту; префикс-функция находит и период строки. O(n + m) 2 задачи STR Алгоритм Алгоритм Ахо — Корасик Все вхождения тысяч слов за один проход: бор из слов плюс ссылки отказа, как у префикс-функции. O(n + Σ|wᵢ| + z) 1 задача STR Структура данных Суффиксный автомат Все подстроки текста в графе из меньше чем 2n состояний: склейка фразы из кусков «Онегина» за один проход. O(n) 2 задачи STR Алгоритм LZ77 и LZW Повторы — ссылками назад (LZ77) или номерами фраз растущего словаря (LZW); хеш-цепочки, уровни, окно. O(n · chain) 2 задачи NUM~ Приём Суммирование Кэхэна Сложить миллионы дробных чисел и не растерять младшие разряды: поправка Кэхэна, попарное и точное суммирование. O(n) 1 задача SYS Структура данных Count-Min Sketch Частоты элементов потока в фиксированной памяти: минимум из d счётчиков, ошибка только вверх. O(d) на элемент и на запрос 2 задачи SYS Структура данных HyperLogLog Число разных элементов потока в килобайте памяти: длинные серии нулей в хешах и среднее по регистрам. O(1) на элемент, O(m) на оценку 2 задачи SYS Алгоритм Резервуарная выборка k случайных элементов из потока неизвестной длины за один проход и O(k) памяти. O(n) 2 задачи SYS Алгоритм Ограничение частоты запросов Не больше N запросов в единицу времени: окно, журнал, два счётчика и ведро с токенами. O(1) на запрос (журнал — O(N)) 2 задачи SYS Алгоритм Алгоритм rsync Передаёт только изменённые куски файла: суммы блоков туда, новые байты обратно; блоки находятся на любом смещении.

O(n + m): сумма окна сдвигается за O(1), сильная сумма — только при совпадении слабой

2 задачи ML Алгоритм Наивный Байес Считает, как часто каждый признак встречается в каждом классе, и складывает логарифмы этих частот. O(N) обучение, O(L·m) ответ 2 задачи ML Алгоритм Линейная регрессия Подбирает коэффициенты модели так, чтобы сумма квадратов промахов по данным была наименьшей. O(n·d² + d³) 2 задачи TEC Приём Скользящее окно Окно ширины w ползёт по данным: ответ правится по входящему и уходящему элементу за O(1) вместо O(w). O(n) 2 задачи

Задачи

Миллион температур Выборка по энергии Два ограничителя Две оценки Место в каталоге Повороты на конвейере Распаковать LZW Сейсмическая тревога Старые блоки в новом файле Хроника из региональных каталогов Частые слова за один проход Декодер Запас ведра Медиана за окно Самое сильное за месяц Сколько раз перепишется резервуар Точная сумма Фильтр учится на ходу Эхо

Часто рядом

в проде 10 собеседования 7 классика 6 аналитика 5 сети 4 хеширование 4 поиск в тексте 3 автомат 3 олимпиады 3 скользящее окно 3 вероятностная структура 3 куча 2