# فصل ۰۴ — `list.insert(0, x)` یک تله است

<div dir="rtl">

# فصل ۰۴ — `list.insert(0, x)` یک تله است

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

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

دو جدولِ دوبرابری می‌گیریم: یکی برای `append` و یکی برای `insert(0, x)`. **ستونِ اولی نزدیکِ `2` است و دومی نزدیکِ `4`.** همان کار، همان تعداد عضو، فقط سرِ دیگرِ ظرف. بعد ظرفِ دیگری معرفی می‌شود که هزینهٔ ابتدای ظرف را دوباره صاف می‌کند — و آن هم با جدول ثابت می‌شود.

![قفسه‌ای پر که با گذاشتنِ یک چیز در ابتدایش، تک‌تکِ اجزایش یک خانه جابه‌جا می‌شوند](/lesson-assets/t2-s04-insert-delete/prompt/01-image-front-of-the-shelf.png)

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

- بگویی چرا `insert(0, x)` و `pop(0)` هزینهٔ `O(n)` دارند و `append` و `pop()` ندارند
- هزینهٔ درج و حذف را **بر حسبِ محلش** در ظرف گزارش کنی
- با `collections.deque` هزینهٔ ابتدای ظرف را صاف کنی و **با جدول** ثابتش کنی

## قبل از شروع

**از فصلِ ۱:** خانه‌های پیوسته و هم‌اندازه. **از فصلِ ۳:** `append` هزینهٔ `O(1)`ِ `amortised` دارد.

</div>

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

<div dir="rtl">

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

## ۱. چرا ابتدای ظرف فرق دارد

خانه‌های آرایه پشتِ سرِ هم‌اند و **جای خانهٔ `i` با اندیسش تعیین می‌شود**. پس اگر بخواهی چیزی را در ابتدا جا بدهی، عضوی که تا حالا اندیسِ `0` داشت باید برود به `1`، آنی که `1` بود برود به `2`، و همین‌طور تا آخر. **هر درج در ابتدا یعنی جابه‌جا کردنِ همهٔ چیزی که تا حالا داخل ظرف است.**

در انتها هیچ‌کدام از این‌ها لازم نیست: خانهٔ خالیِ بعدی همان‌جاست و هیچ اندیسی عوض نمی‌شود.

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

> 🤔 **اول حدس بزن:** ستونِ نسبت برای هرکدام چه عددی می‌دهد؟

</div>

```python
def writes_append(n):
    """n بار در انتها: هر بار فقط یک خانه نوشته می‌شود."""
    slots = []
    written = 0
    for i in range(n):
        slots.append(None)
        slots[len(slots) - 1] = i
        written += 1
    return written


def writes_insert_front(n):
    """n بار در ابتدا: هر بار همهٔ خانه‌های قبلی یکی به جلو می‌روند."""
    slots = []
    written = 0
    for i in range(n):
        slots.append(None)
        for j in range(len(slots) - 1, 0, -1):
            slots[j] = slots[j - 1]
            written += 1
        slots[0] = i
        written += 1
    return written


LADDER = [1_000, 2_000, 4_000, 8_000]
print("— نوشتن در انتها")
table([(n, writes_append(n)) for n in LADDER], "نوشتن در خانه", ",d")
print("\n— نوشتن در ابتدا")
table([(n, writes_insert_front(n)) for n in LADDER], "نوشتن در خانه", ",d")
print("\nراستی‌آزماییِ فرمول در n = 4000:  n =", 4_000,
      "·  n(n+1)/2 =", 4_000 * 4_001 // 2)
```

```text
— نوشتن در انتها
         n     نوشتن در خانه     نسبت به سطر قبل
     1,000             1,000                   —
     2,000             2,000                2.00
     4,000             4,000                2.00
     8,000             8,000                2.00

— نوشتن در ابتدا
         n     نوشتن در خانه     نسبت به سطر قبل
     1,000           500,500                   —
     2,000         2,001,000                4.00
     4,000         8,002,000                4.00
     8,000        32,004,000                4.00

راستی‌آزماییِ فرمول در n = 4000:  n = 4000 ·  n(n+1)/2 = 8002000
```

<div dir="rtl">

**`2.00` در برابرِ `4.00`، بدونِ یک ذره نویز.** و فرمولِ سطرِ آخر دقیقاً همان عددِ ستونِ دومِ جدولِ پایینی است: `1 + 2 + 3 + … + n`.

## ۲. حالا با ساعت

شمارش می‌گوید `O(n)` در برابرِ `O(n²)`. **ساعت هم باید همین را بگوید — این بار روی متدهای واقعیِ خودِ پایتون.**

</div>

