کدی که درست کار می‌کند و غیرقابلِ استفاده است

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

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

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

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

• زمانِ اجرا را یکی از ویژگی‌های برنامه ببینی، نه یک اتفاق
• بگویی n در یک قطعه کد دقیقاً چیست و چرا هر ادعای سرعتی بدونِ آن ناقص است
• «درست» و «قابلِ استفاده» را از هم جدا کنی
• به‌جای پرسشِ «این کد سریع است؟» بپرسی «تا کدام n سریع است؟»

قبل از شروع#

از سرنخ ترمِ ۱: list، حلقه، range، تابع و f-string.

از سرنخ ترمِ ۲: time.perf_counter به‌عنوان کرنومتر — عددی که خودش به‌تنهایی معنایی ندارد، ولی تفاضلِ دو بار صدا زدنش می‌گوید بینشان چقدر گذشته.

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

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

• SEED — عددی که تولیدکنندهٔ تصادفیِ پایتون با آن راه می‌افتد. random.Random(SEED) یعنی «همان دنبالهٔ به‌ظاهر تصادفی، در هر اجرا و روی هر ماشینی». این قراردادِ بازتولیدپذیریِ کلِ دوره است: بدونِ آن، جدولِ تو و جدولِ من روی دو ورودیِ متفاوت گرفته شده‌اند و مقایسه‌شان بی‌معناست.
• SIZES — نردبانِ اندازه‌ها، [1_000, 2_000, 4_000, 8_000]: چهار عدد که هر بار دو برابر می‌شوند. شکلش عوض نمی‌شود و فصلِ ۵ می‌گوید چرا حتماً باید ضربی باشد.
• table(rows) — سه ستون چاپ می‌کند: n، خودِ اندازه‌گیری، و نسبتِ هر سطر به سطرِ قبل (یعنی همین سطر تقسیم بر سطرِ بالایی). ستونِ سوم ابزارِ اصلیِ کلِ دوره است؛ از همین فصل به بعد هر نتیجه‌ای از روی آن خوانده می‌شود. فصلِ ۵ قاعدهٔ کاملِ خواندنش را می‌دهد — اینکه نزدیکِ 2 یعنی چه و نزدیکِ 4 یعنی چه.

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

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

۱. تابعی که کارش درست است#

انبار یک فهرست از کدهای محصول می‌دهد و می‌پرسد: کدی هست که دو بار ثبت شده باشد؟

ساده‌ترین راهی که به ذهنِ هر کسی می‌رسد این است: هر کد را با تکِ تکِ کدهای بعد از خودش مقایسه کن.

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


small = [41, 17, 88, 23, 17, 96]
print("ورودی      :", small)
print("جوابِ تابع :", first_duplicate(small))
print("جوابِ درست :", 17)

ورودی      : [41, 17, 88, 23, 17, 96]
جوابِ تابع : 17
جوابِ درست : 17

این تابع درست است. نه تقریباً درست و نه معمولاً درست: هر کدی که دو بار در فهرست باشد پیدا می‌شود، و اگر تکراری نباشد None برمی‌گردد. می‌توانی روی کاغذ دنبالش کنی و مطمئن شوی.

اگر این تنها معیارِ ما بود، کار تمام بود. نیست.

✅ چک کن: 88 را در small با 23 جابه‌جا کن ([41, 17, 23, 88, 17, 96]) و دوباره اجرا کن. جواب باید 17 بماند، چون 17 هنوز تنها کدی است که دو بار آمده. اگر None گرفتی، احتمالاً return را از داخلِ حلقه بیرون برده‌ای.

۲. n چیست#

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

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

یک ادعای سرعت بدونِ گفتنِ n، ناقص است — نه اشتباه، ناقص؛ مثلِ اینکه بگویی «این ماشین سنگین است» و نگویی با بار یا بدونِ بار. این سومین قانونِ ثابتِ کلِ دوره است: «nِ خودت را بگو».

۳. همان تابع، چهار اندازه#

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

🤔 اول حدس بزن: قبل از اجرا بنویس — اگر n را دو برابر کنیم، زمان چند برابر می‌شود؟ دو برابر؟ چهار برابر؟ همان‌قدر؟ جوابت را یادداشت کن؛ چند خط پایین‌تر جدول را می‌بینی.

