# فصل ۰۲ — `list` پایتون یک آرایهٔ پویاست

<div dir="rtl">

# فصل ۰۲ — `list` پایتون یک آرایهٔ پویاست

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

فصلِ قبل گفت خانه‌های آرایه پشتِ سرِ هم و به تعدادِ ثابت‌اند. **ولی `list` پایتون `append` دارد** — یعنی تعدادِ خانه‌ها ثابت نیست. این دو حرف چطور با هم می‌سازند؟

جواب را با یک ابزار پیدا می‌کنیم که مستقیماً به حافظه نگاه می‌کند: `sys.getsizeof`. با آن می‌بینی که **یک `list` تقریباً همیشه بیشتر از طولش خانه دارد**، این خانه‌های اضافی پله‌پله زیاد می‌شوند، و هر پله یک **کپیِ کاملِ داده** است. برای رسیدن به هشت هزار عضو، ظرف دقیقاً ۴۵ بار بزرگ می‌شود — و این عدد روی ماشینِ تو هم دقیقاً همین است.

![کشویی با یک ردیف خانهٔ هم‌اندازه که نیمی پر است و نیمی از پیش ساخته و خالی مانده](/lesson-assets/t2-s02-dynamic-array/prompt/01-image-drawer-with-spare-slots.png)

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

- تفاوتِ **طول** و **ظرفیت** یک `list` را بگویی و هر دو را اندازه بگیری
- با `sys.getsizeof` پله‌های رشدِ یک `list` را ببینی
- بشماری یک `list` برای رسیدن به `n` عضو چند بار بزرگ می‌شود
- نشان بدهی که هزینهٔ کپیِ کاملِ داده `O(n)` است

## قبل از شروع

**از فصلِ ۱:** خانه‌های پیوسته و هم‌اندازه، و اینکه دسترسی با اندیس به همین پیوستگی بند است.

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

</div>

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

<div dir="rtl">

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

## ۱. تناقضِ ظاهری

آرایه یعنی نوارِ پیوستهٔ خانه‌ها. **نوارِ پیوسته را نمی‌شود کش داد**، چون درست بعد از آخرین خانه‌اش ممکن است چیزِ دیگری نشسته باشد.

پس `append` چطور کار می‌کند؟ **راهش این است که ظرف از اول بزرگ‌تر از چیزی که لازم دارد ساخته شود.** یک `list` دو عددِ متفاوت دارد:

- **طول (`len`)** — چند خانه واقعاً پر است
- **ظرفیت** — چند خانه اصلاً ساخته شده

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

این حرف قابلِ آزمون است. `sys.getsizeof` تعدادِ بایت‌های خودِ ظرف را می‌دهد — نه چیزهایی که داخلش ارجاع داده شده — پس از رویش می‌شود ظرفیت را حساب کرد.

## ۲. پله‌های `getsizeof`

> 🤔 **اول حدس بزن:** یک `list` خالی می‌سازیم و هجده بار `append` می‌کنیم و قبل از هر بار `sys.getsizeof` می‌گیریم. بنویس انتظار داری آن عدد چند بار عوض شود: یک بار؟ هجده بار؟ چند بار؟

</div>

```python
CELL = 8                               # هر خانه یک ارجاعِ هشت‌بایتی است
EMPTY = sys.getsizeof([])


def capacity(values):
    """چند خانه ساخته شده — از روی بایت‌های خودِ ظرف."""
    return (sys.getsizeof(values) - EMPTY) // CELL


print("بایت‌های یک list خالی:", EMPTY)
print(f"\n{'طول':>6}{'بایت':>10}{'ظرفیت':>10}")
values = []
previous = 0
for i in range(18):
    cap = capacity(values)
    mark = "بزرگ شد" if cap != previous else ""
    print(f"{len(values):>6}{sys.getsizeof(values):>10}{cap:>10}   {mark}".rstrip())
    previous = cap
    values.append(i)
```

```text
بایت‌های یک list خالی: 56

   طول      بایت     ظرفیت
     0        56         0
     1        88         4   بزرگ شد
     2        88         4
     3        88         4
     4        88         4
     5       120         8   بزرگ شد
     6       120         8
     7       120         8
     8       120         8
     9       184        16   بزرگ شد
    10       184        16
    11       184        16
    12       184        16
    13       184        16
    14       184        16
    15       184        16
    16       184        16
    17       248        24   بزرگ شد
```

<div dir="rtl">

**عدد فقط در چهار سطر عوض شد، نه در هجده سطر.** ظرفیت `4`، بعد `8`، بعد `16`، بعد `24` — و بینِ هر دو پله، `append` هیچ خانهٔ تازه‌ای نمی‌سازد.

