How to Efficiently Compare Unordered Lists of Non-Hashable Objects?

Efficiently Comparing Unordered Lists of Non-Hashable Objects

Unordered lists (not sets) pose a challenge when comparing them for equality, as their elements can be in any order. This difficulty becomes more pronounced when dealing with non-hashable objects, such as instances of user-defined classes.

To facilitate such comparisons, various approaches exist with varying time complexities:

O(n)

For hashable objects, Counter provides an optimal solution:

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

O(n log n)

If the objects are orderable, sorted offers a suitable alternative:

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

O(n * n)

When neither hashability nor orderability is available, a straightforward approach using equality can be employed:

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

By choosing the appropriate solution based on the nature of your objects, you can efficiently compare unordered lists, even when the elements are not hashable or orderable.

The above is the detailed content of How to Efficiently Compare Unordered Lists of Non-Hashable Objects?. For more information, please follow other related articles on the PHP Chinese website!