# فصل ۰۴ — کِی بس کنی

<div dir="rtl">

# فصل ۰۴ — کِی بس کنی

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

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

یک تابع را چهار بار می‌نویسیم. نسخهٔ دوم یک بردِ واقعی می‌گیرد. **نسخهٔ سوم یکی-دو درصد بهتر به‌نظر می‌رسد و بازهٔ اندازه‌گیریِ دو نسخه روی هم می‌افتد** — یعنی آن یکی-دو درصد هیچ چیزی نیست. **و نسخهٔ چهارم از همهٔ قبلی‌ها سریع‌تر است، هیچ خطایی نمی‌دهد، و جوابِ غلط برمی‌گرداند.**

![چراغی که سه کلیدِ توقفِ جداگانه دارد و هر کدام به‌تنهایی خاموشش می‌کند](/lesson-assets/t6-s04-when-to-stop/prompt/01-image-three-stops.png)

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

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

## قبل از شروع

**از ترمِ ۱ فصلِ ۳:** پراکندگیِ اندازه‌گیری و آستانهٔ باور. **از ترمِ ۱ فصلِ ۹:** ثابتِ پنهان. **از فصلِ ۱:** برگهٔ شکلِ مسئله.

</div>

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

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-6-choose-and-defend/session-04-when-to-stop.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. معیارِ توقف، پیش از اولین خط کد

مسئله: از یک سیاههٔ رویداد، تعدادِ رکوردِ هر شهر را بشمار.

**برگهٔ شکلِ مسئله، طبقِ فصلِ ۱:** سیاهه یک بار خوانده می‌شود و یک بار شمرده؛ **بازهٔ واقعیِ `n` حداکثر بیست هزار سطر است** و هر دقیقه یک فایل می‌آید.

**و یک سطرِ چهارم که فقط این فصل اضافه‌اش می‌کند — معیارِ توقف:**

> **هدف: بیست هزار سطر، زیرِ پنج میلی‌ثانیه. وقتی رسید، بس است.**

**این جمله باید قبل از اولین بهینه‌سازی نوشته شود، نه بعدش.** معیاری که بعد از دیدنِ نتیجه نوشته شود، همیشه دقیقاً همان‌جایی می‌افتد که کار تمام شده.

</div>

```python
CITIES = ("shiraz", "tabriz", "rasht", "yazd", "ahvaz", "kerman", "mashhad", "sari")
N = 20_000


def make_log(n, seed=SEED):
    """هر سطر هفت فیلدِ جداشده با tab؛ شهر فیلدِ دوم است."""
    rng = random.Random(seed)
    return ["\t".join((f"{i:07d}", rng.choice(CITIES), f"{rng.randrange(1000)}",
                       "ok", f"{rng.randrange(100)}", "-", "-"))
            for i in range(n)]


def v1(rows):
    """نسخهٔ اول — سطر را کامل می‌شکند."""
    counts = {}
    for line in rows:
        city = line.split("\t")[1]
        counts[city] = counts.get(city, 0) + 1
    return counts


log = make_log(N)
print("یک سطرِ نمونه:", repr(log[0]))
print("شمارش:", sorted(v1(log).items())[:3], "...")
```

```text
یک سطرِ نمونه: '0000000\tsari\t119\tok\t0\t-\t-'
شمارش: [('ahvaz', 2479), ('kerman', 2545), ('mashhad', 2531)] ...
```

<div dir="rtl">

## ۲. نسخهٔ دوم: بردی که واقعی است

`split("\t")` هر سطر را به هفت تکه می‌شکند و ما فقط تکهٔ دوم را می‌خواهیم. `split("\t", 2)` بعد از دو جدایی می‌ایستد.

</div>

