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?
$\begingroup$
$\endgroup$
1
2 Answers
$\begingroup$
$\endgroup$
2
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}
answered Aug 10, 2017 at 11:05
-
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$– ciaoAug 10, 2017 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$ Aug 10, 2017 at 11:44
$\begingroup$
$\endgroup$
2
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:
- Is there a fast product operation for PackedArrays? (Stack Overflow)
answered Aug 11, 2017 at 2:30
-
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 likesumprob2[{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$ Aug 11, 2017 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$ Aug 11, 2017 at 16:38
Total[Times @@@ Tuples[lst, {size}]]? $\endgroup$