# فصل ۰۹ — پروژه: از جست‌وجوی خطی تا ساختارِ درست

<div dir="rtl">

# فصل ۰۹ — پروژه: از جست‌وجوی خطی تا ساختارِ درست

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

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

یک انبارِ رکورد داریم و باید در آن دنبالِ کد بگردیم. سه راه می‌سازیم که **جوابِ کاملاً یکسان** می‌دهند، برای هر سه جدولِ رشد می‌گیریم، و یک تصمیمِ مستند می‌نویسیم. در `n = 16,000` میانگینِ گامِ روشِ اول **`7,807.5`** است و روشِ دوم **`13.06`**.

**ولی نتیجهٔ اصلی در آن جدول نیست:** پرسشی پیدا می‌کنیم که سریع‌ترین ساختار **اصلاً نمی‌تواند** جوابش را بدهد و ۱۶٬۰۰۰ گام برمی‌دارد، در حالی که ساختارِ «کندتر» با **۳۲۲** گام تمامش می‌کند.

![سه میزِ جست‌وجو کنارِ هم: یکی قفسهٔ بی‌ترتیب، یکی قفسهٔ شماره‌دارِ مرتب، یکی جعبهٔ کلید](/lesson-assets/t4-s09-project-search/prompt/01-image-three-desks.png)

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

- سه ساختارِ جست‌وجو را روی یک مسئله بسنجی و برابریِ جوابشان را ثابت کنی
- هزینهٔ ساختِ اولیه را از هزینهٔ هر پرسش جدا کنی
- تشخیص بدهی کِی «سریع‌ترین» ساختار جوابِ مسئلهٔ تو را ندارد
- یک تصمیمِ مستند بنویسی که شرطِ باطل شدنش هم در آن نوشته باشد

## قبل از شروع

**از ترمِ ۳ فصلِ ۵:** `dict` و هزینهٔ ثابتِ جست‌وجویش. **از فصلِ ۷:** `bisect` و نقطهٔ سربه‌سر.

</div>

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

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-4-recursion-sorting-searching/session-09-project-search.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

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

هر رکورد یک **کدِ یکتا** دارد و یک **شهر**. کدها بی‌ترتیب می‌آیند. دو پرسش داریم:

1. **پرسشِ نقطه‌ای:** شهرِ این کد چیست؟
2. **پرسشِ بازه‌ای:** کدهای بینِ این دو عدد کدام‌اند؟

**الگوی دسترسی، قبل از هر کدی:** انبار یک بار ساخته می‌شود و بعد بارها پرسیده می‌شود. **پس هزینهٔ ساخت یک بار پرداخت می‌شود و هزینهٔ هر پرسش `q` بار** — و این تنها چیزی است که تصمیم را تعیین می‌کند.

</div>

```python
from bisect import bisect_left

CITIES = ("shiraz", "tabriz", "rasht", "yazd", "ahvaz", "kerman", "mashhad", "sari")
LOW, HIGH = 100_000, 1_100_000           # بازهٔ کدها، مستقل از n


def make_records(n, seed=SEED):
    """n رکوردِ (کد، شهر) با کدِ یکتا و بی‌ترتیب."""
    rng = random.Random(seed)
    codes = rng.sample(range(LOW, HIGH), n)
    return [(code, rng.choice(CITIES)) for code in codes]


for row in make_records(6):
    print(row)
```

```text
(915965, 'shiraz')
(562141, 'tabriz')
(222526, 'tabriz')
(107855, 'kerman')
(195046, 'yazd')
(1055227, 'shiraz')
```

<div dir="rtl">

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

## ۲. سه روش، یک جواب

</div>

```python
def city_linear(records, code):
    """روشِ ۱ — از اول تا آخر."""
    for c, city in records:
        if c == code:
            return city
    return None


def build_sorted(records):
    """روشِ ۲ — یک بار مرتب می‌کنیم و کدها را جدا نگه می‌داریم."""
    ordered = sorted(records)
    return ordered, [c for c, _ in ordered]


def city_binary(ordered, codes, code):
    i = bisect_left(codes, code)
    if i < len(codes) and codes[i] == code:
        return ordered[i][1]
    return None


def build_index(records):
    """روشِ ۳ — یک dict."""
    return {c: city for c, city in records}


sample = make_records(2_000)
ordered, codes = build_sorted(sample)
index = build_index(sample)
picker = random.Random(SEED)
probes = [picker.choice(sample)[0] for _ in range(200)] + [1, 2, 3]
print("هر سه روش یک جواب می‌دهند؟",
      all(city_linear(sample, p) == city_binary(ordered, codes, p) == index.get(p)
          for p in probes))
print("یک کدِ موجود   :", probes[0], "->", index.get(probes[0]))
print("یک کدِ ناموجود :", 1, "->", index.get(1))
```

```text
هر سه روش یک جواب می‌دهند؟ True
یک کدِ موجود   : 359978 -> mashhad
یک کدِ ناموجود : 1 -> None
```

<div dir="rtl">

**این سطر اول می‌آید، نه آخر** — و کدهای ناموجود عمداً در نمونه‌ها هستند، چون خطاهای مرزی همان‌جا خودشان را نشان می‌دهند.

> 🤔 **اول حدس بزن:** برای هر سه روش ستونِ نسبتِ «گام به‌ازای هر پرسش» را بنویس. **سه عدد**، بعد جدول را ببین.

## ۳. جدولِ گام‌ها

</div>

```python
def linear_steps(records, code):
    for i, (c, _) in enumerate(records):
        if c == code:
            return i + 1
    return len(records)


def binary_steps(codes, code):
    lo, hi, steps = 0, len(codes) - 1, 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if codes[mid] == code:
            return steps
        if codes[mid] < code:
            lo = mid + 1
        else:
            hi = mid - 1
    return steps


LADDER = [2_000, 4_000, 8_000, 16_000]
sets = {}
for n in LADDER:
    rows = make_records(n)
    o, cs = build_sorted(rows)
    pick = random.Random(SEED)
    asked = [pick.choice(rows)[0] for _ in range(200)]
    sets[n] = (rows, o, cs, build_index(rows), asked)

print("— روشِ ۱: میانگینِ گام برای هر پرسش")
table([(n, sum(linear_steps(sets[n][0], p) for p in sets[n][4]) / 200)
       for n in LADDER], "گام", ",.1f")
print("\n— روشِ ۲: میانگینِ گام برای هر پرسش")
table([(n, sum(binary_steps(sets[n][2], p) for p in sets[n][4]) / 200)
       for n in LADDER], "گام", ",.2f")
```

```text
— روشِ ۱: میانگینِ گام برای هر پرسش
         n               گام     نسبت به سطر قبل
     2,000             976.4                   —
     4,000           1,952.3                2.00
     8,000           3,904.0                2.00
    16,000           7,807.5                2.00

— روشِ ۲: میانگینِ گام برای هر پرسش
         n               گام     نسبت به سطر قبل
     2,000             10.13                   —
     4,000             10.97                1.08
     8,000             11.86                1.08
    16,000             13.06                1.10
```

<div dir="rtl">

**`2.00` در برابرِ `1.08`: `O(n)` در برابرِ `O(log n)`** — و در سطرِ آخر، `7,807.5` در برابرِ `13.06`. روشِ ۳ ستونِ گام ندارد چون گامش همیشه یکی است.

</div>

```python
for name, fn in (
    ("۱ خطی", lambda n: [city_linear(sets[n][0], p) for p in sets[n][4]]),
    ("۲ مرتب + binary", lambda n: [city_binary(sets[n][1], sets[n][2], p) for p in sets[n][4]]),
    ("۳ dict", lambda n: [sets[n][3].get(p) for p in sets[n][4]]),
):
    print(f"— روشِ {name}: زمانِ ۲۰۰ پرسش")
    table([(n, 1000 * clock(lambda k=n: fn(k), repeat=3)) for n in LADDER],
          "زمان (ms)", ",.3f")
    print()
```

```text-approx
— روشِ ۱ خطی: زمانِ ۲۰۰ پرسش
         n         زمان (ms)     نسبت به سطر قبل
     2,000             4.288                   —
     4,000             8.481                1.98
     8,000            17.361                2.05
    16,000            34.186                1.97

— روشِ ۲ مرتب + binary: زمانِ ۲۰۰ پرسش
         n         زمان (ms)     نسبت به سطر قبل
     2,000             0.061                   —
     4,000             0.070                1.16
     8,000             0.075                1.07
    16,000             0.081                1.08

— روشِ ۳ dict: زمانِ ۲۰۰ پرسش
         n         زمان (ms)     نسبت به سطر قبل
     2,000             0.012                   —
     4,000             0.012                1.06
     8,000             0.013                1.04
    16,000             0.013                1.01
```

<div dir="rtl">

**سه ستونِ نسبت، سه مرتبه: `2.00`، `1.08`، `1.00`.** روشِ ۳ با هشت برابر شدنِ داده اصلاً تکان نخورد — `O(1)`.

## ۴. هزینهٔ ساخت، که در جدولِ پرسش دیده نمی‌شود

</div>

