Есть ли более быстрый способ найти повторяющиеся шаблоны в списке?

Question

Python новичок здесь. У меня есть проблема, в которой я хочу найти все повторяющиеся шаблоны в списке (это, в моем случае, список целых чисел). Так, например, с учетом списка [2,1,4,3,12,8,3,3,4,16,2,9,9,8,3,3,4,1,4,3,4 , 8,3,3,4] и минимальной длиной паттерна 3 алгоритм найдет, что [8,3,3,4] встречается трижды, а [1,4,3] встречается дважды (также неплохо иметь индекс все случаи).

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

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

Вот код:

# Searches list to determine how many times small list is included in big list
def contains(small, big):
    counter = 0
    # initiating list of indexes. N.B. indexlist gives LAST index of sequence, not first
    indexlist = []
    for i in range(len(big)-len(small)+1):
        for j in range(len(small)):
            if big[i+j] != small[j]:
                break
        else:
            counter += 1
            indexlist.append(i+j)
    if counter > 0:
        return counter, indexlist
    return False

def findrepeats(sequence, n_letters):
    fulldict = {}
    # Iterating through all the short-sequences of n letters in the list
    for i in range(0, len(sequence) - n_letters):
        shortliststr = ""
        shortlist = sequence[i:i + n_letters]
        for number in shortlist:
            shortliststr = shortliststr + "." + str(number)
        # If short-sequence is found in full sequence more than once (i.e. itself), add to dict
        if contains(shortlist, sequence)[0] > 1 and len(shortlist) == n_letters:
            fulldict[shortliststr] = contains(shortlist, sequence)
    return fulldict

def findallrepeats(sequence, min_letters, max_letters):
    fulldict = {}
    # Iterating through all possible n_letters in findrepeats() between given range
    for i in range(min_letters, max_letters):
        newdict = findrepeats(sequence, i)
        fulldict.update(newdict)
    return fulldict

Answer 1

С перекрытием

Вы можете использовать скользящее окно размером n = 3, которое повторяет вашу последовательность и подсчитывает количество вхождений этого окна.

Использование more_itertools.

Например:

import collections
import more_itertools

sequence = [
    2, 1, 4, 3, 12, 8, 3, 3, 4, 16, 2, 9, 9,
    8, 3, 3, 4, 1, 4, 3, 4, 8, 3, 3, 4,
]
size = 3
windows = [
    tuple(window)
    for window in more_itertools.windowed(sequence, size)
]
counter = collections.Counter(windows)
for window, count in counter.items():
    if count > 1:
        print(window, count)

Вы получаете:

(1, 4, 3) 2
(8, 3, 3) 3
(3, 3, 4) 3