Re: Can I do this faster?
- To: mathgroup at smc.vnet.net
- Subject: [mg103019] Re: Can I do this faster?
- From: pfalloon <pfalloon at gmail.com>
- Date: Fri, 4 Sep 2009 03:14:58 -0400 (EDT)
- References: <h7o2cd$jtk$1@smc.vnet.net>
On Sep 3, 7:30 pm, Andreas <aa... at ix.netcom.com> wrote:
> I start with two 2 dimensional lists. The have equal depths, but may
> or may not have equal lengths. Possible data looks like this:
>
> list1 = RandomReal[{0, 1}, {1500, 3}];
> list2 = RandomReal[ExponentialDistribution[2], {1000, 3}];
>
> The following produces the results I need, but takes longer to run
> than I'd like:
>
> Rest[FoldList[Times, 1, Transpose[(t = #; 1 + Inner[Times, t, # - 1,
> Plus] & /@ list1) & /@
> list2]]]
>
> Any suggestions rewriting this so I can make it run faster?
>
> Thanks.
I think the main reason for the slowness is that the Inner function is
much less efficient for large numerical matrices than the standard Dot
function. When you re-express the function using Dot, it is much
faster:
(* original definition *)
f1[list1_,list2_] := Module[{t}, Rest[FoldList[Times, 1, Transpose[(t
= #; 1 + Inner[Times, t, # - 1, Plus] & /@ list1) & /@ list2]]]]
(* first attempt: incorporate the addition & subtraction into the
Inner function *)
f2[list1_,list2_] := Inner[Times[#1-1,#2] &, list1, Transpose@list2,
Plus[1, ##] &] // FoldList[Times, 1, #] & // Rest
(* best attempt: apply the addition & subtraction to the matrices as a
whole, so we can use the more-efficient Dot function *)
f3[list1_,list2_] := Rest@FoldList[Times, 1, 1+(list1-1).Transpose
[list2]]
Here is an example to show the speed-up:
In[62]:= (* sample matricies *)
list1 = RandomReal[{0, 1}, {1000, 3}];
list2 = RandomReal[ExponentialDistribution[2], {1500, 3}];
In[64]:= (* timings *)
res1=f1[list1, list2]; // AbsoluteTiming
res2=f2[list1, list2]; // AbsoluteTiming
res3=f3[list1, list2]; // AbsoluteTiming
Out[64]= {14.0311602,Null}
Out[65]= {9.7811874,Null}
Out[66]= {1.7187390,Null}
However, in testing this I noticed that the function appears to be
highly unstable numerically -- so you may want to investigate that
further:
(* test correctness of results: appears to be numerically unstable! *)
Max /@ Abs[res1 - res2]
Max /@ Abs[res1 - res3]
Hope this helps!
Cheers,
Peter.