преобразовать определение списка из итерации в понимание

Question

У меня есть метод, который принимает список ребер, ребро имеет такую ​​форму: (v1,v2,capacity) и возвращает словарь этой формы:

dico = {v1:{v2:capacity,v3:capacity} v2:...}

это dico представляет график

Я хочу определить этот дико с помощью способа понимания, но я действительно заблокирован, и я даже не уверен, что мы можем это сделать, поэтому кто-то может сказать мне, если это возможно?это моя функция:

def _init_from_edges(self, edges):
    self._G={}
    for e in edges:
        if e[0] in self._G:
            self._G[e[0]][e[1]]=e[2]
        else:
            self._G[e[0]]={e[1]:e[2]}

Answer 1

Это немного запутанно, но, похоже, работает:

edges = [(1, 2, 3),
         (1, 3, 4),
         (2, 1, 5),
         (2, 3, 6),
         (2, 2, 7)]
dico = {v1: {v2: cap for v, v2, cap in edges if v == v1} for v1, _, _ in edges}
# {1: {2: 3, 3: 4}, 2: {1: 5, 2: 7, 3: 6}}

В основном для каждого v1 он добавляет каждую пару ключ: значение в edges с этим v1.Внешнему пониманию не нужны v2 или cap, поэтому он просто использует подчеркивание, чтобы игнорировать эти значения.Внутренний цикл должен сравнивать его значение v1 со значением внешнего цикла, поэтому он использует другое имя.

Answer 2

Ваш код не может легко использовать преимущества dict пониманий, потому что это фактически мультидикт (когда ключ не имеет одно значение, но много).

Вы можете немного упростить код с collections.defaultdict:

from collections import defaultdict

def _init_from_edges(self, edges):
    self._G = defaultdict(dict)
    for v1, v2, capacity in edges:
        self._G[v1][v2] = capacity
    # Optional: Remove defaultdict behaviors after building
    self._G = dict(self._G)

Использование defaultdict(dict) означает, что когда ключ отсутствует в словаре, он сразу создается с новым dict, поэтому вы не сможетенужно вообще проверять членство.

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

Единственный способ сделать этоработать с фактическим пониманием dict можно следующим образом:

1. Повторно сканировать edges один раз для каждого ввода, чтобы собрать все пары v2 / capacity для данного v1 (ноэто O(n**2), поэтому плохая идея, если edges может быть большим)
2. Заранее упаковать все значения для каждого v1 вместе, так что каждый под dict может быть построен все водин раз.

Поскольку вариант № 1, как правило, довольно расточительныйединственный практический способ сделать это как dict понимание без повторного сканирования edges снова и снова - это вариант # 2, который вы можете сделать в O(n log n) с сортировкой , за которой следует itertools.groupby:

from itertools import groupby
from operator import itemgetter

def _init_from_edges(self, edges):
    self._G = {v1: {v2: capacity for _, v2, capacity in grp}
               for v1, grp in groupby(sorted(edges, key=itemgetter(0)),
                                      key=itemgetter(0))}

Требуется O(n log n) работа для сортировки edges (если edges уже отсортирована, TimSort Python означает, что она ближе к O(n) работе), тогда O(n)работать, чтобы сгруппировать результаты.Быстрее, чем {v1: {v2: capacity for v, v2, capacity in edges if v == v1} for v1, _, _ in edges}, но все же медленнее, чем метод непонимания с defaultdict (что при всех обстоятельствах равно O(n)).