Getting rid of nesting for loops which rely on reordering

Question

Daniel Tweed 2017-5-10

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/339684-getting-rid-of-nesting-for-loops-which-rely-on-reordering

评论： Daniel Tweed 2017-5-12

I have two K x N matrices B and H.. I need to calculate a new matrix z according to:

     z(k,n) = a + B(k,n)*H(k,n) + ...
             sum{j = 1...(i-1)} 2B(j,n)*H(j,n)t +...
             sum{j = (i+1)...K)} B(j,n)*H(j,n)

where a and t are scalar constants and i depends on the "rank" in the column if H is sorted descending, i.e. for

H = [1,2;5,6;3,4];

Column ranks are 2,3,1 for both columns. Sorry if this is confusing, I'm doing my best.

Anyways, I need to do this calculation for every element of z and I'm always only worried about the rank in each column and all terms in z are of elements of H and B in the same column.

My naive attempt to solve is using nested for loops:

    z = H.*B + a;
    for n=1:N       
        [Hsorted, idx] = sort(H(:,n),'descend');  % look at each column      
        for i=1:K                   %for each element of z(:,n)
            for j=1:K               %look at every other element in H(:,n)
                if j ~= i 
                    if  j < i                             
                        z(idx(i),n) = z(idx(i),n) + 2*B(idx(j),n)*Hsorted(j)*t;
                    else                               
                        z(idx(i),n) = z(idx(i),n) + B(idx(j),n)*Hsorted(j);
                    end
                end
            end  
        end 
    end

As you can probably imagine, this takes a lot of time for large K and N. I also am doing this as part of an iterative algorithm and a calculation like this gets done 2 or 3 times on each iteration. So, even for pretty small K and N, the time really adds up.

I've figured out that I can sort H, then reorder B according to the order of H with

     [Hsorted,orderH] = sort(H,'descend');
     [m,n] = size(B);
     Bsorted = B(sub2ind([m,n],orderH,repmat(1:n,m,1)));

and I'm guessing (hoping) that I can somehow replicate the ranked summation part of calculating the elements of z with matrix operations. This is where I'm stuck. Any help/advice or even a direction would be really appreciated

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2017-5-10

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/339684-getting-rid-of-nesting-for-loops-which-rely-on-reordering#answer_266470

编辑：Matt J 2017-5-10

在 MATLAB Online 中打开

      [K,N]=size(H);
       z = H.*B + a;
       [Hsorted, orderH] = sort(H,1,'descend');
       %sort B consistently with Hsorted
       idx=sub2ind([K,N],orderH,repmat(1:N,K,1));
       Bsorted=B(idx);
           e=ones(K);
           W=(triu(e,1)+2*t*tril(e,-1));
       z(idx)=z(idx)+W*(Bsorted.*Hsorted);

4 个评论
显示 2更早的评论隐藏 2更早的评论

Daniel Tweed 2017-5-11

编辑：Daniel Tweed 2017-5-11

That's a really good improvement. I wasn't expecting anything to great.

I actually see a much bigger improvement on my end (~300 times faster). I have several functions I need to calculate in the loop, and I think I can modify your answer to get those other functions out too. It's a HUGE help. Thanks!

Daniel Tweed 2017-5-12

I posted a follow up question here and I don't know if it'd be too much to ask if you could take a look. If not, thanks for what you've already given me.

请先登录，再进行评论。