[PYTHON] Implementieren Sie UnionFind (gleichwertig) in 10 Zeilen

** [Union-Find](https://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87 % E3% 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0) ** ist eine Datenstruktur, die Elemente in Gruppen klassifiziert, die sich nicht überschneiden. Die Standardimplementierungsmethode ist der Union-Find-Baum. Ich denke, das weiß schon jeder.

Der Union-Find-Baum enthält viele Implementierungsbeispiele in Qiita, aber ich habe mich immer gefragt.

1. Es ist schwer zu verstehen, da es einen rekursiven Aufruf von "find ()" gibt. Können Sie es klarer und in Kürze schreiben?
2. Ist es nicht tatsächlich schneller, den integrierten Sammlungstyp zu verwenden?

10-zeilige Implementierung

Also habe ich eine kurze Implementierung in Python mit dict und Frozen Set geschrieben. 10 Zeilen inklusive Leerzeichen.

class EasyUnionFind:
    def __init__(self, n):
        self._groups = {x: frozenset([x]) for x in range(n)}

    def union(self, x, y):
        group = self._groups[x] | self._groups[y]
        self._groups.update((c, group) for c in group)

    def groups(self):
        return frozenset(self._groups.values())

Ich habe versucht zu vergleichen

Vergleichen wir es mit der Implementierung des Union-Find-Baums. Suchen Sie zum Vergleich auf Qiita nach "Union Find Python" und finden Sie den Artikel mit den meisten Likes Implementierung eingeführt.

** Das Ergebnis ist, dass diese 10-Zeilen-Implementierung langsamer ist **. Es scheint auch, dass der Unterschied mit zunehmender Anzahl von Elementen zunimmt. Es tut uns leid.

Selbst wenn es langsam ist, ist es ungefähr doppelt so langsam wie der Union-Find-Baum, so dass es in einigen Fällen nützlich sein kann.

Vergleichscode und Ausführungsergebnis

Code:

import random
import timeit
import sys
import platform


class EasyUnionFind:
    """
Implementierung mit dict und frozenset.
    """
    def __init__(self, n):
        self._groups = {x: frozenset([x]) for x in range(n)}

    def union(self, x, y):
        group = self._groups[x] | self._groups[y]
        self._groups.update((c, group) for c in group)

    def groups(self):
        return frozenset(self._groups.values())


class UnionFind(object):
    """
Typische Union-Implementiert von Find tree.
    https://www.kumilog.net/entry/union-Ich habe das Beispiel der Find-Implementierung kopiert.
Löschen Sie diesmal unnötige Elementfunktionen.groups()Wurde hinzugefügt.
    """
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
        self.n = n

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def groups(self):
        groups = {}
        for i in range(self.n):
            groups.setdefault(self.find(i), []).append(i)
        return frozenset(frozenset(group) for group in groups.values())


def test1():
    """Testen Sie, ob die Ergebnisse der beiden Implementierungen identisch sind. Wenn es einen Unterschied gibt, wird ein AssertionError gesendet."""
    print("===== TEST1 =====")
    random.seed(20200228)
    n = 2000
    for _ in range(1000):
        elements = range(n)
        pairs = [
            (random.choice(elements), random.choice(elements))
            for _ in range(n // 2)
        ]
        uf1 = UnionFind(n)
        uf2 = EasyUnionFind(n)
        for x, y in pairs:
            uf1.union(x, y)
            uf2.union(x, y)
        assert uf1.groups() == uf2.groups()
    print('ok')
    print()


def test2():
    """
Geben Sie die für die beiden Implementierungen erforderliche Zeit aus und erhöhen Sie gleichzeitig die Anzahl der Elemente.
    """
    print("===== TEST2 =====")
    random.seed(20200228)

    def execute_union_find(klass, n, test_datum):
        for pairs in test_datum:
            uf = klass(n)
            for x, y in pairs:
                uf.union(x, y)

    timeit_number = 1
    for n in [1000, 2000, 4000, 8000]:
        print(f"n={n}")
        test_datum = []
        for _ in range(1000):
            elements = range(n)
            pairs = [
                (random.choice(elements), random.choice(elements))
                for _ in range(n // 2)
            ]
            test_datum.append(pairs)

        t = timeit.timeit(lambda: execute_union_find(UnionFind, n, test_datum), number=timeit_number)
        print("UnionFind", t)

        t = timeit.timeit(lambda: execute_union_find(EasyUnionFind, n, test_datum), number=timeit_number)
        print("EasyUnionFind", t)
        print()

def main():
    print(sys.version)
    print(platform.platform())
    print()
    test1()
    test2()

if __name__ == "__main__":
    main()

** Ausführungsergebnis **:

3.7.6 (default, Dec 30 2019, 19:38:28)
[Clang 11.0.0 (clang-1100.0.33.16)]
Darwin-18.7.0-x86_64-i386-64bit

===== TEST1 =====
ok

===== TEST2 =====
n=1000
UnionFind 0.7220867589999997
EasyUnionFind 1.1789850389999987

n=2000
UnionFind 1.460918638999999
EasyUnionFind 2.4546459260000013

n=4000
UnionFind 2.925022847000001
EasyUnionFind 5.142797402000003

n=8000
UnionFind 6.01257184
EasyUnionFind 10.963117657000005