Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1995
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1995

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

Search the Archive

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
	


  • 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