# ساختمان داده در پایتون: list، tuple، dict، set، deque و heapq را کِی به کار ببریم

ساختمان داده یعنی روشی که داده در حافظه چیده می‌شود تا یک کار مشخص روی آن ارزان باشد. پایتون شش ساختمان دادهٔ پرکاربرد آماده دارد: `list` برای دنبالهٔ مرتب با دسترسی با اندیس، `tuple` برای دنبالهٔ ثابت، `dict` برای «کلید ← مقدار»، `set` برای «هست یا نه؟»، `deque` برای صف، و `heapq` برای «کوچک‌ترین بعدی کدام است؟». هیچ‌کدام در همه‌چیز بهتر نیست. هر کدام یک کار را ارزان می‌کند و بهایش را جای دیگری می‌گیرد.

(در بعضی کتاب‌ها و در خودآموز بنیاد به این مفهوم «ساختار داده» هم می‌گویند. هر دو یک چیزند.)

## سؤال اول: برنامه‌ات چه کاری را بیشتر انجام می‌دهد؟

پیش از انتخاب ظرف باید «الگوی دسترسی» را بدانی: کدام عملیات چند بار انجام می‌شود. چند نمونه:

- با اندیس می‌خوانی، مثلاً «عضو هزارم»؟
- فقط به انتها اضافه می‌کنی، یا از ابتدا هم برمی‌داری؟
- مدام می‌پرسی «این عضو هست یا نه؟»
- مدام کوچک‌ترین یا مهم‌ترین عضو را می‌خواهی؟

یک ظرف ممکن است برای یکی از این‌ها عالی و برای دیگری فاجعه باشد. برای همین اول باید کار را شناخت، بعد ظرف را.

## `list`: نوار پیوسته

`list` عضوها را پشت‌سرهم در حافظه نگه می‌دارد. نتیجه‌اش این است:

| عملیات | هزینه | چرا |
|---|---|---|
| خواندن با اندیس `a[i]` | `O(1)` | جای خانه با یک حساب ساده معلوم است |
| افزودن به انتها `append` | `O(1)` به‌طور سرشکن (`amortised`) | گاهی کل نوار به جای بزرگ‌تری کپی می‌شود، ولی آن‌قدر کم که میانگین ثابت می‌ماند |
| برداشتن از انتها `pop()` | `O(1)` | چیزی جابه‌جا نمی‌شود |
| افزودن یا برداشتن از ابتدا `insert(0, x)`، `pop(0)` | `O(n)` | همهٔ عضوهای بعدی یک خانه جابه‌جا می‌شوند |
| پرسش عضویت `x in a` | `O(n)` | باید تک‌تک عضوها را نگاه کند |

این‌ها همان چیزی است که فصل‌های ترم ۲ بنیاد اندازه می‌گیرند. `list` بهترین `stack` پایتون است، چون `append` و `pop()` هر دو از انتها کار می‌کنند. ولی برای صف، که از ابتدا برمی‌دارد، انتخاب بدی است.

## `tuple`: همان دنباله، ولی ثابت

`tuple` مثل `list` دنباله است و با اندیس خوانده می‌شود، ولی بعد از ساختن عوض نمی‌شود. این محدودیت یک امتیاز مهم می‌دهد: اگر همهٔ عضوهایش قابل‌`hash` باشند، `tuple` خودش می‌تواند کلید `dict` یا عضو `set` باشد. `list` نمی‌تواند.

```python
grid = {(0, 0): "start", (2, 3): "goal"}
print(grid[(2, 3)])

try:
    bad = {[2, 3]: "goal"}
except TypeError as e:
    print("TypeError:", e)
```

```text
goal
TypeError: cannot use 'list' as a dict key (unhashable type: 'list')
```

متن دقیق پیام خطا در نسخه‌های مختلف پایتون کمی فرق دارد، ولی عبارت `unhashable type` همیشه هست. هر جا کلید مرکب لازم داری، مثل مختصات یا «نام و تاریخ»، `tuple` جواب است.

## `dict` و `set`: جدول `hash`

`dict` و `set` هر کلید را با یک تابع `hash` به یک خانه در یک جدول می‌برند. پس برای فهمیدن اینکه کلیدی هست یا نه، لازم نیست همه را نگاه کنند. پرسش عضویت و خواندن با کلید به‌طور میانگین `O(1)` است.

```python
from collections import Counter

words = "red blue red green blue red".split()
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1
print(counts)
print(Counter(words).most_common(1))

seen = set(words)
print(sorted(seen), "blue" in seen)
```

```text
{'red': 3, 'blue': 2, 'green': 1}
[('red', 3)]
['blue', 'green', 'red'] True
```

سه نکته را معمولاً کسی نمی‌گوید:

1. **«به‌طور میانگین» قید واقعی است.** فصل‌های ترم ۳ بنیاد ورودی خصمانه‌ای می‌سازند که همهٔ کلیدها در یک خانه بیفتند، و آن‌جا جست‌وجو دوباره خطی می‌شود.
2. **ساختن `set` رایگان نیست.** ساختنش یعنی `n` بار `hash` گرفتن. در اندازه‌گیری [فصل set و dict](/courses/bonyad/lessons/t3/s05-set-and-dict) روی یک فهرست دویست‌هزارتایی، برای یک یا دو پرسش، جست‌وجوی مستقیم در `list` ارزان‌تر بود. نقطهٔ سربه‌سر بین چهار و هشت پرسش افتاد. اگر فقط یک بار می‌پرسی، `set` ساختن صرف نمی‌کند.
3. **`set` ترتیب ندارد، `dict` دارد.** `dict` ترتیب درج را نگه می‌دارد. ترتیب چاپ یک `set` از رشته‌ها حتی بین دو اجرا عوض می‌شود، برای همین در کد بالا از `sorted` استفاده کردیم.

