python - Python 字典列表字典中的最大值

Question

考虑字典列表的字典，如下所示:

{1: [{'date': 6/31/2015, 'bits': 1},
     {'date': 6/25/2015, 'bits': 5}],
 2: [{'date': 7/31/2013, 'bits': 5},
     {'date': 7/28/2015, 'bits': 0}],
 6: [{'date': 4/23/2010, 'bits': 10},
     {'date': 1/1/2009,  'bits': 1}]}

什么是最有效的方法(从时间复杂度的角度)从内部字典中找到具有最大值的条目，并从主字典中按键分组？在平局的情况下，最里面的字典中的另一个键决定获胜者。

使用上面的字典，找到键 'bits' 的最大值，使用键 'date' 打破平局(有利于最近的)结果应该是词典

{1: {'date': 6/25/2015, 'bits': 5},
 2: {'date': 7/31/2013, 'bits': 5},
 6: {'date': 4/23/2010, 'bits': 10}}`.

我目前有一个使用两个嵌套的 for 循环的实现。我正在考虑按字段 bits 对列表进行排序，以找到具有最大值的条目。

当前的实现如下:

for key in dicts:
   for data in dicts[key]:
      if(data["bits"]>max_bits):
         max_bits= data["bits"]
         date =data["date"]
      elif (data["bits_corrected"]==max_bits):
           if(data["date"] >date):
              date=data["date"]

但是对于大型数据集来说需要花费很多时间。请提出最佳解决方案

Answer 1

让我们建立一个框架来根据经验回答这个问题。测试算法实际运行的速度总是最好的，而不是仅仅猜测。

首先是一种生成测试数据的方法:

import datetime
import random

def generate_data(sz_outer, sz_inner):
    res = {}
    for n in range(sz_outer):
        res[n] = []
        for m in range(sz_inner):
            date = datetime.date(
                year=random.sample(range(2010, 2015), 1)[0],
                month=random.sample(range(1, 13), 1)[0],
                day=random.sample(range(1, 29), 1)[0],
                )
            bits = random.sample(range(10), 1)[0]
            res[n].append({'date': date, 'bits': bits})
    return res

这里有两种可能的解决方案。第一个使用 pandas 模块将您的字典列表转换为更结构化的数据类型。第二种是使用纯 Python 的直接实现，以及基于键的元组按重要性排序的排序键。

def choose_best1(dict_list):
    df = pandas.DataFrame.from_records(dict_list)
    return df.sort(['bits', 'date']).irow(-1).to_dict()

def choose_best2(dict_list):
    srted = sorted(dict_list, key=lambda k: (k['bits'], k['date']))
    return srted[-1]

运行测试的方法:

def run_test(data, method=choose_best1):
    bests = {}
    for key, dict_list in data.items():
        best = method(dict_list)
        bests[key] = best
    return bests

我们用这两种方法得到相同的结果:

data = generate_data(10, 10000)
bests1 = run_test(data, choose_best1)
bests2 = run_test(data, choose_best2)

哪个更快？完全取决于你最里面的字典列表的大小。对于足够大的内部列表，支付转换为 DataFrame 的前期成本是值得的，以便从 pandas 中可用的更优化的排序算法中获益。对于一个简短的内部列表，最好只使用 sorted。

对于 10000 条记录，pandas 方法更快:

data = generate_data(10, 10000)

In [79]: %timeit run_test(data, choose_best1)
10 loops, best of 3: 116 ms per loop

In [80]: %timeit run_test(data, choose_best2)
10 loops, best of 3: 151 ms per loop

对于 100 条记录，排序方法要快得多:

data = generate_data(10, 10000)

In [82]: %timeit run_test(data, choose_best1)
100 loops, best of 3: 15 ms per loop

In [84]: %timeit run_test(data, choose_best2)
1000 loops, best of 3: 710 µs per loop

请注意，外部字典的大小完全无关，因为每个条目都是完全独立处理的。所以总时间就是外层字典中每个条目所需时间的总和。