# فصل ۰۵ — `set` و `dict` در عمل

<div dir="rtl">

# فصل ۰۵ — `set` و `dict` در عمل

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

سه فصل با دست کار کردیم تا بدانیم پشتِ `set` و `dict` چه می‌گذرد. حالا سراغِ خودشان می‌رویم و همان پرسشِ فصلِ ۱ را می‌پرسیم: **صد هزار پرسش، و ظرفی که هر بار دو برابر می‌شود.**

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

![دو میزِ اطلاعات کنارِ هم، یکی با صفی طولانی و دیگری با تابلوی شماره‌دار و بدون صف](/lesson-assets/t3-s05-set-and-dict/prompt/01-image-two-desks.png)

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

- عضویت، شمارش و گروه‌بندی را با هزینهٔ ثابت انجام بدهی
- `defaultdict` را جای `KeyError` بگذاری
- نقطهٔ سربه‌سرِ `set` و جست‌وجوی خطی را برای مسئلهٔ خودت پیدا کنی

## قبل از شروع

**از فصلِ ۳:** `hash table`، `load factor` و اینکه هزینهٔ یک جست‌وجو به تعدادِ کلیدها بند نیست. **`set` و `dict` در پایتون همان ایده‌اند: جای کلید از `hash`ش می‌آید و جدول با پر شدن بزرگ می‌شود.** فرقشان در برخورد است: زنجیری در کار نیست و کلیدِ دوم به خانهٔ خالیِ دیگری داخلِ خودِ جدول می‌رود.

**از فصلِ ۱:** جست‌وجوی خطی و هزینهٔ `O(n)`ش.

**از ترمِ ۱ فصلِ ۹:** نقطهٔ تقاطع — الگوریتمِ با مرتبهٔ بدتر که در `n` کوچک برنده است. **این فصل یک نمونهٔ دیگرش را می‌سازد.**

</div>

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

<div dir="rtl">

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

## ۱. یک تابع، دو ظرف

این بار آزمایش را برعکسِ فصلِ ۱ می‌چینیم: **تعدادِ پرسش‌ها ثابت است و ظرف دو برابر می‌شود.** این دقیقاً همان چیزی است که ادعای «هزینهٔ ثابت» را آزمون می‌کند — اگر هزینهٔ یک پرسش به `n` بند نباشد، دو برابر شدنِ ظرف نباید هیچ اثری داشته باشد.

</div>

```python
rng = random.Random(SEED)
LADDER = [250, 500, 1_000, 2_000]
ASKS = 100_000
base = [f"user-{rng.randrange(10 ** 9)}" for _ in range(2_000)]
pools = {n: base[:n] for n in LADDER}
known = {n: set(base[:n]) for n in LADDER}
questions = [base[rng.randrange(250)] if i % 4 == 0
             else f"user-{rng.randrange(10 ** 9)}" for i in range(ASKS)]


def hits_in(container, asked):
    """به همهٔ پرسش‌ها جواب می‌دهد؛ ظرف هر چه باشد، کد یکی است."""
    hits = 0
    for q in asked:
        if q in container:
            hits += 1
    return hits


print("list و set یک جواب می‌دهند؟",
      all(hits_in(pools[n], questions) == hits_in(known[n], questions) for n in LADDER))
print("تعدادِ پرسش:", len(questions), "· تعدادِ جوابِ «بله»:", hits_in(known[250], questions))
```

```text
list و set یک جواب می‌دهند؟ True
تعدادِ پرسش: 100000 · تعدادِ جوابِ «بله»: 25000
```

<div dir="rtl">

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

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

</div>

```python
print("— پرسیدن از list")
table([(n, 1000 * clock(lambda c=pools[n]: hits_in(c, questions), repeat=2))
       for n in LADDER], "زمان (ms)", ",.1f")
print("\n— پرسیدن از set")
table([(n, 1000 * clock(lambda c=known[n]: hits_in(c, questions), repeat=3))
       for n in LADDER], "زمان (ms)", ",.1f")
```

```text-approx
— پرسیدن از list
         n         زمان (ms)     نسبت به سطر قبل
       250             236.4                   —
       500             452.7                1.91
     1,000             914.4                2.02
     2,000           1,648.1                1.80

— پرسیدن از set
         n         زمان (ms)     نسبت به سطر قبل
       250               2.8                   —
       500               2.6                0.91
     1,000               2.9                1.13
     2,000               2.6                0.91
```

<div dir="rtl">

