# فصل ۰۲ — جدولِ تصمیم: هزینهٔ هر عملیات در هر ساختار

<div dir="rtl">

# فصل ۰۲ — جدولِ تصمیم: هزینهٔ هر عملیات در هر ساختار

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

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

**اول، خودِ جدول را با اندازه‌گیری راستی‌آزمایی می‌کند**: هفت خانه، یک ورودی، یک اجرا، یک ماشین. **دوم، ستونی را نشان می‌دهد که هیچ جدولِ هزینه‌ای ندارد** — و همان یک ستون کافی است که خانه‌ای با نمادِ درست، تصمیمِ غلط بسازد: `O(1)` در برابرِ `O(n)` در `n = 100` فقط **۱٫۶ برابر** درمی‌آید و در `n = 100,000` نزدیکِ **سی برابر**. **و سوم، خانه‌هایی را نام می‌برد که این دوره هرگز اندازه‌شان نگرفته** و پرکردنشان از حافظه، بدترین کاری است که می‌شود با یک جدول کرد.

![جدولِ شبکه‌ای که چند خانه‌اش با ابزار سنجیده می‌شود و چند خانه‌اش خالی مانده](/lesson-assets/t6-s02-decision-table/prompt/01-image-measured-grid.png)

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

- جدولِ یکپارچهٔ هزینه را برای شش ساختارِ این دوره بخوانی
- هر خانه‌اش را با یک `benchmark`ِ واحد راستی‌آزمایی کنی
- بگویی چرا نمادِ درست در یک خانه، تصمیمِ درست تولید نمی‌کند
- خانهٔ اندازه‌گیری‌نشده را از خانهٔ اندازه‌گیری‌شده تشخیص بدهی و خالی رهایش کنی

## قبل از شروع

**از ترمِ ۲ فصلِ ۸:** جدولِ هزینه برای ظرف‌های ترتیبی. **از ترمِ ۱ فصلِ ۹:** ثابتِ پنهان و نقطهٔ تقاطع. **از فصلِ ۱:** برگهٔ شکلِ مسئله.

</div>

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

<div dir="rtl">

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

## ۱. جدولِ یکپارچه

هر خانه یک مرتبه دارد و **شمارهٔ فصلی که آن را اندازه گرفته**. `✗` یعنی این ساختار اصلاً چنین عملیاتی ندارد، و **نسنجیده** یعنی این دوره اندازه‌اش نگرفته — که با «ارزان است» یکی نیست.

</div>

| ساختار | خواندن با اندیس | «هست یا نه؟» | افزودن | افزودن در ابتدا | حذف | کوچک‌ترین عضو | پرسشِ بازه‌ای |
|---|---|---|---|---|---|---|---|
| `list` | `O(1)` ت۲ف۱ | `O(n)` ت۳ف۱ | `O(1)` `amortised` ت۲ف۳ | `O(n)` ت۲ف۴ | از انتها `O(1)` · از ابتدا `O(n)` ت۲ف۴ · با مقدار `O(n)` همین فصل | نسنجیده | `O(n)` ت۴ف۹ |
| `deque` | `O(n)` ت۲ف۸ | نسنجیده | `O(1)` ت۲ف۷ | `O(1)` ت۲ف۷ | از هر دو سر `O(1)` ت۲ف۷ | نسنجیده | ✗ |
| فهرستِ مرتب + `bisect` | `O(1)` ت۲ف۱ | `O(log n)` ت۴ف۷ | `O(n)` ت۲ف۴ | `O(n)` ت۲ف۴ | `O(n)` ت۲ف۴ | نسنجیده | `O(log n)` + خروجی ت۴ف۹ |
| `set` / `dict` | ✗ | `O(1)` ت۳ف۵ | `O(1)` ت۳ف۳ | ✗ | `O(1)` همین فصل | نسنجیده | `O(n)` ت۴ف۹ |
| `BST` | ✗ | `O(log n)` / منحرف `O(n)` ت۵ف۳ | `O(log n)` / منحرف `O(n)` ت۵ف۳ · روی `n` کلیدِ مرتب، کلِ ساخت `O(n²)` ت۵ف۳ | ✗ | نسنجیده | نسنجیده | نسنجیده |
| `heap` | ✗ | نسنجیده | `O(log n)` بدترین · `O(1)` حالتِ متوسط · روی ورودیِ نزولی `n` درج `O(n log n)` ت۵ف۴ | ✗ | ریشه `O(log n)` ت۵ف۴ | `O(1)` ت۵ف۴ | ✗ |

