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

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

Страницы: 1 2 3
-=MASTER=-Удалёнwww13 июля 201821:18#30
youtube
> Жаль. Существует алгоритм со сложностью O(N log N), доп. память O(N).
ну так в студию, чем больше на этом форуме полезной ифны - тем лучше, я порой сам для себя здесь что-то пощу, что бы осталось для истории, а учитывая то, что форум гуглиться на раз два - потом найти будет не сложно
MrShoorУчастникwww13 июля 201823:30#31
-=MASTER=-
> ой...да там долго рассказывать, но в двух словах, но если провести аналогию с
> графикой, представь, что у тебя есть картинка/текстура и на ней есть
> разноцветные пиксели, у каждого пикселя цвет может иметь id от 1 до 1 000 001
> (ну просто миллион цветов), какой это реально цвет - не имеет значения (это
> всего лишь аналогия). Пиксели не все разные, очень много повторов, то есть на
> картинке много пикселей с одинаковым ID цвета, ну так вот алгоритм выглядит как
> NxN, то есть представь, код шейдера каждого пикселя делает перебор по всем
> остальным, то есть каждый из миллиона пикселей на картинке (да, из тоже 1 000
> 000), обращается ко всем другим (кроме себя), короче NxN. Так вот, что этот
> пиксель делает, он суммирует цвета, но суммирует не просто всё подряд, а
> суммирует только уникальные цвета, то есть если какой-то цвет с определённым ID
> он уже добавил в свою внутреннюю сумму, то его добавляют уже не нужно, а
> учитывая, что повторов на картинке много, случая отброса повтора очень частые.
> То есть ему при обращение к очередному пикселю нужно проверить, а не
> просуммировал ли она уже ранее цвет с таким-то Id... Ну вот как-то так...
Так, я представил. Меня бы в этом случае спасла обычная сортировка.
-=MASTER=-Удалёнwww14 июля 20189:51#32
MrShoor
> Так, я представил. Меня бы в этом случае спасла обычная сортировка.
вообще темя уже не актуальна, но раз она вызвала такой резонанс, давайте её тогда добьём до конца. Хмм... вот ещё одна аналогия проблемы:
Изображение

Вот видишь толпу людей, а теперь представь, что есть задача:
1. Есть секретный шифр/код из 3-х цифр
2. Есть толпа людей, плотно стоящих друг к другу, по этому они не могут ходить, они могут лишь кричать что-то своим соседям.
3. Задача всей толпы - как можно скорее узнать этот секретный код из 3-х цифр и не важно, кто его из толпы узнает первым, вся толпа в этом заинтересованна...хмм..ну допустим, когда эта толпа узнает код (кто-то первый из толпы), её сверху польют водой из шлангов что-бы освежиться и всем станет легче стоять на жаре.
4. Теперь мы случайно говорим 3-м рандомным людям в толпе по 1-й цифре кода, одному говорим первую цифру, второму - вторую, а третьему соответственно третью. Все люди знают задачу, что нужно как можно быстрей узнать все 3 цифры кода что бы полил освежающий "дождь", но пока-что полностью кода никто не знает, известны лишь часть кода по отдельности, отданные случайным людям. Люди могут кричать только соседям, допустим они не кричат, а шепчутся как бы, то есть одного человека слышат только соседи рядом.
5. Вопрос: что должны говорить люди друг другу, распространяя волну своих знаний по толпе? Ну допустим, получив по одной цифре каждый из этих трёх людей (которые знают цифру) говорят соседям мол "первая цифра кода такая-то!!" или "вторая цифра такая-то, распространи эту информацию дальше, ну типа передай соседу..." 
6. По скольку на картинке точка С находится далеко от А и B, очевидно, что волна распространения от А и B сойдётся раньше, чем дойдёт до С, то есть в какой-то момент, люди между точками А и В начнут слышать вокруг фразы типа "я знаю первую цифру" и "я знаю вторую цифру", то есть появятся люди, которые будут слышать шёпот уже о двух цифрах, а не только об одной...хмм.. ок, но что же должны распространять люди, которые знают уже две цифры своим соседям? ну наверное говорить эти две цифры.... но поскольку это толпа, то волны распространения от людей, знающих по 1-й цифре всё равно будут пересекаться с волнами людей, знающих две цифры и вот тут-то и вопрос, что должен делать человек, который слышат вокруг шёпот типа "я знаю уже две цифры, первая такая-то, вторая - такая-то" и в то же время слышать так же вокруг себя в том числе и шёпот типа "я знаю первую цифру" или "я знаю вторую цифру".... что должен делать человек, слышащий это? По идее он должен сказать мол "я и так знаю уже и первую и вторую - а вы, кто тут распространяет их по отдельности - идите нах...", то есть по идее он их должен проигнорировать как бы и распространять уже сразу свои две цифры...или нет? В любом случае, он должен сверить ID этих цифр (ну первая - 1, вторая - 2) с тем, что он уже знает и понять, что их в себя впитывать уже не надо....... ой ...глупо объяснил наверное, если не понятно - спрашивайте :)

