@Azaliya89

Наибольшая невозрастающая подпоследовательность. Как оптимизировать алгоритм на Python?

Прохожу курс по алгоритмам на stepic.org
Застряла на задаче по поиску наибольшей невозрастающей подпоследовательности за время n log n (см.картинку)
5df7d5c4f3e19446122495.png
Мое решение проходит все тесты, кроме последнего, 20-го, выдавая ошибку Failed test #20 of 20. Time limit exceeded - понятно, что не прохожу по времени, но уже неделю пытаюсь понять почему. И, как назло, никто в комментариях именно с такой проблемой не сталкивался, поэтому прошу помощи здесь.
Заранее прошу прощения, если вопрос глупый, я еще только учусь и, к сожалению, знакомых программистов, к которым могу обратиться с вопросами, у меня нет(
Описание алгоритма для поиска наибольшей возрастающей подпоследовательности за время n log n с использованием бинарного поиска есть тут: https://en.wikipedia.org/wiki/Longest_increasing_s...

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

Вот мой код:
n = int(input())
x = list(map(int, input().split()))
x.reverse()
p = [0]*n
m = [0]*(n+1)
l = 0

for i in range(n):
    left = 1
    right = l
    while left <= right:
        mid = (left+right) // 2
        if x[m[mid]] < x[i]:
            left = mid+1
        elif x[m[mid]] == x[i]:
            left += 1
        else:
            right = mid-1
    new_l = left
    p[i] = m[new_l-1]
    
    if new_l > l:
        m[new_l] = i
        l = new_l 
    elif x[i] < x[m[new_l]]:
        m[new_l] = i
        
print(l)
k = m[l]
for i in range(l-1,-1,-1):
    print (n-k, end = '  ')
    k = p[k]


UPD. Спасибо всем большое за советы и помощь! Ошибку нашла и исправила, решение приняли, ура!
  • Вопрос задан
  • 1943 просмотра
Решения вопроса 1
sgjurano
@sgjurano
Разработчик
Для начала рекомендую переотправить решение, таймауты могут случаться просто из-за всплеска нагрузки на тестирующий сервер.

Если это не поможет, то вам действительно стоит оптимизировать print, потому что в Python очень дорогие вызовы функций, на моём компьютере вот такие замеры получились:
l = list(range(10**5))

for i in l:  # 107 ms
    print(i, end=' ')

s = ' '.join(map(str, l))
print(s)  # 55 ms


В целом при отладке таких проблем имеет смысл искать крайние случаи, на которых ваша программа будет работать медленнее всего — в данном случае, если я правильно понял вашу программу (читал не очень внимательно), это упорядоченный в обратном порядке массив размером 10^5.

UPD: Я нашёл плохой вход для вашей программы - проверьте её на массиве, где все значения одинаковые, время выполнения получилось около 20 секунд на массиве длиной 10^4, на 10^5 ответа я не дождался.

Это происходит вот из-за этих строк:
for i in range(n):
    left = 1 
    right = l 
...
    elif x[m[mid]] == x[i]:
        left += 1
...


В худшем случае у вас здесь возникает O(n^2).

Кажется, достаточно будет просто поменять цикл на вот такой:
for i in range(n):
    left = 1
    right = l

    while left <= right:
        mid = (left+right) // 2
        if x[m[mid]] <= x[i]:
            left = mid+1
        else:
            right = mid-1
...
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@antonksa
Мадам, если этот реально Ваш код, то поверьте, у вас нет проблем и все в порядке. Многие "программисты" даже не смогут понять что тут написано. По сабжу мне лень настолько глубоко ковыряться в задаче, но если решение не проходит, то не факт что это ваша проблема, возможно у ребят в среде стоит слишком маленький таймаут на исполнение тестов. Скорость чаще всего теряется на вложенных циклах, у вас есть один for с вложенным while, while опасная штука, которая может приводить к бесконечным зацикливаниям. Проверьте ваш код, чтобы он не мог при определенных условиях переходить к бесконечному исполнению.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы