<p>一种选择是使用字典来存储所需的有关数据项的信息,而不是直接存储该项上的属性。例如,您可以引用<code>d.size</code>,而不是引用<code>size[d]</code>(其中<code>size</code>是<code>dict</code>实例)。这要求您的数据项是可散列的,但不需要允许对它们分配属性。在</p>
<p>下面是使用此样式的当前代码的直接翻译:</p>
<pre><code>class UnionFind:
def __init__(self,data):
self.data = data
self.size = {d:1 for d in data}
self.leader = {d:d for d in data}
self.next = {d:None for d in data}
self.last = {d:d for d in data}
def find(self,element):
return self.leader[element]
def union(self,leader1,leader2):
if self.size[leader1] >= self.size[leader2]:
newleader = leader1
oldleader = leader2
else:
newleader = leader2
oldleader = leader1
self.size[newleader] = self.size[leader1] + self.size[leader2]
d = oldleader
while d != None:
self.leader[d] = newleader
d = self.next[d]
self.next[self.last[newleader]] = oldleader
self.last[newleader] = self.last[oldleader]
</code></pre>
<p>最小测试用例:</p>
^{pr2}$
<p>除此之外,您还可以考虑稍微更改一下您的实现,以减少初始化的需要。这是一个不做任何初始化的版本(它甚至不需要知道要处理的数据集)。它使用路径压缩和按等级联合,而不是始终为一个集合的所有成员维护一个最新的<code>leader</code>值。它应该比您当前的代码快得多,尤其是当您正在进行大量联合时:</p>
<pre><code>class UnionFind:
def __init__(self):
self.rank = {}
self.parent = {}
def find(self, element):
if element not in self.parent: # leader elements are not in `parent` dict
return element
leader = self.find(self.parent[element]) # search recursively
self.parent[element] = leader # compress path by saving leader as parent
return leader
def union(self, leader1, leader2):
rank1 = self.rank.get(leader1,1)
rank2 = self.rank.get(leader2,1)
if rank1 > rank2: # union by rank
self.parent[leader2] = leader1
elif rank2 > rank1:
self.parent[leader1] = leader2
else: # ranks are equal
self.parent[leader2] = leader1 # favor leader1 arbitrarily
self.rank[leader1] = rank1+1 # increment rank
</code></pre>