I was trying to write an associative function f
using the attribute Flat
.
Remove[f];
SetAttributes[f, {Flat, OneIdentity}];
f[0, i_] := i;
f[i_, 0] := i;
f[i_, i_] := 0;
f[i_, j_] /; i != j := 6 - i - j;
To test the performance, I first generate two test sets A
and B
. They are of the same lengths and just differed by the patterns.
n = 20;
{A, B} = Flatten /@ {Transpose@#, #} &@ConstantArray[{0, 1, 2, 3}, n]
(*{{0, 0, ..., 1, 1, ..., 2, 2, ..., 3, 3, ...},
{0, 1, 2, 3, 0, 1, 2, 3,...}}*)
I would expect f@@
acting on them to have the similar efficiency. But to my surprise, I found f@@A
is about 40 times slower than f@@B
on my computer (Mathematica 10, Mac OS X). This slowdown ratio will continue to increase with the size $n$ of the problem, following a quadratic power law, i.e. $t_A/t_B\sim O(n^2)$, where $t_A$ or $t_B$ is the time to evaluate f@@A
or f@@B
respectively.
Timing[f @@ A] (* {0.041280, 0} *)
Timing[f @@ B] (* {0.001190, 0} *)
However, if instead of using the Flat
attribute, and forcing the function f
to be evaluated in sequential pairings, then f@@A
and f@@B
do have similar performance (f@@A
is even slightly faster, and both are faster than the best performance using the Flat
attribute).
Remove[f];
f[0, i_] := i;
f[i_, 0] := i;
f[i_, i_] := 0;
f[i_, j_] /; i != j := 6 - i - j;
f[i_, j_, k__] := f[f[i, j], k];
Timing[f @@ A] (* {0.000507, 0} *)
Timing[f @@ B] (* {0.000610, 0} *)
It seems to me that for Flat
attributed functions, Mathematica is seeking to arrange the pairing in an optimal way, but unfortunately this arrangement actually slowdown the performance prominently.
So my question is how does Mathematica actually arrange the pairing when evaluating Flat
attributed functions? In particular, why is f@@A
evaluated much slower than f@@B
with a $O(n^2)$ slowdown ratio in the former example?
- Ordering of downvalue definitions matters.
As @gpap mentioned in the comment below, the order of the definition of the downvalues of f
matters a lot. For example, I found the following arrangement gives an extreme contrast of $10^3$ times slowdown!
Remove[f];
SetAttributes[f, {Flat, OneIdentity}];
f[i_, i_] := 0;
f[0, i_] := i;
f[i_, 0] := i;
f[i_, j_] /; i != j := 6 - i - j;
Timing[f @@ A] (* {0.123521, 0} *)
Timing[f @@ B] (* {0.000071, 0} *)
f[i_ ,j_]
without the conditioni != j
is not working as expected.
The multiplication table for the monoidal (associative and has identity) function f
is like:
$$\begin{array}{c|cccc}
f & 0 & 1 & 2 & 3\\
\hline
0 & 0 & 1 & 2 & 3\\
1 & 1 & 0 & 3 & 2\\
2 & 2 & 3 & 0 & 1\\
3 & 3 & 2 & 1 & 0\\
\end{array},$$
which actually forms an Abelian group (but I do not want to impose the attribute Orderless
in my definition). Due to this Abelian property, the result f@@A
(or f@@B
) is not going to be affected by the ordering of the elements in A
(or B
), and it is also expected that f@@A == f@@B
to be True
. However it is found by @user18792 and @gpap that the result does change with the ordering of the elements as well as the ordering of downvalue definition of f
, if f[i_, j_] /; i != j
is not defined with the condition i != j
. Usually given the definition of f[i_, i_]
already, f[i_, j_]
is expected to only match the cases with different i
and j
. However this expectation is not working here. I would also like to know why.
f@@B
is -2 whereasf@@A
still 0. $\endgroup$ – gpap Nov 7 '14 at 12:12f@@B
evaluates to -2 is a bug. I do not expect the result to change. I found one has to enforce the conditioni != j
in the definition off[i_, j_]
in order to get the right result. But usually having definedf[i_, i_]
,f[i_, j_]
is assumed to take differenti
andj
. But I don't understand why it does not behave as expected here. $\endgroup$ – Everett You Nov 7 '14 at 19:03