Re: Threading objects of unequal length
- To: mathgroup at smc.vnet.net
- Subject: [mg8362] Re: [mg8112] Threading objects of unequal length
- From: Olivier Gerard <jacquesg at pratique.fr>
- Date: Tue, 26 Aug 1997 02:22:59 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Hello Carl, hello group,
thanks for your synthesis of our various solutions.
It is quite helpful.
Commenting on the timing performances (which stands
at the middle of the sample) of my solution,
I think it has clearly two bottlenecks.
-> One is the use of Select which is much
slower than Cases or DeleteCases as shows this version:
Clear[NotAnElt];
f4bis[ hd_Symbol[jk__List] ]:=
With[{mlotl=Max[Map[Length,List[jk]]]},
Map[ hd@@DeleteCases[#1,NotAnElt,1]&,
Transpose[Map[Join[#1,Array[NotAnElt&,mlotl-Length[#1]]]&,List[jk]]] ]]
which
is approximately 10% faster for the first test and
2 times faster for the second test. One of the evident
reason of this speedup is the reduction of function calls
in favor of pattern matching;
-> and also the systematic build of the complement array
at each step, a bottleneck that f1 and f5 address in
the same and efficient manner together with the
important cost of accessing the length of each element.
However, for that kind of function, the nature and form
of the sample is highly relevant.
For instance f5 has a supplementary speedup by doing before
Mathematica itself the removing of the dummy element. But
this only efficient with large samples. For smaller ones
the final evaluation procedure of the result by the Kernel
has a fixed cost which explains why f1 is faster than f5 on this,
I think.
An important aspect of a list primitive such as the one
we have tried to provide is memory management. In this
respect, mine is not a very good challenger either.
I feel that this (message) thread is good example of
the way can mutually learn from each other by subscribing to
this list.
I look forward for further comments, and maybe further improvments.
Best regards,
Olivier Gerard
> Hi group,
>
> I received several suggestions on how to come up with a function which
> threads objects of unequal length. In case anyone is interested here are
> those functions along with my attempt, and a speed comparision. Note: f1
> is my solution, f2 is Christophe Armand's solution, f3 is Wouter
> Meeussen's solution, f4 is Olivier Gerard's solution, and f5 is Allan
> Hayes' solution. Some of the solutions have been tweaked to get them to
> accept the same kind of input. My solution and Allan Hayes' solutions were
> essentially the same, Christophe Armand's and Wouter Meeussen's solutions
> were similar. For small expressions, Armand's solution seems to be the
> fastest, although timings were all very close. For large expressions, my
> solution and Allan Hayes' solutions were definitely the best. The
> following is the Mma notebook I used to compare solutions.
>
> Adding uneven lists
> In[1]:=
> f1[b:hd_[__List]]:=Module[{mx=Max@@Length/@b,m,dummy,dummylist},
> dummylist=Table[dummy,{mx}];
> m=Take[Join[#,dummylist],mx]&/@b;
> m=Thread[m];
> dummy=Sequence[];
> m
> ]
> In[2]:=
> f2[hd_[a__List]]:=
> Apply[hd,Table[#[[i]]&/@Select[{a},Length[#]>=i&],{i,Max@@Length/@{a}}],1]
> In[3]:=
> f3[hd_[a__List]]:=
> Table[hd@@Part[{a},Flatten[Position[Length/@{a},b_/;b>=i]],i],{i,
> Max@@Length/@{a}}]
> In[4]:=
> Clear[NotAnElt];
> TestEltQ[NotAnElt]=False;
> TestEltQ[__]=True;
>
> f4[ hd_Symbol[jk__List] ]:=
> Module[{mlotl=Max[Map[Length,List[jk]]]},
> Map[ hd@@Select[#1,TestEltQ]&,
> Transpose[Map[Join[#1,Array[NotAnElt&,
> mlotl-Length[#1]]]&,List[jk]]] ]]
> In[5]:=
> f5[b:hd_[a__List]]:=Module[{x,ml,pd,tb,mth},
> ml=Max@@Length/@b;
> pd=Table[x,{ml}];
> tb=Take[Join[#,pd],ml]&/@{a};
> mth=MapThread[hd,tb];
> DeleteCases[mth,x,{2}]
> ]
> In[6]:=
> Do[t1=f1[h[{1,2,3},{4},{5,6}]],{100}]//Timing
> Do[t2=f2[h[{1,2,3},{4},{5,6}]],{100}]//Timing
> Do[t3=f3[h[{1,2,3},{4},{5,6}]],{100}]//Timing
> Do[t4=f4[h[{1,2,3},{4},{5,6}]],{100}]//Timing
> Do[t5=f5[h[{1,2,3},{4},{5,6}]],{100}]//Timing
> t1===t2===t3===t4===t5
> Out[6]=
> {0.53 Second,Null}
> Out[7]=
> {0.48 Second,Null}
> Out[8]=
> {0.9 Second,Null}
> Out[9]=
> {0.65 Second,Null}
> Out[10]=
> {0.61 Second,Null}
> Out[11]=
> True
> In[12]:=
> test=h@@Table[Table[Random[],{20+Random[Integer,30]}],{1000}];
> padtest=h@@Table[Table[Random[],{50}],{1000}];
> In[13]:=
> t1=f1[test];//Timing
> t2=f2[test];//Timing
> t3=f3[test];//Timing
> t4=f4[test];//Timing
> t5=f5[test];//Timing
> t1===t2===t3===t4===t5
> Thread[padtest];//Timing
> Out[13]=
> {0.66 Second,Null}
> Out[14]=
> {10.08 Second,Null}
> Out[15]=
> {11.39 Second,Null}
> Out[16]=
> {5.94 Second,Null}
> Out[17]=
> {0.82 Second,Null}
> Out[18]=
> True
> Out[19]=
> {0.12 Second,Null}