A matrix and a column vector containing indices, how to iterate with no loop?

1
votes

I have a big matrix (500212x7) and a column vector like below

matrix F         vector P
0001011          4
0001101          3
1101100          6
0000110          1
1110000          7

The vector contains indices considered within the matrix rows. P(1) is meant to point at F(1,4), P(2) at F(2,3) and so on.

I want to negate a bit in each row in F in a column pointed by P element (in the same row).

I thought of things like

F(:,P(1)) = ~F(:,P(1));
F(:,P(:)) = ~F(:,P(:));

but of course these scenarios won't produce the result I expect as the first line won't make P element change and the second one won't even let me start the program because a full vector cannot make an index.

The idea is I need to do this for all F and P rows (changing/incrementing "simultaneously") but take the value of P element.

I know this is easily achieved with for loop but due to large dimensions of the F array such a way to solve the problem is completely unacceptable.

Is there any kind of Matlab wizardry that lets solving such a task with the use of matrix operations?

3
arraysmatlabmatrixoctave

3 Answers

4
votes

I know this is easily achieved with for loop but due to large dimensions of the F array such a way to solve the problem is completely unacceptable.

You should never make such an assumption. First implement the loop, then check to see if it really is too slow for you or not, then worry about optimizing.

Here I'm comparing Luis' answer and the trival loop:

N = 500212;
F = rand(N,7) > 0.6;
P = randi(7,N,1);

timeit(@()method1(F,P))
timeit(@()method2(F,P))

function F = method1(F,P)
   ind = (1:size(F,1)) + (P(:).'-1)*size(F,1); % create linear index
   F(ind) = ~F(ind); % negate those entries
end

function F = method2(F,P)
   for ii = 1:numel(P)
      F(ii,P(ii)) = ~F(ii,P(ii));
   end
end

Timings are 0.0065 s for Luis' answer, and 0.0023 s for the loop (MATLAB Online R2019a).

It is especially true for very large arrays, that loops are faster than vectorized code, if the vectorization requires creating an intermediate array. Memory access is expensive, using more of it makes the code slower.

Lessons: don't dismiss loops, don't prematurely try to optimize, and don't optimize without comparing.

3
votes

Another solution:

xor( F, 1:7 == P )

Explanation:

  • 1:7 == P generates one-hot arrays.
  • xor will cause a bit to retain its value against a 0, and flip it against a 1
2
votes

Not sure if it qualifies as wizardry, but linear indexing does exactly what you want:

F = [0 0 0 1 0 1 1; 0 0 0 1 1 0 1; 1 1 0 1 1 0 0; 0 0 0 0 1 1 0; 1 1 1 0 0 0 0];
P = [4; 3; 6; 1; 7];
ind = (1:size(F,1)) + (P(:).'-1)*size(F,1); % create linear index
F(ind) = ~F(ind); % negate those entries