Флейм
GameDev.ru / Флейм / Форум / Хитрый контейнер и сжатие / криптография

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

Страницы: 1 2 3 Следующая »
-=MASTER=-Удалёнwww11 июля 20180:14#0
Тэкс... В общем ребят, задача не тривиальная, есть у меня, ну скажем, 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  а вот такая битовая комбинаций уже как бы есть, хотя это число я туда и не клал...

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

exchgПостоялецwww11 июля 20180:31#1
-=MASTER=-
> Короче, вы ж поняли о чём я? :) Есть идеи?
Фильтр Блума?
DelfigamerПостоялецwww11 июля 20180:31#2
Разреженный битсет.
Разобьём всё пространство флагов на блоки размером 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.
-=MASTER=-Удалёнwww11 июля 20180:50#3
exchg
> Фильтр Блума?
да не...
Delfigamer
> Разобьём всё пространство флагов на блоки размером N. Тогда числу n будет
> соответствовать бит n%N блока n/N.
хмм, не очень понял, как это может работать, ведь разряженный бит сет или нет, одно число, например 0010 может входить сумму двух (1010 и 0011), то есть всё равно биты могут накладывать или я чего-то не понял?
Вообще по сути мне нужен набор таких чисел, у каждого из которых вообще все биты отличаются друг от друга...  Короче говоря, мне нужен хотя бы миллион чисел, который я могу побитово складывать и проверять на каждом складывание, а не было ли уже такого числа...
Да..наверное всё таки тут единственное решение - для миллиона чисел нужно миллион битное число-контейнер для хранения (на каждое число 1-му биту) :(

Правка: 11 июля 2018 0:51

=A=L=X=Постоялецwww11 июля 20184:49#4
-=MASTER=-
> для миллиона чисел нужно миллион битное число-контейнер

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

clcПостоялецwww11 июля 20185:37#5
... а также на полностью заполненные блоки и на сами блоки ввести свой битсет. Блоки можно объединять. Но такое усложнение под очень большие числа.
-=MASTER=-Удалёнwww11 июля 201810:12#6
=A=L=X=
> Ну, миллион unsigned int-ов занял бы 4 Мб памяти только самих данных
=A=L=X=
> Битовая упаковка же даёт массив на 131 Кб. Экономия и скорость налицо.
дело в том, что задача NxN, то есть таких вот контейнеров по миллион чисел у меня должно быть так же миллион и всё это нужно читать и обрабатывать на GPU, то есть это получается как если бы у тебя в коде шейдера каждый пиксель читал бы по эти 4 мегабайта (ну или даже хотя бы по 131 кб) из SSBO, короче это дохлый номер, буду думать как уйти от этого...
jaguardУчастникwww11 июля 201810:17#7
Теме не хватает вореций.
+ Показать
TonalПостоялецwww11 июля 201810:42#8
=A=L=X=
> Тебе еще предложили разбивать битовое поле на динамически выделяемые сегменты
> на случай если по природе своей в задаче бывают большие промежутки не
> встречающихся значений.
или если есть плотные заполненные области, такое тоже хорошо RLC алгоритмом жмется
OgraПостоялецwww11 июля 201811:01#9
-=MASTER=-
> желательно размером с тот же unsigned int.
Наивный ;) По первым прикидкам, тут мегабайт 6 надо. 2 мегабайта под быстрый фильтр Блума и четыре мегабайта под бинарное дерево с данными, если фильтр вдруг выдал положительное срабатывание.
-=MASTER=-Удалёнwww11 июля 201811:04#10
а..ладно, забейте, собственно я и не наделялся на чудо, буду менять алгоритм :)
OgraПостоялецwww11 июля 201811:11#11
-=MASTER=-
> я и не наделялся на чудо

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

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

Правка: 11 июля 2018 13:08

Panzerschrek[CN]Участникwww11 июля 201813:14#13
-=MASTER=-
Опиши требования к алгоритму поподробнее. Какая должна быть сложность у вставки, поиска? Допустимы ли ложноположительные и ложноотрицательные случаи в поиске?
-=MASTER=-Удалёнwww11 июля 201814:05#14
Panzerschrek[CN]
> Допустимы ли ложноположительные и ложноотрицательные случаи в поиске?
не допустимы
Panzerschrek[CN]
> Какая должна быть сложность у вставки, поиска?
ну конечно желательно O(1) :), но допускается и logN
главное требование к минимизации памяти, т.к. таких контейнеров должно быть так же много, как и самих чисел, то есть на N чисел N контейнеров

Правка: 11 июля 2018 14:06

Страницы: 1 2 3 Следующая »

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

2001—2018 © GameDev.ru — Разработка игр