Блог

Главная - Вопросы по программированию - Python : Быстрый поиск допустимой подстроки для текста из списка подстрок

Python : Быстрый поиск допустимой подстроки для текста из списка подстрок

#python #search #optimization #substring #linear-search

Вопрос:

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

Условия —

  1. У меня есть список из 100 строк шаблона, добавленных в определенной последовательности (известной).
  2. Файл тестового примера имеет размер 35 ГБ и содержит длинные строки в последующих строках

Спросите —

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

Пример —

pattern_strings = [«земля круглая и огромная»,»земля круглая», «марс маленький»]

Содержимое файла тестового набора — Среди всех планет земля круглая, а Марс маленький.

..

..

Следовательно, для первой строки строка с индексом 1 должна соответствовать условию.

В настоящее время я пытаюсь выполнить линейный поиск —

 def search(line,list_of_patterns):
    for pat in list_of_patterns:
        if pat in line:
            return pat
        else:
            continue
    return -1

Текущее время выполнения составляет 21 минуту. Цель состоит в том, чтобы еще больше сократить его. Нужны предложения!

Ответ №1:

Один трюк, о котором я знаю, хотя он не имеет ничего общего с изменением существующего кода, заключается в том, чтобы попытаться запустить свой код с помощью PyPy, а не стандартного интерпретатора CPython. Это может быть одним из трюков, который значительно ускоряет выполнение.

https://www.pypy.org/features.html

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

Это один из вариантов, если вы не хотите изменять свой код.

Другим предложением было бы рассчитать время вашего кода или использовать профилировщики, чтобы увидеть, где находится узкое место и что занимает относительно много времени.

С точки зрения кода вы могли бы избежать цикла for и попробовать следующие методы: https://betterprogramming.pub/how-to-replace-your-python-for-loops-with-map-filter-and-reduce-c1b5fa96f43a

Последним вариантом было бы написать этот фрагмент кода на более быстром и производительном языке, таком как C , и вызвать этот файл .exe (если в Windows) из Python.

Комментарии:

1. Спасибо за предложения. Единственное узкое место, которое я обнаружил, — это линейный поиск. Без реализации поиска время выполнения составляет около 5 минут. Я попробую методы для замены цикла.

2. @Джонни, если использование PyPy вообще возможно, я предлагаю вам это сделать. Даже если это не так, попробуйте и посмотрите на разницу в производительности, просто из любопытства.

3. Конечно, я попробую PyPy и сравню разницу в производительности.

4. @Johnny Мне любопытно узнать о результатах, поэтому, если вы попробуете что-то другое, кроме цикла for, и попробуете PyPy, объявите результаты 🙂

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

Метки: