Optimización de bucles críticos

Hacer menos trabajo, no el mismo trabajo más rápido

Cuando el perfilador ha señalado un bucle crítico, las mayores mejoras vienen de cambiar cuánto trabajo hace, no de exprimir el mismo trabajo. Un bucle que suma una ventana de 250 precios en cada una de un millón de posiciones hace 250 millones de sumas; una versión que desliza la ventana hace dos millones. Esa diferencia, la complejidad algorítmica, eclipsa cualquier truco en la línea interior. Mira primero qué repite el bucle: una búsqueda en una lista, una suma recalculada desde cero, un valor que nunca cambia pero se reconstruye cada vez.

# 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

Deslizar, buscar una vez, sacar del bucle

Tres patrones cubren la mayoría de los bucles críticos. Deslizar en vez de recalcular: una suma móvil añade el valor que entra en la ventana y resta el que sale, así cada posición cuesta dos operaciones sea cual sea la longitud de la ventana. Construir la búsqueda una vez: convertir una lista de pares en un dict cuesta una pasada, tras lo cual cada búsqueda es instantánea, en vez de recorrer la lista en cada consulta. Sacar lo que no cambia: todo lo que se calcula dentro de un bucle y solo depende de valores externos (una constante, len(x), una búsqueda de atributo) va antes del bucle. Prueba con un contador de lecturas u operaciones, como este laboratorio: un recuento no depende de la velocidad de la máquina, así que es una medida estable del trabajo.

# 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

Deja que NumPy haga el bucle por ti

Cuando el trabajo es realmente aritmética sobre muchos números, saca el bucle de Python. Un array de NumPy guarda los números en un solo bloque de memoria y aplica una operación a todos en código compilado, así que np.log(prices[1:] / prices[:-1]) sustituye un bucle de Python por una sola llamada típicamente decenas de veces más rápida. Es la vectorización, y es la primera optimización a la que recurrir en código numérico. Funciona mejor con arrays enteros sin un if por elemento; si hace falta una condición, usa np.where o una máscara booleana. Vigila también la memoria: vectorizar crea arrays temporales del tamaño de los datos.

# 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

• Reduce primero la cantidad de trabajo: desliza una ventana en lugar de volver a sumarla y evita recalcular lo que ya tienes.
• Usa la estructura adecuada: un conjunto o dict para búsquedas (construido una vez), no una lista recorrida en cada consulta; saca las constantes de los bucles.
• Vectoriza los bucles numéricos con NumPy, cuenta el trabajo y no los segundos en las pruebas, y sigue comparando la versión rápida con una lenta y obviamente correcta.

A continuación: Numba, compilar a código máquina bucles numéricos de Python con un decorador.

Lab: qué se califica

• Deslizar la ventana en moving_sum25 pts
• Usar un conjunto en has_duplicates25 pts
• Construir un dict una sola vez en lookup_prices25 pts
• Vectorizar log_returns25 pts