# فصل ۰۶ — پروژهٔ نهایی: یک مسئلهٔ واقعی، دو ساختار، یک تصمیمِ مستند

<div dir="rtl">

# فصل ۰۶ — پروژهٔ نهایی: یک مسئلهٔ واقعی، دو ساختار، یک تصمیمِ مستند

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

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

دو نامزد می‌سازیم که **جوابِ کاملاً یکسان** می‌دهند. نامزدِ اول هر پرسش را در حدودِ **یک‌دهم میکروثانیه** جواب می‌دهد و حافظه‌اش با `n` **اصلاً بزرگ نمی‌شود**؛ نامزدِ دوم صدها برابر کندتر است و حافظه‌اش خطی رشد می‌کند.

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

![دو ماشینِ پیشنهاددهنده کنارِ هم، یکی با کشوهای از پیش پرشده و یکی با یک ریلِ مرتب](/lesson-assets/t6-s06-capstone/prompt/01-image-two-candidates.png)

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

- شکلِ یک مسئلهٔ واقعی را قبل از انتخابِ ساختار بنویسی
- دو نامزد را در زمان، گام و حافظه بسنجی و برابریِ جوابشان را ثابت کنی
- تشخیص بدهی کِی «سریع‌تر و کم‌حافظه‌تر» هنوز انتخابِ غلط است
- گزارشی بنویسی که شرطِ باطل شدنش هم در آن باشد

## قبل از شروع

**از فصلِ ۱:** برگهٔ شکلِ مسئله. **از فصلِ ۳:** معاملهٔ حافظه و زمان. **از فصلِ ۵:** نُه بندِ گزارش. **از ترمِ ۴ فصلِ ۷:** `bisect` روی فهرستِ مرتب.

</div>

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

<div dir="rtl">

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

## ۱. صورتِ مسئله، و شکلش

سیاههٔ جست‌وجوی یک سایت را داریم: هر عبارت با تعدادِ دفعاتی که جست‌وجو شده. کاربر شروع به تایپ می‌کند و ما باید **پنج عبارتِ پرتکرارِ شروع‌شونده با آنچه تا حالا تایپ کرده** را نشان بدهیم.

**برگهٔ شکلِ مسئله، قبل از هر کدی:**

1. **الگوی دسترسی:** ساختار یک بار شبانه ساخته می‌شود و بعد میلیون‌ها بار پرسیده می‌شود؛ هیچ درجِ زنده‌ای نداریم.
2. **نسبتِ خواندن به نوشتن:** به‌شدت خواندن‌محور — پس طبقِ فصلِ ۱، پیش‌محاسبه صرف می‌کند.
3. **بازهٔ واقعیِ `n`:** ده هزار تا هشتاد هزار عبارتِ یکتا.

**و یک قیدِ چهارم که هیچ‌کدام از این سه نمی‌گویدش:** کاربر از حرفِ اول تایپ می‌کند و نمی‌ایستد — **پس طولِ پیشوند هر عددی می‌تواند باشد.**

</div>

```python
from bisect import bisect_left

LETTERS = "abcdefghij"
PREFIX = 3
TOP = 5
LADDER = [10_000, 20_000, 40_000, 80_000]


def make_queries(n, seed=SEED):
    """n عبارتِ یکتا، هرکدام با تعدادِ دفعاتِ جست‌وجو."""
    rng = random.Random(seed)
    seen, out = set(), []
    while len(out) < n:
        phrase = "".join(rng.choice(LETTERS) for _ in range(rng.randint(5, 9)))
        if phrase not in seen:
            seen.add(phrase)
            out.append((phrase, rng.randrange(1, 10_000)))
    return out


data = {n: make_queries(n) for n in LADDER}
print("سه عبارتِ اول:", data[10_000][:3])
```

```text
سه عبارتِ اول: [('babjabbf', 3880), ('aafjh', 7595), ('bcbaih', 4094)]
```

<div dir="rtl">

## ۲. دو نامزد، یک جواب

**نامزدِ الف** برای **هر پیشوندِ سه‌حرفیِ ممکن** پنج عبارتِ برترش را از پیش حساب می‌کند و در یک `dict` می‌گذارد. **نامزدِ ب** فقط یک فهرستِ مرتب نگه می‌دارد و در هر پرسش با `bisect` جای شروعِ پیشوند را پیدا می‌کند و همان بازه را می‌خواند.

