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

آخر این فصل میتوانی:
- بگویی چرا
insert(0, x)وpop(0)هزینهٔO(n)دارند وappendوpop()ندارند - هزینهٔ درج و حذف را بر حسبِ محلش در ظرف گزارش کنی
- با
collections.dequeهزینهٔ ابتدای ظرف را صاف کنی و با جدول ثابتش کنی
قبل از شروع#
از فصلِ ۱: خانههای پیوسته و هماندازه. از فصلِ ۳: append هزینهٔ O(1)ِ amortised دارد.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | حدودِ یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. چرا ابتدای ظرف فرق دارد#
خانههای آرایه پشتِ سرِ هماند و جای خانهٔ i با اندیسش تعیین میشود. پس اگر بخواهی چیزی را در ابتدا جا بدهی، عضوی که تا حالا اندیسِ 0 داشت باید برود به 1، آنی که 1 بود برود به 2، و همینطور تا آخر. هر درج در ابتدا یعنی جابهجا کردنِ همهٔ چیزی که تا حالا داخل ظرف است.
در انتها هیچکدام از اینها لازم نیست: خانهٔ خالیِ بعدی همانجاست و هیچ اندیسی عوض نمیشود.
این را میشود بدونِ ساعت شمرد. دو تابع مینویسیم که کارِ نوشتن در خانهها را دستی انجام میدهند و میشمارند.
🤔 اول حدس بزن: ستونِ نسبت برای هرکدام چه عددی میدهد؟
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)
— نوشتن در انتها
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
2.00 در برابرِ 4.00، بدونِ یک ذره نویز. و فرمولِ سطرِ آخر دقیقاً همان عددِ ستونِ دومِ جدولِ پایینی است: 1 + 2 + 3 + … + n.
۲. حالا با ساعت#
شمارش میگوید O(n) در برابرِ O(n²). ساعت هم باید همین را بگوید — این بار روی متدهای واقعیِ خودِ پایتون.
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")
جوابِ دو نسخه یکی است؟ 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
ستونِ نسبتِ append نزدیکِ 2 و ستونِ نسبتِ insert(0, x) نزدیکِ 4. ساعت و شمارنده یک چیز میگویند.
و به خودِ عددها هم نگاه کن، نه فقط به نسبتها: در n = 80,000 یکی چند میلیثانیه است و دیگری بیش از یک ثانیه. و این فاصله با هر دوبرابر شدنِ n دو برابر میشود، چون یکی خطی است و دیگری درجهدو.
۳. همان داستان، برای حذف#
pop() عضوِ آخر را برمیدارد و pop(0) عضوِ اول را. از بیرون شبیهِ هماند و از نظرِ هزینه دو دنیای متفاوتاند، دقیقاً به همان دلیل: برداشتنِ عضوِ اول یعنی همهٔ بقیه یک خانه عقب بروند.
🤔 اول حدس بزن:
pop()وpop(0)هر دو یک عضو برمیدارند. بنویس ستونِ نسبتِ هر کدام چه عددی میدهد — و اگر فکر میکنی یکیاند، همان را بنویس.
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")
— 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
باز هم 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)جلو میزند.
ولی هیچ کدام از اینها ادعا نیست تا وقتی جدولش را نگرفته باشیم:
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")
همان ترتیبِ نهایی؟ 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
هر دو ستون نزدیکِ 2 — و سطرِ اول تأیید میکند که خروجی هم دقیقاً همان است. یعنی deque همان کار را میکند و مرتبهاش خطی است، نه درجهدو.
۵. سه ظرف، یک عمل، یک جدول#
آخرین اندازهگیریِ فصل: همان n، همان کار، سه راه.
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}")
n = 40,000
روش زمان (ms) نسبت به بهترین
list.append 0.99 1
list.insert(0, x) 359.91 365
deque.appendleft 1.30 1
سه خط کدِ تقریباً یکسان، و یکی از آنها صدها برابر گرانتر.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ سه راهِ ساختنِ یک دنبالهٔ
nتایی، با خروجیِ برابرِ تأییدشده. در کدام بازهٔn؟ جدولهای رشد در ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ و جدولِ آخر در یک اندازهٔ ثابت،n = 40,000. با چند تکرار، و کمینه یا میانگین؟ دو یا سه تکرار بهعلاوهٔ گرمکننده، همیشه کمینه — و هر اجرا ظرفِ تازهٔ خودش را میسازد، چون این توابع ظرف را مصرف میکنند.
🔧 اگر کار نکرد: هر دو ظرف روی ظرفِ خالی خطا میدهند، ولی پیامشان یکی نیست و همین یک نویسه میگوید کدام ظرف را در دست داری:
for empty in ([], deque()):
try:
empty.pop()
except IndexError as err:
print(f"{type(err).__name__}: {err}")
IndexError: pop from empty list
IndexError: pop from an empty deque
اگر پیامِ دومی را گرفتی ولی فکر میکردی یک list داری، جایی در کدت ظرف عوض شده — و این از خواندنِ خودِ کد سختتر پیدا میشود تا از خواندنِ پیامِ خطا.
🤖 از دستیارت بپرس: «چرا
list.insert(0, x)هزینهٔO(n)دارد ولیappendندارد؟» بعد این را هم بپرس: «اگر بخواهم هزار بار در وسطِ یکlistصدهزارتایی درج کنم، هزینهاش چقدر است؟» — جوابِ درست حدودِ نصفِ حالتِ ابتدا است و اگر بتوانی بگویی چرا، قاعدهٔ «بهاندازهٔ تعدادِ عضوهای بعد از محلِ درج» را فهمیدهای.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| shifting | شیفتینگ | جابهجا شدنِ همهٔ عضوهای بعد از محلِ درج یا حذف |
| deque | دِک | ظرفی که در هر دو سرش درج و حذفِ ارزان دارد |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
insert(0, x) یک تلهٔ آشکار است: اسمِ صریحی دارد و همین که ببینیاش میشود شک کرد.
فصلِ بعد دربارهٔ تلههای نامرئی است. چهار تکه کد که هیچکدام حلقهٔ تودرتوی آشکار ندارند و هر چهارتا میتوانند O(n²) باشند. برای هر چهارتا جدول میگیریم — و یکی از آنها بر خلافِ همهٔ کتابها خطی درمیآید — و آخرش یک قاعدهٔ تشخیص درمیآید که با آن میشود این تله را در کدِ خودت پیدا کرد، قبل از اینکه کاربر پیدایش کند.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.