Standard Forth versus Python: a case study

Paul McGuire ptmcg at
Thu Oct 12 16:18:45 CEST 2006

"Fredrik Lundh" <fredrik at> wrote in message 
news:mailman.379.1160661911.11739.python-list at
> 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.
> </F>


-- Paul

More information about the Python-list mailing list