# فصل ۰۵ — جدولِ دوبرابری: `n` را دو برابر کن و نگاه کن

<div dir="rtl">

# فصل ۰۵ — جدولِ دوبرابری: `n` را دو برابر کن و نگاه کن

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

چهار تابع می‌سازیم و هر چهارتا را با شمارندهٔ فصلِ قبل روی یک نردبانِ دوبرابری می‌بریم. ستونِ نسبتِ هر کدام یک عددِ متفاوت می‌دهد و **هر چهار عدد بلافاصله می‌گویند کد چه شکلی رشد می‌کند**: `1.00`، `1.10`، `2.00`، `4.00`.

بعد یک تلهٔ واقعی را باز می‌کنیم. **همان یک تابع، همان شمارنده: در `n`های ۱۰ تا ۸۰ ستونِ نسبت `1.03` می‌دهد و در `n`های ۵۰۰ تا ۴۰۰۰ می‌دهد `3.99`.** اگر فقط جدولِ اول را دیده بودی، دربارهٔ آن کد نتیجه‌ای می‌گرفتی که صد در صد غلط بود.

![نردبانی که فاصلهٔ هر پله تا پلهٔ بعد دقیقاً دو برابرِ فاصلهٔ قبلی است](/lesson-assets/t1-s05-doubling-table/prompt/01-image-doubling-ladder.png)

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

- جدولِ دوبرابری بسازی: چهار اندازه که هر بار دو برابر می‌شوند، به‌علاوهٔ ستونِ نسبت
- **از روی ستونِ نسبت** بگویی هزینه چه شکلی با `n` می‌رود
- بگویی چرا دوبرابری، و نه مثلاً «هر بار هزار تا اضافه کن»
- تشخیص بدهی جدولی که در `n`های کوچک گرفته شده کِی دروغ می‌گوید
- `lambda`ی جدول‌سازت را طوری بنویسی که هر سطر واقعاً `n`ِ خودش را بسنجد

## قبل از شروع

**از فصلِ ۴:** شمارندهٔ عملیات، و اینکه شمارش قطعی است.

**از فصلِ ۱:** جدولی که ستونِ نسبت دارد. **همان ستون، از این فصل به بعد ابزارِ اصلیِ ماست.**

</div>

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

<div dir="rtl">

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

## ۱. چرا دوبرابری، و نه چیزِ دیگری

می‌شد نردبانِ اندازه‌ها را جمعی ساخت: `1000`، `2000`، `3000`، `4000`. **ولی آن نردبان ستونِ نسبتِ بی‌معنایی می‌دهد**، چون فاصلهٔ سطرها یکسان نیست: از `1000` به `2000` دو برابر شده‌ای و از `3000` به `4000` فقط یک‌سومِ بیشتر.

با نردبانِ **ضربی** — هر بار دقیقاً دو برابر — سؤالِ هر سطر همیشه یکی است: **«`n` دو برابر شد؛ کار چند برابر شد؟»** و چون سؤال ثابت است، جواب‌ها با هم قابلِ مقایسه‌اند.

> 🌱 **ریشه‌اش کجاست:** دو برابر کردنِ پیاپی همان چیزی است که در [ریشه ترمِ ۱ فصل ۸](/courses/risheh/lessons/term-1-numbers/session-08-powers) با نامِ **توان** ساخته می‌شود: چهار بار دو برابر کردن یعنی ضرب در `2⁴`. **نردبانِ ما هم دقیقاً یک نردبانِ توانی است**، و همین باعث می‌شود با چهار سطرِ کوتاه بتوانی بازهٔ هشت برابری از `n` را پوشش بدهی.

## ۲. چهار شکلِ رشد، با شمارنده

چهار تابع می‌نویسیم که هر کدام کارِ متفاوتی می‌کنند. **هر چهارتا شمارندهٔ خودشان را دارند، پس عددها قطعی‌اند.**

> 🤔 **اول حدس بزن:** برای هر یک از این چهار تابع بنویس با دو برابر شدنِ `n` تعدادِ عملیات چند برابر می‌شود. مخصوصاً برای `halve_down` حدس بزن، چون دشوارترینشان است.

</div>

