Last active
February 21, 2020 15:34
-
-
Save jgomo3/70df1704a5c242be8b17ab4198bbdf70 to your computer and use it in GitHub Desktop.
Return the first n elements of a collection by natural order of by a key function
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import heapq | |
def top(n, col, key=None): | |
return heapq.nsmallest(n, col, key) | |
# Alternative, descent only for small n. | |
from itertools import count | |
def top_small_n(n, col, key=None): | |
podium = [] | |
for i, e in enumerate(col): | |
if i < n: | |
podium.append(e) | |
else: | |
podium[-1] = e | |
if i >= n: | |
podium.sort(key=key) | |
if i < n: | |
podium.sort(key=key) | |
return podium |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@jackboot7: Good! Really straightforward.
As the docs of
heapq.nsmallest
says:And I was thinking, that
top_small
function could be the best option for really big size of collections and smalln
. Think about it: the top 10 of many millions of something. The function would traverse the collection only once, and sort thepodium
of 10 elements, many millions of times. That is still linear, I think.