Как оптимизировать элементы на двухмерном массиве(пиксели) в прямоугольники?

Question

[Константин]

Например, есть двухмерный массив:

[ ]  [ ]  [ ] [x]   [ ]
[ ]  [x]  [x] [x]   [ ]
[ ]  [x]  [x] [ ]   [ ]
[ ]  [ ]  [x] [ ]   [ ]
[ ]  [ ]  [x] [ ]   [ ]

,
в котором [x] обозначает 1 закрашенную ячейку, а элементов [] не существует. Этот список coords всегда выглядит как непрерывающаяся кривая. Задачей является постоянный рендер всех этих пикселей(т.к. список всегда обновляется, а надо всегда обновлять то, что показывается на экране), которую легко можно реализовать списком for x in coods:. Но что, если наше пространство в 4 раза больше, закрашенных ячеек тоже больше, а мы запускаем данный рендер на очень медленном оборудовании? В результате чем больше наш список coords, тем больше требуется времени на то, чтобы отрисовать все эти ячейки.
Но мы знаем, что каждая ячейка отрисовывается, например, функцией newRect(x, y, width, height), которая отрисовывает прямоугольник. Значит, зная, что у нас кривая линия никогда не прерывается, как змея, а иногда и могут случаться моменты, когда координаты могут создавать группу из прямоугольников или даже квадратов, наверняка возможно разделить эти координаты на группу из прямоугольников,которые, оптимизировав, можно будет также отрисовать через тот же цикл for. Но отличие при этом будет в том, что элементов в новом списке будет гораздо меньше, что улучшит производительность.

И вот главный вопрос: возможно ли реализовать такой алгоритм, который будет тратить меньше времени, чем простейший цикл for? А если и возможно, то как это можно реализовать в Python?

Answer 1

[mayton2019]

Например, есть двухмерный массив:

Сразу неправильно. В компьютерной графике и графическом моделировании (книжка образца 1990х годов)
перечислены большинство графических оптимизаций. И практически везде нет никаких много-мерных
массивов. Забудьте многомерные массивы если хотите перформанса. Это блажь. Забудьте пиксели-объекты. Никаких объектов! Только WORD (ARGB) или индесные цвета.

Тезисно.
1) Растровая картинка - всегда отображатеся в 1-мерный массив в памяти. Выравнивается по границе кеш-линии и т.д. Тоесть решил рисовать в 1024х768 в RGB цвете - будь добр выдели - 3145728 байт памяти (я округлил RGB до 4 байтов).

2) Все операции рисования линий, прямоугольников кругов и полигонов и даже шрифтов - работают через прямой (direct) доступ к памяти. Никто пикселями не рисует. И ежу понятно что накладные расходы на стек и все съедают и когерентность доступа идет всегда неудачно по кешам. Одни промахи. Эти-же принципы реализованы в OpenGL, Direct3d только там еще и с позиции параллелизма. Одну фигурку может рисовать несколько графических ядер.

Я не знаю как в Python. Здесь надо быть глубоким специалистом в Python чтоб понять как там соптимизировать for. (Я думаю никак). Но все быстрые графические алгоритмы обычно пишуться на C/C++ и там работают с бегущим указателем. Если условия позволяют - делают SIMD. Чтоб за 1 команду закрасить или наложить маску на 2 пиксела сразу. Или на 4. Или на 8.

Вообще с Питоном идея - тухляк изначально. Если хочешь быстро красить краской прямоугольники в экране - тебя надо реализовать это на сях а потом дописать фасад для Питона чтоб делать вызов сразу рисования прямоугольника. И все современные библиотеки машинного обучения вобщем-то так и реализованы. Питон - только запускает а реализация вращает циклы в других более быстрых языках.

Comments

[Griboks]

Не переживайте, в питоне давно уже решили проблему с быстродействием.

Answer 2

[Griboks]

1) Грубо говоря, у вас есть одномерный массив бит. Каждую отрисовку можно записать как бинарный сдвиг 1 << n (при очищении считаем массив == 0), где n - индекс первого пикселя фигуры.

2) Тогда рисование можно заменить на череду бинарных И: (1 << n1) & (1 << n2) & (1 << n3) & .... Получается, можно сделать эти операции векторными и многократно ускорить рисование.

3) Разобьём панель рисования на отдельные чанки (подквадраты). Тогда неизменившиеся квадраты можно даже не перерисовывать. При этом изменившиеся квадраты можно перерисовывать параллельно. Поздравляю, вы изобрели видеокарту!

Answer 3

[Wataru]

По идее, должно быть пофигу, сколько там вызовов. Каждый вызов newRect закрашивает какие-то пиксели и работает пропорционально площади. Поэтому объединение клеток в прямоугольники сократит лишь количество вызовов, но не сократит время работы никак.

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

Самый тривиальный алгоритм - идти по строкам. Если встретили x, то пропускайте до конца строки и до первой пустой ячейки. Красьте длинным прямоугольником в этой строке. Если змейка не особо петляет, то в каждой строке вообще только один прямоугольник будет.

Потом, встает вопрос, а как дорого делать overdraw. Может быть быстрее одну и ту же клетку прорисовывать несколько раз, но зато меньше графических вызовов делать. А может быть наоборот нельзя ни одну клетку прорисовывать более одного раза, даже если можно сократить так количество прямоугольников. Это две разные задачи, вам надо решить, что на вашей системе работает быстрее.

Но вообще, задача разбить область на минимальное количество прямоугольников - очень сложная. Решение скорее всего будет медленнее прописовки каждой клетки отдельно.

Answer 4

[Vindicar]

Для простых случаев - да.
Если текущий и следующий элемент формируют горизонтальную или вертикальную прямую, запоминаем, который вариант реализовался (влево, вправо, вверх, вниз) и составляем список сегментов для отрисовки.
Пока элементы после следующего ложатся на эту прямую, добавляем их в список отрисовки. Если встретили элемент, который не ложится - дальше не проверяем.
Все элементы в списке можно отрисовать за один проход, так как они формируют линейный сегмент. Дальшейшую обработку выполняем, начиная с первого "неподходящего" элемента.
В этом случае мы каждый элемент читаем только один раз, поэтому алгоритм должен по идее иметь линейную сложность, как и просто цикл.

Но тут есть два вопроса.
1. А ты уверен, что дело именно в количестве "пикселей"? Ты замерял производительность, и именно это - узкое место?
2. Возможно, было бы проще при составлении списка "пикселей" описать позицию пикселя как смещение относительно позиции предыдущего "пикселя" ("влево", "вверх" и т.д.)? Тогда линейные сегменты будут выглядеть как последовательности одинаковых элементов ("..., вверх, вправо, вправо, вправо, вправо, вверх, ..."), что упростит дальнейший расчёт.