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