translating the APL 'deal' function into M recursively, procedurally and functionally - one-liners are faster

• To: mathgroup at yoda.physics.unc.edu
• Subject: translating the APL 'deal' function into M recursively, procedurally and functionally - one-liners are faster
• From: gaylord at ux1.cso.uiuc.edu
• Date: Thu, 20 Aug 1992 05:30:31 -0500

```on p.200 in nancy blachman's book, an exercise (#11.4) is given to
translate the APL function 'deal' which randomly selects elements from a
list without replacement into M. it is recommended to do this recursively.

from the manuscript of a text, another person has written the deal function
in M both procedurally and as a recursive rewrite rule and found that the
procedural program runs 4 times faster than the recursive program:

it seems to me that the deal function is an obviously candidate for a
one-liner: here it is:

deal1[lis_List,n_Integer]
:=Complement[lis,Nest[Delete[#,Random[Integer,{1,Length[#]}]]&,lis,n]]

-----------------------------------------------

to clarify what's going on here:

SeedRandom[0]
deal1[Range[9],4]
{2, 5, 6, 7}

we can look at the actual selection process using NestList

SeedRandom[0]
NestList[Delete[#,Random[Integer,{1,Length[#]}]]&,Range[9],4]
{{1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 4, 5, 6, 8, 9},

{1, 2, 3, 4, 5, 8, 9}, {1, 2, 3, 4, 8, 9},

{1, 3, 4, 8, 9}}

---------------------------------------------

i ran timing test on the recursive program[deal3], the procedural
program[deal2] and the one-liner program[deal1] with the following results

{Timing[deal1[Range[200],60];],
Timing[deal2[Range[200],60];],
Timing[deal3[Range[200],60];]}
{{0.866667 Second, Null}, {1.01667 Second, Null}, {5.25 Second, Null}}

\$RecursionLimit = 1000;

{Timing[deal1[Range[200],200];],
Timing[deal2[Range[200],200];],
Timing[deal3[Range[200],200];]}
{{2.01667 Second, Null}, {2.78333 Second, Null}, {14.3667 Second, Null}}

i can't say that the recursive or the procedural programs (which i did not
write) are the best programs that can be written in those styles but i do
think that the speed of the one-liner confirms the general view that the
more compact the M program and and more built-in M functions that are used,
the faster the code will run.

richard j. gaylord, university of illinois, gaylord at ux1.cso.uiuc.edu

"if you're not programming functionally, then you must be programming
dysfunctionally"

```

• Prev by Date: Conflict between Mma and Compact Virtual
• Next by Date: Re: FontForm
• Previous by thread: Conflict between Mma and Compact Virtual
• Next by thread: RE>Conflict between Mma and