4

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

下面是我对联合查找数据结构的实现（用于 Kruskal 算法）。尽管实现相对较短且运行良好（没有太多错误检查），但还是有一些奇怪的地方。例如，我的代码假定最初传递给 union-find 的数据是一个对象列表。但是，如果传入的是显式数据片段列表（即整数列表），则代码将失败。有没有更清晰、更 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)
4

5 回答 5

2

一般来说，以 Python 方式做这种事情意味着你试图让你的代码不在乎给它什么，至少不超过它真正需要的。

让我们以联合查找算法为例。union-find 算法实际上对传递给它的值所做的唯一一件事就是比较它们是否相等。因此，要创建一个普遍有用的UnionFind类，您的代码不应依赖于它接收到的具有除相等性测试之外的任何行为的值。特别是，您不应该依赖能够为值分配任意属性。

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

实际上，至少在这种情况下，假设您的值是可散列的应该是安全的，这样您就可以将它们用作 Python 字典中的键来查找与给定值对应的包装器对象。当然，并非 Python 中的所有对象都必须是可散列的，但那些不是相对罕见的对象，并且要制作能够处理这些对象的数据结构将需要做更多的工作。

于 2012-12-22T02:28:28.917 回答
0

更 Pythonic 的方法是避免不必要的乏味对象。

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)
于 2012-12-22T01:12:32.923 回答
0

要检查参数是否为预期类型，请使用内置isinstance()函数：

if not isinstance(leader1, UnionFind):
    raise ValueError('leader1 must be a UnionFind instance')

此外，将文档字符串添加到函数、类和成员函数中是一个好习惯。函数或方法的此类文档字符串应该描述它的作用、要传递给它的参数以及如果适用，返回什么以及可以引发哪些异常。

于 2012-12-22T01:21:56.303 回答
0

一种选择是使用字典来存储您需要的有关数据项的信息，而不是直接存储该项目的属性。例如，与其指代d.size你，不如指代size[d]（where sizeis a dictinstance）。这要求您的数据项是可散列的，但它们不需要允许对其分配属性。

这是您当前代码的直接翻译以使用此样式：

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]

一个最小的测试用例：

>>> uf = UnionFind(list(range(100)))
>>> uf.find(10)
10
>>> uf.find(20)
20
>>> uf.union(10,20)
>>> uf.find(10)
10
>>> uf.find(20)
10

除此之外，您还可以考虑稍微更改您的实现以减少初始化。这是一个不做任何初始化的版本（它甚至不需要知道它要处理的数据集）。它使用路径压缩和按等级联合，而不是始终为集合的所有成员维护最新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
于 2012-12-22T06:19:42.157 回答
-2

我猜这里的缩进问题只是将代码输入SO的简单错误。您能否创建一个简单的内置数据类型的子类？例如，您可以通过将数据类型放在括号中来创建列表数据类型的子类：

class UnionFind(list):
'''extends list object'''
于 2012-12-22T00:13:24.110 回答