MathGroup Archive 1992

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

Search the Archive

the rotterdam programming competition

  • To: mathgroup at yoda.physics.unc.edu
  • Subject: the rotterdam programming competition
  • From: gaylord at ux1.cso.uiuc.edu
  • Date: Mon, 16 Nov 1992 11:11:37 -0600

in the latest issue of the Mathematica Journal, the results of the
programming competition at the Boston and the Rotterdam Mathematica
meetings were reported.

I've already expressed in this group my (self) righteous indignation over
the  choice  for most elegant program in Boston of a  pattern-matched
function over the clearly aesthetically superior as well as faster
functional program  so i'll only discuss  the 'split' function program from
Rotterdam. split takes two lists, the first of which is an arbitrary list
and the second of which is a list of non-negative integers whose sum is the
length of the first list.

The function works like this:

split[{a,b,c,d,e,f,g},{2,0,3,1,1}]
{{a,b},{},{c,d,e},{f},{g}}

clearly, the second list tells you how to 'split up' the first list.

the winner of the contest for elegance was:

splitElegant[lis_,parts_] :=
    Take[lis,#]& /@
       Rest[FoldList[#[[2]]+{1,#2}&,{0,0},parts]]

the winner of the contest for efficiency was:

splitFast[list_,parts_] := 
     Block[{accumulation = FoldList[Plus,0,parts]},
       Inner[Take[list,{#1,#2}]&,
           Drop[accumulation,-1]+1,
           Rest[accumulation],
           List]]     

It was reported in the article that splitFast is 50% faster than
splitElegant. I tested this:

parts = Table[Random[Integer,{0,5}],{500}]; 

parts/.List->Plus
1255

lis = Table[Random[Integer,{1,10}], {parts/.List->Plus}];

Length[lis]
1255

Timing[splitElegant[lis,parts];]
{2.05 Second, Null}

Timing[splitFast[lis,parts];]
{1.35 Second, Null}

================

the first point i want to raise is that splitElegant is really not that 
elegant if elegant also means it should be readable. 
[ how long it took you to figure out what the anonymous function #[[2]]
+{1,#2}& does?]

i have come up with an alternative program which slightly faster than 
splitFast and is  more elegant than splitElegant {my dog darwin concurs
with this judgement and he's incredibly picky about his code} :


split[lis_, parts_] := 
 Map[Take[lis, #]&, 
  Drop[Thread[List[# + 1, RotateLeft[#]]]& [FoldList[Plus,0,parts]], -1] ]

Timing[split[lis,parts];]
{1.28333 Second, Null}


the nice thing about the split function given here is that it follows a
prime directive of functional programming:

"never disassemble a list and then reassemble the list". 



as an aside: in order to increase speed i used Thread[List[a,b]] rather
than the somewhat slower Transpose[{a,b}] .  mathematically oriented people
may find that using Transpose  increases the elegance of the program
further. 

i don't suppose they're accepting any late entries to the Rotterdam
Confereence contest?



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: manipulating equations
  • Next by Date: [no subject]
  • Previous by thread: manipulating equations
  • Next by thread: Re: the rotterdam programming competition