Как ускорить код на Python?

Question

У меня проблема не могу ускорить код на Python.Лимит 3 секунды. Задание: Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел, на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём. Код: **

def asf(v, f):
    for i in range(int(v[0]) - int(v[1]) + 1):
        print(min([int(i) for i in f[0:int(v[1])]]))
        f.pop(0)
asf(input().split(), input().split())

** Входные данные

В первой строке входных данных содержатся два числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N) – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.

Выходные данные

Выходные данные должны содержать N − K + 1 строк – минимумы для каждого положения “окна”. Пробовал все и генераторы списков и функцию def не получается. Измените код только свой код или другой мне не нужен вот мой код:

Answer 1

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

Answer 2

Не понимаю вот этой загадочной фразы: Измените код только свой код или другой мне не нужен . А что изменять, если ваш код в принципе неверен. Хотел написать реализацию, но если не нужен "другой код" - отлично. Опишу, что НЕПРАВИЛЬНО в вашем коде и что там должно быть.

Вы в каждом цикле (для каждого положения скользящего окна) вызываете функцию min, которая очень затратна. Это в корне неправильно. Вы должны:

на первом шаге найти текущий минимум и его индекс.
на каждом последующем шаге проверять, не "выпадает" ли ваш текущий минимум из вашего окна, и только если он выпадает - вызывать функцию min. Выполнить это необходимо по проверке равенства индекса "выпадающего" элемента и индекса текущего минимума.
если минимум "не выпадает" - в новом окне сравнивать новое значени (то которое добавлено справа) с текущим минимум и в случае если новое значение меньше - заменять им текущий минимум а также его индекс.

Понятно, что при таком подходе количество самых затратных операций min существенно снизиться.

Удачи в реализации.

Answer 3

С комментаторами выше я согласен. То, что вы делаете, в принципе не верно и просто подправить немного ваш код, чтобы всё работало быстро, не получится. Надо писать с нуля и применять алгоритмы.

Предлагаю два способа решения проблемы:

С асимптотической сложностью O(N): Приблизительно то же самое, что и было предложено выше. Только асимптотика лучше, засчёт использования структур данных. Более хорошую сложность, как я знаю, уже не получить. Но если такая есть — мне очень интересно. Можно реализовать с помощью структуры данных "очередь с поддержкой поиска минимума".

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

Общая суть: для сдвига окна вправо вы сначала делаете pop старого левого элемента, а потом push нового правого. Таким образом, у вас в очереди всё время будут находиться элементы искомого окна. Остаётся только выводить результат поиска минимума.

Как работает алгоритм можно почитать здесь, либо в гугле. Почитать мою реализацию алгоритма, которая, правда, написана на C++, можно здесь.
С асимптотической сложностью O(N*log(N)): Чуть хуже по производительности (но вам повезло, у вас очень добрые временные ограничения, это тоже сработает. У меня было по-другому). Лично для моего восприятия немного проще. Используется структура данных "дерево отрезков". Очень базовая структура данных, рекомендую изучить. Может ОЧЕНЬ много где пригодиться.

Идея решения: вы в дерево отрезков сохраняете весь массив, а потом просто выполняете к нему запросы поиска минимума на отрезке.

Ознакомиться, как работает алгоритм, можно здесь, либо в Гугле. Почитать мою C++ реализацию можно здесь.

Предупреждаю! У меня она написана для поиска суммы, а не минимума. Переделать в поиск минимума можно очень быстро (образно говоря, надо заменить все sum() на min()), но заниматься я этим не буду. Код даю просто чтобы вам было легче разобраться в сути.

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

Answer 4

Решение за линейное время с использованием структуры данных "дек"

from collections import deque

 def mininslidingwindow(A, k):
    mins = []
    deq = deque()
    for i in range(len(A)):
        if (len(deq) > 0) and (deq[0] <= i - k):
            deq.popleft()  #слишком старый индекс

        while len(deq) > 0 and A[deq[-1]] >= A[i]:
            deq.pop()
            #удалить элементы, у которых уже нет шансов стать минимумом в окошке

        deq.append(i)

        if i >= k - 1:
            mins.append(A[deq[0]]) #голова дека - минимум в текущем окне

    return mins

print(mininslidingwindow([0,2,1,5,7,2,8,4,4,2], 3))

[0, 1, 1, 2, 2, 2, 4, 2]

БЛОГ НА HUSL

Как ускорить код на Python?

Ответы (4 шт):