[PYTHON] Implémenter UnionFind (équivalent) en 10 lignes

** [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) ** est une structure de données qui classe les éléments en groupes qui ne se croisent pas. La méthode de mise en œuvre standard est l'arborescence Union-Find. Je pense que tout le monde le sait déjà.

L'arbre Union-Find a de nombreux exemples d'implémentation dans Qiita, mais je me suis toujours posé la question.

1. C'est difficile à comprendre car il y a un appel récursif à «find ()». Pouvez-vous l'écrire plus clairement et rapidement?
2. N'est-il pas en fait plus rapide d'utiliser le type de collection intégré?

Implémentation en 10 lignes

J'ai donc écrit une courte implémentation en Python en utilisant dict et un ensemble gelé. 10 lignes y compris les blancs.

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

J'ai essayé de comparer

Comparons-le avec l'implémentation de l'arborescence Union-Find. La cible de comparaison est [l'implémentation introduite] dans l'article avec le plus de likes trouvé en recherchant «Union Find Python» dans Qiita. (https://www.kumilog.net/entry/union-find).

** Le résultat est que cette implémentation sur 10 lignes est plus lente **. De plus, il semble que la différence augmente à mesure que le nombre d'éléments augmente. Pardon.

Cependant, même s'il est lent, il est environ deux fois plus lent que l'arborescence Union-Find, il peut donc être utile dans certains cas.

Code de comparaison et résultat d'exécution

code:

import random
import timeit
import sys
import platform


class EasyUnionFind:
    """
Implémentation à l'aide de dict et 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):
    """
Union typique-Implémenté par Find tree.
    https://www.kumilog.net/entry/union-J'ai copié l'exemple d'implémentation find,
Supprimer les fonctions membres inutiles cette fois.groups()Était ajouté.
    """
    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():
    """Testez si les résultats des deux implémentations sont identiques. S'il y a une différence, une AssertionError est envoyée."""
    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():
    """
Sortie du temps requis pour les deux implémentations tout en augmentant le nombre d'éléments.
    """
    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()

** Résultat d'exécution **:

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