Python зависает из-за плохой реализации

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

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

Квадратичная временная сложность

Мы рассмотрим случай такого зависания, вызванного неэффективной реализацией некоторой логики в Python. Давайте посмотрим на код, с которым я столкнулся в своей работе, который вызывал длительное зависание при каждом запуске. Этого можно было бы избежать, приняв во внимание стоимость основных операций в CPython. р>

Предположим, у нас есть список файлов, которые мы хотим обработать, и список игнорируемых файлов, которые следует исключить из обработки.

files = [f'/tmp/temp{i}.txt' for i in range(29_000, 69_000)]
ignored_files = [f'/tmp/temp{i}.txt' for i in range(30_000)]

Чтобы проиллюстрировать проблему, я использую генератор списков для создания списков. На практике они считывались из файла и передавались в метод в качестве параметров.

Следующий код должен был получить нам файлы, за исключением игнорируемых.

files_to_be_processed = []
for file in files:
    for ignored in ignored_files:
        if file == ignored:
            break
    else:
        files_to_be_processed.append(file)

Код перебирал список файлов. Для каждого файла в списке files он перебирал ignored_files, чтобы выяснить, следует ли игнорировать файл. Предположим, что:

• n – длина файлов
.
• m – длина ignored_files
.

Код имел O(m*n) временную сложность для получения files_to_be_processed.

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

Время работы незначительно, когда m << н. Но когда n сравнимо с m, время выполнения становится заметным из-за текущей реализации, которая дает примерно O(n²) временную сложность, в то время как он может быть линейным O(n). Учитывая тот факт, что у нас были десятки тысяч файлов, их обработка в некоторых случаях занимала до 1 минуты. Оказалось, что это тот случай, когда перекрытие файлов и игнорируемых_файлов было небольшим. Поскольку большинство элементов из файлов не было в списке игнорируемых, каждый из них перебирал все ignored_files.

Такая простая задача, как исключение файлов из обработки, не должна быть столь затратной по времени даже для десятков тысяч файлов. Оказалось, что зависание произошло из-за дорогостоящей реализации исключения файлов в Python.

Улучшение временной сложности

Мы можем сократить время выполнения и преобразовать O(n²) в O(n) с учетом временная сложность различных операций в CPython. Согласно документам, проверка является ли элемент членом набора в среднем занимает O(1). Итак, мы можем использовать структуру данных set для ignored_files, чтобы улучшить временную сложность:

files_to_be_processed = []
unique_ignored_files = set(ignored_files)
for file in files:
    if file not in unique_ignored_files:
        files_to_be_processed.append(file)

# or using a list comprehension

unique_ignored_files = set(ignored_files)
files_to_be_processed = [f for f in files if f not in unique_ignored_files]

Здесь мы проверяем, находится ли файл в unique_ignored_files для O(1). Поскольку нам нужно перебирать все файлы, мы получаем в целом O(n ) временная сложность. Это очень выгодно по сравнению с предыдущим решением O(n²), особенно когда входные данные велики. В результате требуется менее секунды, чтобы подготовить несколько десятков тысяч файлов files_to_be_processed. Вы можете запустить пример самостоятельно, чтобы увидеть изменяется время работы.

В качестве альтернативы Python имеет difference для наборов, что может еще больше упростить код. Он возвращает новый набор с элементами в левом наборе, которых нет в правом наборе.

files_to_be_processed = set(files) - set(ignored_files)

Согласно разница во времени-сложности, дает тот же O(n). Результирующий набор files_to_be_processed можно преобразовать в любая конкретная структура данных, если это необходимо.

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