```python
LADDER = [500, 1_000, 2_000, 4_000]


def look_first(values):
    """فقط به اولین عضو نگاه می‌کند."""
    return values[0], 1


def total(values):
    """همهٔ عضوها را یکی‌یکی جمع می‌زند."""
    ops = 0
    running = 0
    for v in values:
        running += v
        ops += 1
    return running, ops


def halve_down(values):
    """هر بار نصفِ بازه را کنار می‌گذارد تا یک عضو بماند."""
    ops = 0
    size = len(values)
    while size > 1:
        size //= 2
        ops += 1
    return size, ops


def all_pairs(values):
    """هر جفتِ ممکن را دقیقاً یک بار می‌بیند."""
    ops = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            ops += 1
    return None, ops


data = {n: list(range(n)) for n in LADDER}
for name, fn in (("look_first", look_first), ("halve_down", halve_down),
                 ("total", total), ("all_pairs", all_pairs)):
    print(f"— {name}")
    table([(n, fn(data[n])[1]) for n in LADDER], "عملیات", ",d")
    print()
```

```text
— look_first
         n            عملیات     نسبت به سطر قبل
       500                 1                   —
     1,000                 1                1.00
     2,000                 1                1.00
     4,000                 1                1.00

— halve_down
         n            عملیات     نسبت به سطر قبل
       500                 8                   —
     1,000                 9                1.12
     2,000                10                1.11
     4,000                11                1.10

— total
         n            عملیات     نسبت به سطر قبل
       500               500                   —
     1,000             1,000                2.00
     2,000             2,000                2.00
     4,000             4,000                2.00

— all_pairs
         n            عملیات     نسبت به سطر قبل
       500           124,750                   —
     1,000           499,500                4.00
     2,000         1,999,000                4.00
     4,000         7,998,000                4.00

```

<div dir="rtl">

**چهار عددِ متفاوت در ستونِ نسبت، و هر کدام یک داستانِ متفاوت.**

به `halve_down` بیشتر دقت کن، چون تنها موردی است که با حدسِ شهودی جور در نمی‌آید. با دو برابر شدنِ `n`، تعدادِ عملیات فقط **یکی** اضافه می‌شود: `8`، `9`، `10`، `11`. **منطقش ساده است: یک بار دو برابر کردنِ ورودی، فقط یک نصف‌کردنِ اضافه لازم دارد.** برای همین نسبتش نه ثابت است و نه دو؛ عددی کمی بالای یک است که با بزرگ‌تر شدنِ `n` **به یک نزدیک‌تر هم می‌شود**.

> ✅ **چک کن:** `LADDER` را به `[4_000, 8_000, 16_000, 32_000]` ببر و فقط `halve_down` را دوباره بگیر. ستونِ نسبت باید از `1.10` به چیزی مثلِ `1.08` برود. **اگر نرفت، احتمالاً `size //= 2` را به `size -= 2` تبدیل کرده‌ای** — و آن‌وقت نسبت `2.00` می‌شود، چون کارِ کاملاً متفاوتی است.

## ۳. قاعدهٔ خواندنِ ستونِ نسبت

حالا می‌شود یک قاعدهٔ عملی نوشت. **`n` را دو برابر کن و به نسبت نگاه کن:**

- **نزدیکِ `1`** — کار به اندازهٔ ورودی تقریباً کاری ندارد. `look_first` مثالِ خالصش است.
- **کمی بالای `1` و رو به کاهش** — با هر دو برابر شدنِ `n` فقط یک قدم اضافه می‌شود. این شکلِ `halve_down` است.
- **نزدیکِ `2`** — کار پابه‌پای `n` جلو می‌رود: دو برابر داده، دو برابر کار.
- **کمی بالای `2` و رو به کاهش** — پابه‌پای `n` جلو می‌رود، به‌علاوهٔ یک لایهٔ نصف‌کردن. این شکل را در فصلِ بعد می‌بینی.
- **نزدیکِ `4`** — کار با **مربعِ** `n` می‌رود: دو برابر داده، چهار برابر کار.
- **بزرگ‌تر از `4` و رو به انفجار** — نسبت خودش هم با `n` بزرگ می‌شود. این بدترین حالت است و فصلِ بعد نشانت می‌دهد چقدر بد.

