Standard Forth versus Python: a case study

[Paul McGuire]

"Fredrik Lundh" <fredrik at pythonware.com> wrote in message 
news:mailman.379.1160661911.11739.python-list at python.org...
> Paul McGuire wrote:
>
>> My original question was in response to your post, that sort() wasn't 
>> required but only a temp variable.  I am very interested in seeing your 
>> solution that does not require the data to be sorted.  (This is not just 
>> an academic exercise - given a large historical data set, sorting the 
>> data is one of the costliest parts of computing the median, and I would 
>> greatly appreciate seeing an alternative algorithm.)
>
> if you absolutely definitely cannot afford to modify or copy the input 
> data set, but can
> read the data sequentially multiple times reasonably fast, you can do 
> what's basically a
> binary search for the median, by counting how many values you have that's 
> above or
> below the current guess, and repeating until you find the right value. 
> see e.g.
>
>    http://ndevilla.free.fr/median/median/src/torben.c
>
> </F>

Thanks!

-- Paul