MathGroup Archive 1992

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

Search the Archive

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

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:



to clarify what's going on here:

{2, 5, 6, 7}

we can look at the actual selection process using NestList

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

{{0.866667 Second, Null}, {1.01667 Second, Null}, {5.25 Second, Null}}

$RecursionLimit = 1000;

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

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

  • 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