Re: Re: Can I do this faster?
- To: mathgroup at smc.vnet.net
- Subject: [mg103031] Re: [mg102998] Re: Can I do this faster?
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Fri, 4 Sep 2009 03:17:11 -0400 (EDT)
- References: <h7o2cd$jtk$1@smc.vnet.net> <200909032354.TAA16768@smc.vnet.net>
- Reply-to: drmajorbob at yahoo.com
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?