       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  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  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.



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}]][]

7.33333 Second

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

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}]][]

6.28333 Second

For bigger data interleave3A maintains its advantage over interleave3.

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

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

4.58333 Second

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

3.6 Second



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}]][]
5.7 Second

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

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

Timing[Do[interleave3With[{list1,list2}],{1000}]][]
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

```

• Prev by Date: The Case of the Mystery Option
• Next by Date: Optica?
• Previous by thread: Re: The Case of the Mystery Option