Используя случайность, команда учёных создала простой алгоритм для подсчёта большого количества отдельных объектов в потоке данных.
Представьте, что вас отправили в девственный тропический лес, чтобы провести перепись диких животных. Каждый раз, когда вы видите животное, вы делаете снимок. Ваша цифровая камера будет фиксировать общее количество снимков, но вас интересует только количество уникальных животных — всех тех, которых вы ещё не посчитали. Как лучше всего получить это число? «Очевидное решение — запомнить всех животных, которых вы уже видели, и сравнивать каждое новое животное с этим списком», — говорит Лэнс Фортноу, специалист по информатике из Иллинойского технологического института. Но есть и более умные способы, добавил он, потому что если у вас тысячи записей, то очевидный подход далеко не так прост.
Всё становится ещё хуже. Что если вы — Facebook, и вам нужно подсчитать количество отдельных пользователей, которые заходят на сайт каждый день, даже если некоторые из них заходят с нескольких устройств и в разное время? Теперь мы сравниваем каждый новый вход со списком, который может исчисляться миллиардами.
В недавней статье учёные описали новый способ приблизительного определения количества отдельных записей в длинном списке, который требует запоминания лишь небольшого числа записей. Алгоритм работает для любого списка, в который элементы поступают по одному — как слова в речи, товары на конвейере или автомобили на шоссе.
Алгоритм CVM, названный так по имени его создателей — Сурава Чакраборти из Индийского статистического института, Винодчандрана Варияма из Университета Небраски в Линкольне и Кулдипа Мила из Университета Торонто, — это значительный шаг к решению так называемой проблемы отдельных элементов, над которой компьютерные учёные бьются уже более 40 лет. Она заключается в том, чтобы найти способ эффективно отслеживать поток элементов, общее количество которых может превышать объём доступной памяти, а затем оценить количество уникальных элементов.
«Новый алгоритм поразительно прост и лёгок в реализации, — говорит Эндрю Макгрегор из Массачусетского университета в Амхерсте. — Я не удивлюсь, если на практике это станет стандартным подходом к проблеме [отдельных элементов]».
Чтобы проиллюстрировать проблему и то, как алгоритм CVM её решает, представьте, что вы слушаете аудиокнигу «Гамлет». В пьесе 30 557 слов. Сколько из них являются уникальными? Чтобы узнать это, вы можете прослушать пьесу (часто пользуясь кнопкой паузы), записать каждое слово в алфавитном порядке в блокнот и пропускать слова, которые уже есть в вашем списке. Когда вы дойдёте до конца, вы просто посчитаете количество слов в списке. Этот подход работает, но он требует объёма памяти, примерно равного количеству уникальных слов.
В типичных ситуациях потоковой передачи данных могут быть миллионы элементов, которые необходимо отслеживать. «Возможно, вы не захотите хранить всё», — говорит Вариям. И именно здесь алгоритм CVM может предложить более простой путь. Хитрость, по его словам, заключается в том, чтобы полагаться на рандомизацию.
Вернёмся к «Гамлету», но на этот раз в вашей рабочей памяти, состоящей из доски, есть место всего для 100 слов. Как только пьеса начнётся, вы запишете первые 100 слов, которые услышите, снова пропуская все повторы. Когда место будет заполнено, нажмите на паузу и подбросьте монетку для каждого слова. Орёл — слово остаётся в списке; решка — вы его удаляете. После этого предварительного раунда у вас останется около 50 разных слов.
Теперь вы переходите к тому, что команда называет раундом 1. Продолжайте читать «Гамлета», добавляя новые слова по ходу дела. Если вы встретите слово, которое уже есть в вашем списке, снова подбросьте монетку. Если выпадет орёл, вычеркните слово; если решка — слово останется в списке. Продолжайте в том же духе, пока на доске не останется 100 слов. Затем снова удалите в случайном порядке примерно половину, основываясь на результатах 100 подбрасываний монетки. На этом первый раунд завершён.
Далее переходите ко второму раунду. Продолжайте, как в первом раунде, только теперь мы усложним задачу. Когда вы дойдёте до повторяющегося слова, снова подбросьте монетку. Если выпадет орёл, вы удалите его, как и раньше. Но если выпадет решка, подбросьте монету второй раз. Оставляйте слово, только если выпала вторая решка. Как только вы заполните доску, раунд закончится ещё одной очисткой примерно половины слов, основанной на 100 бросках монеты.
В третьем раунде, чтобы оставить слово, вам потребуется три решки подряд. В четвёртом раунде вам понадобится четыре решки подряд. И так далее.
В конце концов, в k-м раунде вы дойдёте до конца «Гамлета». Смысл упражнения заключается в том, чтобы убедиться, что каждое слово, в силу случайного выбора, имеет одинаковую вероятность оказаться там: 1/2^k. Если, например, в конце «Гамлета» в вашем списке оказалось 61 слово, а процесс занял шесть раундов, вы можете разделить 61 на вероятность, 1/2^6, чтобы оценить количество отдельных слов — в данном случае это 3 904. (Легко понять, как работает эта процедура: предположим, у вас есть 100 монет, и вы подбрасываете каждую по отдельности, сохраняя только те, что выпали решками. В итоге у вас будет около 50 монет, и если кто-то разделит это число на вероятность ½, то сможет догадаться, что изначально монет было около 100.)
Вариям и его коллеги математически доказали, что точность этой техники зависит от объёма памяти. В «Гамлете» ровно 3 967 уникальных слов. (В экспериментах с памятью на 100 слов средняя оценка после пяти запусков составила 3 955 слов. При памяти в 1 000 слов среднее значение улучшилось до 3 964. «Конечно, — говорит Вариям, — если память настолько велика, что в ней помещаются все слова, то мы можем добиться 100-процентной точности».
«Это отличный пример того, что даже для базовых и хорошо изученных проблем иногда находятся очень простые, но неочевидные решения, которые ещё предстоит найти», — сказал Уильям Кушмаул из Гарвардского университета.
Комментарии (46)
MzMz
13.06.2024 16:47+10HyperLogLog вроде выглядит ничуть не хуже по оценке сложности и памяти?
mentin
13.06.2024 16:47+3У HLL ещё много полезных возможностей, например можно объединять независимо посчитанные скетчи, оценивать кардинальность пересечения и разницы. Интересно, если ли аналогичные тут.
Но этот гораздо проще. Хотя если значения переменной длины и большие, то придется всё равно накапливать хеши вместо значений, и все опять усложнится.
muxa_ru
13.06.2024 16:47+17Ага, а пользователю этот результат покажут как ТОЧНЫЙ, а не как статистическое шмуду-вуду.
Ivan22
13.06.2024 16:47а ты думаешь число просмотров на ютубе сейчас точное показывается??? ха-ха-ха
ArtTwink
13.06.2024 16:47+2Мне кажется подсчёт уникальных элементов не только (и не столько) для Ютубовских просмотров нужен :)
muxa_ru
13.06.2024 16:47+1Я думаю, что некорректно сравнивать универсальный метод оценки доли уникальных элементов и узкоспециализированное решение для анализа посещаемости.
Анализ посещаемости.в первую очередь требует не механизма подсчёта уникальных элементов, а выработки критериев уникальности.
ready4wisdom
13.06.2024 16:47+9Смысл упражнения заключается в том, чтобы убедиться, что каждое слово, в силу случайного выбора, имеет одинаковую вероятность оказаться там: 1/2^k
Текст статьи создает ощущение объяснения алгоритма "на пальцах". Но при попытке задуматься над обоснованностью утверждений проваливаешся в "кроличью нору".
Итак, алгоритм на каждой итерации вдвое понижает шансы остаться в списке слову для которого нашелся очередной дубль и из набранной очередной порции просто удаляет половину. Снимаю шляпу перед тему, кому очевидно, что число уникальных элементов можно посчитать по приведенной формуле после такого алгоритма.
adante
13.06.2024 16:47У меня это в голове сразу проассоциировалось с рядом
1/2 +1/4 + 1/8….
И сумма вероятностей получается близка к 1
r31t3r
13.06.2024 16:47+1Как вариант можно подобрать количество бросков монет по количеству элементов в исходном массиве, результаты бросков записать в двоичном виде, перевести в десятичную систему счислений и представить это как приблизительный результат.
Может быть он и не будет точным, зато очень эффективным
vit84
13.06.2024 16:47+38Правильный заголовок должен быть: способ ПРИБЛИЗИТЕЛЬНОГО подсчёта уникальных элементов
Zara6502
13.06.2024 16:47Всё становится ещё хуже. Что, если вы — Facebook, и вам нужно подсчитать количество отдельных пользователей, которые заходят на сайт каждый день, даже если некоторые из них заходят с нескольких устройств и в разное время? Теперь мы сравниваем каждый новый вход со списком, который может исчисляться миллиардами.
статью всю не читал, но у меня вопрос сразу по вот этому конкретному примеру. Доступ же к элементу конкретного пользователя это О(1), соответственно подсчёт пользователей которые зашли сегодня, это O(n). Отсюда не ясно, зачем "сравниваем каждый новый вход со списком". Там же простая выборка из фибоначчиевой кучи, то есть О(1), для n элементов базы и одно условие с датой "сегодня".
можно сделать вообще проще, входы каждого дня складывать в разные базы, ну или список списков с индексом текущего дня. Тогда у вас вся сегодняшняя база, это и есть все кто заходил сегодня. Точно так же О(1) до конкретного пользователя и O(n) для всего списка, только n(сегодня) сильно меньше чем n(всей базы).
mentin
13.06.2024 16:47+1Это всё про логи, а не базы данных. Есть терабайты логов, для каждого пользователя там могут быть тысячи или больше записей. Надо всё прочитать (желательно в один проход), и подсчитать. Писать в базу на каждую прочитанную запись - база умрет, считать желательно в памяти. Плюс считать надо много разных вещей, заранее часто не известных, скажем читать лог и считать пользователей кликнувших на чью-то рекламу
Zara6502
13.06.2024 16:47Логи - это функция, а не способ представления информации. Вам никто не запрещает логи держать в виде таблиц. Вопрос не в том "можно/нельзя", а в том - как потом вы с этим работать собираетесь. Если вам нужно быстро получать доступ к чему-то, то и организовывать доступ вы будете не просто всё сваливая в кучу. Так что ваше замечание считаю просто неправильным подходом к хранению данных. То есть вы сами себе создаёте проблему.
Писать в базу на каждую прочитанную запись - база умрет
А в чем принципиальное отличие базы от текстового лога? ОЗУ то же, ЦПУ тот же, диски - те же, почему от записи в текстовик ничего не умрёт, а именно от записи в базу вдруг умрёт.
считать желательно в памяти
Так СУБД для этого и используются.
Плюс считать надо много разных вещей, заранее часто не известных, скажем читать лог и считать пользователей кликнувших на чью-то рекламу
С больной головы на здоровую не перекладывайте. Мы рассматриваем только конкретный вопрос описанный в статье, а вы уже все проблемы фейсбука притянули.
mentin
13.06.2024 16:47Вам никто не запрещает логи держать в виде таблиц.
Никто кроме здравого смысла. Логи в таких системах каждый из тысяч фронтэнд серверов пишет отдельно, с минимальными издержками. Каждый датацентр изолированно от других. Потом уже всё собирается и обрабатывается.
Не знаю уж как именно вы собираетесь организовывать базу, одну на всех судя по описанию, и фронтэнд из Австралии будет делать INSERT в базу в США? Или таки отдельно? Но тогда вы ничего не изменили, все равно число записей на много порядков больше числа пользователей и надо их обрабатывать, как выше. Только потеряли порядок или два производительности.
А в чем принципиальное отличие базы от текстового лога?
А вы попробуйте. Писать в локальный файл и делать INSERT в таблицу, а ещё лучше как в вашем оригинальном описании - UPDATE таблицы с пользователями.
vvzvlad
13.06.2024 16:47А типа сейчас при входе пользователя в базу ничего не пишется по вашему? Никакой смены статуса “онлайн”/“был полчаса назад” например?
Aquahawk
13.06.2024 16:47Нету у памяти доступа за O(1), особенно когда памяти много, особенно когда это не влазит сначала в оперативу, а потом и сервер вообще
https://habr.com/ru/articles/309394/
Psychosynthesis
13.06.2024 16:47Ну, скажем, поиск по мапе это log(n), у меня вопрос настолько ли это затратно, что имеет смысл немного ускорять алгоритм ради приблизительного подсчёта.
wataru
13.06.2024 16:47+2Тут главное приемущество - не ускорение, а то, что не надо в памяти все элементы держать. Можно обрабатывать гигабайты логов, храня в памяти лишь несколько килобайт элементов. Если вы посмотрите на оригинальную статью, то там огромный упор делается на ограниченном размере используемой памяти. А сложность работы алгоритма по времени вообще, кажется, не упоминается.
aamonster
13.06.2024 16:47+1Тут речь не о "немного ускорить", а о том, чтоьы не выделять O(n) памяти.
Panzerschrek
13.06.2024 16:47+2Главный вопрос - а какова область применения данного алгоритма? Сейчас ведь памяти много, можно хоть миллиарды элементов хранить и не полагаться на вероятностные алгоритмы.
Zara6502
13.06.2024 16:47ну как вариант - контроллер в стиральной машине со встроенной 512 байт ОЗУ, идёт поток данных от датчиков, не слишком важно знать что у вас точно 394 события, достаточно понимать что их около 400. Экономия доллара на модуле памяти и еще 8 долларов на проектировании платы, напайке и габаритах. ИМХО
KirpaPuto
13.06.2024 16:47+7Протечка, перегрев, наличие воды, закрытая крышка, таймер... чем можно пренебречь или среагировать дожно-положительно?
seriych
13.06.2024 16:47+4Не так уж и много памяти сейчас. Вот есть у нас несколько юзеров БД, каждый запустил запрос на количество уникальных по нескольким колонкам. А среди них еще и строковые могут быть. И на практике это реально кучу памяти отъедает. Плюс это еще и медленно. Поэтому приблизительные алгоритмы рулят, особенно которые дают точный результат на маленьком числе групп, а неточность возникает только после тысяч.
Есть разница между тем, что запрос отожрал всю память и если повезет, то не упал и выполнился за время пока ты кофе пошел сделать, и тем, что запрос ничего не отожрал и выполнился за пару секунд (но может быть выдал 123456700 вместо 123456789, какой ужас).
Panzerschrek
13.06.2024 16:47+2каждый запустил запрос на количество уникальных по нескольким колонкам
Какой-то случай слишком абстрактный. В каких конкретных случаях нужны такие запросы на количество всех уникальных элементов?
На счёт потребления памяти - если там миллионы элементов, то её хватит. Если миллиарды - хватит при умелом обращении и достаточном количестве оперативки (десятки гигабайт).
В случаях с приблизительными запросами можно тогда вообще, не изобретать каких-то приблизительных алгоритмов, а проводить точный подсчёт и просто кешировать результат на какое-то время.Ivan22
13.06.2024 16:47+1в аналитике данных таких запросов дофига. Все эти уникальные клиенты за сегодня, уникальные товары за месяц, или уникальные теги в твиттере.
Да, так сейчас и делается где можно - результат кэшируется но не везде это возможно, а как раз дистинкты и плохо агрегеруются. Если например сумму продаж ты можешь просто хранить для каждого магазина, а потом если в отчете надо весь город - просто сложить все магазины - и вот тебе сумма. То с уникальными товарами в тех же магазинах так не выйдет. Если есть 100 уников в одном и втором магазине - то в двух вместе их будет не 200, а X (от 100 до 200) т.е. надо пересчитать заново, для группы. И то есть либо всегда считать дистинкты на лету (что очень медленно) либо хранить их для КАЖДОЙ комбинации измерений (что оо-о-о-чень много данных)
Panzerschrek
13.06.2024 16:47Компании, у которых столько клиентов, что не хватит памяти пересчитать их всех, очень редки. У остальных же подсчёт их нескольких тысяч клиентов займёт доли секунды. С товарами ситуация аналогична - если это не Amazon, то памяти на их пересчёт хватит.
Описанный же в данной статье алгоритм нужен только для тех случаев, когда реально поток данных колоссален и в память всё не умещается, и посему приходится жертвовать точностью ради самой возможности работы алгоритма.Ivan22
13.06.2024 16:47ты путаешь теплое с мягким. В обычной торговой компании 10000 уникальных товаров, но миллирды фактов продаж. И менеджеру постоянно хочется то уникальные по этому городу, то уникальные на этой неделе, то уникальные по этой акции. И на каждую смену фильтра в репорте надо быстренько желательно за 2 секунды посчитать это из миллирада продаж.
muxa_ru
13.06.2024 16:47Сейчас ведь памяти много, можно хоть миллиарды элементов хранить и не полагаться на вероятностные алгоритмы.
Это в теории и для частного пользователя, где можно воткнуть в комп лишние ресурсы и развлекаться.
А когда промышленное производство на продажу, там между указанными в тексте 100 словами и 150 словами может находиться граница окупаемости.
thousbe
13.06.2024 16:47+10В заголовке обещают подсчёт, а в теле статьи описывают оценку количества слов.
Rebelqwe
13.06.2024 16:47взял Гамлета http://lib.ru/SHAKESPEARE/hamlet5.txt
В пьесе 30 557 слов
Это неверно, в пьесе 54 251 слово, судя по свойствам файла в notepad++
допустим имелась ввиду английская книга, но уже странно. При переводе одно слово обращалось в два?
засовываем в подсчёт уникальных слов. https://planetcalc.ru/3204/
В "Гамлете" ровно 3 967 уникальных слов.
Тоже не верно, уникальных слов 14425, Да и в принципе серьезно кто-то поверит, что у Шекспира был словарный запас в 4000 слов, как у среднего семиклассника, который 3 года учит английский как иностранный? Или в то, что при переводе на русский одно слово превращается в 5?
Попробую конечно прописать и запустить именно этот алгоритм на Гамлете, но тут даже по ошибкам в фактологии уже явно что-то не так, попахивает недоброкачественными выводами или сознательными искажениями действительности.
TheMrWhite
13.06.2024 16:47wc hamlet_TXT_FolgerShakespeare.txt > 6080 32004 182866 hamlet_TXT_FolgerShakespeare.txt в данном файле гамлет на айнглийском, если убрать названия сцен/актов, их номера, разделители типа ====== то похоже на правду, что там действительно 30к+ слов
файл отсюда https://www.folger.edu/explore/shakespeares-works/download/#hamletRebelqwe
13.06.2024 16:47Уникальных слов в указанном Вами варианте Гамлета через https://planetcalc.ru/3204/ - 5192
А https://ciox.ru/count-the-number-of-unique-words даёт более похожее на правду число 9140
Возможно это разница между приведенными в lowercase словами и уникальными без приведения.
TheMrWhite
13.06.2024 16:47на первом сайте подсчёт тоже так себе, если такие ошибки исключить думаю число упадёт до искомых ~4k
вот как он посчитал - What(203) think(49) you(553) on(134) 't(81)?
что это за слово 81раз встречается 't? )))
seriych
13.06.2024 16:47Можете сами придумать регулярку, которая слова вычленяет на ваш взгляд правильно, и заменить тут простую \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, но занимает меньше памяти. Но тут данных мало, если найдется файлик пожирнее, разница будет больше.
ArtTwink
13.06.2024 16:47+3допустим имелась ввиду английская книга
Эта статья - перевод, естественно они использовали не русский перевод Гамлета
R0bur
13.06.2024 16:47Алгоритм работает для любого списка, в который элементы поступают по одному — как слова в речи, товары на конвейере или автомобили на шоссе.
Что-то мне кажется, что играет роль ещё и вид распределения поступающих элементов. Если оно будет не равномерным, то точность может серьёзно ухудшиться. Тогда область применимости этого метода ещё больше сужается.
wataru
13.06.2024 16:47Там доказательство есть. Точность не зависит от распределения элементов во входном потоке.
aamonster
Хм. Про фильтр Блума никто даже не вспомнил?
Хотя алгоритм из статьи выглядит более шустрым.
Да, и при переводе потерялись верхние индексы – 2⁶ превратилось в 26.
artptr86
Фильтр Блума же не про подсчёт уникальных элементов, а про проверку нахождения в множестве.
aamonster
Именно! У нас поток элементов, каждый проверяем фильтром и если не было – добавляем в него.
Подход даст систематическую погрешность (ложно-положительные срабатывания фильтра – занижение числа уникальных элементов), но её можно оценить и учесть (тогда погрешность станет меньше, но уже может быть и вверх, и вниз)
Но это так, баловство на самом деле, тут уже вспомнили HyperLogLog, который требует всего один хэш, он явно будет эффективнее.
artptr86
Похоже, что вы изобрели алгоритм Флажоле–Мартина (1984). HyperLogLog развивает их идею, но с большей точностью.
Rebelqwe
Не важно, что не про подсчёт, про него всё равно никто не вспомнит.