python - 总结 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

排序很容易:

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 (equivalent version 对于 Python 2.4+):

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

OrderedDict 具有与 dict 相同的 API，但会记住插入顺序。