Кое-что о вероятностных структурах данных / Павел Айткулов (piano.io)

Опубликовано 14 апреля 2020, 18:07

Приглашаем на конференцию HighLoad++ 2024, которая пройдет 2 и 3 декабря в Москве!
Программа, подробности и билеты по ссылке: clck.ru/3DD4yb
--------
При поддержке AvitoTech мы впервые публикуем все видео с HighLoad++ 2019 в открытый доступ. Учитесь, вдохновляйтесь и перенимайте лучшие практики у спикеров, не выходя из дома.

Календарь конференций - ontico.ru

HighLoad++ 2019

Тезисы и презентация:
highload.ru/moscow/2019/abstra...

Вероятностные структуры данных позволяют значительно экономить на памяти для таких запросов, как поиск количества уникальных объектов, вхождение объекта, подсчет конкретного объекта. При этом используется на 1-2 порядка меньше памяти (в некоторых задачах вообще константный объем), чем на хранение исходных данных. Как недостаток, мы иногда контролируемо ошибаемся, например, с ошибкой 10^{-9}.
...

Нашли ошибку в видео? Пишите нам на support@ontico.ru