Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Can I do this faster?

• To: mathgroup at smc.vnet.net
• Subject: [mg102998] Re: Can I do this faster?
• From: Szabolcs Horvát <szhorvat at gmail.com>
• Date: Thu, 3 Sep 2009 19:54:14 -0400 (EDT)
• References: <h7o2cd$jtk$1@smc.vnet.net>

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

• Follow-Ups:
  • Re: Re: Can I do this faster?
    • From: DrMajorBob <btreat1@austin.rr.com>
  • Re: Re: Can I do this faster?
    • From: DrMajorBob <btreat1@austin.rr.com>