به سطرِ `طول = 1` دقت کن: ظرفیت `4` است. **سه خانهٔ خالیِ آماده، همان لحظه.** این همان «تخصیصِ اضافی» است و دلیلِ وجودش دقیقاً این است که سه `append` بعدی مجانی باشند.

> ✅ **چک کن:** `capacity(list(range(100)))` را بگیر. **عدد باید دقیقاً `100` باشد، نه بیشتر** — وقتی پایتون از اول می‌داند چند تا عضو هست، هیچ خانهٔ اضافه‌ای نمی‌سازد. حالا `capacity(list(x for x in range(100)))` را هم بگیر: **این یکی بیشتر از صد است**، چون تعدادِ نهایی از قبل معلوم نیست. **تخصیصِ اضافی هزینهٔ ندانستن است، نه یک عادت.**

## ۳. چند بار بزرگ می‌شود؟

حالا سؤالِ اصلی: **برای رسیدن به `n` عضو، ظرف چند بار بزرگ می‌شود؟**

> 🤔 **اول حدس بزن:** ستونِ نسبتِ این جدول را حدس بزن. اگر برای رسیدن به هزار عضو مثلاً بیست بار بزرگ شود، برای دو هزار عضو چند بار؟

</div>

```python
def growth_events(n):
    """چند بار ظرفیتِ یک list در مسیرِ رسیدن به n عضو عوض می‌شود."""
    values = []
    events = 0
    cap = capacity(values)
    for i in range(n):
        values.append(i)
        new = capacity(values)
        if new != cap:
            events += 1
            cap = new
    return events


table([(n, growth_events(n)) for n in SIZES], "بزرگ‌شدن", ",d")
print("\nتفاضلِ سطرها:", [growth_events(2 * n) - growth_events(n) for n in SIZES[:-1]])
```

```text
         n          بزرگ‌شدن     نسبت به سطر قبل
     1,000                28                   —
     2,000                33                1.18
     4,000                39                1.18
     8,000                45                1.15

تفاضلِ سطرها: [5, 6, 6]
```

<div dir="rtl">

**ستونِ نسبت نزدیکِ `1.15` است — نه `2`.** یعنی با دو برابر شدنِ `n`، تعدادِ بزرگ‌شدن‌ها دو برابر نمی‌شود.

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

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

## ۴. هر بزرگ‌شدن یک کپیِ کامل است

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

خودِ این کپی را می‌شود جدا اندازه گرفت، چون `list(values)` دقیقاً همان کار را می‌کند: یک نوارِ تازه و یک انتقالِ کامل.

> 🤔 **اول حدس بزن:** ستونِ نسبتِ زمانِ `list(values)` با دو برابر شدنِ `n` چه عددی می‌شود؟

</div>

```python
COPY = [500_000, 1_000_000, 2_000_000, 4_000_000]
big = {n: [None] * n for n in COPY}        # ظرفِ خالی، بدونِ هیچ عددی داخلش
print("طول و ظرفیت برابرند؟", all(len(big[n]) == capacity(big[n]) for n in COPY))
table([(n, 1000 * clock(lambda v=big[n]: list(v), repeat=7)) for n in COPY],
      "زمان کپی (ms)", ",.2f")
del big
```

```text-approx
طول و ظرفیت برابرند؟ True
         n     زمان کپی (ms)     نسبت به سطر قبل
   500,000              1.37                   —
 1,000,000              2.98                2.18
 2,000,000              5.85                1.96
 4,000,000             12.08                2.06
```

<div dir="rtl">

**ستونِ نسبت نزدیکِ `2` است: کپی `O(n)` است.**

پس هر بار که یک `list` بزرگ می‌شود، کاری به‌اندازهٔ طولِ فعلی‌اش انجام می‌دهد. **و همین‌جا یک نگرانیِ کاملاً بجا پیش می‌آید:** اگر `append` گاهی `O(n)` است، پس ساختنِ یک `list` `n`تایی با `n` بار `append` باید `O(n²)` باشد.

**این استدلال ظاهراً بی‌عیب است و جوابش غلط است.** فصلِ بعد کلاً دربارهٔ همین است.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** هزینهٔ ساختنِ یک کپیِ کامل از یک `list`، با خودش در چهار اندازه. **در کدام بازهٔ `n`؟** ۵۰۰٬۰۰۰ تا ۴٬۰۰۰٬۰۰۰ — عمداً بزرگ، چون کپی در اندازه‌های کوچک زیرِ نویز گم می‌شود. **با چند تکرار، و کمینه یا میانگین؟** هفت تکرار به‌علاوهٔ یک گرم‌کننده، کمینه.

## ۵. ظرفیت مالِ `list` است، نه مالِ همه

`tuple` هم یک نوارِ پیوسته است، **ولی هیچ خانهٔ اضافه‌ای ندارد** — چون قرار نیست هیچ‌وقت بزرگ شود.

