Comment accélérer la boucle imbriquée python?

Question

J'effectue une boucle imbriquée dans python qui est inclus ci-dessous. Cela constitue un moyen fondamental de chercher dans les séries chronologiques financières existantes et de chercher des périodes dans les séries temporelles qui correspondent à certaines caractéristiques. Dans ce cas, il existe deux tableaux séparés, de taille égale, représentant la «clôture» (c'est-à-dire le prix d'un actif) et le «volume» (c'est-à-dire le montant de l'actif échangé sur la période). Pour chaque période de temps je voudrais anticiper tous les intervalles futurs avec des longueurs entre 1 et INTERVAL_LENGTH et voir si certains de ces intervalles ont des caractéristiques qui correspondent à ma recherche (dans ce cas, le rapport des valeurs proches est supérieur à 1.0001 et moins 1,5 et le volume additionné est supérieur à 100). Ma compréhension est que l'une des principales raisons de l'accélération lors de l'utilisation de NumPy est que l'interpréteur n'a pas besoin de vérifier par type les opérandes chaque fois qu'il évalue quelque chose tant que vous opérez sur le tableau en tant que entier (par exemple, numpy_array * 2), mais évidemment le code ci-dessous n'en profite pas. Y a-t-il un moyen de remplacer la boucle interne par une sorte de fonction de fenêtre qui pourrait entraîner une accélération, ou de toute autre manière en utilisant numpy/scipy pour accélérer cela sensiblement en python natif?

Sinon, existe-t-il un meilleur moyen de le faire en général (par exemple, est-ce que cela sera beaucoup plus rapide d'écrire cette boucle en C++ et d'utiliser le tissage)?

ARRAY_LENGTH = 500000 
INTERVAL_LENGTH = 15 
close = np.array(xrange(ARRAY_LENGTH)) 
volume = np.array(xrange(ARRAY_LENGTH)) 
close, volume = close.astype('float64'), volume.astype('float64') 

results = [] 
for i in xrange(len(close) - INTERVAL_LENGTH): 
    for j in xrange(i+1, i+INTERVAL_LENGTH): 
     ret = close[j]/close[i] 
     vol = sum(volume[i+1:j+1]) 
     if ret > 1.0001 and ret < 1.5 and vol > 100: 
      results.append([i, j, ret, vol]) 
print results 

Answer 1

Mise à jour: (presque) complètement la version vectorisée ci-dessous dans "new_function2" ...

Je vais ajouter des commentaires pour expliquer les choses dans un bit.

Il donne une accélération de ~ 50x, et une plus grande accélération est possible si vous êtes d'accord avec la sortie étant des tableaux numpy au lieu de listes. Tel quel:

In [86]: %timeit new_function2(close, volume, INTERVAL_LENGTH) 
1 loops, best of 3: 1.15 s per loop 

Vous pouvez remplacer votre boucle interne par un appel à np.cumsum() ...Voir ma fonction "new_function" ci-dessous. Cela donne une considérable ... speedup

In [61]: %timeit new_function(close, volume, INTERVAL_LENGTH) 
1 loops, best of 3: 15.7 s per loop 

vs

In [62]: %timeit old_function(close, volume, INTERVAL_LENGTH) 
1 loops, best of 3: 53.1 s per loop 

Il devrait être possible de vectoriser la chose entière et éviter les boucles tout à fait, mais ... Donne-moi une minute, et je ll voir ce que je peux faire ...

import numpy as np 

ARRAY_LENGTH = 500000 
INTERVAL_LENGTH = 15 
close = np.arange(ARRAY_LENGTH, dtype=np.float) 
volume = np.arange(ARRAY_LENGTH, dtype=np.float) 

def old_function(close, volume, INTERVAL_LENGTH): 
    results = [] 
    for i in xrange(len(close) - INTERVAL_LENGTH): 
     for j in xrange(i+1, i+INTERVAL_LENGTH): 
      ret = close[j]/close[i] 
      vol = sum(volume[i+1:j+1]) 
      if (ret > 1.0001) and (ret < 1.5) and (vol > 100): 
       results.append((i, j, ret, vol)) 
    return results 