**ستونِ بالا نزدیکِ `2` و ستونِ پایین نزدیکِ `1`.**

ستونِ بالا یعنی هزینهٔ هر پرسش با `n` بالا می‌رود: `O(n)`. ستونِ پایین یعنی **هزینهٔ هر پرسش به `n` هیچ کاری ندارد**: `O(1)`. عددهای `set` حولِ یک عددِ ثابت بالا و پایین می‌روند و همان بالا و پایین رفتن هم نویزِ ترمِ ۱ فصلِ ۳ است، نه یک روند.

</div>

```python
n = 2_000
slow = clock(lambda: hits_in(pools[n], questions), repeat=2)
fast = clock(lambda: hits_in(known[n], questions), repeat=3)
print(f"n = {n:,} و {ASKS:,} پرسش  ·  list: {1000 * slow:,.1f} ms"
      f"  ·  set: {1000 * fast:,.1f} ms  ·  نسبت: {slow / fast:,.0f}")
```

```text-approx
n = 2,000 و 100,000 پرسش  ·  list: 1,694.9 ms  ·  set: 3.0 ms  ·  نسبت: 572
```

<div dir="rtl">

**چند صد برابر، با یک `list` که فقط دو هزار عضو دارد.** و عددِ ثانیه روی ماشینِ تو فرق می‌کند؛ **نسبت است که نباید فرق کند.**

**و مهم‌تر: این نسبت خودش با `n` بزرگ می‌شود.** روی یک `list` صد هزارتایی همین کد حدودِ پنجاه برابرِ این‌جا طول می‌کشد و `set` تقریباً همان‌قدر می‌ماند که حالا هست.

## ۲. ولی ساختنِ `set` رایگان نیست

در جدولِ بالا `set` را از قبل ساخته بودیم. در کارِ واقعی باید ساختش را هم حساب کرد، و ساختن یعنی `n` بار `hash` گرفتن و `n` بار درج کردن.

</div>

```python
big = [f"user-{rng.randrange(10 ** 9)}" for _ in range(200_000)]
table([(n, 1000 * clock(lambda v=big[:n]: set(v), repeat=3))
       for n in (25_000, 50_000, 100_000, 200_000)], "زمانِ ساخت (ms)", ",.1f")
```

```text-approx
         n   زمانِ ساخت (ms)     نسبت به سطر قبل
    25,000               1.3                   —
    50,000               1.9                1.47
   100,000               5.2                2.77
   200,000              12.8                2.47
```

<div dir="rtl">

**نسبت‌ها حولِ `2` می‌چرخند و هیچ‌کدام `2.00` نیستند** — یعنی ساخت خطی است، ولی با ثابتی که در اندازه‌های بزرگ‌تر کمی بدتر می‌شود. **این بالا رفتنِ ملایم `Big-O` نیست؛ از حافظه می‌آید:** جدولِ کوچک در حافظهٔ نزدیکِ پردازنده جا می‌شود و جدولِ بزرگ نه — همان چیزی که ترمِ ۲ فصلِ ۱ با خواندنِ به‌هم‌ریخته نشانش داد.

## ۳. نقطهٔ سربه‌سر

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

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

</div>

```python
print(f"{'تعدادِ پرسش':>12}{'list (ms)':>12}{'set (ms)':>12}{'برنده':>8}")
for m in (1, 2, 4, 8, 16, 32):
    asked = [f"user-{rng.randrange(10 ** 9)}" for _ in range(m)]
    with_list = 1000 * clock(lambda: hits_in(big, asked), repeat=3)
    with_set = 1000 * clock(lambda: hits_in(set(big), asked), repeat=3)
    print(f"{m:>12}{with_list:>12.2f}{with_set:>12.2f}"
          f"{('list' if with_list < with_set else 'set'):>8}")
```

```text-approx
 تعدادِ پرسش   list (ms)    set (ms)   برنده
           1        2.41       12.25    list
           2        4.84       12.90    list
           4        9.94       12.42    list
           8       21.30       12.92     set
          16       38.71       12.22     set
          32       79.00       12.59     set
```

<div dir="rtl">

**نقطهٔ سربه‌سر بینِ چهار و هشت پرسش است.**

