Comment comparer efficacement des listes non ordonnées d’objets non hachables ?

Comparer efficacement des listes non ordonnées d'objets non hachables

Les listes non ordonnées (et non les ensembles) posent un défi lorsqu'on les compare pour l'égalité, car leur les éléments peuvent être dans n’importe quel ordre. Cette difficulté devient plus prononcée lorsqu'il s'agit d'objets non hachables, tels que des instances de classes définies par l'utilisateur.

Pour faciliter de telles comparaisons, diverses approches existent avec des complexités temporelles variables :

O(n)

Pour les objets hachables, Counter fournit un solution :

def compare(s, t):
    return Counter(s) == Counter(t)

O(n log n)

Si les objets sont commandables, triés propose une alternative adaptée :

def compare(s, t):
    return sorted(s) == sorted(t)

O(n*n)

Quand ni l'un ni l'autre la hachage ni la possibilité de commander ne sont disponibles, une approche simple utilisant l'égalité peut être utilisée :

def compare(s, t):
    t = list(t)   # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t

En choisissant la solution appropriée en fonction de la nature de vos objets, vous pouvez comparer efficacement des listes non ordonnées, même lorsque les éléments ne sont pas hachable ou commandable.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!