MathGroup Archive 1995

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

Search the Archive

Re:Challenge! ....RESULTS..., (Corrected)

  • To: mathgroup at christensen.cybernetics.net
  • Subject: [mg1069] Re:[mg950] Challenge! ....RESULTS..., [mg986] (Corrected)
  • From: Allan Hayes <hay at haystack.demon.co.uk>
  • Date: Fri, 12 May 1995 16:50:58 -0400

I have corrected some typing errors in my previous posting. The  
corrected version ([2]CORRECTED COPY) follows the first section.
I have also, got closer to seeing why codes involving Module and  
With can be inefficient. I suggest some ways of using them more  
efficiently. Since this is of more general consequence I will  
explain it at once.


[1] USING MODULE AND WITH

*************************
(*6*)	
	Module[{a=A},B] and With[{a=A},B]
	can be slow when A or B are big.

Some Suggestions:
	
	Name A, preferaby inside Block,: eg
	Block[{a = A}, With[{a=a},B]];
			
	Minimize B by placing Module and With as deep inside the 		
	expression as possible; consistent with its working as 	
	required. Try naming all or parts of B (eg.
	Block[{b = B}, With[{a=A},b]]) but don't remove symbols
	that you wish With to replace.

	
In the test below it turns out that we need to deal with both A and  
B to get a significant improvement.


***********************
Examples: For brevity I deal only with With.
Please note that thes are not realstic examples: they are chosen to  
investigate the behaviour of Module and With. The fastest form of  
he code is simply test[L_] :=  {5 len, L[[1,1]]}.

