Нового ДИКТ верхних значений п (и ключи) из словаря (Python)

Question

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

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 и найти имя/счет, который выше, чем у нас в ne w_dict. Однако я не могу понять, как удалить меньшие из new_dict после того, как мы добавим более крупные из names_dict.

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

Answer 1

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

import heapq 
from operator import itemgetter 

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

При этом используется более эффективный алгоритм (O (NlogK) для Dict размера N и К детали верхнего), чтобы извлечь первые 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() class вместо этого. Counter.most_common() method сделал бы ваш случай использования тривиальным для решения. Реализация для этого метода использует heapq.nlargest() под капотом.

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

Answer 2

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

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

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 l-i < 1: 
       break 
      if highest_values[l-i-1]>highest_values[l-i-2]: 
       temp = highest_values[l-i-2] 
       highest_values[l-i-2] = highest_values[l-i-1] 
       highest_values[l-i-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)