rng = random.Random(SEED)


def unique_ids(n):
    """n کدِ یکتا — بدترین ورودیِ ممکن، چون تابع مجبور است تا آخر بگردد."""
    return rng.sample(range(10 * n), n)


rows = []
for n in SIZES:
    ids = unique_ids(n)
    start = time.perf_counter()
    answer = first_duplicate(ids)
    rows.append((n, 1000 * (time.perf_counter() - start)))
    print(f"n={n:>6,}  جوابِ تابع: {answer}")
print()
table(rows)

n= 1,000  جوابِ تابع: None
n= 2,000  جوابِ تابع: None
n= 4,000  جوابِ تابع: None
n= 8,000  جوابِ تابع: None

         n         زمان (ms)     نسبت به سطر قبل
     1,000              16.9                   —
     2,000              72.4                4.29
     4,000             282.3                3.90
     8,000           1,126.8                3.99

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

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

و به ناهمواریِ همان ستون نگاه کن: 4.29، بعد 3.90، بعد 3.99. هر سه «حدودِ چهار» هستند ولی هیچ‌کدام دقیقاً چهار نیستند. این ناهمواری خودش موضوعِ دو فصلِ بعد است — فصلِ ۲ می‌گوید چطور اندازه بگیریم که کمتر بلرزد و فصلِ ۳ می‌گوید بخشی از این لرزش هیچ‌وقت نمی‌رود و باید با آن کنار آمد.

۴. عددی که اندازه نگرفتیم#

«حدودِ چهار برابر به‌ازای هر دو برابر شدنِ n» یک قاعده است، و از قاعده می‌شود بیرونِ بازهٔ اندازه‌گیری‌شده هم استفاده کرد. این کار اسم دارد: برون‌یابی — و ریسک هم دارد.

def human(seconds):
    if seconds < 90:
        return f"{seconds:,.0f} ثانیه"
    if seconds < 5400:
        return f"{seconds / 60:,.0f} دقیقه"
    if seconds < 172800:
        return f"{seconds / 3600:,.0f} ساعت"
    return f"{seconds / 86400:,.0f} روز"


last_n, last_ms = rows[-1]
print(f"اندازه‌گیریِ واقعی : n = {last_n:>10,}  →  {human(last_ms / 1000)}")
for factor in (10, 100, 1000):
    print(f"برون‌یابی         : n = {last_n * factor:>10,}"
          f"  →  {human(last_ms / 1000 * factor ** 2)}")

اندازه‌گیریِ واقعی : n =      8,000  →  1 ثانیه
برون‌یابی         : n =     80,000  →  2 دقیقه
برون‌یابی         : n =    800,000  →  3 ساعت
برون‌یابی         : n =  8,000,000  →  13 روز

هشتصد هزار کدِ محصول عددِ عجیبی نیست؛ یک فروشگاهِ اینترنتیِ متوسط همین‌قدر ردیف دارد. و همان تابعِ درستِ شش‌خطی، روی همان داده، سه ساعت طول می‌کشد.

⚠️ مواظب باش: سه سطرِ آخر اندازه‌گیری نشده‌اند، حساب شده‌اند. ما n = 8,000,000 را اجرا نکردیم — سیزده روز طول می‌کشید. آنچه کردیم این بود که قاعدهٔ «چهار برابر» را از بازهٔ اندازه‌گیری‌شده بیرون بردیم و به آن اعتماد کردیم. هر جای این کتاب که عددی برون‌یابی شده باشد، صریح گفته می‌شود — چون برون‌یابی یک پیش‌بینی است و پیش‌بینی می‌تواند غلط باشد. فصلِ ۸ کاملاً دربارهٔ همین است و آنجا خطای پیش‌بینی را هم اندازه می‌گیریم.

۵. «قابلِ استفاده» یعنی «تا کدام n»#

«این کد کند است» جمله‌ای است که هیچ کاری با آن نمی‌شود کرد. جملهٔ قابلِ استفاده این است: «این کد تا nِ فلان، زیرِ بودجهٔ زمانیِ ما می‌ماند.»

پس اول بودجه را می‌نویسیم، بعد اندازه می‌گیریم. اینجا بودجه را نیم ثانیه می‌گذاریم — عددی که خودمان انتخاب کرده‌ایم، چون کاربری که روی دکمه کلیک می‌کند بیشتر از این صبر نمی‌کند.

