Re: Re: Can I do this faster?
- To: mathgroup at smc.vnet.net
- Subject: [mg103032] Re: [mg102998] Re: Can I do this faster?
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Fri, 4 Sep 2009 03:17:22 -0400 (EDT)
- References: <h7o2cd$jtk$1@smc.vnet.net> <200909032354.TAA16768@smc.vnet.net>
- Reply-to: drmajorbob at yahoo.com
Sorry... I meant your Outer (not Inner) is Dot with a Transpose.
Bobby
On Thu, 03 Sep 2009 20:32:08 -0500, DrMajorBob <btreat1 at 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@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 at 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@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 at yahoo.com
- References:
- Re: Can I do this faster?
- From: Szabolcs Horvát <szhorvat@gmail.com>
- Re: Can I do this faster?