"Fredrik Lundh" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > 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 -- http://mail.python.org/mailman/listinfo/python-list
