Хороший стиль в объектах Python

Ответ 1

Вообще говоря, такое поведение Python означает, что вы пытаетесь заставить свой код не заботиться о том, что ему дано, по крайней мере, не больше, чем это действительно нужно.

Возьмем ваш конкретный пример алгоритма объединения-поиска. Единственное, что алгоритм объединения-находки на самом деле делает со значениями, которые вы передаете ему, сравнивает их для равенства. Поэтому, чтобы сделать обычно полезный класс UnionFind, ваш код не должен полагаться на значения, которые он получает, имея какое-либо поведение, отличное от проверки равенства. В частности, вы не должны полагаться на возможность присвоить произвольные атрибуты значениям.

То, как я предлагаю обойти это, состоит в том, чтобы UnionFind использовать объекты-оболочки, которые содержат заданные значения и любые атрибуты, необходимые для работы алгоритма. Вы можете использовать namedtuple, как было предложено другим ответом, или создать небольшой класс-оболочку. Когда элемент добавляется в UnionFind, вы сначала переносите его в один из этих объектов и используете объект-обертку для хранения атрибутов leader, size и т.д. Единственный раз, когда вы получаете доступ к обернутой вещи, - это чтобы проверить, равно ли оно другому значению.

На практике, по крайней мере в этом случае, должно быть безопасно предположить, что ваши значения хешируются, поэтому вы можете использовать их в качестве ключей в словаре Python, чтобы найти объект-оболочку, соответствующий заданному значению. Конечно, не все объекты в Python обязательно хешируются, но те, которые не являются относительно редкими, и будет намного больше работать, чтобы создать структуру данных, способную обрабатывать их.

Ответ 2

Чем больше pythonic, тем лучше избегать утомительных объектов, если вам это не нужно.

class UnionFind(object):
    def __init__(self, members=10, data=None):
        """union-find data structure for Kruskal 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)

Ответ 3

Чтобы проверить, соответствует ли аргумент ожидаемому типу, используйте встроенную функцию isinstance():

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

Кроме того, хорошая привычка добавлять docstrings функции, классы и функции-члены. Такая docstring для функции или метода должна описывать, что она делает, какие аргументы должны быть переданы ей и, если применимо, то, что возвращается, и какие исключения могут быть подняты.

Ответ 4

Один из вариантов - использовать словари для хранения необходимой информации о элементе данных, а не атрибуты на элементе напрямую. Например, вместо обращения к 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]

Минимальный тестовый пример:

>>> 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

Ответ 5

Я предполагаю, что здесь проблемы с отступом - это просто ошибки при вводе кода в SO. Не могли бы вы создать подкласс простого, встроенного типа данных? Например, вы можете создать подкласс класса данных списка, поставив его в круглые скобки:

class UnionFind(list):
'''extends list object'''