ساعتِ صادق: تکرار، کمینه، گرم‌کردن

در این فصل چه یاد می‌گیری#

همان تابعِ فصلِ قبل را روی همان دادهٔ ثابت پنج بار پشتِ سرِ هم اجرا می‌کنیم و پنج عددِ متفاوت می‌گیریم. بیشینه‌شان دو برابرِ کمینه‌شان است.

بعد یک پروتکلِ سه‌قدمی می‌سازیم — گرم‌کننده، تکرار، کمینه — و همان جدولِ فصلِ قبل را دو بار پشتِ سرِ هم می‌گیریم. با یک اجرا، دو گزارشِ پیاپی تا ۱۸ درصد با هم فرق داشتند؛ با پروتکل، حدودِ ۳ درصد. همین شش برابر شدنِ پایداری، تفاوتِ بینِ عددی که می‌شود رویش تصمیم گرفت و عددی که نمی‌شود.

آخر این فصل می‌توانی:

• بگویی حدِ تفکیکِ ساعت چیست و چرا اندازه‌گیریِ چیزهای خیلی کوچک بی‌معناست
• هر اندازه‌گیری را تکرار کنی و کمینه را گزارش کنی، و دلیلش را در یک جمله بگویی
• اجرای گرم‌کننده را دور بریزی و بدانی چرا اجرای اول همیشه گران‌تر است
• timeit را با ساعتِ دستیِ خودت مقایسه کنی و بگویی کدام کجا به‌کار می‌آید

قبل از شروع#

از فصلِ ۱: n، بدترین ورودی، و جدولی که ستونِ نسبت دارد. همان تابعِ first_duplicate را دوباره می‌سازیم، چون نوت‌بوکِ این فصل باید به‌تنهایی از بالا تا پایین اجرا شود.

از سرنخ ترمِ ۲: time.perf_counter.

آن تابعِ clock که در سلولِ راه‌اندازی می‌بینی همان چیزی است که این فصل قدم به قدم می‌سازد. تا بخشِ ۶ به آن دست نمی‌زنیم — اول باید بدانی هر خطش برای رفعِ کدام مشکل آنجاست.

📓 نوت‌بوک: نوت‌بوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

۱. ساعت هم دقتِ محدود دارد#

هیچ ساعتی بی‌نهایت دقیق نیست. time.perf_counter هم یک حدِ تفکیک دارد: کوچک‌ترین فاصلهٔ زمانی‌ای که اصلاً می‌تواند ببیند. پایتون خودش این عدد را به تو می‌گوید.

info = time.get_clock_info("perf_counter")
print("حدِ تفکیکِ perf_counter:", info.resolution, "ثانیه")

start = time.perf_counter()
value = 2 + 2
spent = time.perf_counter() - start
print(f"اندازه‌گیریِ یک جمعِ ساده: {spent:.9f} ثانیه")

start = time.perf_counter()
for _ in range(1_000_000):
    value = 2 + 2
spent = time.perf_counter() - start
print(f"یک میلیون بار همان جمع : {spent:.9f} ثانیه")
print(f"یعنی هر بار حدودِ       : {spent / 1_000_000:.9f} ثانیه")

حدِ تفکیکِ perf_counter: 1e-07 ثانیه
اندازه‌گیریِ یک جمعِ ساده: 0.000000300 ثانیه
یک میلیون بار همان جمع : 0.047799100 ثانیه
یعنی هر بار حدودِ       : 0.000000048 ثانیه

به دو سطرِ آخر با هم نگاه کن. وقتی یک جمع را تنها اندازه گرفتیم، عدد سه برابرِ حدِ تفکیکِ ساعت درآمد — یعنی تقریباً هیچ چیزی جز خودِ خطای ساعت را اندازه نگرفتیم. وقتی یک میلیون بار انجامش دادیم و تقسیم کردیم، عددِ واقعی درآمد: حدودِ نصفِ حدِ تفکیک.

قاعده‌ای که از این درمی‌آید و در کلِ دوره به‌کار می‌آید: اگر چیزی که می‌سنجی از حدِ تفکیکِ ساعت خیلی بزرگ‌تر نیست، آن را تنها نسنج — دسته‌ای بسنج و تقسیم کن.

✅ چک کن: عددِ حدِ تفکیک روی ماشینِ تو ممکن است فرق کند و اشکالی ندارد. چیزی که باید ببینی این است: اندازه‌گیریِ یک عملِ تکی عددی هم‌مرتبهٔ همان حدِ تفکیک می‌دهد، ولی اندازه‌گیریِ یک میلیون‌تا تقسیم بر یک میلیون، عددی خیلی کوچک‌تر. اگر این دو عدد پیشِ تو تقریباً برابر درآمدند، احتمالاً حلقه را جا انداخته‌ای.

۲. یک کد، پنج اجرا، پنج عدد#

