Как оптимизировать код на Python?

Question

[К А]

Имеется список дневных температур T. Для каждого дня во входных данных необходимо определить, сколько дней придется ждать более теплой температуры. Если в последующих днях нет более теплой температуры, количество дней будет равно 0.

На входе:
T - список дневных температур, значения температур от 30 до 100
На выходе:
массив с количеством дней

Пример:
T = [73, 74, 75, 71, 69, 72, 76, 73]
daysNumber( T ) --> [1, 1, 4, 2, 1, 1, 0, 0]
Реализуйте функцию daily_temperatures

t = [73, 74, 75, 71, 69, 72, 76, 73]


def daily_temperatures(lst):
    list_count = []
    for start_index in range(len(lst)):
        count = 0
        for letter in range(start_index + 1, len(lst)):
            if lst[letter] > lst[start_index]:
                count += 1
                list_count.append(letter - start_index)
                break
        if count == 0:
            list_count.append(0)
    return list_count


daily_temperatures(t)

Собственно, как оптимизировать это?

Comments

[Wispik]

А с этой функцией что не так? Для чего нужна оптимизация?

[К А]

Убрать вложенный цикл, и счетчик.

Answer 1

[aRegius]

days = []

for ind, temp in enumerate(t):
	   temp_greater = next(((i, val) for i, val in enumerate(t[ind+1:], ind+1) if val > temp), 0)
	   day = temp_greater[0]-ind if temp_greater else 0
	   days.append(day)

Comments

[Wataru]

А в чем здесь оптимизация? Разве что код короче, а работать будет даже медленнее, потому что на каждой итерации проверяет все значения, после текущего. У автора в вопросе же после первого большего элемента стоит break.

Answer 2

[Wataru]

У вас решение за O(N^2), когда как можно сделать решение за O(N). Тут не в питоне дело, а в плохом алгоритме.

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

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

Я не совсем питонист, но вот примерный код:

def days_till_warming(T):
    counts = []
    stack = []
    for i, curr_temp in enumerate(reversed(T)):
        while len(stack)>0 and stack[-1][0] <= curr_temp:
            stack.pop()
        delta = i - stack[-1][1] if len(stack) > 0 else 0
        stack.append([curr_temp, i])
        counts.append(delta)
    return list(reversed(counts))

Answer 3

[Andrey Dugin]

Один из вариантов "в лоб" (без использования допфункций типа takewhile):

def days_till_warming(T):
    counts = []
    for i, curr_temp in enumerate(T):
        for j, next_temp in enumerate(T[i+1:], i + 1):
            if next_temp > curr_temp:
                delta = j - i
                break
        else:
             delta = 0
        counts.append(delta)
    return counts