Убедитесь, что список питонов соответствует определенной повторяющейся схеме

Question

У меня есть список Python, который содержит только два символа, скажем, они a и b, и список выглядит так:

l = ['a','b','a','b','a','b','a','b','a','b','a','b','a','b','a','b']

Теперь в моем приложении у меня есть тысячииз этих списков, и они различаются по длине (обычно несколько сотен).Но их объединяет то, что у них повторяющийся паттерн (a,b).Этот список, например, не работает:

l_broken = ['a','b','b','a','a','b','a','b','a','a','a','b','a','b','b','a']

Все, что отличается от повторяющегося шаблона a,b в l, должно считаться неработающим.Даже если список не имеет четной длины, он не работает.Так что это должно быть очень строгим тестом.Но по существу, если список l имеет длину N, то это означает, что (a,b) должен повторяться N/2 раз.Символы a и b являются единственными вещами, которые когда-либо будут появляться в этих списках, поэтому проверка этого не требуется, поскольку в этом приложении это невозможно представить, чтобы было видно что-либо еще.

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

assert my_fancy_test(l), 'the list does not follow the correct pattern'

Я думаю, что я ищу соответствие подпоследовательности, но мои поиски в Google заканчиваются.

РЕДАКТИРОВАТЬ:

Спасибо всем за ваши отличные решения.Я понятия не имел, что вы могли бы сделать даже половину из них.Отличный материал.В конце я добавил краткий обзор производительности, чтобы вы могли его просмотреть.

Answer 1

Вот что вам нужно проверить

Есть ли в вашем списке какие-либо другие символы, и длина вашего списка делится на 2:

assert len(l) == l.count('a') + l.count('b') and len(L) % 2 == 0

И нет повторения символов:

j = ''.join(l)
assert 'aa' not in j and 'bb' not in j

Первый элемент в вашем списке: 'a'

assert 'a' is L[0]

Есливсе они проходят, это должно означать, что у вас есть только два ваших символа, и два последующих символа никогда не совпадают

Answer 2

Производительность

Список испытаний: l = ['a','b']*100000

RomanPerekhrest Решение:

CPU times: user 636 µs, sys: 0 ns, total: 636 µs
Wall time: 639 µs

GZ0 's ответ:

CPU times: user 14.6 ms, sys: 78 µs, total: 14.7 ms
Wall time: 13.9 ms

Silveris 'ответ:

CPU times: user 95.2 ms, sys: 3.95 ms, total: 99.1 ms
Wall time: 98 ms

h4z3 ответ:

CPU times: user 39.9 ms, sys: 0 ns, total: 39.9 ms
Wall time: 38.6 ms

tituszban ответ:

CPU times: user 2.71 ms, sys: 46 µs, total: 2.76 ms
Wall time: 2.76 ms

ruso_ro1 ответ:

CPU times: user 32.4 ms, sys: 3.35 ms, total: 35.8 ms
Wall time: 34.7 ms

Элиас Штреле

CPU times: user 11.7 ms, sys: 0 ns, total: 11.7 ms
Wall time: 12.1 ms

Answer 3

Простая функция тестирования, основанная на умножении списка:

