在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函数把求和和筛选功能连在一起，但在实际的语法上遇到了困难。

Answer 1

对于这么小的一部分，使用islice就不太划算了。

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

Answer 2

用排序的方法来解决这个问题很简单：

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的使用方法和dict是一样的，但它会记住插入的顺序。