</div>

```python
def build_table(pairs):
    """نامزد الف — پنج برترِ هر پیشوندِ سه‌حرفی، از پیش."""
    groups = {}
    for phrase, hits in pairs:
        groups.setdefault(phrase[:PREFIX], []).append((phrase, hits))
    return {p: sorted(v, key=lambda ph: (-ph[1], ph[0]))[:TOP]
            for p, v in groups.items()}


def build_sorted(pairs):
    """نامزد ب — یک فهرستِ مرتب، به‌علاوهٔ ستونِ عبارت‌ها برای bisect."""
    ordered = sorted(pairs)
    return ordered, [phrase for phrase, _ in ordered]


def top_by_table(ready, prefix):
    return ready.get(prefix, [])


def top_by_scan(ordered, phrases, prefix):
    i = bisect_left(phrases, prefix)
    box = []
    while i < len(phrases) and phrases[i].startswith(prefix):
        box.append(ordered[i])
        i += 1
    return sorted(box, key=lambda ph: (-ph[1], ph[0]))[:TOP]


ready = {n: build_table(data[n]) for n in LADDER}
lists = {n: build_sorted(data[n]) for n in LADDER}
picker = random.Random(SEED)
asks = {n: [phrase[:PREFIX] for phrase, _ in picker.sample(data[n], 200)]
        for n in LADDER}
print("جوابِ دو نامزد در هر چهار اندازه یکی است؟",
      all(top_by_table(ready[n], p) == top_by_scan(lists[n][0], lists[n][1], p)
          for n in LADDER for p in asks[n]))
print("نمونه برای پیشوندِ", asks[20_000][0], ":",
      top_by_scan(lists[20_000][0], lists[20_000][1], asks[20_000][0])[:2])
```

```text
جوابِ دو نامزد در هر چهار اندازه یکی است؟ True
نمونه برای پیشوندِ fdf : [('fdfjahdbh', 8753), ('fdfebajf', 7676)]
```

<div dir="rtl">

**برابریِ جواب اول می‌آید، نه آخر** — و روی هر چهار اندازه، نه فقط یکی.

## ۳. جدولِ پرسش

> 🤔 **اول حدس بزن:** ستونِ نسبتِ هر دو نامزد را بنویس. **برای نامزدِ ب دقت کن:** بازه‌ای که `bisect` پیدا می‌کند، با `n` بزرگ‌تر می‌شود یا نه؟

</div>

```python
for name, fn in (("الف — جدولِ آماده",
                  lambda k: [top_by_table(ready[k], p) for p in asks[k]]),
                 ("ب — مرتب + bisect",
                  lambda k: [top_by_scan(lists[k][0], lists[k][1], p) for p in asks[k]])):
    print(f"— نامزد {name} · µs به‌ازای هر پرسش")
    table([(n, 1e6 * clock(lambda k=n, f=fn: f(k), repeat=3) / 200) for n in LADDER],
          "µs", ",.3f")
    print()
```

```text-approx
— نامزد الف — جدولِ آماده · µs به‌ازای هر پرسش
         n                µs     نسبت به سطر قبل
    10,000             0.093                   —
    20,000             0.097                1.04
    40,000             0.095                0.99
    80,000             0.095                1.00

— نامزد ب — مرتب + bisect · µs به‌ازای هر پرسش
         n                µs     نسبت به سطر قبل
    10,000             3.418                   —
    20,000             5.894                1.72
    40,000            11.890                2.02
    80,000            27.470                2.31
```

<div dir="rtl">

**`1.0` در برابرِ `2`: `O(1)` در برابرِ `O(n)`.** و در `n = 80,000` نامزدِ الف حدودِ **سیصد برابر** جلوتر است. برای فهمیدنِ اینکه چرا نامزدِ ب رشد می‌کند، گام‌هایش را می‌شماریم:

</div>