```python
n = 16_000
rows = sets[n][0]
build_list = clock(lambda: list(rows), repeat=3)
build_sort = clock(lambda: build_sorted(rows), repeat=3)
build_dict = clock(lambda: build_index(rows), repeat=3)
print(f"n = {n:,} · هزینهٔ ساختِ اولیه (یک بار)")
print(f"  روشِ ۱ (هیچ ساختی)     : {1000 * build_list:>7,.2f} ms")
print(f"  روشِ ۲ (مرتب کردن)     : {1000 * build_sort:>7,.2f} ms")
print(f"  روشِ ۳ (ساختنِ dict)    : {1000 * build_dict:>7,.2f} ms")
```

```text-approx
n = 16,000 · هزینهٔ ساختِ اولیه (یک بار)
  روشِ ۱ (هیچ ساختی)     :    0.05 ms
  روشِ ۲ (مرتب کردن)     :    3.87 ms
  روشِ ۳ (ساختنِ dict)    :    1.09 ms
```

<div dir="rtl">

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

## ۵. پرسشی که `dict` جوابش را ندارد

حالا پرسشِ دومِ بخشِ ۱: **کدهای بینِ ۲۰۰٬۰۰۰ و ۲۲۰٬۰۰۰ کدام‌اند؟**

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

</div>

```python
def range_by_scan(records, low, high):
    """با dict یا با فهرستِ خام: چاره‌ای جز دیدنِ همه نیست."""
    out = []
    steps = 0
    for c, _ in records:
        steps += 1
        if low <= c <= high:
            out.append(c)
    return sorted(out), steps


def range_by_bisect(codes, low, high):
    """روی فهرستِ مرتب: از جای شروع تا جای پایان، و نه یک گامِ بیشتر."""
    i = bisect_left(codes, low)
    out = []
    steps = 0
    while i < len(codes) and codes[i] <= high:
        out.append(codes[i])
        steps += 1
        i += 1
    return out, steps


WINDOW = (200_000, 220_000)
print("— پرسشِ «همهٔ کدهای بینِ ۲۰۰٬۰۰۰ و ۲۲۰٬۰۰۰»")
print(f"{'n':>8}{'پیدا شد':>10}{'پیمایشِ همه':>16}{'bisect':>10}{'نسبت':>10}")
for n in LADDER:
    rows, o, cs, idx, _ = sets[n]
    hit1, s1 = range_by_scan(rows, *WINDOW)
    hit2, s2 = range_by_bisect(cs, *WINDOW)
    assert hit1 == hit2
    print(f"{n:>8,}{len(hit1):>10,}{s1:>16,}{s2:>10,}{s1 / s2:>10,.0f}")
```

```text
— پرسشِ «همهٔ کدهای بینِ ۲۰۰٬۰۰۰ و ۲۲۰٬۰۰۰»
       n   پیدا شد     پیمایشِ همه    bisect      نسبت
   2,000        33           2,000        33        61
   4,000        80           4,000        80        50
   8,000       162           8,000       162        49
  16,000       322          16,000       322        50
```

<div dir="rtl">

**فهرستِ مرتب دقیقاً به تعدادِ جواب‌ها گام برمی‌دارد و نه یکی بیشتر** — ستونِ «پیدا شد» و ستونِ `bisect` یکی‌اند. **پیمایشِ کامل همیشه `n` گام می‌خورد، حتی وقتی جواب خالی باشد.**

**و این کلِ درسِ پروژه است: «سریع‌ترین ساختار» یک صفتِ مطلق نیست.** روشِ ۳ برای پرسشِ نقطه‌ای بی‌رقیب بود و برای پرسشِ بازه‌ای بدترینِ سه‌تاست. **ساختار را پرسش انتخاب می‌کند، نه برعکس.**

</div>

