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

آخر این فصل میتوانی:
- چهار شکلِ رایجِ
O(n²)ِ تصادفی را در کد بشناسی - قاعدهٔ تشخیص را روی کدِ خودت بهکار ببری
- بگویی چرا یکی از این چهارتا روی پایتونِ امروز خطی است و چرا نباید رویش حساب کرد
قبل از شروع#
از فصلِ ۴: هزینهٔ درج و حذف بر حسبِ محلش، و اینکه list جابهجا میکند.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | حدودِ یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. شکلِ اول: in روی یک list، داخلِ حلقه#
x in known یک عبارتِ کوتاه و بیآزار است. ولی اگر known یک list باشد، این عبارت از ابتدا تا آخرش میگردد. داخلِ یک حلقهٔ nتایی، همین میشود n بار گشتن.
🤔 اول حدس بزن: ستونِ نسبتِ این کد با دو برابر شدنِ
nچه عددی میدهد؟
rng = random.Random(SEED)
def count_shared(items, known):
hits = 0
for x in items:
if x in known: # این خط، خودش یک حلقه است
hits += 1
return hits
def counted_shared(items, known):
"""همان کار، با شمارندهٔ صریح بهجای in."""
ops = 0
for x in items:
for y in known:
ops += 1
if x == y:
break
return ops
LADDER = [250, 500, 1_000, 2_000]
pairs = {n: (rng.sample(range(4 * n), n), rng.sample(range(4 * n), n)) for n in LADDER}
print("— شمارشِ مقایسهها")
table([(n, counted_shared(*pairs[n])) for n in LADDER], "مقایسه", ",d")
— شمارشِ مقایسهها
n مقایسه نسبت به سطر قبل
250 55,553 —
500 218,729 3.94
1,000 873,254 3.99
2,000 3,514,059 4.02
4.00. شمارنده قطعی است و جای شک نمیگذارد.
🌱 ریشهاش کجاست: چرا دقیقاً چهار برابر؟ چون هر یک از
nعضوِitemsتاnخانهٔknownرا میبیند، وnبارnمیشودn². همین شکل در بخشهای ۲ و ۴ کمی فرق دارد: آنجا ظرف در هر دور یکی بزرگتر میشود، پس کلِ کار1 + 2 + … + nاست که با باز کردن و فاکتور گرفتن بهn(n+1)/2تبدیل میشود — یعنی نصفِn²بهعلاوهٔ نصفِn. باز کردن و فاکتور گرفتن در ریشه ترمِ ۳ فصل ۴ ساخته میشود. در هر دو حالت جملهٔn²غالب است و برای همین نسبت به4میرسد، نه به2.
راهِ حلش ظرفِ دیگری است که هزینهٔ پرسشِ «هست یا نه؟» را ثابت میکند. ساختش موضوعِ ترمِ ۳ است — این فصل فقط کارش این است که تشخیصش بدهی.
۲. شکلِ دوم: ساختنِ رشته با +=#
هر کتابی میگوید s += "x" در حلقه O(n²) است، چون رشته در پایتون تغییرناپذیر است و هر بار نسخهٔ تازهای ساخته میشود.
🤔 اول حدس بزن: بنویس ستونِ نسبتش را چه عددی انتظار داری:
2یا4؟
def grow_plain(n):
s = ""
for _ in range(n):
s += "x"
return s
def grow_with_shadow(n):
"""همان حلقه، فقط یک ارجاعِ دومِ زنده به رشته هم نگه میدارد."""
s = ""
shadow = s
for _ in range(n):
s += "x"
shadow = s
return s
TEXT = [20_000, 40_000, 80_000, 160_000]
print("جوابِ دو نسخه یکی است؟", grow_plain(2_000) == grow_with_shadow(2_000))
print("\n— s += 'x'")
table([(n, 1000 * clock(lambda k=n: grow_plain(k), repeat=2)) for n in TEXT],
"زمان (ms)", ",.2f")
print("\n— همان حلقه، با یک ارجاعِ دومِ زنده")
table([(n, 1000 * clock(lambda k=n: grow_with_shadow(k), repeat=2)) for n in TEXT],
"زمان (ms)", ",.2f")
جوابِ دو نسخه یکی است؟ True
— s += 'x'
n زمان (ms) نسبت به سطر قبل
20,000 1.96 —
40,000 3.95 2.01
80,000 8.17 2.07
160,000 15.49 1.90
— همان حلقه، با یک ارجاعِ دومِ زنده
n زمان (ms) نسبت به سطر قبل
20,000 7.81 —
40,000 26.85 3.44
80,000 82.95 3.09
160,000 332.86 4.01
جدولِ اول 2 میدهد، نه 4. کتابها اشتباه نمیگویند؛ فقط دربارهٔ پایتونِ امروز حرف نمیزنند.
پایتون یک میانبر دارد: اگر هیچکس دیگری به آن رشته ارجاع نداشته باشد، بهجای ساختنِ نسخهٔ تازه، همانجا بزرگش میکند. جدولِ دوم دقیقاً همین را ثابت میکند: یک متغیرِ اضافه که فقط نگاه میکند، ستونِ نسبت را از 2 به حدودِ 4 میبرد. هیچ چیزِ دیگری عوض نشد.
پس این میانبر یک تضمین نیست، یک شانس است — و شانسی که با یک خط کدِ کاملاً بیربط از دست میرود. اگر رشتهای را در حلقه میسازی، "".join(parts) را بهکار ببر: همیشه خطی است و به هیچ شرطی بند نیست.
۳. شکلِ سوم: del items[0] مکرر#
def drain_front(n):
items = list(range(n))
while items:
del items[0]
return len(items)
def drain_back(n):
items = list(range(n))
while items:
del items[-1]
return len(items)
DEL = [10_000, 20_000, 40_000, 80_000]
print("— del items[0]")
table([(n, 1000 * clock(lambda k=n: drain_front(k), repeat=2)) for n in DEL],
"زمان (ms)", ",.2f")
print("\n— del items[-1]")
table([(n, 1000 * clock(lambda k=n: drain_back(k), repeat=2)) for n in DEL],
"زمان (ms)", ",.2f")
— del items[0]
n زمان (ms) نسبت به سطر قبل
10,000 19.79 —
20,000 78.00 3.94
40,000 324.74 4.16
80,000 1,212.42 3.73
— del items[-1]
n زمان (ms) نسبت به سطر قبل
10,000 0.30 —
20,000 0.60 1.99
40,000 1.27 2.10
80,000 2.74 2.16
4 در برابرِ 2، دقیقاً مثلِ pop(0) در برابرِ pop() در فصلِ قبل. یک نویسه اختلاف — 0 یا -1 — و دو مرتبهٔ متفاوت.
۴. شکلِ چهارم: items = items + [x]#
این یکی موذیترینشان است، چون خیلی شبیهِ append بهنظر میرسد.
def grow_by_concat(n):
items = []
for i in range(n):
items = items + [i] # یک list تازه، هر بار
return items
def grow_by_append(n):
items = []
for i in range(n):
items.append(i) # همان list، هر بار
return items
CONCAT = [4_000, 8_000, 16_000, 32_000]
print("جوابِ دو نسخه یکی است؟", grow_by_concat(500) == grow_by_append(500))
print("\n— items = items + [x]")
table([(n, 1000 * clock(lambda k=n: grow_by_concat(k), repeat=2)) for n in CONCAT],
"زمان (ms)", ",.2f")
print("\n— items.append(x)")
table([(n, 1000 * clock(lambda k=n: grow_by_append(k), repeat=2)) for n in CONCAT],
"زمان (ms)", ",.2f")
جوابِ دو نسخه یکی است؟ True
— items = items + [x]
n زمان (ms) نسبت به سطر قبل
4,000 14.55 —
8,000 69.79 4.80
16,000 324.32 4.65
32,000 1,169.11 3.60
— items.append(x)
n زمان (ms) نسبت به سطر قبل
4,000 0.11 —
8,000 0.27 2.39
16,000 0.54 2.02
32,000 0.84 1.56
4 در برابرِ 2، با خروجیِ کاملاً یکسان. items + [i] یک list تازه میسازد و همهچیز را در آن کپی میکند؛ append همان ظرف را نگه میدارد.
⚠️ مواظب باش:
items += [x]— با علامتِ مساوی — رفتارِappendرا دارد نه رفتارِ+. سه شکلِ نوشتاریِ نزدیک به هم، دو مرتبهٔ متفاوت. اینجا هم مثلِ شکلِ دوم، تفاوت در این است که ظرف همان یکی میماند یا دوباره ساخته میشود.
۵. قاعدهٔ تشخیص#
هر چهار شکل یک ساختارِ مشترک دارند و این ساختار را میشود در یک جمله نوشت:
یک عملِ
O(n)داخلِ یک حلقهٔnتایی.
و برای بهکار بردنش لازم نیست کدِ کسی را بخوانی؛ فقط باید بدانی کدام عملها O(n) هستند. تا اینجای دوره فهرستشان این است — و ستونِ آخر میگوید هر سطر کجا اندازه گرفته شد، چون سطری که اندازه گرفته نشده با سطری که شده یکی نیست:
| عمل | مرتبه | چرا | کجا اندازه گرفته شد |
|---|---|---|---|
x in values روی list |
O(n) |
از ابتدا میگردد | همین فصل، بخشِ ۱ |
values.index(x) |
O(n) |
همان | ت۲ف۱ بخشِ ۳ |
values.insert(0, x) · values.pop(0) |
O(n) |
همه را جابهجا میکند | ت۲ف۴ بخشهای ۱ تا ۳ |
del values[0] |
O(n) |
همان | همین فصل، بخشِ ۳ |
a + b روی list یا رشته |
O(n) |
ظرفِ تازه میسازد و کپی میکند | همین فصل، بخشهای ۲ و ۴ |
list(values) · values[:] |
O(n) |
کپیِ کامل | ت۲ف۲ بخشِ ۴ (فقط list(values)) |
values.append(x) |
O(1) amortised |
فقط انتها | ت۲ف۳ بخشِ ۵ |
values.pop() · del values[-1] |
O(1) |
فقط انتها | ت۲ف۴ بخشِ ۳ · همین فصل، بخشِ ۳ |
values[i] |
O(1) |
آدرس را حساب میکند | ت۲ف۱ بخشِ ۱ |
len(values) |
O(1) |
طول را جدا نگه میدارد | نسنجیده |
یک سطر «نسنجیده» علامت خورده و این عمدی است. len(values) جوابش بدیهی بهنظر میرسد — و این دوره اندازهاش نگرفته. values[:] هم همینطور: فقط list(values) سنجیده شد. مخصوصاً len: اینکه پایتون طول را جدا نگه میدارد بهجای اینکه هر بار بشمارد، یک جزئیاتِ پیادهسازی است، نه یک قانون. در جدولِ خودت هم همین کار را بکن؛ خانهٔ نقلشده را با خانهٔ اندازهگیریشده یک شکل ننویس. (ترمِ ۶ فصلِ ۲ کلِ یک بخش را به همین میدهد.)
و بازهٔ n هم بخشی از این جدول است: سطرهای اندازهگیریشده در بازهای بینِ حدودِ ۲۵۰ و ۱۶۰٬۰۰۰ عضو گرفته شدهاند. زیرِ چند ده عضو هیچکدام از این مرتبهها دیده نمیشوند — همان درسِ ترمِ ۱ فصلِ ۵.
و مهمترین نکتهٔ این جدول ستونِ مرتبه نیست، ستونِ اول است: شش سطرِ اول همه یک خط کدِ کوتاهاند. هیچکدامشان شبیهِ حلقه نیستند.
✅ چک کن:
count_sharedرا طوری تغییر بده کهknownرا قبل از حلقه به یکsetتبدیل کند و جدولِ زمانش را بگیر. ستونِ نسبت باید از4به حدودِ2بیفتد. فعلاً همینقدر بدان کهsetپرسشِ عضویت را ارزان میکند؛ ترمِ ۳ نشان میدهد چطور، و هزینهٔ پنهانش چیست.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ چهار الگوی
O(n²)، هرکدام با نسخهٔ خطیِ متناظرش که خروجیِ یکسان میدهد. در کدام بازهٔn؟ هر شکل در بازهٔ خودش — از ۲۵۰ تا ۲٬۰۰۰ برای شمارش، و از ۴٬۰۰۰ تا ۱۶۰٬۰۰۰ برای زمان، چون بازه را طوری انتخاب کردیم که هر جدول در حدودِ یک ثانیه تمام شود. با چند تکرار، و کمینه یا میانگین؟ دو تکرار بهعلاوهٔ گرمکننده، کمینه، و هر اجرا ورودیِ تازهٔ خودش را میسازد.
🔧 اگر کار نکرد: موقعِ درست کردنِ شکلِ چهارم، رایجترین اشتباه این است که
+را نگه داری و فقط براکت را برداری:
try:
items = [1, 2, 3]
items = items + 4
except TypeError as err:
print(f"{type(err).__name__}: {err}")
TypeError: can only concatenate list (not "int") to list
پیام صریح است: + روی list فقط list قبول میکند. و همین سختگیری یادآورِ همان چیزی است که گران بود — items + [4] یک ظرفِ سوم میسازد. اگر یک عضو میخواهی اضافه کنی، append کارِ درست است.
🤖 از دستیارت بپرس: «چه عملیاتی در پایتون
O(n)هستند ولی شبیهِ یک عملِ ساده بهنظر میرسند؟» بعد این را هم بپرس: «چراs += "x"در حلقه گاهی خطی است و گاهی درجهدو؟» — جوابِ درست به تعدادِ ارجاعهای زندهٔ آن رشته برمیگردد، و اگر دستیارت فقط گفت «همیشه درجهدو است»، جدولِ بخشِ ۲ را جلویش بگذار.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| accidental quadratic | اکسیدنتال کوادراتیک | کدی که بدونِ حلقهٔ تودرتوی آشکار، O(n²) است |
| hidden loop | هیدن لوپ | عملی که در یک خط نوشته میشود ولی داخلش روی کلِ داده میگردد |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
هر بار که هزینهٔ جابهجایی را دیدیم، یک فکر پیش آمده: اگر ظرفی داشتیم که خانههایش لازم نبود کنارِ هم باشند، هیچکدام از این جابهجاییها لازم نمیشد.
فصلِ بعد آن ظرف را میسازد — linked list — و روی همان کاری که قرار است در آن برنده باشد اندازهاش میگیرد. نتیجه منفی است، و ما همانقدر پررنگ گزارشش میکنیم که یک نتیجهٔ مثبت را: در یک آزمایش، list بیش از چهل برابر سریعتر درمیآید. دلیلش هم Big-O نیست.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.