Каков наиболее эффективный способ написания циклов for в Matlab?

12

Я читал, что если, например, у меня есть двойной forцикл, который работает над индексами матрицы, то размещение индекса выполнения столбца во внешнем цикле более эффективно. Например:

a=zeros(1000);
for j=1:1000
 for i=1:1000
  a(i,j)=1;
 end
end

Каков наиболее эффективный способ его кодирования, если у меня три или более forциклов?

Например:

a=zeros(100,100,100);
for j=1:100
 for i=1:100
  for k=1:100
   a(i,j,k)=1;
  end
 end
end
Тензор
источник
4
Forпетли очень медленные в MATLAB. Вы должны по возможности избегать явных циклов в MATLAB. Вместо этого обычно проблема может быть выражена в терминах матричных / векторных операций. Это MATLABic способ. Есть также много встроенных функций для инициализации матриц и т. Д. Например, есть функция ones () , которая установит все элементы матрицы в 1 (путем расширения, в любое значение путем умножения (скаляр умножается на единичную матрицу)). Это также работает с трехмерными массивами (которые, я думаю, покрывают пример здесь).
Питер Мортенсен
3
@PeterMortensen Каким фактором (примерно) эффективность циклов в Matlab меньше по сравнению с C и Python? И почему так? Кроме того, разве эффективность циклов в Matlab не улучшилась за последние несколько лет?
TensoR
3
@PeterMortensen «обычно проблему можно выразить через матричные / векторные операции» - для определенных значений «обычно», да. ИМО точнее сказать, что люди, работающие в Matlab и тому подобное, имеют многолетнюю культуру игнорирования всего, что нельзя сделать с помощью матричных / векторных операций, настолько, что все кажется им гвоздем для этого молотка , И мы должны не просто сказать «поскольку циклы в Matlab медленны», но «Matlab медленен» (случается, что он связан только с быстрой библиотекой примитивов LA, написанных на C и Fortran).
оставил около
5
Производительность для петель является спорным: matlabtips.com/matlab-is-no-longer-slow-at-for-loops
ohreally
@leftaroundabout Правда. Забота о скорости в интерпретируемом (или полуинтерпретируемом) языке является довольно четким свидетельством того, что у вас есть проблема XY, где реальное решение - «не используйте этот язык». Исключением, конечно, является случай, если вы используете генерацию кода в Simulink, но тогда возникает вопрос, что С создает генератор кода и насколько это эффективно.
Грэм

Ответы:

18

Короткий ответ, вы хотите иметь крайний левый индекс на самом внутреннем цикле. В вашем примере индексы цикла будут идти k, j, i, а индексы массива будут i, j, k. Это связано с тем, как MATLAB хранит различные измерения в памяти. Для получения дополнительной информации см. № 13 этого поста Reddit .

whpowell96
источник
2
Или используйте встроенную функцию ones () .
Питер Мортенсен
5
Пример @Peter OP, скорее всего, просто игрушечный пример цикла for, который что-то делает, а не фактический вариант использования.
Мэтт
@ Matt Вы правы.
TensoR
11

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

Во-первых, MATLAB (и Fortran, но не C и большинство других языков программирования) хранит массивы в памяти в «главном порядке столбцов». например, если A является матрицей 2 на 3 на 10, то записи будут храниться в памяти в порядке

А (1,1,1)

А (2,1,1)

А (1,2,1)

А (2,2,1)

А (1,3,1)

А (2,3,1)

А (1,1,2)

А (2,1,2)

...

А (2,3,10)

Этот выбор основного порядка столбцов является произвольным - мы могли бы легко принять соглашение о «главном порядке строк», и фактически это то, что делается в C и некоторых других языках программирования.

Вторая важная вещь, которую вам нужно понять, это то, что современные процессоры не обращаются к памяти по одному месту за раз, а загружают и хранят «строки кэша» из 64 или даже 128 смежных байтов (8 или 16 чисел с плавающей запятой двойной точности) за один раз из памяти. Эти порции данных временно сохраняются в быстром кеше памяти и при необходимости записываются обратно. (На практике архитектура кеша теперь довольно сложна с 3 или 4 уровнями кеш-памяти, но основную идею можно объяснить одноуровневым кешем, подобным тому, который был у компьютеров в мои молодые годы.)

Теперь предположим, что - это массив с 10000 строк и столбцов, и я перебираю все записи. A

Если циклы вложены так, что внутренний цикл обновляет нижний индекс строки, то доступ к элементам массива будет осуществляться в порядке A (1,1), A (2,1), A (3,1), ... Когда при доступе к первой записи A (1,1) система перенесет строку кэша, содержащую A (1,1), A (2,1), ..., A (8,1), в кэш из основной памяти , Следующие 8 итераций самого внутреннего цикла работают с этими данными без каких-либо дополнительных передач основной памяти.

Если в альтернативном варианте мы структурируем циклы так, чтобы индекс столбца изменялся в самом внутреннем цикле, то записи A будут доступны в порядке A (1,1), A (1,2), A (1,3 ), ... В этом случае первый доступ приведет к тому, что A (1,1), A (2,1), ..., A (8,1) попадет в кэш из основной памяти, но 7/8 эти записи не будут использоваться. Доступ к A (1,2) во второй итерации принесет еще 8 записей из основной памяти и так далее. К тому времени, когда код приступил к работе над строкой 2 матрицы, запись A (2,1) вполне может быть выгружена из кэша, чтобы освободить место для других необходимых данных. В результате код генерирует в 8 раз больше трафика, чем необходимо.

Некоторые оптимизирующие компиляторы способны автоматически реструктурировать циклы, чтобы избежать этой проблемы.

Многие алгоритмы числовой линейной алгебры для умножения и факторизации матриц могут быть оптимизированы для эффективной работы со схемой упорядочения по главному или главному столбцу в зависимости от языка программирования. Неправильное поведение может оказать существенное негативное влияние на производительность.

Брайан Борхерс
источник