Подведение итогов словаря массивов в Python

Question

Я получил следующий словарь:

mydict = {
  'foo': [1,19,2,3,24,52,2,6],          # sum: 109
  'bar': [50,5,9,7,66,3,2,44],          # sum: 186
  'another': [1,2,3,4,5,6,7,8],         # sum:  36
  'entry': [0,0,0,2,99,4,33,55],        # sum: 193
  'onemore': [21,22,23,24,25,26,27,28]  # sum: 196
}

Мне нужно эффективно отфильтровать и отсортировать верхние записи x по сумме массива.

Например, список Top 3, отсортированный и отфильтрованный для приведенного выше примера, будет

sorted_filtered_dict = {
  'onemore': [21,22,23,24,25,26,27,28], # sum: 196
  'entry': [0,0,0,2,99,4,33,55],        # sum: 193
  'bar': [50,5,9,7,66,3,2,44]           # sum: 186
}

Я довольно новичок в Python, и я сам попробовал это с цепочкой функций суммы и фильтра для лямбда-функции, но боролся с реальным синтаксисом.

Answer 1

Это легко сделать с помощью сортировки:

sorted(mydict.iteritems(), key=lambda tup: sum(tup[1]), reverse=True)[:3]

Это разумно, если соотношение аналогично этому (3/5).Если оно больше, вам нужно избегать сортировки (O (n log n)), так как топ-3 можно выполнить за O (n).Например, используя heapq , модуль кучи:

heapq.nlargest(3, mydict.iteritems(), key=lambda tup: sum(tup[1]))

Это O (n + 3 log n), так как при сборке начальная куча - O (n) и повторная кучаравно O (log n).

РЕДАКТИРОВАТЬ: Если вы используете Python 2.7 или более поздней версии, вы можете легко преобразовать в OrderedDict ( эквивалентную версию дляPython 2.4 +):

OrderedDict(heapq.nlargest(3, mydict.iteritems(), key=lambda tup: sum(tup[1])))

OrderedDict имеет тот же API, что и dict, но запоминает порядок вставки.

Answer 2

Для такого маленького среза не стоит использовать islice

sorted(mydict.iteritems(), key=lambda (k,v): sum(v), reverse=True)[:3]