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

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

Страницы: 1 2 3
#30
21:18, 13 июля 2018

youtube
> Жаль. Существует алгоритм со сложностью O(N log N), доп. память O(N).
ну так в студию, чем больше на этом форуме полезной ифны - тем лучше, я порой сам для себя здесь что-то пощу, что бы осталось для истории, а учитывая то, что форум гуглиться на раз два - потом найти будет не сложно


#31
23:30, 13 июля 2018

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

#32
9:51, 14 июля 2018

MrShoor
> Так, я представил. Меня бы в этом случае спасла обычная сортировка.
вообще темя уже не актуальна, но раз она вызвала такой резонанс, давайте её тогда добьём до конца. Хмм... вот ещё одна аналогия проблемы:
Изображение

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

#33
17:14, 14 июля 2018

-=MASTER=-
Теперь ты описал flood fill алгоритм...
Короче у тебя классическая проблема XYZ.

#34
19:55, 14 июля 2018

-=MASTER=-
> вот ещё одна аналогия проблемы:

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

#35
20:16, 14 июля 2018

Ogra
> Ты только запутываешь нас и не даешь нам предложить нормальный алгоритм для
> решения задачи.
Ты хочешь, что бы я рассказал, как работает моя модель Ultimate AI? Этого не будет!
Но через пол года я дам тебе ссылку на сайт своей собственной конторы, где ты сможешь многое почерпнуть и лицезреть

#36
21:19, 14 июля 2018

-=MASTER=-
> Но через пол года я дам тебе ссылку на сайт своей собственной конторы, где ты
> сможешь многое почерпнуть и лицезреть
А давай ты дашь такую ссылку всем? Итак, дедлайн 14-ое января 2019 года.

#37
21:51, 14 июля 2018

MrShoor
> Итак, дедлайн 14-ое января 2019 года
это крайний срок, в реальности всё случиться намного раньше.  О..мистер Шур, тебе и Суслику я конечно же в первую очередь ссылку скину :)

#38
22:19, 14 июля 2018

-=MASTER=-
Я верю в твой проект. Только постарайся.

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

#39
1:02, 15 июля 2018

И мне, и мне. А удаляться-то зачем?

#40
1:55, 15 июля 2018

Super_inoy
> И мне, и мне. А удаляться-то зачем?
Бомбануло просто. Ничего, вернется через пару месяцев. Это кстати уже его второй аккаунт тут. Предыдущий раз он точно так же с драмой уходил.

#41
8:26, 16 июля 2018

-=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
ФлеймФорумПрограммирование

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