Комментарии 40
Оцениваем мощность множества за O(1)
В комментариях заметили, что в самом общем случае, сложность алгоритма по памяти будет O(eps^-2 * log(log(n)) + log(n)). Это математически строгий ответ, но на практике все оказывается несколько проще.
Моя реализация как и все известные мне реализации алгоритма устанавливают какую-то разумную верхнюю границу мощности множества: 2^32, 2^64 или 2^128. Предполагается, что вы никогда не достигните этой границы. Тогда, если верхняя граница, скажем, 2^64, потребляемая память становится постоянной и определяется точно согласно формуле m * 6bit и не зависит от мощности оцениваемого множества. В О-нотации постоянная память есть О(1).
Всё равно не понял как вы
Оцениваем мощность множества за O(1)
если вы сначала пропускаете весь поток чтобы посчитать хэши и их частоту..
O(n), конечно, должно быть
Правильнее будет O(n), O(1) это стоимость оценки уже добавленного множества. Мне почему-то казалось, что это выдающееся свойство алгоритма, хотя обычное множество умеет также. Но зато у HyperLogLog'a все операции имеют сложность O(1) и потребляемая память O(1), что его выгодно выделяет при работе с большими объемами данных.
и потребляемая память O(1)
Что-то не верится. Где об этом почитать?
В самой статье есть формула для потребляемой памяти: m * 6bit, где m — константа алгоритма, если быть более точным, потребляемая память будет O(m), что есть O-большое от константы.
m оценивается исходя из размера множества и требуемой точности оценки. То есть не является константой. Реальная потребляемая память будет O(log n) при фиксированной точности. Подробнее на википедии
m не оценивается, а определяется параметром точности алгоритма как 2^precision. В некоторых реализация, например от Redis, пользователь не может задавать точность алгоритма, а значит и определять m при инициализации.
m остается неизменным во время работы алгоритма и не зависит от мощности оцениваемого множества, поэтому я считаю что это константа. Требуемая для алгоритма память определяется m, а значит она тоже постоянна.
В моих тестах, при фиксированном параметре m, а значит и потребляемой памяти, точность оценки не превышала теоретическое значение для мощностей в диапазоне от 0 до 2^28, большие мощности я не исследовал. Поэтому я придерживаюсь мнения, что точность оценки скорее не зависит от мощности множества, если, конечно, мощность не порядка 2^64.
Если вы со мной не согласны, то, объясните, пожалуйста, при каких условиях потребляемая алгоритмом память может начать превышать m * 6bit.
Поэтому я придерживаюсь мнения, что точность оценки скорее не зависит от мощности множества, если, конечно, мощность не порядка 2^64.
Вопрос оценки логарифмической сложности O (log n) вообще не имеет особого смысла на маленьких числах вроде 64. Надо устремлять размер множества ближе к бесконечности :) и там смотреть.
Совершенно очевидно, что память в данном случае не может иметь оценку O(1), так как при общем времени работы алгоритма O(n) нужна работающая на каждом шаге за O(1) по времени хеш-функция, а такая (не итеративная) хеш-функция должна иметь хеш-таблицу, размер которой зависит от n. При хеш-функции недостаточной разрядности вы просто в самом начале обработки множества переберёте все возможные значения хеш-функции, и дальнейшие элементы множества не будут никак влиять на оценку. Таким образом, на самом деле память расходуется на хеш-таблицу, а не на ваш массив m*6.
С оценками сложности надо быть очень аккуратным, и рассматривать реализацию алгоритма до условных машинных команд, а не останавливаться на вызовах библиотечных функций.
Я не понимаю зачем вам хеш-таблица. Алгоритм работает с хешами. Хранить элементы или хеши не нужно. Поясните, если не согласны.
В чем вообще смысл такого алгоритма, если мы параллельно строим хеш-таблицу с добавляемыми элементами?
Посмотрите, как внутри устроена хеш-функция, с помощью которой вы вычисляете хеш-значение от данного элемента. Там либо таблица, либо цикл (на практике всегда таблица, так как небольшое количество памяти дешевле времени). Это не добавляемые элементы, а просто набор констант, представляющих собой, например, коэффициенты полинома n-й степени.
Но ведь ни размер этой таблицы, ни количество итераций этого цикла от количества элементов на входе не зависит.
Они прямо зависят от разрядности хеш-функции. А разрядность хеш-функции должна быть такой, чтобы мощность множества значений хеш-функции не была значительно меньше мощности множества различных элементов в нашей генеральной совокупности. Поскольку мы не накладываем в задаче никаких ограничений на разнообразие элементов, то количество необходимых значений хеш-функции пропорционально объёму входных данных.
Например, если у нас на входе множество из 2^64 различных значений, то нам понадобится не менее чем 64-разрядная хеш-функция, чтобы значительно не потерять в точности оценки. Если у нас множество из 2^64000 значений, то понадобится 64000-разрядная хеш-функция.
64000-разрядная хеш-функция будет сложнее 64-разрядной либо по времени, либо по памяти.
Это несколько умозрительные цифры для реальных задач, но такова уж оценка O(log n).
Если у нас множество из 2^64000 значений, то понадобится 64000-разрядная хеш-функция.
Во вселенной атомов меньше.
На практике вам вряд ли придется оценивать множество размером больше 2^64, но если вдруг придется, то для оценки множества разменом меньше 2^128 нам придется просто добавить 1 бит к регистру.
Чтобы эта математика работала, вам нужна хеш-функция переменной разрядности и независимая оценка требуемой разрядности, ведь её нужно выбрать до начала алгоритма.
Поскольку всего этого нет — сложность алгоритма остаётся O(n), сложность хеш-функции — O(1), а то что при больших n оценка сильно теряет в точности оказывается просто ещё одним свойством алгоритма, не влияющим на время.
ИМХО, хеш-функция переменной разрядности это слишком. Все известные мне реализации используют 32, 64 или 128 битные хеш-функции и я не вижу в этом проблемы.
Не ужели так сложно гарантировать, что оцениваемое множество будет меньше 2^64 или даже 2^128?
при больших n оценка сильно теряет в точности
Только если мы приближаемся к верхней границе множества, тогда оценку придется скорректировать, как это делают в 32-битной реализации, в 64 битной считают что мы никогда не приблизимся верхней границы и забивают.
Если вы гарантируете, что множество будет меньше 2^128, то разговоры о сложности O (log n) вообще не имеют смысла, так как 128 – маленькое число.
Не понимаю, почему вы оцениваете как O(log n).
Точная формула требуемой памяти для оценки множества размером не больше чем n следующая: m * log2(log2(n)).
Давайте сойдемся на том, что алгоритм не предполагает хеширования переменной разрядности и работает с множествами ограниченного размера, поэтому log2(log2(n)) будет константой, не зависящей от размера множества, а значит и память тоже будет постоянной.
Не понимаю, почему вы оцениваете как O(log n)
Потому что значение хеш-фунции, имеющей мощность N, записывается в виде двоичного числа длиной log2 (N) разрядов, для вычисления которого необходимо выполнить не менее чем порядка log2 (N) операций или сохранить в таблице порядка log2 (N) предвычисленных значений. А log2 (N) равен log (N) с точностью до константы, поэтому двойка в оценке сложности опускается.
Давайте сойдемся на том
Я бы не против, но мы не на рынке ;) Это строгая математика.
Точная формула требуемой памяти для оценки множества размером не больше чем n следующая: m * log2(log2(n)).
Выше вам приводили ссылку на точную оценку в википедии, по объёму памяти получается O (eps^-2 * log (log (n)) + log (n)), где первое слагаемое связано с самим алгоритмом HyperLogLog, а второе – как раз с вычислением хеша.
Если мы все-таки согласимся на ограничение размера множества множества, замечу, допустимое для всех практических задач. То даже O (eps^-2 * log (log (n)) + log (n)) будет константой.
Я хочу сказать, что все известные мне реализации работают с ограниченными множествами, и поэтому задействуют постоянные объемы памяти.
Математически, возможно, вы правы. Но на практике потребляемая память всегда постоянна и определяется формулой m * log2(log2(n)). Это просто удобнее и почти ни в чем нас не ограничивает.
Не понял, почему это нужно выбрать до начала алгоритма.
В любом случае, ничто не мешает ни написать хеш-функцию переменной разрядности, ни даже динамически генерировать лямбду с телом хеш-функции в ходе выполнения алгоритма. Это вообще не те проблемы, которые должны заботить человека, занимающегося теорией вычислительных процессов и выводящего математическую оценку сложности алгоритма.
Хеш-функция преобразует поток байт в чиселки, обычно, используя цикл. Объясните, пожалуйста, как таблица может помочь в вычислении хеш-функции.
С циклом – это упрощённая реализация, для понимания сути алгоритма хеширования. На практике цикл никто не запускает, так как некоторые получаемые в цикле значения можно предвычислить и записать в массив в виде констант.
Посмотрите, например, для начала реализацию CRC16 в виде цикла и в виде таблицы. Это один из самых простых алгоритмов.
Более сложный случай разобран, например, в этой статье. Вот о той таблице, которая приведена в конце статьи, я и говорю.
Если же вы будете для вычисления хеш-функции запускать цикл, то не уложитесь в O(n) по времени, так как каждый из n шагов займёт больше О(1).
Поделитесь, пожалуйста, реализацией CRC16, в которой не будет цикла.
Естественно, если вы хотите обработать больше байтов, чем размер индекса таблицы, то вам надо будет, кроме цикла вычисления CRC, разворачиваемого в таблицу, ещё делать цикл по обрабатываемым порциям данных.
Но тут же есть цикл
uint16_t // Returns Calculated CRC value
CalculateCRC16(
uint16_t crc, // Seed for CRC calculation
const void *c_ptr, // Pointer to byte array to perform CRC on
size_t len) // Number of bytes to CRC
{
const uint8_t *c = c_ptr;
while (len--)
crc = (crc << 8) ^ crctable[((crc >> 8) ^ *c++)];
return crc;
}
Есть отличные хеш-функции, не использующие таблицы. Например, Murmurhash, который я применял.
Тут цикл, потому что таблица у вас побайтная, а считается crc для len байтов.
Есть отличные хеш-функции, не использующие таблицы. Например, Murmurhash, который я применял.
В murmurhash таблица из 4 элементов прописана в самом коде, в однотипных группах по 4 логические операции с разными коэффициентами. Если бы значение murmurhash было не 4-байтовым, а 400-байтовым, там было бы по 400 присваиваний в группе, или массив на 400 элементов, или цикл на 400 итераций.
Вот, кстати, прекрасное практическое упражнение: написать 64-разрядный murmurhash.
А как это влияет на асимптотику алгоритма?
И что вы имели в виду, когда говорили?
На практике цикл никто не запускает
А как это влияет на асимптотику алгоритма?
Именно так, что сложность увеличивается пропорционально разрядности. А разрядность равна логарифму мощности множества.
И что вы имели в виду, когда говорили?
На практике цикл никто не запускает
Что цикла по разрядам числа в практически используемых алгоритмах нет.
У вас в статье есть формула для подсчета estimate. Очевидно, что у этой функции есть максимум, который достигается, когда во всех потоках мы видим max(rank), т.е. нулевой хэш. Выше этого значения при фиксированном m оценку мы не увидим. Можно провести мысленный эксперимент: перебирать натуральные числа до бесконечности. В какой-то момент, перебрав N натуральных чисел, мы достигнем максимальной оценки. Поскольку числа мы перебираем до бесконечности, то для любого фиксированного m найдется некое N, при котором максимальная оценка будет достигнута. Соответственно m надо подбирать исходя из максимального числа уникальных элементов множества, которое мы ожидаем. Понятно, что на практике 64-битного хэша может быть достаточно в большинстве случаев, но мы же тут про асимптотику говорим.
Вот тут мой топик на тостере про вероятностные алгоритмы. Достаточно много интересного можно найти по ссылкам.
https://qna.habr.com/q/91971
Добавляйте еще туда, если что-то знаете.
Для чего это может быть полезно? Мы можем быстро оценивать число элементов, удовлетворяющих сложным условиям поиска. Например, торговая площадка может оценить для пользователя, сколько ноутбуков обладает 4 или 6 или 8 ядрами, и при этом в них установлена IPS матрица и SSD диск. Если для всех условий будет заранее построена структура HLL, это оценку можно сделать почти моментально
Так не покатит. В данном случае для пользователя очень существенной будет разница между ответами 0 или 1, а для алгоритма это допустимая погрешность.
Да, вы правы, есть такая проблема, если результирующее множество порядка погрешности. Магазину такую ситуацию обнаружить не сложно. Лично для меня подобный обман на 1 не был бы ОЧЕНЬ существенным, я бы просто упростил условия поиска.
Но если мы большой магазин, в котором много товаров и мы уверены, что для большинства критериев у нас будет много товаров, то алгоритм отлично себя покажет. В противном случае можно попробовать применить другие алгоритмы. У всего есть границы применимости :).
Это был лишь простой пример, демонстрирующий технику работы с алгоритмом, возможно, не слишком удачный.
Оцениваем мощность множества за O(1)
В комментариях заметили, что в самом общем случае, сложность алгоритма по памяти будет O(eps^-2 * log(log(n)) + log(n)). Это математически строгий ответ, но на практике все оказывается несколько проще.
Моя реализация как и все известные мне реализации алгоритма устанавливают какую-то разумную верхнюю границу мощности множества: 2^32, 2^64 или 2^128. Предполагается, что вы никогда не достигните этой границы. Тогда, если верхняя граница, скажем, 2^64, потребляемая память становится постоянной и определяется точно согласно формуле m * 6bit и не зависит от мощности оцениваемого множества. В О-нотации постоянная память есть О(1).
про распределение нулей в md5 зависимости от качества входных данных.
в данном примере. в md5 подаются id int(32) в зависмости кол-во абстрактных пользователей
<?php
declare(strict_types=1);
function nulles($max)
{
$x = [];
for ($i = 1; $i < $max; ++$i) {
$md5 = md5((string)$i);
$cnt = 0;
for ($md_i = 0; $md_i < 32; ++$md_i) {
if ($md5[$md_i] !== '0') {
break;
}
++$cnt;
}
$x[$cnt] = 1 + ($x[$cnt] ?? 0);
}
return [$max => $x];
}
function raspred($x)
{
$result = [];
foreach ($x as $max => $res) {
foreach ($res as $zeros => $count) {
$result["от 1 до $max"]["md5 имеет $zeros нулей в начале"] = '1/' . round($max / $count, 3) . ' или ' . round( $count / $max * 100, 2) . '%';
}
}
return $result;
}
foreach (
[
5000,
10000,
50000,
100000,
500000,
1000000,
10000000,
] as $size
) {
var_dump(raspred(nulles($size)));
}
Алгоритм HyperLogLog, или Оцениваем мощность множества за O(1)