|
Двумерные массивы используются для таких целей, как хранение изображений, задание графов и так далее. Но в большинстве языков программирования двумерный массив представляется в памяти как один большой одномерный массив размером КоличествоСтрок * КоличествоСтолбцов элементов, логически интерпретируемый как двумерный.
Иногда появляется необходимость в создании динамического двумерного массива.
Если попытаться решить эту задачу "в лоб", то при вставке и удалении элементов часто придтся передвигать практически все элементы массива. При большом размере массива это может привести к катастрофическому падению производительности.
Основным достоинством предлагаемой реализации динамического двумерного массива является то, что она обеспечивает более высокую скорость операций модификации.
ПРИМЕЧАНИЕ
Приведенный в статье способ представления двумерных массивов, как и сами двумерные массивы, хорош при условии высокой степени заполнения ячеек массива значащими данными или при относительно небольшом размере массива. Если возникает потребность в создании разреженного массива большого размера, лучше эмулировать его на базе хеш-таблицы, создавая из пары индексов один составной ключ. Хеш-таблица позволит более экономно расходовать память. При этом время доступа к элементам останется константным. - прим.ред.
|
Описание реализации
Допустим, у нас имеется двумерный массив:
памяти он выглядит следующим образом:
Самая тривиальная операция, которую мы можем сделать - это добавить строку к массиву.
Добавление строки {1, 2}:
Операция посложнее – вставка строки в массив. Здесь уже необходимо сдвинуть вправо элементы массива на длину строки, начиная с последнего и заканчивая первым элементом по индексу новой строки.
Общее количество сдвигов: КоличествоСтолбцов * (КоличествоСтрок - ИндексНовойСтроки).
ставка строки {1, 2} по индексу 1:
И самая трудомкая операция – вставка столбца. Здесь уже необходимо сдвигать вправо элементы, начиная с последнего, причм сдвиг должен происходить так: элементы последней строки, начиная с ИндексаНовогоСтолбца, в количестве КоличествоСтолбцов – ИндексНовогоСтолбца, сдвигаются на КоличествоСтрок, а элементы, предшествующие этому индексу, в количестве ИндексНовогоСтолбца сдвигаются на КоличествоСтрок - 1. Элементы предпоследней строки, начиная с ИндексаНовогоСтолбца, в количестве КоличествоСтолбцов – ИндексНовогоСтолбца, сдвигаются на КоличествоСтрок - 1, а элементы, предшествующие этому индексу в количестве ИндексНовогоСтолбца сдвигаются на КоличествоСтрок - 2 и так далее.
Общее количество сдвигов: КоличествоСтолбцов * КоличествоСтрок - ИндексНовогоСтолбца.
ставка столбца {1, 2} по индексу 1:
Самый очевидный вариант повышения быстродействия этих операций - минимизировать количество сдвигов.
Пойдм так же по порядку:
Самое простое решение по вставке строк – хранить каждую строку в одномерном массиве, а адрес этого массива записывать в другой одномерный массив – массив базовых адресов строк.
ыглядит это примерно так:
При такой организации чтобы получить адрес элемента двумерного массива нужно: по ИндексуСтроки взять значение АдресаСтроки из массива базовых адресов и прибавить к нему смещение: ИндексКолонки * РазмерЭлемента.
Теперь операция вставки строки в массив сводится только к сдвигу вправо базовых адресов и количество сдвигов для этой операции: КоличествоСтрок - ИндексНовойСтроки.
ставка строки {1, 2} по индексу 1:
ПРИМЕЧАНИЕ
Хоть это и не принципиально, но при таком подходе мы вдобавок избавились от операции умножения для получения индекса, что происходит при обычном двумерном массиве: чтобы в массиве NxM получить элемент [i, j] нужно обратиться по адресу Массив[(i * КоличествоСтолбцов + j) * РазмерЭлемента].
Адрес строки занимает 4 байта, а элемент массива может быть любого размера, так что мы не только минимизировали количество сдвигов, но и при размере элемента больше 4-х байт, уменьшили количество обращений к памяти. А так же мы получили возможность менять строки местами всего лишь поменяв базовые адреса строк местами.
|
Если мы оставим вс, как есть, то для вставки столбца нам потребуется в каждой строке сдвинуть вправо элементы, начинающиеся с ИндексаНовогоСтолбца в количестве КоличествоСтолбцов - ИндексНовогоСтолбца.
Общее количество сдвигов: КоличествоСтрок * (КоличествоСтолбцов – ИндексНовогоСтолбца).
Хоть алгоритм вставки столбца и упростился, и количество сдвигов уменьшилось, для нас это вс равно неприемлемо, так что идм дальше.
По аналогии со строками введм вспомогательный массив для столбцов – массив смещений в строках. Для определнности считаем, что каждый элемент массива занимает 2 байта.
ыглядит это примерно так:
При такой организации, чтобы получить адрес элемента двумерного массива, нужно: по ИндексуСтроки взять значение АдресаСтроки из массива базовых адресов и прибавить к нему смещение, взятое по ИндексуКолонки из массива смещений.
Теперь операция вставки столбца в массив сводится только к сдвигу вправо смещений в строках, и количество сдвигов для этой операции: КоличествоСтолбцов - ИндексНовойКолонки.
ставка столбца {1, 2} по индексу 1:
ПРИМЕЧАНИЕ
Так же, как и со строками, смещение занимает 4 байта, и мы получаем немалый выигрыш при работе с большими элементами. И, так же, чтобы поменять столбцы местами, нужно поменять смещения в строках местами. Плюс обеспечивается когерентность столбцов – то есть по какому смещению он находится в одной строке по такому же смещению он находится и во всех остальных строках.
|
Ну, вот вроде бы и вс со вставками, но резонно напрашивается мысль о том, что раз у нас есть операции вставки, то должны быть и операции удаления.
Ну со строками вс просто - получить адрес строки, освободить занимаемую ей память и убрать е адрес из массива базовых адресов, а вот со столбцами малость сложнее.
Чтобы при каждом удалении столбца не делать ненужных нам сдвигов, введм ещ один вспомогательный массив – карта блоков, показывающая, занят в данный момент определнный блок (элемент строки) или свободен.
ыглядит это примерно так:
Удаление столбца по индексу 2:
Если мы теперь захотим добавить столбец, то он просто займт первый свободный блок.
ПРИМЕЧАНИЕ
Сравнение методов: я лишь приведу приблизительные цифры для своего метода и обычных сдвигов. Для сдвигов я сразу выделял необходимый объм памяти под массив 8192 * 8192 и считал, что в нм 8192 строки и соответственно 1 столбец. На добавление ещ 8191 столбца уходила примерно минута, а вот своим методом я создавал массив 16384 * 16384 на что уходило всего 6-7 секунд, причм объм памяти занимаемый массивом 8192 * 8192 = 256М, а вот массив 16384 * 16384 занимает 1Г, причм в мом методе не было никаких поблажек – вся память выделялась по мере требования. Но тут я хочу обратить внимание ещ на один нюанс – я пользовался памятью из кучи (malloc), а не виртуальной памятью, поэтому в моей реализации есть гранулярность выделения памяти – то есть даже если в массиве находится одна строка, то она занимает 1, 2, 4, 8, 16, 32 или 64К. Результат в 7 секунд получался при гранулярности в 64К – то есть каждая строка как раз вмещала 16384 элемента по 4 байта, а вот при гранулярности в 32К результат получился 12-15 секунд, что тоже очень неплохо, учитывая, что для таких вещей использовать виртуальную память должно быть обязательным требованием!!!
|
Применить это можно, например, к шифрованию спутниковых каналов, где вещание ведтся как раз с изменнным чередованием строк, или же в каком-нибудь графическом приложении например для изменения размера картинки или е зеркального отображения по вертикали/горизонтали ну и так далее.
www.rsdn.ru
24-05-2007
InternetExpress Borland Delphi 20-08-2008
Borland Delphi 5 InternetExpress - Internet MIDAS. Delphi , - Internet ISAPI/NSAPI, ASP CGI, , , XML (eXtended Markup La...
07-07-2008
. , . , DOC , . : EXE , , ...
07-05-2008
. . «» -, . . 1) ?2) ().3) ...
|