> 🌱 **ریشه‌اش کجاست:** «دو برابر شدنِ طول، چهار برابر شدنِ مساحت» همان شهودی است که [ریشه ترمِ ۵ فصل ۵](/courses/risheh/lessons/term-5-geometry/session-05-area-perimeter) با پیتزا می‌سازد. **`all_pairs` دقیقاً همان است**: هر عضو با هر عضو، یعنی یک مربعِ `n` در `n` — و مساحتِ مربع با مربعِ ضلعش می‌رود.

**و مهم‌ترین نکتهٔ این قاعده:** هیچ‌کدام از این عددها به ثانیه، ماشین یا زبانِ برنامه‌نویسی بند نیستند. **نسبت را ادعا کن، نه ثانیه را** — این دومین قاعدهٔ ثابتِ گزارش‌نویسی در این دوره.

## ۴. اندازه‌های کوچک دروغ می‌گویند

حالا تابعی که پیش از حلقهٔ اصلی‌اش یک **آماده‌سازیِ ثابت** دارد — کاری که هزینه‌اش به `n` بستگی ندارد. این در کدِ واقعی همه‌جا هست: خواندنِ یک فایلِ تنظیمات، ساختنِ یک جدول، برقراری یک اتصال.

> 🤔 **اول حدس بزن:** همین تابع را روی **دو** نردبان می‌بریم — یکی `10` تا `80` و یکی `500` تا `4000`. **برای هر کدام یک عدد در ستونِ نسبت بنویس.** و مهم‌ترین بخشِ حدست این باشد: آیا انتظار داری دو عدد یکی باشند؟

</div>

```python
SETUP_COST = 5_000


def with_setup(values):
    """یک آماده‌سازیِ ثابت، بعد همان حلقهٔ جفت‌ها."""
    ops = 0
    for _ in range(SETUP_COST):          # به n بستگی ندارد
        ops += 1
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            ops += 1
    return ops


print("— اندازه‌های کوچک")
table([(n, with_setup(list(range(n)))) for n in (10, 20, 40, 80)], "عملیات", ",d")
print("\n— اندازه‌های بزرگ‌تر، همان تابع")
table([(n, with_setup(data[n])) for n in LADDER], "عملیات", ",d")
```

```text
— اندازه‌های کوچک
         n            عملیات     نسبت به سطر قبل
        10             5,045                   —
        20             5,190                1.03
        40             5,780                1.11
        80             8,160                1.41

— اندازه‌های بزرگ‌تر، همان تابع
         n            عملیات     نسبت به سطر قبل
       500           129,750                   —
     1,000           504,500                3.89
     2,000         2,004,000                3.97
     4,000         8,003,000                3.99
```

<div dir="rtl">

**یک تابع، یک شمارنده، دو جدول، دو نتیجهٔ کاملاً متضاد.**

جدولِ اول می‌گوید «نسبت `1.03` است، پس اندازهٔ ورودی تقریباً بی‌اثر است». جدولِ دوم می‌گوید «نسبت `3.99` است، پس کار با مربعِ `n` می‌رود». **هر دو جدول درست‌اند و فقط یکی‌شان به دردِ تصمیم می‌خورد.**

دلیلش را می‌شود با یک تقسیم دید: در `n = 10`، آن `5,000` عملِ آماده‌سازی **۹۹ درصدِ کل** است و حلقهٔ جفت‌ها `45` تا. در `n = 4000`، آماده‌سازی `5,000` از `8,003,000` است — کمتر از یک‌دهمِ درصد. **بخشی که غالب است عوض شده، و ستونِ نسبت شکلِ همان بخشِ غالب را نشان می‌دهد.**

**قاعده‌ای که از این درمی‌آید و تا آخرِ دوره برقرار است: جدولت را در بازه‌ای بساز که به `n`ِ واقعیِ خودت نزدیک باشد.** جدولی که در `n = 10` گرفته شده، دربارهٔ `n = 4000` هیچ چیزی نمی‌گوید — و برعکس.

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

## ۵. همان جدول، این بار با ساعت

شمارنده صاف است؛ حالا ببینیم ساعت همان شکل را نشان می‌دهد یا نه.

