MathGroup Archive 1996

[Date Index] [Thread Index] [Author Index]

Search the Archive

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