HyperLogLog: как посчитать миллиарды, используя лишь килобайты

Как можно подсчитать миллиарды уникальных посетителей, не храня миллиарды имен? HyperLogLog решает эту удивительную задачу, используя случайные биты, редкие шаблоны и крошечный объем памяти. В этом анимированном объяснении по информатике огромная вечеринка превращается в простую историю из реальной жизни для понимания приблизительного подсчета уникальных посетителей. Вы узнаете, как хеширование преобразует каждый элемент в биты, выглядящие случайными, почему длинные последовательности ведущих нулей указывают на большое количество наблюдений и почему HyperLogLog распределяет данные по множеству небольших регистров, вместо того чтобы полагаться на один удачный результат. Вы также узнаете, как HyperLogLog: • Оценивает количество уникальных элементов в огромном наборе данных • Использует сегменты и счетчики с ведущими нулями для экономии памяти • Объединяет значения регистров с помощью формулы, основанной на гармоническом среднем • Применяет корректировки для повышения точности • Эффективно объединяет счетчики на нескольких компьютерах • Обеспечивает работу аналитики уникальных посетителей, поиска, кликов и баз данных В конце вы поймете, как вероятностная структура данных может пожертвовать небольшой точностью ради огромной экономии памяти — и почему такие системы, как Redis, используют HyperLogLog, когда точный подсчет был бы слишком затратным. Подпишитесь на KindlySimplify, чтобы получать больше доступных анимированных объяснений алгоритмов, структур данных, распределенных систем и других увлекательных концепций информатики. #HyperLogLog #Информатика #Алгоритмы #СтруктурыДанные #БольшиеДанные