Re: CHALLENGE (still more)
- To: mathgroup at christensen.cybernetics.net
- Subject: [mg1138] Re: CHALLENGE (still more)
- From: colinr at extro.ucc.su.OZ.AU (Colin Rose)
- Date: Wed, 17 May 1995 03:49:20 -0400
The so-called "Challenge" continues to inspire interest - this probably has more to do with marketing (everyone likes a 'Challenge'), than with the inherent question itself. Some time ago, Paul Howland provided a 'summary' result list, which found Dave Wagner's soln to be the fastest. This list was clearly not the summary list it purported to be: several people had already posted faster solutions. More generally, since Wagner's solution used Transpose[], it was difficult to believe that it really was the fastest, since mma's functional list operators tend to be more efficient than the Transpose fn. Recent attempts can be split into two groups: * The transposers: Allan Hayes, Daniel Lichtblau, and Dave Wagner * The threaders: Colin Rose, Arnd Roth, Jorma Virtamo, and Rob Villegas I am pleased to announce that the threaders, in something of a team effort, have trounced the transposers. As far as I can tell, thread development seems to have followed the following time-path... Rose1 : MapThread [If[Random[Integer] == 0, #1, #2]&,{l1, l2}] Villegas3: Thread @Unevaluated [If[Random[Integer] == 0, #1, #2]& [l1, l2]] Virtamo : Thread @Unevaluated [If[Random[Integer] == 0, l1, l2]] Roth2 : Thread [If[EvenQ[Random[Integer]],l1, l2]] Rose2 : Thread [If[Random[Integer] != 0, l1, l2]] [ There also exists Villegas1 (also a MapThread soln) which was simultaneously independent with Rose1. ] All of these are faster than the fastest Transpose soln. Rose2 is almost twice as fast as Rose 1, though the credit here belongs almost entirely to Villegas, Virtamo and Roth. Villegas provided the most significant change from MapThread to Thread, Virtamo simplified the exposition (and thus provided the major speed increase!), Roth provided two neat ideas: 1) using SetAttributes[Thread, HoldFirst] to replace Unevaluated, and 2) improving the speed by replacing the == 0 test with EvenQ[]. Finally, Rose managed to get a teensy bit more speed by replacing EvenQ with != 0. Here are the full functions with timings on a Mac Quadra 700: In[1]:= l1 = {a,b,c,d,e,f,g,h,i,j}; l2 = {A,B,C,D,E,F,G,H,I,J}; WAGNER'S FUNCTION wagner at bullwinkle.cs.Colorado.EDU In[3]:= swap6[list1_, list2_] := #[[Random[Integer,{1,2}]]]& /@ Transpose[{list1,list2}] swap6[l1, l2] Timing[Do[swap6[l1, l2], {1000}]] Out[4]= {A, b, c, d, E, F, G, H, i, j} Out[5]= {16.7667 Second, Null} COLIN ROSE colinr at extro.ucc.su.oz.au In[6]:= swap8[list1_, list2_] := MapThread[If[Random[Integer] == 0, #1, #2]&, {list1, list2}] swap8[l1, l2] Timing[Do[swap8[l1, l2], {1000}]] Out[8]= {a, b, C, D, e, f, G, H, I, J} Out[9]= {12.2333 Second, Null} VILLEGAS3 villegas at wri.com In[10]:= swap9[list1_List, list2_List] := Thread @ Unevaluated[If[Random[Integer] == 0, #1, #2]& [list1, list2]] swap9[l1, l2] Timing[Do[swap9[l1, l2], {1000}]] Out[12]= {A, B, c, D, e, F, g, H, I, j} Out[13]= {10.7 Second, Null} VIRTAMO villegas3 modified by jorma.virtamo at vtt.fi In[14]:= swap10[list1_List, list2_List] := Thread @ Unevaluated[If[Random[Integer] == 0, list1, list2]] swap10[l1, l2] Timing[Do[swap10[l1, l2],{1000}]] Out[16]= {a, B, C, d, e, F, G, h, I, J} Out[17]= {7.25 Second, Null} ARND ROTH #2 roth at sunny.mpimf-heidelberg.mpg.de In[50]:= SetAttributes[Thread, HoldFirst] swap11[list1_List, list2_List] := Thread[If[EvenQ[Random[Integer]], list1, list2]] swap11[l1, l2] Timing[Do[swap11[l1, l2],{1000}]] Out[52]= {A, B, c, d, e, F, G, h, I, j} Out[53]= {6.98333 Second, Null} VILLEGAS-VIRTAMO-ROTH-ROSE In[54]:= SetAttributes[Thread, HoldFirst] swap[list1_List, list2_List] := Thread[If[Random[Integer] != 0, list1, list2]] swap[l1, l2] Timing[Do[swap[l1, l2], {1000}]] Out[56]= {A, b, c, d, E, F, g, h, i, J} Out[57]= {6.78 Second, Null} The speed seems to be converging. It will be interesting to see if this can be further improved upon. Cheerio Colin Colin Rose tr(I) - Theoretical Research Institute ______________________________________ colinr at extro.ucc.su.oz.au