ستونِ `list` دقیقاً دو برابر می‌شود، چون هر پرسش یک پویشِ کاملِ ظرف است. ستونِ `set` تقریباً ثابت می‌ماند، چون تقریباً تمامش هزینهٔ **ساخت** است و ساخت به تعدادِ پرسش‌ها کاری ندارد.

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

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک تابعِ ثابت که فقط ظرفش عوض می‌شود — `list` در برابرِ `set` — با پرسش‌های کاملاً یکسان و جوابِ تأییدشدهٔ برابر. **در کدام بازهٔ `n`؟** ظرفِ ۲۵۰ تا ۲٬۰۰۰ با صد هزار پرسشِ ثابت برای مرتبه، ظرفِ ۲۵٬۰۰۰ تا ۲۰۰٬۰۰۰ برای هزینهٔ ساخت، و ظرفِ ثابتِ ۲۰۰٬۰۰۰ با ۱ تا ۳۲ پرسش برای نقطهٔ سربه‌سر. **با چند تکرار، و کمینه یا میانگین؟** دو تا سه تکرار به‌علاوهٔ گرم‌کننده، کمینه.

## ۴. شمارش با `dict`

`dict` همان ساختار است، با این تفاوت که کنارِ هر کلید یک مقدار هم نگه می‌دارد. رایج‌ترین کاربردش شمارش است — و رایج‌ترین اشتباهش هم همان‌جاست.

</div>

```python
LEVELS = ("INFO", "WARN", "ERROR")
rng2 = random.Random(SEED)
log = [f"{i:06d} {rng2.choice(LEVELS)} unit-{rng2.randrange(20)}" for i in range(50_000)]
print(log[0])
print(log[1])

counts = {}
try:
    for line in log:
        counts[line.split(" ")[1]] += 1
except KeyError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
000000 WARN unit-3
000001 INFO unit-2
KeyError: 'WARN'
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** `KeyError` یعنی کلیدی خواسته‌ای که در `dict` نیست، و `counts[k] += 1` اول **می‌خواند** و بعد می‌نویسد. **دقت کن که خطا روی همان سطرِ اول افتاد**، پس هیچ شمارشی انجام نشده. سه راهِ درست هست و ما وسطی را می‌گیریم: `counts.get(k, 0) + 1`، یا `defaultdict(int)`، یا `Counter` که از سرنخ می‌شناسی‌اش.

</div>

```python
from collections import defaultdict

counts = defaultdict(int)
for line in log:
    counts[line.split(" ")[1]] += 1
for level in LEVELS:
    print(f"{level:>6}: {counts[level]:>7,}")
```

```text
  INFO:  16,839
  WARN:  16,659
 ERROR:  16,502
```

<div dir="rtl">

`defaultdict(int)` یعنی «اگر کلید نبود، از صفر شروع کن». **و کارِ مهم‌ترش این است که سه سطرِ شرطی را از حلقه بیرون می‌برد** — هر سطری که از حلقه بیرون برود، هم کد را ساده‌تر می‌کند و هم یک جای کمتر برای اشتباه می‌گذارد.

**و هزینه‌اش: پنجاه هزار سطر با یک عبور، بدونِ هیچ جست‌وجویی.** با `list` باید برای هر سطر می‌گشتی که «این سطح را قبلاً دیده‌ام یا نه». با سه سطح این گشتن کوتاه است، ولی با کلیدهای زیاد همان `O(n²)`ی می‌شود که ترمِ ۲ فصلِ ۵ نشانش داد.

## ۵. گروه‌بندی با `defaultdict(list)`

همان ایده، با یک `list` به‌جای یک عدد: به‌ازای هر کلید، همهٔ سطرهایش را جمع کن.

</div>

```python
by_unit = defaultdict(list)
for line in log:
    parts = line.split(" ")
    by_unit[parts[2]].append(parts[1])
print("تعدادِ واحدها:", len(by_unit))
for unit in ("unit-0", "unit-1", "unit-19"):
    rows = by_unit[unit]
    print(f"{unit:>8}: {len(rows):>6,} سطر  ·  ERROR: {rows.count('ERROR'):>6,}")
```

```text
تعدادِ واحدها: 20
  unit-0:  2,521 سطر  ·  ERROR:    865
  unit-1:  2,463 سطر  ·  ERROR:    787
 unit-19:  2,532 سطر  ·  ERROR:    824
