Я хотел бы создать растровое изображение во время выполнения. Растровое изображение должно быть масштабируемым со всех сторон, а доступ к пикселям должен быть достаточно эффективным.
Некоторая иллюстрация http://img546.imageshack.us/img546/4995/maptm.jpg
Между и после команд, показанных на рисунке, Map.setPixel () и Map.getPixel () должны устанавливать / возвращать данные, сохраненные в растровом изображении.
Я не ожидаю, что реализация - это просто концепция, как распределить память таким образом, чтобы setPixel () / getPixel работали как можно быстрее.
extendX
методы, чтобы быстроsetPixel
иgetPixel
быстро?Ответы:
Если
extend()
операция должна быть достаточно быстрой, Quadtree может подойти; на самом деле это даже не потребует явных операций расширения. Следует признать, что это не даст оптимальной производительности для произвольного доступа к отдельным пикселям, но ваш комментарий говорит, что ваша основная операция заключается в итерации по пикселям, что квадродерево может сделать очень быстро, возможно, почти так же быстро, как реализация на основе матрицы (и быстрее если итерация не всегда происходит одинаково, матрица выложена).Ваши требования звучат так, будто вы пытаетесь внедрить сотовый автомат, такой как Игра Жизни. Возможно, вы захотите взглянуть на Hashlife , чрезвычайно эффективный способ реализовать игру жизни на бесконечной сетке. Обратите внимание, что он основан на Quadtree, но выполняет некоторые очень умные дополнительные оптимизации в зависимости от локальности правил игры.
источник
@SecStone сказал, что для операции расширения достаточно времени, поэтому самый простой и эффективный способ хранения пикселей - это использование одного плоского массива или двумерного массива, поскольку к пикселям можно получить доступ в постоянное время.
источник
Рукой
Если память не является очень редким ресурсом, я рассматриваю работу большими кусками.
Вот немного псевдокода.
Эта реализация довольно наивна.
Во-первых, он создает чанки в getPixel (в принципе, было бы хорошо просто вернуть 0 или около того, если чанки не были определены для этой позиции). Во-вторых, он основан на предположении, что у вас достаточно быстрая и масштабируемая реализация Map. Насколько мне известно, каждый приличный язык имеет один.
Также вам придется играть с размером куска. Для плотных растровых изображений большой размер порции хорош, для разреженных растровых изображений меньший размер порции лучше. На самом деле для очень разреженных «размер порции» равен 1, что делает «порции» самими устаревшими и сокращает структуру данных до int-карты int-карты пикселей.
С полки
Другим решением может быть просмотр некоторых графических библиотек. На самом деле они неплохо рисуют один 2D буфер в другой. Это будет означать, что вы просто выделите больший буфер и поместите оригинал в соответствующие координаты.
Как общая стратегия: при наличии «динамически растущего блока памяти» хорошей идеей будет выделить его несколько раз, когда он израсходован. Это довольно много памяти, но значительно сокращает затраты на выделение и копирование . Большинство векторных реализаций выделяют вдвое больше своего размера, когда он превышен. Поэтому, особенно если вы используете готовое решение, не расширяйте свой буфер только на 1 пиксель, потому что был запрошен только один пиксель. Выделенная память дешевая. Перераспределение, копирование и выпуск - это дорого.
источник
Просто пара советов:
Если вы реализуете это как массив некоторого целочисленного типа (или массив массивов ...), вам, вероятно, следует каждый раз увеличивать резервный массив на некоторое количество бит / пикселей, чтобы избежать сдвига битов при их копировании. Недостатком является то, что вы используете больше места, но доля расточенного пространства уменьшается по мере увеличения растрового изображения.
Если вы используете структуру данных на основе карт, вы можете замять проблему выращивания растрового изображения, просто переселение х, у координаты аргументов
getPixel
иsetPixel
вызовов.Если вы используете структуру данных на основе карты, вам нужны только записи карты для «единиц». «Нули» могут указывать на отсутствие записи. Это экономит значительное количество места, особенно если растровое изображение состоит в основном из нулей.
Вам не нужно использовать карту карт. Вы можете закодировать
int
пару x, y как одинlong
. Аналогичный процесс может быть использован для сопоставления массива массивов с массивом.Наконец, вам нужно сбалансировать 3 вещи:
getPixel
иsetPixel
,extend*
операций, иисточник
Прежде чем пытаться сделать что-то более сложное, и если вы не можете хранить все в памяти, сделайте все просто и используйте двумерный массив вместе с информацией о происхождении вашей системы координат. Чтобы расширить его, используйте ту же стратегию, как, например, в C ++ std :: vector: сделайте различие между фактическим размером вашего массива и емкостью массива и увеличивайте емкость порциями при достижении предела. «емкость» здесь должна быть определена в терминах интервалов (с_х, до_х), (с_y, до_y).
Это может потребовать полного перераспределения памяти время от времени, но пока это происходит не слишком часто, это может быть достаточно быстрым для вашей цели (на самом деле, вы должны попробовать / профилировать это).
источник
Абсолютно быстрый способ сделать пиксельный доступ - это двумерный массив индивидуально адресуемых пикселей.
Для расширений начните с простой реализации, которая перераспределяет и копирует каждый раз (так как этот код вам все равно понадобится). Если профилирование не указывает на то, что вы тратите на него много времени, нет необходимости дорабатывать его дальше.
Если при профилировании обнаруживается необходимость уменьшить количество перераспределений, а объем памяти не ограничен, рассмотрите возможность перераспределения на процент в каждом направлении и сохранения смещения к источнику. (Например, если вы начнете новое растровое изображение с 1x1 и выделите массив 9x9 для его хранения, начальные
x
иy
смещения будут такими4
.) Здесь компромисс заключается в необходимости дополнительной математики во время доступа к пикселям для применения смещения.Если расширения оказываются действительно дорогими, вы можете попробовать один или оба из них:
Относитесь к вертикальным и горизонтальным расширениям по-разному. Расширение массива по вертикали в любом направлении может быть достигнуто путем выделения нового блока и создания единственной копии всего существующего массива с соответствующим смещением в новой памяти. Сравните это с горизонтальными расширениями, где вы должны выполнять эту операцию один раз в строке, потому что существующие данные не являются непрерывными в новом блоке.
Следите за наиболее частым количеством и направлением расширения. Используйте эту информацию, чтобы выбрать новый размер и смещение, что уменьшит вероятность необходимости перераспределять и копировать для любого расширения.
Лично я сомневаюсь, что вам понадобится любой из них, если только соотношение между количеством пикселей и расширением не является низким.
источник
Map.setPixel()
иMap.getPixel()
который изменяет один пиксель за раз, также предоставляют методы, которые копируют и изменяют один прямоугольник пикселей за раз. Это позволит звонящему выбрать более эффективную форму доступа в зависимости от информации, доступной звонящему.(Давайте не будем одобрять смешные ответы ...)
источник
Наиболее гибкая и, возможно, надежная реализация - это связанный список со структурами, дающими координату x, координату y и значение бита. Я построил бы это сначала и заставил бы это работать.
Затем, если он слишком медленный и / или большой, попробуйте обычные способы его ускорения: массив, матрица, растровое изображение, сжатие, кэширование, инверсия, сохранение только значений «1» и т. Д.
Проще сделать медленную правильную реализацию быстрее, чем исправить быструю ошибочную реализацию. И пока вы тестируете свою «быструю» вторую реализацию, у вас есть стандарт ссылок, с которым можно сравнить.
И, кто знает, вы, вероятно, обнаружите, что медленная версия достаточно быстрая. Пока вся структура помещается в памяти, все уже происходит удивительно быстро.
источник
Я предлагаю следующую реализацию в Python:
Имеет следующие преимущества:
map[(1,2)]
можно рассмотретьO(1)
.источник
Если вам действительно нужно растровое изображение любого произвольного размера - и я имею в виду что-то от 1x1 до 1000000x1000000 и более, и нужно, чтобы его можно было расширять по требованию ... одним из возможных способов является использование базы данных. Поначалу это может показаться нелогичным, но у вас действительно есть проблема с памятью. База данных позволит вам получить доступ к отдельным пикселям и хранить любое количество данных. Я не обязательно имею в виду БД SQL, кстати.
Это будет достаточно быстро для ваших целей? На это я не могу ответить, так как здесь нет контекста относительно того, что вы делаете с этим растровым изображением. Но если это для отображения на экране, учтите, что вам, как правило, нужно только отозвать дополнительные строки сканирования, чтобы отобразить их при прокрутке экрана, а не все данные.
Это, как говорится, я не могу помочь, но интересно, если вы собираетесь что-то не так. Может быть, стоит вместо этого использовать векторную графику и отслеживать отдельные объекты в памяти, а затем отображать растровое изображение настолько большого размера, сколько необходимо для экрана?
источник
Вот шаги, чтобы заставить это работать должным образом:
Пример реализации будет:
Очевидно, что для реальной реализации XSize () и YSize () не будут работать, но вам понадобятся MinX (), MaxX (), MinY (), MaxY () или что-то подобное для поддержания согласованности номеров индексов.
источник