Упражнение, над которым я работаю, требует, чтобы я прочитал двоичную последовательность, хранящуюся в текстовом файле. Цель состоит в том, чтобы найти вхождения всех подпоследовательностей длины от a до b (их значения указаны в параметрах функции) и поместить их в список кортежей.

Например: если следующая двоичная последовательность задана в качестве входных данных и длина каждой подпоследовательности должна быть от 2 до 4:

a = 2 
b = 4 

01010010010001000111101100001010011001111000010010011110010000000

Я должен написать программу для генерации следующего вывода:

[(1, ["1011", "1101"]), 
 (2, ["0101", "0110", "1010"]), 
 (3, ["0111", "101", "1110", "1111"]), 
 (4, ["0001", "0011", "1100"]), 
 (5, ["011", "1000", "110"]), 
 (6, ["0000", "111"]), 
 (7, ["0010", "1001"]), 
 (8, ["0100"]), 
 (10, ["010"]), 
 (11, ["000", "001", "11"]), 
 (12, ["100"]),            
 (15, ["01", "10"]), 
 (23, ["00"] )]

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

Например, первый кортеж указывает, что подпоследовательности «1011» и «1101» появляются только один раз в данной последовательности.

Написанное мною решение действительно решает проблему (оно проходит все тесты на правильность), но оно медленное и не проходит тесты производительности (оно проходит только 5 из 22 тестов), в которых максимальный тайм-аут установлен на 1 секунду. Как я могу сделать это решение быстрее?

Мне не разрешено импортировать внешний библиотеки.

def ex1(ftesto,a,b,n):
    with open(ftesto,encoding='utf8') as f: 
        S = f.read().replace('n','')
    N = len(S)
    D = {} 
    subsequences = {} 
    for i in range(N+1):
        for j in range(i+1,N+1): 
            if a <= len(S[i:j]) <= b: 
                if S[i:j] not in D:
                    D[S[i:j]] = 1   
                else:
                    D[S[i:j]] += 1                     
    for k,v in D.items(): 
        subsequences.setdefault(v,[]).append(k)
    result = sorted([(k,sorted(v)) for k,v in subsequences.items()])   
    return result[:n] 

if __name__ == '__main__':
    
   ftesto = 'ft1.txt'
   a = 2
   b = 4
   n = 20

Количество элементов в списке должно быть равно или меньше «n». Это объясняет, почему я использую нарезку в конце функции.

PEP 8

Вы нарушаете несколько Руководство по стилю кода Python правила:

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

Никогда не звонил

ex1() никогда не вызывается вашей основной линией.

Объявите переменные ближе к тому месту, где они используются

subsequences объявляется на 7 строк раньше, чем нужно.

Отделить ввод / вывод от обработки

ex1() не может быть вызван с тестовыми данными, если эти тестовые данные не находятся в файле. Используйте две функции. Один решает проблему со строкой в ​​памяти, а второй считывает строку из файла для обработки.

Избегать dict.setdefault(...)

subsequences.setdefault(v, []).append(k) создаст новый список ([]) каждый раз, когда он выполняется. Часто это значение по умолчанию никогда не будет использоваться, и его придется собирать мусором. Это просто трата времени.

Вместо этого используйте collections.defaultdict. Обратите внимание, что collections не является внешней библиотекой; он внутренний, встроенный в Python.

Прилавок

Точно так же используйте collections.Counter для подсчета предметов. Опять же, встроенный в Python; не внешняя библиотека.

Переработанный код

from collections import Counter, defaultdict

def binary_sequence_counts(sequence, shortest, longest, limit):
    n = len(sequence)

    sequence_counter = Counter()
    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            if shortest <= len(sequence[i:j]) <= longest:
                sequence_counter[sequence[i:j]] += 1

    subsequences = defaultdict(list)
    for subsequence, count in sequence_counter.items():
        subsequences[count].append(subsequence)

    result = sorted((count, sorted(subseqs)) for count, subseqs in subsequences.items())
    return result[:limit]