```python
def build_append(n):
    out = []
    for i in range(n):
        out.append(i)
    return out


def build_insert_front(n):
    out = []
    for i in range(n):
        out.insert(0, i)
    return out


TIMED = [10_000, 20_000, 40_000, 80_000]
print("جوابِ دو نسخه یکی است؟",
      build_append(500) == list(reversed(build_insert_front(500))))
print("\n— list.append(x)")
table([(n, 1000 * clock(lambda k=n: build_append(k), repeat=2)) for n in TIMED],
      "زمان (ms)", ",.2f")
print("\n— list.insert(0, x)")
table([(n, 1000 * clock(lambda k=n: build_insert_front(k), repeat=2)) for n in TIMED],
      "زمان (ms)", ",.2f")
```

```text-approx
جوابِ دو نسخه یکی است؟ True

— list.append(x)
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.26                   —
    20,000              0.49                1.91
    40,000              1.14                2.34
    80,000              2.24                1.96

— list.insert(0, x)
         n         زمان (ms)     نسبت به سطر قبل
    10,000             22.90                   —
    20,000             90.43                3.95
    40,000            357.84                3.96
    80,000          1,447.42                4.04
```

<div dir="rtl">

**ستونِ نسبتِ `append` نزدیکِ `2` و ستونِ نسبتِ `insert(0, x)` نزدیکِ `4`.** ساعت و شمارنده یک چیز می‌گویند.

و به خودِ عددها هم نگاه کن، نه فقط به نسبت‌ها: در `n = 80,000` یکی چند میلی‌ثانیه است و دیگری بیش از یک ثانیه. **و این فاصله با هر دوبرابر شدنِ `n` دو برابر می‌شود، چون یکی خطی است و دیگری درجه‌دو.**

## ۳. همان داستان، برای حذف

`pop()` عضوِ آخر را برمی‌دارد و `pop(0)` عضوِ اول را. **از بیرون شبیهِ هم‌اند و از نظرِ هزینه دو دنیای متفاوت‌اند**، دقیقاً به همان دلیل: برداشتنِ عضوِ اول یعنی همهٔ بقیه یک خانه عقب بروند.

> 🤔 **اول حدس بزن:** `pop()` و `pop(0)` هر دو یک عضو برمی‌دارند. بنویس ستونِ نسبتِ هر کدام چه عددی می‌دهد — و اگر فکر می‌کنی یکی‌اند، همان را بنویس.

</div>

```python
def drain_back(values):
    while values:
        values.pop()


def drain_front(values):
    while values:
        values.pop(0)


DRAIN = [5_000, 10_000, 20_000, 40_000]
print("— pop()")
table([(n, 1000 * clock(lambda k=n: drain_back(list(range(k))), repeat=2))
       for n in DRAIN], "زمان (ms)", ",.2f")
print("\n— pop(0)")
table([(n, 1000 * clock(lambda k=n: drain_front(list(range(k))), repeat=2))
       for n in DRAIN], "زمان (ms)", ",.2f")
```

```text-approx
— pop()
         n         زمان (ms)     نسبت به سطر قبل
     5,000              0.16                   —
    10,000              0.33                2.00
    20,000              0.65                1.99
    40,000              1.39                2.13

— pop(0)
         n         زمان (ms)     نسبت به سطر قبل
     5,000              1.12                   —
    10,000              4.77                4.25
    20,000             19.17                4.02
    40,000             91.04                4.75
```

<div dir="rtl">

**باز هم `2` در برابرِ `4`.**

> ⚠️ **مواظب باش:** هزینهٔ درج و حذف در یک `list` به **محلش** بند است، نه به خودِ عمل. `insert(len(values), x)` دقیقاً به‌ارزانیِ `append` است و `insert(0, x)` گران‌ترین حالتِ ممکن. **درج در وسط هم نصفِ گران است** — چون فقط نیمهٔ دوم جابه‌جا می‌شود. یک قاعدهٔ ساده: **هزینه به‌اندازهٔ تعدادِ عضوهایی است که بعد از محلِ درج قرار دارند.**

> ✅ **چک کن:** در `build_insert_front` عددِ `0` را به `len(out)` تغییر بده و دوباره بگیر. **ستونِ نسبت باید از `4` به `2` بیفتد** — همان تابع، همان متد، فقط محلِ درج عوض شده. اگر عوض نشد، احتمالاً هنوز `0` را جایی جا گذاشته‌ای؛ `print(len(out))` را داخلِ حلقه بگذار و ببین اندیسی که به `insert` می‌دهی واقعاً با طولِ فعلی جلو می‌رود یا نه.

## ۴. ظرفی که هر دو سر را ارزان می‌کند

اگر مسئله‌ات واقعاً ابتدای ظرف است، **راهش این نیست که `insert(0, x)` را سریع‌تر بنویسی؛ راهش این است که ظرفِ دیگری برداری.**

`collections.deque` دقیقاً برای همین ساخته شده: **در هر دو سرش درج و حذفِ ارزان دارد.** فعلاً همین‌قدر بدان که ساختنش با `list` فرق دارد؛ فصلِ ۷ کاملاً بازش می‌کند و همان‌جا نشان می‌دهد چه چیزی را در ازایش می‌دهد.