```python
try:
    build_index([(1, "shiraz"), ([2], "yazd")])
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: unhashable type: 'list'
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** `dict` هر کلیدی را قبول نمی‌کند — همان `TypeError` ترمِ ۳ فصلِ ۶. **اگر کدها به‌جای عدد، `list`ی از چند بخش باشند، روشِ ۳ اصلاً ساخته نمی‌شود** و باید به `tuple` تبدیلشان کنی. **دو روشِ دیگر بی‌سروصدا کار می‌کنند** — پس این خطا دارد یک قیدِ واقعیِ روشِ ۳ را اعلام می‌کند.

> ✅ **چک کن:** `WINDOW` را به بازه‌ای ببر که هیچ کدی در آن نباشد — مثلاً `(1_200_000, 1_300_000)`. **اول باید ستونِ «نسبت» را امن کنی**، چون تقسیم بر صفر می‌شود: در همان خطِ `print`، به‌جای `s1 / s2` بنویس `(s1 / s2 if s2 else float("inf"))`. **حالا ستونِ `bisect` باید صفر شود و ستونِ پیمایشِ کامل هنوز `n` بماند.** **و همان `ZeroDivisionError` خودش جوابِ سؤال است:** وقتی جوابی نیست، فهرستِ مرتب هیچ گامی برنمی‌دارد.

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

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

**این شش بند تصمیمِ مستندِ این پروژه‌اند:**

1. **الگوی دسترسی:** یک بار ساخت، `q` بار پرسش؛ دو جنسِ پرسش — نقطه‌ای و بازه‌ای.
2. **بازهٔ `n`:** ۲٬۰۰۰ تا ۱۶٬۰۰۰ رکورد، با کدهای یکتا در یک بازهٔ ثابت.
3. **مرتبهٔ اعلام‌شده:** پرسشِ نقطه‌ای — روشِ ۱ `O(n)`، روشِ ۲ `O(log n)`، روشِ ۳ `O(1)`؛ هر سه از ستونِ نسبت. پرسشِ بازه‌ای — روشِ ۳ `O(n)`، روشِ ۲ به اندازهٔ تعدادِ جواب‌ها.
4. **درستی:** جوابِ هر سه روش در هر دو پرسش برابر تأیید شد، با کدهای ناموجود در نمونه.
5. **هزینهٔ پذیرفته‌شده:** ساختِ اولیه — روشِ ۲ گران‌ترین، و از حدودِ بیست پرسش به بعد جبران می‌شود (فصلِ ۷).
6. **تصمیم:** اگر **فقط** پرسشِ نقطه‌ای داری، روشِ ۳. **اگر حتی یک پرسشِ بازه‌ای هم داری، روشِ ۲** — و اگر `q` از حدودِ بیست کمتر است، روشِ ۱ و هیچ ساختاری.

**بندِ ششم شرطش را نوشته و بندِ سوم دو سطر دارد، نه یکی.** تصمیمی که فقط یک جنسِ پرسش را دیده باشد، برای پرسشِ دوم بی‌اعتبار است.

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

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| point query | پوینت کوئری | پرسش دربارهٔ یک کلیدِ مشخص |
| range query | رِینج کوئری | پرسش دربارهٔ همهٔ کلیدهای بینِ دو مقدار |
| index | ایندکس | ساختاری که از قبل ساخته می‌شود تا پرسش‌ها ارزان شوند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا: چرا `dict` پرسشِ بازه‌ای را ارزان جواب نمی‌دهد؟

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

**تمرینِ ستاره‌دار ⭐:** فرض کن انبار **ثابت نیست** و مدام رکوردِ تازه می‌گیرد. **قبل از اجرا پیش‌بینی کن** نگه داشتنِ ترتیب با `insort` چه مرتبه‌ای دارد، بعد اندازه‌اش بگیر و **خطای پیش‌بینی‌ات را بنویس**. حالا بندِ ۶ گزارش را دوباره بنویس. **سؤالِ آخر: از چه نسبتی بینِ درج و پرسش به بعد، تصمیمت عوض می‌شود؟**

## در فصل بعد

ترمِ چهار تمام شد: `recursion`، سه الگوریتمِ مرتب‌سازی، مرزِ پایین، و `binary search`.

**و آخرین جدولِ همین فصل، ترمِ بعد را باز می‌کند.** برای پرسشِ نقطه‌ای بهترین ساختار ترتیب را دور می‌ریزد و برای پرسشِ بازه‌ای بهترین ساختار به ترتیب نیاز دارد. **فهرستِ مرتب هم کامل نیست: جست‌وجویش `O(log n)` است ولی درجش `O(n)`.**

**ترمِ پنج ساختاری می‌سازد که ترتیب را نگه می‌دارد و درجش هم ارزان است** — درخت — **و همان‌جا اندازه‌اش می‌گیرد: `n` درج ستونِ نسبتِ `2.24` می‌دهد در برابرِ `3.94`ِ `insort`.** ولی همان فصل شرطش را هم نشان می‌دهد، چون **این ارزانی روی ورودیِ از پیش مرتب کاملاً برعکس می‌شود.** بعد سراغِ گراف می‌رود. **پرسشِ بازه‌ای روی درخت را همان‌جا هم اندازه نمی‌گیریم؛ ترمِ ۶ فصلِ ۲ آن خانه را «نسنجیده» علامت می‌زند و می‌گوید چرا.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t4/s09-project-search (یادستان, Yaadestan)
