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"