# فصل ۰۸ — کدام ظرفِ ترتیبی، برای کدام الگوی دسترسی

<div dir="rtl">

# فصل ۰۸ — کدام ظرفِ ترتیبی، برای کدام الگوی دسترسی

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

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

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

![سه ظرفِ هم‌طول با ساختِ متفاوت، کنارِ سه ابزارِ اندازه‌گیری](/lesson-assets/t2-s08-choosing-a-sequence/prompt/01-image-three-containers.png)

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

- **الگوی دسترسیِ** یک مسئله را قبل از انتخابِ ظرف بنویسی
- جدولِ هزینهٔ عملیات را برای `list`، `deque` و `array` بخوانی و راستی‌آزمایی کنی
- ظرف را از روی **نسبتِ خواندن به نوشتن** انتخاب کنی، نه از روی عادت
- بگویی `array` و `bytearray` کِی به‌کار می‌آیند و چه چیزی را از تو می‌گیرند

## قبل از شروع

**از فصلِ ۱:** دسترسی با اندیس در `list` هزینهٔ ثابت دارد. **از فصلِ ۷:** `deque` در دو سرش ارزان است و در وسطش نه.

</div>

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

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-2-arrays-and-lists/session-08-choosing-a-sequence.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. الگوی دسترسی: سؤالی که قبل از انتخاب پرسیده می‌شود

«کدام ظرف بهتر است؟» **سؤالِ بی‌جوابی است**، دقیقاً مثلِ «کدام ابزار بهتر است؟». سؤالی که جواب دارد این است:

> **در این مسئله، کدام عملیات چند بار انجام می‌شود؟**

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

## ۲. جدولِ هزینه، اندازه‌گیری‌شده

هر مرجعی یک جدولِ هزینهٔ عملیات دارد. **قاعدهٔ این دوره این است که جدولِ نقل‌شده را قبول نکنیم**، پس خودمان می‌سازیمش.

> 🤔 **اول حدس بزن:** برای هر شش خانهٔ این جدول حدس بزن کدام ظرف برنده است — و مخصوصاً برای «خواندنِ خانهٔ وسط» در `deque` حدس بزن چند برابرِ `list` می‌شود.

</div>

```python
from array import array
from collections import deque

N = 100_000
OPS = 20_000
rng = random.Random(SEED)
picks = [rng.randrange(N) for _ in range(OPS)]


def read_many(box, idxs):
    seen = None
    for i in idxs:
        seen = box[i]
    return seen


def repeat_op(make, op, times=OPS):
    box = make()
    return clock(lambda: [op(box) for _ in range(times)], repeat=3) / times


print(f"{'عملیات':>26}{'list (µs)':>13}{'deque (µs)':>13}{'array (µs)':>13}")
rows = [
    ("خواندن با اندیسِ تصادفی",
     lambda: clock(lambda: read_many(list(range(N)), picks), repeat=3) / OPS,
     lambda: clock(lambda: read_many(deque(range(N)), picks), repeat=3) / OPS,
     lambda: clock(lambda: read_many(array("q", range(N)), picks), repeat=3) / OPS),
    ("افزودن به انتها",
     lambda: repeat_op(lambda: list(range(N)), lambda b: b.append(1)),
     lambda: repeat_op(lambda: deque(range(N)), lambda b: b.append(1)),
     lambda: repeat_op(lambda: array("q", range(N)), lambda b: b.append(1))),
    ("افزودن به ابتدا",
     lambda: repeat_op(lambda: list(range(N)), lambda b: b.insert(0, 1)),
     lambda: repeat_op(lambda: deque(range(N)), lambda b: b.appendleft(1)),
     lambda: repeat_op(lambda: array("q", range(N)), lambda b: b.insert(0, 1))),
]
for name, a, b, c in rows:
    print(f"{name:>26}{1e6 * a():>13.4f}{1e6 * b():>13.4f}{1e6 * c():>13.4f}")
```

```text-approx
                    عملیات    list (µs)   deque (µs)   array (µs)
   خواندن با اندیسِ تصادفی       0.1198       1.1876       0.3380
           افزودن به انتها       0.0663       0.0534       0.1293
           افزودن به ابتدا      59.4147       0.0595      26.5636
```

<div dir="rtl">

**سه سطر، و هیچ ستونی در هر سه برنده نیست.**

- **خواندن با اندیس:** `list` ارزان‌ترین است و `array` نزدیکِ سه برابرش — چون هر خانه‌اش عددِ خام است و برای برگرداندنش باید یک شیءِ پایتونی از رویش ساخته شود. `deque` نزدیکِ ده برابرِ `list` است، چون برای رسیدن به اندیسِ وسط باید از یکی از دو سر راه بیفتد.
- **افزودن به انتها:** هر سه ارزان و هر سه در یک بازه.
- **افزودن به ابتدا:** `deque` ارزان، و `list` و `array` هر دو صدها برابر گران‌تر — چون هر دو نوارِ پیوسته‌اند و باید همه‌چیز را جابه‌جا کنند.

**پس جدولِ تصمیم را نمی‌شود به یک ستون خلاصه کرد.** هر خانه‌اش یک معامله است.

