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] ====