home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / symbolic / 2980 < prev    next >
Encoding:
Internet Message Format  |  1992-11-16  |  3.1 KB
  1. Path: sparky!uunet!ogicse!uwm.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!mm-mac22.mse.uiuc.edu!gaylord
  2. From: gaylord@ux1.cso.uiuc.edu (Richard J. Gaylord)
  3. Newsgroups: sci.math.symbolic
  4. Subject: Rootterdam Competition in Mathematica Journal
  5. Message-ID: <BxtJGM.472@news.cso.uiuc.edu>
  6. Date: 16 Nov 92 17:05:08 GMT
  7. Article-I.D.: news.BxtJGM.472
  8. Sender: usenet@news.cso.uiuc.edu (Net Noise owner)
  9. Organization: University of Illinois
  10. Lines: 86
  11. X-Xxdate: Mon, 16 Nov 92 11:06:44 GMT
  12. X-Useragent: Nuntius v1.1.1d12
  13. X-Xxmessage-Id: <A72D314486049B16@mm-mac22.mse.uiuc.edu>
  14.  
  15. in the latest issue of the Mathematica Journal, the results of the
  16. programming competition at the Boston and the Rotterdam Mathematica
  17. meetings were reported.
  18.  
  19. I've already expressed in this group my (self) righteous indignation over
  20. the  choice  for most elegant program in Boston of a  pattern-matched
  21. function over the clearly aesthetically superior as well as faster
  22. functional program so i'll only discuss  the 'split' function program
  23. from Rotterdam. split takes two lists, the first of which is an arbitrary
  24. list and the second of which is a list of non-negative integers whose sum
  25. is the length of the first list.
  26.  
  27. The function works like this:
  28.  
  29. split[{a,b,c,d,e,f,g},{2,0,3,1,1}]
  30. {{a,b},{},{c,d,e},{f},{g}}
  31.  
  32. clearly, the second list tells you how to 'split up' the first list.
  33.  
  34. the winner of the contest for elegance was:
  35.  
  36. splitElegant[lis_,parts_] :=
  37.     Take[lis,#]& /@
  38.        Rest[FoldList[#[[2]]+{1,#2}&,{0,0},parts]]
  39.  
  40. the winner of the contest for efficiency was:
  41.  
  42. splitFast[list_,parts_] := 
  43.      Block[{accumulation = FoldList[Plus,0,parts]},
  44.        Inner[Take[list,{#1,#2}]&,
  45.            Drop[accumulation,-1]+1,
  46.            Rest[accumulation],
  47.            List]]     
  48.  
  49. It was reported in the article that splitFast is 50% faster than
  50. splitElegant. I tested this:
  51.  
  52. parts = Table[Random[Integer,{0,5}],{500}]; 
  53.  
  54. parts/.List->Plus
  55. 1255
  56.  
  57. lis = Table[Random[Integer,{1,10}], {parts/.List->Plus}];
  58.  
  59. Length[lis]
  60. 1255
  61.  
  62. Timing[splitElegant[lis,parts];]
  63. {2.05 Second, Null}
  64.  
  65. Timing[splitFast[lis,parts];]
  66. {1.35 Second, Null}
  67.  
  68. ================
  69.  
  70. the first point i want to raise is that splitElegant is really not that 
  71. elegant if elegant also means it should be readable. 
  72. [ how long it took you to figure out what the anonymous function #[[2]]
  73. +{1,#2}& does?]
  74.  
  75. i have come up with an alternative program which slightly faster than 
  76. splitFast and is  more elegant than splitElegant {my dog darwin concurs
  77. with this judgement and he's incredibly picky about his code} :
  78.  
  79.  
  80. split[lis_, parts_] := 
  81.  Map[Take[lis, #]&, 
  82.   Drop[Thread[List[# + 1, RotateLeft[#]]]& [FoldList[Plus,0,parts]], -1] ]
  83.  
  84. Timing[split[lis,parts];]
  85. {1.28333 Second, Null}
  86.  
  87.  
  88. the nice thing about the split function given here is that it follows a
  89. prime directive of functional programming:
  90.  
  91. "never disassemble a list and then reassemble the list". 
  92.  
  93.  
  94. as an aside: in order to increase speed i used Thread[List[a,b]] rather
  95. than the somewhat slower Transpose[{a,b}] .  mathematically oriented
  96. people may find that using Transpose  increases the elegance of the
  97. program further. 
  98.  
  99. i don't suppose they're accepting any late entrie to theRotterdam
  100. Confereence contest?
  101.