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

Question

[Azaliya89]

Прохожу курс по алгоритмам на stepic.org
Застряла на задаче по поиску наибольшей невозрастающей подпоследовательности за время n log n (см.картинку)

Мое решение проходит все тесты, кроме последнего, 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. Спасибо всем большое за советы и помощь! Ошибку нашла и исправила, решение приняли, ура!

Comments

[Влад Григорьев]

1. уберите x.reverse() - эта операция не бесплатная, лучше изменить условие.
2. удобнее итерировать объекты напрямую, для номера индекса можно использовать enumerate
3. в конце вместо цикла с принтом, используйте join, и выведите один раз, это тоже чуть быстрее должно быть.
4. вместо list(map(int, input().split())) можно заменить на [int(v) for v in input().split()] - вы все равно создаете список, но тут нет накладных расходов на создание генератора.

не экономте в названии переменных, так другим будет проще понимать что происходит.

Answer 1

[Владимир Олохтонов]

Для начала рекомендую переотправить решение, таймауты могут случаться просто из-за всплеска нагрузки на тестирующий сервер.

Если это не поможет, то вам действительно стоит оптимизировать 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
...

Comments

[Azaliya89]

Действительно, вы правы. В случае большого массива с одинаковыми значениями программа работает непозволительно медленно..и проблема в условие elif. подумаю, как исправить - это условие необходимо, чтобы оставлять повторяющиеся элементы массива. спасибо Вам большое, что помогли найти ошибку!

[Azaliya89]

О, у меня получилось, решение прошло! Спасибо еще раз!
Кстати, не увидела, что вы поправили цикл - сама разобралась)

[Владимир Олохтонов]

Azaliya89, Спасибо вам за интересный вопрос :)

PS: отмечайте решением если мой ответ вам помог.

Answer 2

[antonksa]

Мадам, если этот реально Ваш код, то поверьте, у вас нет проблем и все в порядке. Многие "программисты" даже не смогут понять что тут написано. По сабжу мне лень настолько глубоко ковыряться в задаче, но если решение не проходит, то не факт что это ваша проблема, возможно у ребят в среде стоит слишком маленький таймаут на исполнение тестов. Скорость чаще всего теряется на вложенных циклах, у вас есть один for с вложенным while, while опасная штука, которая может приводить к бесконечным зацикливаниям. Проверьте ваш код, чтобы он не мог при определенных условиях переходить к бесконечному исполнению.

Comments

[Hemul GM]

Если проходит первые тесты, то логично предположить, что результат возвращается (нет бесконечных циклов). Также, если проходит первые тесты, логично предположить, что таймаут задан специально коротки для 20-го теста, дабы проверить оптимальность решения.