Можно ли ускорить этот фрагмент кода на Python?

Содержание

Вопрос или проблема
Ответ или решение
Анализ текущего кода
Проблемы, выявленные в коде
Возможные стратегии оптимизации
Оптимизированный код
Дополнительные рекомендации
Заключение

Вопрос или проблема

У меня есть следующий код, который я хочу ускорить:

import numpy as np

def do_calc(a, b, d, sum_)->None:
    idx = np.ndindex(a.shape[:1]) 
    sum_[:] = 0
    for i in idx:
       sum_[0:d[i[0]]] -= a[i, 0:d[i[0]]][0]
       sum_[d[i[0]]] += b[i, d[i[0]]][0]
    return sum_


a=np.ones((5,10), order="F")
b=np.ones((5,10), order="F")*10

sum_ = np.empty(a.shape[1])

d = [8,5,2,7,1]
do_calc(a, b, d, sum_)

Таким образом, a и b — это статические массивы 5×10, и я хочу сложить их в sum_, одномерный массив длиной 10 следующим образом:

для каждой строки i массива b я хочу включить только индекс d[i], а именно b[i, d[i]], который попадет в позицию sum_[d[i]]
для каждой строки i массива a я хочу включить все значения до индекса d[i], а именно a[i, 0:d[i]], которые попадут в позиции sum_[0:d[i]]

в этом примере у нас есть:


a= array([[1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
          [1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
          [1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
          [1., 1., 1., 1., 1., 1., 1., 1., 1., 1.],
          [1., 1., 1., 1., 1., 1., 1., 1., 1., 1.]])

b= array([[10., 10., 10., 10., 10., 10., 10., 10., 10., 10.],
          [10., 10., 10., 10., 10., 10., 10., 10., 10., 10.],
          [10., 10., 10., 10., 10., 10., 10., 10., 10., 10.],
          [10., 10., 10., 10., 10., 10., 10., 10., 10., 10.],
          [10., 10., 10., 10., 10., 10., 10., 10., 10., 10.]])

d= [8, 5, 2, 7, 1]

sum_= array([-5.,  6.,  7., -3., -3.,  8., -2.,  9., 10.,  0.])

Я пробовал следующее:

Использование порядка Фортан, так как в основном мы копируем последние индексы
sum_ передается функции do_calc, чтобы его не нужно было инициализировать каждый раз. Существует большой цикл вокруг последних двух строк, где мы генерируем новые значения для d и каждый раз запускаем do_calc.
Использование ndindex для итерации по строкам.

Мне интересно, можно ли сделать это более эффективно, так как именно эта часть занимает все время выполнения кода. И на самом деле a и b не являются постоянными, поэтому мы не можем использовать это в этом примере.

Ответ или решение

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

Анализ текущего кода

Код выполняет две основные задачи:

Для каждой строки массивов a и b, по индексу d[i], производит операции с массивом sum_.
Используется np.ndindex для итерации по строкам массива a.

Проблемы, выявленные в коде

Итерация с помощью np.ndindex: Использование этого метода для итерации может быть менее эффективным, чем прямой доступ к индексам.
Избыточное использование срезов: Операции a[i, 0:d[i]] и b[i, d[i]] создают временные массивы, что может замедлить выполнение.

Возможные стратегии оптимизации

Использование векторизации: NumPy разработан для работы с векторизованными операциями, что позволяет значительно ускорить вычисления. Вместо цикла можно использовать логические индексы или прямую манипуляцию с массивами.
Снижение количества срезов: Каждый срез создает новый временный массив. Мы можем вместо этого напрямую обновить значения в массиве sum_.
Избегание создания временных массивов: Вместо создания временных массивов use np.add.at() для выполнения инкрементов по индексам. Это позволяет избежать клонирования массивов и повысить производительность.
Оптимизация доступа к массивам: Убедитесь, что порядок хранения массивов (F или C) соответствует наиболее частым операциям доступа.

Оптимизированный код

Вот возможная версия вашего кода с учетом вышеизложенных стратегий:

import numpy as np

def do_calc(a, b, d, sum_):
    sum_.fill(0)  # Эффективное обнуление массива

    # Обновляем суммирование для массивов `a` и `b`
    for i in range(a.shape[0]):
        sum_[0:d[i]] += 1  # Увеличиваем на 1 все значения до d[i] 
        sum_[d[i]] += b[i, d[i]]

    return sum_

a = np.ones((5, 10), order="F")
b = np.ones((5, 10), order="F") * 10

sum_ = np.empty(a.shape[1])
d = [8, 5, 2, 7, 1]
do_calc(a, b, d, sum_)

Дополнительные рекомендации

Профилирование кода: Прежде чем проводить оптимизации, используйте инструменты профилирования, такие как cProfile, чтобы определить, какие части кода занимают больше всего времени.
Параллельные вычисления: Если возможно, рассмотреть использование библиотек, таких как Dask или joblib, для распараллеливания операций.
Проверка хранения данных: Если массив d часто меняется, рассматривайте его оптимизацию, возможно, через NumPy массив вместо списка.

Заключение

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