```

<div dir="rtl">

**یک عبور روی داده، و حالا هر پرسشی دربارهٔ هر واحد، یک `lookup` است.** این الگو — یک بار ساختنِ یک `index`، بعد هزار بار پرسیدن از آن — همان چیزی است که در بخشِ ۳ نقطهٔ سربه‌سرش را پیدا کردیم.

> ✅ **چک کن:** در بخشِ ۱، `known` را از `set(base[:n])` به `list(base[:n])` تغییر بده و **بدونِ هیچ تغییرِ دیگری** جدولِ دوم را بگیر. **جواب‌ها باید دقیقاً همان بمانند و ستونِ نسبت باید از `1` به `2` برود.** اگر جواب‌ها هم عوض شدند، جایی برشِ `[:n]` را جا انداخته‌ای — و آن‌وقت داری دو ظرفِ متفاوت را با دو دادهٔ متفاوت می‌سنجی، که هیچ نتیجه‌ای ندارد.

> ⚠️ **مواظب باش:** `set` ترتیب ندارد و این را باید جدی گرفت:

</div>

```python
units = {"unit-3", "unit-1", "unit-2"}
print("مرتب‌شده:", sorted(units))
try:
    print(units[0])
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
مرتب‌شده: ['unit-1', 'unit-2', 'unit-3']
TypeError: 'set' object is not subscriptable
```

<div dir="rtl">

پیام صریح است: `set` اندیس ندارد، چون **جای هر عضو از `hash`ش می‌آید نه از ترتیبِ ورودش**. و یک نکتهٔ ظریف‌تر که فصلِ ۲ زمینه‌اش را ساخت: چون `hash` رشته‌ها بینِ دو اجرا عوض می‌شود، **ترتیبِ چاپِ یک `set` از رشته‌ها هم بینِ دو اجرا عوض می‌شود.** اگر خروجی‌ات باید تکرارپذیر باشد، `sorted` را جا نینداز. **`dict` بر عکس، ترتیبِ درج را نگه می‌دارد** و می‌شود به آن تکیه کرد.

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

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `defaultdict` | دیفالت‌دیکت | `dict`ی که برای کلیدِ تازه خودش یک مقدارِ اولیه می‌سازد |
| break-even point | بریک-ایون پوینت | تعدادِ پرسشی که از آن به بعد ساختنِ ساختار صرف می‌کند |
| index | ایندکس | ساختاری که یک بار ساخته می‌شود تا پرسش‌های بعدی ارزان شوند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا ستونِ `set` در جدولِ نقطهٔ سربه‌سر تقریباً ثابت است؟

**تمرینِ اجباری:** گروه‌بندیِ بخشِ ۵ را یک بار هم بدونِ `dict` بنویس: یک `list` از واحدهای دیده‌شده نگه دار و برای هر سطر داخلش بگرد. جدولِ چهار اندازه‌ای‌اش را بگیر (سیاهه را از ۱۲٬۵۰۰ تا ۱۰۰٬۰۰۰ سطر بزرگ کن). **سؤالِ اصلی: ستونِ نسبت چه می‌شود، و چرا با وجودِ اینکه فقط بیست واحد داریم، جواب همانی نیست که انتظار داشتی؟** جوابت باید به تعدادِ **کلیدهای یکتا** اشاره کند، نه به تعدادِ سطرها.

**تمرینِ ستاره‌دار ⭐:** جدولِ نقطهٔ سربه‌سر را برای سه اندازهٔ ظرف بگیر: ۲۰٬۰۰۰ و ۲۰۰٬۰۰۰ و ۲٬۰۰۰٬۰۰۰ عضو. **قبل از اجرا پیش‌بینی کن** نقطهٔ سربه‌سر با بزرگ‌تر شدنِ ظرف جابه‌جا می‌شود یا نه، و **چرا**. حالا اندازه بگیر و خطای پیش‌بینی‌ات را بنویس. (راهنمایی: هر دو ستون با `n` بزرگ می‌شوند؛ سؤال این است که به یک نسبت یا نه.)

## در فصل بعد

تا حالا هر کلیدی که به `set` و `dict` داده‌ایم رشته یا عدد بوده. فصلِ بعد می‌پرسد **چه چیزی اصلاً می‌تواند کلید باشد** — و از یک خطای واقعی شروع می‌کند: `TypeError: unhashable type: 'list'`.

بعد قاعده‌ای را می‌بینی که پشتِ آن خطاست، و یک `dict` که **سه بار درج می‌شود و آخرش یک عضو دارد**. آخرِ فصل هم، با همان `hash table` دست‌سازِ فصلِ ۳، کلیدی را که بعد از درج عوض شده گم می‌کنیم — **در حالی که خودش هنوز همان‌جا داخلِ `bucket` نشسته و دیده می‌شود.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t3/s05-set-and-dict (یادستان, Yaadestan)
