Порядок массивов и Permute() в MATLAB

Эффективное зацикливание в MATLAB/Octave

Порядок массива и функция permute()

Порядок массива является важным фактором при циклическом просмотре данных в MATLAB/Octave. Выбор того, какое измерение использовать в цикле, может существенно повлиять на эффективность вычислений. В этом руководстве я представляю и иллюстрирую концепцию порядка массива, создаю простой эксперимент, чтобы продемонстрировать влияние порядка массива при циклировании, и объясняю, как можно использовать команду permute() в MATLAB для записи эффективные циклы каждый раз.

Весь исходный код примеров можно найти в репозитории GitHub.

Порядок массива

При работе с многомерными или N-мерными (ND) массивами важно знать, как данные хранятся в памяти. Это называется упорядочением массива. Существует два основных соглашения: порядок по строкам и по столбцам. Эти два разных метода просто относятся к тому, какие элементы области массива ND непрерывны в памяти, а также к тому, как такие массивы должны быть линейно индексированы. В порядке столбцов элементы столбцов являются смежными в памяти. и в порядке строк элементы строк являются смежными в памяти. Таким образом, в основном мы считаем элементы по столбцам для столбцов и по строкам для строк.

В следующем фрагменте кода показан пример матрицы 3 x 3, где каждый элемент показывает, что такое линейный индекс. Точно так же вы можете думать о числах в матрице как о порядке данных в памяти (например, 1 — это первый адрес памяти, 2 — второй адрес памяти и т. д.).

colMaj = [ 1, 4, 7; 2, 5, 8; 3, 6, 9 ];
disp( colMaj )
           1   4   7
           2   5   8
           3   6   9
rowMaj = [ 1:3; 4:6; 7:9 ];
           1   2   3
           4   5   6
           7   8   9
disp( rowMaj )

Мы можем тривиально увидеть, как MATLAB хранит данные, используя оператор «:», который разворачивает данные. Поскольку MATLAB работает с основными столбцами, вы можете видеть, что матрица colMaj возвращает индекс в правильном порядке, а матрица rowMaj возвращает элементы не по порядку.

disp( colMaj(:) )
1
           2
           3
           4
           5
           6
           7
           8
           9
disp( rowMaj(:) )
1
           4
           7
           2
           5
           8
           3
           6
           9

Чтобы сделать это более понятным, мы можем создать простую анимацию. Анимация показывает, как разворачивается матрица с использованием обоих соглашений. Линейный индекс внизу показывает, как отдельные элементы фактически хранятся в памяти.

Перебор данных

Итак, почему порядок массива имеет значение? Ну, когда вы перебираете данные в цикле, порядок массива может существенно повлиять на время выполнения. Гораздо эффективнее обращаться к непрерывным данным в памяти. Таким образом, знание того, как наши данные организованы в памяти, также может помочь нам написать более эффективный в вычислительном отношении код.

Продемонстрируем это на простом примере. Предположим, у нас есть набор изображений, с которыми мы хотим работать. Изображения имеют размер (nX, nY) пикселей, и в нашем наборе данных есть изображения nI. Возможны два варианта расположения этих изображений в памяти: [nX, nY, nI] или [nI, nX, nY]. В первой ориентации изображения будут располагаться в памяти последовательно, а во второй ориентации — нет.

Чтобы увидеть, какая разница в порядке массива, мы можем написать следующий тестовый код. Обратите внимание, что функции tic() и toc() позволяют нам определять время выполнения частей нашего кода. Если вы не знакомы с этими функциями, tic() фактически запускает таймер и toc() записывает, сколько времени прошло с момента запуска таймера. Дополнительную документацию можно найти в справке по MATLAB.

% Arrange images at the first two dimension
imageData = randn( nX, nY, nI );
a = tic();
for ix1=1 : nI
  thisImg = imageData( :, :, ix1 );
end
et1 = toc( a );
% Arrange images at the last two dimensions
imageData = randn( nI, nX, nY );
a = tic();
for ix1=1 : nI
  thisImg = imageData( ix1, :, : );
end
et2 = toc( a );
% Plot the results
fprintf( 'Looping over the last dimension: %0.4f seconds\n', et1 );
fprintf( 'Looping over the first dimension: %0.4f seconds\n', et2 );
fprintf( '%0.1f factor increase\n', et2/et1 );

Чтобы проиллюстрировать влияние порядка массива, код был запущен с nX = nY = 128 и nI со значениями 1 000, 10 000 и 50 000. Смелым и любознательным предлагается скачать исходный код и опробовать более интересные комбинации!

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