حالا برویم سراغِ چیزی که خیلی بزرگ‌تر از حدِ تفکیک است، تا این بهانه از میان برود.

🤔 اول حدس بزن: اگر یک تابع را روی کاملاً همان داده پنج بار پشتِ سرِ هم اجرا کنیم، پنج عدد چقدر با هم فرق می‌کنند؟ یک درصد؟ ده درصد؟ اصلاً فرق نمی‌کنند؟ حدست را بنویس.

rng = random.Random(SEED)
ids = rng.sample(range(20_000), 2_000)


def first_duplicate(values):
    """اولین مقداری که دو بار آمده؛ اگر تکراری نبود، None."""
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] == values[j]:
                return values[i]
    return None


for k in range(5):
    start = time.perf_counter()
    first_duplicate(ids)
    print(f"اجرای {k + 1}: {1000 * (time.perf_counter() - start):>7.1f} ms")

اجرای 1:    70.7 ms
اجرای 2:    71.2 ms
اجرای 3:    71.6 ms
اجرای 4:   111.2 ms
اجرای 5:    91.2 ms

هیچ چیزی عوض نشده. همان تابع، همان فهرست، همان ماشین، پنج بار پشتِ سرِ هم. و عددها یکی نیستند.

دلیلش هم رازآلود نیست: روی همان CPU چیزهای دیگری هم در حالِ اجرا هستند — سیستم‌عامل، مرورگر، کارهای پس‌زمینه — و هر کدام گاهی چند میلی‌ثانیه CPU را از برنامهٔ تو می‌گیرند. در Colab این بدتر است، چون ماشین با کاربرانِ دیگری هم شریک است.

۳. کدام عدد را گزارش کنیم#

پنج عدد داریم و باید یکی را بنویسیم. برای اینکه بحث روی عددهای لرزان نچرخد، این بخش را روی یک نمونهٔ ثابت انجام می‌دهیم: پنج اندازه‌گیریِ واقعی که یک بار گرفته شده و در کد نوشته شده‌اند.

import statistics

SAMPLE = [71.4, 72.9, 88.6, 71.8, 143.2]     # پنج اندازه‌گیریِ واقعی، بر حسبِ ms

print(f"کمینه  : {min(SAMPLE):>7.1f} ms")
print(f"میانه  : {statistics.median(SAMPLE):>7.1f} ms")
print(f"میانگین: {statistics.mean(SAMPLE):>7.1f} ms")
print(f"بیشینه : {max(SAMPLE):>7.1f} ms")
print(f"بیشینه چند برابرِ کمینه است؟ {max(SAMPLE) / min(SAMPLE):.2f}")

کمینه  :    71.4 ms
میانه  :    72.9 ms
میانگین:    89.6 ms
بیشینه :   143.2 ms
بیشینه چند برابرِ کمینه است؟ 2.01

بیشینه دقیقاً دو برابرِ کمینه است، و میانگین از میانه هجده درصد بالاتر.

میانگین به‌خاطرِ یک عددِ پرت (143.2) بالا کشیده شده. آن عدد چیزی دربارهٔ کدِ ما نمی‌گوید؛ دربارهٔ چیزِ دیگری می‌گوید که همان لحظه روی این ماشین اتفاق افتاده.

پس کمینه، و دلیلش یک جمله است: هر اختلالِ بیرونی زمان را فقط زیاد می‌کند، هرگز کم. هیچ اتفاقی در دنیا نمی‌تواند کدِ تو را از آنچه واقعاً هست سریع‌تر کند، ولی هزار اتفاق می‌تواند کندش کند. پس کمینهٔ چند اجرا، نزدیک‌ترین چیزی است که به «زمانِ خالصِ خودِ کد» داریم.

🌱 ریشه‌اش کجاست: اینکه یک عددِ پرت میانگین را می‌کشد ولی میانه را نه، همان درسی است که ریشه ترمِ ۶ فصل ۶ با حقوقِ یک شرکت می‌سازد: نُه نفر با درآمدِ کم و یک مدیر، میانگین 38 و میانه 20. مثالِ ما دقیقاً همان شکل است — چهار عددِ حولِ 72 و یک 143.2. آن فصل همان‌جا می‌گوید هر جا داده مقادیرِ پرتِ بزرگ دارد، میانگین بالاتر از واقعیتِ اکثریت است.

و یک هشدارِ صادقانه: کمینه سؤالِ «کاربرِ من چقدر صبر می‌کند؟» را جواب نمی‌دهد — برای آن باید میانه یا حتی صدکِ بالا را نگاه کنی، چون کاربر همان اجرای بدشانس را هم تجربه می‌کند. در این دوره کمینه را می‌گیریم، چون سؤالِ ما «این کد چقدر کار می‌کند؟» است، نه «کاربر چقدر صبر می‌کند؟». این دو سؤالِ متفاوت‌اند و جوابِ متفاوت می‌خواهند.

