时间戳

首页 > 解决方案 > 将列表的定义从迭代转换为理解

python - 将列表的定义从迭代转换为理解

问题描述

我有一个采用边缘列表的方法，边缘具有这种形式：(v1,v2,capacity)并返回这种形式的字典：

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

这dico代表一个图表

我想通过理解的方式定义这个 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]}

标签： pythonpython-3.xdictionary-comprehension

解决方案

您的代码不能轻易利用dict理解，因为它实际上是一个 multidict（其中一个键没有一个值，而是多个值）。

您可以使用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已经排序，Python 的 TimSort 意味着它更接近O(n)工作），然后O(n)对结果进行分组。比 快{v1: {v2: capacity for v, v2, capacity in edges if v == v1} for v1, _, _ in edges}，但仍然比不理解的方法慢defaultdict（O(n)在所有情况下）。

推荐阅读