3
$\begingroup$

My function:

  sumprob[lst_,size_]:=Sum[Product[x,{x,part}],{part,Tuples[lst,{size}]}];

Example:

   sumprob[Range[1, 50, 3], 5]

13865791015625

How might I speed this up?

$\endgroup$
4
$\begingroup$

For optimization, worth playing around with and comparing a few different almost identical ways of doing the same thing. What seems like just syntactic sugar can sometimes cost:

In[1]:= sumprobAtCubed[lst__, size_] := Total[Times @@@ Tuples[lst, {size}]]

In[2]:= sumprobAtMap[lst__, size_] := Total[(Times @@ #) & /@ Tuples[lst, {size}]]

In[3]:= AbsoluteTiming[sumprobAtMap[xxx = RandomInteger[{1, 50}, 20], 5]]

Out[3]= {0.743279, 77114156402999}

In[4]:= AbsoluteTiming[sumprobAtCubed[xxx, 5]]

Out[4]= {4.352, 77114156402999}

In[5]:= xxx

Out[5]= {45, 48, 49, 17, 25, 8, 50, 31, 32, 27, 33, 36, 43, 16, 30, 35, 33, 29, 9, 3}

In[6]:= RepeatedTiming[sumprobAtMap[xxx, 5]]    

Out[6]= {0.618, 77114156402999}

In[7]:= RepeatedTiming[sumprobAtCubed[xxx, 5]]

Out[7]= {4.3, 77114156402999}

In[8]:= sumprob[lst_, size_] := Sum[Product[x, {x, part}], {part, Tuples[lst, {size}]}];

In[9]:= AbsoluteTiming[sumprob[xxx, 5]] (* Compare with poster's orig *)

Out[9]= {12.4336, 77114156402999}

(V.11.1 Mac OS)

Edit: Thanks ciao -- solving the problem should always win ;-)

In[14]:= AbsoluteTiming[Tr[xxx]^5]

Out[14]= {0.000017, 77114156402999}
$\endgroup$
  • 2
    $\begingroup$ I'd venture the version with map is getting auto-compiled. In any case, away from machines so can't test but seems like sumthing[l_,s_]:=Tr[l]^s; should do the trick quickly... $\endgroup$ – ciao Aug 10 '17 at 11:17
  • $\begingroup$ @ciao I think you're right re: auto-comp. Worth including a link to this question on compilation where Leonid Shifrin's answer has a nice discussion of Map and auto-compile. $\endgroup$ – John Joseph M. Carrasco Aug 10 '17 at 11:44
3
$\begingroup$

Although not as fast as ciao's formula the direct computation can be done more quickly like this, assuming the input list is all positive numbers:

sumprob2[lst_, size_] := Tr @ Exp @ Total[Tuples[N @ Log @ lst, {size}], {2}];

sumprob2[Range[1, 50, 3], 5] // Round // RepeatedTiming
{0.0511, 13865791015625}

Reference:

$\endgroup$
  • 1
    $\begingroup$ I like this, and nice reference. Perhaps worth warning about introduction of finite-precision arithmetic for speedup due to the N[#]&. I.e. Combined with the exp and log games, something like sumprob2[{10^4},5] will have an error of $O(10^5)$, so best with small integers etc. Still great trick, thanks for sharing! (+1) $\endgroup$ – John Joseph M. Carrasco Aug 11 '17 at 14:23
  • $\begingroup$ @John Good point, I should have warned of that. Old habits from Project Euler coming through, where I would use machine precision by default and check my answer, and only if it were wrong examine round-off errors. Of course that's not a good way to proceed in general. $\endgroup$ – Mr.Wizard Aug 11 '17 at 16:38

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.