> ✅ **چک کن:** `picks` را با `[0] * OPS` عوض کن و فقط سطرِ اول را دوباره بگیر. **ستونِ `deque` باید به‌اندازهٔ `list` ارزان شود.** اگر نشد، `picks` را جای دیگری هم به‌کار برده‌ای. **این آزمایش می‌گوید هزینهٔ `deque` به خودِ خواندن نیست، به فاصلهٔ اندیس تا نزدیک‌ترین سر است.**

## ۳. همان بارِ کاری، دو نسبتِ متفاوت

جدولِ بالا هزینهٔ **تکِ عملیات** را می‌دهد. **تصمیم ولی به ترکیب بند است، نه به تک‌عملیات.**

پس یک بارِ کاریِ ثابت می‌سازیم و فقط نسبتِ خواندن به نوشتن را عوض می‌کنیم.

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

</div>

```python
WRITES = 10_000


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


def write_front(box, k):
    if isinstance(box, deque):
        for i in range(k):
            box.appendleft(i)
    else:
        for i in range(k):
            box.insert(0, i)
    return len(box)


base_l = clock(lambda: list(range(N)), repeat=3)
base_d = clock(lambda: deque(range(N)), repeat=3)
read_l = clock(lambda: read_only(list(range(N)), picks), repeat=3) - base_l
read_d = clock(lambda: read_only(deque(range(N)), picks), repeat=3) - base_d
write_l = clock(lambda: write_front(list(range(N)), WRITES), repeat=2) - base_l
write_d = clock(lambda: write_front(deque(range(N)), WRITES), repeat=2) - base_d

print(f"روی {N:,} عنصر، هزینهٔ ساختنِ خودِ ظرف کم شده\n")
print(f"{'الگوی دسترسی':>26}{'list (ms)':>13}{'deque (ms)':>13}"
      f"{'برنده':>9}{'چند برابر':>12}")
for label, tl, td in ((f"{OPS:,} خواندنِ تصادفی", read_l, read_d),
                      (f"{WRITES:,} افزودن به ابتدا", write_l, write_d)):
    winner = "list" if tl < td else "deque"
    print(f"{label:>26}{1000 * tl:>13.2f}{1000 * td:>13.2f}"
          f"{winner:>9}{max(tl, td) / min(tl, td):>12,.0f}")
```

```text-approx
روی 100,000 عنصر، هزینهٔ ساختنِ خودِ ظرف کم شده

              الگوی دسترسی    list (ms)   deque (ms)    برنده   چند برابر
     20,000 خواندنِ تصادفی         1.52        22.76     list          15
    10,000 افزودن به ابتدا       483.71         0.80    deque         607
```

<div dir="rtl">

**همان دو ظرف، همان داده، همان `n` — و برنده عوض شد.**

در الگوی خواندن‌محور `list` بیش از ده برابر جلوست، و در الگوی نوشتن‌محور `deque` **صدها برابر**. **هیچ‌کدام از این دو عدد به‌تنهایی «کدام ظرف بهتر است» را جواب نمی‌دهد؛ هر دو با هم جواب می‌دهند که سؤال غلط بوده.**

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

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** `list` و `deque` روی دو الگوی دسترسیِ متفاوت با همان داده و همان اندیس‌های تصادفیِ ثابت. **در کدام بازهٔ `n`؟** یک اندازه، `n = 100,000`، با بیست هزار خواندن و ده هزار نوشتن — **ادعای این آزمایش دربارهٔ رشد نیست، دربارهٔ ترکیبِ عملیات است.** **با چند تکرار، و کمینه یا میانگین؟** دو تا سه تکرار، کمینه، و **هزینهٔ ساختنِ خودِ ظرف جدا اندازه گرفته و کم شد** — وگرنه همان یک ساخت نتیجه را عوض می‌کرد.

## ۴. وقتی دیوار حافظه است

تا اینجا همه‌چیز دربارهٔ زمان بود. **گاهی دیوارِ مسئله زمان نیست، حافظه است** — و آن‌جا `list` گران‌ترین انتخابِ ممکن است.

دلیلش را فصلِ ۱ گفت: هر خانهٔ `list` **یک ارجاع** است، نه خودِ مقدار. پس برای صد هزار عدد، هم صد هزار ارجاعِ هشت‌بایتی داری و هم صد هزار شیءِ عددِ جدا.

`array` از ماژولِ `array` مقدارها را **خام و پشتِ سرِ هم** نگه می‌دارد، و `bytearray` همان کار را برای عددهای صفر تا دویست و پنجاه و پنج می‌کند.

</div>

```python
M = 200_000
lst = list(range(M))
arr = array("q", range(M))          # هر عضو یک عددِ صحیحِ هشت‌بایتی
ba = bytearray(M)                   # هر عضو یک بایت
one_int = sys.getsizeof(1_000_000)

print(f"{'ظرف':>12}{'خودِ ظرف':>14}{'با عددها':>16}")
print(f"{'list':>12}{sys.getsizeof(lst):>14,}"
      f"{sys.getsizeof(lst) + M * one_int:>16,}")
print(f"{'array(q)':>12}{sys.getsizeof(arr):>14,}{sys.getsizeof(arr):>16,}")
print(f"{'bytearray':>12}{sys.getsizeof(ba):>14,}{sys.getsizeof(ba):>16,}")
print(f"\nیک عددِ صحیحِ پایتون به‌تنهایی: {one_int} بایت")
print(f"list در برابرِ array : "
      f"{(sys.getsizeof(lst) + M * one_int) / sys.getsizeof(arr):.1f} برابر")
print(f"list در برابرِ bytearray: "
      f"{(sys.getsizeof(lst) + M * one_int) / sys.getsizeof(ba):.1f} برابر")
```

```text
         ظرف      خودِ ظرف        با عددها
        list     1,600,056       7,200,056
    array(q)     1,691,304       1,691,304
   bytearray       200,057         200,057

یک عددِ صحیحِ پایتون به‌تنهایی: 28 بایت
list در برابرِ array : 4.3 برابر
list در برابرِ bytearray: 36.0 برابر
```

<div dir="rtl">

**چند برابر برای `array` و ده‌ها برابر برای `bytearray`.** روی دویست هزار عضو این یعنی چند مگابایت اختلاف؛ روی بیست میلیون عضو یعنی تفاوتِ «جا می‌شود» و «نشستِ Colab بی‌صدا ری‌استارت می‌شود».

**و بهایش این است که این ظرف‌ها فقط یک نوع داده قبول می‌کنند.** `list` هر چیزی را می‌پذیرد چون ارجاع نگه می‌دارد؛ `array` باید بداند هر خانه چند بایت است، و همان قیدِ فصلِ ۱ است که دسترسی با اندیس را ارزان می‌کند.

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

## ۵. جدولِ تصمیم

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

</div>

| الگوی دسترسی | ظرفِ درست | چرا (فصل) |
|---|---|---|
| خواندنِ زیاد با اندیسِ دلخواه | `list` | ۱ — دسترسیِ `O(1)` |
| افزودن و برداشتن فقط از انتها (`stack`) | `list` | ۳ و ۷ — `append` و `pop` هر دو `O(1)`ِ `amortised` |
| افزودن و برداشتن از هر دو سر (`queue`) | `deque` | ۴ و ۷ — `popleft` در برابرِ `pop(0)` |
| درج در وسط، با اندیس | `list` | ۶ — حتی `linked list` هم نبرد |
| عددِ خام و زیاد، حافظه تنگ | `array` / `bytearray` | ۸ — چند برابر تا ده‌ها برابر کمتر |
| پرسشِ مکررِ «هست یا نه؟» | هیچ‌کدام | ۵ — ترمِ ۳ |

<div dir="rtl">

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

> 🔧 **اگر کار نکرد:** `array` سخت‌گیر است و همان سخت‌گیری چیزی است که ارزانش می‌کند:

</div>

```python
try:
    array("q", [1, 2, "سه"])
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
try:
    bytearray([1, 2, 300])
except ValueError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: 'str' object cannot be interpreted as an integer
ValueError: byte must be in range(0, 256)
```

<div dir="rtl">

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

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

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| access pattern | اکسس پترن | اینکه در یک مسئله کدام عملیات چند بار انجام می‌شود |
| `array` | اَرِی | ظرفی که مقدارهای هم‌نوع را خام و پشتِ سرِ هم نگه می‌دارد |
| `bytearray` | بایت‌اَرِی | ظرفی از بایت‌های خام، برای عددهای صفر تا ۲۵۵ |

<div dir="rtl">

## تمرین‌ها

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

**تمرینِ اجباری:** آزمایشِ بخشِ ۳ را با **پنج نسبت** تکرار کن: نوشتن به خواندنِ ۱ به ۱۰۰، ۱ به ۱۰، ۱ به ۱، ۱۰ به ۱ و ۱۰۰ به ۱. برای هر کدام برندهٔ بینِ `list` و `deque` را بنویس. **سؤالِ اصلی: نقطهٔ تقاطع کجاست؟** یعنی از کدام نسبت به بعد برنده عوض می‌شود. جوابت باید یک نسبت باشد، و بگو این عدد به `n` هم بستگی دارد یا نه.

**تمرینِ ستاره‌دار ⭐:** یک ظرفِ ترکیبی بنویس که **از هر دو دنیا بردارد**: داده را در یک `list` نگه می‌دارد ولی افزودن به ابتدا را در یک `deque`ِ جداگانه جمع می‌کند و فقط وقتی کسی با اندیس چیزی خواست، دو تکه را یکی می‌کند. **قبل از هر اندازه‌گیری پیش‌بینی کن روی کدام‌یک از پنج نسبتِ تمرینِ قبل برنده می‌شود و روی کدام بازنده.** بعد اندازه بگیر. **و در آخر بنویس چه هزینه‌ای پرداختی که در هیچ جدولی دیده نمی‌شود** — این سؤال از خودِ عددها مهم‌تر است و ترمِ ۶ کاملاً درباره‌اش است.

## در فصل بعد

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

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

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t2/s08-choosing-a-sequence (یادستان, Yaadestan)