</div>

```python
for n in (0, 1, 4, 100):
    t = tuple(range(n))
    lst = list(range(n))
    print(f"n={n:>4}   tuple {sys.getsizeof(t):>5} بایت   ·   list {sys.getsizeof(lst):>5} بایت")
```

```text
n=   0   tuple    40 بایت   ·   list    56 بایت
n=   1   tuple    48 بایت   ·   list    72 بایت
n=   4   tuple    72 بایت   ·   list    88 بایت
n= 100   tuple   840 بایت   ·   list   856 بایت
```

<div dir="rtl">

**`tuple` کوچک‌تر است و همیشه دقیقاً به‌اندازهٔ طولش.** این تنها تفاوتِ `list` و `tuple` نیست ولی مهم‌ترینِ تفاوت‌هایشان از نظرِ حافظه است.

> 🔧 **اگر کار نکرد:** اگر روی چیزی `append` بزنی که آرایهٔ پویا نیست، پیام صریح است:

</div>

```python
try:
    (1, 2, 3).append(4)
except AttributeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
AttributeError: 'tuple' object has no attribute 'append'
```

<div dir="rtl">

**و این خطا یک واقعیتِ حافظه را لو می‌دهد، نه یک تصمیمِ سلیقه‌ای.** `tuple` متدِ `append` ندارد چون خانهٔ خالی ندارد که پرش کند؛ برای اضافه کردن باید کلِ نوار دوباره ساخته شود — که همان `t + (4,)` است و یک `tuple` تازه می‌دهد، نه همان یکی.

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

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| dynamic array | داینامیک اَرِی | آرایه‌ای که با پر شدن، نوارِ بزرگ‌تری می‌سازد و داده را منتقل می‌کند |
| capacity | کپسیتی | تعدادِ خانه‌های ساخته‌شده، چه پر باشند چه خالی |
| over-allocation | اُوِرالوکیشن | ساختنِ خانهٔ بیشتر از چیزی که همین حالا لازم است |
| reallocation | ری‌الوکیشن | ساختنِ نوارِ تازه و کپیِ کاملِ داده به آن |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: تفاوتِ طول و ظرفیت چیست، و کدامشان را `len` به تو می‌دهد؟

**تمرینِ اجباری:** تابعی بنویس که تا `n` بار `append` کند و **فهرستِ همهٔ ظرفیت‌هایی را که ظرف از آن‌ها رد شده** برگرداند. برای `n = 100` اجرایش کن و فهرست را چاپ کن. **حالا دو سؤال:** نسبتِ هر ظرفیت به ظرفیتِ قبلی‌اش در سطرهای اول چقدر است و در سطرهای آخر چقدر؟ و آیا این نسبت به یک عددِ ثابت نزدیک می‌شود یا نه؟ جوابت باید یک عدد داشته باشد.

**تمرینِ ستاره‌دار ⭐:** با `growth_events` نشان بده که تعدادِ بزرگ‌شدن‌ها `O(log n)` است. **پروتکلِ کاملِ فصلِ ۸ ترمِ ۱ را اجرا کن:** جدولِ چهار اندازه‌ای بساز، ستونِ `بزرگ‌شدن ÷ log2(n)` را حساب کن تا انتخابِ شکل را تأیید کنی، معیارِ پذیرش را **قبل از اجرا** بنویس، تعدادِ بزرگ‌شدن‌ها برای `n = 16_000` را پیش‌بینی کن و خطای نسبی را گزارش کن. **چون این عددها قطعی‌اند، اگر پیش‌بینی‌ات رد شد تقصیرِ نویز نیست — یعنی شکلی که انتخاب کرده‌ای دقیق نیست.**

## در فصل بعد

این فصل با یک تناقضِ حل‌نشده تمام شد: **اگر بعضی از `append`ها یک کپیِ کاملِ `O(n)` هستند، چرا ساختنِ یک `list` بزرگ با `append` سریع است؟**

فصلِ بعد جوابش را با دو اندازه‌گیری می‌دهد. اول تک‌تکِ چهارصد هزار `append` را جداگانه می‌سنجد و **گران‌ترین‌هایشان را پیدا می‌کند** — که هزاران برابر گران‌تر از بقیه‌اند و دقیقاً روی همان لحظه‌های بزرگ‌شدن افتاده‌اند. بعد نشان می‌دهد که میانگینِ همان‌ها **صاف** است. اسمِ این پدیده `amortised` است، و همان‌جا می‌بینی که اگر ظرفیت به‌جای ضرب‌شدن، هر بار مقدارِ ثابتی اضافه می‌شد، کلِ ماجرا `O(n²)` می‌شد.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t2/s02-dynamic-array (یادستان, Yaadestan)
