MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: how to solve the integer equation Abs[3^x-2^y]=1
  • Next by Date: Re: Re: Can I do this faster?
  • Previous by thread: Re: Can I do this faster?
  • Next by thread: Re: Re: Can I do this faster?