<div dir="rtl">

**سطرِ `BST` دو مرتبه در یک خانه دارد و این غلطِ چاپی نیست.** ترمِ ۵ نشان داد که همان درخت روی ورودیِ مرتب منحرف می‌شود و `O(log n)`اش به `O(n)` می‌رسد. **خانه‌ای که به شکلِ ورودی بند است، بدونِ گفتنِ آن شکل نوشته نمی‌شود.**

**و خانهٔ «افزودن»ِ `heap` سه چیز می‌گوید، نه یکی**، چون ت۵ف۴ اندازه گرفت که `n` درج روی ورودیِ تصادفی خطی است و روی ورودیِ **نزولی** `O(n log n)`. **پس آن `O(1)` حالتِ متوسط است، نه `amortised`:** `amortised`ِ ت۲ف۳ تضمینی روی **هر** دنبالهٔ عملیات است، ولی حالتِ متوسط میانگینی روی ورودیِ تصادفی است که یک ورودیِ خاص می‌تواند از آن بیرون بزند. **تنها خانهٔ `amortised`ِ این جدول، «افزودن»ِ `list` است.**

**و ستونِ «حذف» تازه است و باید از اول می‌بود:** الگوی دسترسی — از ت۲ف۸ و فصلِ ۱ — سه چیز است، نه دو: **کجا اضافه می‌کنی، از کجا برمی‌داری، و چطور می‌خوانی.** **دو خانه از این ستون در همین فصل اندازه گرفته می‌شود و یکی‌اش «نسنجیده» می‌ماند** — حذف از `BST`، که این دوره هیچ‌وقت ننوشت و هیچ‌وقت نسنجید.

## ۲. چرا این جدول هنوز قابلِ اعتماد نیست

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

پس یک `benchmark`ِ واحد می‌سازیم: **یک مجموعه کلید، یک مجموعه پرسش، سه ظرف که از همان کلیدها ساخته می‌شوند، و همه در یک اجرا.**

</div>

```python
from bisect import bisect_left
from collections import deque

BENCH = [4_000, 8_000, 16_000, 32_000]
QUERIES = 200
rng = random.Random(SEED)
box = {}
for n in BENCH:
    keys = rng.sample(range(10 * n), n)
    asks = [rng.choice(keys) for _ in range(QUERIES)]
    box[n] = (keys, sorted(keys), set(keys), asks)

print("اندازه‌ها:", ", ".join(f"{n:,}" for n in BENCH), "· پرسش در هر اندازه:", QUERIES)
print("هر سه ظرف از کلیدهای یکسان ساخته شده‌اند؟",
      all(set(box[n][0]) == box[n][2] == set(box[n][1]) for n in BENCH))
```

```text
اندازه‌ها: 4,000, 8,000, 16,000, 32,000 · پرسش در هر اندازه: 200
هر سه ظرف از کلیدهای یکسان ساخته شده‌اند؟ True
```

<div dir="rtl">

**آن سطرِ دوم همان کاری است که ترمِ ۳ فصلِ ۷ با `==` می‌کرد:** تا وقتی سه ظرف واقعاً یک چیز را نگه ندارند، مقایسهٔ هزینهٔ خواندنشان بی‌معناست.

## ۳. راستی‌آزماییِ خانه‌ها با شمارشِ گام

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

> 🤔 **اول حدس بزن:** ستونِ نسبت را برای هر دو جدول بنویس. جدولِ `O(n)` باید `2` بدهد و جدولِ `O(log n)` باید `1`ِ چیزی بدهد. **حدس بزن آن «چیزی» چقدر است** — و اینکه با هر دو برابر شدنِ `n`، `bisect` چند گامِ اضافه برمی‌دارد.

</div>

