Wie beschleunigt man Python Nested Loop?

Question

Ich führe eine verschachtelte Schleife in Python, die unten enthalten ist. Dies dient als eine grundlegende Möglichkeit, bestehende Finanzzeitreihen zu durchsuchen und Zeiträume in den Zeitreihen zu suchen, die bestimmten Merkmalen entsprechen. In diesem Fall gibt es zwei separate, gleich große Arrays, die das "Schließen" (d. H. Den Preis eines Vermögenswertes) und das "Volumen" (d. H. Den Betrag des Vermögenswerts, der über den Zeitraum ausgetauscht wurde) repräsentieren. Für jeden Zeitraum möchte ich mich auf alle zukünftigen Intervalle mit Längen zwischen 1 und INTERVAL_LENGTH freuen und sehen, ob irgendwelche dieser Intervalle Merkmale haben, die zu meiner Suche passen (in diesem Fall ist das Verhältnis der geschlossenen Werte größer als 1.0001 und weniger) als 1,5 und das summierte Volumen ist größer als 100).

Mein Verständnis ist, dass einer der Hauptgründe für die Beschleunigung bei der Verwendung von NumPy ist, dass der Interpreter die Operanden nicht jedes Mal, wenn es etwas überprüft, die Operanden überprüft, solange Sie auf dem Array als arbeiten Ganze (zB numpy_array * 2), aber offensichtlich nutzt der untenstehende Code keinen Vorteil. Gibt es eine Möglichkeit, die interne Schleife durch irgendeine Art von Fensterfunktion zu ersetzen, was zu einer Beschleunigung führen könnte, oder auf irgendeine andere Weise, die numpy/scipy verwendet, um dies wesentlich in nativem Python zu beschleunigen?

Alternativ gibt es eine bessere Möglichkeit, dies im Allgemeinen zu tun (z. B. wird es viel schneller sein, diese Schleife in C++ zu schreiben und Webart zu verwenden)?

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

Update: (fast) vollständig vektorisiert Version unten in "new_function2" ...

ich Kommentare hinzufügen würde Dinge in einem erklären, Bit.

Es gibt eine ~ 50x Beschleunigung, und eine größere Beschleunigung ist möglich, wenn Sie in Ordnung sind mit der Ausgabe als numpy Arrays anstelle von Listen. Wie es ist:

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

Sie können Ihre innere Schleife durch einen Anruf an np.cumsum() ersetzen ...Siehe meine "new_function" Funktion unten. Daraus ergibt sich eine erhebliche Beschleunigung ...

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 

Es sollte möglich sein, die ganze Sache vektorisieren und ganz für Schleifen zu vermeiden, obwohl ... Geben Sie mir eine Minute, und ich ll sehen, was ich tun kann ...

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

Ein Speedup wäre den sum Teil zu entfernen, wie in dieser Implementierung wird eine Liste der Länge 2 bis INTERVAL_LENGTH summiert. Fügen Sie stattdessen volume[j+1] zum vorherigen Ergebnis von vol aus der letzten Iteration der Schleife hinzu. Daher addieren Sie jedes Mal nur zwei ganze Zahlen, anstatt eine ganze Liste zu summieren UND jedes Mal zu schneiden. Anstatt sum(volume[i+1:j+1]) zu tun, tun Sie einfach vol = volume[i+1] + volume[j+1], wie Sie wissen, der erste Fall wird hier immer nur zwei Indizes sein.

Eine weitere Beschleunigung wäre .extend anstelle von .append zu verwenden, da die Python-Implementierung extend deutlich schneller ausgeführt wird.

Sie könnten auch die endgültige if Anweisung aufteilen, um nur bestimmte Berechnungen durchzuführen, falls erforderlich. Zum Beispiel, Sie wissen if vol <= 100, müssen Sie ret nicht berechnen.

Dies beantwortet Ihr Problem nicht genau, aber ich denke besonders mit dem Summenproblem, dass Sie signifikante Beschleunigungen mit diesen Änderungen sehen sollten.

Bearbeiten - Sie brauchen auch nicht len, da Sie speziell die Länge der Liste bereits wissen (es sei denn, das war nur für das Beispiel). Definieren Sie es als eine Zahl, anstatt len(something) ist immer schneller.

Bearbeiten - Implementierung (dies ist nicht getestet):

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

Warum versuchen Sie nicht, das Ergebnis als eine einzige Liste (viel schneller als das Anhängen oder Erweiterung), so etwas wie zu generieren:

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 
      ]