Heiße Schleifen optimieren

Weniger Arbeit leisten, nicht dieselbe schneller

Hat der Profiler auf eine heiße Schleife gezeigt, kommen die größten Gewinne aus einer Änderung der Arbeitsmenge, nicht aus dem Auspressen derselben Arbeit. Eine Schleife, die an jeder von einer Million Positionen ein Fenster von 250 Preisen aufsummiert, macht 250 Millionen Additionen; eine Version, die das Fenster verschiebt, macht zwei Millionen. Dieser Unterschied, die algorithmische Komplexität, übertrifft jeden Trick in der inneren Zeile. Sehen Sie also zuerst, was die Schleife wiederholt: eine Suche in einer Liste, eine von Grund auf neu berechnete Summe, ein Wert, der sich nie ändert, aber jedes Mal neu gebaut wird.

# Membership in a list scans it; in a set it is a hash lookup. Same answer, very different work
import time

ids = list(range(20_000))
as_set = set(ids)
wanted = list(range(19_000, 20_000))

start = time.perf_counter()
found_list = sum(1 for x in wanted if x in ids)             # scans up to 20,000 items for each of 1,000 lookups
slow = time.perf_counter() - start

start = time.perf_counter()
found_set = sum(1 for x in wanted if x in as_set)
fast = time.perf_counter() - start

print(found_list, found_set)                                # 1000 1000
print(slow > 20 * fast)                                     # True  the set is at least twenty times faster here

Verschieben, einmal nachschlagen, herausziehen

Drei Muster decken die meisten heißen Schleifen ab. Verschieben statt neu berechnen: Eine gleitende Summe addiert den neu hereinkommenden Wert und zieht den herausgehenden ab, sodass jede Position unabhängig von der Fensterlänge zwei Operationen kostet. Das Nachschlagen einmal aufbauen: Eine Liste von Paaren in ein dict zu verwandeln kostet einen Durchlauf, danach ist jedes Nachschlagen sofort, statt die Liste für jede Anfrage zu durchsuchen. Unveränderliches herausziehen: Alles, was in einer Schleife berechnet wird und nur von Werten außerhalb abhängt (eine Konstante, len(x), ein Attributzugriff), gehört vor die Schleife. Testen Sie mit einem Zähler für Lesezugriffe oder Operationen, wie dieses Lab: Eine Zählung hängt nicht von der Rechnergeschwindigkeit ab und misst die Arbeit daher stabil.

# A sliding sum does two operations per position; recomputing each window does `window` of them
def moving_sum_slow(values, window):
    operations = 0
    sums = []
    for i in range(len(values) - window + 1):
        total = 0
        for v in values[i : i + window]:
            total += v
            operations += 1
        sums.append(total)
    return sums, operations

def moving_sum_fast(values, window):
    operations = window
    total = sum(values[:window])
    sums = [total]
    for i in range(window, len(values)):
        total += values[i] - values[i - window]
        operations += 2
        sums.append(total)
    return sums, operations

values = list(range(1_000))
slow, slow_ops = moving_sum_slow(values, 250)
fast, fast_ops = moving_sum_fast(values, 250)
print(slow == fast)                                   # True  the same answers
print(slow_ops, fast_ops)                             # 187750 1750  about a hundred times less work

# Hoisting: a value that never changes is computed once, outside the loop
import math

calls = {"count": 0}

def annualisation_factor():                          # imagine something costly that never changes
    calls["count"] += 1
    return math.sqrt(252)

def scale_slow(returns):
    return [r * annualisation_factor() for r in returns]

def scale_fast(returns):
    factor = annualisation_factor()                  # hoisted out of the loop
    return [r * factor for r in returns]

returns = [0.001 * i for i in range(2_000)]
slow = scale_slow(returns)
slow_calls, calls["count"] = calls["count"], 0
fast = scale_fast(returns)
print(slow == fast)                                  # True  the same numbers
print(slow_calls, calls["count"])                    # 2000 1   one call instead of two thousand

NumPy für Sie die Schleife machen lassen

Ist die Arbeit wirklich Arithmetik auf vielen Zahlen, verlagern Sie die Schleife aus Python. Ein NumPy-Array speichert die Zahlen in einem Speicherblock und wendet eine Operation in kompiliertem Code auf alle an, sodass np.log(prices[1:] / prices[:-1]) eine Python-Schleife durch einen einzigen Aufruf ersetzt, der typischerweise zig Mal schneller ist. Das ist Vektorisierung, die erste Optimierung bei numerischem Code. Sie funktioniert am besten mit ganzen Arrays ohne if pro Element; wo eine Bedingung nötig ist, nutzen Sie np.where oder eine boolesche Maske. Achten Sie auch auf den Speicher: Vektorisierung erzeugt temporäre Arrays in Datengröße.

# Vectorising: one NumPy call replaces a Python loop and gives the same numbers
import math
import time
import numpy as np

rng = np.random.default_rng(3)
prices = 100 * np.exp(np.cumsum(rng.normal(0, 0.001, size=300_000)))

start = time.perf_counter()
loop = [math.log(prices[i] / prices[i - 1]) for i in range(1, len(prices))]
loop_time = time.perf_counter() - start

start = time.perf_counter()
vector = np.log(prices[1:] / prices[:-1])
vector_time = time.perf_counter() - start

print(np.allclose(loop, vector))                    # True  the same returns
print(loop_time > 5 * vector_time)                  # True  at least five times faster here

• Verringern Sie zuerst die Arbeitsmenge: Verschieben Sie ein Fenster, statt es neu zu addieren, und berechnen Sie nichts neu, was Sie schon haben.
• Nutzen Sie die richtige Struktur: eine Menge oder ein dict für Nachschlagen (einmal gebaut), keine bei jeder Anfrage durchsuchte Liste; ziehen Sie Konstanten aus Schleifen.
• Vektorisieren Sie numerische Schleifen mit NumPy, zählen Sie in Tests Arbeit statt Sekunden und vergleichen Sie die schnelle Version weiter mit einer langsamen, offensichtlich richtigen.

Als Nächstes: Numba, numerische Python-Schleifen mit einem Dekorator zu Maschinencode kompilieren.

Lab: Was bewertet wird

• Das Fenster in moving_sum verschieben25 Pkt.
• Eine Menge in has_duplicates nutzen25 Pkt.
• In lookup_prices ein dict nur einmal bauen25 Pkt.
• log_returns vektorisieren25 Pkt.