def test_repeating_pattern(lst, pat):
    pat_len = len(pat)
    assert len(lst) % pat_len == 0, 'mismatched length of list'
    assert list(pat) * (len(lst) // pat_len) == lst, 'the list does not follow the correct pattern'
    print(lst, 'is valid')


L = ['a','b','a','b','a','b','a','b','a','b','a','b','a','b','a','b']
L_broken = ['a','b','b','a','a','b','a','b','a','a','a','b','a','b','b','a']

Тестирование:

test_repeating_pattern(L, ('a', 'b'))
['a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b'] is valid

---

test_repeating_pattern(L_broken, ('a', 'b'))
AssertionError: the list does not follow the correct pattern

Answer 4

Один метод может состоять в том, чтобы сначала создать пары:

>>> l = ['a','b','a','b','a','b','a','b','a','b','a','b','a','b','a','b']
>>> pairs = [[l[i], l[i + 1]] for i in range(0, len(l) - 1, 2)]
>>> pairs
[['a', 'b'], ['a', 'b'], ['a', 'b'], ['a', 'b'], ['a', 'b'], ['a', 'b'], ['a', 'b'], ['a', 'b']]

А затем подсчитать вхождения пар ['a', 'b'] в списке пар и сравнить его с половиной размера списка:

>>> pairs.count(['a', 'b']) == len(l) / 2
True

Это будет выглядеть следующим образом:

def my_fancy_test(l):
    pairs = [[l[i], l[i + 1]] for i in range(0, len(l) - 1, 2)]
    return pairs.count(['a', 'b']) == len(l) / 2

PS: Обратите внимание, что в соответствии с PEP8 имена в верхнем регистре должны быть только для констант.

Answer 5

def my_fancy_test(my_list):
    pattern = ['a', 'b']
    if not len(my_list) % len(pattern) == 0:
        return False
    for i in range(0, len(my_list)):
        if not my_list[i] == pattern[i % len(pattern)]:
            return False
    return True

Шаблон может быть любым списком любой длины (универсальное решение).

Проверяет только полный шаблон (например, a, b, a потерпит неудачу), и шаблон должен начинаться с начала (например, b, a, b также не удастся).

L = ['a','b','a','b','a','b','a','b','a','b','a','b','a','b','a','b']
assert my_fancy_test(L) #passes
L2 = ['a','b','a','b','a','b','a','b','a','b','a','b','a','b','a','c']
assert my_fancy_test(L2) #fails

Answer 6

Список правильный , если и только он удовлетворяет следующим четырем требованиям:

• В списке есть хотя бы одна запись
• Последняя запись b
• Каждая запись с четным индексом a
• Каждая запись с нечетным индексом b

def is_correct_entry(idx, v):
    if idx % 2 == 0:
        return v == 'a'
    else:
        return v == 'b'

def my_fancy_test(l):
    return l and l[-1] == 'b' and all(is_correct_entry(idx, v) for idx, v in enumerate(l))

Этот код может иметьпреимущество в скорости, потому что оно не создает новые списки, избегает дорогостоящих len вычислений и не проверяет оставшуюся часть списка, если находит неправильную запись (проверьте all документацию для встроенного *1022*метод).

Answer 7

Другой подход состоит в том, чтобы присоединиться к списку и использовать регулярные выражения для сопоставления с образцом:

import re

def is_broken(input_list, pattern = re.compile("(?:ab)*")):
    return pattern.fullmatch(''.join(input_list)) is None

print(is_broken(['a','b','a','b','a','b','a','b','a','b','a','b','a','b','a','b']))
print(is_broken(['a','b','b','a','a','b','a','b','a','a','a','b','a','b','b','a']))

Вывод:

False
True

Этот подход также можно использовать для сопоставления с некоторыми более сложными образцамиэффективно или извлекать информацию при сопоставлении шаблонов.

Answer 8

вы можете использовать:

pattern = ['a', 'b']

p_len = len(pattern)
assert all(pattern == L[i: i + p_len] for i in range(0, len(L), p_len))

вы берете кусок за кусок размера шаблона и проверяете его по шаблону

, например:

pattern = ['a', 'b']

p_len = len(pattern)
l_broken = ['a','b','b','a','a','b','a','b','a','a','a','b','a','b','b','a']
all(pattern == l_broken[i: i+p_len] for i in range(0, len(l_broken), p_len))

вывод:

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-160-edf435d855b9> in <module>
      1 p_len = len(pattern)
      2 l_broken = ['a','b','b','a','a','b','a','b','a','a','a','b','a','b','b','a']
----> 3 assert all(pattern == l_broken[i: i+p_len] for i in range(0, len(l_broken), p_len))

AssertionError: