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

Comparaison efficace de listes non ordonnées

Comparer des listes non ordonnées, également appelées sacs, peut être une tâche difficile, en particulier lorsque vous travaillez avec des objets au lieu de types de données simples comme des entiers. . Voici trois approches efficaces pour résoudre ce problème :

1. Méthode Counter (O(n))

Pour les objets pouvant être hachés (c'est-à-dire pouvant être convertis en une valeur de hachage unique), la méthode Counter() du module collections de Python peut être utilisée. Il crée un objet de type dictionnaire où les clés sont les éléments de la liste et les valeurs sont leurs comptes respectifs. La comparaison de deux listes à l'aide de cette approche a une complexité temporelle linéaire de O(n), où n est la longueur des listes.

import collections

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

2. Méthode triée (O(n log n))

Si les objets de la liste sont comparables (c'est-à-dire qu'ils ont un ordre défini), le tri des listes peut fournir un mécanisme de comparaison efficace. La méthode sorted() en Python trie les éléments de la liste, ce qui permet de déterminer facilement si les deux listes contiennent les mêmes éléments dans n'importe quel ordre. Cette approche a une complexité temporelle de O(n log n), où n est la longueur des listes.

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

3. Comparaison d'égalité (O(n * n))

Si les objets ne sont ni hachables ni commandables, une approche simple consiste à effectuer des comparaisons d'égalité entre les éléments des deux listes. Pour chaque élément de la première liste, nous le supprimons de la deuxième liste. Si un élément de la première liste n'est pas trouvé dans la deuxième liste, la comparaison échoue. Cette approche a une complexité temporelle dans le pire des cas de O(n * n), où n est la longueur des listes.

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 utilisant ces techniques de comparaison efficaces, vous pouvez comparer efficacement des listes d'objets non ordonnées. , qu'ils soient hachables, commandables ou ni l'un ni l'autre.

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!