3

Python で MultiGraph のエッジ リストを実装しようとしています。

私がこれまでに試したこと：

>>> l1 = Counter({(1, 2): 2, (1, 3): 1})
>>> l2 = [(1, 2), (1, 2), (1, 3)]

l12 つの頂点間のすべてのエッジを一定時間で削除しますが (例: del l1[(1, 2)])、それらのエッジでは線形時間でランダムに選択します (例: random.choice(list(l1.elements())))。elements（l1それ自体に対して）選択を行う必要があることに注意してください。

l2一定時間のランダム選択 ( random.choice(l2)) がありますが、指定されたエッジに等しいすべての要素の線形時間削除 ( [i for i in l2 if i != (1, 2)]) があります。

質問: 一定時間のランダム選択と削除の両方を可能にする Python データ構造はありますか?

4

1 に答える 1

2

あなたがやろうとしていることは、理論的には達成できないと思います。

重複を表すために加重値を使用している場合、一定時間のランダム選択を取得できません。あなたができる最善のことは、対数である加重インデックスで要素をバイナリ検索できるある種のスキップリストタイプの構造です。

重複を表すために加重値を使用していない場合は、複数のコピーを保存できる構造が必要です。また、ハッシュ テーブルでは対応できません。dup は独立したオブジェクト (たとえば、(edge, autoincrement)) である必要があります。つまり、特定の基準に一致するものを一定時間内にすべて削除する方法はありません。

対数時間を受け入れることができる場合、当然の選択はツリーです。たとえば、次を使用しblistます。

>>> l3 = blist.sortedlist(l2)

ランダムに 1 つを選択するには:

>>> edge = random.choice(l3)

ドキュメントは、これが何か O(n) を行わないことを保証していないようです。しかし幸いなことに、3.3と2.7の両方のソースは、それが正しいことをすることを示しています。あなたがそれを信用しないなら、ただ書いてl3[random.randrange(len(l3))]ください。

エッジのすべてのコピーを削除するには、次のようにします。

>>> del l3[l3.bisect_left(edge):l3.bisect_right(edge)]

または：

>>> try:
...     while True:
...         l3.remove(edge)
... except ValueError:
...     pass

ドキュメントには、関連するすべての操作の正確なパフォーマンス保証が説明されています。特にlenは定数ですが、インデックス付け、スライス、インデックスまたはスライスによる削除、二分、および値による削除はすべて対数であるため、どちらの操作も対数になります。

(これblistは B+Tree であることに注意してください。赤黒木やトレプなどからパフォーマンスが向上する可能性があります。PyPI では、ほとんどのデータ構造の適切な実装を見つけることができます。)

sentle が指摘したように、エッジの最大コピー数がコレクションのサイズよりもはるかに小さい場合、最大コピー数の二次関数で時間内にそれを行うデータ構造を作成できます。彼の提案をコードに変換する:

class MGraph(object):
    def __init__(self):
        self.edgelist = []
        self.edgedict = defaultdict(list)
    def add(self, edge):
        self.edgedict[edge].append(len(self.edgelist))
        self.edgelist.append(edge)
    def remove(self, edge):
        for index in self.edgedict.get(edge, []):
            maxedge = len(self.edgelist) - 1
            lastedge = self.edgelist[maxedge]
            self.edgelist[index], self.edgelist[maxedge] = self.edgelist[maxedge], self.edgelist[index]
            self.edgedict[lastedge] = [i if i != maxedge else index for i in self.edgedict[lastedge]]
            del self.edgelist[-1]
        del self.edgedict[edge]
    def choice(self):
        return random.choice(self.edgelist)

(もちろん、replace-list-with-list-comprehension 行を 3 行の find-and-update-in-place に変更することもできますが、それでも重複の数は線形です。)

明らかに、これを実際に使用する場合は、クラスを少し強化することをお勧めします。いくつかのメソッドを実装し、残りを適切な/で埋めることにより、エッジの 、各エッジの複数のコピーの のlist、などのように見せることができます。settupleCountercollections.abc.Foocollections.Foo

それで、どれが良いですか？サンプルの場合、平均重複カウントはリストのサイズの半分であり、最大値はサイズの 2/3 です。log Nそれが実際のデータに当てはまる場合、明らかに吹き飛ばされるため、ツリーははるかに優れてい(N/2)**2ます。一方、dup がめったにない場合は、senderle のソリューションの方が明らかに優れていW**2ますW。

もちろん、3 要素のサンプルの場合、一定のオーバーヘッドと乗数がすべてを支配します。しかし、おそらくあなたの本当のコレクションはそれほど小さくありません。（そうであれば、list...を使用してください）

実際のデータを特徴付ける方法がわからない場合は、両方の実装を作成し、さまざまな現実的な入力で時間を計ってください。

于 2013-02-18T22:15:00.663 に答える