> 🤔 **اول حدس بزن:** `deque` ادعا می‌کند در هر دو سر ارزان است. ستونِ نسبتش را حدس بزن، و بنویس در `n = 80,000` چند برابر از `list.insert(0, x)` جلو می‌زند.

**ولی هیچ کدام از این‌ها ادعا نیست تا وقتی جدولش را نگرفته باشیم:**

</div>

```python
from collections import deque


def build_appendleft(n):
    out = deque()
    for i in range(n):
        out.appendleft(i)
    return out


def drain_popleft(values):
    while values:
        values.popleft()


print("همان ترتیبِ نهایی؟", list(build_appendleft(500)) == build_insert_front(500))
print("\n— deque.appendleft(x)")
table([(n, 1000 * clock(lambda k=n: build_appendleft(k), repeat=3)) for n in TIMED],
      "زمان (ms)", ",.2f")
print("\n— deque.popleft()")
table([(n, 1000 * clock(lambda k=n: drain_popleft(deque(range(k))), repeat=3))
       for n in DRAIN], "زمان (ms)", ",.2f")
```

```text-approx
همان ترتیبِ نهایی؟ True

— deque.appendleft(x)
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.48                   —
    20,000              0.62                1.28
    40,000              1.36                2.21
    80,000              2.88                2.12

— deque.popleft()
         n         زمان (ms)     نسبت به سطر قبل
     5,000              0.17                   —
    10,000              0.35                2.03
    20,000              0.73                2.09
    40,000              1.40                1.93
```

<div dir="rtl">

**هر دو ستون نزدیکِ `2` — و سطرِ اول تأیید می‌کند که خروجی هم دقیقاً همان است.** یعنی `deque` همان کار را می‌کند و مرتبه‌اش خطی است، نه درجه‌دو.

## ۵. سه ظرف، یک عمل، یک جدول

آخرین اندازه‌گیریِ فصل: **همان `n`، همان کار، سه راه.**

</div>

```python
N = 40_000
rows = (
    ("list.append", lambda: build_append(N)),
    ("list.insert(0, x)", lambda: build_insert_front(N)),
    ("deque.appendleft", lambda: build_appendleft(N)),
)
best = None
print(f"n = {N:,}\n")
print(f"{'روش':>20}{'زمان (ms)':>14}{'نسبت به بهترین':>18}")
results = [(name, 1000 * clock(fn, repeat=2)) for name, fn in rows]
best = min(t for _, t in results)
for name, t in results:
    print(f"{name:>20}{t:>14.2f}{t / best:>18,.0f}")
```

```text-approx
n = 40,000

                 روش     زمان (ms)    نسبت به بهترین
         list.append          0.99                 1
   list.insert(0, x)        359.91               365
    deque.appendleft          1.30                 1
```

<div dir="rtl">

**سه خط کدِ تقریباً یکسان، و یکی از آن‌ها صدها برابر گران‌تر.**

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

> 🔧 **اگر کار نکرد:** هر دو ظرف روی ظرفِ خالی خطا می‌دهند، ولی **پیامشان یکی نیست** و همین یک نویسه می‌گوید کدام ظرف را در دست داری:

</div>

```python
for empty in ([], deque()):
    try:
        empty.pop()
    except IndexError as err:
        print(f"{type(err).__name__}: {err}")
```

```text
IndexError: pop from empty list
IndexError: pop from an empty deque
```

<div dir="rtl">

اگر پیامِ دومی را گرفتی ولی فکر می‌کردی یک `list` داری، جایی در کدت ظرف عوض شده — و این از خواندنِ خودِ کد سخت‌تر پیدا می‌شود تا از خواندنِ پیامِ خطا.

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

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| shifting | شیفتینگ | جابه‌جا شدنِ همهٔ عضوهای بعد از محلِ درج یا حذف |
| deque | دِک | ظرفی که در هر دو سرش درج و حذفِ ارزان دارد |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا هزینهٔ `insert` به محلش بند است و به خودِ عمل نه؟

**تمرینِ اجباری:** تابعی بنویس که یک `list` صدهزارتایی بسازد و هزار بار در **محلِ `p`** درج کند، و آن را برای `p` برابرِ `0`، `25_000`، `50_000`، `75_000` و `len(values)` زمان بگیر. جدولی از پنج سطر بساز. **سؤالِ اصلی: زمانِ `p = 50_000` نسبت به `p = 0` چقدر است؟** جوابت باید یک نسبت باشد و بگوید با پیش‌بینیِ «هزینه به‌اندازهٔ تعدادِ عضوهای بعد از محلِ درج» می‌خواند یا نه.

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

## در فصل بعد

`insert(0, x)` یک تلهٔ **آشکار** است: اسمِ صریحی دارد و همین که ببینی‌اش می‌شود شک کرد.

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

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t2/s04-insert-delete (یادستان, Yaadestan)
