Python でのリストの重複のテスト

はじめに

Python では、あるリストの要素が別のリストに存在するかどうかを判断することは、さまざまなデータ操作タスクに不可欠です。この記事では、この重複をテストし、その効率を評価し、ベスト プラクティスを提供するためのさまざまな方法について説明します。

アプローチ

1. Generator Expression

any(i in a for i in b)

このメソッドは、1 つのリストを反復処理し、もう 1 つのリストのメンバーシップをチェックし、一致する場合は True を返します。見つかった。その時間計算量は O(n) です。ここで、n は大きい方のリストの長さです。

2。 Set Intersection

bool(set(a) & set(b))

このアプローチでは、両方のリストをセットに変換し、それらの交差を見つけます。交差部分が空でない場合は、True を返します。この場合の最悪の場合の時間計算量は O(n m) です。ここで、n と m はリストの長さです。

3。ハイブリッド セット交差

a = set(a)
any(i in a for i in b)

このメソッドは、1 つのリストのみをセットに変換し、他のリストを反復処理して、セットのメンバーシップを確認します。これにより、中間セットの作成が回避され、従来のセット交差よりも高速になります。

4. Isdisjoint メソッド

not set(a).isdisjoint(b)

このアプローチでは、フリーズ セットの isdisjoint メソッドを使用して、それらに共通の要素があるかどうかを判断します。そうでない場合、結果は False になります。それ以外の場合は True です。

効率の比較

ワーストケース:

• ジェネレータ式: O(n)
• セット交差: O(n m)
• ハイブリッド セット交差: O(n m)
• Isdisjoint メソッド: O(1)

ほとんどの場合、定数時間のセット メンバーシップ チェックの恩恵を受けるため、isdisjoint メソッドが最も高速です。

ジェネレーター式の最適なケース:

• リストの最初のいくつかの要素が重複する場合。この場合、ジェネレータ式はすぐに True を返すことができます。

考慮すべき要素:

• リスト サイズ
• 分布リスト内の要素
• 共有要素の頻度

最高実践

• 小さなリスト (
• リストの構造が予測可能な場合 (ソートなど)、ジェネレーター式の方が高速になる可能性があります。
• リスト間のサイズに大きな違いがある場合は、小さい方のリストを最初として isdisjoint メソッドを使用します。 argument.
• 共有要素がほとんどまたはまったくないリストの場合、一般に isdisjoint メソッドの方が効率的です。