Here is a method that has far better computational complexity than Position
:
f1[m_] := Cases[Last @ Reap @ MapIndexed[Sow[#2, #] &, m, {2}], {_, __}]
Test:
SeedRandom[0]
m = RandomInteger[5, {4, 4}];
m // MatrixForm
$\left(
\begin{array}{cccc}
5 & 1 & 0 & 4 \\
0 & 4 & 1 & 2 \\
1 & 0 & 3 & 3 \\
4 & 2 & 0 & 4
\end{array}
\right)$
f1[m]
{{{1, 2}, {2, 3}, {3, 1}},
{{1, 3}, {2, 1}, {3, 2}, {4, 3}},
{{1, 4}, {2, 2}, {4, 1}, {4, 4}},
{{2, 4}, {4, 2}},
{{3, 3}, {3, 4}}}
Alternative code; it is slightly faster than f1
in version 7, but might faster (or slower) in newer versions:
f2[m_] := Module[{x}, Cases[ArrayRules[m, x] ~GatherBy~ Last, {_, __}][[All, All, 1]] ];
To my consternation I tried the same method that rasher recently posted but I managed to lose the potential performance of that method. My mistake was to use Extract[m, #] &
instead of m[[#[[1]], #[[2]]]] &
. I expected Extract
to be at least as fast; I still don't know why it is not. Nevertheless my revised f3
:
f3[m_] := GatherBy[Tuples @ Range @ Dimensions @ m, m[[#[[1]], #[[2]]]] &] ~Cases~ {_, __}
Timings
Comparative timings with Öskå's pos
. Timing function:
SetAttributes[timeAvg, HoldFirst]
timeAvg[func_] := Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}]
On small arrays my functions are only a few times faster. (f3
is already much faster.)
m = RandomInteger[40, {15, 20}];
Scan[Print @ timeAvg @ #[m] &, {pos, f1, f2, f3}]
0.0005984
0.00020992
0.0002096
0.000089856
But as the array size and especially number of unique elements increases pos
rapidly slows down:
m = RandomInteger[500, {40, 70}];
Scan[Print @ timeAvg @ #[m] &, {pos, f1, f2, f3}]
0.04744
0.0020464
0.0019968
0.000848
m = RandomInteger[3000, {120, 160}];
Scan[Print @ timeAvg @ #[m] &, {pos, f1, f2, f3}]
2.792
0.02372
0.02308
0.005872
m = RandomInteger[10000, {300, 400}];
Scan[Print @ timeAvg @ #[m] &, {pos, f1, f2, f3}] (* warning: very slow! *)
122.991
0.2404
0.2404
0.04244