تحسين الحلقات الحرجة

اعمل أقل، لا العمل نفسه أسرع

حين يشير المحلّل إلى حلقة ساخنة تأتي أكبر المكاسب من تغيير مقدار العمل الذي تؤديه لا من عصر العمل نفسه. فحلقة تجمع نافذة من 250 سعرًا عند كل موضع من مليون موضع تجري 250 مليون عملية جمع؛ ونسخة تنزلق بالنافذة تجري مليونين. هذا الفرق، التعقيد الخوارزمي، يتضاءل أمامه أي حيلة في السطر الداخلي. فانظر أولًا إلى ما تكرره الحلقة: بحث في قائمة، أو مجموع يُعاد حسابه من الصفر، أو قيمة لا تتغير لكنها تُبنى في كل مرة.

# 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

انزلق، وابحث مرة واحدة، وأخرج من الحلقة

ثلاثة أنماط تغطي معظم الحلقات الساخنة. انزلق بدل أن تعيد الحساب: المجموع المتحرك يضيف القيمة الداخلة إلى النافذة ويطرح الخارجة فيكلف كل موضع عمليتين مهما كان طول النافذة. ابنِ البحث مرة واحدة: تحويل قائمة أزواج إلى dict يكلف تمريرة واحدة ثم يصير كل بحث فوريًا بدل مسح القائمة لكل استعلام. أخرج ما لا يتغير: كل ما يُحسب داخل حلقة ويعتمد على قيم خارجها فقط (ثابت أو len(x) أو بحث عن خاصية) مكانه قبل الحلقة. واختبر بعدّاد للقراءات أو العمليات كما يفعل هذا المختبر: فالعدد لا يتعلق بسرعة الجهاز ولذا هو مقياس ثابت للعمل.

# 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 يدور عنك

حين يكون العمل فعلًا حسابًا على أرقام كثيرة أخرج الحلقة من بايثون. يخزّن مصفوفة NumPy الأرقام في كتلة ذاكرة واحدة ويطبّق عملية على جميعها في شيفرة مترجمة، فتستبدل np.log(prices[1:] / prices[:-1]) حلقة بايثون بنداء واحد أسرع عادة بعشرات المرات. هذا هو التوجيه (vectorisation) وهو أول تحسين يُلجأ إليه في الشيفرة العددية. ويعمل أفضل على مصفوفات كاملة دون if لكل عنصر؛ وحيث يلزم شرط استعمل np.where أو قناعًا منطقيًا. وانتبه للذاكرة أيضًا: التوجيه ينشئ مصفوفات مؤقتة بحجم البيانات.

# 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

• قلّل مقدار العمل أولًا: حرّك النافذة بدل إعادة جمعها وتجنب إعادة حساب ما لديك.
• استعمل البنية المناسبة: مجموعة أو قاموسًا للبحث (يُبنى مرة واحدة) لا قائمة تُمسح لكل استعلام؛ وأخرج الثوابت من الحلقات.
• وجّه الحلقات العددية بـ NumPy، وعُدّ العمل لا الثواني في الاختبارات، وواصل مقارنة النسخة السريعة بأخرى بطيئة صحيحة بوضوح.

التالي: Numba، ترجمة حلقات بايثون العددية إلى شيفرة آلة بمزخرِف.

المختبر: ما الذي يُقيَّم

• حرّك النافذة في moving_sum25 نقطة
• استخدم مجموعة في has_duplicates25 نقطة
• ابنِ قاموسًا مرة واحدة في lookup_prices25 نقطة
• حوِّل log_returns إلى عملية متجهية25 نقطة