Python でより大きなリスト内のサブリストの存在を効率的に判断するにはどうすればよいでしょうか?

Python でのリストのサブリストの存在の検索

大きなリスト内のサブリストの存在を識別することは、一般的なプログラミング タスクです。 Python は、カスタム関数を使用して、この問題に対する簡単な解決策を提供します。

問題の定式化:

2 つのリスト list1 と list2 が与えられた場合、list2 の要素が次のように存在するかどうかを判断します。 list1 内の連続したシーケンス。次のテスト ケースを考えてみましょう:

<code class="python">list1 = [1,0,1,1,1,0,0]
list2 = [1,0,1,0,1,0,1]

# Should return True
sublistExists(list1, [1,1,1])

# Should return False
sublistExists(list2, [1,1,1])</code>

実装:

Python の関数プログラミング機能により、any() 関数とリスト内包表記を使用した簡潔な解決策が可能になります:

<code class="python">def contains_sublist(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in range(len(lst)-n+1))</code>

この関数は、lst (メイン リスト) と sublst (検索されるサブリスト) の 2 つの引数を取ります。 sublst の長さを計算し、リスト内包表記を使用して lst 内のインデックス範囲のシーケンスを生成します。範囲ごとに、sublst を lst 内の対応する要素と比較します。一致するものが見つかった場合、any() は True を返します。それ以外の場合は、False を返します。

使用例:

提供されたテスト ケースでは、sublistExists(list1, [1,1,1]) は True と sublistExists( list2, [1,1,1]) は、予想どおり False を返します。

注:

any() 関数は、最初の一致で終了することで検索を最適化します。 。この関数の時間計算量は O(m*n) です。ここで、m は lst の長さ、n は sublst の長さです。

以上がPython でより大きなリスト内のサブリストの存在を効率的に判断するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。