unexpected accumarray behavior

I recently discovered the function accumarray. Example 2 in the doc for this function produced a counter-intuitive answer for me prompting me to investigate. This example is repeated below.

Example 2

val = 101:106;
subs=[1 2; 1 2; 3 1; 4 1; 4 4; 4 1];
B = accumarray(subs,val,[],@(x)sum(diff(x)))
B =
     0    -1     0     0
     0     0     0     0
     0     0     0     0
     2     0     0     0

Intuitively, the nonzero values should have the same sign. I was surprised to find that this is a built-in function, thus I was unable to inspect the code directly to determine the source of this behavior. I have a more illuminating example (below) that points to the source of the behavior in question but does not fully explain it.

val = [1 2 3 4];
subs1 = [1 2; 1 2; 2 1; 2 1];
subs2 = [1 1; 1 1; 2 2; 2 2];
func = @(x)x(1);
A = accumarray(subs1,val,[],func)
A =
     0     2
     3     0
B = accumarray(subs2,val,[],func)
B =
     1     0
     0     3

This shows that, for the subs1 call, the bin for position (1,2) is [2 1] when func is called, while, for the subs2 call, the bin for position (1,1) is [1 2] when func is called.

My Questions: Why is the order in which entries of val are accumulated into bins dependent on the bin location? How can I predict the accumulation order? Can a more consistent behavior be forced?

Answer 1

[Oleg Komarov]

From the documentation of accumarray:

Note If the subscripts in subs are not sorted, fun should not depend on the order of the values in its input data.

EDIT

[trash,idx] = sort(sub2ind([4,4],subs(:,1),subs(:,2)));
B = accumarray(subs(idx,:),val(idx),[],@(x)sum(diff(x)));

[Jonathan]

Yes, this is true. It is good that you point this out. Still, my three questions are unanswered by this observation.

[Oleg Komarov]

There's no way to tell the order if subs are not ordered. Thus, order the subs. You can transform them into linear indices and use the size argument of accumarray to force a matrix output.

[Oleg Komarov]

See my edit with the example.

[Jonathan]

Thank you for your help. I tried this on my example with the results you predicted. I now understand (correctly, I hope) that for the subscripts in subs to be sorted they have to be sorted in ascending order _with respect to linear indices_. this was not at all clear to me before.

Thank you!

Answer 2

[the cyclist]

Looking at the documentation example (but not yours, yet), it seems to me there is a typo in the documentation. I get B(1,2) = 1, not -1, when I do that accumarray(). That is also the value I expect.

In your example, I do not get the same result for "A" that you do. I get

A = [0 1
     3 0];

This is just as I expect. The (1,2) element is the "accumulation" of the values [1 3], where you have defined the accumulation function to be the first element of the vector. Similarly, A(2,1) is the "accumulation" of [3 4]. Again, because you have defined the accumulation function to be taking the first element, that value is "3".

Does that help?

[Jonathan]

This is interesting. When I duplicated the example in the documentation I got the same answer as the documentation. Since you did not, this points to an implementation dependent answer. Would you help us troubleshoot this theory by sharing your Matlab version and Operating System? Mine are R2010a and Windows XP Pro SP3. I duplicated my result on a different machine in R2010b with the same OS.

What results do others with a different version/OS get?

[Jonathan]

When I just tried the same on Redhat Linux with 64-bit R2010b, my A and B matrices both show a 1 in the first row. I should note that in my above comment R2010a is 32-bit and R2010b is 64-bit. So, both of the Windows XP tries give a 2 in the first row, while the Redhat try gives a 1 in the first row.

[the cyclist]

I get the results I mentioned for both R2011a and R2011b, on Mac OS X (10.6.8).