```python
def v2(rows):
    """نسخهٔ دوم — فقط تا فیلدِ دوم بشکن."""
    counts = {}
    for line in rows:
        city = line.split("\t", 2)[1]
        counts[city] = counts.get(city, 0) + 1
    return counts


def pieces_built(rows, limit=-1):
    """چند رشتهٔ تازه ساخته می‌شود — عددی قطعی، مستقل از ماشین."""
    return sum(len(line.split("\t", limit)) for line in rows)


print("جوابِ دو نسخه یکی است؟", v1(log) == v2(log))
print("— رشته‌های ساخته‌شده، نسخهٔ اول")
table([(n, pieces_built(make_log(n))) for n in (5_000, 10_000, 20_000, 40_000)],
      "رشته", ",d")
print("\n— رشته‌های ساخته‌شده، نسخهٔ دوم")
table([(n, pieces_built(make_log(n), 2)) for n in (5_000, 10_000, 20_000, 40_000)],
      "رشته", ",d")
```

```text
جوابِ دو نسخه یکی است؟ True
— رشته‌های ساخته‌شده، نسخهٔ اول
         n              رشته     نسبت به سطر قبل
     5,000            35,000                   —
    10,000            70,000                2.00
    20,000           140,000                2.00
    40,000           280,000                2.00

— رشته‌های ساخته‌شده، نسخهٔ دوم
         n              رشته     نسبت به سطر قبل
     5,000            15,000                   —
    10,000            30,000                2.00
    20,000            60,000                2.00
    40,000           120,000                2.00
```

<div dir="rtl">

**هر دو `O(n)` — ستونِ نسبت دقیقاً `2.00` — و ثابتشان فرق دارد: هفت رشته در برابرِ سه.** این همان تفکیکِ ترمِ ۱ فصلِ ۹ است: **مرتبه عوض نشد، ثابت عوض شد.**

</div>

```python
for name, fn in (("نسخهٔ ۱", v1), ("نسخهٔ ۲", v2)):
    print(f"{name}: {1000 * clock(lambda f=fn: f(log), repeat=7):>6.3f} ms")
```

```text-approx
نسخهٔ ۱:  5.067 ms
نسخهٔ ۲:  4.205 ms
```

<div dir="rtl">

**`5.07` به `4.21` — حدودِ ۱٫۲ برابر، و عدد زیرِ پنج میلی‌ثانیه آمد.**

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

## ۳. معیارِ دوم: بهبودی که از نوسان کوچک‌تر است

نسخهٔ سوم یک ترفندِ کوچک می‌زند: به‌جای `counts.get(city, 0) + 1`، مستقیم `counts[city] += 1` و `except KeyError` برای بارِ اول. چون شهرها فقط هشت تا هستند، آن `except` تقریباً هرگز اجرا نمی‌شود.

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

</div>

```python
def v3(rows):
    """نسخهٔ سوم — همان کار، با try/except به‌جای get."""
    counts = {}
    for line in rows:
        city = line.split("\t", 2)[1]
        try:
            counts[city] += 1
        except KeyError:
            counts[city] = 1
    return counts


print("جوابِ نسخهٔ ۳ با نسخهٔ ۲ یکی است؟", v2(log) == v3(log))
runs2 = [1000 * clock(lambda: v2(log), repeat=5) for _ in range(15)]
runs3 = [1000 * clock(lambda: v3(log), repeat=5) for _ in range(15)]
for name, runs in (("نسخهٔ ۲", runs2), ("نسخهٔ ۳", runs3)):
    print(f"{name}: کمینه {min(runs):.3f} · بیشینه {max(runs):.3f} ms"
          f" · پراکندگی {100 * (max(runs) - min(runs)) / min(runs):>5.1f} درصد")
print(f"بهبودِ اسمیِ نسخهٔ ۳ نسبت به نسخهٔ ۲: "
      f"{100 * (min(runs2) - min(runs3)) / min(runs2):.1f} درصد")
print("دو بازه روی هم می‌افتند؟",
      min(runs2) <= max(runs3) and min(runs3) <= max(runs2))
```

