4

Python を使用する前の私のプログラミングのほとんどは、C++ または Matlab で行われていました。私は CS の学位を持っていません (物理学の博士号をほぼ取得しています) が、いくつかのコースを受講し、実際のプログラミングをかなり行っています。今、私は Coursera でアルゴリズムのコースを受講しています (ちなみに、スタンフォード大学の教授による優れたコースです)。宿題を Python で実装することにしました。しかし、言語がそれほど簡単にサポートしていないものが欲しくなることがあります。私は、データをグループ化するためだけに 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)
4

5 に答える 5

2

一般的に言って、この種のことをPythonで行うということは、コードに何が与えられているかを気にしないようにすることを意味します。少なくとも、実際に必要な以上のことはしません。

union-findアルゴリズムの特定の例を見てみましょう。union-findアルゴリズムが実際に渡す値に対して行うのは、それらが等しいかどうかを比較することだけです。したがって、一般的に有用なUnionFindクラスを作成するために、コードは、等価性テスト以外の動作をするために受け取る値に依存するべきではありません。特に、値に任意の属性を割り当てることができることに依存するべきではありません。

これを回避する方法としてUnionFind、アルゴリズムを機能させるために必要な特定の値と属性を保持するラッパーオブジェクトを使用することをお勧めします。namedtuple別の回答で提案されているように使用することも、小さなラッパークラスを作成することもできます。要素がに追加されるとUnionFind、最初にこれらのオブジェクトの1つでラップし、ラッパーオブジェクトを使用して属性などを格納しますleader。sizeラップされているものにアクセスするのは、それが別の値と等しいかどうかを確認する場合のみです。 。

実際には、少なくともこの場合は、値がハッシュ可能であると想定して安全である必要があります。これにより、Pythonディクショナリのキーとして使用して、特定の値に対応するラッパーオブジェクトを見つけることができます。もちろん、Pythonのすべてのオブジェクトが必ずしもハッシュ可能であるとは限りませんが、そうでないオブジェクトは比較的まれであり、それらを処理できるデータ構造を作成するには、さらに多くの作業が必要になります。

于 2012-12-22T02:28:28.917 に答える
0

1 つのオプションは、項目の属性を直接ではなく、辞書を使用してデータ項目に関して必要な情報を格納することです。たとえば、参照するのではなく、参照する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 に答える
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 に答える
-2

ここでのインデントの問題は、コードを SO に入力する際の単なるエラーだと思います。単純な組み込みデータ型のサブクラスを作成できますか? たとえば、リスト データ型のサブクラスを作成するには、データ型を括弧で囲みます。

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