MathGroup Archive 1995

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

Search the Archive

Re: CHALLENGE (still more)

  • To: mathgroup at
  • Subject: [mg1138] Re: CHALLENGE (still more)
  • From: colinr at (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:

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

swap6[list1_, list2_] :=
        #[[Random[Integer,{1,2}]]]& /@ Transpose[{list1,list2}]
swap6[l1, l2]
Timing[Do[swap6[l1, l2], {1000}]]

{A, b, c, d, E, F, G, H, i, j}
{16.7667 Second, Null}

COLIN ROSE        colinr at

swap8[list1_, list2_] :=
   MapThread[If[Random[Integer] == 0, #1, #2]&, {list1, list2}]
swap8[l1, l2]
Timing[Do[swap8[l1, l2], {1000}]]

{a, b, C, D, e, f, G, H, I, J}
{12.2333 Second, Null}

VILLEGAS3      villegas at
swap9[list1_List, list2_List] := Thread @
    Unevaluated[If[Random[Integer] == 0, #1, #2]& [list1, list2]]
swap9[l1, l2]
Timing[Do[swap9[l1, l2], {1000}]]

{A, B, c, D, e, F, g, H, I, j}
{10.7 Second, Null}

VIRTAMO    villegas3 modified by jorma.virtamo at

swap10[list1_List, list2_List] := Thread @
       Unevaluated[If[Random[Integer] == 0, list1, list2]]
swap10[l1, l2]
Timing[Do[swap10[l1, l2],{1000}]]

{a, B, C, d, e, F, G, h, I, J}
{7.25 Second, Null}

ARND ROTH #2     roth at

SetAttributes[Thread, HoldFirst]

swap11[list1_List, list2_List] :=
      Thread[If[EvenQ[Random[Integer]], list1, list2]]
swap11[l1, l2]
Timing[Do[swap11[l1, l2],{1000}]]

{A, B, c, d, e, F, G, h, I, j}
{6.98333 Second, Null}


SetAttributes[Thread, HoldFirst]

swap[list1_List, list2_List] :=
     Thread[If[Random[Integer] != 0, list1, list2]]
swap[l1, l2]
Timing[Do[swap[l1, l2], {1000}]]

{A, b, c, d, E, F, g, h, i, J}
{6.78 Second, Null}

The speed seems to be converging.
It will be interesting to see if this can be further improved upon.



Colin Rose
tr(I) - Theoretical Research Institute
colinr at

  • Prev by Date: DSolveConstants problem
  • Next by Date: MathLink and CodeWarrior
  • Previous by thread: DSolveConstants problem
  • Next by thread: MathLink and CodeWarrior