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

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

Страницы: 1 2 3 Следующая »
Panzerschrek[CN]Участникwww11 июля 201814:54#15
-=MASTER=-
> но допускается и logN
> главное требование к минимизации памяти

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

OgraПостоялецwww11 июля 201816:07#16
-=MASTER=-
Как значения распределены? Равновероятно от 0 до MAX_INT?
-=MASTER=-Удалёнwww11 июля 201817:54#17
Ogra
> Как значения распределены? Равновероятно от 0 до MAX_INT?
не имеет значения, ну пусть будет так.
OgraПостоялецwww11 июля 201821:33#18
-=MASTER=-
> таких контейнеров должно быть так же много, как и самих чисел, то есть на N
> чисел N контейнеров

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

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

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

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

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

-=MASTER=-Удалёнwww12 июля 201812:12#21
Ogra
> Одна картинка?
нее...она постоянно меняется
Ogra
> Вот смотри, уже 20 бит, а не 32.
про миллион я дли примера сказал, в реальности их намного больше, но для примера пусть будет миллион :)
Ogra
> О, не равновероятное распределение, можно попробовать пожать Хаффманом, и
> получить, скажем, в среднем 10 бит.
хмм, подумаю на досуге над этим...
OgraПостоялецwww12 июля 201812:29#22
-=MASTER=-
> нее...она постоянно меняется

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

ХаусПостоялецwww12 июля 201816:07#23
-=MASTER=-

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

gudleifrПостоялецwww12 июля 201816:16#24
Хаус
> зачем тебе это всё?
Видимо, пытается пронумеровать мысли.
-=MASTER=-Удалёнwww12 июля 201816:33#25
Хаус
> зачем тебе это всё?
в ближайшие пол года...год ты всё узнаешь

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

Panzerschrek[CN]Участникwww12 июля 201816:38#26
-=MASTER=-
> ребят, забейте на тред, я уже перешёл на другой механизм и эта штука мне уже не
> нужна :)
Одобряю.
Лучшее решение проблемы - избавление от проблемы.
-=MASTER=-Удалёнwww12 июля 201817:18#27
Panzerschrek[CN]
> Лучшее решение проблемы - избавление от проблемы.
+  :-)
*Lain*Постоялецwww12 июля 201820:40#28
jaguard
> Теме не хватает вореций.
+ Показать
youtubeПостоялецwww13 июля 201813:15#29
-=MASTER=-
> —ребят, забейте на тред, я уже перешёл на другой механизм и эта штука мне уже
> не нужна :)
Жаль. Существует алгоритм со сложностью O(N log N), доп. память O(N).
Страницы: 1 2 3 Следующая »

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

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