# فصل ۱۰ — پروژه: مرتبهٔ یک کدِ ناشناس را اعلام کن

<div dir="rtl">

# فصل ۱۰ — پروژه: مرتبهٔ یک کدِ ناشناس را اعلام کن

## در این فصل چه یاد می‌گیری

هیچ مفهومِ تازه‌ای. **این فصل همهٔ نُه فصلِ قبل را یکجا به‌کار می‌برد.**

چهار تابع به تو داده می‌شود که هیچ توضیحی ندارند. کارت این است که برای هرکدام **مرتبه را اعلام کنی** — با جدول، با پیش‌بینی، و با خطای گزارش‌شده. یکی از آن چهارتا عمداً تله دارد: **روی نردبانِ ۱۰۰ تا ۸۰۰ ستونِ نسبتش `1.00` است و روی نردبانِ ۵۰٬۰۰۰ تا ۴۰۰٬۰۰۰ می‌شود `1.91`.** همان یک تابع، همان شمارنده.

![چهار جعبهٔ دربستهٔ هم‌شکل روی میزِ آزمایش، که فقط از راهِ ترازو و کرنومتر می‌شود درباره‌شان حرف زد](/lesson-assets/t1-s10-project-order/prompt/01-image-four-sealed-boxes.png)

آخر این فصل می‌توانی:

- کلِ پروتکلِ دوره را بی‌کمک روی یک کدِ ناشناس اجرا کنی
- مرتبه‌ای اعلام کنی که کسِ دیگری بتواند بازتولید و ردش کند
- بگویی گزارشِ تو دقیقاً چه چیزهایی باید داشته باشد تا قابلِ رد کردن باشد

## قبل از شروع

**از فصلِ ۸:** پروتکلِ چهارقدمی — جدول، اعلامِ شکل، معیارِ پذیرش، پیش‌بینی و خطا. **از فصلِ ۵:** اینکه اندازه‌های کوچک دروغ می‌گویند. **از فصلِ ۹:** اینکه بازهٔ `n` بخشی از صورتِ مسئله است.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-1-measure-then-predict/session-10-project-order.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. صورتِ پروژه

**یک «اعلامِ مرتبه» که این پنج چیز را نداشته باشد، قابلِ قبول نیست:**

1. **بازهٔ `n`ی که اندازه‌گیری در آن انجام شده.** بدونِ آن، اعلام هیچ معنایی ندارد.
2. **جدولِ دوبرابری با ستونِ نسبت**، دستِ‌کم چهار اندازه.
3. **مرتبهٔ اعلام‌شده**، همراه با اینکه از کدام ستون و کدام عدد به آن رسیده‌ای.
4. **پیش‌بینیِ اندازهٔ بعدی و معیارِ پذیرشی که قبل از اجرا نوشته شده.**
5. **خطای نسبیِ اندازه‌گیری‌شده، و حکمِ «قبول» یا «رد».**

پنجمی مهم‌ترینشان است: **گزارشی که فقط نتیجه‌های موفق را می‌نویسد، گزارش نیست.**

## ۲. چهار جعبهٔ دربسته

> 🤔 **اول حدس بزن:** کدها را بخوان و **قبل از دیدنِ جدول** برای هر چهارتا یک مرتبه حدس بزن و روی کاغذ بنویس. بعد جدول را ببین. **هر جا حدست غلط بود، آن مورد ارزشِ آموزشیِ بیشتری از سه تای دیگر دارد.**

</div>

```python
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()
```

```text
— 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
```

<div dir="rtl">

**به `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)`.

</div>

```python
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 "رد")
```

```text
         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 درصد  → قبول
```

<div dir="rtl">

**ستونِ `عملیات ÷ (n log n)` چهار بار تقریباً `1.003` داد — یعنی شکل درست انتخاب شده — و خطای پیش‌بینی دو صدمِ درصد شد.**

> ✅ **چک کن:** همین برازش را با شکلِ `n²` تکرار کن. ستونِ نسبتِ برازش باید به‌جای ثابت ماندن، در هر سطر **نصف** شود. آن نصف شدن دقیقاً همان چیزی است که می‌گوید شکل غلط است — و هیچ خطایی هم نمی‌دهد، پس باید خودت نگاهش کنی.

## ۴. تلهٔ `mystery_d`

جدولِ بخشِ ۲ برای `mystery_d` نسبتِ `1.05` و `1.09` و `1.17` داد. وسوسه‌کننده است که بنویسی `O(1)`. **دو نردبانِ دیگر را ببین:**

> 🤔 **اول حدس بزن:** کدِ `mystery_d` را دوباره بخوان و **برای هر دو نردبان یک عدد در ستونِ نسبت بنویس** — یکی ۱۰۰ تا ۸۰۰ و یکی ۵۰٬۰۰۰ تا ۴۰۰٬۰۰۰. اگر حدست برای هر دو یک عدد است، **همان حدس چیزی است که این بخش می‌خواهد بشکند.**

</div>

```python
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")
```

```text
— 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
```

<div dir="rtl">

**`1.00` در یک نردبان و `1.91` در نردبانِ دیگر. همان تابع، همان شمارنده، بدونِ ذره‌ای نویز.**

آن `20_000` عملِ ثابت تا وقتی `n` کوچک است کلِ کار است و مرتبهٔ واقعی را کاملاً پنهان می‌کند. **این همان درسِ فصلِ ۵ است، این بار به‌شکلِ یک تلهٔ واقعی در یک پروژه.**

