36

ノイズに囲まれた既知のパターンを含むリストが与えられた場合、そのパターンに等しいすべてのアイテムを取得するエレガントな方法はありますか? 私の粗いコードについては以下を参照してください。

list_with_noise = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
known_pattern = [1,2,3,4]
res = []


for i in list_with_noise:
    for j in known_pattern:
        if i == j:
            res.append(i)
            continue

print res

私たちは得るだろう2, 1, 2, 3, 4, 2, 1, 2, 3, 4, 1, 2, 3, 4, 4, 3

ボーナス: 完全なパターンが存在しない場合は i を追加しないでください (つまり、1,2,3,4 は許可しますが、1,2,3 は許可しません)。

例:

find_sublists_in_list([7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5],[1,2,3,4])

[1,2,3,4],[1,2,3,4],[1,2,3,4]


find_sublists_in_list([7,2,1,2,3,2,1,2,3,6,9,9,1,2,3,4,7,4,3,1,2,6],[1,2,3,4])

[1,2,3],[1,2,3],[1,2,3]

リストには名前付きタプルが含まれています。

4

7 に答える 7

51

この質問は5か月前のもので、すでに「受け入れられている」ことは知っていますが、非常によく似た問題をグーグルで検索すると、この質問にたどり着きました。すべての回答には、いくつかのかなり重大な問題があるようです。さらに、退屈で、自分の手を試してみたいと思いますSOの答えなので、見つけたものをガタガタ鳴らすだけです。

私が理解しているように、質問の最初の部分は非常に簡単です。「パターン」に含まれていないすべての要素を除外して元のリストを返すだけです。その考えに従って、最初に思いついたコードは filter() 関数を使用していました。

def subfinder(mylist, pattern):
    return list(filter(lambda x: x in pattern, mylist))

この解決策は元の解決策よりも間違いなく簡潔だと思いますが、それほど高速ではなく、少なくとも目に見えるほどではありません。使用する正当な理由がない場合は、ラムダ式を使用しないようにしています。実際、私が思いついた最善の解決策は、単純なリスト内包表記でした。

def subfinder(mylist, pattern):
    pattern = set(pattern)
    return [x for x in mylist if x in pattern]

このソリューションは、オリジナルよりも洗練されており、大幅に高速です。理解はオリジナルよりも約 120% 高速ですが、パターンをセットの最初のバンプにキャストすると、私のテストではなんと 320% も速くなります。

おまけとして、すぐに始めましょう。私の解決策は次のとおりです。

def subfinder(mylist, pattern):
    matches = []
    for i in range(len(mylist)):
        if mylist[i] == pattern[0] and mylist[i:i+len(pattern)] == pattern:
            matches.append(pattern)
    return matches

これは、Steven Rumbalski の「非効率的なワンライナー」のバリエーションであり、「mylist[i] == pattern[0]」チェックの追加と、python の短絡評価のおかげで、元の両方のステートメントよりも大幅に高速です。および itertools バージョン (および私が知る限り、他のすべての提供されたソリューション)であり、重複するパターンもサポートしています。では、どうぞ。

于 2012-09-25T05:37:35.710 に答える
5

これにより、質問の「ボーナス」部分が得られます。

pattern = [1, 2, 3, 4]
search_list = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
cursor = 0
found = []
for i in search_list:
    if i == pattern[cursor]:
        cursor += 1
        if cursor == len(pattern):
            found.append(pattern)
            cursor = 0
    else:
        cursor = 0

非ボーナスの場合:

pattern = [1, 2, 3, 4]
search_list = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
cursor = 0
found = []
for i in search_list:
    if i != pattern[cursor]:
        if cursor > 0:
            found.append(pattern[:cursor])
        cursor = 0
    else:
        cursor += 1

最後に、これはオーバーラップを処理します。

def find_matches(pattern_list, search_list):
    cursor_list = []
    found = []
    for element in search_list:
        cursors_to_kill = []
        for cursor_index in range(len(cursor_list)):
            if element == pattern_list[cursor_list[cursor_index]]:
                cursor_list[cursor_index] += 1
                if cursor_list[cursor_index] == len(pattern_list):
                    found.append(pattern_list)
                    cursors_to_kill.append(cursor_index)
            else:
                cursors_to_kill.append(cursor_index)
        cursors_to_kill.reverse()
        for cursor_index in cursors_to_kill:
            cursor_list.pop(cursor_index)
        if element == pattern_list[0]:
            cursor_list.append(1)
    return found
于 2012-04-11T13:36:17.190 に答える
1 
list_with_noise = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
string_withNoise = "".join(str(i) for i in list_with_noise)
known_pattern = [1,2,3,4]
string_pattern = "".join(str(i) for i in known_pattern)
string_withNoise.count(string_pattern)
于 2012-04-11T13:37:16.147 に答える
0

与えられた:

a_list = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
pat = [1,2,3,4]

非効率的なワンライナーを次に示します。

res = [pat for i in range(len(a_list)) if a_list[i:i+len(pat)] == pat]

より効率的な itertools バージョンを次に示します。

from itertools import izip_longest, islice

res = []
i = 0  

while True:
    try:
        i = a_list.index(pat[0], i)
    except ValueError:
        break
    if all(a==b for (a,b) in izip_longest(pat, islice(a_list, i, i+len(pat)))):
        res.append(pat)
        i += len(pat)
    i += 1
于 2012-04-11T14:25:03.570 に答える