</div>

```python
rows = [(n, 1000 * clock(lambda values=data[n]: all_pairs(values), repeat=3))
        for n in LADDER]
table(rows)
```

```text-approx
         n         زمان (ms)     نسبت به سطر قبل
       500               3.3                   —
     1,000              14.2                4.27
     2,000              63.4                4.47
     4,000             237.0                3.74
```

<div dir="rtl">

**ستونِ زمان همان داستان را می‌گوید، ولی با لهجه‌ای لرزان: `4.27`، `4.47`، `3.74` به‌جای `4.00`، `4.00`، `4.00`.**

هر سه «حدودِ چهار» هستند و هیچ‌کدام چهار نیستند. **این همان نویزِ فصلِ ۳ است و هیچ‌وقت هم کاملاً نمی‌رود.** برای همین از این به بعد، **هر جا بتوانیم هر دو جدول را می‌گیریم**: شمارنده برای اعلامِ شکلِ رشد، ساعت برای اینکه بدانیم آن شکل روی این ماشین چقدر گران است.

**و حالا به یک تکه از همان خط نگاه کن که تا آخرِ دوره ده‌ها بار تکرار می‌شود:** `lambda values=data[n]: all_pairs(values)`.

`lambda` را فصلِ ۲ ساخت: `clock` یک **تابع** می‌خواهد نه نتیجهٔ یک تابع. **ولی آن `values=data[n]` چیزِ دیگری است و کارش این است که مقدار را همین حالا میخ کند.** یک `lambda` مقدارِ متغیرهای بیرونی‌اش را **موقعِ صدا زده شدن** می‌خواند، نه موقعِ ساخته شدن؛ آرگومانِ پیش‌فرض برعکس است و **موقعِ ساخته شدن** حساب می‌شود. **تا وقتی `clock` را در همان دورِ حلقه صدا بزنی، این تفاوت هیچ اثری ندارد. اولین باری که یک خط جابه‌جا شود، دارد.**

> 🔧 **اگر کار نکرد:** اگر ستونِ نسبتت **دقیقاً `1.00`** درآمد، قبل از هر چیز به `lambda`هایت نگاه کن. این‌جا همان کار را با شمارنده انجام می‌دهیم تا عددها قطعی بمانند — اول `lambda`ها را می‌سازیم و **بعد** صدایشان می‌زنیم، همان کاری که هر کسی موقعِ مرتب کردنِ کدش می‌کند:

</div>

```python
DEMO = [250, 500, 1_000, 2_000]
demo_data = {n: list(range(n)) for n in DEMO}

loose = [lambda: all_pairs(demo_data[n]) for n in DEMO]
pinned = [lambda values=demo_data[n]: all_pairs(values) for n in DEMO]

print("— بدونِ پین کردن")
table([(n, job()[1]) for n, job in zip(DEMO, loose)], "عملیات", ",d")
print("\n— با پینِ آرگومانِ پیش‌فرض")
table([(n, job()[1]) for n, job in zip(DEMO, pinned)], "عملیات", ",d")
```

```text
— بدونِ پین کردن
         n            عملیات     نسبت به سطر قبل
       250         1,999,000                   —
       500         1,999,000                1.00
     1,000         1,999,000                1.00
     2,000         1,999,000                1.00

— با پینِ آرگومانِ پیش‌فرض
         n            عملیات     نسبت به سطر قبل
       250            31,125                   —
       500           124,750                4.01
     1,000           499,500                4.00
     2,000         1,999,000                4.00
```

<div dir="rtl">

**جدولِ اول هیچ خطایی نداد، هیچ هشداری نداد، و کاملاً غلط است.** هر چهار `lambda`ی نسخهٔ اول موقعِ صدا زده شدن `n` را می‌خوانند و آن موقع `n` دیگر `2000` است — پس **هر چهار سطر همان بزرگ‌ترین اندازه را می‌سنجند** و ستونِ نسبت `1.00` می‌شود. **و `1.00` در این دوره یک عددِ محترم است: یعنی `O(1)`.** یک جدولِ مرتب و باورپذیر که یک نتیجهٔ کاملاً ساختگی اعلام می‌کند.