**پس گزارشِ درست برای `mystery_d` این است:** «در بازهٔ ۱۰۰ تا ۸۰۰ رفتار عملاً ثابت است؛ از حدودِ ۵۰٬۰۰۰ به بعد `O(n)` است.» **دو جمله، دو بازه — و هیچ‌کدام بدونِ دیگری کامل نیست.**

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** چهار تابعِ ناشناس با شکل‌های رشدِ استاندارد، از راهِ ستونِ نسبت. **در کدام بازهٔ `n`؟** ۱٬۰۰۰ تا ۸٬۰۰۰ برای هر چهار تابع، به‌علاوهٔ دو بازهٔ اضافه برای `mystery_d` (۱۰۰ تا ۸۰۰ و ۵۰٬۰۰۰ تا ۴۰۰٬۰۰۰). **با چند تکرار، و کمینه یا میانگین؟** شمارش است، پس یک اجرا و بدونِ خلاصه — **و به همین دلیل هر عددِ این فصل روی ماشینِ تو هم دقیقاً همین است.**

> 🔧 **اگر کار نکرد:** اگر نردبانت را از صفر یا یک شروع کنی، برازشِ `n log n` می‌شکند:

</div>

```python
try:
    print(shape_n_log_n(0))
except ValueError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
ValueError: math domain error
```

<div dir="rtl">

`math.log2` برای صفر تعریف نشده است و برای `n = 1` جوابش صفر می‌شود، که تقسیم را می‌شکند. **نردبانِ برازش همیشه از عددی شروع می‌شود که به `n`ِ واقعیِ تو نزدیک باشد**، نه از کوچک‌ترین عددِ ممکن.

> 🤖 **از دستیارت بپرس:** «چطور از روی ستونِ نسبت تشخیص بدهم بینِ `O(n)` و `O(n log n)`؟» بعد این را هم بپرس: **«اگر ستونِ نسبتِ من ۲٫۲ باشد و با بزرگ‌تر شدنِ `n` پایین بیاید، این به نفعِ کدام‌شان است؟»** — جوابِ درست `O(n log n)` است و دلیلش این است که `log n` با بزرگ شدنِ `n` کندتر رشد می‌کند، پس سهمش از نسبت کم می‌شود.

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| order declaration | اُردر دکلریشن | اعلامِ مستندِ مرتبهٔ یک کد، همراه با بازه و خطا |
| reproducible report | ریپرودیوسبل ریپورت | گزارشی که کسِ دیگری می‌تواند دوباره بسازد و ردش کند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: پنج چیزی که یک اعلامِ مرتبه باید داشته باشد کدام‌اند؟

**تمرینِ اجباری:** برای **هر سه تابعِ باقی‌مانده** — `mystery_b`، `mystery_c` و `mystery_d` — همان پنج بندِ بخشِ ۱ را کامل بنویس. برای هرکدام شکلِ برازش را انتخاب کن، ستونِ «عملیات ÷ شکل» را بساز تا انتخابت را تأیید کند، معیارِ پذیرش را **قبل از اجرا** بنویس، `n` بعدی را پیش‌بینی کن و خطا را گزارش کن. **برای `mystery_d` گزارشت باید دو بازه داشته باشد، نه یکی.**

**تمرینِ ستاره‌دار ⭐:** یک `mystery_e` بنویس که **همکلاسی‌ات را گول بزند**: در بازهٔ ۱٬۰۰۰ تا ۸٬۰۰۰ ستونِ نسبتِ نزدیکِ `2` بدهد ولی در بازهٔ ۱۰۰٬۰۰۰ به بعد نسبتش به `4` برسد. (راهنمایی: یک جملهٔ خطیِ خیلی سنگین کنارِ یک جملهٔ درجه‌دو.) بعد **همان تابع را با پروتکلِ خودت لو بده**: نشان بده کدام یک از پنج بندِ بخشِ ۱ جلوی این تله را می‌گیرد. **جوابت دقیقاً همان دلیلی است که این دوره روی «بازهٔ `n` را بنویس» این‌قدر پافشاری می‌کند.**

## در فصل بعد

ترمِ یک تمام شد و **کلِ روشِ دوره را داری**: ساعتِ صادق، شمارندهٔ قطعی، جدولِ دوبرابری، شش منحنی، `Big-O` به‌عنوان پیش‌بینی، پروتکلِ برازش و پیش‌بینی، و نقطهٔ تقاطع. **هر پنج ترمِ بعدی فقط همین‌ها را روی ساختارها و الگوریتم‌های واقعی اجرا می‌کنند.**

ترمِ دو از اولین و پرکاربردترین ظرفِ برنامه‌نویسی شروع می‌کند: **آرایه و `list`.** آنجا می‌بینی چرا رفتن به خانهٔ هزارمِ یک `list` گران‌تر از خانهٔ دومش نیست، چرا `append` ارزان است و `insert(0, x)` نه، و اینکه یک حلقهٔ کاملاً بی‌گناه چطور می‌تواند مرتبهٔ درجه‌دو را در خودش پنهان کند. **و هر ادعایی که آنجا می‌شود، با همین جدول‌هایی که این ترم ساختی آزمون می‌شود.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t1/s10-project-order (یادستان, Yaadestan)
