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

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

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

-=MASTER=-
> но допускается и logN
> главное требование к минимизации памяти

Ну тогда всё просто - используй дерево диапазонов. Других способов сделать, как тебе надо, я не вижу.


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

-=MASTER=-
Как значения распределены? Равновероятно от 0 до MAX_INT?

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

Ogra
> Как значения распределены? Равновероятно от 0 до MAX_INT?
не имеет значения, ну пусть будет так.

#18
21:33, 11 июля 2018

-=MASTER=-
> таких контейнеров должно быть так же много, как и самих чисел, то есть на N
> чисел N контейнеров

А что это за такая странная зависимость?

-=MASTER=-
> не имеет значения, ну пусть будет так.
Плохо ;)

#19
9:30, 12 июля 2018

Ogra
> А что это за такая странная зависимость?
ой...да там долго рассказывать, но в двух словах, но если провести аналогию с графикой, представь, что у тебя есть картинка/текстура и на ней есть разноцветные пиксели, у каждого пикселя цвет может иметь id от 1 до 1 000 001 (ну просто миллион цветов), какой это реально цвет - не имеет значения (это всего лишь аналогия). Пиксели не все разные, очень много повторов, то есть на картинке много пикселей с одинаковым ID цвета, ну так вот алгоритм выглядит как NxN, то есть представь, код шейдера каждого пикселя делает перебор по всем остальным, то есть каждый из миллиона пикселей на картинке (да, из тоже 1 000 000), обращается ко всем другим (кроме себя), короче NxN. Так вот, что этот пиксель делает, он суммирует цвета, но суммирует не просто всё подряд, а суммирует только уникальные цвета, то есть если какой-то цвет с определённым ID он уже добавил в свою внутреннюю сумму, то его добавляют уже не нужно, а учитывая, что повторов на картинке много, случая отброса повтора очень частые. То есть ему при обращение к очередному пикселю нужно проверить, а не просуммировал ли она уже ранее цвет с таким-то Id... Ну вот как-то так...

#20
9:50, 12 июля 2018

-=MASTER=-
> представь, что у тебя есть картинка/текстура
Одна картинка? Если так, нельзя ли все просуммировать один раз и раздать пикселям (а они уже пусть решают, что с этим делать)

> может иметь id от 1 до 1 000 001
Вот смотри, уже 20 бит, а не 32.

-=MASTER=-
> очень много повторов, то есть на картинке много пикселей с одинаковым ID цвета
О, не равновероятное распределение, можно попробовать пожать Хаффманом, и получить, скажем, в среднем 10 бит.

#21
12:12, 12 июля 2018

Ogra
> Одна картинка?
нее...она постоянно меняется
Ogra
> Вот смотри, уже 20 бит, а не 32.
про миллион я дли примера сказал, в реальности их намного больше, но для примера пусть будет миллион :)
Ogra
> О, не равновероятное распределение, можно попробовать пожать Хаффманом, и
> получить, скажем, в среднем 10 бит.
хмм, подумаю на досуге над этим...

#22
12:29, 12 июля 2018

-=MASTER=-
> нее...она постоянно меняется

Что значит постоянно меняется (25 кадров в секунду, что ли), раскрывай по нормальному. У тебя одна картинка или миллион картинок? Почему ты считаешь, что у тебя задача NxN, миллион на миллион?
Если картинка одна в один данный конкретный момент времени, то нужно просто построить из этого миллиона значений бинарное дерево без повторов и использовать его (N logN). Ну или, если айдишников в районе N миллионов, то просто заюзать N / 8 Мегабайт оперативки в битовое поле  (N). И уже после этого построения проводить расчеты в каждом "пикселе".

#23
16:07, 12 июля 2018

-=MASTER=-

зачем тебе это всё?

#24
16:16, 12 июля 2018

Хаус
> зачем тебе это всё?
Видимо, пытается пронумеровать мысли.

#25
16:33, 12 июля 2018

Хаус
> зачем тебе это всё?
в ближайшие пол года...год ты всё узнаешь

—ребят, забейте на тред, я уже перешёл на другой механизм и эта штука мне уже не нужна :)

#26
16:38, 12 июля 2018

-=MASTER=-
> ребят, забейте на тред, я уже перешёл на другой механизм и эта штука мне уже не
> нужна :)
Одобряю.
Лучшее решение проблемы - избавление от проблемы.

#27
17:18, 12 июля 2018

Panzerschrek[CN]
> Лучшее решение проблемы - избавление от проблемы.
+  :-)

#28
20:40, 12 июля 2018

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

+ Показать
#29
13:15, 13 июля 2018

-=MASTER=-
> —ребят, забейте на тред, я уже перешёл на другой механизм и эта штука мне уже
> не нужна :)
Жаль. Существует алгоритм со сложностью O(N log N), доп. память O(N).

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

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