2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Количество уникальных элементов множества
Сообщение07.05.2024, 16:08 
Заслуженный участник


20/08/14
11668
Россия, Москва
Всех приветствую.
Встала такая практическая задача: хотя бы грубо и лучше сверху оценить количество уникальных элементов некоторого итерационно вычисляемого множества. Т.е. на каждом шаге к имеющемуся множеству применяется некий оператор, добавляющий (или не добавляющий) в него элементы. После нескольких первых шагов элементы добавляться перестают (оператор переводит элементы только в уже существующие) и размер множества застывает - вот этот размер и надо бы оценить. Порядок размера множества в точности неизвестен, но самая грубая оценка даёт много триллионов элементов, ни в память ни на диск полный список не влезает. Каждый элемент множества - число в интервале $0\ldots2^{128}$ (16 байтов). Если это чем-то поможет, то единиц в этом числе максимум четверть (скорее даже 28-30), но как это применить не представляю.

Основная трудность - проверить что новый вычисленный элемент уже встречался.

Какие методы знаю:
0. Тривиальный битовый массив всех возможных состояний элементов. Но объём $2^{128}$ битов за гранью даже фантастики.
1. Сортированный массив всех элементов. Проверка наличия относительно быстрая $O(\ln n)$, но вот добавление элемента - смерть, пересортировка массива.
2. Двоичное дерево поиска. В каждом узле - сам элемент множества (16 байтов) плюс 2-3 указателя (8-24 байтов). Всё бы хорошо, все операции тоже относительно быстрые $O(\ln n)$, но хотелось бы ещё быстрее.
3. Несколько последовательных (в следующую класть лишь коллизии предыдущей) хеш-таблиц с разными хеш-функциями (одной мало или слишком трудно вычислимая). Проверка наличия элемента моментальная $O(1)$, удаление (оно требуется на нескольких первых шагах пока суммарный объём меньше миллионов элементов) тоже в общем не сильно сложно, вопрос только в объёме.
3а. Не хранить в хеш-таблицах сами числа/элементы, только бит наличия (фактически гарантированного отсутствия) элементов с заданным хешем, памяти всего 1 бит на элемент, с коллизиями разбираться отдельно в надежде что их будет намного меньше.
4. Сделать хеш-таблицы не последовательными, а одновременными, как в китайской теореме об остатках. Пока размеры каждой хеш-таблицы меньше суммарного размера множества будет потеря информации и соответственно оценка выйдет сверху - вопрос насколько грубой окажется. Ну и с удалением элементов засада (но в принципе обходимая).

Насколько понимаю ни один из методов не позволяет даже примерно оценить количество если оно сильно больше размера памяти (на крайний случай диска). А на то есть подозрения.
Запускать несколько (реально как бы не миллионы) раз для подсчёта таблиц/массивов по частям тоже не вариант (в основном из-за итерационности построения множества).

Есть какие-то ещё хитрые способы? Или ограничение в бит/элемент не улучшаемо (как и подозреваю)? Даже если отказаться от точного подсчёта и допустить не слишком большую (максимум полпорядка) погрешность?

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 16:18 


17/10/16
4744
Dmitriy40
Похоже на задачу нахождения длины цикла для конечного автомата. Кажется, в алгоритмах генерации псевдослучайных чисел эта длина имеет важное значение.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 16:40 


14/01/11
3017
А исходное множество, с которого стартуют итерации, допускает сколько-нибудь компактное описание?

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 16:43 
Заслуженный участник
Аватара пользователя


16/07/14
9066
Цюрих
Оператор работает поэлементно или на всём множестве сразу?
Если на всем сразу - то непонятно, как можно обойтись без хранения всего множества.
Если поэлементно - то всё равно надо же его как-то хотя бы применить к каждому элементу, а то вдруг у нас там есть один с орбитой на почти все возможные строки, а остальные моментально зацикливаются.
Вообще, можно ли что-то хорошее сказать про оператор?

Если задачу можно как-то свести к "нам прилетают элементы, посчитать число уникальных", то это известная штука https://en.wikipedia.org/wiki/Count-distinct_problem.

