Alternative way for nested for loops and if statements

Hi everyone,

I am looking an alternative way for the algorithm that is mentioned below. There are nested for loops and multiple if statements.

I would like to run it faster, do you have any opinion how to do that ?

Thanks in advance.

for i = 1: totalCount
         for j= 1: totalCount2

                if (telArray(i,1) ~= telArray(j,1))
                    
                    firstTel = find ( telArray(i,1) == sortedArray(:,3) ,1 );
                    [r] = find(heuristic(:,firstTel)~= 0); 
                    placeOfFirst = r(1,1);                   
    
                    secondTel  = find ( telArray(j,1) == sortedArray(:,3) ,1 );              
                    [r] = find(heuristic(:,secondTel )~= 0); 
                    placeOfSecond = r(1,1);
                        
                    idx = placeOfFirst:repRate:macroPeriod;
                    sum1= sum(basePeriod(idx,2)); 

                    idx = placeOfSecond:repRate:macroPeriod;
                    sum2= sum(basePeriod(idx,2)); 

                    if( ( sum1> sum2+ 10 ) && (sortedArray (firstTel,1) > (sortedArray (secondTel , 1) + 1) )  )

                        firstDifference = sum1- sum2
                        sum1= sum1 + (macroPeriod / repRate) * ( sortedArray (secondTel ,1) - sortedArray (firstTel,1) );
                        sum2= sum2- (macroPeriod / repRate) * ( sortedArray (secondTel ,1) - sortedArray (firstTel,1) );
                        secondDifference = abs(sum1 - sum2);
                        
                        if ( secondDifference < (firstDifference - 5) )                     

                            x = firstBP:repRate:macroPeriod;
                            basePeriod(x, 2) = basePeriod(x, 2) + sortedArray (secondTel ,1) - sortedArray (firstTel,1);
                              
                            y = secondBP:repRate:macroPeriod;
                            basePeriod(y, 2) = basePeriod(y, 2) + sortedArray (firstTel,1) - sortedArray (secondTel ,1);
                                                       
                        end 
                    end
                end
            end
 end

[Walter Roberson]

Minor optimization:

[r] = find(heuristic(:,firstTel)~= 0);
placeOfFirst = r(1,1);      

since you never use the other values of r, you can modify this to

placeOfFirst = find(heuristic(:,firstTel), 1);

[cglr]

Thank you for your offer.

I made this modification in the code but surprisingly run time did not change remarkably :) (it is almost the same)

Is there any alternative for nested for loops?

[Walter Roberson]

I think you just might be able to create... Let me see... 4? 6? dimensional arrays that you compare everything to everything and then zero out the parts you do not need by using parallel index arrays and logical operations and operations along just the right axes...

Let me see... size(telArray,1) x size(telArray,1) x size(sortedArray,1) x repRate ... at least.

Estimated amount of the calculations that would be thrown away... Ummm, 98% or so.

Many algorithms can be converted from for loops into multidimensional vectorized problems, if you have enough memory, and are willing to wait the extra time to do the calculations that you are just going to throw away afterwards. Sometimes it can be worth doing, if the extended multidimensional problem fits into memory on a GPU, so that the extra calculations that will be thrown away are calculated in massively parallel form.

But more of the time, leaving things in loop form is

• less memory
• much much clearer code
• faster

[Steven Lord]

Taking a step back, can you explain in words not code the goal of this script? What is it supposed to do? There may be a function or a combination of a few functions that can achieve your goal more efficiently and/or be clearer to understand.

[cglr]

Sure.

I have one sorted array that keeps all messages in there.

Each messages have duration in microseconds and individual period in miliseconds. Messages are placed into each cycle looking at their individual period and duration. You can find one example below. My goal is to minimize duration of maximum cycle and to keep all of them in balanced.

In nested for loops I make comparison for all possibilities according to messages (1-2,1-3,...9-7,9-8), to find out is there any message that have bigger duration but placed in small duration cycle. Of course, there are any other constraints but this is the first step.

Is it more clear now ?

Answer 1

[J. Alex Lee]

For nested loops you can keep as much outside of the inner loop as possible, in this case the search for placeOfFirst looks like it can be outside the inner loop?

At first glance it doesn't seem you can really get away from the nested structure, though maybe there is...

But it also looks like you may be spending a lot of time on redundant "find()" statements. It looks like you could pre-find the indices rather than find-ing each loop (for the inner find)

Not really an optimization, but to avoid nested if's this case, you can test for opposite of what you want and continue, since you don't have other bits of code happening after the if's

for i = size(telArray,1):-1:1
    idx = find ( telArray(i,1) == sortedArray(:,3) ,1 );
    placeof_a(i,1) = find(heuristic(:,idx)~=0,1);
end

for i = 1: totalCount
    for j= 1: totalCount2
        if telArray(i,1) == telArray(j,1)
            continue
        end
        
        placeOfFirst  = placeof_a(i);
        placeOfSecond = placeof_a(j);
        % ...
        
    end
end

Does this work?