LogLog — находим число уникальных элементов

[@impwx]

Я читаю теги.

[@stab]

Повезло тебе, сейчас начнётся голосование ;)

[@impwx]

На самом деле, весьма полезная статья. Я думаю, многие начинающие (и не только) программисты по привычке решают проблемы «в лоб» гарантированным методом, даже когда нужна только приблизительная оценка. Я, к своему стыду, должен признать, что регулярно поступаю так же, поэтому читать про вероятностные алгоритмы и структуры данных мне очень интересно.

[@stab]

Я от них просто без ума, немного жертвуя точностью можно получить огромный выигрыш в производительности и/или ресурсах. Хотя, для повседневных задач они порой как из пушки по воробьям.

[@impwx]

Ну да, если гостевухи на PHP писать, то да, некуда их там применить :)

[@alexey_lahtadir]

Спасибо. Хорошая статья. Как раз скоро будет на чем проверить ваш подход

[@stab]

Пожалуйста. Надеюсь, «взлетит» :)

[@alexey_lahtadir]

Спасибо. Хочется верить :)

[@IPv6]

Спасибо, познавательно!!!

[@ilnarb]

в jsfiddle поигрался, и при
var log_log = HyperLogLog(0.01);
var log_log = HyperLogLog(0.001);
упорно получаю ошибку 44%
чем это объясняется?

[@ilnarb]

походу что-то не так со стадией «make corrections»

[@stab]

Угу, беда именно с ней — при малом количестве уникальных элементов, она себя так ведёт.

[@ilnarb]

а откуда такие формулы? может в них ошибка?
и еще, по ссылке «мэд скилзы» стандартная ошибка определена через 1.3, а не 1.04, и даже с какими-то коррекциями 1.05. И еще смущает подсчет alpha_m.
хочется разобраться, ибо мне помог бы этот алгоритм

[@stab]

В первой «бумаге» описывается именно HyperLogLog, во второй просто LogLog и SuperLogLog. У них разные стандартные ошибки, т.к. алгоритмы немного разные. Вторые два без коррекций ведут себя совсем плохо, параметры надо более точно подбирать, чтобы добиться приемлемых результатов, SuperLogLog в этом плане более всеяден и выдаёт меньшую ошибку.

По-большому счёту, все три алгоритма заточены на подсчёт большого количества элементов. При небольшом, получается что массив M населён мало, т.е. если m не сильно меньше N, то начинает расти ошибка, а m как раз таки зависит от желаемой точности. В HyperLogLog эта ситуация немного подправляется корректировкой, так же как и перенаселение массива M, в (Super)LogLog оставляется как есть.

Все коэффициенты и поправки взяты из первой публикации про HyperLogLog.

[@stab]

селффикс:

Вторые два без коррекций, ведут себя совсем плохо, параметры надо более точно подбирать, чтобы добиться приемлемых результатов, HyperLogLog в этом плане более всеяден и выдаёт меньшую ошибку.

[@ilnarb]

все понятно, ты в последних формулах использовал логарифм с основанием 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);


[@stab]

Я валенок, сейчас поправлю :)

[@ilnarb]

поправь заодно такую вот это. Висточнике пишут =, но я думаю что имеется ввиду < =
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

[@stab]

Реализация из публикации на такое не рассчитана, при m меньше 16, ошибка от 40% и выше. Тут лучше эксепшен выкидывать, но код для поиграться сделан, поэтому тихий фейл.

[@ilnarb]

понятно, и про степень двойки, тогда примерами для сравнения будут 8 и 128

[@stab]

Не, ну если очень нужны m менее 16, в публикации есть метод расчёта alpha_m для них, 0.673 их так же плохо аппроксимирует, как и 0.7213 / (1 + 1.079 / m). В любом случае, смысла особого нет в их использовании, т.к. абсолютная величина ошибки в 95%-доверительном интервале практически равна самой измеряемой величиной.

[@stab]

… только что проверил, 0.7213 / (1 + 1.079 / m) всё-таки лучше аппроксимирует.

[@ilnarb]

на практике возможно все ((

[@stab]

… кстати, m всегда степень двойки.

[@stab]

Кстати, там ссылки две, «мэд» и «скилзы», может не заметил :)

[@santa324]

Очень интересно!
Но вот у меня такая мысль, а нельзя на таком же принципе сделать аналог фильтра Блума с еще меньшими потребностями памяти?
Простейшая идея: если добавление очередного элемента достаточно (на 1?) увеличивает этот счетчик — значит такого элемента, скорее всего, еще не было. Если увеличивает недостаточно — то, скорее всего, уже встечался. Правда ошибка будет очень большой боюсь…

Может кто-нибудь уже встречал похожий алгоритм?

[@SeptiM]

Я правильно понимаю, что идея — использовать подсчет числа различных элементов, чтобы проверить лежит ли элемент в множестве. Если это так, нам потребуется константная абсолютная погрешность. По информационным оценкам на такое потребуется как минимум линейная память, а по оценкам HyperLogLog-а она будет квадратичной от числа различных элементов.

Если хочется максимально ужать множество, посмотрите коды Голомба: http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters

[@SeptiM]

А еще есть Count-Min Sketch: https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch

[@begemot_sun]

А еще какие нибудь вероятностные алгоритмы из этой области вам известны? Я тут веду список таких алгоритмов:
https://toster.ru/q/91971

[@SeptiM]

Да, известны. На самом деле трудно найти что-то детерминированное. Вот есть неплохой курс: http://www.cs.dartmouth.edu/~ac/Teach/CS85-Fall09/ и блог: http://research.neustar.biz/ по стримингу.