Правка: 14 июля 2018 9:54

MrShoorУчастникwww14 июля 201817:14#33
-=MASTER=-
Теперь ты описал flood fill алгоритм...
Короче у тебя классическая проблема XYZ.
OgraПостоялецwww14 июля 201819:55#34
-=MASTER=-
> вот ещё одна аналогия проблемы:

Да не надо нам аналогий, дай нам реальную проблему!
Нам все эти твои "задачи", "идеи" и весьма кривые "аналогии" нафиг не нужны. Ты только запутываешь нас и не даешь нам предложить нормальный алгоритм для решения задачи.

-=MASTER=-Удалёнwww14 июля 201820:16#35
Ogra
> Ты только запутываешь нас и не даешь нам предложить нормальный алгоритм для
> решения задачи.
Ты хочешь, что бы я рассказал, как работает моя модель Ultimate AI? Этого не будет!
Но через пол года я дам тебе ссылку на сайт своей собственной конторы, где ты сможешь многое почерпнуть и лицезреть

Правка: 14 июля 2018 20:18

MrShoorУчастникwww14 июля 201821:19#36
-=MASTER=-
> Но через пол года я дам тебе ссылку на сайт своей собственной конторы, где ты
> сможешь многое почерпнуть и лицезреть
А давай ты дашь такую ссылку всем? Итак, дедлайн 14-ое января 2019 года.
-=MASTER=-Удалёнwww14 июля 201821:51#37
MrShoor
> Итак, дедлайн 14-ое января 2019 года
это крайний срок, в реальности всё случиться намного раньше.  О..мистер Шур, тебе и Суслику я конечно же в первую очередь ссылку скину :)
*Lain*Постоялецwww14 июля 201822:19#38
-=MASTER=-
Я верю в твой проект. Только постарайся.

Мне ссылку тоже скинь пожалуйста.

Super_inoyПостоялецwww15 июля 20181:02#39
И мне, и мне. А удаляться-то зачем?
MrShoorУчастникwww15 июля 20181:55#40
Super_inoy
> И мне, и мне. А удаляться-то зачем?
Бомбануло просто. Ничего, вернется через пару месяцев. Это кстати уже его второй аккаунт тут. Предыдущий раз он точно так же с драмой уходил.
youtubeПостоялецwww16 июля 20188:26#41
-=MASTER=-
> ну так в студию,
Если кому-то еще интересно:
1. Как правильно заметил MrShoor, сортируем картинку.
2. Каждый пиксель добавляем в переменную СУММА, если только он уже не был добавлен ранее. Поскольку картинка отсортирована, это легко сделать.
3. Для каждого пикселя вычисляем сколько раз он появляется в картинке. Опять же, раз картинка отсортирована, это делается просто.
4. Заводим массив helper, в который пишем 0, если пиксель появился больше одного раза и 1 в противном случае. Тут опять помогает то, что картинка отсортирована.
5. Перед использованием надо из СУММЫ вычесть значение пикселя умноженное на значение в хелпере.

Шаги со второго по четвертый можно и нужно объединить в один цикл.

Самое сложное и прожорливое в данном алгоритме - это сортировка. Лучшие сортировки имеют сложность по операциям O(N log N), по памяти O(N), где N - количество пикселей.
Если это действительно картинка и вычислять сумму надо поканально, то можно взять сортировку подсчётом. И вообще не сортировать, а использовать только первый шаг сортировки - собственно, подсчёт. Тогда алгоритм упростится до O(N), память O(1).

Реализация на D. Скорее всего в ней куча дыр, связанных с переполнением.

+ Показать

Страницы: 1 2 3

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

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