Ускорение цикла NumPy

Question

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

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

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

The 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] в некоторой переменной, прежде чем начать время цикла и использовать его вместо переменной. Это позволит сэкономить кучу поисковых запросов к массиву grid.

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 для этого. Это может позволить статическое типирование индексов и эффективный прямой доступ к базовому буферу данных массива numpy со скоростью c.

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

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

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

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

Answer 3

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

Scipy PerformancePython

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

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

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