```python
def linear_steps(items, asks):
    """گامِ «هست یا نه؟» روی list: تا پیدا شدن، یکی‌یکی."""
    total = 0
    for a in asks:
        for value in items:
            total += 1
            if value == a:
                break
    return total / len(asks)


def bisect_steps(ordered, asks):
    """گامِ همان پرسش روی فهرستِ مرتب: هر گام بازه را نصف می‌کند."""
    total = 0
    for a in asks:
        lo, hi = 0, len(ordered) - 1
        while lo <= hi:
            total += 1
            mid = (lo + hi) // 2
            if ordered[mid] == a:
                break
            if ordered[mid] < a:
                lo = mid + 1
            else:
                hi = mid - 1
    return total / len(asks)


print("— «هست یا نه؟» روی list")
table([(n, linear_steps(box[n][0], box[n][3])) for n in BENCH], "گام", ",.1f")
print("\n— «هست یا نه؟» روی فهرستِ مرتب با bisect")
table([(n, bisect_steps(box[n][1], box[n][3])) for n in BENCH], "گام", ",.2f")
```

```text
— «هست یا نه؟» روی list
         n               گام     نسبت به سطر قبل
     4,000           2,094.4                   —
     8,000           3,934.2                1.88
    16,000           7,671.2                1.95
    32,000          15,056.5                1.96

— «هست یا نه؟» روی فهرستِ مرتب با bisect
         n               گام     نسبت به سطر قبل
     4,000             11.10                   —
     8,000             12.05                1.09
    16,000             13.19                1.09
    32,000             14.05                1.07
```

<div dir="rtl">

**دو خانهٔ جدول تأیید شدند.** ستونِ اول به `2` نزدیک می‌شود — `O(n)` — و اینکه دقیقاً `2.00` نشد، چون هر پرسش در جای تصادفی‌ای از فهرست پیدا می‌شود و میانگینِ دویست پرسش هنوز کمی نوسان دارد.

ستونِ دوم `1.07` تا `1.09` است و **جالب‌ترین چیزِ این جدول در ستونِ گام است، نه ستونِ نسبت**: از `11.10` به `12.05` به `13.19` به `14.05`. **هر بار که `n` دو برابر می‌شود، حدودِ یک گام اضافه می‌شود** — و این دقیقاً تعریفِ `O(log n)` است.

> ✅ **چک کن:** یک اندازهٔ پنجم به `BENCH` اضافه کن — `64_000` — بعد سلولِ ساختِ `box` و جدولِ `bisect` را دوباره بگیر. **گامِ سطرِ تازه باید حدودِ یکی بیشتر از `32,000` باشد، نه دو برابر.** اگر دو برابر شد، ورودی را مرتب نداده‌ای و `bisect` دارد روی داده‌ای کار می‌کند که پیش‌شرطش را ندارد.

**حالا خانه‌ای از ستونِ تازه.** `values.remove(x)` دو کار پشتِ سرِ هم می‌کند: می‌گردد تا مقدار را پیدا کند، و بعد بقیه را یک خانه عقب می‌کشد.

> 🤔 **اول حدس بزن:** ستونِ نسبت را بنویس — **و مهم‌تر: حدس بزن گامِ حذف به محلِ مقدار در فهرست بستگی دارد یا نه.**

</div>

```python
victim_rng = random.Random(SEED)
DROPS = 2_000
victims = {n: victim_rng.sample(box[n][0], DROPS) for n in BENCH}


def remove_steps(items, dying):
    """گامِ list.remove(x) با دست: تا پیدا شدن بگرد، بعد بقیه را یک خانه عقب بکش."""
    work = list(items)
    total = 0
    for v in dying:
        i = 0
        while work[i] != v:
            total += 1
            i += 1
        total += 1 + (len(work) - i - 1)
        del work[i]
    return total / len(dying)


print("— حذفِ یک مقدار از list · گام به‌ازای هر حذف")
table([(n, remove_steps(box[n][0], victims[n][:QUERIES])) for n in BENCH], "گام", ",.1f")
```

```text
— حذفِ یک مقدار از list · گام به‌ازای هر حذف
         n               گام     نسبت به سطر قبل
     4,000           3,900.5                   —
     8,000           7,900.5                2.03
    16,000          15,900.5                2.01
    32,000          31,900.5                2.01
```

