Помогите оптимизировать код. Python

Question

Есть задача.

Дана последовательность N прямоугольников различной ширины и высоты (wi,hi). Прямоугольники расположены, начиная с точки (0, 0), на оси ОХ вплотную друг за другом (вправо). Требуется найти M - площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.

При n <= 8000 задача проходит, а при n <= 10**5 - нет. Вот код

inf = int(2e9+1)#барьеры для массива
n = int(input())
a = []#высоты для прямоугольников
w = []#ширина для прямоугольников
for i in range(n):#получаем значения.
    v,h= map(int,input().split())
    a.append(h)
    w.append(v)
a = [-inf] + a + [-inf]#добавляем барьеры
ans = [0] * (n+2)#список для ответов
st = [0]
l = []#список элементов левее i, которые меньше a[i]
r = []#список элементов правее i, которые меньше a[i]
rez = []
for i in range(1,n+2):#ищем кандидатов для r
    while int(a[st[-1]]) > int(a[i]):
        ans[st.pop()] = i-1   
    st.append(i)
for i in range(1,n+1):#добавляем их в ответ
    if ans[i] == 0:
        r.append(n)
    else:
        r.append(ans[i])

a = a[::-1]#разворачиваем массив, для того, чтобы найти элементы, левее i и <a[i]
ans = [0] * (n+2)
st = [0]
for i in range(1,n+2):
    while int(a[st[-1]]) > int(a[i]):
        ans[st.pop()] = i-1   
    st.append(i)
ans = ans[::-1]
for i in range(1,n+1):#добавляем их в ответ
    if ans[i] == n:
        l.append(-1)
    else:
        l.append((n-ans[i])-1)
        
rez = []
a = a[::-1]
a.pop(0)
a.pop()
pref = []
for i in range(len(l)):#считаем длины прямоугольников, которые влезают в границы l[i],r[i]
    #if l[i] == -1:
        #pref.append(sum(w[0:r[i]]))
        
    if r[i] == n:
        pref.append(sum(w[l[i]+1:]))
        
    else:
        pref.append(sum(w[l[i]+1:r[i]]))
      

for i in range(n):#выводим площади прямоугольников.
    rez.append(a[i]*pref[i])
print(max(rez))

Answer 1

Хорошо бы, если бы можно было пользоваться библиотекой Numpy. Но даже если нельзя, то для начала избавьтесь от всех append по возможности, сразу задав максимальный размер всем спискам, так же как вы делаете это в этой строке:

ans = [0] * (n+2)

То есть

l = [0] * n # или n + 2 или n * 2 смотря по ситуации
i = 0

И потом вместо

l.append(x)

Пишите

l[i] = x
i += 1

Должно работать быстрее. Но лучше бы использовать Numpy, там числовые массивы работают гораздо быстрее, чем списки Python.

И да, список l приведён в качестве примера, у вас там такого добра полно в коде, почти в каждом цикле можно сделать так же.

P.S. Провёл небольшой тест в Google Colab, ускорение от этого всего в 1.5 раза, мало. Списки Python очень медленные в любом случае.

Answer 2

Я "перевел" код Igor с JS на Python в этом вопросе, возможно вас устроит: вопрос

Вот сам код:

def maxArea(rs):
    a = 0
    for i in range(len(rs)):
        r = rs[i]
        ai = r[0] * r[1] + back(rs, r[1], i) + forward(rs, r[1], i)
        a = max(a, ai)
    return a

def back(rs, h, idx):
    a = 0
    for j in range(idx-1, -1, -1):
        if rs[j][0] >= h:
            a += rs[j][0] * h
        else:
            break
    return a

def forward(rs, h, idx):
    a = 0
    for j in range(idx+1, len(rs)):
      if rs[j][1] >= h:
        a += rs[j][0] * h
      else:
        break
    return a

rs1 = [[4, 3], [2, 1], [2, 5]]
rs2 = [[4, 3], [2, 1], [3, 5]]

print(maxArea(rs1))
print(maxArea(rs2))

БЛОГ НА HUSL

Помогите оптимизировать код. Python

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