如何从字典列表中找到5个玩家ID最高的分数？

Question

我有一份类似字典的清单

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}]

如何使用python从这里找到5个最大分数和玩家ID。谢谢

Answer 1

^{} module提供了nlargest和nsmallest函数来返回这样的序列段

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")

产生：

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

Answer 2

一种方法是对第一个元素进行排序，并选择在O(n * log n)中运行的第一个k=5元素：

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}]

但运行此任务更有效的方法是使用在 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}