data =Array[#,{300}]&/@(Range[100]);

First the direct application of With
testWith[L_] :=  						 	 
						
  		With[ {len = Length[L]}, {5 len, L[[1,1]]}  ]
testWith[data]//Timing
	{1.48333 Second, {500, 1[1]}}


Now to try the suggestions individually and together

testWith2[L_] :=  						
	Block[{len = Length[L]}, 	   (*name A *)
  		With[ {len = len}, {5 len, L[[1,1]]}  ]
 	];
testWith2[data]//Timing
	{1.46667 Second, {500, 1[1]}}

testWith3[L_] :=							
   {With[{len = Length[L]},5 len],  L[[1,1]]};(*With inside*)
testWith3[data]//Timing
	{1.41667 Second, {500, 1[1]}}

testWith4[L_] :=					
   Block[{len = Length[L]},		      (*name A*)
     { With[ {len = len},5 len ],  L[[1,1]] } (*With inside*)
  ]
testWith4[data]//Timing
{0. Second, {500, 1[1]}}


testWith5[L_] :=  						
	Block[{len = Length[L], l = L},        (*name A and B*)
  		With[ {len = len}, {5 len, l[[1,1]]}  ]
 	];
testWith5[data]//Timing
	{0. Second, {500, 1[1]}}

Why do we need to deal with both A and B before any significant  
improvement is seen?


There is another way: use replacement directly like this

testReplace[L_] :=
	Block[{len},
  		{5 len, L[[1,1]]} /. len -> Length[L]
 	];
testReplace[data]//Timing
{0. Second, {500, 1[1]}}

For repeated use we have the following timings

Do[testWith4[data],{1000}]//Timing
Do[testReplace[data],{1000}]//Timing
{1.46667 Second, Null}
{1.61667 Second, Null}

So using With seems better. Unfortunately this speed up does not  
seem to carry through to the interleaving code.

(*previous code using replacement*)
interleave3Replace[L:{s_,___}] :=
Block[{len},
   Transpose[
	L[[(Random[Integer,{1,len}]&/.len-> Length[L])/@s ]], (*4*)
	{1,1}
   ]
];
Do[interleave3Replace[data],{30}]//Timing//First
3.55 Second

(*new code using With*)
interleave3With[L:{s_,___}] :=
Block[{len = Length[L]},
   Transpose[
	L[[With[{len=len},Random[Integer,{1,len}]&]/@s ]], (*4*)
	{1,1}
   ]
];
Do[interleave3With[data],{30}]//Timing//First
3.51667 Second


One final point: we can avoid the need to take With inside as follows

interleave3WithA[L_] :=
Block[{len = Length[L]L},
	With[{len=len},
   Transpose[
	L[[Random[Integer,{1,len}]&/@First[LL] ]],
	{1,1}
   ]
]];

Do[interleave3WithA[data],{30}]//Timing//First
Do[interleave3WithA[{list1,list2}],{1000}]//Timing//First
3.61667 Second
5.68333 Second


[2] CORRECTED COPY
    (I have change the numbering:[1] to [2a] and [2] to [2b])
*************************
Paul Howland <PEHOWLAND at taz.dra.hmg.gb> asked in [mg889] for the  
most efficient function for generating a new list by randomly  
interchanging the elements of two other lists.

I give in [2a] below a further speed up to my best code in my  
response [mg986] and find  another speed up rule:

(*4*) Simple replacements can be very fast

But first a correction: in [mg986] I let my keenness to try out  
larger tests take me away from the original challenge problem.The  
statement that interleave3 is faster than Dave Wagner's code swap is  
incorrect for the two lists in the original problem. However, the  
new code, is faster for these lists.

In [2b] I compare this new code interleave3Replace with the results  
of using straightforward Block, Module and With on interleave3.  
Module and With come out badly for large data sets.
Hence, the rule:

(*5*) Try Block for speed.

[2a]

My previous best

interleave3[L:{s_,___}] :=
Transpose[
	L[[Random[Integer,{1,Length[L]}]&/@s ]],
	{1,1}
];

The new code

interleave3Replace[L:{s_,___}] :=
Block[{len},
   Transpose[
	L[[(Random[Integer,{1,len}]&/.len-> Length[L])/@s ]], (*4*)
	{1,1}
   ]
];


TIMINGS

list1 = {a,b,c,d,e,f,g,h,i,j};
list2 = {A,B,C,D,E,F,G,H,I,J};

Timing[Do[interleave3[{list1,list2}],{1000}]][[1]]

7.33333 Second

Timing[Do[interleave3Replace[{list1,list2}],{1000}]][[1]]

5.6 Second

Dave Wagner's swap code is

swap[list1_List,list2_List] :=
	#[[Random[Integer,{1,2}]]]& /@ Transpose[{list1,list2}]
	
and gives the timing

Timing[Do[swap[list1,list2],{1000}]][[1]]

6.28333 Second


For bigger data interleave3Replace maintains its advantage over  
interleave3.

test =Array[#,{300}]&/@(Range[100]);

Do[interleave3[test],{30}]//Timing//First

4.58333 Second

Do[interleave3Replace[test],{30}]//Timing//First

3.6 Second


[2b]

Is the complication of interleave3Replace necessary? Let's try a  
straightforward use of Block, Module and With

interleave3Block[L:{s_,___}] :=
Block[{len = Length[L]},
   Transpose[
	L[[Random[Integer,{1,len}]&/@s ]],
	{1,1}
   ]
];

interleave3Module[L:{s_,___}] :=
Module[{len = Length[L]},
   Transpose[
	L[[Random[Integer,{1,len}]&/@s ]],
	{1,1}
   ]
];

interleave3With[L:{s_,___}] :=
With[{len = Length[L]},
   Transpose[
	L[[Random[Integer,{1,len}]&/@s ]],
	{1,1}
   ]
];

Timings:


Timing[Do[interleave3Replace[{list1,list2}],{1000}]][[1]]
5.7 Second

Timing[Do[interleave3Block[{list1,list2}],{1000}]][[1]]
5.93333 Second

Timing[Do[interleave3Module[{list1,list2}],{1000}]][[1]]
8.3 Second

Timing[Do[interleave3With[{list1,list2}],{1000}]][[1]]
6.08333 Second


But for bigger data interleave3Replace has more of an advantage  
over interleave3Block, but Module and With fall dramatically behind.
This may be due to their being scoping constructs. For example  
Module has to look up $ModuleNumber and if it is n it then replaces  
len with len$n and sets up the assignment

len$n = k  (* where k is the length of L*)

Block simply sets up the assignment

len = k.

But this seems quite inadequate to explain such large differneces.



Do[interleave3Replace[test],{30}]//Timing//First
3.66667 Second

Do[interleave3Block[test],{30}]//Timing//First
4.28333 Second

Do[interleave3Module[test],{30}]//Timing//First
48.9667 Second                                      (*!*)

Do[interleave3With[test],{30}]//Timing//First
48.5333 Second                                      (*!*)


Allan Hayes
hay at haystack.demon.co.uk




  • Prev by Date: Mma problem on PowerMac
  • Next by Date: Re: The Case of the Mystery Option
  • Previous by thread: Re: Mma problem on PowerMac
  • Next by thread: Package writing.