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

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"