       Re: Challenge! , mg,mg

• To: mathgroup at christensen.cybernetics.net
• Subject: [mg986] Re: [mg889] Challenge! , mg,mg
• 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 and Lou Dandria mg 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:=
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:=
interleave2[s__List] :=
#[[Random[Integer, {1,Length[{s}]}]]]& /@ Transpose[{s}];

Timings:

Make sum test data
In:=
test1 = Array[#,{30}]&/@(Range);

In:=
Do[interleave@@test1,{30}]//Timing//First
Do[interleave2@@test1,{30}]//Timing//First

Out=
1.08333 Second
Out=
0.8 Second

The advantage  is more marked with larger lists.
In:=
test2 =Array[#,{300}]&/@(Range);

In:=
interleave@@test2//Timing//First
interleave2@@test2//Timing//First

Out=
2.28333 Second
Out=
0.916667 Second

(*Code for Interleave3*)
In:=
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:=
test0 = Array[#,{8}]&/@Range
Out=
{{1, 1, 1, 1, 1, 1, 1, 1},

{, 2, 2, 2, 2, 2, 2, 2},

{3, 3, 3, 3, 3, 3, 3, 3}}

In:=
interleave3[test0]
Out=
{1, 1, 3, 2, 2, 2, 3, 2}

Timings (first for interleave2 second for interleave3)

In:=
Do[interleave2@@test1,{30}]//Timing//First
Do[interleave3[test1],{30}]//Timing//First

Out=
0.816667 Second
Out=
0.483333 Second

The advantage with interleave3 is more marked with larger lists.

In:=
interleave2@@test2//Timing//First
interleave3[test2]//Timing//First
Out=
0.9 Second
Out=
0.133333 Second

Interleave3 works as follows
In:=
(L = {s,r,t}= test0)//TableForm
Out//TableForm=
1   1   1   1   1   1   1   1

2   2   2   2   2   2   2   2

3   3   3   3   3   3   3   3

In:=
choiceindices = Random[Integer,{1,Length[L]}]&/@s
Out=
{2, 1, 3, 1, 1, 2, 1, 3}
In:=
(choicelist = L[[choiceindices]])//TableForm
Out//TableForm=
2   2   2   2   2   2   2   2

1   1   1   1   1   1   1   1

3   3   3   3   3   3   3   3

1   1   1   1   1   1   1   1

1   1   1   1   1   1   1   1

2   2   2   2   2   2   2   2

1   1   1   1   1   1   1   1

3   3   3   3   3   3   3   3

Take the diagonal of this matrix.

In:=
Transpose[ choicelist,{1,1}]
Out=
{2, 1, 3, 1, 1, 2, 1, 3}

Block prevents the attempted evaluation of Part before threading.
In speed it is between interleave2 and interleave3.

In:=
Clear[interleave4];
interleave4[L:{s_,___}] :=
Block[{Part},
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

```

• Prev by Date: Re: MMA to BTM & Vice-Versa
• Next by Date: Mathematica Programming Reference Recommendation
• Previous by thread: Re: MMA to BTM & Vice-Versa
• Next by thread: Mathematica Programming Reference Recommendation