<div dir="rtl">

**نسبت `2.00` — یعنی `O(n)` — ولی عددِ خودِ ستونِ گام جالب‌تر است: `3,900.5` روی فهرستی با `4,000` عضو.**

**گامِ هر حذف تقریباً برابرِ طولِ فهرست است، هر جای فهرست که آن مقدار باشد.** اگر مقدار در خانهٔ `i` باشد، گشتن `i` گام می‌خورد، خودِ پیدا کردنش یک گام، و جابه‌جایی `n - i - 1` گام؛ **جمعشان همیشه `n` است و جای مقدار فقط سهمِ گشتن و جابه‌جایی را عوض می‌کند.** (عددِ `3,900.5` به‌جای `4,000` است چون فهرست در طولِ همین دویست حذف کوچک می‌شود.) **خانهٔ «حذف»ِ سطرِ `list` دیگر نقلِ قول نیست.**

## ۴. همان خانه‌ها روی ساعت

</div>

```python
def ask_all(container, asks):
    hits = 0
    for a in asks:
        if a in container:
            hits += 1
    return hits


def ask_bisect(ordered, asks):
    hits = 0
    for a in asks:
        i = bisect_left(ordered, a)
        if i < len(ordered) and ordered[i] == a:
            hits += 1
    return hits


for label, pick in (("list", 0), ("مرتب + bisect", None), ("set", 2)):
    print(f"— {label} · µs به‌ازای هر پرسش")
    if pick is None:
        rows = [(n, 1e6 * clock(lambda k=n: ask_bisect(box[k][1], box[k][3]),
                                repeat=3) / QUERIES) for n in BENCH]
    else:
        rows = [(n, 1e6 * clock(lambda k=n, i=pick: ask_all(box[k][i], box[k][3]),
                                repeat=3) / QUERIES) for n in BENCH]
    table(rows, "µs", ",.3f")
    print()
```

```text-approx
— list · µs به‌ازای هر پرسش
         n                µs     نسبت به سطر قبل
     4,000            13.247                   —
     8,000            26.668                2.01
    16,000            54.971                2.06
    32,000           105.782                1.92

— مرتب + bisect · µs به‌ازای هر پرسش
         n                µs     نسبت به سطر قبل
     4,000             0.211                   —
     8,000             0.232                1.10
    16,000             0.266                1.15
    32,000             0.290                1.09

— set · µs به‌ازای هر پرسش
         n                µs     نسبت به سطر قبل
     4,000             0.033                   —
     8,000             0.030                0.89
    16,000             0.033                1.10
    32,000             0.030                0.92
```

<div dir="rtl">

**سه ستونِ نسبت، سه مرتبه: نزدیکِ `2`، کمی بالای `1`، و `1`.** `O(n)` و `O(log n)` و `O(1)`، همان‌طور که جدول ادعا کرده بود.

و در `n = 32,000`، همان سه خانه روی ساعتِ این ماشین این‌اند: `106` میکروثانیه، `0.29` و `0.030`. **نسبتِ `list` به `set` بیش از سه هزار برابر درآمد** — و چنین عددی در هیچ خانه‌ای از جدولِ بخشِ ۱ نوشته نشده، چون جدول ثابت‌ها را نمی‌بیند.

**و حالا خانهٔ «حذف»ِ `set`، که شمارنده نمی‌تواند بگیردش:** گامِ `bisect` را می‌شد شمرد چون کدش مالِ خودمان بود، ولی داخلِ `set` را از بیرون نمی‌شود شمرد. **پس این یکی فقط با ساعت به دست می‌آید — و حذف ظرفش را عوض می‌کند، همان تلهٔ ترمِ ۱ فصلِ ۳.** راهِ حل همان است: یک بار «کپی + حذف» را بسنج، یک بار «فقط کپی»، و تفریق کن.

</div>