```python
def scan_steps(phrases, prefix):
    """گامِ bisect، و اندازهٔ بازه‌ای که بعدش پیموده می‌شود."""
    lo, hi, steps = 0, len(phrases) - 1, 0
    while lo < hi:
        steps += 1
        mid = (lo + hi) // 2
        if phrases[mid] < prefix:
            lo = mid + 1
        else:
            hi = mid
    i, width = bisect_left(phrases, prefix), 0
    while i < len(phrases) and phrases[i].startswith(prefix):
        width += 1
        i += 1
    return steps, width


print(f"{'n':>10}{'گامِ bisect':>14}{'اندازهٔ بازه':>16}{'مجموع':>10}")
for n in LADDER:
    pairs = [scan_steps(lists[n][1], p) for p in asks[n]]
    jumps = sum(s for s, _ in pairs) / 200
    width = sum(w for _, w in pairs) / 200
    print(f"{n:>10,}{jumps:>14.2f}{width:>16.1f}{jumps + width:>10.1f}")
```

```text
         n   گامِ bisect    اندازهٔ بازه     مجموع
    10,000         13.41            11.0      24.4
    20,000         14.30            20.9      35.2
    40,000         15.39            41.2      56.6
    80,000         16.37            79.8      96.2
```

<div dir="rtl">

**دو ستونِ کاملاً متفاوت.** ستونِ `bisect` با هر دو برابر شدنِ `n` **یک گام** اضافه می‌کند — `O(log n)` — و ستونِ بازه **دو برابر** می‌شود، چون تعدادِ پیشوندهای ممکن ثابت است و عبارت‌های بیشتر در همان هزار گروه جا می‌گیرند. **رشدِ نامزدِ ب از جست‌وجو نمی‌آید، از خواندنِ بازه می‌آید.**

## ۴. حافظه، و انتظاری که برعکس درمی‌آید

فصلِ ۳ گفت پیش‌محاسبه با حافظه پرداخته می‌شود. **اینجا برعکس است:**

</div>

```python
print(f"{'n':>10}{'الف (بایت)':>14}{'ب (بایت)':>14}{'نسبتِ ب':>10}{'الف/ب':>10}")
last = None
for n in LADDER:
    box = ready[n]
    small = sys.getsizeof(box) + sum(sys.getsizeof(v) for v in box.values())
    big = sys.getsizeof(lists[n][0]) + sys.getsizeof(lists[n][1])
    step = "—" if last is None else f"{big / last:.2f}"
    print(f"{n:>10,}{small:>14,}{big:>14,}{step:>10}{small / big:>10.2f}")
    last = big
print("\nکلیدهای جدولِ الف:", len(ready[80_000]), "· پیشوندِ ممکن:",
      len(LETTERS) ** PREFIX)
```

```text
         n    الف (بایت)      ب (بایت)   نسبتِ ب     الف/ب
    10,000       121,800       165,232         —      0.74
    20,000       122,032       333,072      2.02      0.37
    40,000       122,032       671,120      2.01      0.18
    80,000       122,032     1,352,016      2.01      0.09

کلیدهای جدولِ الف: 1000 · پیشوندِ ممکن: 1000
```

<div dir="rtl">

**حافظهٔ نامزدِ الف با `n` بزرگ نمی‌شود.** جدولش هزار کلید دارد و هر کلید فقط پنج عبارت — پس اندازه‌اش به **تعدادِ پیشوندها** بند است، نه به تعدادِ عبارت‌ها. ستونِ «نسبتِ ب» هم `2.01` است: **حافظهٔ نامزدِ ب `O(n)` است** و در `n = 80,000` بیش از **یازده برابرِ** الف جا می‌گیرد.

**پس نامزدِ الف هم سریع‌تر است و هم کم‌حافظه‌تر.** ظاهراً تصمیم تمام است.

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

## ۵. پرسشی که نامزدِ الف بی‌صدا غلط جواب می‌دهد

قیدِ چهارمِ بخشِ ۱: **کاربر از حرفِ اول تایپ می‌کند.**

</div>

```python
ordered, phrases = lists[80_000]
print(f"{'پیشوند':>10}{'الف':>8}{'ب':>8}   نمونه از جوابِ ب")
for prefix in ("ab", "abc", "abcd"):
    a = top_by_table(ready[80_000], prefix)
    b = top_by_scan(ordered, phrases, prefix)
    print(f"{prefix:>10}{len(a):>8}{len(b):>8}   {b[:1]}")
```

```text
    پیشوند     الف       ب   نمونه از جوابِ ب
        ab       0       5   [('abade', 9997)]
       abc       5       5   [('abccahhb', 9919)]
      abcd       0       5   [('abcdicaa', 8262)]
```