```text-approx
جوابِ نسخهٔ ۳ با نسخهٔ ۲ یکی است؟ True
نسخهٔ ۲: کمینه 4.189 · بیشینه 4.263 ms · پراکندگی   1.8 درصد
نسخهٔ ۳: کمینه 4.107 · بیشینه 4.232 ms · پراکندگی   3.0 درصد
بهبودِ اسمیِ نسخهٔ ۳ نسبت به نسخهٔ ۲: 1.9 درصد
دو بازه روی هم می‌افتند؟ True
```

<div dir="rtl">

**سطرِ آخر تصمیم را می‌گیرد: دو بازه روی هم می‌افتند.** نسخهٔ سوم در بدترین اجرایش کندتر از بهترین اجرای نسخهٔ دوم است، پس آن «بهبودِ اسمیِ» یکی-دو درصدی هیچ چیزی را ثابت نمی‌کند — **تفاوتی که از پراکندگیِ خودِ اندازه‌گیریِ تو کوچک‌تر است، تفاوت نیست** (ترمِ ۱ فصلِ ۳، که وعدهٔ همین فصل را داده بود).

پس نسخهٔ سوم **نه بهتر است و نه بدتر — نمی‌دانیم**. **معیارِ دوم همین است: وقتی برای دیدنِ بهبودت باید ابزارِ دقیق‌تری بسازی، بهبود آن‌قدر کوچک است که ارزشش را ندارد.**

> ✅ **چک کن:** `pieces_built(log, 1)` را صدا بزن. **باید دقیقاً `40000` بدهد** — دو تکه در هر سطر، ضربدرِ بیست هزار سطر. اگر عددِ دیگری داد، `limit` را به `split` پاس نداده‌ای و شمارنده دارد نسخهٔ اول را می‌شمارد.

## ۴. معیارِ سوم: سقف

معیارِ سوم قبل از هر اندازه‌گیری‌ای جواب می‌دهد. **[داربست ترمِ ۱ فصلِ ۶](/courses/darbast/lessons/term-1-code-you-can-trust/session-06-profiling) این را با عدد نشان داده و اینجا فقط نتیجه‌اش را به‌کار می‌بریم: سقفِ بهبودِ تو، سهمِ همان بخش از کلِ زمان است.**

</div>

```python
def loop_only(rows):
    for line in rows:
        pass


def split_only(rows):
    for line in rows:
        line.split("\t", 2)[1]


empty = clock(lambda: loop_only(log), repeat=7)
splitting = clock(lambda: split_only(log), repeat=7)
whole = clock(lambda: v2(log), repeat=7)
print(f"حلقهٔ خالی        : {1000 * empty:>6.3f} ms")
print(f"حلقه + split      : {1000 * splitting:>6.3f} ms")
print(f"کلِ نسخهٔ ۲        : {1000 * whole:>6.3f} ms")
print(f"سهمِ split         : {100 * (splitting - empty) / whole:>4.0f} درصد")
print(f"سهمِ شمارش         : {100 * (whole - splitting) / whole:>4.0f} درصد")
print(f"\nسقفِ هر بهینه‌سازیِ شمارش: {100 * (whole - splitting) / whole:.0f} درصد")
```

```text-approx
حلقهٔ خالی        :  0.099 ms
حلقه + split      :  2.232 ms
کلِ نسخهٔ ۲        :  4.486 ms
سهمِ split         :   48 درصد
سهمِ شمارش         :   50 درصد

سقفِ هر بهینه‌سازیِ شمارش: 50 درصد
```

<div dir="rtl">

**نسخهٔ سوم فقط بخشِ شمارش را دست زد، و آن بخش روی این ماشین حدودِ نیمی از زمان است.** حتی اگر شمارش را **مجانی** می‌کردیم، بیشتر از همان نصف نمی‌گرفتیم — و ما یکی-دو درصد گرفتیم، آن هم زیرِ نوسان.