3a - это Вы, вроде бы, переизобретаете фильтр Блума.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 16:54 
Заслуженный участник


20/08/14
11668
Россия, Москва
sergey zhukov
Ну ... Если только по постановке задачи, так-то там зависимость от одного числа, а тут в общем почти от всего множества (реально где-то от 1/5-1/4). Да и функция (оператор) возвращает не одно число, а множество новых элементов (размер растёт сначала раз в 5-7 на каждом шаге, потом в 3, потом в 1.5, потом на проценты и в конце на десятки штук). Конечно каждый новый элемент вычисляется всего по одному элементу множества, не сразу от многих, зато и точной закольцованности нет, лишь итоговая замкнутость/закрытость (если не ошибаюсь в термине) множества относительно оператора "рождения" (все новые элементы уже присутствуют в множестве).

Sender в сообщении #1638375 писал(а):
А исходное множество, с которого стартуют итерации, допускает сколько-нибудь компактное описание?
Да, оно из одного элемента (для простоты можно считать равного $2^{128}-1$, все единицы в числе). Каждый шаг - обнуление некоторого набора битов в числе, что приводит к новому числу. Количество наборов обнуляемых битов - мало, максимум десятки на каждом шаге, но каждый применяется к каждому элементу множества.
По наблюдениям за аналогичными задачами в итоге остаётся всегда одно число из всех нулей (т.е. просто 0), плюс все варианты с одной единицей, плюс 30%-40% вариантов с двумя единицами, плюс и так далее, дальше очень сильно далеко не все возможные варианты.

mihaild
Поэлементо. Более того, количество единиц в числе (элементе множества) может только уменьшаться (или оставаться тем же), увеличиваться не может. Но шагом считается применение всего комплекта наборов обнуляемых бит к каждому элементу множества (and двух чисел).
Оператор - просто and набора масок (на каждом шаге своих, десятки штук) и всех элементов множества в виде чисел.
За ссылки спасибо, сейчас поизучаю.

UPD. О, HyperLogLog похоже решает задачу с хорошей точностью. Осталось понять насколько он трудоёмок, а то всего элементов надо проверить несколько квадриллионов (больше 1e15), но есть надежда что уникальных среди них максимум триллионы.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 16:58 
Заслуженный участник
Аватара пользователя


16/07/14
9066
Цюрих
Т.е. формально, если $A_i$ - множество элементов на $i$-м шаге, $B_i$ - множество масок, то $A_{i + 1} = \bigcup\limits_{\substack{x \in A_i\\ y \in B_i}} \{x \& y\}$ (для простоты считаем, что $\overline{0} \in B_i$)?

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 17:06 
Заслуженный участник


20/08/14
11668
Россия, Москва
mihaild
Если я правильно понимаю обозначения, то да. $\&$ считаю битовой операцией.

-- 07.05.2024, 17:15 --

mihaild в сообщении #1638376 писал(а):
3a - это Вы, вроде бы, переизобретаете фильтр Блума.
Да, похоже, только думал хранить не в одном массиве. Ведь читал же про него, очень понравился, но тогда куда применить не знал.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 17:42 
Аватара пользователя


29/04/13
8011
Богородский
Dmitriy40, а это разве не наша задача из
«кортежи последовательных простых. ключ к 19-252» ? Только обобщённая.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 17:46 


14/01/11
3017
Вообще, элементы множества можно рассматривать как таблицы истинности булевых функций $7$ переменных, тогда можно несколько сократить расчёты за счёт симметрии как минимум перестановок переменных. Вот, например, последовательность классов эквивалентности всех булевых функций от n входов A003181.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 18:03 
Заслуженный участник


20/08/14
11668
Россия, Москва
Yadryara
Это скорее подзадача оттуда - оценить требуемый суммарный размер ww[], по возможности не вычисляя их все. А так да, множество здесь это как раз все ww[] в сумме оттуда (если забыть про счётчик повторов).
А то гложет меня подозрение что нифига оно в память не влезет, даже вместе с диском.

