在 Python 中的 dict 构造函数中使用 for 循环初始化不相交集

Question

首先，我主要使用 python 完成非常琐碎的事情，所以我对 pythonic 语法不是很满意。我正在学习不相交集，并且对实现有基本的了解。

我遇到了一个 python 森林实现（不是我的！），我很难理解 __init__ 中的字典是如何工作的。维基百科示例很简单（此实现基于 the wiki's pseudocode）。特别是，这条线对我来说很陌生

  def __init__(self, vertices):
    self.struct = dict((v, [v, 0]) for v in vertices)

我看不出这个 dict 构造函数在做什么，我的猜测是对于从 0 到 vertices 的每个数字，一个 v 被插入到字典中作为键和一个值，但键有一个包含 v 的子集和一个附加的 0？我可能大错特错了。

此外，当我比较 python 代码时

   xV = self.struct[xRoot]
    yV = self.struct[yRoot]
    if xV[1] < yV[1]:
      xV[0] = yRoot
    elif xV[1] > yV[1]:
      yV[0] = xRoot
    else:
      yV[0] = xRoot
      xV[1] += 1

到维基百科的伪代码，

 if xRoot.rank < yRoot.rank
     xRoot.parent := yRoot
 else if xRoot.rank > yRoot.rank
     yRoot.parent := xRoot
 else
     yRoot.parent := xRoot
     xRoot.rank := xRoot.rank + 1

我试图了解 [0] 和 [1] 的用法。我只能将 [0] 与我们初始化字典结构的方式联系起来。当然，仅仅通过比较就知道它们指的是什么是很简单的，但是在struct中使用0和1是怎么做到的呢？

此外，如果您需要我所说的完整代码，您可以找到它 here。

Answer 1

def __init__(self, vertices):
    self.struct = dict((v, [v, 0]) for v in vertices)

这里发生的是 dict 正在构建，其中顶点是键并映射到具有两个元素的 list，element[0] 是顶点本身（.parent 在伪代码中）和 element[1] 是伪代码中顶点的 .rank。

因此，与其构建具有命名字段的结构，不如将它们映射到 Python list.

中的索引

顶点映射到的 list（dict 所做的）包含两个元素，第一个是某种顶点，其类型无关紧要。列表的第二个元素初始化为 0（参见代码的 [v, 0] 部分），一个整数。

使用整数列表索引，...[1] 寻址特定整数。并且整数可以用来表示顶点的等级，并且可以很容易地修改：...[1] += 1 将 1 添加到当前等级。

Answer 2

我写了 python 代码，我很乐意传达我对这个主题的想法。

基本思想是点调用在 Python 中很慢，正如所证明的那样 here. Problematically, the proposed structure on the wiki 需要点调用：

def makeset(x):
  x.parent = x
  x.rank = 0

但是，我们不想做点调用，所以我们可以用第一个位置是父级，第二个位置是等级的列表替换父级和等级。如果我们将初始化对象从 makeset 转换为列表，我们将得到：

x = [x.parent, x.rank]

现在，我们可以将每个 x 放入一个列表中，但在最坏的情况下，这将使每次调用 x O(n)。因此，我们将每个 x 放入一个由其自身名称索引的字典中，以进行 O(1) 查找。这相当于：

dictofsets = {}
for x in vertices:
  dictofsets[x] = [x, 0]

并且，这可以是从键值对列表计算字典的快捷方式（请注意，不可变元组是字典的键值对，而不是 [parent, rank] 的列表）：

dictofsets = dict([(x, [x, 0]) for x in vertices])

或者，dictionary comprehension if one wants to do it even faster (Note that I used Python 2.6 syntax for reasons that are not clear to me. Both are included below; though the literal from 2.7 should be preferred for reasons specified here。我更改了博客上的代码以适应这一发现。)

2.6

dictofsets = dict((x, [x, 0]) for x in vertices)

2.7

dictofsets = {x: [x, 0] for x in vertices}

因此，使用原始命名约定，访问 dict 如下：

dictofsets[x][0] #parent
dictofsets[x][1] #rank

希望这更有意义！

如果您还有其他问题，请给我留言。

男

在 Python 中的 dict 构造函数中使用 for 循环初始化不相交集

Initialising a disjoint set using a for-loop in a dict constructor in Python

python

dictionary

data-structures

disjoint-sets