**قاعده، و از این‌جا به بعدِ دوره بی‌استثنا:** هر `lambda`یی که داخلِ حلقه یا `list comprehension` ساخته می‌شود، **باید مقدارش را با آرگومانِ پیش‌فرض پین کند** — `lambda v=data[n]: ...`، نه `lambda: ... data[n] ...`. **حتی وقتی همان‌جا صدایش می‌زنی و لازم نیست**؛ چون عادت است که تو را نجات می‌دهد، نه دقت در یک لحظهٔ خاص.

**و یک اشتباهِ رایج‌ترِ دیگر با `table`:** قالبِ عدد را با نوعِ داده جور نکنی — زمانِ اعشاری را با قالبِ عددِ صحیح چاپ کنی:

</div>

```python
try:
    table(rows, "زمان", ",d")
except ValueError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
         n              زمان     نسبت به سطر قبل
ValueError: Unknown format code 'd' for object of type 'float'
```

<div dir="rtl">

دقت کن که **سطرِ عنوان چاپ شد و بعد کار خوابید** — یعنی خطا وسطِ کار افتاده، نه اولِ کار. پیام هم صریح است: قالبِ `d` مالِ عددِ صحیح است. برای شمارشِ عملیات `",d"` و برای زمان `",.1f"` — که مقدارِ پیش‌فرضِ `table` هم همین است.

> 🤖 **از دستیارت بپرس:** «چرا نردبانِ ضربی برای دیدنِ شکلِ رشد بهتر از نردبانِ جمعی است؟» بعد این را هم بپرس: **«اگر به‌جای دو برابر، هر بار سه برابر کنم، ستونِ نسبت برای یک الگوریتمِ درجه‌دوم چه عددی می‌دهد؟»** — جوابش `9` است و اگر بتوانی بگویی چرا، قاعدهٔ خواندنِ ستونِ نسبت را واقعاً فهمیده‌ای.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| doubling table | دابلینگ تیبل | جدولی که در آن `n` هر بار دو برابر می‌شود |
| growth ratio | گروث ریشیو | نسبتِ اندازه‌گیریِ هر سطر به سطرِ قبل |
| setup cost | ستاپ کاست | هزینهٔ ثابتی که به `n` بستگی ندارد |
| dominant part | دامیننت پارت | بخشی که سهمش از کلِ کار از بقیه بیشتر است |
| late binding | لیت بایندینگ | اینکه یک `lambda` مقدارِ متغیرِ بیرونی را موقعِ **صدا زده شدن** می‌خواند، نه موقعِ ساخته شدن |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: ستونِ نسبتِ نزدیکِ `4` چه چیزی دربارهٔ کد می‌گوید، و ستونِ نسبتِ نزدیکِ `1` چه؟

**تمرینِ اجباری:** `SETUP_COST` را از `5_000` به `500_000` ببر و **هر دو جدولِ بخشِ ۴** را دوباره بساز. **سؤالِ اصلی: از کدام `n` به بعد ستونِ نسبت به `4` نزدیک می‌شود؟** جوابت باید یک عدد باشد، و بعد در یک جمله بگو چرا آن عدد با بزرگ‌تر شدنِ آماده‌سازی جابه‌جا می‌شود.

**تمرینِ ستاره‌دار ⭐:** تابعی بنویس که ستونِ نسبت را در `n`های ۵۰ تا ۴۰۰ نزدیکِ `8` بدهد — **بازه را عمداً کوچک گرفته‌ایم، چون سه حلقهٔ تودرتو در `n = 4000` بیش از ده میلیارد دور می‌شود و اجرایش تمام نمی‌شود.** (راهنمایی: `all_pairs` دو حلقهٔ تودرتو دارد؛ سه‌تا چه می‌شود؟) بعد **قبل از اجرا پیش‌بینی کن** شمارشِ `n = 50` چند می‌شود و بنویس از کدام فرمول درآوردی‌اش. حالا اجرا کن. **اگر پیش‌بینی‌ات غلط بود، فرمول را اصلاح کن، نه کد را** — و بنویس کجا اشتباه کرده بودی.

## در فصل بعد

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

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t1/s05-doubling-table (یادستان, Yaadestan)