۴. اجرای اول همیشه گران‌تر است#

for k in range(7):
    start = time.perf_counter()
    first_duplicate(ids)
    spent = 1000 * (time.perf_counter() - start)
    mark = "  ← اجرای اول" if k == 0 else ""
    print(f"اجرای {k + 1}: {spent:>7.1f} ms{mark}")

اجرای 1:    87.6 ms  ← اجرای اول
اجرای 2:    75.9 ms
اجرای 3:    71.5 ms
اجرای 4:    73.0 ms
اجرای 5:    71.7 ms
اجرای 6:    69.2 ms
اجرای 7:    69.6 ms

اجرای اول گران‌ترینِ هفت‌تاست و این تصادفی نیست. بارِ اول، دادهٔ تو تازه ساخته شده و هنوز در نزدیک‌ترین حافظه به پردازنده ننشسته؛ خودِ تابع هم تازه اجرا می‌شود. از اجرای دوم به بعد همه‌چیز «گرم» است.

پس اجرای اول دور ریخته می‌شود. اسمش اجرای گرم‌کننده است: انجامش می‌دهی، ولی زمانش را نمی‌شماری.

⚠️ مواظب باش: این سکه دو رو دارد و رویِ خطرناکش برعکسِ همین است. اگر نسخهٔ الف را اول بسنجی و نسخهٔ ب را بلافاصله بعدش، ب از یک حالتِ گرم شروع می‌کند که الف نداشت — و تو یک بردِ ده‌درصدی گزارش می‌کنی که مالِ ترتیبِ اجرا بوده، نه مالِ کد. این رایج‌ترین راهِ ناخواسته دروغ‌گفتن با یک benchmark است، و هیچ پیامِ خطایی هم ندارد. علاجش این است که هر دو نسخه گرم‌کنندهٔ خودشان را داشته باشند، که دقیقاً کاری است که clock می‌کند.

۵. timeit: همین کار، در کتابخانهٔ استاندارد#

پایتون ماژولی دارد که همین پروتکل را پیاده کرده است: timeit.

import timeit

ours = clock(lambda: first_duplicate(ids))
theirs = min(timeit.repeat(lambda: first_duplicate(ids), number=1, repeat=REPEAT))
print(f"clock خودمان : {1000 * ours:>7.1f} ms")
print(f"timeit       : {1000 * theirs:>7.1f} ms")
print(f"اختلاف       : {100 * abs(ours - theirs) / theirs:>7.1f} درصد")

clock خودمان :    71.1 ms
timeit       :    65.9 ms
اختلاف       :     8.0 درصد

دو عدد نزدیک‌اند و اختلافشان از پراکندگیِ خودِ اندازه‌گیری بزرگ‌تر نیست.

timeit.repeat دو ورودیِ مهم دارد: number یعنی «در هر دور، چند بار اجرا شود» (همان ترفندِ بخشِ ۱ برای کارهای خیلی کوچک) و repeat یعنی «چند دور». خروجی فهرستی از زمانِ دورهاست و مستنداتِ خودِ پایتون می‌گوید کمینه را بردار — دقیقاً به همان دلیلی که در بخشِ ۳ گفتیم.

timeit یک کارِ اضافه هم می‌کند: جمع‌کنندهٔ زبالهٔ پایتون را موقتاً خاموش می‌کند تا یک پاک‌سازیِ اتفاقی وسطِ اندازه‌گیری نیفتد.

پس چرا clock خودمان را نگه می‌داریم؟ چون این دوره دربارهٔ فهمیدنِ اندازه‌گیری است و clock هشت خط است که می‌توانی بخوانی‌شان. در کارِ روزمره timeit انتخابِ درست‌تری است.

۶. پروتکل، خط به خط#

حالا هر سه درسِ بالا را کنارِ هم می‌گذاریم. این همان clockی است که از فصلِ اول در سلولِ راه‌اندازی بوده:

def clock(fn, repeat=REPEAT):
    fn()                                # ۱) گرم‌کننده: انجام می‌شود، شمرده نمی‌شود
    best = float("inf")
    for _ in range(repeat):             # ۲) تکرار
        start = time.perf_counter()
        fn()
        best = min(best, time.perf_counter() - start)   # ۳) کمینه
    return best


print("clock دوباره تعریف شد؛ رفتارش با نسخهٔ سلولِ راه‌اندازی یکی است.")

clock دوباره تعریف شد؛ رفتارش با نسخهٔ سلولِ راه‌اندازی یکی است.

سه خطِ نشان‌دار، سه درسِ این فصل‌اند. و یک ریزه‌کاریِ چهارم هم هست: clock یک تابع می‌گیرد، نه نتیجهٔ یک تابع. برای همین همه‌جا lambda می‌بینی — چون clock باید بتواند خودش چند بار صدایش بزند.

