В комментариях заметили, что в самом общем случае, сложность алгоритма по памяти будет O(eps^-2 * log(log(n)) + log(n)). Это математически строгий ответ, но на практике все оказывается несколько проще. Моя реализация как и все известные мне реализации алгоритма устанавливают какую-то разумную верхнюю границу мощности множества: 2^32, 2^64 или 2^128. Предполагается, что вы никогда не достигните этой границы. Тогда, если верхняя граница, скажем, 2^64, потребляемая память становится постоянной и определяется точно согласно формуле m * 6bit и не зависит от мощности оцениваемого множества. В О-нотации постоянная память есть О(1).
Если мы все-таки согласимся на ограничение размера множества множества, замечу, допустимое для всех практических задач. То даже O (eps^-2 * log (log (n)) + log (n)) будет константой.
Я хочу сказать, что все известные мне реализации работают с ограниченными множествами, и поэтому задействуют постоянные объемы памяти. Математически, возможно, вы правы. Но на практике потребляемая память всегда постоянна и определяется формулой m * log2(log2(n)). Это просто удобнее и почти ни в чем нас не ограничивает.
Не понимаю, почему вы оцениваете как O(log n). Точная формула требуемой памяти для оценки множества размером не больше чем n следующая: m * log2(log2(n)).
Давайте сойдемся на том, что алгоритм не предполагает хеширования переменной разрядности и работает с множествами ограниченного размера, поэтому log2(log2(n)) будет константой, не зависящей от размера множества, а значит и память тоже будет постоянной.
Да, вы правы, есть такая проблема, если результирующее множество порядка погрешности. Магазину такую ситуацию обнаружить не сложно. Лично для меня подобный обман на 1 не был бы ОЧЕНЬ существенным, я бы просто упростил условия поиска.
Но если мы большой магазин, в котором много товаров и мы уверены, что для большинства критериев у нас будет много товаров, то алгоритм отлично себя покажет. В противном случае можно попробовать применить другие алгоритмы. У всего есть границы применимости :).
Это был лишь простой пример, демонстрирующий технику работы с алгоритмом, возможно, не слишком удачный.
В общем случае вы, конечно, правы, но подобный анализ асимптотики я считаю сильно избыточным. Гораздо удобнее работать с алгоритмом в предположении что у нас есть какая-то разумная верхняя граница множества.
ИМХО, хеш-функция переменной разрядности это слишком. Все известные мне реализации используют 32, 64 или 128 битные хеш-функции и я не вижу в этом проблемы.
Не ужели так сложно гарантировать, что оцениваемое множество будет меньше 2^64 или даже 2^128?
при больших n оценка сильно теряет в точности
Только если мы приближаемся к верхней границе множества, тогда оценку придется скорректировать, как это делают в 32-битной реализации, в 64 битной считают что мы никогда не приблизимся верхней границы и забивают.
В теории оно может и так, но на практике очень сложно найти задачу задачу подсчета масштаба 2^64. Но если вдруг придется, то HyperLogLog справится с этой и большими задачами лучше всех известным мне алгоритмов.
Если у нас множество из 2^64000 значений, то понадобится 64000-разрядная хеш-функция.
Во вселенной атомов меньше.
На практике вам вряд ли придется оценивать множество размером больше 2^64, но если вдруг придется, то для оценки множества разменом меньше 2^128 нам придется просто добавить 1 бит к регистру.
m не оценивается, а определяется параметром точности алгоритма как 2^precision. В некоторых реализация, например от Redis, пользователь не может задавать точность алгоритма, а значит и определять m при инициализации.
m остается неизменным во время работы алгоритма и не зависит от мощности оцениваемого множества, поэтому я считаю что это константа. Требуемая для алгоритма память определяется m, а значит она тоже постоянна.
В моих тестах, при фиксированном параметре m, а значит и потребляемой памяти, точность оценки не превышала теоретическое значение для мощностей в диапазоне от 0 до 2^28, большие мощности я не исследовал. Поэтому я придерживаюсь мнения, что точность оценки скорее не зависит от мощности множества, если, конечно, мощность не порядка 2^64.
Если вы со мной не согласны, то, объясните, пожалуйста, при каких условиях потребляемая алгоритмом память может начать превышать m * 6bit.
В самой статье есть формула для потребляемой памяти: m * 6bit, где m — константа алгоритма, если быть более точным, потребляемая память будет O(m), что есть O-большое от константы.
Правильнее будет O(n), O(1) это стоимость оценки уже добавленного множества. Мне почему-то казалось, что это выдающееся свойство алгоритма, хотя обычное множество умеет также. Но зато у HyperLogLog'a все операции имеют сложность O(1) и потребляемая память O(1), что его выгодно выделяет при работе с большими объемами данных.
В комментариях заметили, что в самом общем случае, сложность алгоритма по памяти будет O(eps^-2 * log(log(n)) + log(n)). Это математически строгий ответ, но на практике все оказывается несколько проще.
Моя реализация как и все известные мне реализации алгоритма устанавливают какую-то разумную верхнюю границу мощности множества: 2^32, 2^64 или 2^128. Предполагается, что вы никогда не достигните этой границы. Тогда, если верхняя граница, скажем, 2^64, потребляемая память становится постоянной и определяется точно согласно формуле m * 6bit и не зависит от мощности оцениваемого множества. В О-нотации постоянная память есть О(1).
Если мы все-таки согласимся на ограничение размера множества множества, замечу, допустимое для всех практических задач. То даже O (eps^-2 * log (log (n)) + log (n)) будет константой.
Я хочу сказать, что все известные мне реализации работают с ограниченными множествами, и поэтому задействуют постоянные объемы памяти.
Математически, возможно, вы правы. Но на практике потребляемая память всегда постоянна и определяется формулой m * log2(log2(n)). Это просто удобнее и почти ни в чем нас не ограничивает.
А как это влияет на асимптотику алгоритма?
И что вы имели в виду, когда говорили?
Не понимаю, почему вы оцениваете как O(log n).
Точная формула требуемой памяти для оценки множества размером не больше чем n следующая: m * log2(log2(n)).
Давайте сойдемся на том, что алгоритм не предполагает хеширования переменной разрядности и работает с множествами ограниченного размера, поэтому log2(log2(n)) будет константой, не зависящей от размера множества, а значит и память тоже будет постоянной.
Но тут же есть цикл
Есть отличные хеш-функции, не использующие таблицы. Например, Murmurhash, который я применял.
Да, вы правы, есть такая проблема, если результирующее множество порядка погрешности. Магазину такую ситуацию обнаружить не сложно. Лично для меня подобный обман на 1 не был бы ОЧЕНЬ существенным, я бы просто упростил условия поиска.
Но если мы большой магазин, в котором много товаров и мы уверены, что для большинства критериев у нас будет много товаров, то алгоритм отлично себя покажет. В противном случае можно попробовать применить другие алгоритмы. У всего есть границы применимости :).
Это был лишь простой пример, демонстрирующий технику работы с алгоритмом, возможно, не слишком удачный.
В общем случае вы, конечно, правы, но подобный анализ асимптотики я считаю сильно избыточным.
Гораздо удобнее работать с алгоритмом в предположении что у нас есть какая-то разумная верхняя граница множества.
ИМХО, хеш-функция переменной разрядности это слишком. Все известные мне реализации используют 32, 64 или 128 битные хеш-функции и я не вижу в этом проблемы.
Не ужели так сложно гарантировать, что оцениваемое множество будет меньше 2^64 или даже 2^128?
Только если мы приближаемся к верхней границе множества, тогда оценку придется скорректировать, как это делают в 32-битной реализации, в 64 битной считают что мы никогда не приблизимся верхней границы и забивают.
Поделитесь, пожалуйста, реализацией CRC16, в которой не будет цикла.
В теории оно может и так, но на практике очень сложно найти задачу задачу подсчета масштаба 2^64. Но если вдруг придется, то HyperLogLog справится с этой и большими задачами лучше всех известным мне алгоритмов.
Во вселенной атомов меньше.
На практике вам вряд ли придется оценивать множество размером больше 2^64, но если вдруг придется, то для оценки множества разменом меньше 2^128 нам придется просто добавить 1 бит к регистру.
Хеш-функция преобразует поток байт в чиселки, обычно, используя цикл. Объясните, пожалуйста, как таблица может помочь в вычислении хеш-функции.
Я не понимаю зачем вам хеш-таблица. Алгоритм работает с хешами. Хранить элементы или хеши не нужно. Поясните, если не согласны.
В чем вообще смысл такого алгоритма, если мы параллельно строим хеш-таблицу с добавляемыми элементами?
m не оценивается, а определяется параметром точности алгоритма как 2^precision. В некоторых реализация, например от Redis, пользователь не может задавать точность алгоритма, а значит и определять m при инициализации.
m остается неизменным во время работы алгоритма и не зависит от мощности оцениваемого множества, поэтому я считаю что это константа. Требуемая для алгоритма память определяется m, а значит она тоже постоянна.
В моих тестах, при фиксированном параметре m, а значит и потребляемой памяти, точность оценки не превышала теоретическое значение для мощностей в диапазоне от 0 до 2^28, большие мощности я не исследовал. Поэтому я придерживаюсь мнения, что точность оценки скорее не зависит от мощности множества, если, конечно, мощность не порядка 2^64.
Если вы со мной не согласны, то, объясните, пожалуйста, при каких условиях потребляемая алгоритмом память может начать превышать m * 6bit.
В самой статье есть формула для потребляемой памяти: m * 6bit, где m — константа алгоритма, если быть более точным, потребляемая память будет O(m), что есть O-большое от константы.
Правильнее будет O(n), O(1) это стоимость оценки уже добавленного множества. Мне почему-то казалось, что это выдающееся свойство алгоритма, хотя обычное множество умеет также. Но зато у HyperLogLog'a все операции имеют сложность O(1) и потребляемая память O(1), что его выгодно выделяет при работе с большими объемами данных.