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"