# فصل ۰۱ — پرسشِ «هست یا نه؟» چقدر خرج دارد

<div dir="rtl">

# فصل ۰۱ — پرسشِ «هست یا نه؟» چقدر خرج دارد

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

«این عضو در فهرست هست یا نه؟» کوتاه‌ترین پرسشی است که از یک ظرف می‌شود پرسید و بی‌آزارترین به‌نظر می‌رسد. در این فصل هزینه‌اش را می‌شماریم و می‌بینیم که برای **یک** پرسش واقعاً ارزان است — و برای **هزار** پرسش، همان کد اصلاً تمام نمی‌شود.

شمارندهٔ ترمِ ۱ را برمی‌داریم و دو جدول می‌سازیم: یکی با یک پرسش که ستونِ نسبتش `2.00` می‌دهد، و یکی با پرسش‌هایی که تعدادشان هم با `n` بالا می‌رود و ستونِ نسبتش `4.00` می‌شود. **همان یک پرسش، دو مرتبهٔ کاملاً متفاوت** — و تفاوت در خودِ پرسش نیست، در تعدادِ دفعاتش است.

![کشویی از پرونده‌های ردیف‌شده که برای پیدا کردنِ یک برگه باید از اولین برگه تا آخری یکی‌یکی بالا زده شود](/lesson-assets/t3-s01-lookup-cost/prompt/01-image-drawer-one-by-one.png)

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

- جست‌وجوی خطی را با شمارندهٔ خودت اندازه بگیری و مرتبه‌اش را از ستونِ نسبت بخوانی
- بگویی بهترین، بدترین و متوسطِ یک جست‌وجوی خطی چه فرقی با هم دارند
- تشخیص بدهی کِی یک پرسشِ ارزان، به‌خاطرِ تکرار، به گران‌ترین بخشِ برنامه تبدیل می‌شود

## قبل از شروع

**از ترمِ ۱ فصلِ ۴:** شمارندهٔ عملیات، و اینکه شمارش قطعی است ولی ثانیه نیست.

**از ترمِ ۲ فصلِ ۵:** قاعدهٔ تشخیص — یک عملِ `O(n)` داخلِ یک حلقهٔ `n`تایی. **این فصل همان قاعده را از سمتِ دیگرش نگاه می‌کند:** این بار عملِ `O(n)` را می‌شناسیم و می‌خواهیم بدانیم دقیقاً چقدر خرج دارد.

</div>

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

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-3-hashing/session-01-lookup-cost.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. کاری که پایتون واقعاً می‌کند

`x in values` یک عبارتِ سه‌کلمه‌ای است، ولی داخلش یک حلقه نشسته: از خانهٔ اول شروع می‌کند، هر عضو را با `x` مقایسه می‌کند، و به‌محضِ برابری می‌ایستد. اگر هیچ‌کدام برابر نبودند، تا آخر می‌رود. **اسمش جست‌وجوی خطی است و «خطی» دقیقاً همان چیزی است که ستونِ نسبت نشان می‌دهد.**

می‌نویسیمش تا شمارنده داشته باشیم.

</div>

```python
def find_linear(values, target):
    """می‌گردد تا پیدا شود یا فهرست تمام شود؛ تعدادِ مقایسه را هم برمی‌گرداند."""
    ops = 0
    for v in values:
        ops += 1
        if v == target:
            return True, ops
    return False, ops


small = [7, 3, 9, 4]
for target in (7, 4, 5):
    found, ops = find_linear(small, target)
    print(f"دنبالِ {target}: پیدا شد؟ {found} · مقایسه‌ها: {ops}")
```

```text
دنبالِ 7: پیدا شد؟ True · مقایسه‌ها: 1
دنبالِ 4: پیدا شد؟ True · مقایسه‌ها: 4
دنبالِ 5: پیدا شد؟ False · مقایسه‌ها: 4
```

<div dir="rtl">

**سه پرسش روی یک فهرستِ چهارتایی، سه هزینهٔ متفاوت: یک، چهار، چهار.**

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

</div>

```python
n = 1_000
values = list(range(n))
print("بهترین حالت — عضوِ اول:", find_linear(values, 0)[1])
print("بدترین حالت — عضوِ آخر:", find_linear(values, n - 1)[1])
print("اصلاً نبودن در فهرست :", find_linear(values, -1)[1])
print("میانگینِ همهٔ عضوهای موجود:",
      sum(find_linear(values, v)[1] for v in values) / n)
```

