Как ускорить код на Python?

Question

[Ananasi0]

Скорость кода не удовлетворяет условиям, нужно менее секунды, имеется 1,089 секунд. Есть ли способы ещё ускорить код?

n, m = [int(i) for i in input().split()]
arr = {}
summa = 0
for i in range(m):
    l, r, x = [int(i) for i in input().split()]
    for j in range(l-1, r):
        get = arr.get(j,0)
        if get < x:
            summa += x - get
            arr[j] = x
print(summa)

Comments

[Vindicar]

1. Что вообще должен делать код?
2. Ну можно попробовать использовать defaultdict() вместо обычного словаря, но не факт что поможет.
3. Погоняй отдельные куски кода через timeit, поищи узкие места.

[Сергей Горностаев]

Какое отношение к вопросу имеет тег "Client side optimization"?

[alexbprofit]

n можно убрать, оно нигде не используется

[Wataru]

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

[Adamos]

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

Answer 1

[Wataru]

Я предполагаю, что условие вашей задачи такое - дано куча запросов вида <начало отрезка, конец, значение>. Все ячейки в этом отрезке заполняются заданным значением, если они меньше его. Надо найти сумму всех ячеек в конце.

Тут есть два решения. Первое - через дерево отрезков с отложенным изменением. Само дерево немного странное получается, потому что оно ничего не считает в промежуточных вершинах, а будет только хранить отложенное изменение. Физический смысл отложенного изменения - "все ячейки в этом поддереве должны быть не меньше этого значения". Релаксация (спуск вниз) отложенного изменения происходит так: отложенное изменение в детях заменяется на максимум из того, что там лежит и отложенного значения в родителе. Значение в родителе заменяется на 0. При запросе спускайтесь рекурсивно по дереву, релаксируя изменения, пока текущее поддерево не будет целиком лежать в запросе. Тогда перезаписывайте отложенное значение в текущей вершине, если оно меньше. В конце обработки запросов релаксируйте все вершины сверху вниз и просуммируйте значения в листьях.

Второе решение - через метод сканирующей прямой может быть проще в реализации из-за наличия встроенных структур данных. Я думаю, в питоне должна быть структура, которая умеет быстро добавлять число, удалять число и брать максимум из всех чисел. В C++ есть std::set или std::priority_queue.
Для каждого отрезка-запроса создайте два события вида <координата, отрезок открылся/закрылся, значение> (разберитесь, где там +-1 поставить так, чтобы длина отрезка по координатам равнялась количеству покрытых ячеек). Засуньте их все в один массив и отсортируйте по координате. Потом проходитесь слева-на-право. Применяйте текущее событие - или добавляйте число в вашу структуру данных, или удаляйте оттуда. Между текущим и следующим событием по координатам все ячейки покрыты одним и тем же множеством отрезков, поэтому можно их все быстро посчитать, ведь ваша структура умеет брать максимум. Добавляйте к ответу разность координат между текущим и следующим событиями, умноженную на значение максимума из структуры. Все.