def ex1(ftesto, a, b, n):
    with open(ftesto, encoding='utf8') as f:
        sequence = f.read().replace('n', '')

    return binary_sequence_counts(sequence, a, b, n)

def testcase():
    seq = "01010010010001000111101100001010011001111000010010011110010000000"
    result = binary_sequence_counts(seq, 2, 4, 20)
    # print result, or
    # check if result is correct

Приведенный выше код более читабелен, чем оригинал.

Эффективность

Этот код просто ужасен:

    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            if shortest <= len(sequence[i:j]) <= longest:
                ...

Если ваша последовательность состоит из 100 000 цифр, внутренний цикл будет выполняться примерно 5 000 000 000 раз! Это много! Особенно, если вас интересуют только подпоследовательности длиной от 2 до 4 цифр, и в этом случае вам нужно всего около 300 000 итераций.

Простая модификация range(...) ограничения значительно улучшат вашу скорость. Если сделать это правильно, можно даже избавиться от a <= len(...) <= b test, потому что с правильными диапазонами вы не сможете сгенерировать последовательности неправильной длины.

Фактически, с правильными ограничениями вы даже можете использовать счетчик для подсчета полностью за вас:

sequence_counts = Counter(sequence[i:j]
                          for i in range(...)
                          for j in range(...))

Правильные пределы диапазона оставлены в качестве упражнения для ученика.

мин куча

Вы сортируете потенциально огромный список значений, а затем возвращаете только n-наименьшие результаты. sorted(iterable)[:n] Это может быть огромной тратой времени!

С использованием heapq.nsmallest(n, iterable) (опять же, встроенная, а не внешняя библиотека), вы можете уменьшить объем используемого пространства и, возможно, количество времени. Обратите внимание, что это быстрее только для меньших значений n. Если n большой, его можно использовать быстрее sorted(iterable)[:n]. Всегда в профиль!

Сделай сам

Вопрос был обновлен, чтобы запретить импорт. Без проблем. Нам просто нужно реализовать свои собственные defaultdict и Counter. Предполагая, что вам разрешено создавать свои собственные class …

object.__missing__

Когда dict.__getitem__ вызывается, но словарь не содержит этого ключа, object.__missing__(self, key) называется. Мы можем использовать этот метод, чтобы изменить поведение.

Прилавок

Для реализации простого «счетного» словаря нам просто нужно 0 подлежит возврату за любой недостающий ключ.

class Counter(dict):
    def __missing__(self, key):
        return 0

Если ключ отсутствует, 0 возвращается. Если вы «добавите 1» к отсутствующему ключу, 0 возвращается, 1 добавляется к возвращаемому значению, и результат 1 сохраняется под этим ключом:

>>> c = Counter()
>>> c['foo']
0
>>> c['bar'] += 1
>>> c['bar'] += 1
>>> c
{'bar': 2}

Обратите внимание, что 'foo' ключ все еще не существует; только 'bar' ключ существует, потому что на самом деле в него были записаны значения.

defaultdict

На самом деле вам не нужен полный defaultdict здесь. Вам просто нужен словарь, который возвращает пустой список при получении неизвестного ключа. в отличие от Counter выше, нам нужно запомнить список, который был возвращен для ключа, потому что мы будем добавлять элементы в список, которые (в отличие от += оператор) не будет записывать результат обратно в словарь.

class DictOfLists(dict):
    def __missing__(self, key):
        self[key] = []
        return self[key]

в отличие от Counter, ссылка на неизвестный ключ создаст ключ в словаре, заполнив его пустым списком:

>>> dol = DictOfLists()
>>> dol['foo']
[]
>>> dol['bar'].append("baz")
>>> dol
{'foo': [], 'bar': ['baz']}
>>> 

Настоящий defaultdict позволяет указать в конструкторе фабричную функцию для создания значений для недостающих ключей. Это не намного сложнее. Не стесняйтесь исследовать это.