Looping over the last dimension: 0.8328 seconds
Looping over the first dimension: 0.9570 seconds
1.1 factor increase

Увеличив количество изображений до 10 000, мы начинаем видеть гораздо более существенную разницу во времени выполнения. Время выполнения увеличивается в 2,4 раза, когда изображения не хранятся в памяти непрерывно.

Looping over the last dimension: 0.9039 seconds
Looping over the first dimension: 2.1613 seconds
2.4 factor increase

При дальнейшем увеличении количества изображений до 50 000 мы по-прежнему наблюдаем значительное увеличение времени выполнения. Теперь время выполнения увеличено в 8 раз!

Looping over the last dimension: 1.2299 seconds
Looping over the first dimension: 10.3527 seconds
8.4 factor increase

Важно отметить, что это был простой пример с одной петлей и только тремя измерениями. Этот эффект на самом деле может быть намного хуже для массивов с большим количеством измерений или когда мы вкладываем несколько циклов. Иногда имеет смысл добавить несколько вызовов tic() / toc() в свой код или запустить Profiler там, где вы, возможно, захотите внести некоторые изменения в свой код.

Переставить() в MATLAB

MATLAB включает функцию под названием permute(), которая является обобщением функции транспонирования, но для массивов ND. Permute() принимает массив ND и желаемый порядок массива, а затем возвращает переупорядоченные данные. Синтаксис выглядит следующим образом: newArray = permute( oldArray, [oldDim1, oldDim2, oldIm3 и т. д.]). В этом синтаксисе переменные oldDim# представляют собой порядковый индекс старого массива, а позиция во входных данных функции представляет новую порядковую позицию массива.

Например, предположим, что у нас есть ND-массив A формы [200, 450, 120, 680] и мы вызвали функцию permute() как таковую: B = перестановка( A, [3, 1, 4, 2]). Результирующая форма массива B будет [120, 200, 680, 450]. Здесь мы переместили измерение 3 в измерение 1, измерение 1 в измерение 2, измерение 4 в измерение 3 и измерение 2 в измерение 4.

Используя функцию permute(), мы можем переупорядочить любой ND-массив в зависимости от того, какое измерение мы хотим перебрать. Возвращаясь к нашему предыдущему примеру с изображением, мы можем взять наш массив imageData формы [nI, nX, nY] и преобразовать его в массив формы [nI , nX, nY] с помощью следующей команды.

imageData = permute( imageData, [ 2, 3, 1 ] );

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

% Arrange images at the first two dimension
imageData = randn( nX, nY, nI );
a = tic();
for ix1=1 : nI
  thisImg = imageData( :, :, ix1 );
end
et1 = toc( a );
% Permute data before looping
imageData = randn( nI, nX, nY );
imageData = permute( imageData, [ 2, 3, 1 ] ); % loop over the last dim
a = tic();
for ix1=1 : nI
  thisImg = imageData( :, :, ix1 );
end
et2 = toc( a );
% Plot the results
fprintf( 'Looping over the last dimension: %0.4f seconds\n', et1 );
fprintf( 'Permute and loop over the last dimension: %0.4f seconds\n', et2 );
fprintf( '%0.1f factor increase\n', et2/et1 );

Выполнение этого эксперимента с nI = 50 000 приводит к следующему результату.

Looping over the last dimension: 1.0844 seconds
Permute and loop over the last dimension: 1.1350 seconds
1.0 factor increase

Использование команды permute() значительно сократило время цикла. Конечно, использование функции перестановки сопряжено с небольшими накладными расходами, но почти во всех практических случаях ее лучше включать. Как я упоминал ранее, это особенно верно для многомерных массивов и когда мы вкладываем несколько циклов.

Резюме

В этом уроке мы рассмотрели важность порядка массивов при циклическом обходе ND-массивов в MATLAB/Octave. Используя простой код MATLAB, мы продемонстрировали преимущества циклического воспроизведения данных, расположенных в памяти непрерывно. Далее мы показали, что команда permute() позволяет нам переупорядочивать размеры массива перед циклом, чтобы мы всегда могли убедиться, что цикл выполняется эффективно.

Вот несколько моментов, которые следует помнить:

• Данные расположены в порядке столбцов в MATLAB
• Мы всегда должны перебирать самые внешние измерения, чтобы сделать наши циклы максимально эффективными.
• Permute() можно использовать до (и после) любого цикла, чтобы обеспечить эффективный цикл по ND-массивам.
• Для вложенных циклов самый внутренний цикл должен зацикливаться на самом внешнем измерении.

Удачного кодирования!