در این فصل چه یاد میگیری#
هیچ مفهومِ تازهای. این فصل همهٔ نُه فصلِ قبل را یکجا بهکار میبرد.
چهار تابع به تو داده میشود که هیچ توضیحی ندارند. کارت این است که برای هرکدام مرتبه را اعلام کنی — با جدول، با پیشبینی، و با خطای گزارششده. یکی از آن چهارتا عمداً تله دارد: روی نردبانِ ۱۰۰ تا ۸۰۰ ستونِ نسبتش 1.00 است و روی نردبانِ ۵۰٬۰۰۰ تا ۴۰۰٬۰۰۰ میشود 1.91. همان یک تابع، همان شمارنده.
آخر این فصل میتوانی:
- کلِ پروتکلِ دوره را بیکمک روی یک کدِ ناشناس اجرا کنی
- مرتبهای اعلام کنی که کسِ دیگری بتواند بازتولید و ردش کند
- بگویی گزارشِ تو دقیقاً چه چیزهایی باید داشته باشد تا قابلِ رد کردن باشد
قبل از شروع#
از فصلِ ۸: پروتکلِ چهارقدمی — جدول، اعلامِ شکل، معیارِ پذیرش، پیشبینی و خطا. از فصلِ ۵: اینکه اندازههای کوچک دروغ میگویند. از فصلِ ۹: اینکه بازهٔ n بخشی از صورتِ مسئله است.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. صورتِ پروژه#
یک «اعلامِ مرتبه» که این پنج چیز را نداشته باشد، قابلِ قبول نیست:
- بازهٔ
nی که اندازهگیری در آن انجام شده. بدونِ آن، اعلام هیچ معنایی ندارد. - جدولِ دوبرابری با ستونِ نسبت، دستِکم چهار اندازه.
- مرتبهٔ اعلامشده، همراه با اینکه از کدام ستون و کدام عدد به آن رسیدهای.
- پیشبینیِ اندازهٔ بعدی و معیارِ پذیرشی که قبل از اجرا نوشته شده.
- خطای نسبیِ اندازهگیریشده، و حکمِ «قبول» یا «رد».
پنجمی مهمترینشان است: گزارشی که فقط نتیجههای موفق را مینویسد، گزارش نیست.
۲. چهار جعبهٔ دربسته#
🤔 اول حدس بزن: کدها را بخوان و قبل از دیدنِ جدول برای هر چهارتا یک مرتبه حدس بزن و روی کاغذ بنویس. بعد جدول را ببین. هر جا حدست غلط بود، آن مورد ارزشِ آموزشیِ بیشتری از سه تای دیگر دارد.
def mystery_a(values):
ops, n, step = 0, len(values), 1
while step < n:
for _ in range(n):
ops += 1
step *= 2
return ops
def mystery_b(values):
ops, n, i = 0, len(values), 0
while i < n:
ops += 1
i += i // 2 + 1
return ops
def mystery_c(values):
ops, n = 0, len(values)
for i in range(n):
for j in range(0, n, 64):
ops += 1
return ops
def mystery_d(values):
ops, n = 0, len(values)
for _ in range(n):
ops += 1
for _ in range(20_000):
ops += 1
return ops
MYSTERIES = [("mystery_a", mystery_a), ("mystery_b", mystery_b),
("mystery_c", mystery_c), ("mystery_d", mystery_d)]
LADDER = SIZES
data = {n: list(range(n)) for n in LADDER}
for name, fn in MYSTERIES:
print(f"— {name}")
table([(n, fn(data[n])) for n in LADDER], "عملیات", ",d")
print()
— mystery_a
n عملیات نسبت به سطر قبل
1,000 10,000 —
2,000 22,000 2.20
4,000 48,000 2.18
8,000 104,000 2.17
— mystery_b
n عملیات نسبت به سطر قبل
1,000 16 —
2,000 18 1.12
4,000 20 1.11
8,000 21 1.05
— mystery_c
n عملیات نسبت به سطر قبل
1,000 16,000 —
2,000 64,000 4.00
4,000 252,000 3.94
8,000 1,000,000 3.97
— mystery_d
n عملیات نسبت به سطر قبل
1,000 21,000 —
2,000 22,000 1.05
4,000 24,000 1.09
8,000 28,000 1.17
به mystery_c دقت کن، چون آموزندهترینِ این چهارتاست: آن 64 در range(0, n, 64) باعث میشود عددهایش کوچک بمانند — در n = 1000 فقط شانزده هزار عمل. ولی ستونِ نسبتش 4 است. عددِ کوچک و مرتبهٔ بزرگ، دو چیزِ متفاوتاند: در n = 100,000 همان تابع صد و پنجاه میلیون عمل میکند.
۳. یک نمونهٔ کاملِ حلشده#
mystery_a را کامل حل میکنیم تا شکلِ گزارش دستت بیاید. ستونِ نسبتش 2.20، 2.18، 2.17 است: کمی بالای دو و آرامآرام پایینرونده — دقیقاً امضای O(n log n).
import math
TOLERANCE = 25.0 # معیارِ پذیرش، پیش از اجرا نوشته شد
def shape_n_log_n(n):
return n * math.log2(n)
measured = {n: mystery_a(data[n]) for n in LADDER}
print(f"{'n':>10}{'عملیات ÷ (n log n)':>24}")
for n in LADDER:
print(f"{n:>10,}{measured[n] / shape_n_log_n(n):>24.5f}")
LAST = LADDER[-1]
NEXT = 2 * LAST
c = measured[LAST] / shape_n_log_n(LAST)
predicted = c * shape_n_log_n(NEXT)
print(f"\nمرتبهٔ اعلامشده : O(n log n)")
print(f"ثابتِ برازش : c = {c:.5f}")
print(f"معیارِ پذیرش : خطای کمتر از {TOLERANCE:.0f} درصد")
print(f"پیشبینی n = {NEXT:,}: {predicted:,.0f} عملیات")
actual = mystery_a(list(range(NEXT)))
error = 100 * abs(predicted - actual) / actual
print(f"اندازهگیریِ واقعی : {actual:,} عملیات")
print(f"خطای نسبی : {error:.2f} درصد →",
"قبول" if error < TOLERANCE else "رد")
n عملیات ÷ (n log n)
1,000 1.00343
2,000 1.00312
4,000 1.00286
8,000 1.00264
مرتبهٔ اعلامشده : O(n log n)
ثابتِ برازش : c = 1.00264
معیارِ پذیرش : خطای کمتر از 25 درصد
پیشبینی n = 16,000: 224,042 عملیات
اندازهگیریِ واقعی : 224,000 عملیات
خطای نسبی : 0.02 درصد → قبول
ستونِ عملیات ÷ (n log n) چهار بار تقریباً 1.003 داد — یعنی شکل درست انتخاب شده — و خطای پیشبینی دو صدمِ درصد شد.
✅ چک کن: همین برازش را با شکلِ
n²تکرار کن. ستونِ نسبتِ برازش باید بهجای ثابت ماندن، در هر سطر نصف شود. آن نصف شدن دقیقاً همان چیزی است که میگوید شکل غلط است — و هیچ خطایی هم نمیدهد، پس باید خودت نگاهش کنی.
۴. تلهٔ mystery_d#
جدولِ بخشِ ۲ برای mystery_d نسبتِ 1.05 و 1.09 و 1.17 داد. وسوسهکننده است که بنویسی O(1). دو نردبانِ دیگر را ببین:
🤔 اول حدس بزن: کدِ
mystery_dرا دوباره بخوان و برای هر دو نردبان یک عدد در ستونِ نسبت بنویس — یکی ۱۰۰ تا ۸۰۰ و یکی ۵۰٬۰۰۰ تا ۴۰۰٬۰۰۰. اگر حدست برای هر دو یک عدد است، همان حدس چیزی است که این بخش میخواهد بشکند.
print("— mystery_d روی نردبانِ کوچک")
table([(n, mystery_d(list(range(n)))) for n in (100, 200, 400, 800)], "عملیات", ",d")
print("\n— mystery_d روی نردبانِ بزرگ")
table([(n, mystery_d(list(range(n)))) for n in (50_000, 100_000, 200_000, 400_000)],
"عملیات", ",d")
— mystery_d روی نردبانِ کوچک
n عملیات نسبت به سطر قبل
100 20,100 —
200 20,200 1.00
400 20,400 1.01
800 20,800 1.02
— mystery_d روی نردبانِ بزرگ
n عملیات نسبت به سطر قبل
50,000 70,000 —
100,000 120,000 1.71
200,000 220,000 1.83
400,000 420,000 1.91
1.00 در یک نردبان و 1.91 در نردبانِ دیگر. همان تابع، همان شمارنده، بدونِ ذرهای نویز.
آن 20_000 عملِ ثابت تا وقتی n کوچک است کلِ کار است و مرتبهٔ واقعی را کاملاً پنهان میکند. این همان درسِ فصلِ ۵ است، این بار بهشکلِ یک تلهٔ واقعی در یک پروژه.
پس گزارشِ درست برای mystery_d این است: «در بازهٔ ۱۰۰ تا ۸۰۰ رفتار عملاً ثابت است؛ از حدودِ ۵۰٬۰۰۰ به بعد O(n) است.» دو جمله، دو بازه — و هیچکدام بدونِ دیگری کامل نیست.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ چهار تابعِ ناشناس با شکلهای رشدِ استاندارد، از راهِ ستونِ نسبت. در کدام بازهٔ
n؟ ۱٬۰۰۰ تا ۸٬۰۰۰ برای هر چهار تابع، بهعلاوهٔ دو بازهٔ اضافه برایmystery_d(۱۰۰ تا ۸۰۰ و ۵۰٬۰۰۰ تا ۴۰۰٬۰۰۰). با چند تکرار، و کمینه یا میانگین؟ شمارش است، پس یک اجرا و بدونِ خلاصه — و به همین دلیل هر عددِ این فصل روی ماشینِ تو هم دقیقاً همین است.
🔧 اگر کار نکرد: اگر نردبانت را از صفر یا یک شروع کنی، برازشِ
n log nمیشکند:
try:
print(shape_n_log_n(0))
except ValueError as err:
print(f"{type(err).__name__}: {err}")
ValueError: math domain error
math.log2 برای صفر تعریف نشده است و برای n = 1 جوابش صفر میشود، که تقسیم را میشکند. نردبانِ برازش همیشه از عددی شروع میشود که به nِ واقعیِ تو نزدیک باشد، نه از کوچکترین عددِ ممکن.
🤖 از دستیارت بپرس: «چطور از روی ستونِ نسبت تشخیص بدهم بینِ
O(n)وO(n log n)؟» بعد این را هم بپرس: «اگر ستونِ نسبتِ من ۲٫۲ باشد و با بزرگتر شدنِnپایین بیاید، این به نفعِ کدامشان است؟» — جوابِ درستO(n log n)است و دلیلش این است کهlog nبا بزرگ شدنِnکندتر رشد میکند، پس سهمش از نسبت کم میشود.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| order declaration | اُردر دکلریشن | اعلامِ مستندِ مرتبهٔ یک کد، همراه با بازه و خطا |
| reproducible report | ریپرودیوسبل ریپورت | گزارشی که کسِ دیگری میتواند دوباره بسازد و ردش کند |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
ترمِ یک تمام شد و کلِ روشِ دوره را داری: ساعتِ صادق، شمارندهٔ قطعی، جدولِ دوبرابری، شش منحنی، Big-O بهعنوان پیشبینی، پروتکلِ برازش و پیشبینی، و نقطهٔ تقاطع. هر پنج ترمِ بعدی فقط همینها را روی ساختارها و الگوریتمهای واقعی اجرا میکنند.
ترمِ دو از اولین و پرکاربردترین ظرفِ برنامهنویسی شروع میکند: آرایه و list. آنجا میبینی چرا رفتن به خانهٔ هزارمِ یک list گرانتر از خانهٔ دومش نیست، چرا append ارزان است و insert(0, x) نه، و اینکه یک حلقهٔ کاملاً بیگناه چطور میتواند مرتبهٔ درجهدو را در خودش پنهان کند. و هر ادعایی که آنجا میشود، با همین جدولهایی که این ترم ساختی آزمون میشود.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.