Speed up indexing without using a loop

Hi all,

I would like to know if there is a way to speed up indexing procedure in the following code:

N; % given nx1 matrix with some values
D = inf(n,1);
D(1,1) = 0;
M = zeros(n,1)
while sum(M)~=length(N)
    D_adj = D;
    M_index = find(M);
    D_adj(M_index) = inf; % or any very large number
    [~,index_m] = min(D_adj);
    M(index_m) = 1;
    FOR LOOP % another code for a FOR loop to update values in matrix D;
end

Essentially, for every iteration within WHILE loop, I update a corresponding element of matrix M (by allocation value of 1). My main problem and what slows down my code is the procedure for computing M_index, updating the corresponding elements in matrix D_adj (by allocation value of inf so that they are not taken into account when computing the min value of all elements in matrix D_adj that have zero value in matrix M), and finding the index (of the min element in D_adj) in matrix D. Do you have any suggestion on how I can improve these operations?

Thanks in advance!

[James Tursa]

In addition to the code, what would be useful to us is a small example of inputs and desired outputs. That way we can more easily see what the end result should be, and maybe think of other ways to do it.

[Igor Dakic]

Thanks for your response. Sorry for not providing an example. Hope this can help. Please let me know if it doesn't.

Let's say N = [1;3;10;15;20], with n = 5 (number of elements). Then the initialization goes as follow:

D = inf(n,1);
D(1,1) = 0;
M = zeros(n,1);
WHILE there is at least one element equal to zero in M
D_adj = D; % in this iteration D_adj = [0;inf;inf;inf;inf]
M_index = find(M); % in this iteration M_index = [1;2;3;4;5]
[~,index_m] = min(D_adj); % in this iteration the smallest element in D_adj is 0, with an index = 1, i.e. index_m = 1
M(index_m) = 1; % in this iteration M gets updated as M = [1;0;0;0;0]. Note that elements in M do not have to be updated in a sequence, but random, depending on the procedure in the for loop below
FOR LOOP % for updating the values in matrix D, e.g. after the for loop D = [0;inf;inf;4;inf]
END FOR;
% now the procedure for indexing M is repeated: in this iteration D_adj = [0;inf;inf;4;inf]; M_index = [2;3;4;5]; index_m = 4 (4th element in D_adj has the min value and has a zero value in M); another FOR LOOP and so on...
END WHILE

[Igor Dakic]

Is there any suggestion on how this could be improved? Thanks!

[Jan]

This is no Matlab code. "WHILE"? "END WHILE"? How should we run this? Better provide real code, such that we can test suggestions. This is much easier than a "blind" programming.

Answer 1

[Jan]

Maybe logical indexing is faster:

N; % given nx1 matrix with some values
D = inf(n,1);
D(1,1) = 0;
M = false(n,1);
while ~all(M)
  D_adj = D;
  D_adj(M) = inf; % or any very large number
  [~, index_m] = min(D_adj);
  M(index_m) = true;
  FOR LOOP % another code for a FOR loop to update values in matrix D;
end

Remember the golden rule of optimizing code: Use the profiler at first to find the bottleneck of the function. If you accelerate a part of the by a factor 2, but this part needs 2% of the processing time, the total speedup is 1% only.

I doubt, that this indexing is the bottleneck of your code. But logical indexing should be at least faster.

I guess, that the part hidden behind "FOR LOOP" can be improved such, that the new minimal value can be found by a cheaper method.

[Igor Dakic]

Hi Simon,

Thanks for your answer. I run profiler and this was actually indicated as a bottleneck. I have copied my code here:

load('data.mat');
p_v = zeros(length(N_v),1);
p_v(1,1) = N_v(1,1);
d_v = inf(length(N_v),1);
d_v(1,1) = 0;
M = false(length(N_v),1);
MM = [1:1:length(N_v)]';
while ~all(M)
    d_v_adj = d_v;
    d_v_adj(M) = inf;
    [~,indx_v] = min(d_v_adj);
    M(indx_v) = 1;
    aa= A_indx(aa_indx1{indx_v,1},:);
    a = aa(~ismembc(aa(:,2),MM(M)),:);
    for i = 1:length(a(:,1))
        d_v_indx_j = a(i,2);
        if d_v(d_v_indx_j) > d_v(indx_v) + a(i,3)
            d_v(d_v_indx_j) = d_v(indx_v) + a(i,3);
            p_v(d_v_indx_j) = N_v(indx_v);
        end
    end
end

[Jan]

Posting the original code is useful. You create variables dynamically by a load without catching the inputs. This impedes the JIT acceleration and the debugging. I guess, that all data you load from the file in "N_v", "aa_indx1" and "A_indx"? Then:

Data     = load('data.mat');
N_v      = Data.N_v;
aa_indx1 = Data.aa_indx1;
A_indx   = Data.A_indx;
... expand this on demand

Replace:

MM = [1:1:length(N_v)]';

by the nicer:

MM = (1:length(N_v)).';

This will not improve the runtime, but there is no need for the concatenation operator [] here.

ismembc is not supported in modern Matlab versions anymore. I assume that this part can be simplified:

aa= A_indx(aa_indx1{indx_v,1},:);
a = aa(~ismembc(aa(:,2),MM(M)),:);

Something like this:

a = aa(M(aa(:, 2)));

but this is a bold guess only. I cannot run your code currently.

This loop can be vectorized:

for i = 1:length(a(:,1))
   d_v_indx_j = a(i,2);
   if d_v(d_v_indx_j) > d_v(indx_v) + a(i,3)
      d_v(d_v_indx_j) = d_v(indx_v) + a(i,3);
      p_v(d_v_indx_j) = N_v(indx_v);
   end
end

by:

c      = a(:, 2);  % do this before the loops
...
d      = d_v(index_v) + a(:, 3);
m      = d_v(c) > d;
d_v(m) = d(m);
p_v(m) = N_v(indx_v);

As said already: This is untested, but the idea should be clear.

[Igor Dakic]

Thanks a lot for your help!