```python
def drop_from_list(items, dying):
    for v in dying:
        items.remove(v)
    return len(items)


def drop_from_set(bag, dying):
    for v in dying:
        bag.discard(v)
    return len(bag)


list_rows, set_rows = [], []
for n in BENCH:
    keys, _, bag, _ = box[n]
    dying = victims[n]
    copy_list = clock(lambda k=keys: list(k), repeat=5)
    copy_set = clock(lambda b=bag: set(b), repeat=5)
    with_list = clock(lambda k=keys, d=dying: drop_from_list(list(k), d), repeat=5)
    with_set = clock(lambda b=bag, k=keys: drop_from_set(set(b), k), repeat=5)
    list_rows.append((n, 1e6 * (with_list - copy_list) / DROPS))
    set_rows.append((n, 1e6 * (with_set - copy_set) / n))

print("— حذف با مقدار از list · µs به‌ازای هر حذف")
table(list_rows, "µs", ",.3f")
print("\n— حذف از set · µs به‌ازای هر حذف")
table(set_rows, "µs", ",.3f")
print(f"\nدر n = 32,000 نسبتشان {list_rows[-1][1] / set_rows[-1][1]:,.0f} برابر است.")
```

```text-approx
— حذف با مقدار از list · µs به‌ازای هر حذف
         n                µs     نسبت به سطر قبل
     4,000            12.170                   —
     8,000            28.119                2.31
    16,000            63.235                2.25
    32,000           135.498                2.14

— حذف از set · µs به‌ازای هر حذف
         n                µs     نسبت به سطر قبل
     4,000             0.051                   —
     8,000             0.039                0.75
    16,000             0.031                0.80
    32,000             0.035                1.12

در n = 32,000 نسبتشان 3,908 برابر است.
```

<div dir="rtl">

**ستونِ `list` نزدیکِ `2` است و ستونِ `set` حولِ `1` می‌لرزد: `O(n)` در برابرِ `O(1)`.** خانهٔ «حذف»ِ سطرِ `set` دیگر «نسنجیده» نیست.

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

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک پرسشِ واحد — «این کلید هست یا نه؟» — روی سه ظرف که از **کلیدهای یکسان** ساخته شده‌اند، با همان دویست پرسشِ ثابت؛ و بعد یک حذفِ واحد روی دو ظرف از همان کلیدها. **در کدام بازهٔ `n`؟** ۴٬۰۰۰ تا ۳۲٬۰۰۰ کلید، با کلیدهایی در بازه‌ای ده برابرِ `n` تا نسبتِ پیدا شدن ثابت بماند. **با چند تکرار، و کمینه یا میانگین؟** جدول‌های گام یک اجرا و قطعی؛ جدول‌های زمان سه تا پنج تکرار به‌علاوهٔ گرم‌کننده، کمینه، و جدولِ حذف با تفریقِ هزینهٔ کپی.

## ۵. ستونی که جدول ندارد

جدولِ بخشِ ۱ می‌گوید خواندن با اندیس روی `list` هزینهٔ ثابت دارد و روی `deque` هزینهٔ `O(n)`. **هر دو درست‌اند. حالا ببین آن «درست» در عمل چقدر است.**

> 🤔 **اول حدس بزن:** ستونِ نسبتِ `list` و ستونِ نسبتِ `deque` را جدا بنویس — و مخصوصاً حدس بزن `deque` از همان سطرِ اول عددِ `2` می‌دهد یا نه.

</div>

```python
READS = 2_000
picker = random.Random(SEED)
LADDER = [4_000, 8_000, 16_000, 32_000]
shelf = {}
for n in LADDER + [100, 100_000]:
    shelf[n] = (list(range(n)), deque(range(n)),
                [picker.randrange(n) for _ in range(READS)])


def read_all(container, idxs):
    total = 0
    for i in idxs:
        total += container[i]
    return total


print("— list · ns به‌ازای هر خواندن")
table([(n, 1e9 * clock(lambda k=n: read_all(shelf[k][0], shelf[k][2]), repeat=5) / READS)
       for n in LADDER], "ns", ",.1f")
print("\n— deque · ns به‌ازای هر خواندن")
table([(n, 1e9 * clock(lambda k=n: read_all(shelf[k][1], shelf[k][2]), repeat=5) / READS)
       for n in LADDER], "ns", ",.1f")
```

