Комментарии 50
Хм. Про фильтр Блума никто даже не вспомнил?
Хотя алгоритм из статьи выглядит более шустрым.
Да, и при переводе потерялись верхние индексы – 2⁶ превратилось в 26.
Фильтр Блума же не про подсчёт уникальных элементов, а про проверку нахождения в множестве.
Именно! У нас поток элементов, каждый проверяем фильтром и если не было – добавляем в него.
Подход даст систематическую погрешность (ложно-положительные срабатывания фильтра – занижение числа уникальных элементов), но её можно оценить и учесть (тогда погрешность станет меньше, но уже может быть и вверх, и вниз)
Но это так, баловство на самом деле, тут уже вспомнили HyperLogLog, который требует всего один хэш, он явно будет эффективнее.
Не важно, что не про подсчёт, про него всё равно никто не вспомнит.
HyperLogLog вроде выглядит ничуть не хуже по оценке сложности и памяти?
У HLL ещё много полезных возможностей, например можно объединять независимо посчитанные скетчи, оценивать кардинальность пересечения и разницы. Интересно, если ли аналогичные тут.
Но этот гораздо проще. Хотя если значения переменной длины и большие, то придется всё равно накапливать хеши вместо значений, и все опять усложнится.
Ага, а пользователю этот результат покажут как ТОЧНЫЙ, а не как статистическое шмуду-вуду.
а ты думаешь число просмотров на ютубе сейчас точное показывается??? ха-ха-ха
Мне кажется подсчёт уникальных элементов не только (и не столько) для Ютубовских просмотров нужен :)
Я думаю, что некорректно сравнивать универсальный метод оценки доли уникальных элементов и узкоспециализированное решение для анализа посещаемости.
Анализ посещаемости.в первую очередь требует не механизма подсчёта уникальных элементов, а выработки критериев уникальности.
Смысл упражнения заключается в том, чтобы убедиться, что каждое слово, в силу случайного выбора, имеет одинаковую вероятность оказаться там: 1/2^k
Текст статьи создает ощущение объяснения алгоритма "на пальцах". Но при попытке задуматься над обоснованностью утверждений проваливаешся в "кроличью нору".
Итак, алгоритм на каждой итерации вдвое понижает шансы остаться в списке слову для которого нашелся очередной дубль и из набранной очередной порции просто удаляет половину. Снимаю шляпу перед тему, кому очевидно, что число уникальных элементов можно посчитать по приведенной формуле после такого алгоритма.
Как вариант можно подобрать количество бросков монет по количеству элементов в исходном массиве, результаты бросков записать в двоичном виде, перевести в десятичную систему счислений и представить это как приблизительный результат.
Может быть он и не будет точным, зато очень эффективным
Правильный заголовок должен быть: способ ПРИБЛИЗИТЕЛЬНОГО подсчёта уникальных элементов
Всё становится ещё хуже. Что, если вы — Facebook, и вам нужно подсчитать количество отдельных пользователей, которые заходят на сайт каждый день, даже если некоторые из них заходят с нескольких устройств и в разное время? Теперь мы сравниваем каждый новый вход со списком, который может исчисляться миллиардами.
статью всю не читал, но у меня вопрос сразу по вот этому конкретному примеру. Доступ же к элементу конкретного пользователя это О(1), соответственно подсчёт пользователей которые зашли сегодня, это O(n). Отсюда не ясно, зачем "сравниваем каждый новый вход со списком". Там же простая выборка из фибоначчиевой кучи, то есть О(1), для n элементов базы и одно условие с датой "сегодня".
можно сделать вообще проще, входы каждого дня складывать в разные базы, ну или список списков с индексом текущего дня. Тогда у вас вся сегодняшняя база, это и есть все кто заходил сегодня. Точно так же О(1) до конкретного пользователя и O(n) для всего списка, только n(сегодня) сильно меньше чем n(всей базы).
Это всё про логи, а не базы данных. Есть терабайты логов, для каждого пользователя там могут быть тысячи или больше записей. Надо всё прочитать (желательно в один проход), и подсчитать. Писать в базу на каждую прочитанную запись - база умрет, считать желательно в памяти. Плюс считать надо много разных вещей, заранее часто не известных, скажем читать лог и считать пользователей кликнувших на чью-то рекламу
Логи - это функция, а не способ представления информации. Вам никто не запрещает логи держать в виде таблиц. Вопрос не в том "можно/нельзя", а в том - как потом вы с этим работать собираетесь. Если вам нужно быстро получать доступ к чему-то, то и организовывать доступ вы будете не просто всё сваливая в кучу. Так что ваше замечание считаю просто неправильным подходом к хранению данных. То есть вы сами себе создаёте проблему.
Писать в базу на каждую прочитанную запись - база умрет
А в чем принципиальное отличие базы от текстового лога? ОЗУ то же, ЦПУ тот же, диски - те же, почему от записи в текстовик ничего не умрёт, а именно от записи в базу вдруг умрёт.
считать желательно в памяти
Так СУБД для этого и используются.
Плюс считать надо много разных вещей, заранее часто не известных, скажем читать лог и считать пользователей кликнувших на чью-то рекламу
С больной головы на здоровую не перекладывайте. Мы рассматриваем только конкретный вопрос описанный в статье, а вы уже все проблемы фейсбука притянули.
Вам никто не запрещает логи держать в виде таблиц.
Никто кроме здравого смысла. Логи в таких системах каждый из тысяч фронтэнд серверов пишет отдельно, с минимальными издержками. Каждый датацентр изолированно от других. Потом уже всё собирается и обрабатывается.
Не знаю уж как именно вы собираетесь организовывать базу, одну на всех судя по описанию, и фронтэнд из Австралии будет делать INSERT в базу в США? Или таки отдельно? Но тогда вы ничего не изменили, все равно число записей на много порядков больше числа пользователей и надо их обрабатывать, как выше. Только потеряли порядок или два производительности.
А в чем принципиальное отличие базы от текстового лога?
А вы попробуйте. Писать в локальный файл и делать INSERT в таблицу, а ещё лучше как в вашем оригинальном описании - UPDATE таблицы с пользователями.
Нету у памяти доступа за O(1), особенно когда памяти много, особенно когда это не влазит сначала в оперативу, а потом и сервер вообще
https://habr.com/ru/articles/309394/
Ну, скажем, поиск по мапе это log(n), у меня вопрос настолько ли это затратно, что имеет смысл немного ускорять алгоритм ради приблизительного подсчёта.
Тут главное приемущество - не ускорение, а то, что не надо в памяти все элементы держать. Можно обрабатывать гигабайты логов, храня в памяти лишь несколько килобайт элементов. Если вы посмотрите на оригинальную статью, то там огромный упор делается на ограниченном размере используемой памяти. А сложность работы алгоритма по времени вообще, кажется, не упоминается.
Тут речь не о "немного ускорить", а о том, чтоьы не выделять O(n) памяти.
Главный вопрос - а какова область применения данного алгоритма? Сейчас ведь памяти много, можно хоть миллиарды элементов хранить и не полагаться на вероятностные алгоритмы.
ну как вариант - контроллер в стиральной машине со встроенной 512 байт ОЗУ, идёт поток данных от датчиков, не слишком важно знать что у вас точно 394 события, достаточно понимать что их около 400. Экономия доллара на модуле памяти и еще 8 долларов на проектировании платы, напайке и габаритах. ИМХО
Не так уж и много памяти сейчас. Вот есть у нас несколько юзеров БД, каждый запустил запрос на количество уникальных по нескольким колонкам. А среди них еще и строковые могут быть. И на практике это реально кучу памяти отъедает. Плюс это еще и медленно. Поэтому приблизительные алгоритмы рулят, особенно которые дают точный результат на маленьком числе групп, а неточность возникает только после тысяч.
Есть разница между тем, что запрос отожрал всю память и если повезет, то не упал и выполнился за время пока ты кофе пошел сделать, и тем, что запрос ничего не отожрал и выполнился за пару секунд (но может быть выдал 123456700 вместо 123456789, какой ужас).
каждый запустил запрос на количество уникальных по нескольким колонкам
Какой-то случай слишком абстрактный. В каких конкретных случаях нужны такие запросы на количество всех уникальных элементов?
На счёт потребления памяти - если там миллионы элементов, то её хватит. Если миллиарды - хватит при умелом обращении и достаточном количестве оперативки (десятки гигабайт).
В случаях с приблизительными запросами можно тогда вообще, не изобретать каких-то приблизительных алгоритмов, а проводить точный подсчёт и просто кешировать результат на какое-то время.
в аналитике данных таких запросов дофига. Все эти уникальные клиенты за сегодня, уникальные товары за месяц, или уникальные теги в твиттере.
Да, так сейчас и делается где можно - результат кэшируется но не везде это возможно, а как раз дистинкты и плохо агрегеруются. Если например сумму продаж ты можешь просто хранить для каждого магазина, а потом если в отчете надо весь город - просто сложить все магазины - и вот тебе сумма. То с уникальными товарами в тех же магазинах так не выйдет. Если есть 100 уников в одном и втором магазине - то в двух вместе их будет не 200, а X (от 100 до 200) т.е. надо пересчитать заново, для группы. И то есть либо всегда считать дистинкты на лету (что очень медленно) либо хранить их для КАЖДОЙ комбинации измерений (что оо-о-о-чень много данных)
Компании, у которых столько клиентов, что не хватит памяти пересчитать их всех, очень редки. У остальных же подсчёт их нескольких тысяч клиентов займёт доли секунды. С товарами ситуация аналогична - если это не Amazon, то памяти на их пересчёт хватит.
Описанный же в данной статье алгоритм нужен только для тех случаев, когда реально поток данных колоссален и в память всё не умещается, и посему приходится жертвовать точностью ради самой возможности работы алгоритма.
ты путаешь теплое с мягким. В обычной торговой компании 10000 уникальных товаров, но миллирды фактов продаж. И менеджеру постоянно хочется то уникальные по этому городу, то уникальные на этой неделе, то уникальные по этой акции. И на каждую смену фильтра в репорте надо быстренько желательно за 2 секунды посчитать это из миллирада продаж.
Сейчас ведь памяти много, можно хоть миллиарды элементов хранить и не полагаться на вероятностные алгоритмы.
Это в теории и для частного пользователя, где можно воткнуть в комп лишние ресурсы и развлекаться.
А когда промышленное производство на продажу, там между указанными в тексте 100 словами и 150 словами может находиться граница окупаемости.
В заголовке обещают подсчёт, а в теле статьи описывают оценку количества слов.
взял Гамлета http://lib.ru/SHAKESPEARE/hamlet5.txt
В пьесе 30 557 слов
Это неверно, в пьесе 54 251 слово, судя по свойствам файла в notepad++
допустим имелась ввиду английская книга, но уже странно. При переводе одно слово обращалось в два?
засовываем в подсчёт уникальных слов. https://planetcalc.ru/3204/
В "Гамлете" ровно 3 967 уникальных слов.
Тоже не верно, уникальных слов 14425, Да и в принципе серьезно кто-то поверит, что у Шекспира был словарный запас в 4000 слов, как у среднего семиклассника, который 3 года учит английский как иностранный? Или в то, что при переводе на русский одно слово превращается в 5?
Попробую конечно прописать и запустить именно этот алгоритм на Гамлете, но тут даже по ошибкам в фактологии уже явно что-то не так, попахивает недоброкачественными выводами или сознательными искажениями действительности.
Это из этой версии:
Hidden text
wc hamlet_TXT_FolgerShakespeare.txt > 6080 32004 182866 hamlet_TXT_FolgerShakespeare.txt в данном файле гамлет на айнглийском, если убрать названия сцен/актов, их номера, разделители типа ====== то похоже на правду, что там действительно 30к+ слов
файл отсюда https://www.folger.edu/explore/shakespeares-works/download/#hamlet
Уникальных слов в указанном Вами варианте Гамлета через https://planetcalc.ru/3204/ - 5192
А https://ciox.ru/count-the-number-of-unique-words даёт более похожее на правду число 9140
Возможно это разница между приведенными в lowercase словами и уникальными без приведения.
на первом сайте подсчёт тоже так себе, если такие ошибки исключить думаю число упадёт до искомых ~4k
вот как он посчитал - What(203) think(49) you(553) on(134) 't(81)?
что это за слово 81раз встречается 't? )))
Можете сами придумать регулярку, которая слова вычленяет на ваш взгляд правильно, и заменить тут простую \w+ на нужную: https://fiddle.clickhouse.com/1a424911-2450-4668-82bc-c27a24b4161b
со \w+ и lowercase получается:
count(): 32583
uniqExact(word): 4650
uniq(word): 4650
uniqCombined(word): 4657
uniqHLL12(word): 4663
length(toString(uniqExactState(word))): 74402
length(toString(uniqState(word))): 18603
length(toString(uniqCombinedState(word))): 98505
length(toString(uniqHLL12State(word))): 2651Примерный uniq дает такой же результат, что и точный uniqExact, но занимает меньше памяти. Но тут данных мало, если найдется файлик пожирнее, разница будет больше.
допустим имелась ввиду английская книга
Эта статья - перевод, естественно они использовали не русский перевод Гамлета
Алгоритм работает для любого списка, в который элементы поступают по одному — как слова в речи, товары на конвейере или автомобили на шоссе.
Что-то мне кажется, что играет роль ещё и вид распределения поступающих элементов. Если оно будет не равномерным, то точность может серьёзно ухудшиться. Тогда область применимости этого метода ещё больше сужается.
Тут вопрос не в количестве слов в Гамлете. Не понятно, каким образом в статье получилось перебрать 30 000 слов всего за 6 раундов при емкости памяти в 100 слов. Если количество уникальных слов примерно 3 900, то в выборке из 100 слов вероятность появления повтора ~2,5%. То есть для заполнение доски в нулевом раунде требуется прочитать примерно 103 слова из пьесы. После случайного вычеркивания остается 50 свободных мест. Для их заполнения в 1-м раунде требуется прочитать примерно 51-52 слова. Вычеркивание ~1 повтора с вероятностью 50% не сильно влияет на общий расклад.
Понимаете? Мы прочитали всего 155 слов из 30 000 и уже дошли до 2-го раунда. В следующих раундах, с ростом k, будет вычеркиваться практически каждый встречающийся повтор, но это опять же не имеет большого значения, т.к. повторяется всего 1-2 слова из 50 и в каждом раунде для заполнения 50 мест нужно прочитать 51-52 слова. То есть на то, чтобы прочитать все 30 000 слов требуется ~580 раундов. В конце получим бессмысленное число 61*2^580.
В итоге, видимо, в каждом новом раунде нужно не вычеркивать повторяющиеся слова с вероятностью 1/2^k, а с вероятностью 1/2^k добавлять новые, которых нет в данный момент на доске. Повторы при этом просто игнорировать, как и в нулевом раунде. И тогда в каждый момент времени вероятность нахождения слова на доске как раз и будет равна 1/2^k.
Хотя нет, мое последнее предположение тоже не работает. Из него в итоге получается примерно общее количество слов ~30 000.
В статье алгоритм изложен "неточно".
На следующих раундах все, а не только совпадающие слова добавляются с вероятностью 1/2^k. Совпадение проверяется только для того, чтобы выкинуть слово из сохранённых перед тем, как пробовать его добавлять:
X ← X \ {ai} - выкинуть слово, если такое уже есть (аi - текущее слово взятое из текста, X - наш пул сохранённых слов)
With probability p, X ← X ∪ {ai} - с вероятностью p, установленной для данного раунда сохраняем слово.
И, соответственно, количество уникальных будет - количество элементов в нашем массиве когда мы дойдём до конца текста, разделить на текущую вероятность. В приведённом примере это примерно от 50*2^6 =3200 до 99*2^6=6336.
Специалисты по информатике изобрели новый эффективный способ подсчёта уникальных элементов