```text
بهترین حالت — عضوِ اول: 1
بدترین حالت — عضوِ آخر: 1000
اصلاً نبودن در فهرست : 1000
میانگینِ همهٔ عضوهای موجود: 500.5
```

<div dir="rtl">

**یک، هزار، هزار، و پانصد و نیم.** میانگین دقیقاً وسطِ بهترین و بدترین درآمد، و این تصادفی نیست: اگر همهٔ عضوها به یک اندازه پرسیده شوند، به‌طورِ متوسط نصفِ فهرست دیده می‌شود.

**ولی «نبودن» میانگین ندارد.** پرسشی که جوابش «نه» است **همیشه** کلِ فهرست را می‌بیند، و در بیشترِ کارهای واقعی — فیلترِ هرزنامه، بررسیِ تکراری‌بودن، کنترلِ دسترسی — جوابِ اکثرِ پرسش‌ها «نه» است. **پس حالتِ گران، حالتِ استثنایی نیست؛ حالتِ عادی است.**

## ۲. جدولِ رشد برای یک پرسش

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

</div>

```python
LADDER = [1_000, 2_000, 4_000, 8_000]
pools = {n: list(range(n)) for n in LADDER}
table([(n, find_linear(pools[n], -1)[1]) for n in LADDER], "مقایسه", ",d")
```

```text
         n            مقایسه     نسبت به سطر قبل
     1,000             1,000                   —
     2,000             2,000                2.00
     4,000             4,000                2.00
     8,000             8,000                2.00
```

<div dir="rtl">

**`2.00`، سه بار پشتِ هم و بدونِ کوچک‌ترین نوسان.** شمارنده قطعی است و این عددها روی ماشینِ تو هم دقیقاً همین‌اند.

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

## ۳. همان پرسش، این بار تکراری

حالا صورتِ مسئله را به چیزی نزدیک‌تر به کارِ واقعی می‌بریم. یک فهرستِ `n`تایی از عضوهای شناخته‌شده داریم و یک دستهٔ تازه می‌رسد که باید برای هرکدامشان بپرسیم «قبلاً دیده شده یا نه؟». **تعدادِ پرسش‌ها هم با حجمِ داده بالا می‌رود** — این‌جا یک‌چهارمِ `n`.

> 🤔 **اول حدس بزن:** حالا با دو برابر شدنِ `n` ستونِ نسبت چه عددی می‌دهد؟ `2` یا چیزِ دیگری؟ **قبل از دیدنِ جدول بنویسش.**

</div>

```python
rng = random.Random(SEED)
asks = {n: [rng.randrange(4 * n) for _ in range(n // 4)] for n in LADDER}


def ask_all(values, questions):
    """به هر پرسش جداگانه جواب می‌دهد و مقایسه‌ها را روی هم جمع می‌زند."""
    ops = 0
    for q in questions:
        ops += find_linear(values, q)[1]
    return ops


print("تعدادِ پرسش در هر سطر:", [len(asks[n]) for n in LADDER])
table([(n, ask_all(pools[n], asks[n])) for n in LADDER], "مقایسه", ",d")
```

```text
تعدادِ پرسش در هر سطر: [250, 500, 1000, 2000]
         n            مقایسه     نسبت به سطر قبل
     1,000           212,263                   —
     2,000           894,367                4.21
     4,000         3,527,341                3.94
     8,000        14,051,508                3.98
```

<div dir="rtl">

**نزدیکِ `4`، نه `2`.** و هیچ چیزی در خودِ پرسش عوض نشده؛ فقط تعدادِ پرسش‌ها هم با `n` بالا رفته.

منطقش یک ضرب است: `n/4` پرسش، هر کدام تا `n` مقایسه، روی هم `n²/4`. **دو برابر شدنِ `n` هر دو عامل را دو برابر می‌کند، پس حاصل‌ضرب چهار برابر می‌شود.** این دقیقاً همان قاعدهٔ تشخیصِ ترمِ ۲ فصلِ ۵ است — یک عملِ `O(n)` داخلِ حلقه‌ای که خودش `n`تایی است — با این تفاوت که این بار **هیچ حلقهٔ تودرتویی در کدِ ما نیست.** حلقهٔ دوم داخلِ `find_linear` پنهان است.

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

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

</div>

