# فصل ۰۱ — کدی که درست کار می‌کند و غیرقابلِ استفاده است

<div dir="rtl">

# فصل ۰۱ — کدی که درست کار می‌کند و غیرقابلِ استفاده است

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

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

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

![یک ماشینِ مقایسه‌گرِ دستی کنارِ قیفی صد برابر بزرگ‌تر از خودش](/lesson-assets/t1-s01-works-but-unusable/prompt/01-image-comparator-and-hopper.png)

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

- زمانِ اجرا را یکی از ویژگی‌های برنامه ببینی، نه یک اتفاق
- بگویی `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` است که در این فصل **عمداً** به آن دست نمی‌زنیم. فصلِ بعد خط به خط می‌سازدش و همان‌جا می‌گوید چرا اندازه‌گیریِ این فصل کافی نیست.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-1-measure-then-predict/session-01-works-but-unusable.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

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

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

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

</div>

```python
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)
```

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

<div dir="rtl">

**این تابع درست است.** نه تقریباً درست و نه معمولاً درست: هر کدی که دو بار در فهرست باشد پیدا می‌شود، و اگر تکراری نباشد `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` را دو برابر کنیم، زمان چند برابر می‌شود؟ دو برابر؟ چهار برابر؟ همان‌قدر؟ جوابت را یادداشت کن؛ چند خط پایین‌تر جدول را می‌بینی.

</div>

```python
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)
```

```text-approx
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
```

<div dir="rtl">

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

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

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

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

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

</div>

```python
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)}")
```

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

<div dir="rtl">

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

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

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

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

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

</div>

```python
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:,}")
```

```text-approx
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
```

<div dir="rtl">

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

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

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

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

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

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

</div>

```python
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}")
```

```text
IndexError: list index out of range
```

<div dir="rtl">

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

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

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `n` | اِن | اندازهٔ ورودی؛ هر بار باید بگویی دقیقاً چه چیزی را می‌شمارد |
| runtime | ران‌تایم | زمانی که اجرای یک کد طول می‌کشد |
| worst case | وُرست کیس | ورودی‌ای که کد را به بیشترین کار مجبور می‌کند |
| extrapolation | اکستراپولیشن | بردنِ یک قاعده بیرون از بازه‌ای که در آن اندازه‌گیری شده |
| scalability | اسکیلبیلیتی | اینکه با بزرگ شدنِ `n` چه بلایی سرِ هزینه می‌آید |

<div dir="rtl">

## تمرین‌ها

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

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

**تمرینِ ستاره‌دار ⭐:** بودجه را از نیم ثانیه به ده ثانیه ببر — یعنی **بیست برابر** — و دوباره بزرگ‌ترین `n` را پیدا کن. **حدس بزن چند برابر بزرگ‌تر می‌شود، بعد اجرا کن.** جوابِ اندازه‌گیری‌شده را با حدست مقایسه کن و بنویس چرا بیست برابر بودجه، بیست برابر `n` نمی‌دهد. (راهنمایی: اگر زمان با مربعِ `n` می‌رود، برای بیست برابر شدنِ زمان `n` چند برابر می‌شود؟)

## در فصل بعد

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

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t1/s01-works-but-unusable (یادستان, Yaadestan)