```text-approx
— list · ns به‌ازای هر خواندن
         n                ns     نسبت به سطر قبل
     4,000              32.7                   —
     8,000              35.2                1.08
    16,000              35.3                1.01
    32,000              37.5                1.06

— deque · ns به‌ازای هر خواندن
         n                ns     نسبت به سطر قبل
     4,000              58.7                   —
     8,000              78.8                1.34
    16,000             123.1                1.56
    32,000             224.5                1.82
```

<div dir="rtl">

**ستونِ `deque` از `1.34` شروع می‌شود و به `1.82` می‌رسد — نه از همان اول `2`.** دلیلش همان ثابتِ پنهانِ ترمِ ۱ فصلِ ۹ است: هر خواندن یک هزینهٔ ثابت دارد که به `n` ربطی ندارد، و در `n`های کوچک آن ثابت هنوز بخشِ بزرگی از عدد است. **مرتبه با بزرگ شدنِ `n` خودش را نشان می‌دهد، نه در سطرِ اول.**

حالا همان دو خانه، این بار با ستونی که هیچ جدولِ هزینه‌ای ندارد:

</div>

```python
print(f"{'n':>10}{'list (ns)':>12}{'deque (ns)':>13}{'چند برابر':>12}")
for n in [100] + LADDER + [100_000]:
    fast = 1e9 * clock(lambda k=n: read_all(shelf[k][0], shelf[k][2]), repeat=5) / READS
    slow = 1e9 * clock(lambda k=n: read_all(shelf[k][1], shelf[k][2]), repeat=5) / READS
    print(f"{n:>10,}{fast:>12.1f}{slow:>13.1f}{slow / fast:>12.1f}")
```

```text-approx
         n   list (ns)   deque (ns)   چند برابر
       100        22.8         36.2         1.6
     4,000        28.3         51.9         1.8
     8,000        29.2         69.9         2.4
    16,000        33.2        117.0         3.5
    32,000        35.6        201.1         5.6
   100,000        37.7       1029.9        27.3
```

<div dir="rtl">

**همان دو خانه، همان دو نماد، و ستونِ آخر از `1.6` تا `27.3` می‌رود.**

`O(1)` در برابرِ `O(n)` در نمادنویسی یک فاصلهٔ بی‌نهایت است. **در `n = 100` این فاصله کمتر از دو برابر است — یعنی عملاً هیچ.** اگر مسئلهٔ تو همیشه صد عضو دارد، انتخابِ `deque` به‌جای `list` برای خواندن با اندیس اشتباهِ قابلِ اغماضی است؛ اگر صد هزار عضو دارد، نیست.

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

## ۶. خانه‌هایی که این دوره اندازه‌شان نگرفته

در جدولِ بخشِ ۱ **نُه** خانه **نسنجیده** علامت خورده‌اند. **این عمدی است و مهم‌ترین بخشِ آن جدول است:**

1. **کوچک‌ترین عضو در `BST`** — ساختنش آسان است (تا آخر به چپ برو) ولی این دوره اندازه‌اش نگرفت.
2. **پرسشِ بازه‌ای در `BST`** — ترمِ ۵ درخت را ساخت و پیمایشش کرد، ولی «همهٔ کلیدهای بینِ این دو مقدار» را روی درخت اندازه نگرفت.
3. **حذف از `BST`** — و این از دو تای بالا صریح‌تر است: **این دوره حذف از `BST` را نه نوشت و نه اندازه گرفت.** ترمِ ۵ فصلِ ۳ فقط `bst_insert` و `bst_search` را ساخت؛ حذف سه حالتِ متفاوت دارد (برگ، یک فرزند، دو فرزند) و هیچ‌کدام کد نشده‌اند. **این خانه نه «گران» است و نه «ارزان»؛ خالی است.**
4. **«هست یا نه؟» روی `heap`** — `heap` فقط تضمین می‌کند ریشه کوچک‌ترین است؛ دربارهٔ بقیه هیچ ترتیبی ندارد، پس این پرسش باید کلِ ساختار را ببیند. **این را هم اندازه نگرفتیم.**
5. **کوچک‌ترین عضو در `list`، `deque`، فهرستِ مرتب و `set`/`dict`، و «هست یا نه؟» روی `deque`** — پنج خانه‌ای که جوابشان بدیهی به‌نظر می‌رسد و **دقیقاً به همین دلیل** اندازه گرفته نشدند. «بدیهی است» همان جمله‌ای است که خانهٔ نقل‌شده را شبیهِ خانهٔ اندازه‌گیری‌شده می‌کند.

