Re: functional code

*To*: mathgroup at smc.vnet.net*Subject*: [mg4840] Re: functional code*From*: Count Dracula <lk3a at watt.seas.virginia.edu>*Date*: Fri, 20 Sep 1996 01:12:52 -0400*Organization*: University of Virginia*Sender*: owner-wri-mathgroup at wolfram.com

In Message-ID: <51c52l$b2u at ralph.vnet.net> gaylord at ux1.cso.uiuc.edu (richard j. gaylord) writes: > Given a list of numbers row={18,19,1,11,25,12,22,14} > Select the numbers from the list by taking the largest number > from the ends of the list until the list is empty. Several solutions to this have appeared: p1 -- A variant of Gaylord's procedural solution p2 -- Essentially Gaylord's procedural solution p3 -- Gaylord's functional solution p4 -- Paul Abbott's rule-based solution 1 p5 -- Paul Abbott's rule-based solution 2 Here are the definitions, and a timing test program: p1[row_List] := Module[ {r = row, res = {}}, While[ Length[r] > 0, If[ First[r] >= Last[r], res = {res, First[r]}; r = Rest[r], res = {res, Last[r]}; r = Drop[r, -1] ]; ]; Flatten[res] ] p2[row_List] := Module[ {p = Length[row], result = {}, r = row}, Do[If[First[r]>=Last[r], AppendTo[result, First[r]];r=Rest[r], AppendTo[result,Last[r]];r=Drop[r,-1]], {p}]; result] p3[row_List] := Nest[ Function[y, ({Join[y[[1]],{#}] , DeleteCases[y[[2]], #]})&[Max[First[y[[2]]], Last[y[[2]]]]]], {{}, row}, Length[row]][[1]] p4[row_List] := {{},row}//.{{d___},{a_,b___,c_}}:> {{d,Max[a,c]},If[a<c,{a,b},{b,c}]}//Flatten p5[row_List] := {{},row}//.{ {{d___},{a_,b___,c_}}/;a<c :> {{d,c},{a,b}}, {{d___},{a_,b___,c_}}/;a>=c :> {{d,a},{b,c}}}//Flatten testrow = Range[500] testtime := Timing[#1[testrow]][[1]]& /@ {p1, p2, p3, p4, p5} TableForm[{{p1, p2, p3, p4, p5}, testtime /. Second -> s}] Here's the result of the timing test on an RS6000: Out[4]//TableForm= p1 p2 p3 p4 p5 0.44 s 0.7 s 2.59 s 1.02 s 0.83 s The `functional` solution p3 is the least efficient, and the `procedural` p1 is faster than the rule-based p4 and p5 by a significant margin. Also, the solution p3 doesn't work when `row` has identical entries. -- ___________________________________________________________________________________ Levent Kitis lk3a at cars.mech.virginia.edu lk3a at kelvin.seas.virginia.edu University of Virginia Department of Mechanical, Aerospace, and Nuclear Engineering ==== [MESSAGE SEPARATOR] ====