Re: Challenge! , mg[915],mg[917]
- To: mathgroup at christensen.cybernetics.net
- Subject: [mg986] Re: [mg889] Challenge! , mg[915],mg[917]
- From: hay at haystack.demon.co.uk
- Date: Thu, 4 May 1995 07:44:43 -0400
Paul E Howland <PEHOWLAND at taz.dra.hmg.gb>[mg889] Challenge! wrote: > I have two lists of equal length M. > I wish to generate a third list also of length M, where the i th > element of this list is either the i th element of the first list, > or the i th element of the second list. > It should be equally probable that the new element be chosen from > the first or second list. He then gave a solution and asked for improvements. David Wagner mg[915] and Lou Dandria mg[917] supplied essentially the same improvement and generalized to any number of lists (their code is give as interleave below (Dave's name)) Here are two faster codes: the techniques used are generally applicable. interleave2 is a simple modification of interleave interleave3 is a different code that is faster than interleave2;it is an example of building up a preliminary structure and then modifying it. In[1]:= interleave[s__List] := With[{len = Length[{s}]}, #[[Random[Integer, {1,len}]]]& /@ Transpose[{s}] ] With takes time: it turns out not to be worth it. Admittedly Length is only calculated once instead of as many times as the length of the lists in s___List; but Length is extremely quickly found. Changing With to Block has very nearly the same effect as removing With. Remove With. In[2]:= interleave2[s__List] := #[[Random[Integer, {1,Length[{s}]}]]]& /@ Transpose[{s}]; Timings: Make sum test data In[3]:= test1 = Array[#,{30}]&/@(Range[10]); In[4]:= Do[interleave@@test1,{30}]//Timing//First Do[interleave2@@test1,{30}]//Timing//First Out[4]= 1.08333 Second Out[5]= 0.8 Second The advantage is more marked with larger lists. In[6]:= test2 =Array[#,{300}]&/@(Range[100]); In[7]:= interleave@@test2//Timing//First interleave2@@test2//Timing//First Out[7]= 2.28333 Second Out[8]= 0.916667 Second (*Code for Interleave3*) In[9]:= interleave3[L:{s_,___}] := Transpose[ L[[Random[Integer,{1,Length[L]}]&/@s ]], {1,1} ]; (*Transpose[m,{1,1}] gives the diagonal of matrix m*) Check correctness In[10]:= test0 = Array[#,{8}]&/@Range[3] Out[10]= {{1[1], 1[2], 1[3], 1[4], 1[5], 1[6], 1[7], 1[8]}, {[1], 2[2], 2[3], 2[4], 2[5], 2[6], 2[7], 2[8]}, {3[1], 3[2], 3[3], 3[4], 3[5], 3[6], 3[7], 3[8]}} In[11]:= interleave3[test0] Out[11]= {1[1], 1[2], 3[3], 2[4], 2[5], 2[6], 3[7], 2[8]} Timings (first for interleave2 second for interleave3) In[12]:= Do[interleave2@@test1,{30}]//Timing//First Do[interleave3[test1],{30}]//Timing//First Out[12]= 0.816667 Second Out[13]= 0.483333 Second The advantage with interleave3 is more marked with larger lists. In[14]:= interleave2@@test2//Timing//First interleave3[test2]//Timing//First Out[14]= 0.9 Second Out[15]= 0.133333 Second Interleave3 works as follows In[16]:= (L = {s,r,t}= test0)//TableForm Out[16]//TableForm= 1[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8] 2[1] 2[2] 2[3] 2[4] 2[5] 2[6] 2[7] 2[8] 3[1] 3[2] 3[3] 3[4] 3[5] 3[6] 3[7] 3[8] In[17]:= choiceindices = Random[Integer,{1,Length[L]}]&/@s Out[17]= {2, 1, 3, 1, 1, 2, 1, 3} In[18]:= (choicelist = L[[choiceindices]])//TableForm Out[18]//TableForm= 2[1] 2[2] 2[3] 2[4] 2[5] 2[6] 2[7] 2[8] 1[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8] 3[1] 3[2] 3[3] 3[4] 3[5] 3[6] 3[7] 3[8] 1[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8] 1[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8] 2[1] 2[2] 2[3] 2[4] 2[5] 2[6] 2[7] 2[8] 1[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8] 3[1] 3[2] 3[3] 3[4] 3[5] 3[6] 3[7] 3[8] Take the diagonal of this matrix. In[19]:= Transpose[ choicelist,{1,1}] Out[19]= {2[1], 1[2], 3[3], 1[4], 1[5], 2[6], 1[7], 3[8]} The next code uses Thread. Block prevents the attempted evaluation of Part before threading. In speed it is between interleave2 and interleave3. In[20]:= Clear[interleave4]; interleave4[L:{s_,___}] := Block[{Part}, Thread[ Part[ L,Random[Integer,{1,Length[L]}]&/@s, Range[Length[s]] ], List, -2 (*thread over any Lists amongst last 2 entries*) ] ] Allan Hayes hay at haystack.demon.co.uk