در این فصل چه یاد میگیری#
فصلِ قبل با یک تناقض تمام شد: بعضی از appendها یک کپیِ کاملِ O(n) هستند، پس چرا ساختنِ یک list بزرگ با append سریع است؟
این فصل جوابش را با سه اندازهگیری میدهد. اول تکتکِ چهارصد هزار append را جدا میسنجیم و گرانترینهایشان را پیدا میکنیم — که هزاران برابر بقیهاند و همه دقیقاً روی لحظههای بزرگشدن افتادهاند. بعد نشان میدهیم میانگینِ همانها صاف است. و آخر میبینیم که اگر ظرفیت بهجای ضربشدن هر بار مقدارِ ثابتی اضافه میشد، کلِ ماجرا O(n²) میشد.
بینِ راه یک انتظارِ کتابِ درسی هم میشکند: ظرفیتِ list پایتون دو برابر نمیشود. ضریبش را اندازه میگیریم.

آخر این فصل میتوانی:
- بگویی «هزینهٔ
amortised» چه چیزی را ادعا میکند و چه چیزی را ادعا نمیکند - گرانترین تکِ عملیات را از میانگینِ بلندمدتش جدا کنی و هر دو را گزارش کنی
- نشان بدهی چرا رشدِ ضربیِ ظرفیت لازم است و رشدِ ثابت فاجعه است
قبل از شروع#
از فصلِ ۲: ظرفیت در برابرِ طول، تابعِ capacity، و اینکه هر بزرگشدن یک کپیِ کامل است.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | حدودِ یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. ظرفیت واقعاً چند برابر میشود؟#
فصلِ قبل از روی «شش پله برای هر دو برابر شدن» حدس زد که ضریبِ رشد حدودِ 1.12 است. حالا مستقیم اندازهاش میگیریم.
🤔 اول حدس بزن: بیشترِ کتابها میگویند آرایهٔ پویا ظرفیتش را دو برابر میکند. بنویس انتظار داری ستونِ «نسبت به قبلی» در این جدول چه عددی بدهد.
CELL = 8
EMPTY = sys.getsizeof([])
def capacity(values):
return (sys.getsizeof(values) - EMPTY) // CELL
steps = []
values = []
cap = 0
for i in range(20_000):
values.append(i)
new = capacity(values)
if new != cap:
steps.append(new)
cap = new
print(f"{'ظرفیت':>10}{'نسبت به قبلی':>16}")
for a, b in zip([None] + steps[:-1], steps):
print(f"{b:>10}" + (f"{'—':>16}" if a is None else f"{b / a:>16.3f}"))
print(f"\nتعدادِ پلهها تا بیست هزار: {len(steps)}")
ظرفیت نسبت به قبلی
4 —
8 2.000
16 2.000
24 1.500
32 1.333
40 1.250
52 1.300
64 1.231
76 1.188
92 1.211
108 1.174
128 1.185
148 1.156
172 1.162
200 1.163
232 1.160
268 1.155
308 1.149
352 1.143
400 1.136
456 1.140
520 1.140
592 1.138
672 1.135
760 1.131
860 1.132
972 1.130
1100 1.132
1244 1.131
1404 1.129
1584 1.128
1788 1.129
2016 1.128
2272 1.127
2560 1.127
2884 1.127
3248 1.126
3660 1.127
4124 1.127
4644 1.126
5228 1.126
5888 1.126
6628 1.126
7460 1.126
8396 1.125
9452 1.126
10640 1.126
11976 1.126
13480 1.126
15172 1.126
17072 1.125
19212 1.125
21620 1.125
تعدادِ پلهها تا بیست هزار: 53
ضریب از 2.000 شروع میکند و به 1.125 میرسد و همانجا میماند.
پس آن جملهٔ کتابِ درسی — «ظرفیت دو برابر میشود» — برای این پیادهسازی غلط است. فقط دو پلهٔ اولش دو برابر است و بقیه یکهشتم اضافه میکنند.
و این دقیقاً همان لحظهای است که این دوره برایش ساخته شده: یک جملهٔ درستبهنظر، یک اندازهگیریِ پنجخطی، و یک عددِ متفاوت. جمله را نپذیر؛ عدد را بگیر.
ولی حالا سؤالِ مهمتر: آیا 1.125 هم مثلِ 2 کافی است؟ جوابش را بخشِ ۴ میدهد و جواب مثبت است — چیزی که اهمیت دارد ضربی بودن است، نه خودِ عددِ دو.
۲. تکتکِ appendها#
حالا سراغِ چیزی میرویم که تا اینجا هیچوقت نکردهایم: بهجای زمانِ کلِ حلقه، زمانِ تکتکِ عملیات را میگیریم.
🤔 اول حدس بزن: چهارصد هزار
appendمیزنیم و هر کدام را جدا میسنجیم. بنویس گرانترینشان نسبت به میانه چند برابر میشود: ده؟ صد؟ بیشتر؟
N = 400_000
now = time.perf_counter
values = []
per_op = []
for i in range(N):
start = now()
values.append(i)
per_op.append(now() - start)
ordered = sorted(per_op)
print(f"میانهٔ هر append : {1e6 * ordered[N // 2]:>10.4f} µs")
print(f"گرانترین append : {1e6 * ordered[-1]:>10.4f} µs")
print(f"نسبتِ گرانترین به میانه: {ordered[-1] / max(ordered[N // 2], 1e-9):>10,.0f} برابر")
print(f"مجموعِ همه : {1000 * sum(per_op):>10.1f} ms")
میانهٔ هر append : 0.1000 µs
گرانترین append : 590.9000 µs
نسبتِ گرانترین به میانه: 5,909 برابر
مجموعِ همه : 57.0 ms
گرانترین append هزاران برابرِ میانه است. پس «append ارزان است» بهعنوانِ یک جملهٔ سرراست غلط است.
میانه آنقدر کوچک است که به حدِ تفکیکِ ساعت میخورد — همان چیزی که فصلِ ۲ ترمِ ۱ دربارهاش هشدار داد. برای همین این عدد را بهعنوان یک اندازهگیریِ دقیق نمیخوانیم؛ فقط میگوییم «زیرِ حدِ تفکیک». چیزی که واقعاً میخواهیم بدانیم این است که گرانها کجا افتادهاند.
۳. گرانها کجا افتادهاند؟#
اگر توضیحِ فصلِ ۲ درست باشد، گرانترین appendها باید دقیقاً روی اندیسهایی باشند که ظرفیت در آنها عوض شده. این یک پیشبینیِ آزمونپذیر است.
یک نکتهٔ نحوی در کدِ زیر که فعلاً فقط باید بشناسیاش: sorted(..., key=...) یعنی «مرتب کن، ولی نه بر اساسِ خودِ عضوها — بر اساسِ چیزی که این تابع از هر عضو درمیآورد». اینجا عضوها اندیساند و کلیدِ مرتبسازی -per_op[i] است، یعنی زمانِ هر عمل با علامتِ منفی، تا کندترینها اول بیایند. ترمِ ۴ فصلِ ۸ کاملاً بازش میکند؛ تا آنجا هر بار که ببینیاش همین یک جمله کافی است.
grown_at = []
probe = []
cap = 0
for i in range(N):
probe.append(i)
new = capacity(probe)
if new != cap:
grown_at.append(i)
cap = new
grown = set(grown_at)
slowest = sorted(range(N), key=lambda i: -per_op[i])[:12]
total = sum(per_op)
on_growth = sum(per_op[i] for i in grown_at)
print("تعدادِ کلِ بزرگشدنها در این مسیر:", len(grown_at))
print("کندترین دوازده append روی این اندیسها افتادند:")
print(" ", sorted(slowest))
print("چند تایشان دقیقاً روی یک بزرگشدن بود؟",
sum(1 for i in slowest if i in grown), "از ۱۲")
print(f"\nسهمِ این {len(grown_at)} عمل از تعدادِ کلِ عملیات: "
f"{100 * len(grown_at) / N:.3f} درصد")
print(f"سهمِ همانها از کلِ زمان : {100 * on_growth / total:.1f} درصد")
del probe, per_op
تعدادِ کلِ بزرگشدنها در این مسیر: 78
کندترین دوازده append روی این اندیسها افتادند:
[88988, 112636, 126720, 142564, 160388, 180440, 203000, 228380, 256932, 289052, 325188, 365840]
چند تایشان دقیقاً روی یک بزرگشدن بود؟ 12 از ۱۲
سهمِ این 78 عمل از تعدادِ کلِ عملیات: 0.019 درصد
سهمِ همانها از کلِ زمان : 8.9 درصد
تقریباً همهشان. گاهی هر دوازدهتا و گاهی یازدهتا — آن یکی معمولاً لحظهای است که سیستمعامل وسطِ کار پرید، همان نویزِ فصلِ ۳ ترمِ ۱. پیشبینی درست درآمد و توضیحِ فصلِ ۲ تأیید شد.
ولی دو سطرِ آخر مهمترند، چون به نویز بند نیستند: آن هفتاد و هشت عمل صدمِ درصدِ کلِ عملیاتاند و چند درصدِ کلِ زمان را میخورند. یعنی چند صد برابرِ سهمِ عادلانهشان.
و به فاصلهٔ اندیسها نگاه کن: هرچه جلوتر میرویم، بزرگشدنها دیرتر به دیرتر اتفاق میافتند — چون ظرفیت ضربی رشد میکند و هر بار جای بیشتری باز میشود.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ اندیسِ دوازده کندترین
appendبا فهرستِ اندیسهایی که ظرفیت در آنها عوض شد — دو اندازهگیریِ کاملاً مستقل روی همان دنبالهٔ عملیات. در کدام بازهٔn؟ یک مسیرِ چهارصد هزارتایی، از صفر تاn. با چند تکرار، و کمینه یا میانگین؟ یک اجرا و بدونِ خلاصه — چون سؤال دربارهٔ جای گرانها است نه اندازهشان، و جایشان قطعی است.
۴. پس چرا کلِ ساختن ارزان است؟#
append گاهی O(n) است. ولی آن «گاهی» چقدر است؟ جوابش را میشود بدونِ ساعت شمرد: مدلی میسازیم که فقط تعدادِ عنصرهای جابهجاشده را میشمارد.
🤔 اول حدس بزن: برای دو حالت حدس بزن — ظرفیتی که هر بار دو برابر میشود و ظرفیتی که هر بار صد و بیست و هشت خانه اضافه میکند. ستونِ نسبتِ هر کدام چه عددی میدهد؟
def copied_multiplicative(n, factor=2):
"""ظرفیت هر بار در factor ضرب میشود."""
cap, copied = 0, 0
for size in range(1, n + 1):
if size > cap:
copied += size - 1 # همهٔ عناصرِ قبلی منتقل میشوند
cap = max(cap + 1, int(cap * factor))
return copied
def copied_constant(n, step=128):
"""ظرفیت هر بار step خانه اضافه میکند."""
cap, copied = 0, 0
for size in range(1, n + 1):
if size > cap:
copied += size - 1
cap += step
return copied
LADDER = [10_000, 20_000, 40_000, 80_000]
print("— ظرفیت هر بار دو برابر میشود")
table([(n, copied_multiplicative(n)) for n in LADDER], "عنصرِ منتقلشده", ",d")
print("\n— ظرفیت هر بار ۱۲۸ خانه اضافه میکند")
table([(n, copied_constant(n)) for n in LADDER], "عنصرِ منتقلشده", ",d")
print("\n— ظرفیت هر بار در ۱٫۱۲۵ ضرب میشود (کارِ خودِ پایتون)")
table([(n, copied_multiplicative(n, 1.125)) for n in LADDER], "عنصرِ منتقلشده", ",d")
— ظرفیت هر بار دو برابر میشود
n عنصرِ منتقلشده نسبت به سطر قبل
10,000 16,383 —
20,000 32,767 2.00
40,000 65,535 2.00
80,000 131,071 2.00
— ظرفیت هر بار ۱۲۸ خانه اضافه میکند
n عنصرِ منتقلشده نسبت به سطر قبل
10,000 394,368 —
20,000 1,567,488 3.97
40,000 6,249,984 3.99
80,000 24,960,000 3.99
— ظرفیت هر بار در ۱٫۱۲۵ ضرب میشود (کارِ خودِ پایتون)
n عنصرِ منتقلشده نسبت به سطر قبل
10,000 88,035 —
20,000 178,286 2.03
40,000 321,112 1.80
80,000 650,744 2.03
سه جدول، دو دنیای متفاوت.
- رشدِ ضربی — چه با ضریبِ
2و چه با1.125— ستونِ نسبتِ2.00میدهد. یعنی کلِ کارِ انتقال رویnبارappend، خودشO(n)است. تقسیمش برnمیشود یک عددِ ثابت. - رشدِ ثابت ستونِ نسبتِ
4.00میدهد:O(n²). برای هشتاد هزار عضو نزدیکِ بیست و پنج میلیون عنصر جابهجا میشود، در حالی که نسخهٔ ضربی با ضریبِ2حدودِ صد و سی هزارتا و با ضریبِ واقعیِ پایتون حدودِ ششصد و پنجاه هزارتا — یعنی در بدترین حالت هم نزدیکِ چهل برابر کمتر.
و همینجا کلِ حرفِ فصل است: هزینهٔ amortised یعنی هزینهٔ کلِ یک دنبالهٔ عملیات، تقسیم بر تعدادشان. برای append این عدد ثابت است، پس میگوییم «append هزینهٔ O(1)ِ amortised دارد».
و دقت کن این جمله چه چیزی را ادعا نمیکند: ادعا نمیکند هیچ appendی گران نیست. بخشِ ۲ خلافش را نشان داد. ادعا میکند گرانها آنقدر کماند که وقتی خرجشان بینِ همه پخش شود، سهمِ هرکس ثابت میماند.
🌱 ریشهاش کجاست: چرا مجموعِ انتقالها
O(n)درمیآید؟ چون اگر ظرفیت دو برابر شود، انتقالها1 + 2 + 4 + … + nمیشوند و مجموعِ توانهای دو همیشه کمتر از دو برابرِ آخرینشان است. توان و دو برابر کردنِ پیاپی در ریشه ترمِ ۱ فصل ۸ ساخته میشود.
و برای هر ضریبِ دیگری هم میشود همین را نوشت. آخرین انتقال حدودِ n عضو جابهجا میکند، انتقالِ قبلیاش n ÷ f، آن یکی n ÷ f²، و همینطور. جمعِ این دنباله دو کران دارد که هر دو ضریبی ثابت از n هستند:
n ÷ (f - 1) ≤ مجموعِ کلِ انتقالها ≤ n × f ÷ (f - 1)
دو کران لازم است، نه یک فرمولِ دقیق — چون عددِ واقعی به این بستگی دارد که n کجای فاصلهٔ بینِ دو بزرگشدنِ متوالی افتاده باشد. بیایید هر دو کران را با شمارنده وارسی کنیم:
print(f"{'ضریب':>8}{'شمردهٔ واقعی':>20}{'n ÷ (f-1)':>16}{'n × f ÷ (f-1)':>18}")
for f in (2, 1.125, 1.05):
got = copied_multiplicative(80_000, f)
print(f"{f:>8}{got:>20,}{80_000 / (f - 1):>16,.0f}{80_000 * f / (f - 1):>18,.0f}")
ضریب شمردهٔ واقعی n ÷ (f-1) n × f ÷ (f-1)
2 131,071 80,000 160,000
1.125 650,744 640,000 720,000
1.05 1,621,558 1,600,000 1,680,000
هر سه عددِ شمردهشده داخلِ کرانِ خودشاناند، و مهمترین ستون ستونِ سوم است. f = 2 میدهد n، f = 1.125 میدهد هشت برابرِ n، و f = 1.05 بیست برابرِ n. هر سه ضریبِ ثابتاند و ثابت یعنی O(n) — ولی ثابتشان بیست برابر با هم فرق دارد، و همین دلیلِ اینکه هیچ پیادهسازیای ضریبِ رشد را 1.05 نمیگذارد.
✅ چک کن: قبل از هر اجرایی، از همان کران
n ÷ (f - 1)پیشبینی کن کهcopied_multiplicative(80_000, 1.05)چند درمیآید، بعد اجرایش کن و خطای پیشبینیات را بنویس. حالا جدولِ چهار اندازهایِ همان ضریب را بگیر: عدد باید حدودِ دوازده برابرِ ضریبِ2باشد ولی ستونِ نسبت هنوز2.00بماند. اگر ستونِ نسبت به4رفت،factorرا زیرِ یک گذاشتهای و ظرفیت اصلاً بزرگ نمیشود.
۵. زمانِ واقعی، برای همان ادعا#
شمارش میگوید کلِ ساختن O(n) است. ساعت هم باید همین را بگوید.
def build(n):
out = []
for i in range(n):
out.append(i)
return out
BUILD = [200_000, 400_000, 800_000, 1_600_000]
table([(n, 1000 * clock(lambda k=n: build(k), repeat=3)) for n in BUILD])
print("\nهر append بهطورِ متوسط:",
f"{1e9 * clock(lambda: build(1_600_000), repeat=3) / 1_600_000:.1f} نانوثانیه")
n زمان (ms) نسبت به سطر قبل
200,000 7.3 —
400,000 16.5 2.27
800,000 39.7 2.40
1,600,000 75.1 1.89
هر append بهطورِ متوسط: 46.3 نانوثانیه
ستونِ نسبت نزدیکِ 2 است. ساعت و شمارنده یک چیز میگویند: n بار append روی هم O(n) است.
🔧 اگر کار نکرد: اگر خواستی همین اندازهگیری را روی یک
listکه از قبل ساخته شده انجام بدهی، تلهٔ فصلِ ۳ ترمِ ۱ برمیگردد — اندازهگیریِ گرم. اینجا شکلِ دیگری دارد:
shared = []
warm = 1000 * clock(lambda: shared.append(1), repeat=5)
print(f"زمانِ یک append روی ظرفِ مشترک: {warm:.6f} ms")
print(f"طولِ ظرف بعد از اندازهگیری : {len(shared):,}")
زمانِ یک append روی ظرفِ مشترک: 0.000100 ms
طولِ ظرف بعد از اندازهگیری : 6
عددِ زمان بیمعناست و سطرِ دوم دلیلش را لو میدهد: clock شش بار تابع را صدا زد و هر بار یک عضو اضافه شد، پس اندازهگیری روی شش ظرفِ متفاوت انجام شده. هر اندازهگیری باید ظرفِ تازهٔ خودش را داشته باشد — همان قاعدهٔ «ورودیِ دستنخورده».
🤖 از دستیارت بپرس: «تفاوتِ هزینهٔ
amortisedو هزینهٔ بدترین حالت چیست؟» بعد این را هم بپرس: «در چه نوع برنامهای هزینهٔamortisedجوابِ درست نیست و باید بدترین تکعملیات را گزارش کرد؟» — یکی از جوابهای درست برنامهای است که باید در یک مهلتِ ثابت جواب بدهد؛ آنجا یکappendهزار برابری همان چیزی است که مهلت را میشکند، هرچقدر هم که میانگین خوب باشد.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| amortised cost | اِمورتایزد کاست | هزینهٔ کلِ یک دنبالهٔ عملیات، تقسیم بر تعدادشان |
| worst-case cost | ورستکیس کاست | گرانترین تکِ عملیاتِ ممکن |
| growth factor | گروث فکتور | عددی که ظرفیت هر بار در آن ضرب میشود |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
سه فصل است داریم دربارهٔ انتهای ظرف حرف میزنیم: append در انتها، بزرگشدن در انتها، خانهٔ خالی در انتها.
فصلِ بعد به ابتدای ظرف نگاه میکند و همهچیز عوض میشود. یک جدولِ دوبرابری برای append میگیریم و یکی برای insert(0, x): ستونِ اولی نزدیکِ 2 است و دومی نزدیکِ 4. بعد ظرفِ دیگری معرفی میشود که همان کارِ ابتدای ظرف را دوباره صاف میکند — و آن هم با جدول اثبات میشود، نه با ادعا.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.