Get indices from accumarray

All, in a previous question ( here ) I asked what the best way was to form a matrix from a given set of indices with data assuming you know the size of the resulting matrix (also assuming that you have multiple data points for each index). The best answer was most definitely to use accumarray and it does exactly what I want. I now have another issue however. Say I have an index vector and two different data vectors that correspond to the index vector:

ind = [ 1,  2,  4,  2, 5, 6,  4,  4,  9];
data1 = [32, 14, 36, 45, 3, 1, 78, 90, 69];
data2 = [1, .5, .7, .2, 1, 1, .9, .2, .6];

Now I want to form 2 3x3 matrices from the ind/data pairs. For the first one I want to store the maximum value at each index.

mat1 = reshape(accumarray(ind,data1,[9,1],@max,0),[3,3]);
mat1 = [32,90, 0;
        45, 3, 0;
         0, 1,69]

For the second matix I want to store the value from data2 that corresponds to the maximum value from before. I.E. I want mat2 to look like

mat2 = [ 1,.2, 0;
        .2, 1, 0;
         0, 1,.6]

What is the most efficient way to do this (note that in actuality I am working with matrices that are size 600x600 or so and thus I don't really want to have to loop through each value if at all possible. I have a couple ideas about using some logical checks with bsxfun or possibly creating my own anonymous function to use in accumarray (instead of max) but I feel like those are not the ideal solutions and will they will get pretty messy.

Thanks in advance.

EDIT: Additional information

Here is one of the ideas I have that is not entirely messy, but I do have some worries about it I will point out in a second.

[data2ind,mat2ind] = find(bsxfun(@eq,data1',mat1(:)'));
mat2 = zeros(size(mat1));
mat2(mat2ind) = data2(data2ind);

So this works for the given example, but I run into an issue when mat1 has repeated values. (for example say data1 = [32, 14, 36, 32, 3, 1, 78, 90, 69]; then this won't work as is since there will be multiple places where data1=mat1). Anyway I just wanted to show where I was at right now.

[Matt J]

Will the maxima always be uniquely attained? If not, what happens if distinct data2 values occur at the same maxima?

Answer 1

[Stephen23]

The fastest that I could come up with is to avoid accumarray and stick with loops only... about ten times faster on my computer! Note mat is renamed tam (so that I could run both answers in a timing comparison):

    tam1 = zeros(3);
    tam2 = zeros(3);
    for z = unique(ind)
        ida = ind==z;
        [tam1(z),idz] = max(data1(ida));
        tmp = data2(ida);
        tam2(z) = tmp(idz);
    end

and the outputs are:

>> tam1
tam1 =
    32    90     0
    45     3     0
     0     1    69
>> tam2
tam2 =
    1.0000    0.2000         0
    0.2000    1.0000         0
         0    1.0000    0.6000

And in case you are wondering, for 10000 iterations:

Elapsed time is 6.444340 seconds. % my first answer
Elapsed time is 0.702650 seconds. % this answer

[Andrew]

Thanks again Stephen. I had actually just come to a similar conclusion myself.

[Andrew]

Also,

while this is faster than the array stuff, an even faster loop structure is

mat1 = zeros(3);
mat1(ind) = -1e20;
mat2 = zeros(3);
for i = 1:length(ind)
    if data1(i)>mat1(ind(i))
        mat1(ind(i)) = data1(i);
        mat2(ind(i)) = data2(i);
    end
end

For 100,000 runs on my computer I get about 40 seconds using your loop structure and 0.33 seconds using my loop structure.

Answer 2

[Stephen23]

Basically we need a way to get the max indices... one option is to get them explicitly (although I make no claim about whether this fulfills your requirement for being "the most efficient way to do this"):

ind = [1, 2, 4, 2, 5, 6, 4, 4, 9];
data1 = [32, 14, 36, 45, 3, 1, 78, 90, 69];
data2 = [1, 0.5, 0.7, 0.2, 1, 1, 0.9, 0.2, 0.6];
%
C = accumarray(ind(:),data1,[],@(x){x},{0});
[M,X] = cellfun(@max,C);
mat1 = reshape(M,3,3)
C = accumarray(ind(:),data2,[],@(x){x},{0});
Y = cellfun(@(v,x)v(x),C,num2cell(X));
mat2 = reshape(Y,3,3)

Which displays this in the command window, matching your original output:

mat1 =
    32    90     0
    45     3     0
     0     1    69
mat2 =
    1.0000    0.2000         0
    0.2000    1.0000         0
         0    1.0000    0.6000

Unfortunately you did not give a sample vector with repeated values for us to try, but this vector of identical values:

data1 = [1,1,1,1,1,1,1,1,1];

produces this output:

mat1 =
     1     1     0
     1     1     0
     0     1     1
mat2 =
    1.0000    0.9000         0
    0.2000    1.0000         0
         0    1.0000    0.6000

Note that accumarray processes the values in the sequence of the subs indices, which means you need to change these indices (and the corresponding data) to get a different order of values in the output (and hence a different index from max).

[Andrew]

Thanks for the response Steven. While this does exactly what I want there is a major issue with speed both with the accumarray statements and with the cellfun statement. When I try this code on the actual data I am deal with it takes almost a full minute to run (if I just use accumarray with @max for the first matrix that takes about 2 seconds to run, just to give an idea of my computer speed). I'm hoping to find something that is a little more efficient if possible.

[Stephen23]

You could replace all of the cellfun and arrayfun calls with loops (of course with array preallocation!), which is usually a bit faster. I like cellfun just because it looks neater. I suspect that there is not much that will speed up the accumarray call, when using this method.

But I did figure out how to get accumarray to match the same order as the input vector data1 (so max finds the first value within each element of accumarray's output):

ind =   [ 1,   2,   4,   2, 5, 6,   4,   4,   9];
data1 = [32,  14,  36,  45, 3, 1,  78,  90,  69];
data2 = [ 1, 0.5, 0.7, 0.2, 1, 1, 0.9, 0.2, 0.6];
%
[R,C] = ind2sub([3,3],ind(:));
[X,idy] = sortrows([R,C],[2,1]);
G = accumarray(X,data1(idy),[],@(x){x},{0});
[mat1,idx] = cellfun(@max,G)
H = accumarray(X,data2(idy),[],@(x){x},{0});
mat2 = cellfun(@(v,x)v(x),H,num2cell(idx))

Answer 3

[Matt J]

    function DoIt

       ind = [ 1,  2,  4,  2, 5, 6,  4,  4,  9].';
        data1 = [32, 14, 36, 45, 3, 1, 78, 90, 69].';
        data2 = [1, .5, .7, .2, 1, 1, .9, .2, .6].';

        mask=1:length(data1);

        mat1=reshape(accumarray(ind,data1,[9,1],@max,0),3,3);
        loc= accumarray(ind,mask,[9,1],@attainer,nan);
        map=~isnan(loc);

        mat2=mat1;
        mat2(map)=data2(loc(map)),

            function idx=attainer(Q)
                      [~,mxpt]=max(data1(Q));
                        idx=Q(mxpt);
            end

    end