Новый dict верхних n значений (и ключей) из словаря (Python)

У меня есть словарь имен и количество раз, когда имена появляются в телефонной книге:

names_dict = { 'Adam': 100, 'Anne': 400, 'Britney': 321, 'George': 645, 'Joe': 200, 'John': 1010, 'Mike': 500, 'Paul': 325, 'Sarah': 150 } 

Предпочтительно, не используя sorted() , я хочу перебирать словарь и создавать новый словарь, который имеет только пять лучших имен:

 def sort_top_list(): # create dict of any 5 names first new_dict = {} for i in names_dict.keys()[:5]: new_dict[i] = names_dict[i]: # Find smallest current value in new_dict # and compare to others in names_dict # to find bigger ones; replace smaller name in new_dict with bigger name for k,v in address_dict.iteritems(): current_smallest = min(new_dict.itervalues()) if v > current_smallest: # Found a bigger value; replace smaller key/ value in new_dict with larger key/ value new_dict[k] = v # ?? delete old key/ value pair from new_dict somehow 

Кажется, я могу создать новый словарь, который получает новую пару ключ / значение всякий раз, когда мы итерации через names_dict и находим имя / счет, который выше, чем у нас в new_dict. Однако я не могу понять, как удалить меньшие из new_dict после того, как мы добавим более крупные из names_dict.

Есть ли лучший способ – без необходимости импорта специальных библиотек или использования sorted() – для итерации через dict и создания нового dict из верхних N ключей с самыми высокими значениями?

Для достижения этой цели вы должны использовать heapq.nlargest() :

 import heapq from operator import itemgetter top_names = dict(heapq.nlargest(5, names_dict.items(), key=itemgetter(1))) 

Это использует более эффективный алгоритм (O (NlogK) для определения размера N и K верхних элементов), чтобы извлечь верхние 5 элементов в виде (key, value) кортежей, которые затем передаются в dict() для создания нового словаря ,

Демо-версия:

 >>> import heapq >>> from operator import itemgetter >>> names_dict = {'Adam': 100, 'Anne': 400, 'Britney': 321, 'George': 645, 'Joe': 200, 'John': 1010, 'Mike': 500, 'Paul': 325, 'Sarah': 150} >>> dict(heapq.nlargest(5, names_dict.items(), key=itemgetter(1))) {'John': 1010, 'George': 645, 'Mike': 500, 'Anne': 400, 'Paul': 325} 

Вероятно, вы захотите использовать класс collections.Counter() . Метод Counter.most_common() сделал бы ваш случай использования тривиальным для решения. В реализации этого метода используется heapq.nlargest() под капотом.

Это не специальные библиотеки, они являются частью стандартной библиотеки Python. В противном случае вам придется реализовать двоичную кучу для достижения этой цели. Если вы специально не изучаете этот алгоритм, нет смысла перестраивать свои собственные, реализация Python сильно оптимизирована с расширением, написанным на C для некоторых критических функций).

Я не знаю, почему вы не хотите использовать сортировку, и решение не является совершенным и даже не соответствует вашей проблеме, но я надеюсь, что это может вдохновить вас найти свою собственную реализацию. Я думаю, что это был лишь краткий пример реальной проблемы.

Но, как вы видели на другом ответе: Обычно лучше использовать код, который написан раньше, а не делать все сами.

 names_dict = {'Joe' : 200, 'Anne': 400, 'Mike': 500, 'John': 1010, 'Sarah': 150, 'Paul': 325, 'George' : 645, 'Adam' : 100, 'Britney': 321} def extract_top_n(dictionary, count): #first step: Find the topmost values highest_values = [] for k,v in dictionary.iteritems(): print k,v, highest_values, len(highest_values) highest_values.append(v) l = len(highest_values) for i in range(l-1): print i,l if li < 1: break if highest_values[li-1]>highest_values[li-2]: temp = highest_values[li-2] highest_values[li-2] = highest_values[li-1] highest_values[li-1] = temp highest_values = highest_values [:count] #fill the dirctionary with all entries at least as big as the smallest of the biggest #but pay attention: If there are more than 2 occurances of one of the top N there will be more than N entries in the dictionary last_interesting = highest_values[len(highest_values)-1] return_dictionary = {} for k,v in dictionary.iteritems(): if v >= last_interesting: return_dictionary[k] = v return return_dictionary print extract_top_n(names_dict,3)