How do I find 5 largest score with player ID from this list of dictionary?

Question

i have a list of dictionary like.

players_score = [{'playerID': 'bondsba01', 'score': 771.0309445542441}, 
{'playerID': 'brookhu01', 'score': 334.40601958915977}, 
{'playerID': 'jamesbo01', 'score': 885.9822344322345}, 
{'playerID': 'hassero01', 'score': 593.022015503876}, 
{'playerID': 'addybo01', 'score': 785.2226861630111}, 
{'playerID': 'cedence01', 'score': 75.7351748570627}, 
{'playerID': 'eckerde01', 'score': 787.7921476129764}, 
{'playerID': 'wockejo01', 'score': 674.6701980001981}]

How can i find the 5 largest score and player ID from here using python. Thanks

Answer 1

One way is to sort the first and pick the first k=5 elements which runs in O(n * log n) :

sorted_list = sorted(players_score, key=lambda x: x['score'], reverse=True)
sorted_list[:5]

#[{'playerID': 'jamesbo01', 'score': 885.9822344322345}, 
#{'playerID': 'eckerde01', 'score': 787.7921476129764}, 
#{'playerID': 'addybo01', 'score': 785.2226861630111}, 
#{'playerID': 'bondsba01', 'score': 771.0309445542441}, 
#{'playerID': 'wockejo01', 'score': 674.6701980001981}]

But the more efficient way to run this task is to use Min Heap which runs in O((n-k)*logk):

def FirstKelements(arr, size, k):

    minHeap = []
    for i in range(k):
        minHeap.append(arr[i])

    for i in range(k, size):
        minHeap.sort(key=lambda x: x['score'])

        if (minHeap[0]['score'] > arr[i]['score']):
            continue

        else:
            minHeap.pop(0)
            minHeap.append(arr[i])

    for i in minHeap:
        print(i, end="\n")

FirstKelements(players_score, len(players_score), 5)

#{'playerID': 'bondsba01', 'score': 771.0309445542441} 
# {'playerID': 'addybo01', 'score': 785.2226861630111} 
# {'playerID': 'eckerde01', 'score': 787.7921476129764} 
# {'playerID': 'jamesbo01', 'score': 885.9822344322345} 
# {'playerID': 'wockejo01', 'score': 674.6701980001981}

Answer 2

The heapq module provides both nlargest and nsmallest functions to return such sections of sequences.

import heapq

players_score = [{'playerID': 'bondsba01', 'score': 771.0309445542441}, 
{'playerID': 'brookhu01', 'score': 334.40601958915977}, 
{'playerID': 'jamesbo01', 'score': 885.9822344322345}, 
{'playerID': 'hassero01', 'score': 593.022015503876}, 
{'playerID': 'addybo01', 'score': 785.2226861630111}, 
{'playerID': 'cedence01', 'score': 75.7351748570627}, 
{'playerID': 'eckerde01', 'score': 787.7921476129764}, 
{'playerID': 'wockejo01', 'score': 674.6701980001981}]

winners = heapq.nlargest(3,players_score, key=lambda x:x['score'])
print(*winners,sep="\n")

produces:

{'playerID': 'jamesbo01', 'score': 885.9822344322345}
{'playerID': 'eckerde01', 'score': 787.7921476129764}
{'playerID': 'addybo01', 'score': 785.2226861630111}