总结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个条目.

例如,上面示例的前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很陌生,并且自己尝试在lambda函数上链接一个sum和filter函数,但是在实际的语法上却很挣扎.

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,但记住插入顺序.