Программа курса Урок 77 из 148 · Странные пределы
Странные пределы

Фиксированная память

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

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

Скетч: сводка потока фиксированного размера, которая отвечает на вопросы приближённо, с известной границей ошибки. Count-min sketch, например, хранит несколько строк счётчиков и хеширует каждый элемент в один счётчик на строку; наименьший из этих счётчиков никогда не меньше истинного счёта.

import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width   # same on every run
Твоя очередь

Напишите class ApproxCounter с add(item) (элементы - строки) и estimate(item) (целое число).

Пределы. После 30 000 событий от до 10 000 разных пользователей счётчик может хранить не больше 3 500 элементов (kept() на счётчике). Оценки никогда не должны быть меньше истинного счёта, а как минимум для 95% пользователей (включая никогда не встречавшихся) должны быть не больше истинного счёта плюс 300 (1% событий). Результаты должны повторяться при каждом запуске и на каждом устройстве: не используйте hash() (он меняется от запуска к запуску) и случайные числа; zlib.crc32 или hashlib с фиксированными seed подходят.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.