Challenge! ....RESULTS...
- To: mathgroup at christensen.cybernetics.net
- Subject: [mg950] Challenge! ....RESULTS...
- From: pehowland at taz.dra.hmg.gb (Paul E. Howland)
- Date: Thu, 4 May 1995 01:53:21 -0400
- Organization: Defence Research Agency
Mathgroup,
A few days ago I posted a question asking for the most efficient function
for generating a new list by randomly interchanging the elements of two other
lists (I was simulating the interchange of genes when breeding, for a genetic
minimisation algorithm, if you wonder why!). I've had several excellent
replies, all of which put my paltry efforts to shame.
I give below the different solutions, plus the results of timings to show the
fastest solution. I think they demonstrate the advantages of using
Mathematica's elegant programming language to the full, rather than writing
psuedo-Fortran in it, like my attempt!
Functions (in order of my receiving them...):
MY FUNCTION
swap[list1_List,list2_List] := Module[{newlist={},M,i}, M=Length[list1];
Do[AppendTo[newlist,If[Random[]>0.5,list1[[i]],list2[[i]]]],{i,M}];
newlist]
BUCHANAN'S FUNCTION buchanan at niehs.nih.gov
swap[list1_List,list2_List] := Module[{len,sel},len=Length[list1];
sel = Table[{Random[Integer, {1,2}], i}, {i, len}];
Map[{list1,list2}[[#[[1]],#[[2]]]]&, sel]]
LICHTBLAU'S FUNCTION danl at wri.com
swap[list1_List,list2_List] :=
Map[#[[Random[Integer]+1]]&,Transpose[{list1,list2}]]
VILLEGAS' FUNCTIONS villegas at wri.com
swap[list1_List,list2_List] :=
MapThread[Part[{#1,#2},1+Random[Integer]]&, {list1,list2}]
swap[list1_List,list2_List] := Module[{i,len}, len=Length[list];
Table[Part[{list1,list2},Random[Integer,{1,2}],i],{i,len}]]
WAGNER'S FUNCTION wagner at bullwinkle.cs.Colorado.EDU
swap[list1_List,list2_List] :=
#[[Random[Integer,{1,2}]]]& /@ Transpose[{list1,list2}]
T H E R E S U L T S
++++++++++++++++++++
Tested by using list1 = {a,b,c,d,e,f,g,h,i,j};
list2 = {A,B,C,D,E,F,G,H,I,J};
With
Timing[Do[swap[list1,list2],{1000}]]
on a DEC 3000/400 running Mathematica V2.2.4 for OSF/1.
My function 9.93333 seconds
Buchanan's function 9.56667 seconds
Lichtblau's function 4.06667 seconds
Villegas' function 1 3.9 seconds
Villegas' function 2 6.05 seconds
Wagner's function 3.66667 seconds
So David Wagner is the winner!
It's interesting that Wagner and Lichtblau have almost identical solutions, the
fundamental difference being that Wagner uses Random[Integer, {1,2}] whereas
Lichtblau uses Random[Integer]+1. The latter is obviously slower to compute.
Thanks for everyone's solutions. I'll get back to reading "Programming In
Mathematica" I think...
Paul E Howland
Long Range Ground Radar Systems Section tel. +44 (0)1684 895767
CSS2 Division, Room BY209 fax. +44 (0)1684 896315
Defence Research Agency email: PEHOWLAND at DRA.HMG.GB
Malvern, Worcs, WR14 3PS, UK.
-----------------------------------------------------------------------------