0

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

我遇到了一个 python 森林实现（不是我的！），并且很难理解字典的__init__工作原理。wikipedia 的例子很容易理解（这个实现是基于wiki 的伪代码）。特别是，这条线对我来说很陌生

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

我看不到这个 dict 构造函数在做什么，我的猜测是对于从0to的每个数字vertices， av都作为键和值插入到字典中，但是键有一个包含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]'s 和[1]'s 是如何使用的。我只能通过[0]我们如何初始化字典结构来建立联系。当然，仅基于比较，就很容易知道它们指的是什么，但是在结构中使用 0 和 1 是如何做到的呢？

此外，如果您需要我正在谈论的整个代码，您可以在此处找到它。

4

2 回答 2

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

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

因此，不是使用命名字段构建结构，而是将它们映射到 Python 中的索引list。

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

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

于 2016-02-20T22:08:09.580 回答
0

我编写了 python 代码，我很高兴传达我对这个主题的想法。

基本思想是，点调用在 Python 中很慢，如此处所示。有问题的是， wiki上建议的结构需要点调用：

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

但是，我们不想进行点调用，因此我们可以将 parent 和 rank 替换为第一个位置是父级，第二个位置是排名的列表。如果我们将初始化对象从转换makeset为列表，我们会得到：

x = [x.parent, x.rank]

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

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

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

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

或者，如果想要更快地做到这一点，可以使用字典理解（请注意，我使用 Python 2.6 语法的原因我不清楚。两者都包含在下面；尽管出于此处指定的原因，应该首选 2.7 的文字。我改变了我在博客上的代码以适应此发现。）。

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

希望这更有意义！

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

米

于 2016-02-25T03:33:35.600 回答