Питонический способ группировки списка объектов по списку str

#python #sorting #python-dataclasses

Вопрос:

У меня есть класс данных, например

 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

Комментарии:

1. Конечно, вы можете использовать itertools.groupby . Но это не будет более эффективным. itertools это не какая-то волшебная палочка; это куча петель для, завернутых в аккуратные функции. Очень полезно для написания самодокументируемого кода, но не более эффективно, чем написание циклов самостоятельно.

Ответ №1:

itertools.groupby является полезным/эффективным только в том случае, если:

  1. Вы можете применить порядок к вводимым данным таким образом, чтобы все предполагаемые члены группы были смежными, и
  2. Ни один элемент не должен принадлежать нескольким группам.

Описанный вами вариант использования нарушает оба критерия (каждый элемент принадлежит к стольким группам, сколько у него тегов, нет разумного порядка сортировки, который бы их группировал), поэтому itertools.groupby он неуместен. Правильное решение-то, которое вы описываете; сделайте a dict (или для удобства, a collections.defaultdict(list) , чтобы избежать необходимости возиться с тестированием членства и/или 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)
 

что примерно настолько эффективно, насколько это возможно; каждая пара мест/тегов повторяется ровно один раз, и dict поиск , хотя технически и является наихудшим O(n) , является средним случаем O(1) . Единственная доступная значимая оптимизация заключалась бы в том, если бы теги можно было легко преобразовать в list индексы фиксированного размера, уменьшив средний регистр O(1) до фактического O(1) , но это вряд ли будет иметь значение (попытка улучшить его-преждевременная оптимизация).