python - リストが他のリスト内にあるかどうかのブール式

Question

リストが別のリスト内にあるかどうかを確認する効率的な方法は何ですか? 何かのようなもの：

[2,3] in [1,2,3,4]      #evaluates True
[1,5,4] in [5,1,5,4]    #evaluates True
[1,2] in [4,3,2,1]      #evaluates False

リスト内の順序が重要です。

Answer 1

def check_ordered_sublist_in_list(sub_list, main_list):
    sub_list = np.array(sub_list)
    main_list = np.array(main_list)
    return any(all(main_list[n:(n + len(sub_list))] == sub_list) 
               for n in range(0, len(main_list) - len(sub_list) + 1))

>>> check_ordered_sublist_in_list([2, 3], [1, 2, 3, 4])
True

>>> check_ordered_sublist_in_list([1, 5, 4], [5, 1, 5, 4])
True

>>> check_ordered_sublist_in_list([1, 2], [4, 3, 2, 1])
False

これにより、リストが (計算効率のために) numpy 配列に変換され、次にスライスを使用してsub_listがスライス内に含まれているかどうかがチェックされます。成功すると True が返されます。

Answer 2

これを使用できます：

def is_in(short, long):
    return any(short==long[i:i+len(short)] for i in range(len(long)-len(short)+1))

is_in([2,3], [1,2,3,4])   # True
is_in([1,5,4], [5,1,5,4]) # True
is_in([1,2], [4,3,2,1])   # False

速度が本当に気になるなら、これらの式は 20 ～ 30% 高速です。

def segments(long, length):
    return [long[i:i+length] for i in range(len(long)-length+1)]

def is_in_seg(short, long):
    return short in segments(long, len(short))

is_in_seg([1,5,4], [5,1,5,4])      # true
[1,5,4] in segments([5,1,5,4], 3)  # true

これは 47% 高速ですが、リストの代わりにタプルを使用します。

import itertools
def segments_zip(long, length):
    return itertools.izip(*[long[i:] for i in xrange(length)])

(2,3) in segments_zip((1,2,3,4), 2)    # True
(1,5,4) in segments_zip((5,1,5,4), 3)  # True
(1,2) in segments_zip((4,3,2,1), 2)    # False

余分な速度は、一致が見つかったときにセグメントの生成を停止できる itertools.izip を使用することで得られます。範囲リスト全体の作成を回避する xrange の使用から。タプルの使用は、一般にリストよりもわずかに高速です。ただし、リストをタプルに変換して使用する必要がある場合、わずかな速度の利点は失われます。