8
$\begingroup$

I need to do some iterative summations. Here is a minimum working example:

data = Table[RandomReal[], {x, 1, 1000000}];
(* Method 1 *)
Timing[Total[Table[Total[ Table[data[[i]], {i, j, 10 + j}]], {j, 1, Length[data] - 5*10}]]]

(* Method 2, with constant index *)
m = 10;
Timing[Total[Table[Total[ Table[data[[i]], {i, j, m + j}]], {j, 1, Length[data] - 5*m}]]]

And here are the outputs:

{0.5625, 5.49936*10^6}

{9.28125, 5.49936*10^6}

For some reason, using m=10 makes it much slower. I will need to do a bunch of m's, so this is the bottom of a larger nest.

What is a faster way to do this?

Late Edit:

Bonus question: How to optimize this one as well:

Timing[Total[Table[  (Total[ Table[data[[i]], {i, j, m + j}]])^2   , {j, 1, Length[data] - 5*m}]]]
$\endgroup$
12
$\begingroup$

The problem lies mostly in the inner Table:

Timing[Total[Table[Total[Table[data[[i]], {i, j, 10 + j}]], {j, 1,Length[data] - 5*10}]]]

m = 10;
Timing[Total[Table[Total[Table[data[[i]], {i, j, m + j}]], {j, 1, Length[data] - 5*10}]]]

{0.366407, 5.50276*10^6}

{8.01738, 5.50276*10^6}

I think the reason is this: Because the global variable m could theoretically change its value during the computions, the body of the outer table cannot be compiled (without calls to MainEvaluate). At least, the JIT compiler does not analyze the body of the outer loop thoroughly enough to decide that m won't change.

You can help the JIT compiler by using With:

With[{m = 10},
 Timing[Total[Table[Total[Table[data[[i]], {i, j, m + j}]], {j, 1,Length[data] - 5*m}]]]
 ]

{0.369601, 5.5049*10^6}

Addendum:

By focusing on the post's title, I have completely overlooked the question on how to make it faster. Here is my proposal (c) vs. the OP's one (a) and Carl's (b):

a = With[{m = 10},
     Total[
      Table[Total[Table[data[[i]], {i, j, m + j}]], {j, 1, 
        Length[data] - 5*m}]]
     ]; // RepeatedTiming // First
b = Total@ListCorrelate[ConstantArray[1., m + 1], 
      data[[;; -50 + m - 1]]]; // RepeatedTiming // First
c = Plus[
     Range[1., m].data[[1 ;; m]],
     (m + 1) Total[data[[m + 1 ;; -5*m - 1]]],
     Range[N@m, 1., -1].data[[-5 m ;; -4 m - 1]]
     ]; // RepeatedTiming // First

a == b == c

0.28

0.017

0.0018

True

$\endgroup$
9
$\begingroup$

You can use ListCorrelate:

m=10;
Total @ ListCorrelate[ConstantArray[1,m+1], data[[;;-4 m-1]]] //AbsoluteTiming

{0.017725, 5.50044*10^6}

Bonus question

For the bonus question:

data = RandomReal[1, 10^5];

Your version:

With[{m = 10},
    Total[Table[(Total[Table[data[[i]],{i,j,m+j}]])^2,{j,1,Length[data]-5*m}]]
] //AbsoluteTiming

{0.448739, 3.11778*10^7}

Using ListCorrelate again:

m = 10;
#.#& @ ListCorrelate[ConstantArray[1, m+1], data[[ ;; -4 m - 1]]] //AbsoluteTiming

{0.018401, 3.11778*10^7}

$\endgroup$
  • $\begingroup$ Carl, nice use of the dot-product to overcome the internal compiling issues that would prevent implementing the mapping of a slotted set! I was attempting a solution with this same thought process, but was unable to overcome the change of #^2 to #1^2 during my attempts at a solution. Your use of ListCorrelate will be helpful in the future, thank you! $\endgroup$ – CA Trevillian May 17 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.