Can I do this faster?
in [Mathematica]
|
Prev: plot question
Next: Faster alternative to AppendTo? --
From: Andreas on 4 Sep 2009 03:14 On Sep 3, 7:56 pm, Ray Koopman <koop...(a)sfu.ca> wrote: > Rest(a)FoldList[Times,1,1+(list1-1).Transpose(a)list2] Wow, on my machine the original code took 14.14 seconds to run, yours came in at 0.171! Thanks
From: DrMajorBob on 4 Sep 2009 03:15 We can still do a lot better, since your Inner is just Dot with a Transpose: list1 = RandomReal[{0, 1}, {1500, 3}]; list2 = RandomReal[ExponentialDistribution[2], {1000, 3}]; (* The OP's code: *) Timing[one = Transpose[(t = #; 1 + Inner[Times, t, # - 1, Plus] & /@ list1) & /@ list2];] {10.9069, Null} (* Szabolcs code: *) two = 1 + Outer[Dot, list1 - 1, list2, 1]; // Timing {0.520454, Null} one - two // Abs // Max 0. (* and mine: *) three = 1 + (list1 - 1).Transpose(a)list2; // Timing {0.058527, Null} two - three // Abs // Max 0. Like you, I see no way to improve FoldList... if it's actually needed. Bobby On Thu, 03 Sep 2009 18:54:14 -0500, Szabolcs Horv�t <szhorvat(a)gmail.com> wrote: > On 2009.09.03. 11:30, Andreas wrote: >> Rest[FoldList[Times, 1, Transpose[(t = #; 1 + Inner[Times, t, # - 1, >> Plus]& /@ list1)& /@ >> list2]]] > > > First I'd like to say that it's often much easier (at least for me!) to > come up with a solution if you explain what you want to do in plain > English instead of just providing a program to speed up. Now I have to > convert the program to a form that my brain can handle, then convert it > back to program code... Why not avoid the first step if possible? ;-) > > So, a few things we might notice about this implementation: > > 1. Inner is used with Times and Plus, so why not replace it with Dot? > 2. That nested function (with the assignment to the global t) looks > discomforting. I'm not sure how Mathematica's compiler can handle that > (Map auto-compiles the function when working on large lists). So let's > try to get rid of that also. > > These might not be the main reson for the slowdown. I am just > guessing---predicting Mathematica's performance can be difficult. > > So, rewrite the inner part of the program first. Instead of Inner we > can use Dot, instead of the nested function we can use Outer: > > list1 = RandomReal[{0, 1}, {1500, 3}]; > list2 = RandomReal[ExponentialDistribution[2], {1000, 3}]; > > In[3]:= Timing[ > x = Transpose[(t = #; > 1 + Inner[Times, t, # - 1, Plus] & /@ list1) & /@ list2];] > Out[3]= {21.656, Null} > > In[4]:= Timing[y = Outer[1 + #2.(#1 - 1) &, list1, list2, 1];] > Out[4]= {10.625, Null} > > That's a 2x speedup. > > Are the results equivalent? > > In[5]:= x == y > Out[5]= False > > We got False, but that's only because of numerical errors (the > operations are performed in a different order): > > In[6]:= Max(a)Abs[x - y] > Out[6]= 8.88178*10^-16 > > So the result is correct. > > What else can we do to speed things up? Notice that it is not necessary > to subtract/add 1 in the inner function 1 + #2.(#1 - 1) &. This can be > done on the input and output instead. So we can get rid of custom > functions and use the built-in Dot only: > > In[7]:= Timing[z = 1 + Outer[Dot, list1 - 1, list2, 1];] > Out[7]= {1.25, Null} > > In[8]:= y == z > Out[8]= True > > Now that's a 17x speedup compared to the implementation we started with. > Trying to simplify things will often pay off because it will be easier > to see how to rewrite the program to use built-in functions and packed > arrays as much as possible. It's also much easier to see what the > program does. > > The FoldList part takes an additional 3 seconds on my machine. I can't > help with speeding that up unfortunately. > > I hope this helps, > Szabolcs > -- DrMajorBob(a)yahoo.com
From: DrMajorBob on 4 Sep 2009 03:15
Sorry... I meant your Outer (not Inner) is Dot with a Transpose. Bobby On Thu, 03 Sep 2009 20:32:08 -0500, DrMajorBob <btreat1(a)austin.rr.com> wrote: > We can still do a lot better, since your Inner is just Dot with a > Transpose: > > list1 = RandomReal[{0, 1}, {1500, 3}]; > list2 = RandomReal[ExponentialDistribution[2], {1000, 3}]; > > (* The OP's code: *) > > Timing[one = Transpose[(t = #; > 1 + Inner[Times, t, # - 1, Plus] & /@ list1) & /@ list2];] > > {10.9069, Null} > > (* Szabolcs code: *) > > two = 1 + Outer[Dot, list1 - 1, list2, 1]; // Timing > > {0.520454, Null} > > one - two // Abs // Max > > 0. > > (* and mine: *) > > three = 1 + (list1 - 1).Transpose(a)list2; // Timing > > {0.058527, Null} > > two - three // Abs // Max > > 0. > > Like you, I see no way to improve FoldList... if it's actually needed. > > Bobby > > On Thu, 03 Sep 2009 18:54:14 -0500, Szabolcs Horv�t <szhorvat(a)gmail.com> > wrote: > >> On 2009.09.03. 11:30, Andreas wrote: >>> Rest[FoldList[Times, 1, Transpose[(t = #; 1 + Inner[Times, t, # - 1, >>> Plus]& /@ list1)& /@ >>> list2]]] >> >> >> First I'd like to say that it's often much easier (at least for me!) to >> come up with a solution if you explain what you want to do in plain >> English instead of just providing a program to speed up. Now I have to >> convert the program to a form that my brain can handle, then convert it >> back to program code... Why not avoid the first step if possible? ;-) >> >> So, a few things we might notice about this implementation: >> >> 1. Inner is used with Times and Plus, so why not replace it with Dot? >> 2. That nested function (with the assignment to the global t) looks >> discomforting. I'm not sure how Mathematica's compiler can handle that >> (Map auto-compiles the function when working on large lists). So let's >> try to get rid of that also. >> >> These might not be the main reson for the slowdown. I am just >> guessing---predicting Mathematica's performance can be difficult. >> >> So, rewrite the inner part of the program first. Instead of Inner we >> can use Dot, instead of the nested function we can use Outer: >> >> list1 = RandomReal[{0, 1}, {1500, 3}]; >> list2 = RandomReal[ExponentialDistribution[2], {1000, 3}]; >> >> In[3]:= Timing[ >> x = Transpose[(t = #; >> 1 + Inner[Times, t, # - 1, Plus] & /@ list1) & /@ list2];] >> Out[3]= {21.656, Null} >> >> In[4]:= Timing[y = Outer[1 + #2.(#1 - 1) &, list1, list2, 1];] >> Out[4]= {10.625, Null} >> >> That's a 2x speedup. >> >> Are the results equivalent? >> >> In[5]:= x == y >> Out[5]= False >> >> We got False, but that's only because of numerical errors (the >> operations are performed in a different order): >> >> In[6]:= Max(a)Abs[x - y] >> Out[6]= 8.88178*10^-16 >> >> So the result is correct. >> >> What else can we do to speed things up? Notice that it is not necessary >> to subtract/add 1 in the inner function 1 + #2.(#1 - 1) &. This can be >> done on the input and output instead. So we can get rid of custom >> functions and use the built-in Dot only: >> >> In[7]:= Timing[z = 1 + Outer[Dot, list1 - 1, list2, 1];] >> Out[7]= {1.25, Null} >> >> In[8]:= y == z >> Out[8]= True >> >> Now that's a 17x speedup compared to the implementation we started with. >> Trying to simplify things will often pay off because it will be easier >> to see how to rewrite the program to use built-in functions and packed >> arrays as much as possible. It's also much easier to see what the >> program does. >> >> The FoldList part takes an additional 3 seconds on my machine. I can't >> help with speeding that up unfortunately. >> >> I hope this helps, >> Szabolcs >> > > > -- DrMajorBob(a)yahoo.com |