**و یک خانه که اصلاً در جدول نیست:** `BST`ِ **متوازن**. ترمِ ۵ گفت متوازن‌سازی چیزی است که وجود دارد؛ **این دوره هیچ درختِ متوازنی نساخت و اندازه نگرفت.** پس سطرِ `BST` فقط دربارهٔ درختی حرف می‌زند که ما ساختیم.

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

> 🔧 **اگر کار نکرد:** بعضی خانه‌های جدول نه «گران» بلکه **اصلاً موجود نیستند**، و پایتون این را با خطا می‌گوید:

</div>

```python
try:
    deque(range(10))[3:5]
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: sequence index must be integer, not 'slice'
```

<div dir="rtl">

**`deque` برش ندارد.** خانهٔ «پرسشِ بازه‌ای» در سطرِ `deque` با `✗` علامت خورده و این خطا همان `✗` است. **تفاوتِ `✗` با یک عددِ بزرگ این است که `✗` وقتِ اجرا معلوم می‌شود، نه بعد از تحویل** — و همین آن را از خانهٔ کند بهتر می‌کند، نه بدتر.

> 🤖 **از دستیارت بپرس:** **جدولِ بخشِ ۵ را جلویش بگذار:** «چرا نسبتِ دو خانه با `n` عوض می‌شود، وقتی هر دو مرتبه‌شان ثابت مانده؟» بعد بپرس: **«هزینهٔ کوچک‌ترین عضو در یک `BST` چقدر است؟»** — هر جوابی داد، یادت باشد این دوره آن خانه را اندازه نگرفته. **جوابِ دستیار یک فرضیه است، نه یک اندازه‌گیری.**

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| decision table | دِسیژن تِیبل | جدولی که هزینهٔ هر عملیات را در هر ساختار کنارِ هم می‌گذارد |
| benchmark harness | بنچ‌مارک هارنس | چارچوبی که همهٔ نامزدها را با یک ورودی و در یک اجرا می‌سنجد |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا «نسنجیده» و `✗` در این جدول دو چیزِ کاملاً متفاوت‌اند؟

**تمرینِ اجباری:** خانهٔ «کوچک‌ترین عضو» را برای `list` و برای `heap` اندازه بگیر — با `min()` روی یکی و با `heap[0]` روی دیگری — در همان چهار اندازهٔ `BENCH`، با ستونِ نسبت. **دو سؤال:** ستونِ نسبتِ هر کدام چه عددی درآمد، و **از کدام `n` به بعد اختلافشان از نوسانِ اندازه‌گیریِ ترمِ ۱ فصلِ ۳ بزرگ‌تر می‌شود؟**

**تمرینِ ستاره‌دار ⭐:** یکی از چهار خانهٔ «نسنجیده»ی بندهای ۱ تا ۴ را انتخاب کن و **خودت پرش کن**: ساختار را بساز، جدولِ چهار اندازه‌ای‌اش را بگیر و مرتبه را از ستونِ نسبت اعلام کن. **قبل از اجرا پیش‌بینی کن** چه عددی می‌بینی، و بعد خطای پیش‌بینی‌ات را بنویس. **و در آخر: آیا حالا می‌شود آن خانه را با یک نماد پر کرد، یا هنوز باید کنارش نوشت که در کدام بازهٔ `n` اندازه‌گیری شده؟**

## در فصل بعد

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

**فصلِ بعد همان معامله را باز می‌کند.** یک `index` می‌سازیم که هر پرسش را از حدودِ دو میلی‌ثانیه به کمتر از یک‌دهمِ میکروثانیه می‌رساند، و **قیمتِ دقیقش را به بایت اندازه می‌گیریم**. بعد جایی می‌رویم که حافظه دیوار است نه زمان: جایی که یک `index`ِ کامل‌تر از آن **اصلاً ساخته نمی‌شود**، و انتخابِ «واضح» برمی‌گردد سرِ جای اول.

</div>

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