**و حالا آخرین حساب، که تصمیم را قطعی می‌کند:**

</div>

```python
gain = min(runs2) - min(runs3)
print(f"صرفه‌جویی در هر فایل      : {gain:.3f} ms")
print(f"صرفه‌جویی در یک شبانه‌روز : {gain * 60 * 24 / 1000:.2f} ثانیه")
print(f"برای صرفه‌جوییِ یک ثانیه در یک اجرا، n باید "
      f"{N * (1000 / gain) / 1_000_000:,.0f} میلیون سطر شود")
print(f"بازهٔ اعلام‌شدهٔ n         : حداکثر {N:,} سطر")
```

```text-approx
صرفه‌جویی در هر فایل      : 0.081 ms
صرفه‌جویی در یک شبانه‌روز : 0.12 ثانیه
برای صرفه‌جوییِ یک ثانیه در یک اجرا، n باید 246 میلیون سطر شود
بازهٔ اعلام‌شدهٔ n         : حداکثر 20,000 سطر
```

<div dir="rtl">

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

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** سه نسخه از یک تابع روی یک سیاههٔ یکسان، با جوابِ برابرِ تأییدشده. **در کدام بازهٔ `n`؟** جدولِ رشد ۵٬۰۰۰ تا ۴۰٬۰۰۰ سطر؛ بقیهٔ اندازه‌گیری‌ها در `n = 20,000`، همان بازهٔ اعلام‌شده. **با چند تکرار، و کمینه یا میانگین؟** پنج تا هفت تکرار به‌علاوهٔ گرم‌کننده، کمینه — و برای پراکندگی، **پانزده گزارشِ کاملِ پروتکل**، چون خودِ نوسان موضوعِ اندازه‌گیری بود.

## ۵. هزینه‌ای که در هیچ جدولِ زمانی نیست

نسخهٔ چهارم آخرین وسوسه است: **شناسه همیشه هفت رقم است، پس شهر همیشه از نویسهٔ هشتم شروع می‌شود.** پس اصلاً `split` نکن.

</div>

```python
def v4(rows):
    """نسخهٔ چهارم — بدونِ split، با تکیه بر جای ثابتِ فیلدها."""
    counts = {}
    for line in rows:
        city = line[8:line.index("\t", 8)]
        try:
            counts[city] += 1
        except KeyError:
            counts[city] = 1
    return counts


print(f"نسخهٔ ۲: {1000 * clock(lambda: v2(log), repeat=7):>6.3f} ms")
print(f"نسخهٔ ۴: {1000 * clock(lambda: v4(log), repeat=7):>6.3f} ms")
```

```text-approx
نسخهٔ ۲:  4.556 ms
نسخهٔ ۴:  4.196 ms
```

<div dir="rtl">

**باز هم کمی جلوتر است.** حالا روزی که شناسه‌ها یک رقم بلندتر شوند:

</div>

```python
print("روی همین سیاهه، جوابِ نسخهٔ ۴ با نسخهٔ ۱ یکی است؟", v1(log) == v4(log))
longer = ["\t".join((f"{i:08d}", "shiraz", "1", "ok", "2", "-", "-")) for i in range(5)]
print("سیاهه‌ای با شناسهٔ هشت‌رقمی:")
print("  نسخهٔ ۱:", v1(longer))
print("  نسخهٔ ۴:", v4(longer))
print("  برابرند؟", v1(longer) == v4(longer))
```

```text
روی همین سیاهه، جوابِ نسخهٔ ۴ با نسخهٔ ۱ یکی است؟ True
سیاهه‌ای با شناسهٔ هشت‌رقمی:
  نسخهٔ ۱: {'shiraz': 5}
  نسخهٔ ۴: {'': 5}
  برابرند؟ False
```

<div dir="rtl">

