按 str 列表对对象列表进行分组的 Pythonic 方法

Question

我有一个数据class例如

from dataclasses import dataclass
from typing import List

@dataclass
class Place:
    name: str
    tags: List[str]

以及对象列表：

places = [Place(name='Foo', tags=['tagA', 'tagB']), Place(name='Bar', tags=['tagB', 'tagC']), ...]

如果我想按标签对 10000x 个对象进行分组，例如

{
    'tagA': [Place(name='Foo', tags=['tagA', 'tagB'])],
    'tagB': [Place(name='Foo', tags=['tagA', 'tagB']), Place(name='Bar', tags=['tagB', 'tagC'])],
    'tagC': [Place(name='Bar', tags=['tagB', 'tagC'])]
}

一种方法是遍历列表，然后遍历标签列表并构建字典。

但是有更好的方法吗？也许使用 itertools.groupby

Answer 1

itertools.groupby 只有 useful/efficient 如果：

您可以对您的输入进行排序，使组中的所有预期成员都相邻，并且
任何项目都不应属于多个组。

您描述的用例违反了这两个标准（每个项目所属的组与其标签一样多，没有合理的排序顺序可以对它们进行分组），因此 itertools.groupby 是不合适的。正确的解决方案是您描述的那个；做一个 dict （或者为了方便，一个 collections.defaultdict(list) 以避免需要搞乱成员测试 and/or setdefault 调用），迭代所有对象，将它们添加到所有适当的键，例如：

from collections import defaultdict

places = ...

places_by_tag = defaultdict(list)
for place in places:
    for tag in place.tags:
        places_by_tag[tag].append(place)

这是尽可能高效的；每个 place/tag 对只迭代一次，dict 查找，虽然技术上最坏的情况 O(n)，是平均情况 O(1)。唯一可用的有意义的优化是，如果标签可以很容易地转换为固定大小的 list 的索引，将平均情况 O(1) 减少到 actual O(1)，但这不太可能重要（尝试对其进行改进是过早的优化）。

按 str 列表对对象列表进行分组的 Pythonic 方法

Pythonic way to group list of objects by list of str

python

sorting

python-dataclasses