Standard Forth versus Python: a case study

jacko jackokring at
Thu Oct 12 00:22:29 CEST 2006

bearophileHUGS at 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:
> (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.


More information about the Python-list mailing list