Standard Forth versus Python: a case study

[Gabriel Genellina]

At Thursday 12/10/2006 21:54, Paul Rubin wrote:

>Gabriel Genellina <gagsl-py at yahoo.com.ar> writes:
> > That explains all. Finding the median in an efficient way (that is,
> > without sorting the data first) isn't trivial, so your claim of "I can
> > do that using only one temp variable" was a bit surprising...
> > BTW, the median is the value which sits just in the middle of the list
> > when ordered: median(3,5,12,1,2)=median(1,2,3,5,12) = 3
>
>How is this?  Note that m and n are treated as constants, so
>expressions like n-1, n/2 etc. are also constants.  Also assume
>m[i+1] is evaluated as (m+1)[i] and of course m+1 is constant.
>
>median (int m[], int n)
>{
>   while (1) {
>       for (i = 0; i < n-1; i++) {
>     }
>   return m[n / 2];

Oh, yes, almost no auxiliary storage needed! You are sorting the data 
first, then getting the middle element.
So if you are really really really concerned about variable storage 
(maybe an embedded application?) this may work, at the expense of 
speed: this sort appears to be O(n2), quicksort would do in O(nlogn), 
and a customised version -at each stage, continue sorting only the 
branch containing the median- can work in *expected* linear time.
Of course other set of constraints would dictate another approach, 
maybe minimizing the number of array accesses by example.


-- 
Gabriel Genellina
Softlab SRL 


	
	
		
__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas