Python对象的良好风格

Question

我在Python之前的大部分编程是C++或MATLAB。我没有计算机科学学位（几乎完成了物理学博士学位），但我已经完成了一些课程和大量的实际编程。现在，我在上Coursera的一门算法课程（顺便说一句，斯坦福大学的一位教授的课程非常好）。我决定用Python实现家庭作业。然而，有时我发现自己想要的东西，语言不那么容易支持。我非常习惯于在C++中创建类和对象，以便将数据分组在一起（即，当没有方法时）。但是在Python中，你可以动态地添加字段，我最终想要的是Matlab结构。我想这可能是我没有用好的风格和“Python式”的方式做事。在

下面是我对union-find数据结构的实现（对于Kruskal的算法）。虽然这个实现相对较短并且工作良好（没有太多的错误检查），但也有一些奇怪的地方。例如，我的代码假设最初传递给union find的数据是一个对象列表。但是，如果传递的是显式数据片段列表（即int列表），则代码将失败。有没有更清晰、更具Python式的方法来实现这一点？我试着用google搜索，但是大多数例子都非常简单，并且更多地与过程代码相关（即在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)    

Answer 1

一般来说，以pythonical的方式做这类事情意味着你试图让你的代码不在乎被赋予了什么，至少不会比它真正需要的更多。在

让我们以您的union-find算法为例。union-find算法对传递给它的值的唯一实际操作是比较它们是否相等。因此，要生成一个通常有用的UnionFind类，代码不应该依赖于它接收到的值，而不是进行相等性测试。特别是，您不应该依赖于能够为值分配任意属性。在

我建议解决这个问题的方法是让UnionFind使用包含给定值和使算法工作所需的任何属性的包装器对象。您可以按照另一个答案的建议使用^{}，或者制作一个小的包装类。当一个元素被添加到UnionFind时，首先将其包装在其中一个对象中，并使用包装器对象存储属性leader、size等。访问被包装的对象的唯一时间是检查它是否等于另一个值。在

实际上，至少在这种情况下，可以安全地假设值是散列的，这样就可以在Python字典中使用它们作为键来查找与给定值对应的包装器对象。当然，并不是Python中的所有对象都必须是散列的，但是那些不属于散列的对象相对较少，要制作一个能够处理这些对象的数据结构还需要大量的工作。在

Answer 2

更像Python的方法是避免单调乏味的物体，如果你不需要的话。在

class UnionFind(object):
    def __init__(self, members=10, data=None):
        """union-find data structure for Kruskal's algorithm
        members are ignored if data is provided
        """
        if not data:
            self.data = [self.default_data() for i in range(members)]
            for d in self.data:
                d.size   = 1
                d.leader = d
                d.next   = None
                d.last   = d
        else:
            self.data = data

    def default_data(self):
        """create a starting point for data"""
        return Data(**{'last': None, 'leader':None, 'next': None, 'size': 1})

    def find(self, element):
        return element.leader

    def union(self, leader1, leader2):
        if leader2.leader is leader1:
            return
        if leader1.size >= leader2.size:
            newleader = leader1
            oldleader = leader2
        else:
            newleader = leader2
            oldleader = leader1

        newleader.size = leader1.size + leader2.size

        d = oldleader
        while d is not None:
            d.leader = newleader
            d = d.next

        newleader.last.next = oldleader
        newleader.last = oldleader.last

        oldleader.size = 0
        oldleader.last = None

class Data(object):
    def __init__(self, **data_dict):
        """convert a data member dict into an object"""
        self.__dict__.update(**data_dict)

Answer 3

一种选择是使用字典来存储所需的有关数据项的信息，而不是直接存储该项上的属性。例如，您可以引用d.size，而不是引用size[d]（其中size是dict实例）。这要求您的数据项是可散列的，但不需要允许对它们分配属性。在

下面是使用此样式的当前代码的直接翻译：

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]

最小测试用例：

^{pr2}$

除此之外，您还可以考虑稍微更改一下您的实现，以减少初始化的需要。这是一个不做任何初始化的版本（它甚至不需要知道要处理的数据集）。它使用路径压缩和按等级联合，而不是始终为一个集合的所有成员维护一个最新的leader值。它应该比您当前的代码快得多，尤其是当您正在进行大量联合时：

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