Content deleted Content added
→Sorting and heapselect: sorted order may be useful later |
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(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.▼
▲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.
[[Matlab]] includes <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) k values in a vector as well as their indices.
Line 272:
| volume = 13
| year = 1976}}</ref>
<ref name=python>{{citation|url=https://svn.python.org/projects/python/trunk/Lib/|title=heapq package source code|work=Python library|access-date=2023-03-29}}</ref>
}}
| |||