در این فصل چه یاد میگیری#
این فصل امضای کلِ دوره است. پنج ترمِ بعدی فقط همین پروتکل را روی ساختارها و الگوریتمهای مختلف اجرا میکنند.
پروتکل چهار قدم دارد: جدول بگیر، مرتبه را اعلام کن، معیارِ پذیرش را قبل از اجرا بنویس، بعد اندازهٔ بعدی را اجرا کن و خطای پیشبینیات را گزارش کن.
اول روی یک تابعِ تمیز اجرایش میکنیم و خطای 0.025 درصد میگیریم. بعد عمداً میشکنیمش: یک تابع، یک پروتکل، دو بازهٔ n — خطای 33.2 درصد و خطای 5.9 درصد. اولی رد میشود و دومی قبول، و تنها تفاوتشان این است که جدول را کجا گرفتهایم.
آخر این فصل میتوانی:
- از یک جدولِ اندازهگیری، ثابتِ برازش را دربیاوری
- اندازهٔ بعدی را پیشبینی کنی و قبل از اجرا بنویسی چه خطایی را قبول داری
- خطای نسبی را حساب کنی و نتیجه را «قبول» یا «رد» اعلام کنی
- شکستِ یک پیشبینی را بهعنوان یک نتیجه گزارش کنی، نه یک آبروریزی
قبل از شروع#
از فصلِ ۷: Big-O بهعنوان یک پیشبینی، و اینکه فقط دربارهٔ nهای بزرگ حرف میزند.
از فصلِ ۵: جدولِ دوبرابری و ستونِ نسبت. از فصلِ ۴: شمارندهٔ عملیات.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. برازش یعنی پیدا کردنِ یک عدد#
ستونِ نسبت به تو شکل را میدهد: نزدیکِ 4 یعنی n². ولی شکل بهتنهایی پیشبینی نمیسازد؛ برای پیشبینی به یک عددِ دیگر هم احتیاج داری: ضریبی که آن شکل را روی دادهٔ تو مینشاند.
آن ضریب را از تقسیمِ ساده درمیآوری: c برابر است با اندازهگیری تقسیم بر شکل. اگر شکل درست انتخاب شده باشد، این عدد در همهٔ سطرها تقریباً یکی درمیآید — و همان، آزمونِ درستیِ انتخابِ توست.
def all_pairs(values):
ops = 0
for i in range(len(values)):
for j in range(i + 1, len(values)):
ops += 1
return ops
def square(n):
return n * n
LADDER = [250, 500, 1_000, 2_000]
measured = {n: all_pairs(list(range(n))) for n in LADDER}
table([(n, measured[n]) for n in LADDER], "عملیات", ",d")
print()
print(f"{'n':>10}{'عملیات ÷ n²':>18}")
for n in LADDER:
print(f"{n:>10,}{measured[n] / square(n):>18.5f}")
n عملیات نسبت به سطر قبل
250 31,125 —
500 124,750 4.01
1,000 499,500 4.00
2,000 1,999,000 4.00
n عملیات ÷ n²
250 0.49800
500 0.49900
1,000 0.49950
2,000 0.49975
ستونِ دوم چهار بار تقریباً همان عدد را میدهد: نزدیکِ 0.5.
این یعنی انتخابِ شکل درست بوده. اگر شکل را غلط انتخاب کرده بودی — مثلاً n بهجای n² — این ستون بهجای ثابت ماندن، خودش با n بالا میرفت و همانجا لو میرفت.
✅ چک کن:
squareرا با تابعی عوض کن که فقطnبرمیگرداند و همان ستون را دوباره بگیر. عددها باید124.5،249.5،499.5و999.5شوند — یعنی هر بار تقریباً دو برابر، نه ثابت. همین «ثابت نماندن» تنها آزمونی است که میگوید شکل را غلط انتخاب کردهای، و قبل از هر پیشبینیای باید انجامش بدهی.
🌱 ریشهاش کجاست: اگر عملیات را روی محورِ عمودی و
n²را روی محورِ افقی بگذاری، این چهار نقطه روی یک خطِ راستِ گذرنده از مبدأ مینشینند و آن0.5دقیقاً شیبِ همان خط است. معنای شیب بهعنوانِ نرخِ تغییر در ریشه ترمِ ۴ فصل ۴ ساخته میشود و شکلِy = mx + bدر ریشه ترمِ ۴ فصل ۳. کارِ ما اینجا همان است، باbبرابرِ صفر.
۲. پیشبینی، با معیارِ پذیرشِ نوشتهشده#
حالا قدمی که بیشترین ارزشِ آموزشی را دارد و بیشتر از همه هم جا انداخته میشود: قبل از اجرا بنویس چه خطایی را قبول داری.
اگر معیار را بعد از دیدنِ نتیجه بنویسی، همیشه قبول میشوی — و آن دیگر آزمون نیست.
🤔 اول حدس بزن: ثابتِ برازش نزدیکِ
0.5است و اندازهٔ بعدی4,000. بنویس چند عملیات پیشبینی میکنی، و بنویس خطایت را زیرِ چند درصد انتظار داری.
LAST = LADDER[-1]
NEXT = 2 * LAST
TOLERANCE = 25.0 # درصد — معیارِ پذیرش، پیش از اجرا نوشته شد
c = measured[LAST] / square(LAST)
predicted = c * square(NEXT)
print(f"ثابتِ برازش از n = {LAST:,} : c = {c:.5f}")
print(f"پیشبینی برای n = {NEXT:,} : {predicted:,.0f} عملیات")
print(f"معیارِ پذیرش : خطای کمتر از {TOLERANCE:.0f} درصد")
actual = all_pairs(list(range(NEXT)))
error = 100 * abs(predicted - actual) / actual
print(f"\nاندازهگیریِ واقعی : {actual:,} عملیات")
print(f"خطای نسبی : {error:.3f} درصد")
print("نتیجه :", "قبول" if error < TOLERANCE else "رد")
ثابتِ برازش از n = 2,000 : c = 0.49975
پیشبینی برای n = 4,000 : 7,996,000 عملیات
معیارِ پذیرش : خطای کمتر از 25 درصد
اندازهگیریِ واقعی : 7,998,000 عملیات
خطای نسبی : 0.025 درصد
نتیجه : قبول
خطای بیستوپنج هزارم درصد. و توجه کن که صفر نشد — چون فرمولِ واقعی n(n-1)/2 است و ما با n²/2 تقریبش زدیم. آن -n/2 جا افتاده، و در n = 4000 سهمش دقیقاً همان دو هزار عمل است که کم آوردهایم.
این پروتکل چهار قدم دارد و از این به بعد هر جا ادعای پیچیدگی میکنیم، همین چهار قدم اجرا میشوند:
- جدولِ دوبرابری بگیر و از ستونِ نسبت شکل را اعلام کن.
- ثابتِ برازش را از بزرگترین اندازهٔ اندازهگیریشده دربیاور.
- معیارِ پذیرش را بنویس، بعد اندازهٔ بعدی را پیشبینی کن.
- اجرا کن، خطای نسبی را حساب کن، و «قبول» یا «رد» را اعلام کن.
قدمِ دومْ ریزهکاری دارد: ثابت را از بزرگترین اندازه بردار، نه از میانگینِ همه. بزرگترین اندازه به nی که میخواهی پیشبینی کنی نزدیکتر است، و در بخشِ بعد میبینی چرا این نزدیکی همهچیز است.
۳. یک پیشبینی که رد میشود#
حالا تابعی که دو بخشِ کار دارد: یک حلقهٔ تودرتو و یک کارِ خطیِ سنگین.
K = 100
def mixed_work(values):
"""یک حلقهٔ تودرتو، بهعلاوهٔ یک کارِ خطیِ سنگین."""
ops = 0
n = len(values)
for i in range(n):
for j in range(i + 1, n):
ops += 1
for _ in range(K * n):
ops += 1
return ops
SMALL = [25, 50, 100, 200]
small_measured = {n: mixed_work(list(range(n))) for n in SMALL}
table([(n, small_measured[n]) for n in SMALL], "عملیات", ",d")
c_small = small_measured[200] / square(200)
predicted_small = c_small * square(400)
actual_small = mixed_work(list(range(400)))
error_small = 100 * abs(predicted_small - actual_small) / actual_small
print(f"\nبرازش روی n = 200 → c = {c_small:.5f}")
print(f"پیشبینی برای n = 400: {predicted_small:,.0f}")
print(f"اندازهگیریِ واقعی : {actual_small:,}")
print(f"خطای نسبی : {error_small:.1f} درصد →",
"قبول" if error_small < TOLERANCE else "رد")
n عملیات نسبت به سطر قبل
25 2,800 —
50 6,225 2.22
100 14,950 2.40
200 39,900 2.67
برازش روی n = 200 → c = 0.99750
پیشبینی برای n = 400: 159,600
اندازهگیریِ واقعی : 119,800
خطای نسبی : 33.2 درصد → رد
رد. و این بهترین لحظهٔ این فصل است.
اول به ستونِ نسبت نگاه کن: 2.22، 2.40، 2.67. این عددها نه نزدیکِ 2 هستند و نه نزدیکِ 4؛ بینِ دو خانوادهاند و بالا میروند. دقیقاً همان چیزی که یک تابعِ دوجملهای در ناحیهٔ گذارش نشان میدهد. اگر جدول را با دقت خوانده بودیم، همانجا میفهمیدیم که برای برازش هنوز خیلی زود است.
و اشتباهی که بعدش کردیم صریح است: ما شکلِ n² را روی دادهای نشاندیم که هنوز n² بر آن غالب نشده بود. در n = 200، جملهٔ خطی 20,000 است و جملهٔ تودرتو 19,900 — یعنی نصفِ کار مالِ جملهای است که در فرمولِ پیشبینیِ ما اصلاً نبود.
⚠️ مواظب باش: پیشبینیِ ما بیشتر از واقعیت درآمد، نه کمتر. این ضدِ شهود است — انتظار داری با جا انداختنِ یک جمله، کمبرآورد کنی. ولی ثابتِ
cرا از همان دادهٔ آلوده گرفتیم، پسcبزرگتر از حقش درآمد (0.9975بهجای چیزی نزدیکِ0.5) و بعد آن ثابتِ بزرگشده درn²ضرب شد. درسش این است: وقتی شکل را غلط انتخاب کنی، حتی جهتِ خطا هم قابلِ حدس نیست.
۴. همان تابع، همان پروتکل، بازهٔ درست#
هیچ چیزی از کد را عوض نمیکنیم. فقط جدول را در بازهٔ بزرگتری میگیریم.
BIG = [200, 400, 800, 1_600]
big_measured = {n: mixed_work(list(range(n))) for n in BIG}
table([(n, big_measured[n]) for n in BIG], "عملیات", ",d")
c_big = big_measured[1_600] / square(1_600)
predicted_big = c_big * square(3_200)
actual_big = mixed_work(list(range(3_200)))
error_big = 100 * abs(predicted_big - actual_big) / actual_big
print(f"\nبرازش روی n = 1,600 → c = {c_big:.5f}")
print(f"پیشبینی برای n = 3,200: {predicted_big:,.0f}")
print(f"اندازهگیریِ واقعی : {actual_big:,}")
print(f"خطای نسبی : {error_big:.1f} درصد →",
"قبول" if error_big < TOLERANCE else "رد")
n عملیات نسبت به سطر قبل
200 39,900 —
400 119,800 3.00
800 399,600 3.34
1,600 1,439,200 3.60
برازش روی n = 1,600 → c = 0.56219
پیشبینی برای n = 3,200: 5,756,800
اندازهگیریِ واقعی : 5,438,400
خطای نسبی : 5.9 درصد → قبول
33.2 درصد به 5.9 درصد، بدونِ یک خط تغییر در کد.
ستونِ نسبت هم داستان را میگوید: 3.00، 3.34، 3.60 — هنوز به 4 نرسیده ولی در راهش است. و ثابتِ برازش از 0.9975 به 0.5622 آمده، یعنی به 0.5ِ واقعی نزدیکتر شده.
این کلِ معنای «nِ خودت را بگو» است. یک ادعای پیچیدگی بدونِ بازهٔ n نه درست است و نه غلط؛ بیمعناست.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک پروتکلِ ثابت روی یک تابعِ ثابت، در دو بازهٔ متفاوتِ
n. در کدام بازهٔn؟ برازش روی ۲۵ تا ۲۰۰ و پیشبینی برای ۴۰۰؛ بعد برازش روی ۲۰۰ تا ۱٬۶۰۰ و پیشبینی برای ۳٬۲۰۰. با چند تکرار، و کمینه یا میانگین؟ شمارش است، پس یک اجرا و بدونِ خلاصه — و به همین دلیل عددِ33.2و5.9روی ماشینِ تو هم دقیقاً همینها هستند.
۵. همان پروتکل، این بار با ساعت#
شمارش قطعی است و آسان. ساعت سختتر است، چون نویزِ فصلِ ۳ روی خطای پیشبینی سوار میشود.
TIME_LADDER = [500, 1_000, 2_000]
data = {n: list(range(n)) for n in TIME_LADDER + [4_000]}
times = {n: 1000 * clock(lambda values=data[n]: all_pairs(values), repeat=3)
for n in TIME_LADDER}
table([(n, times[n]) for n in TIME_LADDER])
c_time = times[2_000] / square(2_000)
predicted_time = c_time * square(4_000)
actual_time = 1000 * clock(lambda: all_pairs(data[4_000]), repeat=3)
error_time = 100 * abs(predicted_time - actual_time) / actual_time
print(f"\nپیشبینی برای n = 4,000: {predicted_time:,.1f} ms")
print(f"اندازهگیریِ واقعی : {actual_time:,.1f} ms")
print(f"خطای نسبی : {error_time:.1f} درصد →",
"قبول" if error_time < TOLERANCE else "رد")
n زمان (ms) نسبت به سطر قبل
500 3.4 —
1,000 15.4 4.47
2,000 57.2 3.72
پیشبینی برای n = 4,000: 228.8 ms
اندازهگیریِ واقعی : 233.3 ms
خطای نسبی : 1.9 درصد → قبول
پیشبینیِ زمان هم قبول شد، ولی عددِ خطایش را نمیشود مثلِ شمارش جدی گرفت.
دلیلش را از فصلِ ۳ میدانی: پراکندگیِ خودِ اندازهگیری با این پروتکل حدودِ دو درصد است. خطای 1.9 درصد دقیقاً در همان بازه است، یعنی از نویز قابلِ تشخیص نیست. اگر عدد 1.9 یا 0.4 یا 3.1 درآید، هر سه یک معنا دارند: «پیشبینی خراب نبود».
قاعدهای که از این درمیآید: معیارِ پذیرشِ زمان را هرگز کوچکتر از پراکندگیِ خودِ اندازهگیری نگذار. معیارِ پنجدرصدی روی سنجهای که خودش دو درصد میلرزد، معیارِ خوبی نیست؛ نصفِ وقتها به نویز رأی میدهی.
🔧 اگر کار نکرد: طبیعی است که بخواهی نتیجهٔ اندازهٔ بعدی را از همان دیکشنریِ اندازهگیریها بخوانی. همانجا پروتکل به تو یادآوری میکند که هنوز اجرایش نکردهای:
try:
print(measured[16_000])
except KeyError as err:
print(f"{type(err).__name__}: {err}")
KeyError: 16000
KeyError: 16000 یعنی «چنین اندازهای در اندازهگیریهای تو نیست». و این دقیقاً همان چیزی است که پیشبینی را پیشبینی میکند: عددِ 16,000 هنوز وجود ندارد و تا وقتی اجرایش نکنی، هر چیزی که دربارهاش میگویی یک ادعاست. پروتکل میگوید ادعا را بنویس، بعد اجرا کن، بعد خطا را گزارش کن.
🤖 از دستیارت بپرس: «چرا ثابتِ برازش را باید از بزرگترین اندازهٔ اندازهگیریشده گرفت و نه از میانگینِ همهٔ سطرها؟» بعد این را هم بپرس: «اگر بهجای دو برابر، بخواهم ده برابرِ بزرگترین اندازهٔ اندازهگیریشده را پیشبینی کنم، انتظار دارم خطا چه بلایی سرش بیاید؟» — جوابِ درست این است که خطا بزرگتر میشود، و دلیلش همان چیزی است که در بخشِ ۳ دیدی: هرچه از بازهٔ اندازهگیری دورتر بروی، سهمِ جملههایی که در فرمولت نیستند بیشتر عوض میشود.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| fit | فیت | پیدا کردنِ ضریبی که شکلِ رشد را روی دادهٔ اندازهگیریشده مینشاند |
| relative error | رلتیو ارور | فاصلهٔ پیشبینی تا واقعیت، بر حسبِ درصدِ واقعیت |
| acceptance criterion | اکسپتنس کرایتریون | حدِ خطایی که پیش از اجرا نوشته میشود |
| interpolation | اینترپولیشن | پیشبینی داخلِ بازهای که اندازه گرفتهای |
| extrapolation | اکستراپولیشن | پیشبینی بیرونِ آن بازه — همیشه پرریسکتر |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
تا اینجا فرض کردهایم مرتبهٔ کوچکتر همیشه بهتر است. فصلِ بعد آن فرض را با اندازهگیری میشکند.
دو الگوریتم برای یک مسئلهٔ واحد مینویسیم: یکی O(n²) و دیگری با مرتبهٔ خیلی بهتر ولی با یک سربارِ راهاندازیِ سنگین. در شمارشِ عملیات، نقطهٔ تقاطعشان دقیقاً n = 449 است و این عدد روی هر ماشینی همین است. روی ساعت، نقطهٔ تقاطع n = 550 درآمد — و آن عدد مالِ همین ماشین است. تفاوتِ این دو عدد، کلِ چیزی است که Big-O به تو نمیگوید.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.