Улучшение производительности функции фрагмента скользящего окна в Python 3

Question

У меня есть скрипт в Python 3.6.8, который считывает очень большой текстовый файл, где каждая строка представляет собой строку ASCII, взятую из алфавита {a,b,c,d,e,f}.

Для каждой строки у меня есть функция, которая фрагментирует строку, используя скользящее окно размером k, а затем увеличивает словарь счетчика фрагментов fragment_dict на 1 для каждого видимого фрагмента.

То же fragment_dict используется для всего файла и инициализируется для всех возможных 5^k фрагментов, отображающихся в ноль.

Я также игнорирую любой фрагмент, в котором есть символ c. Обратите внимание, что c встречается редко, и большинство строк его вообще не содержат.

def fragment_string(mystr, fragment_dict, k):
    for i in range(len(mystr) - k + 1):

        fragment = mystr[i:i+k]
        if 'c' in fragment:
            continue

        fragment_dict[fragment] += 1

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

Я боюсь, что скорость может быть ограничена скоростью Python циклов, и в этом случае мне нужно было бы рассмотреть возможность перехода на C / Cython.

Answer 1

Numpy может помочь в ускорении вашего кода:

x = np.array([ord(c) - ord('a') for c in mystr])
filter = np.geomspace(1, 5**(k-1), k, dtype=int)
fragment_dict = collections.Counter(np.convolve(x, filter,mode='valid'))

Идея состоит в том, чтобы представить каждый сегмент длины k в виде k-di git 5-значного числа. Затем преобразование списка из 0-5 целых чисел, эквивалентных строке, в его 5-разрядное представление эквивалентно применению свертки с [1,5,25,125, ...] в качестве фильтра.