Как я могу ускорить выполнение кода?

Question

Как я могу ускорить выполнение кода?

Рейтинг: -2Ответов: 1Опубликовано: 26.02.2023

У меня есть код, который решает некую задачу, аля бинарный поиск, как я могу сделать сложность n+m или n*m? Код:

n = list(map(int, input().split()))
m = list(map(int, input().split()))

def f(a, p):
    left = 0
    right = 0
    for i in range(p):
        if a[i] == a[p]:
            left += 1
    for i in range(p+1, len(a)):
        if a[i] != a[p]:
            right += 1
    return left * right

for x in m:
    max_val = -1
    max_pos = -1
    for i in range(len(n)+1):
        val = f(n[:i] + [x] + n[i:], i)
        if val > max_val:
            max_val = val
            max_pos = i
    print(max_val, end=' ')

Код все тесты проходит, но по времени нет, как можно ускорить данный код на пару секунд по выполнению?

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

1 1 2 2 2 2 1 1 1
1 2 1

Выходные:

8 12 8

Задача: В шеренгу друг за другом стоят n человек, рост i-го из них равен ai условных единиц. Вы тоже собираетесь встать в эту шеренгу, при чем вам хочется встать на такую позицию p, чтобы f(p) = [количество людей левее вас того же роста, что и вы] умножить на [количество людей правее вас ростом, не равным росту вас] было максимально. Для этого вы можете встать в начало шеренги, в её конец, или между любыми 2мя соседними людьми. К сожалению вы не можете точно вспомнить ваш рост, у вас есть только m предположений о том, каким он может быть, и для каждого из них вы хотели бы знать оптимальную позицию, на которую вам стоило бы встать.

python

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

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

equal = [0 for i in range(len(m))]
notequal = [len(list(filter(lambda x: x != m[i], n))) for i in range(len(m))]
valsave = [0 for i in range(len(m))]
possave = [0 for i in range(len(m))]

for i in range(len(n)):
    for x in range(len(m)):
        if n[i] == m[x]:
            equal[x] += 1
        if n[i] != m[x]:
            notequal[x] -= 1

        val = equal[x] * notequal[x]
        if val > valsave[x]:
            valsave[x] = val
            possave[x] = i+1
print(possave)

Как я могу ускорить выполнение кода?

Ответы