Sender
А почему 7 переменных? Как-то число 7 у меня нигде не фигурирует.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 18:07 


14/01/11
3017
$2^7=128$. Впрочем, вряд ли от этого будет какой-то толк, если множества масок не симметричны относительно перестановок переменных.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 18:32 
Заслуженный участник


20/08/14
11668
Россия, Москва
Ну, немало масок как раз симметричны, но не все, если только про зеркальную симметрию, то пожалуй до четверти имеют симметричную копию.
Вообще маска - число из всех единиц, за исключением 2-3 (для практически интересных шагов) нулевых битов на расстоянии простого числа p с почти всеми возможными смещениями (которых не p, а p-19 штук для p>42). Насчёт каких именно симметрий/перестановок кроме зеркальных маски симметричны - не понимаю. И даже при симметрии маски не вижу выигрыша - ведь элементы в множестве не обязаны быть симметричными. Да, при каких-то вариантах сочетаний маски и элемента симметрия позволяет уменьшить вычисления, но как-то их маловато, навскидку. А проверка симметрий элементов множества весьма накладно (масок можно выполнить заранее, это понятно). Не, похоже до меня не доходит идея многих симметрий.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 18:43 
Заслуженный участник
Аватара пользователя


16/07/14
9066
Цюрих
Dmitriy40, а время работы $|A_0| \cdot \prod_i |B_i|$ (все возможные пути получения элемента) устраивает? Если да, то это в точности count distinct.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 19:44 
Заслуженный участник


20/08/14
11668
Россия, Москва
mihaild в сообщении #1638392 писал(а):
Dmitriy40, а время работы $|A_0| \cdot \prod_i |B_i|$ (все возможные пути получения элемента) устраивает? Если да, то это в точности count distinct.
Ну-у-у... Вообще говоря - нет, не устраивает. Засада в том что для желаемой оценки надо посчитать по всем простым до 89, а это порядка 2e26 вариантов. Нереально.

Прикол в том что само решение проблемы должно найтись при проверке до 67 (ну пусть 71 это уж 146%), а для оценки его вероятности (для чего и хочу здесь оценить требуемую память) надо считать сильно дальше ... Идиотизм. Пусть даже и операции сильно проще, но всё равно, 3e17 (для поиска решения) или 2e26 (для оценки его вероятности) итераций, никакая разумная константа в $O()$ это не нивелирует.

Похоже я замахнулся сильно не глядя, хотелки придётся урезать. Например оценить $|A_{59}|$ имея $A_{41}$ размером 31млн. Переход $41\to59$ требует $|B_{43}|\cdot|B_{47}|\cdot|B_{53}|\cdot|B_{59}|=24\cdot28\cdot34\cdot40=913920$ операций над всем $A$, 3e13 вариантов в итоге, и если уникальных станет достаточно много (порядка прикидки в 1e11), то всё, вах, невычисляемо. Так да, 3e13 операций устраивает.

Пока из англовики реального алгоритма не заметил (наивный не катит, а в CVM не разобрался).
HyperLogLog (как и потоковые алгоритмы) сильно опирается на равномерность хеш-функции, по идее она вообще не нужна, сами числа и так распределены неплохо, но вот насколько равномерно - неизвестно, надо изучать. На первый взгляд распределение вообще близко к смещённым нормальному или биномиальному (каким и должно быть), насколько это скажется на точности оценки пока не вкуриваю. Но ещё подумаю.

 Профиль  
                  
 
 Re: Количество уникальных элементов множества
Сообщение07.05.2024, 20:02 
Заслуженный участник
Аватара пользователя


16/07/14
9066
Цюрих
Точно посчитать почти наверняка не получится - даже вопрос о принадлежности нуля итоговому множеству NP-труден.

Еще кстати получается, что $A_0$ симметрично с $B_i$. Что это может дать...

Ну понятно что можно попробовать найти такой набор индексов, что $\left| \mathop{\&}\limits_{i \in S} B_i\right| \ll \prod\limits_{i \in S} |B_i|$. Но не очень понятно, как это делать.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group