Timing differences between multiple executions of identical code

I have a list of pairs of numbers and I'd like to change the sign of the second element in each pair i.e. $(a,b)\rightarrow (a,-b)$.

I'm sure there are many ways to do this. Starting from an example list the ways I know are

list = Table[{j, j}, {j, 200}];

Table[{list[[s, 1]], -list[[s, 2]]}, {s, 1, Length[list], 1}]

Partition[Riffle[Transpose[list][[1]], -1 Transpose[list][[2]]], 2]

{#1, -#2} & @@@ list


They all produce the same output and I expected the final method to be the fastest as it utilises Mathematica's functional programming abilities. More generally I expected the timings for each method to be constant upon repetition, meaning if I executed the same code many times I'd get the same answer.

However when I timed them for 10 runs of 1000 executions each I get the following

Table[Timing[
Do[Table[{list[[s, 1]], -list[[s, 2]]}, {s, 1, Length[list],
1}], {1000}]][[1]], {10}]

(*{0.344, 0.281, 0.312, 0.313, 0.265, 0.297, 0.328, 0.375, 0.297, 0.297}*)

Table[Timing[
Do[Partition[Riffle[Transpose[list][[1]], -1 Transpose[list][[2]]],
2], {1000}]][[1]], {10}]

(*{0.11, 0.093, 0.125, 0.11, 0.109, 0.094, 0.109, 0.094, 0.109, 0.125}*)

Table[Timing[Do[{#1, -#2} & @@@ list, {1000}]][[1]], {10}]

(*{0.219, 0.219, 0.219, 0.25, 0.218, 0.219, 0.25, 0.188, 0.234, 0.312}*)


and it seems I was wrong on both of my expectations. Variable timings and @@@ came in second place. Partition[Riffle..... was approx twice as fast as the others.

Could someone explain the reasons for (a) the variable timing and (b) why the Partition[Riffle..... method is more efficient than the @@@method when I would have guessed it has more computational steps?

-
What about clearing your cache? Would that make a difference? And should you be using AbsoluteTiming? – drN Sep 26 '12 at 15:15
Two orders of magnitude faster is the simple and natural list . {{1, 0}, {0, -1}}. For larger lists, the advantage grows to many orders of magnitude. – whuber Sep 26 '12 at 15:21
Note that the first method's time is linear with list length, while the other two's time doesn't seem to depend on the list's length. – stevenvh Sep 26 '12 at 15:32
Actually, @stevenh, the first method is worse than linear, whereas (at least eventually) the others are linear (it's impossible to do any better asymptotically). By the time the length is $10^5$, the timings for one iteration are 8.6, 0.003, and 0.1 seconds. (The timing for the matrix multiplication is 0.0000004 seconds.) – whuber Sep 26 '12 at 15:40
@whuber I did try something as direct as that. Only thing is my attempt was list.{1,-1}. It didn't work so I started with the above. Looking back now the dimensions are obviously wrong but ya you're right that is more natural method to do it though. Thanks. – fizzics Sep 26 '12 at 15:47

1 Answer

Your question are impossible to answer in detail. Let my try anyway:

a) No one can tell you the exact reason of the different timings on your machine. You should keep in mind that it is very possible, that one run of your computation has side-effects you are not aware of. One obvious example for such a behavior can be demonstrated when you try this on a fresh Mathematica kernel:

AbsoluteTiming[Prime[10^11]]
AbsoluteTiming[Prime[10^11]]
(*
Out[1]= {5.178889, 2760727302517}
Out[2]= {0.000018, 2760727302517}
*)


We just don't no all details of the MathKernel and therefore you can assume that there are things going on which lead to different execution speed.

The next thing is, that you have a computer where your Mathematica session is definitely not the only running program. Even if you close everything there are a lot of deamons and services that run in background. Can you assure that none of them is taking away a bit of your computational resources?

The solution for this is to repeat the measurement many times and if the function is very small (like yours) do it on a lot of data.

b) Again, the only thing you do is (as you wrote) guessing that @@@ should be faster. A general rule in Mathematica is, that the available list manipulating functions are very fast. Another important point is to express the problem as natural as possible. This is a very vague sentence, but @whuber showed you exactly what I mean here. Expression your problem as matrix multiplication is indeed very fast and this is reasonable, because the Dot function is a very fundamental and often used operation.

Conclusion

Say you have a some function and you want to measure its execution time. You could run it 100 times, measure the AbsoluteTiming and look at the Mean and the StandardDeviation of the timings. This gives you a very stable value for the mean and it shows you, how the timing fluctuates

SetAttributes[measure, {HoldAll}];
measure[expr_] := #[Table[First[AbsoluteTiming[expr]], {100}]] & /@ {Mean,StandardDeviation}


The HoldAll attribute is required to evaluate your method inside the AbsoluteTiming. And now you can measure the different methods. I take 10^5 values here

list = RandomReal[{-1, 1}, {100000, 2}];

measure[list.{{1, 0}, {0, -1}}]
(* {0.001563, 0.000051} *)

measure[Transpose[{1, -1}*Transpose[list]]]
(* {0.002419, 0.000181} *)

measure[Partition[Riffle[Transpose[list][[1]], -1 Transpose[list][[2]]], 2]]
(* {0.005972, 0.000133} *)

measure[{#1, -#2} & @@@ list]
(* {0.125322, 0.001092} *)

-
List manipulation functions fast? Don't forget Append and Prepend. They are excruciatingly slow. – Sjoerd C. de Vries Sep 26 '12 at 22:04
+1. You will discover yet another explanation if you study the full distribution of times: timing is discrete and coarse. Use measure[expr_, n_] := SortBy[Tally[ Table[Round[First[AbsoluteTiming[expr;]], .00001], {n}]], First] and experiment like this: results1 = measure[list.{{1, 0}, {0, -1}}, 100]. Despite the rounding to five decimal places, the results will usually be in whole multiples of 0.001, give or take some (single precision!) floating point error. – whuber Sep 27 '12 at 3:58
@SjoerdC.deVries Fair enough, but try to guess the experience level of the OP compared to yours. Do you really think it's a good idea to not lead him to the usage of more list manipulation functions? It is a general rule that they are in most cases faster than the procedural solutions we often complain about. When someone finally has dug deeper into the topic, he'll see why Append and Prepend have to be slow in the light of how arrays are implemented in Mma. – halirutan Sep 27 '12 at 10:54
@SjoerdC.deVries And if (s)he asks then whether it is possible to improve the speed of Append you can refer him to e.g. David Wagners book on page 309. – halirutan Sep 27 '12 at 10:57
@whuber Good point. I didn't check this. Why didn't you just edit my post and add the information? :-) – halirutan Sep 27 '12 at 10:59