有时我发现自己想要的东西语言不太容易支持。我非常习惯用 C++ 创建类和对象来将数据组合在一起(即当没有方法时)。然而,在 Python 中,你可以动态添加字段,而我基本上一直想要的是 Matlab 结构。我认为这可能是我没有使用良好风格并且没有以“Pythonic”方式做事的迹象。
下面是我实现的 union-find 数据结构(用于 Kruskal 算法)。虽然实现相对较短且运行良好(没有太多错误检查),但仍存在一些奇怪之处。例如,我的代码假设最初传递给 union-find 的数据是对象列表。但是,如果传入的是明确的数据列表(即 int 列表),则代码会失败。有没有更清晰、更 Pythonic 的方法来实现这一点?我曾尝试用谷歌搜索,但大多数示例都非常简单,并且与过程代码(即在 Python 中执行 for 循环的“正确”方法)更相关。
class UnionFind:
def __init__(self,data):
self.data = data
for d in self.data:
d.size = 1
d.leader = d
d.next = None
d.last = d
def find(self,element):
return element.leader
def union(self,leader1,leader2):
if leader1.size >= leader2.size:
newleader = leader1
oldleader = leader2
else:
newleader = leader2
oldleader = leader1
newleader.size = leader1.size + leader2.size
d = oldleader
while d != None:
d.leader = newleader
d = d.next
newleader.last.next = oldleader
newleader.last = oldleader.last
del(oldleader.size)
del(oldleader.last)
你在 Python 中的 UnionFind
实现已经非常接近解决问题了,但确实有改进的空间,使代码更符合 Python 的设计哲学(”Pythonic”),同时更清晰易懂。下面是我的一些建议,帮助你用更 Pythonic 的方式实现 Union-Find 数据结构。
动态添加字段的问题:
动态添加字段(如 d.size
, d.leader
, d.next
等)可能导致代码难以维护,尤其是当传入的 data
不是对象列表时(如整数列表)。更好的方法是创建一个轻量级的节点类来明确表示这些属性。
对输入的假设:
当前代码假设传入的 data
是对象列表,而不是简单类型(如整数)。这种假设可能会让用户感到意外,可以通过改进初始化逻辑支持更广泛的输入。
性能优化:
find
方法和 union
方法可以通过路径压缩(path compression)和按秩合并(union by rank)进一步优化。
可读性和 Python 风格:
代码的结构可以进一步简化,并使用 Python 数据结构(如字典)或 dataclasses
来增强清晰性和简洁性。
UnionFind
实现以下是经过改进的实现:
class UnionFind:
class Node:
def __init__(self, value):
self.value = value
self.parent = self # 初始时每个节点的父节点是自己
self.rank = 0 # 用于按秩合并(初始秩为0)
def __init__(self, elements):
# 初始化 Union-Find,每个元素作为单独的集合
self.nodes = {e: self.Node(e) for e in elements}
def find(self, element):
"""查找元素的根节点,并进行路径压缩"""
node = self.nodes[element]
if node.parent != node:
node.parent = self.find(node.parent.value) # 路径压缩
return node.parent.value
def union(self, element1, element2):
"""合并两个集合,按秩合并"""
root1 = self.nodes[self.find(element1)]
root2 = self.nodes[self.find(element2)]
if root1 == root2:
return # 已经属于同一集合,无需合并
# 按秩合并:将小秩树挂在大秩树上
if root1.rank > root2.rank:
root2.parent = root1
elif root1.rank < root2.rank:
root1.parent = root2
else:
root2.parent = root1
root1.rank += 1 # 秩仅在两棵树秩相等时增加
def connected(self, element1, element2):
"""检查两个元素是否在同一集合中"""
return self.find(element1) == self.find(element2)
Node
:value
、parent
和 rank
属性,避免了动态添加字段的做法。这使得代码更加清晰,并且支持任意输入类型(如整数、字符串等)。
路径压缩(Path Compression):
在 find
方法中,递归更新每个节点的父节点为根节点,从而大幅减少后续查找的层数。
按秩合并(Union by Rank):
在 union
方法中,根据树的高度(秩)合并集合,减少了树的深度。
字典存储节点:
使用字典将元素映射到 Node
对象,这样用户可以传入任意类型的元素,而不需要将输入限制为对象列表。
易用性:
connected
方法,简化了检查两个元素是否属于同一集合的逻辑。# 初始化 Union-Find
uf = UnionFind([1, 2, 3, 4, 5])
# 合并一些集合
uf.union(1, 2)
uf.union(3, 4)
uf.union(2, 4)
# 检查连接性
print(uf.connected(1, 4)) # True
print(uf.connected(1, 5)) # False
# 找到元素的根节点
print(uf.find(1)) # 3(可能不同,取决于秩合并的顺序)
这种实现具有接近 (O(1)) 的摊还时间复杂度(amortized complexity):
- find
方法:通过路径压缩优化到几乎常数时间。
- union
方法:通过按秩合并,减少了树的深度。
相比你当前的实现,这种方式在数据规模较大时性能会更好。
UnionFind
实现更加高效。你可以在此基础上进一步扩展,例如支持批量合并或查询操作。希望这对你有所帮助!