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

آخر این فصل میتوانی:
- تفاوتِ طول و ظرفیت یک
listرا بگویی و هر دو را اندازه بگیری - با
sys.getsizeofپلههای رشدِ یکlistرا ببینی - بشماری یک
listبرای رسیدن بهnعضو چند بار بزرگ میشود - نشان بدهی که هزینهٔ کپیِ کاملِ داده
O(n)است
قبل از شروع#
از فصلِ ۱: خانههای پیوسته و هماندازه، و اینکه دسترسی با اندیس به همین پیوستگی بند است.
نکتهٔ سنجش: عددهای این فصل از sys.getsizeof میآیند و قطعیاند — نه ساعتاند و نه نویز دارند. تنها جدولِ لرزانِ فصل، آخری است.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. تناقضِ ظاهری#
آرایه یعنی نوارِ پیوستهٔ خانهها. نوارِ پیوسته را نمیشود کش داد، چون درست بعد از آخرین خانهاش ممکن است چیزِ دیگری نشسته باشد.
پس append چطور کار میکند؟ راهش این است که ظرف از اول بزرگتر از چیزی که لازم دارد ساخته شود. یک list دو عددِ متفاوت دارد:
- طول (
len) — چند خانه واقعاً پر است - ظرفیت — چند خانه اصلاً ساخته شده
تا وقتی طول از ظرفیت کمتر است، append فقط یک خانهٔ خالیِ آماده را پر میکند. وقتی طول به ظرفیت رسید، نوارِ بزرگتری جای دیگری ساخته میشود و همهٔ داده به آنجا کپی میشود.
این حرف قابلِ آزمون است. sys.getsizeof تعدادِ بایتهای خودِ ظرف را میدهد — نه چیزهایی که داخلش ارجاع داده شده — پس از رویش میشود ظرفیت را حساب کرد.
۲. پلههای getsizeof#
🤔 اول حدس بزن: یک
listخالی میسازیم و هجده بارappendمیکنیم و قبل از هر بارsys.getsizeofمیگیریم. بنویس انتظار داری آن عدد چند بار عوض شود: یک بار؟ هجده بار؟ چند بار؟
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)
بایتهای یک 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 بزرگ شد
عدد فقط در چهار سطر عوض شد، نه در هجده سطر. ظرفیت 4، بعد 8، بعد 16، بعد 24 — و بینِ هر دو پله، append هیچ خانهٔ تازهای نمیسازد.
به سطرِ طول = 1 دقت کن: ظرفیت 4 است. سه خانهٔ خالیِ آماده، همان لحظه. این همان «تخصیصِ اضافی» است و دلیلِ وجودش دقیقاً این است که سه append بعدی مجانی باشند.
✅ چک کن:
capacity(list(range(100)))را بگیر. عدد باید دقیقاً100باشد، نه بیشتر — وقتی پایتون از اول میداند چند تا عضو هست، هیچ خانهٔ اضافهای نمیسازد. حالاcapacity(list(x for x in range(100)))را هم بگیر: این یکی بیشتر از صد است، چون تعدادِ نهایی از قبل معلوم نیست. تخصیصِ اضافی هزینهٔ ندانستن است، نه یک عادت.
۳. چند بار بزرگ میشود؟#
حالا سؤالِ اصلی: برای رسیدن به n عضو، ظرف چند بار بزرگ میشود؟
🤔 اول حدس بزن: ستونِ نسبتِ این جدول را حدس بزن. اگر برای رسیدن به هزار عضو مثلاً بیست بار بزرگ شود، برای دو هزار عضو چند بار؟
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]])
n بزرگشدن نسبت به سطر قبل
1,000 28 —
2,000 33 1.18
4,000 39 1.18
8,000 45 1.15
تفاضلِ سطرها: [5, 6, 6]
ستونِ نسبت نزدیکِ 1.15 است — نه 2. یعنی با دو برابر شدنِ n، تعدادِ بزرگشدنها دو برابر نمیشود.
و سطرِ آخر دقیقترش میکند: هر بار که n دو برابر میشود، فقط شش بزرگشدنِ تازه اضافه میشود. این همان امضایی است که در فصلِ ۵ ترمِ ۱ برای halve_down دیدی، فقط برعکس: آنجا هر دوبرابر شدنِ n یک قدم اضافه میکرد، اینجا شش قدم. هر دو O(log n) هستند؛ فقط پایهٔ لگاریتمشان فرق دارد.
از همینجا میشود گفت ظرفیت چطور بزرگ میشود: اگر هر بار در عددِ ثابتِ f ضرب شود، برای رسیدن به n تعدادِ پلهها همان چیزی است که در آن ضرب میشود تا n شود. و شش پله برای دو برابر شدن یعنی f حدودِ 1.12 است، نه 2. فصلِ بعد این عدد را مستقیماً اندازه میگیرد.
۴. هر بزرگشدن یک کپیِ کامل است#
بزرگشدن ارزان نیست: نوارِ تازه جای دیگری ساخته میشود و همهٔ خانههای قبلی باید به آنجا منتقل شوند. هزینهٔ این کپی به طولِ فعلی بند است.
خودِ این کپی را میشود جدا اندازه گرفت، چون list(values) دقیقاً همان کار را میکند: یک نوارِ تازه و یک انتقالِ کامل.
🤔 اول حدس بزن: ستونِ نسبتِ زمانِ
list(values)با دو برابر شدنِnچه عددی میشود؟
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
طول و ظرفیت برابرند؟ 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
ستونِ نسبت نزدیکِ 2 است: کپی O(n) است.
پس هر بار که یک list بزرگ میشود، کاری بهاندازهٔ طولِ فعلیاش انجام میدهد. و همینجا یک نگرانیِ کاملاً بجا پیش میآید: اگر append گاهی O(n) است، پس ساختنِ یک list nتایی با n بار append باید O(n²) باشد.
این استدلال ظاهراً بیعیب است و جوابش غلط است. فصلِ بعد کلاً دربارهٔ همین است.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ هزینهٔ ساختنِ یک کپیِ کامل از یک
list، با خودش در چهار اندازه. در کدام بازهٔn؟ ۵۰۰٬۰۰۰ تا ۴٬۰۰۰٬۰۰۰ — عمداً بزرگ، چون کپی در اندازههای کوچک زیرِ نویز گم میشود. با چند تکرار، و کمینه یا میانگین؟ هفت تکرار بهعلاوهٔ یک گرمکننده، کمینه.
۵. ظرفیت مالِ list است، نه مالِ همه#
tuple هم یک نوارِ پیوسته است، ولی هیچ خانهٔ اضافهای ندارد — چون قرار نیست هیچوقت بزرگ شود.
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} بایت")
n= 0 tuple 40 بایت · list 56 بایت
n= 1 tuple 48 بایت · list 72 بایت
n= 4 tuple 72 بایت · list 88 بایت
n= 100 tuple 840 بایت · list 856 بایت
tuple کوچکتر است و همیشه دقیقاً بهاندازهٔ طولش. این تنها تفاوتِ list و tuple نیست ولی مهمترینِ تفاوتهایشان از نظرِ حافظه است.
🔧 اگر کار نکرد: اگر روی چیزی
appendبزنی که آرایهٔ پویا نیست، پیام صریح است:
try:
(1, 2, 3).append(4)
except AttributeError as err:
print(f"{type(err).__name__}: {err}")
AttributeError: 'tuple' object has no attribute 'append'
و این خطا یک واقعیتِ حافظه را لو میدهد، نه یک تصمیمِ سلیقهای. tuple متدِ append ندارد چون خانهٔ خالی ندارد که پرش کند؛ برای اضافه کردن باید کلِ نوار دوباره ساخته شود — که همان t + (4,) است و یک tuple تازه میدهد، نه همان یکی.
🤖 از دستیارت بپرس: «تفاوتِ طول و ظرفیت در یک آرایهٔ پویا چیست؟» بعد این را هم بپرس: «چرا پایتون وقتی
list(range(17))میسازد ظرفیتِ اضافه نمیگیرد ولی وقتی هفده بارappendمیکنی میگیرد؟» — جوابش این است که در حالتِ اول طولِ نهایی از قبل معلوم است، و اگر بتوانی همین را بگویی، فهمیدهای تخصیصِ اضافی هزینهٔ ندانستن است.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| dynamic array | داینامیک اَرِی | آرایهای که با پر شدن، نوارِ بزرگتری میسازد و داده را منتقل میکند |
| capacity | کپسیتی | تعدادِ خانههای ساختهشده، چه پر باشند چه خالی |
| over-allocation | اُوِرالوکیشن | ساختنِ خانهٔ بیشتر از چیزی که همین حالا لازم است |
| reallocation | ریالوکیشن | ساختنِ نوارِ تازه و کپیِ کاملِ داده به آن |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
این فصل با یک تناقضِ حلنشده تمام شد: اگر بعضی از appendها یک کپیِ کاملِ O(n) هستند، چرا ساختنِ یک list بزرگ با append سریع است؟
فصلِ بعد جوابش را با دو اندازهگیری میدهد. اول تکتکِ چهارصد هزار append را جداگانه میسنجد و گرانترینهایشان را پیدا میکند — که هزاران برابر گرانتر از بقیهاند و دقیقاً روی همان لحظههای بزرگشدن افتادهاند. بعد نشان میدهد که میانگینِ همانها صاف است. اسمِ این پدیده amortised است، و همانجا میبینی که اگر ظرفیت بهجای ضربشدن، هر بار مقدارِ ثابتی اضافه میشد، کلِ ماجرا O(n²) میشد.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.