Comments 30
Я читаю теги.
Повезло тебе, сейчас начнётся голосование ;)
На самом деле, весьма полезная статья. Я думаю, многие начинающие (и не только) программисты по привычке решают проблемы «в лоб» гарантированным методом, даже когда нужна только приблизительная оценка. Я, к своему стыду, должен признать, что регулярно поступаю так же, поэтому читать про вероятностные алгоритмы и структуры данных мне очень интересно.
Спасибо. Хорошая статья. Как раз скоро будет на чем проверить ваш подход
Спасибо, познавательно!!!
в jsfiddle поигрался, и при
var log_log = HyperLogLog(0.01);
var log_log = HyperLogLog(0.001);
упорно получаю ошибку 44%
чем это объясняется?
var log_log = HyperLogLog(0.01);
var log_log = HyperLogLog(0.001);
упорно получаю ошибку 44%
чем это объясняется?
походу что-то не так со стадией «make corrections»
Угу, беда именно с ней — при малом количестве уникальных элементов, она себя так ведёт.
а откуда такие формулы? может в них ошибка?
и еще, по ссылке «мэд скилзы» стандартная ошибка определена через 1.3, а не 1.04, и даже с какими-то коррекциями 1.05. И еще смущает подсчет alpha_m.
хочется разобраться, ибо мне помог бы этот алгоритм
и еще, по ссылке «мэд скилзы» стандартная ошибка определена через 1.3, а не 1.04, и даже с какими-то коррекциями 1.05. И еще смущает подсчет alpha_m.
хочется разобраться, ибо мне помог бы этот алгоритм
В первой «бумаге» описывается именно HyperLogLog, во второй просто LogLog и SuperLogLog. У них разные стандартные ошибки, т.к. алгоритмы немного разные. Вторые два без коррекций ведут себя совсем плохо, параметры надо более точно подбирать, чтобы добиться приемлемых результатов, SuperLogLog в этом плане более всеяден и выдаёт меньшую ошибку.
По-большому счёту, все три алгоритма заточены на подсчёт большого количества элементов. При небольшом, получается что массив M населён мало, т.е. если m не сильно меньше N, то начинает расти ошибка, а m как раз таки зависит от желаемой точности. В HyperLogLog эта ситуация немного подправляется корректировкой, так же как и перенаселение массива M, в (Super)LogLog оставляется как есть.
Все коэффициенты и поправки взяты из первой публикации про HyperLogLog.
По-большому счёту, все три алгоритма заточены на подсчёт большого количества элементов. При небольшом, получается что массив M населён мало, т.е. если m не сильно меньше N, то начинает расти ошибка, а m как раз таки зависит от желаемой точности. В HyperLogLog эта ситуация немного подправляется корректировкой, так же как и перенаселение массива M, в (Super)LogLog оставляется как есть.
Все коэффициенты и поправки взяты из первой публикации про HyperLogLog.
селффикс:
Вторые два без коррекций, ведут себя совсем плохо, параметры надо более точно подбирать, чтобы добиться приемлемых результатов, HyperLogLog в этом плане более всеяден и выдаёт меньшую ошибку.
Вторые два без коррекций, ведут себя совсем плохо, параметры надо более точно подбирать, чтобы добиться приемлемых результатов, HyperLogLog в этом плане более всеяден и выдаёт меньшую ошибку.
все понятно, ты в последних формулах использовал логарифм с основанием 2, хотя по HyperLogLog там просто log, и методом проб между основаниями 10 и e, правильные ответы дает с основанием e
if (E <= 5/2 * m)
{
var V = 0; for (var i = 0; i < m; ++i) if (M[i] == 0) ++V;
if (V > 0) E = m * Math.log(m / V);
}
else if (E > 1/30 * pow_2_32) E = -pow_2_32 * Math.log(1 - E / pow_2_32);
Я валенок, сейчас поправлю :)
поправь заодно такую вот это. Висточнике пишут =, но я думаю что имеется ввиду < =
потому что, если имеем для 16 значение 0.673, для 32 ..., то не может быть, чтобы для 15 было так как и для больше 64
var alpha_m = m <= 16 ? 0.673
: m <= 32 ? 0.697
: m <= 64 ? 0.709
: 0.7213 / (1 + 1.079 / m);
потому что, если имеем для 16 значение 0.673, для 32 ..., то не может быть, чтобы для 15 было так как и для больше 64
Реализация из публикации на такое не рассчитана, при m меньше 16, ошибка от 40% и выше. Тут лучше эксепшен выкидывать, но код для поиграться сделан, поэтому тихий фейл.
понятно, и про степень двойки, тогда примерами для сравнения будут 8 и 128
Не, ну если очень нужны m менее 16, в публикации есть метод расчёта alpha_m для них, 0.673 их так же плохо аппроксимирует, как и 0.7213 / (1 + 1.079 / m). В любом случае, смысла особого нет в их использовании, т.к. абсолютная величина ошибки в 95%-доверительном интервале практически равна самой измеряемой величиной.
… только что проверил, 0.7213 / (1 + 1.079 / m) всё-таки лучше аппроксимирует.
… кстати, m всегда степень двойки.
Кстати, там ссылки две, «мэд» и «скилзы», может не заметил :)
Очень интересно!
Но вот у меня такая мысль, а нельзя на таком же принципе сделать аналог фильтра Блума с еще меньшими потребностями памяти?
Простейшая идея: если добавление очередного элемента достаточно (на 1?) увеличивает этот счетчик — значит такого элемента, скорее всего, еще не было. Если увеличивает недостаточно — то, скорее всего, уже встечался. Правда ошибка будет очень большой боюсь…
Может кто-нибудь уже встречал похожий алгоритм?
Но вот у меня такая мысль, а нельзя на таком же принципе сделать аналог фильтра Блума с еще меньшими потребностями памяти?
Простейшая идея: если добавление очередного элемента достаточно (на 1?) увеличивает этот счетчик — значит такого элемента, скорее всего, еще не было. Если увеличивает недостаточно — то, скорее всего, уже встечался. Правда ошибка будет очень большой боюсь…
Может кто-нибудь уже встречал похожий алгоритм?
Я правильно понимаю, что идея — использовать подсчет числа различных элементов, чтобы проверить лежит ли элемент в множестве. Если это так, нам потребуется константная абсолютная погрешность. По информационным оценкам на такое потребуется как минимум линейная память, а по оценкам HyperLogLog-а она будет квадратичной от числа различных элементов.
Если хочется максимально ужать множество, посмотрите коды Голомба: http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters
Если хочется максимально ужать множество, посмотрите коды Голомба: http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters
А еще есть Count-Min Sketch: https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
А еще какие нибудь вероятностные алгоритмы из этой области вам известны? Я тут веду список таких алгоритмов:
https://toster.ru/q/91971
https://toster.ru/q/91971
Да, известны. На самом деле трудно найти что-то детерминированное. Вот есть неплохой курс: http://www.cs.dartmouth.edu/~ac/Teach/CS85-Fall09/ и блог: http://research.neustar.biz/ по стримингу.
Sign up to leave a comment.
LogLog — находим число уникальных элементов