Войти
ФлеймФорумПрограммирование

Хитрый контейнер и сжатие / криптография

Страницы: 1 2 3 Следующая »
#0
0:14, 11 июля 2018

Тэкс... В общем ребят, задача не тривиальная, есть у меня, ну скажем, 1 000 000 разных чисел типа unsigned int, мне их нужно по одной штуке в рандомном порядке и возможно с повторами (то есть одно число могу пытаться класть много раз) класть в некий контейнер типа std::set / map и пр, в котором могут храниться только уникальные числа, но что бы этот контейнер сам был крайне мал по размеру, желательно размером с тот же unsigned int.
Задача такова, что сами числа в этом контейнере мне вообще не нужны и доставать их оттуда я не собираюсь, главное, что бы при попытке положить в контейнер я бы мог проверить, клал ли я туда ранее текущее число или нет. То есть мне как бы нужно проверять числа на "а не использовал ли я его уже ранее"...     
Конечно первое, что приходит в голову, сделать этот контейнер в виде простого  unsigned int и побитово складывать туда числа, проверяя при попытке положить операцией & мол я не входят ли все биты текущего числа в уже длинное число-контейнер... но разумеется, это не сработает, т.к. всё это будет с нахлёстом, то есть:
[для примера 4-х битный бинарный вид]
число-контейнер:  0000

число 1: 0101
число 2: 1000
число 3: 0001

я кладу в контейнер числа по очереди:

контейнер: 0000 +
число 1:    0101    (такой битовой комбинации в контейнере нет)
=                0101

контейнер: 0101+  (после первой операции уже стал таким)
число 2:    1000
=                1101  (такой битовой комбинации в контейнере нет)

контейнер: 1101+  (после второй операции уже стал таким)
число 2:    0001
=                0001  а вот такая битовая комбинаций уже как бы есть, хотя это число я туда и не клал...

Короче, вы ж поняли о чём я? :)  Есть идеи?


#1
0:31, 11 июля 2018

-=MASTER=-
> Короче, вы ж поняли о чём я? :) Есть идеи?
Фильтр Блума?

#2
0:31, 11 июля 2018

Разреженный битсет.
Разобьём всё пространство флагов на блоки размером N. Тогда числу n будет соответствовать бит n%N блока n/N.
Для хранения блоков можно использовать std::map<int, uintN_t> или std::unordered_map<int, uintN_t>, в зависимости от планируемого количества установленных бит.
Для установки бита, разумеется, используется |= 1 << (n%N), для снятия - &= ~(1 << (n%N)), для считывания - & (1 << (n%N)) != 0.

#3
0:50, 11 июля 2018

exchg
> Фильтр Блума?
да не...
Delfigamer
> Разобьём всё пространство флагов на блоки размером N. Тогда числу n будет
> соответствовать бит n%N блока n/N.
хмм, не очень понял, как это может работать, ведь разряженный бит сет или нет, одно число, например 0010 может входить сумму двух (1010 и 0011), то есть всё равно биты могут накладывать или я чего-то не понял?
Вообще по сути мне нужен набор таких чисел, у каждого из которых вообще все биты отличаются друг от друга...  Короче говоря, мне нужен хотя бы миллион чисел, который я могу побитово складывать и проверять на каждом складывание, а не было ли уже такого числа...
Да..наверное всё таки тут единственное решение - для миллиона чисел нужно миллион битное число-контейнер для хранения (на каждое число 1-му биту) :(

#4
4:49, 11 июля 2018

-=MASTER=-
> для миллиона чисел нужно миллион битное число-контейнер

Ну, миллион unsigned int-ов занял бы 4 Мб памяти только самих данных, а в чём-нибудь типа std::set их бы еще раздуло.
Битовая упаковка же даёт массив на 131 Кб. Экономия и скорость налицо.
Тебе еще предложили разбивать битовое поле на динамически выделяемые сегменты на случай если по природе своей в задаче бывают большие промежутки не встречающихся значений.

#5
5:37, 11 июля 2018

... а также на полностью заполненные блоки и на сами блоки ввести свой битсет. Блоки можно объединять. Но такое усложнение под очень большие числа.

#6
10:12, 11 июля 2018

=A=L=X=
> Ну, миллион unsigned int-ов занял бы 4 Мб памяти только самих данных
=A=L=X=
> Битовая упаковка же даёт массив на 131 Кб. Экономия и скорость налицо.
дело в том, что задача NxN, то есть таких вот контейнеров по миллион чисел у меня должно быть так же миллион и всё это нужно читать и обрабатывать на GPU, то есть это получается как если бы у тебя в коде шейдера каждый пиксель читал бы по эти 4 мегабайта (ну или даже хотя бы по 131 кб) из SSBO, короче это дохлый номер, буду думать как уйти от этого...

#7
10:17, 11 июля 2018

Теме не хватает вореций.

+ Показать

#8
10:42, 11 июля 2018

=A=L=X=
> Тебе еще предложили разбивать битовое поле на динамически выделяемые сегменты
> на случай если по природе своей в задаче бывают большие промежутки не
> встречающихся значений.
или если есть плотные заполненные области, такое тоже хорошо RLC алгоритмом жмется

#9
11:01, 11 июля 2018

-=MASTER=-
> желательно размером с тот же unsigned int.
Наивный ;) По первым прикидкам, тут мегабайт 6 надо. 2 мегабайта под быстрый фильтр Блума и четыре мегабайта под бинарное дерево с данными, если фильтр вдруг выдал положительное срабатывание.

#10
11:04, 11 июля 2018

а..ладно, забейте, собственно я и не наделялся на чудо, буду менять алгоритм :)

#11
11:11, 11 июля 2018

-=MASTER=-
> я и не наделялся на чудо

Чудес не бывает, это да.
Ты расскажи, что за задача то. Может можно построить предположения по поводу диапазона чисел? Или допустимы ложно-положительные срабатывания?

#12
13:05, 11 июля 2018

Ogra
> Ты расскажи, что за задача то
да это вообще не графика, это AI... Ладно, тут ничего не поделаешь, буду исследовать другой подход, этот походу фейльнул. На то это и исследования, шаг вперёд, там тупик, два назад и в другую сторону...
Tonal
> Так а чем фильтр Блума не угодил?)
вот этим:

При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть)
#13
13:14, 11 июля 2018

-=MASTER=-
Опиши требования к алгоритму поподробнее. Какая должна быть сложность у вставки, поиска? Допустимы ли ложноположительные и ложноотрицательные случаи в поиске?

#14
14:05, 11 июля 2018

Panzerschrek[CN]
> Допустимы ли ложноположительные и ложноотрицательные случаи в поиске?
не допустимы
Panzerschrek[CN]
> Какая должна быть сложность у вставки, поиска?
ну конечно желательно O(1) :), но допускается и logN
главное требование к минимизации памяти, т.к. таких контейнеров должно быть так же много, как и самих чисел, то есть на N чисел N контейнеров

Страницы: 1 2 3 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.