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

```

• Prev by Date: Re: Help - transposing equation
• Next by Date: Re: equ. of 'ls' in 'Context' ?
• Previous by thread: Re: functional code
• Next by thread: Re: functional code