[Tutor] Getting greatest 3 numbers from list

[Peter Otten]

On 21/02/2022 12:29, Manprit Singh wrote:
> Dear Sir,
>
> My problem is to get greatest 3 numbers from list, list ls  along with
> solution given below:
> ls = [2, 4, 9, 6, 3, 9, 6, 1]
> sorted(set(ls))[-3:]
>
> gives the right answer
>
> [4, 6, 9]
>
> Tried it with a for loop, just thinking why i am producing  a sorted list , for
>
> only getting largest 3 items
>
> lmax = []
> ls = [2, 4, 9, 6, 3, 9, 6, 1]
> for _ in range(3):
>      mx = ls[0]
>      for ele in ls[1:]:
>          if ele > mx and ele not in lmax:
>              mx = ele
>      lmax.append(mx)
> print(lmax)
>
> gives the correct answer
>
> [9, 6, 4]
>
> This problem be done with a for loop more easily ? i know it is not a good
>
> question - my apologies
>

I don't think it's a bad question. One answer is to keep the 3 largest
values in a heap starting with the first three in the sequence.
Then remove the smallest value and insert the current value from the
iteration whenever it is larger than the smallest value in the heap.

See the source and docs for the heapq.nlargest() function for a detailed
explanation. If the current implementation looks too complicated start
with an older version (before 3.5) of the module where nlargest()
doesn't accept a 'key' parameter.

https://docs.python.org/3/library/heapq.html#heapq.nlargest
https://docs.python.org/3/library/heapq.html#theory

PS: Here's an implementation that uses a sorted list to keep the largest
n items:

 >>> def nlargest(n, items):
	items = iter(items)
	result = sorted(islice(items, n))
	for item in items:
		if item > result[0]:
			result[0] = item
			result.sort()
	return result

 >>> from itertools import islice
 >>> from random import shuffle
 >>> items = list(range(10))
 >>> shuffle(items)
 >>> items
[1, 0, 9, 3, 4, 6, 7, 5, 2, 8]
 >>> nlargest(3, items)
[7, 8, 9]