Фиксированная память
Почему это важно "Посчитайте, как часто случается каждая вещь" - это словарь, пока число вещей не становится неограниченным, а память - нет. Приближённый счёт с гарантированной границей часто стоит гораздо больше, чем точный счёт, который вам не по карману.
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 подходят.
Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке
Это упражнение откроется скоро
Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.
Этот браузер блокирует cookies для learn.floati.life, поэтому завершенные здесь уроки не могут открыться по порядку. Разрешите cookies для этого сайта и перезагрузите страницу.