list.sort, was Re: [Python-Dev] decorate-sort-undecorate

Raymond Hettinger python at rcn.com
Sat Nov 15 08:32:38 EST 2003


> Getting the 25 smallest elements:
> 
> min_and_remove_repeatedly(lst, 25)               7.4
> list(itertools.islice(heapsort(lst), 25))        1.05
> list(itertools.islice(isorted(lst), 25))         1.03
> list.sorted(lst)[:25]                            6.65
> 
> Getting all elements:
> 
> list(heapsort(lst))                              22.49
> list(isorted(lst))                               26.06
> list.sorted(lst)                                 6.65

Can you find out at what value of N does the time for the heap approach
match the time for the list.sorted() approach.  I'm interested to see
how close it comes to my original 10% estimate.


> While heapsort is not much faster than the Python-coded isorted using
the
> C heappop, if there is interest I can submit it to SF.

Without a much larger speed-up I would recommend against it.  This is
doubly true for the cases where N==1 or N > len(lst)//10 which are
dominated by min() or list.sorted().  Why add a function that is usually
the wrong way to do it.

The situation is further unbalanced against the heap approach when the
problem becomes "get the 25 largest" or for cases where the record
comparison costs are more expensive.


Raymond


#################################################################
#################################################################
#################################################################
#####
#####
#####
#################################################################
#################################################################
#################################################################

#################################################################
#################################################################
#################################################################
#####
#####
#####
#################################################################
#################################################################
#################################################################



More information about the Python-Dev mailing list