Faire moins de travail, pas le même travail plus vite
Une fois le profileur pointé sur une boucle critique, les plus gros gains viennent du changement de la quantité de travail, pas du fait de presser le même travail. Une boucle qui additionne une fenêtre de 250 prix à chacune d'un million de positions fait 250 millions d'additions ; une version qui fait glisser la fenêtre en fait deux millions. Cette différence, la complexité algorithmique, éclipse tout ce qu'une astuce sur la ligne interne peut apporter. Regardez donc d'abord ce que la boucle répète : une recherche dans une liste, une somme recalculée de zéro, une valeur qui ne change jamais mais qu'on reconstruit à chaque fois.
# 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 hereGlisser, chercher une fois, sortir de la boucle
Trois motifs couvrent la plupart des boucles critiques. Glisser au lieu de recalculer : une somme mobile ajoute la valeur qui entre dans la fenêtre et retire celle qui sort, donc chaque position coûte deux opérations quelle que soit la longueur de la fenêtre. Construire la recherche une seule fois : transformer une liste de paires en dict coûte un passage, après quoi chaque recherche est instantanée, au lieu de parcourir la liste à chaque requête. Sortir de la boucle ce qui ne change pas : tout ce qui est calculé dans une boucle et ne dépend que de valeurs extérieures (une constante, len(x), une recherche d'attribut) va avant la boucle. Testez avec un compteur de lectures ou d'opérations, comme ce labo : un compte ne dépend pas de la vitesse de la machine, c'est donc une mesure stable du travail.
# 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 thousandLaisser NumPy boucler pour vous
Quand le travail est vraiment de l'arithmétique sur beaucoup de nombres, sortez la boucle de Python. Un tableau NumPy stocke les nombres dans un seul bloc mémoire et applique une opération à tous dans du code compilé, si bien que np.log(prices[1:] / prices[:-1]) remplace une boucle Python par un seul appel typiquement des dizaines de fois plus rapide. C'est la vectorisation, et c'est la première optimisation à tenter dans le code numérique. Elle marche mieux sur des tableaux entiers sans if par élément ; quand une condition est nécessaire, utilisez np.where ou un masque booléen. Surveillez aussi la mémoire : vectoriser crée des tableaux temporaires de la taille des données.
# 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- Réduisez d'abord la quantité de travail : faites glisser une fenêtre au lieu de la re-additionner, et évitez de recalculer ce que vous avez déjà.
- Utilisez la bonne structure : un ensemble ou un dict pour les recherches (construit une fois), pas une liste parcourue à chaque requête ; sortez les constantes des boucles.
- Vectorisez les boucles numériques avec NumPy, comptez le travail plutôt que les secondes dans les tests, et comparez toujours la version rapide à une lente évidemment correcte.
À suivre : Numba, compiler en code machine des boucles numériques Python avec un décorateur.
Lab : ce qui est noté
- Faire glisser la fenêtre dans
moving_sum25 pts - Utiliser un ensemble dans
has_duplicates25 pts - Construire un dict une seule fois dans
lookup_prices25 pts - Vectoriser
log_returns25 pts