BUDGET = 0.5            # ثانیه — بودجهٔ زمانی‌ای که خودمان گذاشتیم
n = 500
while True:
    ids = unique_ids(n)
    start = time.perf_counter()
    first_duplicate(ids)
    spent = time.perf_counter() - start
    print(f"n={n:>6,}  {spent:>6.3f} ثانیه  {'قبول' if spent <= BUDGET else 'رد'}")
    if spent > BUDGET:
        break
    n *= 2
print(f"\nبزرگ‌ترین n که زیرِ {BUDGET} ثانیه ماند: {n // 2:,}")

n=   500   0.004 ثانیه  قبول
n= 1,000   0.018 ثانیه  قبول
n= 2,000   0.072 ثانیه  قبول
n= 4,000   0.291 ثانیه  قبول
n= 8,000   1.221 ثانیه  رد

بزرگ‌ترین n که زیرِ 0.5 ثانیه ماند: 4,000

حالا یک جملهٔ کامل داریم: «این تابع تا حدودِ چهار هزار کد، روی این ماشین، زیرِ نیم ثانیه جواب می‌دهد.»

سه چیز در این جمله هست که هیچ‌کدام تزیینی نیست: بازهٔ n («تا چهار هزار»)، ماشین («روی این ماشین») و بودجه («زیرِ نیم ثانیه»). اگر هر کدام را برداری، جمله دوباره بی‌مصرف می‌شود.

و از همین‌جا معلوم می‌شود که «مقیاس‌پذیر» صفتِ یک کد نیست، یک پرسش است: تا کدام n؟ کدی که برای صد ردیف نوشته شده و هرگز بیشتر نمی‌بیند، هیچ ایرادی ندارد که first_duplicate باشد. همین کد اگر پشتِ صفحهٔ ورودِ کاربر بنشیند، فاجعه است. کد عوض نشده؛ n عوض شده.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک تابع با خودش، در چهار اندازهٔ ورودی — نه دو تابعِ متفاوت. در کدام بازهٔ n؟ از هزار تا هشت هزار برای جدولِ بخشِ ۳، و از پانصد تا هشت هزار برای بودجهٔ بخشِ ۵. با چند تکرار، و کمینه یا میانگین؟ با یک اجرا، و همین ایرادِ بزرگِ این فصل است. هر عددی که این فصل نشان داد، یک بار گرفته شده و هیچ‌کس نمی‌داند چقدر قابلِ اعتماد است. فصلِ بعد دقیقاً همین را درست می‌کند.

۶. یک خطای واقعی سرِ راه#

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

def broken_duplicate(ids):
    for i in range(len(ids)):
        for j in range(i + 1, len(ids) + 1):        # ← یکی زیادی
            if ids[i] == ids[j]:
                return ids[i]
    return None


try:
    broken_duplicate(small)
except IndexError as err:
    print(f"{type(err).__name__}: {err}")

IndexError: list index out of range

🔧 اگر کار نکرد: پیامِ IndexError: list index out of range یعنی اندیسی خواسته‌ای که در فهرست نیست. در فهرستی با n عضو، اندیسِ معتبر از 0 تا n - 1 است، پس مرزِ بالای هر rangeی که با آن اندیس می‌گیری باید دقیقاً len(ids) باشد، نه یکی بیشتر. راهِ سریعِ پیدا کردنش: بلافاصله قبل از خطِ خطادار print(i, len(ids)) بگذار و ببین i تا کجا رفته. این خطا در فصل‌های بعد که مرزهای پیچیده‌تری می‌نویسیم بارها برمی‌گردد و همیشه همین یک راهِ حل را دارد.

🤖 از دستیارت بپرس: «چرا حلقهٔ داخلی از i + 1 شروع می‌شود و نه از 0؟» بعد این را هم بپرس: «اگر از 0 شروع شود، جوابِ تابع عوض می‌شود یا فقط زمانش؟» — جوابِ درست این است که هر دو عوض می‌شوند، و دلیلِ عوض شدنِ جواب مهم‌تر از دلیلِ عوض شدنِ زمان است. خودت هم امتحانش کن.

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

در فصل بعد#

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