Content deleted Content added
There are published journal and book sources for python heapq.nsmallest, but they don't mention its implementation and analysis, or worse garble it. Go back to the source. |
|||
Line 57:
Very few languages have built-in support for general selection, although many provide facilities for finding the smallest or largest element of a list. A notable exception is the [[Standard Template Library]] for [[C++]], which provides a templated <code>nth_element</code> method with a guarantee of expected linear time.{{r|skiena}}
[[Python (programming language)|Python]]'s standard library (since 2.4) includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> subroutines for returning the smallest or largest elements from a collection, in sorted order. As of Python version 3.11, these subroutines use heapselect, taking time <math>O(n+k\log n)</math> to return a list of <math>k</math> elements. When <math>k</math> is large relative to <math>n</math>, they revert to sorting the whole input and then returning a slice of the resulting sorted array. A linear-time selection algorithm is not included.{{r|python}}
For [[Perl]], the module [https://metacpan.org/module/Sort::Key::Top Sort::Key::Top], available from [[CPAN]], provides a set of functions to select the top n elements from a list using several orderings and custom key extraction procedures. Furthermore, the [https://metacpan.org/module/Statistics::CaseResampling Statistics::CaseResampling] module provides a function to calculate quantiles using Quickselect.
| |||