MathGroup Archive 1997

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

Search the Archive

Re: Threading objects of unequal length

  • To: mathgroup at
  • Subject: [mg8362] Re: [mg8112] Threading objects of unequal length
  • From: Olivier Gerard <jacquesg at>
  • Date: Tue, 26 Aug 1997 02:22:59 -0400
  • Sender: owner-wri-mathgroup at

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:

f4bis[ hd_Symbol[jk__List] ]:=
		Map[ hd@@DeleteCases[#1,NotAnElt,1]&,

	Transpose[Map[Join[#1,Array[NotAnElt&,mlotl-Length[#1]]]&,List[jk]]] ]]

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}

  • Prev by Date: Re: Lists without outer braces
  • Next by Date: Re: Scoping (was Procedure to Function)
  • Previous by thread: Re: Re: Threading objects of unequal length
  • Next by thread: Re: Threading objects of unequal length