## `deque`: صف درست

`deque` از کتابخانهٔ `collections` برای افزودن و برداشتن از هر دو سر ساخته شده است. `popleft()` در آن `O(1)` است، در حالی که `pop(0)` روی `list` همهٔ عضوها را جابه‌جا می‌کند. این کد هر دو را اندازه می‌گیرد:

```python
import time
from collections import deque

def best_of(fn, repeat=5):
    times = []
    for _ in range(repeat):
        start = time.perf_counter()
        fn()
        times.append(time.perf_counter() - start)
    return min(times)

def drain_list(n):
    q = list(range(n))
    while q:
        q.pop(0)          # removes from the front: shifts everything left

def drain_deque(n):
    q = deque(range(n))
    while q:
        q.popleft()       # removes from the front: no shifting

for n in (20_000, 40_000, 80_000):
    a = best_of(lambda: drain_list(n))
    b = best_of(lambda: drain_deque(n))
    print(f"{n:>7,}  list {a*1000:7.1f} ms   deque {b*1000:5.2f} ms")
```

نتیجهٔ یک اجرای واقعی (عددهای تو فرق می‌کنند، نسبت‌ها نباید خیلی فرق کنند):

| `n` | `list` با `pop(0)` | `deque` با `popleft()` |
|---|---|---|
| `20,000` | `19.7 ms` | `0.65 ms` |
| `40,000` | `82.3 ms` | `1.43 ms` |
| `80,000` | `326.8 ms` | `2.94 ms` |

ستون `list` با هر دو برابرشدن `n` حدود چهار برابر می‌شود (`82.3 ÷ 19.7 ≈ 4.2` و `326.8 ÷ 82.3 ≈ 4.0`). یعنی صف با `list` درجه‌دوم است. ستون `deque` حدود دو برابر می‌شود، یعنی خطی. اگر این نسبت‌ها برایت آشنا نیست، [Big O به زبان ساده](/blog/big-o-explained) همین خواندن را توضیح می‌دهد.

ولی `deque` هم بهایی دارد. خواندن عضو وسطش با اندیس گران است، چون باید از یکی از دو سر راه بیفتد. در جدول [فصل انتخاب دنباله](/courses/bonyad/lessons/t2/s08-choosing-a-sequence) خواندن با اندیس تصادفی در `deque` حدود ده برابر `list` طول کشید.

## `heapq`: همیشه کوچک‌ترین

`heapq` ظرف جدایی نیست. چند تابع است که یک `list` معمولی را به شکل `heap` نگه می‌دارد: کوچک‌ترین عضو همیشه در `h[0]` است. افزودن با `heappush` و برداشتن کوچک‌ترین با `heappop` هر دو `O(log n)` هستند.

```python
import heapq

tasks = []
heapq.heappush(tasks, (3, "write report"))
heapq.heappush(tasks, (1, "fix bug"))
heapq.heappush(tasks, (2, "reply email"))
print(heapq.heappop(tasks))
print(heapq.nlargest(2, [5, 1, 9, 3, 7]))
```

```text
(1, 'fix bug')
[9, 7]
```

`heapq.nlargest` چند بزرگ‌ترین عضو را بدون مرتب‌کردن کل داده پیدا می‌کند. [فصل heap در بنیاد](/courses/bonyad/lessons/t5/s04-heap) نشان می‌دهد که روی ورودی تصادفی، درج به‌طور متوسط تقریباً هزینهٔ ثابت دارد و `log n` بیشتر در برداشتن است.

یک دام هم هست: وقتی دو `tuple` اولویت برابر دارند، پایتون عضو دوم را مقایسه می‌کند. اگر عضو دوم چیزی مثل `dict` باشد که مقایسه نمی‌شود، `TypeError` می‌گیری. راه رایج این است که یک شمارنده وسط بگذاری: `(priority, counter, item)`.

## جدول انتخاب

| کاری که زیاد انجام می‌دهی | ظرف مناسب |
|---|---|
| خواندن با اندیس دلخواه | `list` |
| افزودن و برداشتن فقط از انتها (`stack`) | `list` |
| افزودن از یک سر و برداشتن از سر دیگر (`queue`) | `deque` |
| دنبالهٔ ثابت، یا کلید مرکب | `tuple` |
| پرسش مکرر «هست یا نه؟» | `set` |
| رسیدن به مقدار با یک نام یا شناسه، یا شمردن | `dict` |
| گرفتن مکرر کوچک‌ترین یا مهم‌ترین | `heapq` |

این جدول نقطهٔ شروع است، نه حکم. همیشه کار واقعی خودت را اندازه بگیر. خودآموز [بنیاد](/courses/bonyad) همین قاعده را دارد: هیچ ادعای هزینه‌ای بدون جدول اندازه‌گیری. [خودآموز دانلودی بنیاد](/store/bonyad-book) نسخهٔ دانلودی همین دوره است.

---
Source: https://yaadestan.com/blog/data-structures-in-python (یادستان, Yaadestan)
