Элегантный список подписок в списке
Учитывая список, содержащий известный шаблон, окруженный шумом, есть элегантный способ получить все элементы, которые соответствуют шаблону. Ниже приведен мой код.
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