オブジェクトの順序なしリストを効率的に比較するにはどうすればよいですか?

順序なしリストの効率的な比較

バッグとも呼ばれる順序なしリストの比較は、特に整数などの単純なデータ型ではなくオブジェクトを扱う場合には、困難な作業になる可能性があります。 。この問題に取り組むための 3 つの効率的なアプローチを次に示します。

1. Counter メソッド (O(n))

ハッシュ可能な (つまり、一意のハッシュ値に変換できる) オブジェクトの場合、Python のコレクション モジュールの Counter() メソッドを使用できます。これは、キーがリストの要素であり、値がそれぞれの数である辞書のようなオブジェクトを作成します。このアプローチを使用して 2 つのリストを比較すると、線形時間計算量は O(n) になります。ここで、n はリストの長さです。

import collections

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

2。 Sorted Method (O(n log n))

リスト内のオブジェクトが比較可能な場合 (つまり、順序が定義されている場合)、リストをソートすることで効率的な比較メカニズムを提供できます。 Python のsorted() メソッドはリスト内の要素を並べ替えるため、2 つのリストに同じ要素が任意の順序で含まれているかどうかを簡単に判断できます。このアプローチの時間計算量は O(n log n) です。ここで、n はリストの長さです。

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

3。等価比較 (O(n * n))

オブジェクトがハッシュ可能でも順序付け可能でもない場合、簡単なアプローチは 2 つのリストの要素間の等価比較を実行することです。最初のリストの各要素を 2 番目のリストから削除します。最初のリストの要素が 2 番目のリストで見つからない場合、比較は失敗します。このアプローチの最悪の場合の時間計算量は O(n * n) です。ここで、n はリストの長さです。

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

これらの効率的な比較手法を利用することで、オブジェクトの順序なしリストを効果的に比較できます。 、ハッシュ可能であるか、注文可能であるか、あるいはそのどちらでもない。

以上がオブジェクトの順序なしリストを効率的に比較するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。