<div dir="rtl">

**در طولِ سه، هر دو درست‌اند. در طولِ دو و چهار، نامزدِ الف فهرستِ خالی می‌دهد و هیچ خطایی هم نمی‌دهد.**

کاربری که «abcd» تایپ کرده پنج پیشنهاد داشت و **هیچ‌کدام را نمی‌بیند.** از دیدِ برنامه هیچ اتفاقی نیفتاده: نه استثنایی، نه سطری در سیاهه. **این همان دستهٔ عیبی است که ترمِ ۳ فصلِ ۷ و فصلِ ۴ همین ترم هم نشانش دادند، و تنها راهِ پیدا شدنش مقایسه با یک نسخهٔ درست بود.**

**و دقت کن که نامزدِ الف در جدولِ زمان و در جدولِ حافظه هر دو بُرد.** هیچ‌کدام از آن دو جدول نمی‌توانستند این را نشان بدهند.

> 🔧 **اگر کار نکرد:** رایج‌ترین اشتباه در نوشتنِ نامزدِ ب این است که `bisect` را روی فهرستِ جفت‌ها بزنی، نه روی ستونِ عبارت‌ها:

</div>

```python
try:
    bisect_left(ordered, "abc")
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
print("درستش:", bisect_left(phrases, "abc"))
```

```text
TypeError: '<' not supported between instances of 'tuple' and 'str'
درستش: 953
```

<div dir="rtl">

**پیام دقیق است: یک `tuple` با یک رشته مقایسه نمی‌شود.** به همین دلیل `build_sorted` دو چیز برمی‌گرداند — خودِ جفت‌ها و **ستونِ جداگانهٔ عبارت‌ها** — و `bisect` فقط با دومی کار دارد.

> ✅ **چک کن:** `PREFIX` را به `4` تغییر بده و کلِ نوت‌بوک را از بالا اجرا کن. **حالا سطرِ `abcd` جدولِ بخشِ ۵ باید برای نامزدِ الف هم جواب بدهد و سطرِ `abc` خالی شود** — عیب جابه‌جا می‌شود، نه رفع. اگر هر دو سطر جواب دادند، `PREFIX` را جایی به‌صورتِ عددِ ثابت نوشته‌ای.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** دو نامزد روی یک سیاههٔ واحد و همان دویست پیشوندِ ثابت، با جوابِ برابرِ تأییدشده در هر چهار اندازه. **در کدام بازهٔ `n`؟** ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ عبارتِ یکتا، الفبای ده‌حرفی، پیشوندِ سه‌حرفی. **با چند تکرار، و کمینه یا میانگین؟** جدولِ گام و جدولِ حافظه یک اجرا و قطعی؛ جدولِ زمان سه تکرار به‌علاوهٔ گرم‌کننده، کمینه.

## ۶. گزارشِ نهایی

**نُه بندِ فصلِ ۵، برای این پروژه:**

1. **شکلِ مسئله:** یک بار ساخت، میلیون‌ها پرسش، بدونِ درجِ زنده — **به‌علاوهٔ قیدِ چهارم: طولِ پیشوند ثابت نیست.**
2. **نامزدها:** الف جدولِ از پیش ساخته برای پیشوندِ سه‌حرفی؛ ب فهرستِ مرتب با `bisect`.
3. **ورودی و بذر:** `make_queries` با بذرِ ثابتِ همین دوره، عبارت‌های یکتا از الفبای ده‌حرفی.
4. **بازهٔ `n`:** ۱۰٬۰۰۰ تا ۸۰٬۰۰۰.
5. **پروتکل:** سه تکرار به‌علاوهٔ گرم‌کننده، کمینه؛ گام و حافظه قطعی.
6. **برابریِ جواب:** فقط برای پیشوندِ **سه‌حرفی** تأیید شد. برای طول‌های دیگر **برابر نیست**.
7. **نتیجه:** الف در زمان حدودِ سیصد برابر جلو، در حافظه بیش از یازده برابر کم‌خرج‌تر — **و در پوششِ پرسش بازنده.**
8. **تصمیم و شرطِ باطل شدنش: نامزدِ ب.** الف فقط اگر پذیرفته شود که پیشوند **همیشه** دقیقاً سه حرف است، یا اگر برای هر طولِ ممکن جدولِ جداگانه ساخته شود — که چون جدولِ الف یک‌بُعدی است، حافظه‌اش با هر حرفِ اضافه **ده برابر** می‌شود، همان `K`ی که فصلِ ۳ نشان داد ده برابر می‌شود (آن‌جا جدول دوبُعدی بود و حافظه صد برابر می‌شد).
9. **حافظه، به بایت:** در `n = 80,000` الف `122,032` بایت و ب `1,352,016` بایت. **چه چیزی شمرده شده:** خودِ ظرف به‌علاوهٔ ظرف‌های داخلش. **چه چیزی نشده:** خودِ جفت‌ها و رشته‌های عبارت — چون نامزدها **همان اشیاء** را ارجاع می‌دهند و کپی‌شان نمی‌کنند (همان تفکیکی که فصلِ ۳ بخشِ ۴ گذاشت). **با شمردنِ آن‌ها، الف با پنج هزار جفتش حدودِ ۸۲۰ کیلوبایت می‌شد و ب با هشتاد هزارتا حدودِ ۱۲٫۵ مگابایت، و نسبتشان از یازده به پانزده می‌رفت** — پس این انتخاب روی نتیجه اثر دارد و باید نوشته شود.