def new_function(close, volume, INTERVAL_LENGTH): 
    results = [] 
    for i in xrange(close.size - INTERVAL_LENGTH): 
     vol = volume[i+1:i+INTERVAL_LENGTH].cumsum() 
     ret = close[i+1:i+INTERVAL_LENGTH]/close[i] 

     filter = (ret > 1.0001) & (ret < 1.5) & (vol > 100) 
     j = np.arange(i+1, i+INTERVAL_LENGTH)[filter] 

     tmp_results = zip(j.size * [i], j, ret[filter], vol[filter]) 
     results.extend(tmp_results) 
    return results 

def new_function2(close, volume, INTERVAL_LENGTH): 
    vol, ret = [], [] 
    I, J = [], [] 
    for k in xrange(1, INTERVAL_LENGTH): 
     start = k 
     end = volume.size - INTERVAL_LENGTH + k 
     vol.append(volume[start:end]) 
     ret.append(close[start:end]) 
     J.append(np.arange(start, end)) 
     I.append(np.arange(volume.size - INTERVAL_LENGTH)) 

    vol = np.vstack(vol) 
    ret = np.vstack(ret) 
    J = np.vstack(J) 
    I = np.vstack(I) 

    vol = vol.cumsum(axis=0) 
    ret = ret/close[:-INTERVAL_LENGTH] 

    filter = (ret > 1.0001) & (ret < 1.5) & (vol > 100) 

    vol = vol[filter] 
    ret = ret[filter] 
    I = I[filter] 
    J = J[filter] 

    output = zip(I.flat,J.flat,ret.flat,vol.flat) 
    return output 

results = old_function(close, volume, INTERVAL_LENGTH) 
results2 = new_function(close, volume, INTERVAL_LENGTH) 
results3 = new_function(close, volume, INTERVAL_LENGTH) 

# Using sets to compare, as the output 
# is in a different order than the original function 
print set(results) == set(results2) 
print set(results) == set(results3) 

Answer 2

Un speedup serait d'enlever la partie sum, comme dans cette mise en œuvre, il résume une liste de longueur 2 à INTERVAL_LENGTH. Au lieu de cela, ajoutez simplement volume[j+1] au résultat précédent de vol à partir de la dernière itération de la boucle. Ainsi, vous ajoutez simplement deux entiers à la fois au lieu de faire la somme d'une liste entière ET de la découper à chaque fois. Aussi, au lieu de commencer par faire sum(volume[i+1:j+1]), il suffit de faire vol = volume[i+1] + volume[j+1], comme vous le savez, le cas initial ici sera toujours juste deux indices.

Une autre accélération serait d'utiliser .extend au lieu de .append, car l'implémentation python a extend fonctionnant beaucoup plus rapidement.

Vous pouvez également diviser l'instruction finale if afin de ne faire que certains calculs si nécessaire. Par exemple, vous connaissez if vol <= 100, vous n'avez pas besoin de calculer ret.

Cela ne répond pas exactement à votre problème, mais je pense surtout avec le problème de somme que vous devriez voir des accélérations significatives avec ces changements. Éditer - vous n'avez pas non plus besoin de len, puisque vous connaissez déjà la longueur de la liste (à moins que ce ne soit juste pour l'exemple). Définir comme un nombre plutôt que len(something) est toujours plus rapide.

Edition - mise en œuvre (ce qui est non testé):

ARRAY_LENGTH = 500000 
INTERVAL_LENGTH = 15 
close = np.array(xrange(ARRAY_LENGTH)) 
volume = np.array(xrange(ARRAY_LENGTH)) 
close, volume = close.astype('float64'), volume.astype('float64') 

results = [] 
ex = results.extend 
for i in xrange(ARRAY_LENGTH - INTERVAL_LENGTH): 
    vol = volume[i+1] 
    for j in xrange(i+1, i+INTERVAL_LENGTH): 
     vol += volume[j+1] 
     if vol > 100: 
      ret = close[j]/close[i] 
      if 1.0001 < ret < 1.5: 
       ex([i, j, ret, vol]) 
print results 

Answer 3

Pourquoi vous essayez de ne pas générer le résultat sous la forme d'une liste unique (beaucoup plus rapide que annexant ou l'extension), quelque chose comme:

results = [ t for t in ((i, j, close[j]/close[i], sum(volume[i+1:j+1])) 
         for i in xrange(len(close)-INT_LEN) 
          for j in xrange(i+1, i+INT_LEN) 
         ) 
      if t[3] > 100 and 1.0001 < t[2] < 1.5 
      ]