Re:Challenge! ....RESULTS...,

*To*: mathgroup at christensen.cybernetics.net*Subject*: [mg1059] Re:[mg950] Challenge! ....RESULTS..., [mg986]*From*: Allan Hayes <hay%haystack at christensen.cybernetics.net>*Date*: Fri, 12 May 1995 15:10:48 -0400

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 [1] 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 [2] 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. [1] 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 interleave3A maintains its advantage over interleave3. test =Array[#,{300}]&/@(Range[100]); Do[interleave3[test2],{30}]//Timing//First 4.58333 Second Do[interleave3Replace[test2],{30}]//Timing//First 3.6 Second [2] Is the compications 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} ] ]; Module[{len = Length[L]}, Transpose[ L[[Random[Integer,{1,len}]&/@s ]], {1,1} ] ]; 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[test2],{30}]//Timing//First 3.66667 Second Do[interleave3Block[test2],{30}]//Timing//First 4.28333 Second Do[interleave3Module[test2],{30}]//Timing//First 48.9667 Second (*!*) Do[interleave3With[test2],{30}]//Timing//First 48.5333 Second (*!*) Allan Hayes hay at haystack.demon.co.uk