CODEWITHSUNDEEP
pythonmax
Albert
Albert

Reputation: 68360

Python: take max N elements from some list

Is there some function which would return me the N highest elements from some list?

I.e. if max(l) returns the single highest element, sth. like max(l, count=10) would return me a list of the 10 highest numbers (or less if l is smaller).

Or what would be an efficient easy way to get these? (Except the obvious canonical implementation; also, no such things which involve sorting the whole list first because that would be inefficient compared to the canonical solution.)

Upvotes: 41

Views: 43580

Answers (5)

Jack
Jack

Reputation: 303

If you do not mind using pandas then:

import pandas as pd
N = 10
column_name = 0
pd.DataFrame(your_array).nlargest(N, column_name)

The above code will show you the N largest values along with the index position of each value.

Pandas nlargest documentation

Upvotes: 1

Gintautas Miliauskas
Gintautas Miliauskas

Reputation: 7892

A fairly efficient solution is a variation of quicksort where recursion is limited to the right part of the pivot until the pivot point position is higher than the number of elements required (with a few extra conditions to deal with border cases of course).

The standard library has heapq.nlargest, as pointed out by others here.

Upvotes: 1

David Webb
David Webb

Reputation: 193814

The function in the standard library that does this is heapq.nlargest

Upvotes: 7

Gareth Rees
Gareth Rees

Reputation: 65884

heapq.nlargest:

>>> import heapq, random
>>> heapq.nlargest(3, (random.gauss(0, 1) for _ in xrange(100)))
[1.9730767232998481, 1.9326532289091407, 1.7762926716966254]

Upvotes: 60

Spacedman
Spacedman

Reputation: 94317

Start with the first 10 from L, call that X. Note the minimum value of X.

Loop over L[i] for i over the rest of L.

If L[i] is greater than min(X), drop min(X) from X and insert L[i]. You may need to keep X as a sorted linked list and do an insertion. Update min(X).

At the end, you have the 10 largest values in X.

I suspect that will be O(kN) (where k is 10 here) since insertion sort is linear. Might be what gsl uses, so if you can read some C code:

http://www.gnu.org/software/gsl/manual/html_node/Selecting-the-k-smallest-or-largest-elements.html

Probably something in numpy that does this.

Upvotes: 3

Related Questions