Количество уникальных элементов множества

[Dmitriy40]

Всех приветствую.
Встала такая практическая задача: хотя бы грубо и лучше сверху оценить количество уникальных элементов некоторого итерационно вычисляемого множества. Т.е. на каждом шаге к имеющемуся множеству применяется некий оператор, добавляющий (или не добавляющий) в него элементы. После нескольких первых шагов элементы добавляться перестают (оператор переводит элементы только в уже существующие) и размер множества застывает - вот этот размер и надо бы оценить. Порядок размера множества в точности неизвестен, но самая грубая оценка даёт много триллионов элементов, ни в память ни на диск полный список не влезает. Каждый элемент множества - число в интервале $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. Сделать хеш-таблицы не последовательными, а одновременными, как в китайской теореме об остатках. Пока размеры каждой хеш-таблицы меньше суммарного размера множества будет потеря информации и соответственно оценка выйдет сверху - вопрос насколько грубой окажется. Ну и с удалением элементов засада (но в принципе обходимая).

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

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

[sergey zhukov]

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

[Sender]

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

[mihaild]

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

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

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

[Dmitriy40]

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), но есть надежда что уникальных среди них максимум триллионы.

[mihaild]

Т.е. формально, если $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$)?

[Dmitriy40]

mihaild
Если я правильно понимаю обозначения, то да. $\&$ считаю битовой операцией.

-- 07.05.2024, 17:15 --

mihaild в сообщении #1638376 писал(а):

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

Да, похоже, только думал хранить не в одном массиве. Ведь читал же про него, очень понравился, но тогда куда применить не знал.

[Yadryara]

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

[Sender]

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

[Dmitriy40]

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

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

[Sender]

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

[Dmitriy40]

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

[mihaild]

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

[Dmitriy40]

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 (как и потоковые алгоритмы) сильно опирается на равномерность хеш-функции, по идее она вообще не нужна, сами числа и так распределены неплохо, но вот насколько равномерно - неизвестно, надо изучать. На первый взгляд распределение вообще близко к смещённым нормальному или биномиальному (каким и должно быть), насколько это скажется на точности оценки пока не вкуриваю. Но ещё подумаю.

[mihaild]

Точно посчитать почти наверняка не получится - даже вопрос о принадлежности нуля итоговому множеству NP-труден.

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

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