**بندِ ششم مهم‌ترین بندِ این گزارش است.** «جوابِ دو نامزد یکی است» در بخشِ ۲ **یک جملهٔ مشروط بود** و شرطش تا بخشِ ۵ دیده نشد. **گزارشی که آن شرط را ننویسد، دو صفحه عدد است که یک تصمیمِ غلط را ثابت می‌کند.**

> 🤖 **از دستیارت بپرس:** **جدولِ بخشِ ۵ را جلویش بگذار:** «کدام نامزد را انتخاب کنم؟» بعد بپرس **«اگر بدانی طولِ پیشوند همیشه سه است، جوابت عوض می‌شود؟»** — جوابِ درست باید عوض شود. **اگر با هر دو صورت یک جواب داد، هنوز به شکلِ مسئله نگاه نکرده.**

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| autocomplete | اتوکامپلیت | پیشنهادِ ادامهٔ عبارت هنگامِ تایپ |
| coverage | کاوریج | اینکه یک ساختار چه کسری از پرسش‌های ممکن را اصلاً می‌تواند جواب بدهد |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: نامزدِ الف در دو جدول از سه جدول برنده بود؛ چرا انتخاب نشد؟

**تمرینِ اجباری:** نامزدِ سومی بساز که برای **هر** طولِ پیشوند از یک تا چهار جدولِ آماده داشته باشد. حافظه‌اش را اندازه بگیر و کنارِ دو نامزدِ دیگر بگذار. **سؤالِ اصلی: از کدام طولِ پیشوند به بعد این نامزد از نامزدِ ب پرخرج‌تر می‌شود؟** جوابت باید یک عدد باشد و از جدول بیاید، نه از شهود.

**تمرینِ ستاره‌دار ⭐:** ساختارِ درختیِ ترمِ ۵ نامزدِ چهارمی است که این پروژه نساختش. **قبل از نوشتن پیش‌بینی کن** گام‌های پرسشش با کدام‌یک از دو ستونِ جدولِ بخشِ ۳ هم‌رفتار است. بعد بسازش، جدولِ چهار اندازه‌ای‌اش را بگیر و خطای پیش‌بینی‌ات را بنویس. **و در آخر، بندِ هشتمِ گزارش را دوباره بنویس** — با شرطِ باطل شدنِ تازه‌اش.

## در فصل بعد

**دوره تمام شد.** شش ترم و چهل و نه فصل، و همه‌شان دورِ یک جمله چرخیدند:

> **`Big-O` یک پیش‌بینی است، نه یک برچسب — و پیش‌بینی‌ای که آزمون نداده، حدس است.**

ترمِ ۱ یاد داد صادقانه اندازه بگیری و مرتبه را از ستونِ نسبت بخوانی. ترم‌های ۲ تا ۵ ساختار ساختند و هزینهٔ هر عملیاتشان را **خودت** اندازه گرفتی. و این ترم سه خانه به هر تصمیم اضافه کرد: الگوی دسترسی، نسبتِ خواندن به نوشتن، و بازهٔ واقعیِ `n`.

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

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t6/s06-capstone (یادستان, Yaadestan)
