Accélérer la boucle NumPy

Question

Je cours un modèle en Python et j'essaye d'accélérer le temps d'exécution. Grâce au profilage du code, j'ai constaté qu'une grande partie du temps de traitement total est passée dans la fonction cell_in_shadow ci-dessous. Je me demande s'il y a moyen de l'accélérer?

Le but de la fonction est de fournir une réponse booléenne indiquant si la cellule spécifiée dans le tableau NumPy est ombrée par une autre cellule (dans la direction x uniquement). Il le fait en reculant le long de la rangée en vérifiant chaque cellule par rapport à la hauteur qu'elle doit avoir pour rendre la cellule donnée dans l'ombre. Les valeurs shadow_map sont calculées par une autre fonction non représentée ici - pour cet exemple, prendre shadow_map être un tableau avec des valeurs similaires à:

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

La fonction add_x est utilisée pour faire en sorte que la boucle d'indices de tableau autour (en utilisant arithmétique de l'horloge), car la grille a des limites périodiques (tout ce qui va d'un côté réapparaîtra de l'autre côté).

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

Je suis d'accord avec Sancho que Cython sera probablement le chemin à parcourir, mais voici quelques petites accélérations:

A. magasin grid[y, orig_x] dans une variable avant de commencer la boucle while et l'utilisation que variable à la place. Cela permettra d'économiser un tas d'appels de recherche au tableau de la grille.

B. Comme vous commencez tout juste à partir de x_len - 1 dans shadow_map et que vous travaillez jusqu'à 1, vous pouvez éviter de trop utiliser le module. En fait, le changement:

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] 

ou tout simplement se débarrasser de la variable height_needed tous ensemble avec:

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

Ce sont des petits changements, mais ils pourraient aider un peu .

En outre, si vous envisagez d'aller sur la route Cython, je considérerais que votre fonction effectue ce processus pour toute la grille, ou au moins une ligne à la fois.Cela permettra d'économiser beaucoup de frais généraux d'appel de fonction. Cependant, vous ne pourrez peut-être pas vraiment le faire en fonction de la façon dont vous utilisez les résultats.

Enfin, avez-vous essayé d'utiliser Psyco? Cela prend moins de travail que Cython, mais il ne vous donnera probablement pas un boost de vitesse aussi important. Je l'essaierais certainement en premier.

Answer 2

Si vous n'êtes pas limité à Python strict, je suggère d'utiliser Cython pour cela. Il peut permettre un typage statique des index et un accès direct efficace au tampon de données sous-jacent d'un tableau de nombres n à c vitesse.

Découvrez un court tutoriel/exemple à http://wiki.cython.org/tutorials/numpy

Dans cet exemple, qui fait des opérations très similaires à ce que vous faites (incrémenter indices, accéder à des éléments individuels de tableaux numpy), l'ajout d'informations de type à la les variables d'index réduisent le temps de moitié par rapport à l'original. Ajouter une indexation efficace dans les tableaux chiffrés en leur donnant des informations de type réduit le temps à environ 1% de l'original.

La plupart du code Python est déjà valide en Cython, donc vous pouvez simplement utiliser ce que vous avez et ajouter des annotations et taper des informations si nécessaire pour vous donner quelques accélérations.

Je suppose que vous obtiendrez le maximum de l'ajout d'informations de type vos indices x, y, orig_x et les tableaux numpy.

Answer 3

Le guide suivant compare plusieurs approches différentes pour l'optimisation du code numérique en python:

Scipy PerformancePython

Il est un peu obsolète, mais toujours utile. Notez qu'il fait référence à pyrex, qui a été depuis forké pour créer le projet Cython, comme mentionné par Sancho.

Personnellement, je préfère f2py, parce que je pense que fortran 90 a beaucoup de fonctionnalités intéressantes de numpy (par exemple ajouter deux tableaux ensemble avec une opération), mais a la pleine vitesse du code compilé. D'un autre côté, si vous ne connaissez pas Fortran, alors ce n'est peut-être pas le chemin à parcourir. J'ai brièvement expérimenté avec Cython, et le problème que j'ai trouvé était que par défaut Cython génère du code qui peut gérer des types python arbitraires, mais qui est encore très lent. Vous devez ensuite passer du temps à ajouter toutes les déclarations cython nécessaires pour que ce soit plus spécifique et plus rapide, alors que si vous allez avec C ou fortran, vous aurez tendance à obtenir un code rapide dès la sortie de la boîte. Encore une fois cela est biaisé par moi étant déjà familier avec ces langues, alors que Cython peut être plus approprié si Python est le seul langage que vous connaissez.