How to build a table inside a parfor loop

I am trying to build a lookup table inside a for loop. A minimal example of what I would like to do is:

% I start with a lookup table, first column is input, second is output (2*input)
table= [ 1  2
         3  6
         5 10
         2  4]; 

n = 30;   % number of input values  

inputs=ceil(unifrnd(0,100,n,1)); %inputs are random numbers from 1 to 100

doubles=zeros(n,1); % doubles collects the outputs... that are doubles

parfor ii=1:n
    comparison= table(:,1)==inputs(ii);  % check if already computed:
    if any(comparison)                   % if already computed
        doubles(ii)=table(comparison,2); % then, retrieve it from table;
    else                                 % if never computed before
        twice=2*inputs(ii);              % then, compute it ...
        doubles(ii)=twice;               % ... use it ...
        table=[       table
                 inputs(ii) twice];      % ... and store it in the table.
    end
end

Unfortunately, this doesn't work because table is seen as a temporary variable by the parfor loop. How can I solve this? Note, I cannot preallocate the vector doubles, because in the real problem n=1e40.

Thank you, Paolo

Answer 1

[Edric Ellis]

PARFOR is designed for "embarassingly parallel" problems where each iteration of the loop is independent. Unfortunately, the problem here is that you are updating the variable "table" in the last line of the loop. This means that the iterations are not independent, because the value of "table(:,1)" can change as the loop progresses.

I can't immediately see how to refactor this algorithm. You may need to use SPMD to allow communication between the loop iterates to implement your algorithm.

[Paolo Bocchini]

Thank you for your answer! I though this application was still "embarassingly parallel" since I am not "really" updating a variable, but only concatenating, adding new elements at the bottom. Since concatenation is handled correctly by parfor, I thought that this slightly different use of the concatenation could have been somehow handled by parfor too.

I will look into SPMD.

Thank you again and... isn't it always surprising how the the implementation of TRIVIAL algorithms (such as this one) can become complex and tricky?