Ускорьте цикл NumPy

Question

Я использую модель на Python и пытаюсь ускорить время выполнения.Посредством профилирования кода я обнаружил, что огромное количество общего времени обработки тратится в функции cell_in_shadow ниже.Мне интересно, есть ли способ ускорить его?

Цель функции - предоставить логический ответ, указывающий, затенена ли указанная ячейка в массиве NumPy другой ячейкой (в направлении xтолько).Он делает это, шагая назад по ряду, проверяя каждую ячейку относительно высоты, которой она должна быть, чтобы сделать данную ячейку в тени.Значения в shadow_map рассчитываются другой функцией, не показанной здесь - в этом примере shadow_map принимается за массив со значениями, похожими на:

[0] = 0 (not used)
[1] = 3
[2] = 7
[3] = 18

Функция add_x используется для обеспечениячто индексы массива зацикливаются (используя арифметику циферблата), поскольку сетка имеет периодические границы (все, что происходит с одной стороны, вновь появится на другой стороне).

def cell_in_shadow(x, y):
   """Returns True if the specified cell is in shadow, False if not."""

   # Get the global variables we need
   global grid
   global shadow_map
   global x_len

   # Record the original length and move to the left
   orig_x = x
   x = add_x(x, -1)

   while x != orig_x:
    # Gets the height that's needed from the shadow_map (the array index is the distance using clock-face arithmetic)
      height_needed = shadow_map[( (x - orig_x) % x_len)]
      if grid[y, x] - grid[y, orig_x] >= height_needed:
          return True

    # Go to the cell to the left
    x = add_x(x, -1)

def add_x(a, b):
   """Adds the two numbers using clockface arithmetic with the x_len"""
   global x_len

   return (a + b) % x_len

Answer 1

Я согласен с Санчо, что Cython, вероятно, будет подходить, но вот пара небольших ускорений:

A. Сохраните grid[y, orig_x] в некоторой переменной перед запуском цикла while и используйте эту переменную. Это сэкономит кучу обращений к массиву сетки.

B. Поскольку вы в основном начинаете с x_len - 1 в shadow_map и работаете до 1, вы можете избежать использования модуля очень часто. В основном, изменить:

while x != orig_x:
    height_needed = shadow_map[( (x - orig_x) % x_len)]

до

for i in xrange(x_len-1,0,-1):
    height_needed = shadow_map[i]

или просто избавьтесь от переменной height_needed вместе с:

    if grid[y, x] - grid[y, orig_x] >= shadow_map[i]:

Это небольшие изменения, но они могут немного помочь.

Кроме того, если вы планируете идти по маршруту Cython, я бы подумал, чтобы ваша функция выполняла этот процесс для всей сетки или, по крайней мере, для строки за раз. Это сэкономит много накладных расходов при вызове функции. Однако вы не сможете сделать это в зависимости от того, как вы используете результаты.

Наконец, вы пытались использовать Psyco ? Это займет меньше работы, чем Cython, хотя, вероятно, это не даст вам такой большой прирост скорости. Я бы сначала попробовал.

Answer 2

Если вы не ограничены строгим Python, я бы предложил использовать Cython для этого. Это может позволить статическую типизацию индексов и эффективный прямой доступ к базовому буферу данных массива с высокой скоростью.

Посмотрите короткий учебник / пример на http://wiki.cython.org/tutorials/numpy

В этом примере, который выполняет операции, очень похожие на то, что вы делаете (увеличивая индексы, получая доступ к отдельным элементам числовых массивов), добавление информации о типе в индексные переменные сокращает время вдвое по сравнению с оригиналом. Добавление эффективной индексации в массивы numpy путем предоставления им информации о типе сокращает время примерно до 1% от исходного.

Большая часть кода Python уже является допустимым Cython, так что вы можете просто использовать то, что у вас есть, добавлять аннотации и вводить информацию, где это необходимо, для ускорения.

Я подозреваю, что вы получите максимальную отдачу от добавления информации о типах, ваших индексов x, y, orig_x и массивов numpy.

Answer 3

В следующем руководстве сравниваются несколько разных подходов к оптимизации числового кода в Python:

Scipy PerformancePython

Это немного устарело, но все же полезно. Обратите внимание, что это относится к pyrex, который с тех пор был разветвлен для создания проекта Cython, как упоминал Санчо.

Лично я предпочитаю f2py, потому что я думаю, что в fortran 90 есть много приятных функций numpy (например, добавление двух массивов вместе с одной операцией), но полная скорость скомпилированного кода. С другой стороны, если вы не знаете фортран, возможно, это не тот путь.

Я кратко поэкспериментировал с cython, и проблема, которую я обнаружил, заключалась в том, что по умолчанию cython генерирует код, который может обрабатывать произвольные типы python, но который все еще очень медленный. Затем вам нужно потратить время на добавление всех необходимых объявлений Cython, чтобы сделать его более конкретным и быстрым, тогда как, если вы используете C или Fortran, вы будете стремиться получить быстрый код прямо из коробки. Опять же, это предвзято, потому что я уже знаком с этими языками, тогда как Cython может быть более подходящим, если Python - единственный язык, который вы знаете.