**جوابِ غلط، بدونِ یک خط خطا، و سریع‌تر از نسخه‌های قبلی.** نویسهٔ هشتم حالا خودِ `tab` است، پس `city` رشتهٔ خالی درمی‌آید و کد **پنج رکوردِ شیراز را زیرِ نامِ هیچ می‌شمارد**. این بدترین دستهٔ عیب است و **تنها راهِ پیدا شدنش همان سطرِ `==` بود** — همان سطری که این دوره از ترمِ ۱ تکرارش می‌کند.

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

> 🔧 **اگر کار نکرد:** نسخهٔ چهارم روی سطرِ خراب همیشه هم ساکت نیست — گاهی می‌شکند، و آن حالتِ بهترش است:

</div>

```python
broken = ["0000001shiraz"]
try:
    v4(broken)
except ValueError as err:
    print(f"{type(err).__name__}: {err}")
try:
    v1(broken)
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
ValueError: substring not found
IndexError: list index out of range
```

<div dir="rtl">

**هر دو پیام دقیق‌اند:** نسخهٔ چهارم جدایی را پیدا نکرد و نسخهٔ اول فیلدِ دوم را. **روی سطرِ خراب هر دو می‌شکنند، و همین خوب است — بینِ خطا و جوابِ غلط، خطا همیشه برنده است.** چیزی که نسخهٔ چهارم را خطرناک می‌کند، سطرِ خراب نیست؛ سطرِ **سالمی** است که فرضِ نانوشته‌اش را نقض می‌کند.

> 🤖 **از دستیارت بپرس:** خروجیِ بخشِ ۳ را جلویش بگذار و بپرس: **«آیا نسخهٔ سوم بهتر است؟»** — جوابِ درست باید بگوید با این پراکندگی نمی‌شود گفت. بعد بپرس **«چطور مطمئن شوم؟»** و ببین آیا هزینهٔ همان اطمینان را هم حساب می‌کند یا نه.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| stopping criterion | استاپینگ کرایتریون | شرطی که پیش از شروع نوشته می‌شود و می‌گوید کِی کار تمام است |
| improvement ceiling | ایمپروومنت سیلینگ | بیشترین بهبودی که یک تغییر می‌تواند بدهد، حتی اگر بی‌نهایت خوب باشد |
| silent wrong answer | سایلنت رانگ آنسر | جوابِ غلطی که هیچ خطایی همراهش نیست |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: سه معیارِ توقفِ این فصل کدام‌اند؟

**تمرینِ اجباری:** معیارِ توقف را برای پروژهٔ ترمِ ۳ فصلِ ۷ (شمردنِ متن‌های یکتا) بنویس — با یک عددِ زمان و یک بازهٔ `n`. بعد نگاه کن کدام‌یک از سه روشِ آن فصل اول به معیارت می‌رسد. **سؤالِ اصلی: بقیهٔ آن فصل بعد از رسیدن به معیار، هدر رفته بود؟** جوابت باید بگوید یک اندازه‌گیری غیر از سرعت هم آن‌جا انجام شد.

**تمرینِ ستاره‌دار ⭐:** نسخهٔ پنجمی بنویس که **سریع‌تر از نسخهٔ دوم و بدونِ فرضِ نانوشته** باشد. **قبل از اجرا پیش‌بینی کن** چند درصد بهبود می‌گیری و آن را کنارِ سقفِ بخشِ ۴ بگذار. بعد اندازه بگیر، پراکندگی را هم گزارش کن، و **بگو بهبودت از نوسان بزرگ‌تر درآمد یا نه.** اگر نه، **همان جواب است** — نه یک شکست.

## در فصل بعد

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

**و خودش هم یک نتیجهٔ خلافِ انتظار دارد:** از چهار راهِ شمردن، ابزاری که مخصوصِ شمردن ساخته شده در یکی از دو حالتِ استفاده‌اش **از همه کندتر** درمی‌آید — بیش از دو برابرِ ساده‌ترین کدِ ممکن.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t6/s04-when-to-stop (یادستان, Yaadestan)
