Нет, я не буду доказывать что яндексовые АА секции это полезно. Я расскажу про кое что другое
Представь такую задачу
Ты стендист на какой-нибудь айтишной конференции. На стенд постоянно приходят участники, чтобы выиграть мерч или просто поболтать. В какой-то момент тебе надоело раздавать мерч и от скуки захотелось посчитать сколько же всего участников посетили твой стенд. Сложность в том, что каждый участник подходит к стенду по несколько раз, но зато у каждого на бейдже написан идентификатор участника (к сожалению число на бейдже рандомное, а не последовательное)
Запоминать каждого в лицо не получается, по номеру тоже так себе. Так что же делать?
И тут можно придумать вероятностный способ. Выберем какое-нибудь число, например 0. У каждого участника будем считать количество нулей в конце идентификатора и запоминать, какой максимум среди всех. А дальше используем такую логику: вероятность встретить один 0 в конце (то есть идентификатор вида ХХХХХ0) = 1/10, два нуля (ХХХХ00) - 1/100 и так далее. Тогда количество посетителей стенда будет 10 или 100, если мы встретили максимум один или два нуля в конце соответственно
Теперь у нас есть приблизительная оценка порядка участников. Но слишком уж большой разрыв между соседними оценками: 10, 100, 1000 и дальше больше. Можно немного улучшить - брать не десятичную запись, а двоичную. Тогда оценка будет намного точнее: 2, 4, 8, 16 и так далее
Примерно так работает алгоритм Флажоле-Мартина: хеширует идентификатор пользователя, считает количество нулей в конце для каждого пользователя и запоминает максимальное, число уникальных значений вычисляет как 2 в степени равной максимальному количеству нулей
Зачем это нужно на практике, если можно считать уникальные значения точно. Потому что считать точно бывает очень дорого - например если у вас миллионы пользователей и миллиарды событий в приложении за каждый день, то посчитать MAU не уронив базу бывает очень сложно. Тут на выручку приходят такие алгоритмы
Как попробовать самому: во многих БД примерный подсчёт уников уже есть. Например в clickhouse это функция uniq, в vertica, mssql, bigquery - APPROX_COUNT_DISTINCT. Работают за секунды, а ошибаются всего на пару процентов