#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
является полезным/эффективным только в том случае, если:
- Вы можете применить порядок к вводимым данным таким образом, чтобы все предполагаемые члены группы были смежными, и
- Ни один элемент не должен принадлежать нескольким группам.
Описанный вами вариант использования нарушает оба критерия (каждый элемент принадлежит к стольким группам, сколько у него тегов, нет разумного порядка сортировки, который бы их группировал), поэтому 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)
, но это вряд ли будет иметь значение (попытка улучшить его-преждевременная оптимизация).