Векторизация нескольких вложенных циклов, содержащих круговое смещение в MATLAB

Question

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

for ss = 1:max_n_steps+1 % max steps + possibility of NO STEP!!
    for tt = 1:max_n_steps+1
        for uu = 1:max_n_steps+1
            curr_perm = horzcat(curr_perm, curr_first + circshift(curr_second, ss-1, 2) + circshift(curr_third, tt-1, 2) + circshift(curr_fourth, uu-1, 2));
        end
    end
end

Это проходит через все четыре матрицы (curr_first, curr_second и т. Д.), Суммирует их и объединяет их с предыдущими комбинациями.Это приводит к удовлетворительному массиву всех возможных сумм столбцов.Однако, чем больше циклов я ввожу (например, когда у меня 5 матриц вместо 4), это занимает все больше и больше времени.Есть ли возможность векторизовать этот процесс?Я видел такие вещи, как bsxfun, но не знаю, как их применять здесь.

Спасибо!

Answer 1

Основная неэффективность вашей начальной точки не в том, что она использует циклы, а в векторе, а в том, что она пересчитывает вызовы circshift с той же матрицей и с одинаковым смещением много раз.Например, ваше выражение circshift(curr_second, ss-1, 2) изменяется только при изменении ss, но оценивается на каждой итерации внутренних циклов:

for tt = 1:max_n_steps+1
    for uu = 1:max_n_steps+1

, хотя curr_second и ss не изменяются во всемэти циклы.

Вы можете избежать этого, оценивая все возможные сдвиги каждой матрицы и затем добавляя перестановки этих сдвигов путем индексации этих результатов:

curr_second_shifts = nan([size(curr_second) max_n_steps+1]);
curr_third_shifts  = nan([size(curr_third ) max_n_steps+1]);
curr_fourth_shifts = nan([size(curr_fourth) max_n_steps+1]);

for ii = 1:max_n_steps+1
    curr_second_shifts(:,:,ii) = circshift(curr_second, ii-1, 2);
    curr_third_shifts( :,:,ii) = circshift(curr_third,  ii-1, 2);
    curr_fourth_shifts(:,:,ii) = circshift(curr_fourth, ii-1, 2);
end

for ss = 1:max_n_steps+1
    for tt = 1:max_n_steps+1
        for uu = 1:max_n_steps+1
            curr_perm = horzcat(curr_perm, curr_first + ...
                                           curr_second_shifts(:,:,ss) + ...
                                           curr_third_shifts( :,:,tt) + ...
                                           curr_fourth_shifts(:,:,uu));
         end
    end
end

Чтобы полностью векторизовать это, выможет хранить различные сдвиги каждой матрицы по разному измерению;Затем одноэлементное расширение MATLAB заполнит этот n-мерный массив соответствующими перестановками при добавлении.

curr_second_shifts = nan([size(curr_second) max_n_steps+1]);
curr_third_shifts  = nan([size(curr_third ) 1 max_n_steps+1]);
curr_fourth_shifts = nan([size(curr_fourth) 1 1 max_n_steps+1]);

for ii = 1:max_n_steps+1
    curr_second_shifts(:,:,ii)     = circshift(curr_second, ii-1, 2);
    curr_third_shifts( :,:,1,ii)   = circshift(curr_third,  ii-1, 2);
    curr_fourth_shifts(:,:,1,1,ii) = circshift(curr_fourth, ii-1, 2);
end

curr_perm = curr_first  + ...
            curr_second_shifts + ...
            curr_third_shifts  + ...
            curr_fourth_shifts);

Затем, чтобы все перестановки, расположенные в более высоких измерениях, вернулись в исходную серию столбцов, просто переиндексируйте с двумясамое высокое измерение:

curr_perm = curr_perm(:,:);

Однако это может быть дополнительно векторизовано, чтобы исключить отдельные переменные для матрицы, что будет важно, если вы добавите больше измерений к этим перестановкам.Давайте определим curr как трехмерную матрицу, такую ​​что:

curr = cat(3,curr_first,curr_second,curr_third,curr_fourth);

Затем все сдвиги можно рассчитать одним вызовом circshift на смещение:

curr_shift = nan([size(curr(:,:,2:end)) max_n_steps+1]);

for ii = 1:max_n_steps+1
    curr_shift(:,:,:,ii) = circshift(curr(:,:,2:end), ii-1, 2);
end

, а затемперестановка с увеличивающимся числом одноэлементных измерений перед добавлением:

curr_perm = curr_first;

for ii = 1:size(curr_shift,3)
    curr_perm = curr_perm + permute(curr_shift(:,:,ii,:),[1:3 5:(ii+3) 4]);
end

curr_perm = curr_perm(:,:);

Для MATLAB ранее, чем R2016b, расширение не произойдет неявно, и вам потребуется bsxfun, как вы предлагаете:

for ii = 1:size(curr_shift,3)
    curr_perm = bsxfun(@plus, curr_perm, permute(curr_shift(:,:,ii,:),[1:3 5:(ii+3) 4]);
end