Элегантный список подписок в списке

Учитывая список, содержащий известный шаблон, окруженный шумом, есть элегантный способ получить все элементы, которые соответствуют шаблону. Ниже приведен мой код.

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]

Списки содержат именованные кортежи.

Ответы

Ответ 1

Я знаю, что этот вопрос уже 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

Это вариант "неэффективного одного лайнера" Стивена Румбальского, который с добавлением "mylist [i] == pattern [0]" проверяет и благодаря оценке короткого замыкания на питоне значительно быстрее, чем оба исходное утверждение и версию itertools (и любое другое предлагаемое решение, насколько я могу судить), и даже поддерживает перекрывающиеся шаблоны. Итак, вы идете.

Ответ 2

Это получит "бонусную" часть вашего вопроса:

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

Ответ 3

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)

Ответ 4

Дано:

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