在字典中对列表项进行分组

Question

我想从一个字典列表中生成一个新的字典，通过某个键的值对列表项进行分组，例如：

input_list = [
        {'a':'tata', 'b': 'foo'},
        {'a':'pipo', 'b': 'titi'},
        {'a':'pipo', 'b': 'toto'},
        {'a':'tata', 'b': 'bar'}
]
output_dict = {
        'pipo': [
             {'a': 'pipo', 'b': 'titi'}, 
             {'a': 'pipo', 'b': 'toto'}
         ],
         'tata': [
             {'a': 'tata', 'b': 'foo'},
             {'a': 'tata', 'b': 'bar'}
         ]
}

到目前为止，我发现有两种方法可以做到这一点。第一种方法只是遍历列表，在字典中为每个键值创建子列表，并将与这些键匹配的元素附加到子列表中：

l = [ 
    {'a':'tata', 'b': 'foo'},
    {'a':'pipo', 'b': 'titi'},
    {'a':'pipo', 'b': 'toto'},
    {'a':'tata', 'b': 'bar'}
    ]

res = {}

for e in l:
    res[e['a']] = res.get(e['a'], []) 
    res[e['a']].append(e)

并且另一种使用 itertools.groupby：

import itertools
from operator import itemgetter

l = [ 
        {'a':'tata', 'b': 'foo'},
        {'a':'pipo', 'b': 'titi'},
        {'a':'pipo', 'b': 'toto'},
        {'a':'tata', 'b': 'bar'}
]

l = sorted(l, key=itemgetter('a'))
res = dict((k, list(g)) for k, g in itertools.groupby(l, key=itemgetter('a')))

我想知道哪种选择最有效？

是否有更具Python风格/简洁或执行效率更高的方法来实现这个目标？

- Erwan Queffélec

Answer 1

你是否想根据列表元素中“a”键的值对输入列表进行分组？如果是这样，您的第一个方法是最好的，但可以进行一些小改进，使用dict.setdefault：

res = {}
for item in l:
    res.setdefault(item['a'], []).append(item)

- Bernhard

---

我想按列表元素的'a'键的值对输入列表进行分组，groupby似乎是最好的选择，但我担心强制排序会比简单的for循环增加不必要的复杂性。 - Erwan Queffélec

“best” 在这里是指复杂度方面的，没错。 - Bernhard

我觉得我的问题表述不够清晰。我会接受你的答案，因为它得到了最多的赞同并且回答了我的问题。然而@gen-y-s的答案也很好，因为它澄清了问题和原因，另一个则展示了其时间效率，这在某些情况下可能与复杂性有所不同：例如，如果输入数据集是有序的 - 这是我真实数据的情况 - 第二种方法的复杂度仍然是O(n)。 - Erwan Queffélec

请注意，@ewilazarus的答案实际上表明，在我的几乎排序的数据中，您的解决方案仍然更有效。 - Erwan Queffélec

Answer 2

如果你指的是“时间效率”，那么可以使用内置模块timeit来衡量。例如：

import timeit
import itertools
from operator import itemgetter

input = [{'a': 'tata', 'b': 'foo'},
         {'a': 'pipo', 'b': 'titi'},
         {'a': 'pipo', 'b': 'toto'},
         {'a': 'tata', 'b': 'bar'}]

def solution1():
    res = {}
    for e in input:
        res[e['a']] = res.get(e['a'], [])
        res[e['a']].append(e)
    return res

def solution2():
    l = sorted(input, key=itemgetter('a'))
    res = dict(
        (k, list(g)) for k, g in itertools.groupby(l, key=itemgetter('a'))
    )
    return res

t = timeit.Timer(solution1)
print(t.timeit(10000))
# 0.0122511386871

t = timeit.Timer(solution2)
print(t.timeit(10000))
# 0.0366218090057

请参考timeit官方文档获取更多信息。

- Gabriel Lima

---

是的，我实际上是指“时间效率”。谢谢分享。 - Erwan Queffélec

Answer 3

一句话概括 -

>>> import itertools
>>> input_list = [
...         {'a':'tata', 'b': 'foo'},
...         {'a':'pipo', 'b': 'titi'},
...         {'a':'pipo', 'b': 'toto'},
...         {'a':'tata', 'b': 'bar'}
... ]
>>> {k:[v for v in input_list if v['a'] == k] for k, val in itertools.groupby(input_list,lambda x: x['a'])}
{'tata': [{'a': 'tata', 'b': 'foo'}, {'a': 'tata', 'b': 'bar'}], 'pipo': [{'a': 'pipo', 'b': 'titi'}, {'a': 'pipo', 'b': 'toto'}]}

- Anand S Kumar

---

这可能只是一个一行代码，但它非常低效。它的时间复杂度是二次方的，而问题已经有一个线性的解决方案。 - stephanos

Answer 4

最佳方法是你提到的第一种方法，甚至可以通过使用 Bernhard 上面提到的 setdefault 来使其更加优雅。这种方法的复杂度为 O(n)，因为我们只需简单地遍历输入一次，并对每个项目执行一次查找来找到要附加到其中的适当列表，这需要常量时间（查找+附加）。所以总体复杂度为 O(n)，这是最优的。

当使用 itertools.groupby 时，必须预先对输入进行排序（这是 O(n log n)）。

- gen-y-s

---

我已经知道第二种方法的复杂度是O(n log n)，因此更糟糕，但感谢您澄清了这一点。实际上，我正在寻找与第一种方法具有相同复杂度的解决方案，但使用低开销、内存高效、高性能等解决方案，例如在itertools中找到的解决方案。我想在这种情况下没有这样的解决方案。 - Erwan Queffélec

请注意，Python 使用 Timsort，在数据已经部分排序的情况下具有 O(n) 的复杂度：https://en.wikipedia.org/wiki/Timsort - Erwan Queffélec