Теперь на нашей главной странице видео при каждом обновлении отображается новый набор из 24 рекомендаций — это стало возможным благодаря переходу на взвешенную выборку с резервуаром (A-Res). Это изменение решило проблему «вечно одной и той же сетки», которая преследовала нашу предыдущую ленту, отсортированную по баллам.

Почему старый подход портил пользовательский опыт

Каждые два часа мы подтягиваем самые популярные видео из восьми регионов и записываем результаты в таблицу SQLite. Наивным решением было отсортировать весь набор по показателю релевантности и взять первые 24 элемента. Этот метод гарантирует появление объектов с наивысшим баллом, но также гарантирует, что они там и останутся. Один вирусный ролик может занимать первую позицию днями напролет, и пользователи видят одну и ту же сетку при каждом обновлении страницы.

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

Что дает нам взвешенная выборка с резервуаром

Взвешенная выборка с резервуаром решает две проблемы одновременно:

  1. Свежесть с учетом смещения — вероятность выбора каждого видео пропорциональна его весу (например, баллу релевантности). Видео с двойным весом имеет в два раза больше шансов появиться в списке, но ни один элемент не гарантирован в выдаче.
  2. Эффективность использования памяти — алгоритм хранит только «резервуар» фиксированного размера из $k$ элементов ($k = 24$ для нашей ленты). Он обрабатывает поток за один проход, поэтому потребление памяти остается на уровне $O(k)$ независимо от количества поступающих кандидатов.

Основная идея проста. При сканировании входящих строк мы присваиваем каждому элементу случайный ключ, учитывающий его вес, а затем оставляем $k$ элементов с самыми высокими ключами.

Алгоритм на практике

Для каждого видео мы:

  1. Генерируем равномерное случайное число $u \in (0, 1)$.
  2. Вычисляем ключ $k = u^{1/\text{weight}}$.
    (Чем выше вес, тем больше ожидаемое значение ключа.)
  3. Вставляем элемент в min-heap, которая хранит $k$ текущих крупнейших ключей.
    Если размер кучи превышает $k$, мы удаляем наименьший ключ.

Когда поток заканчивается, в куче остаются те 24 видео, которые мы и отобразим.

Решение проблемы ограничений чисел с плавающей запятой

Когда вес видео очень велик, значение $u^{1/\text{weight}}$ в арифметике с двойной точностью становится практически неотличимым от 1.0. Из-за этого многие «тяжелые» элементы получают одинаковые ключи, и случайность теряется. Решение — работать в логарифмическом пространстве:

  • Вычисляем log_key = log(u) / weight вместо возведения в степень.

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

Чек-лист реализации

  • Структура данных: min-heap (очередь с приоритетами) размером $k$ эффективно хранит крупнейшие ключи (сложность вставки $O(\log k)$).
  • Тип данных: используйте 64-битные числа с плавающей запятой для $u$ и логарифмических ключей; они обеспечивают достаточную точность для типичных диапазонов весов.
  • Статистическая проверка: проведите быстрый тест методом Монте-Карло на небольшом наборе данных. Если элементы с весом 10 появляются примерно в десять раз чаще, чем элементы с весом 1, значит, реализация верна.
  • Потоковая обработка за один проход: алгоритму не нужно заранее знать общее количество кандидатов, что идеально подходит для нашего курсора SQLite, который выдает строки по одной.

Итог

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