Я читал, что если, например, у меня есть двойной 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
matlab
efficiency
Тензор
источник
источник
Forпетли очень медленные в MATLAB. Вы должны по возможности избегать явных циклов в MATLAB. Вместо этого обычно проблема может быть выражена в терминах матричных / векторных операций. Это MATLABic способ. Есть также много встроенных функций для инициализации матриц и т. Д. Например, есть функция ones () , которая установит все элементы матрицы в 1 (путем расширения, в любое значение путем умножения (скаляр умножается на единичную матрицу)). Это также работает с трехмерными массивами (которые, я думаю, покрывают пример здесь).Ответы:
Короткий ответ, вы хотите иметь крайний левый индекс на самом внутреннем цикле. В вашем примере индексы цикла будут идти k, j, i, а индексы массива будут i, j, k. Это связано с тем, как MATLAB хранит различные измерения в памяти. Для получения дополнительной информации см. № 13 этого поста Reddit .
источник
Несколько более длинный ответ, объясняющий, почему более эффективно, чтобы самый левый индекс изменялся наиболее быстро. Есть две ключевые вещи, которые вам нужно понять.
Во-первых, 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 раз больше трафика, чем необходимо.
Некоторые оптимизирующие компиляторы способны автоматически реструктурировать циклы, чтобы избежать этой проблемы.
Многие алгоритмы числовой линейной алгебры для умножения и факторизации матриц могут быть оптимизированы для эффективной работы со схемой упорядочения по главному или главному столбцу в зависимости от языка программирования. Неправильное поведение может оказать существенное негативное влияние на производительность.
источник