[EMAIL PROTECTED] wrote: > John Doty: > > Yes. The efficient exact algorithms for this problem use *partial* > > sorts. The Forth one from the FSL is of this class (although I know of > > two better ones for big arrays). But it's tough to beat the efficiency > > of the approximate histogram-based method the Python stats module > > implements. > > The usual way to compute a true median with Python may be: > > def median(inlist): > newlist = sorted(inlist) > index = len(newlist) // 2 > if len(newlist) % 2: > return newlist[index] > else: > return (newlist[index] + newlist[index-1]) / 2.0 > > If you can use Psyco and your FITS lines are really long (well, maybe > too much, the treshold if about >~3000 in my PC) you can use something > like this instead the builtin timsort: > http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/466330 > (To compute the median on a image line the median that uses sort is > probably better in most cases, expecially if you use the built in sort > of numerical libraries.) > > Bye, > bearophile
partial bucket sort with quicksort of individual bucket needed for index list. APL would be fast, try a solution in J it calculates need on demand i think, and so the calculation dependance tree only does the one quicksort on the bucket needed, or both if on a bucket boundry, but this can be avoided with clever bucket selection. cheers -- http://mail.python.org/mailman/listinfo/python-list