```python
table([(n, 1000 * clock(lambda v=pools[n], q=asks[n]: ask_all(v, q), repeat=3))
       for n in LADDER], "زمان (ms)", ",.1f")
```

```text-approx
         n         زمان (ms)     نسبت به سطر قبل
     1,000               6.3                   —
     2,000              27.0                4.31
     4,000             111.4                4.13
     8,000             455.2                4.09
```

<div dir="rtl">

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

و یک عددِ ساده که ارزشِ نوشتن دارد و از جدولِ **شمارش** درمی‌آید، نه از ساعت: از سطرِ اول تا سطرِ آخر `n` هشت برابر شد و تعدادِ مقایسه‌ها **بیش از شصت برابر**. اگر همین کد را روی سیاهه‌ای با یک میلیون سطر بگذاری، دیگر منتظرش نمی‌مانی.

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

## ۵. سطری که از ترمِ ۲ خالی ماند

جدولِ فصلِ ۵ ترمِ ۲ برای هر عملیاتِ هر ظرفِ ترتیبی یک هزینه داشت، و برای `x in values` نوشته بود `O(n)`. آن سطر درست بود و **راهِ حلی نداشت**: در یک نوارِ پیوسته، تنها راهِ فهمیدنِ اینکه عضوی هست یا نه، نگاه کردن به همه‌شان است.

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

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

> ✅ **چک کن:** در `asks` عبارتِ `rng.randrange(4 * n)` را به `rng.randrange(n)` تغییر بده تا **همهٔ** پرسش‌ها جوابِ «بله» بگیرند، و جدولِ بخشِ ۳ را دوباره بساز. **تعدادِ مقایسه باید تقریباً نصف شود، ولی ستونِ نسبت باید هنوز نزدیکِ `4` بماند.** اگر نسبت هم عوض شد، احتمالاً `n // 4` را هم دست زده‌ای — و آن‌وقت داری دو چیز را هم‌زمان تغییر می‌دهی، که هیچ آزمایشی از آن درنمی‌آید.

> 🔧 **اگر کار نکرد:** رایج‌ترین اشتباه موقعِ نوشتنِ این آزمایش این است که به‌جای ظرف، اندازه‌اش را جلوی `in` بگذاری:

</div>

```python
try:
    limit = 8
    print(3 in limit)
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: argument of type 'int' is not iterable
```

<div dir="rtl">

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

> 🤖 **از دستیارت بپرس:** «چرا جست‌وجوی خطی برای پرسشی که جوابش «نه» است همیشه بدترین حالت است؟» بعد این را هم بپرس: **«اگر فهرستم مرتب بود، پرسشِ عضویت چقدر ارزان‌تر می‌شد؟»** — جوابِ درست عددِ `log n` را می‌آورد و **هزینهٔ مرتب‌کردن را هم حساب می‌کند**؛ اگر دستیارت فقط از سرعتِ جست‌وجو گفت و از هزینهٔ مرتب‌سازی چیزی نگفت، نصفِ معامله را جا انداخته. (ترمِ ۴ همین معامله را با عدد باز می‌کند.)

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| linear search | لینیر سرچ | گشتن از اولین عضو تا پیدا شدن یا تمام شدنِ ظرف |
| membership test | ممبرشیپ تست | پرسشِ «این عضو در ظرف هست یا نه؟» |
| lookup | لوک‌آپ | یک بار پرسیدن از یک ظرف |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا هزینهٔ «نبودن» با هزینهٔ بدترین حالتِ «بودن» یکی است؟

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

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

## در فصل بعد

برای اینکه بشود جای یک کلید را **حساب کرد** به‌جای اینکه دنبالش گشت، به تابعی احتیاج داریم که هر کلیدی — عدد، رشته، یا هر چیزِ دیگر — را به یک عدد تبدیل کند: `hash`.

فصلِ بعد این تابع را می‌سازد و بعد خرابش می‌کند: **یک نسخهٔ ساده‌اش سه رشتهٔ متفاوت را به یک عددِ کاملاً یکسان می‌فرستد.** بعد نسخهٔ بهتری می‌سازیم و پخشش را با عدد اندازه می‌گیریم، و آخرش به سراغِ چیزی می‌رویم که خیلی‌ها را غافلگیر می‌کند: **`hash` یک رشته در پایتون، در دو اجرای متفاوتِ همان برنامه، دو عددِ متفاوت است.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t3/s01-lookup-cost (یادستان, Yaadestan)