۷. آیا پروتکل واقعاً جواب داد#

ادعا کردیم پروتکل عدد را پایدارتر می‌کند. این خودش یک ادعاست، پس اندازه‌اش می‌گیریم: هر روش را دو بار پشتِ سرِ هم اجرا می‌کنیم و می‌بینیم دو گزارشِ پیاپی چقدر با هم فرق دارند.

LADDER = [500, 1_000, 2_000, 4_000]
INPUTS = {n: rng.sample(range(10 * n), n) for n in LADDER}


def once(n):
    """اندازه‌گیریِ فصلِ ۱: یک اجرا، یک عدد."""
    start = time.perf_counter()
    first_duplicate(INPUTS[n])
    return 1000 * (time.perf_counter() - start)


def protocol(n):
    """اندازه‌گیریِ این فصل: گرم‌کننده، سه تکرار، کمینه."""
    return 1000 * clock(lambda: first_duplicate(INPUTS[n]), repeat=3)


for name, measure in (("یک اجرا", once), ("پروتکل", protocol)):
    first = [measure(n) for n in LADDER]
    second = [measure(n) for n in LADDER]
    gap = max(100 * abs(a - b) / min(a, b) for a, b in zip(first, second))
    print(f"{name:<8} بیشترین اختلافِ دو گزارشِ پیاپی: {gap:>5.1f} درصد")

یک اجرا  بیشترین اختلافِ دو گزارشِ پیاپی:  17.9 درصد
پروتکل   بیشترین اختلافِ دو گزارشِ پیاپی:   3.2 درصد

۱۸ درصد به ۳ درصد. عددهای تو فرق می‌کنند؛ جهت نباید فرق کند.

و حالا معنای عملی‌اش را ببین: با روشِ فصلِ اول، دو گزارش از یک کدِ ثابت می‌توانستند ۱۸ درصد با هم فرق کنند. پس اگر یک بهینه‌سازی ۱۰ درصد بهبود می‌داد، هیچ راهی نداشتی بفهمی واقعی است یا نه. با پروتکل، سقفِ این نوسان حدودِ ۳ درصد است و بهبودِ ۱۰ درصدی حالا قابلِ دیدن است.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ دو روشِ اندازه‌گیری روی یک تابعِ ثابت و ورودی‌های ثابت — نه دو تابع. در کدام بازهٔ n؟ از ۵۰۰ تا ۴۰۰۰. با چند تکرار، و کمینه یا میانگین؟ پروتکل با سه تکرار و کمینه، و «یک اجرا» با تعریفِ خودش یک بار. کمینه را انتخاب کردیم چون اختلالِ بیرونی فقط زمان را زیاد می‌کند.

🔧 اگر کار نکرد: رایج‌ترین اشتباه با clock این است که به‌جای خودِ تابع، نتیجه‌اش را به آن بدهی:

try:
    clock(first_duplicate(ids))          # ← پرانتزِ اضافه: نتیجه فرستاده شد، نه تابع
except TypeError as err:
    print(f"{type(err).__name__}: {err}")

TypeError: 'NoneType' object is not callable

پیام دقیقاً می‌گوید چه شده: first_duplicate(ids) مقدارِ None برگرداند و clock سعی کرد None را صدا بزند. درستش clock(lambda: first_duplicate(ids)) است. اگر تابعت عدد برگرداند، پیام هم عوض می‌شود ('int' object is not callable) ولی علتش همان یک پرانتزِ اضافه است.

🤖 از دستیارت بپرس: «چرا مستنداتِ timeit می‌گویند کمینه را بردار و نه میانگین؟» بعد این را هم بپرس: «در چه موقعیتی گزارشِ کمینه گمراه‌کننده است و باید میانه یا صدکِ ۹۵ را گزارش کرد؟» — جوابش به تفاوتِ «چقدر کار می‌کند» و «کاربر چقدر صبر می‌کند» برمی‌گردد، و همان تفاوتی است که در بخشِ ۳ دیدیم.

واژه‌های تازهٔ این فصل#

در فصل بعد#

پروتکلِ این فصل نوسان را از ۱۸ درصد به حدودِ ۳ درصد رساند — ولی صفر نکرد و هیچ‌وقت هم نمی‌کند. فصلِ بعد همان سه درصدِ باقی‌مانده را جدی می‌گیرد: سی بار پشتِ سرِ هم یک کدِ ثابت را می‌سنجیم، پراکندگی‌اش را می‌بینیم، و بعد دو نسخهٔ کاملاً یکسان را با دو اسمِ متفاوت مقایسه می‌کنیم تا ببینیم نویز چطور می‌تواند بردِ چنددرصدیِ کاملاً ساختگی تحویلت بدهد.