# فصل ۰۴ — عمل بشمار، نه ثانیه

<div dir="rtl">

# فصل ۰۴ — عمل بشمار، نه ثانیه

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

دو فصل با نویز جنگیدیم و بهترین کاری که توانستیم بکنیم رساندنِ پراکندگی به حدودِ دو درصد بود. **این فصل ساعت را کنار می‌گذارد.**

به‌جای ثانیه، **مقایسه‌ها را می‌شماریم.** جدولی که درمی‌آید این است — `۴٬۹۵۰`، `۱۹٬۹۰۰`، `۷۹٬۸۰۰`، `۳۱۹٬۶۰۰` — و **این چهار عدد روی ماشینِ تو، روی ماشینِ من و در هر اجرایی دقیقاً همین‌ها هستند.** پراکندگی صفر است، نه دو درصد.

بعد هزینه‌اش را هم می‌پردازیم: **خودِ شمارنده کد را حدودِ یک‌ونیم برابر کند می‌کند** — و می‌بینیم چرا این اصلاً اهمیتی ندارد.

![دو ابزارِ اندازه‌گیری کنارِ هم: کرنومتری با عقربهٔ لرزان و شمارنده‌ای مکانیکی با ارقامِ قفل‌شده](/lesson-assets/t1-s04-count-operations/prompt/01-image-clock-versus-counter.png)

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

- **عملیاتِ اصلیِ** یک تکه کد را انتخاب کنی و بگویی چرا همان
- شمارنده را طوری بنویسی که جوابِ تابع را عوض نکند
- بگویی چرا شمارش تکرارپذیر است و ثانیه نیست
- بفهمی شمردنِ عملِ اشتباه چطور جدولی می‌سازد که کاملاً درست به‌نظر می‌رسد و کاملاً غلط است

## قبل از شروع

**از فصلِ ۳:** پراکندگی و آستانهٔ باور. **از فصلِ ۱:** `first_duplicate` و بدترین ورودی.

</div>

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

<div dir="rtl">

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

## ۱. کدام عمل را بشماریم

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

**عملیاتِ اصلی** آن کاری است که **با بزرگ شدنِ `n` تعدادش زیاد می‌شود و بقیه دنبالش می‌آیند.** در `first_duplicate` این کار روشن است: مقایسهٔ `values[i] == values[j]`. هر بار که این مقایسه انجام می‌شود، چند کارِ ریزِ دیگر هم انجام می‌شود — ولی همه‌شان **به‌ازای همان یک مقایسه** هستند، پس تعدادشان ضریبی از همان است.

انتخابِ عملیاتِ اصلی یک **تصمیم** است و باید نوشته شود. در بخشِ ۵ می‌بینی اگر بد انتخاب شود چه بلایی سرِ نتیجه می‌آید.

## ۲. تابعی که جوابش را با هزینه‌اش می‌دهد

> 🤔 **اول حدس بزن:** قبل از اجرا بنویس — اگر `n` را دو برابر کنیم، **تعدادِ مقایسه‌ها** چند برابر می‌شود؟ و آیا انتظار داری ستونِ نسبت از ستونِ نسبتِ جدولِ زمانیِ فصلِ ۱ صاف‌تر باشد یا ناهموارتر؟

</div>

```python
COUNT_SIZES = [100, 200, 400, 800]


def counted_duplicate(values):
    """جوابِ تابع، به‌علاوهٔ تعدادِ مقایسه‌هایی که برای رسیدن به آن انجام شد."""
    comparisons = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            comparisons += 1
            if values[i] == values[j]:
                return values[i], comparisons
    return None, comparisons


rng = random.Random(SEED)
inputs = {n: rng.sample(range(10 * n), n) for n in COUNT_SIZES}
rows = []
for n in COUNT_SIZES:
    answer, comparisons = counted_duplicate(inputs[n])
    rows.append((n, comparisons))
table(rows, "مقایسه", ",d")
```

```text
         n            مقایسه     نسبت به سطر قبل
       100             4,950                   —
       200            19,900                4.02
       400            79,800                4.01
       800           319,600                4.01
```

<div dir="rtl">

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

`4,950` عددِ من نیست؛ عددِ خودِ الگوریتم است. برای فهرستی با `100` عضو که هیچ تکراری ندارد، دقیقاً `100 × 99 ÷ 2` مقایسه لازم است، هر که اجرایش کند و هر جا اجرایش کند. **و این عدد از یک جمعِ ساده درمی‌آید که تا آخرِ دوره بارها برمی‌گردد**، پس همین‌جا از صفر می‌سازیمش.

عضوِ اول با `99` عضوِ بعدی مقایسه می‌شود، عضوِ دوم با `98` تا، … و عضوِ یکی‌مانده‌به‌آخر با `1` تا. **پس کلِ کار `1 + 2 + … + 99` است.** برای بستنِ این جمع یک ترفندِ سه‌خطی هست: **همان جمع را یک بار برعکس زیرِ خودش بنویس و ستون‌ها را جمع بزن.**

</div>

```text
   1  +   2  +   3  + … +  98  +  99
  99  +  98  +  97  + … +   2  +   1
 ---   ---   ---         ---   ---
 100  + 100  + 100  + … + 100  + 100
```

<div dir="rtl">

هر ستون `100` می‌شود و `99` ستون داریم، پس **دو برابرِ جمع** برابرِ `99 × 100` است و خودِ جمع نصفش. **همین را با کد وارسی می‌کنیم:**

</div>

```python
m = 99                                   # عضوِ اول با ۹۹ عضوِ بعدی مقایسه می‌شود
forward = list(range(1, m + 1))
backward = list(range(m, 0, -1))
columns = [a + b for a, b in zip(forward, backward)]
print("سه ستونِ اول:", columns[:3], "· همه یکی‌اند؟", len(set(columns)) == 1)
print(f"دو برابرِ جمع = {m} ستونِ {columns[0]}تایی = {m * columns[0]:,}")
print("پس خودِ جمع   =", m * columns[0] // 2)
print("جمعِ مستقیم    =", sum(range(1, m + 1)))
print("فرمولِ n(n-1)/2 در n = 100 =", 100 * 99 // 2)
```

```text
سه ستونِ اول: [100, 100, 100] · همه یکی‌اند؟ True
دو برابرِ جمع = 99 ستونِ 100تایی = 9,900
پس خودِ جمع   = 4950
جمعِ مستقیم    = 4950
فرمولِ n(n-1)/2 در n = 100 = 4950
```

<div dir="rtl">

**سه راه، یک عدد.** با `n` به‌جای `100` همین استدلال `n(n-1)/2` می‌دهد — **و این فرمول از این‌جا به بعد سه بار دیگر لازم می‌شود:** فصلِ ۸ ثابتِ برازشش `0.5` است چون همین فرمول تقریباً `n²/2` است، فصلِ ۹ نقطهٔ تقاطع را از حلِ همین فرمول درمی‌آورد، و ترمِ ۲ فصلِ ۵ همین را برای `1 + 2 + … + n` تکرار می‌کند.

و ستونِ نسبت هم صاف است: `4.02`، `4.01`، `4.01`. **هیچ‌کدام دقیقاً `4` نیستند و این هم دقیق است، نه نویز** — عدد کمی از چهار **بیشتر** است چون فرمول `n(n-1)/2` است، نه `n²/2`. با بزرگ‌تر شدنِ `n` این اختلاف کوچک‌تر می‌شود.

> ✅ **چک کن:** `4950 * 4` می‌شود `19800` ولی جدول `19900` می‌گوید. اگر این صد واحد اختلاف را دیدی و برایت سؤال شد، **دقیقاً همان چیزی را دیده‌ای که باید:** نسبتِ دوبرابری در ابتدا کمی بزرگ‌تر از چهار است و آرام‌آرام به چهار نزدیک می‌شود. با `n = 100_000` نسبت به `4.00` می‌رسد.

## ۳. شمارش تکرار می‌شود، ثانیه نه

</div>

```python
def first_duplicate(values):
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] == values[j]:
                return values[i]
    return None


big = inputs[800]
counts = [counted_duplicate(big)[1] for _ in range(3)]
times = []
for _ in range(3):
    start = time.perf_counter()
    first_duplicate(big)
    times.append(1000 * (time.perf_counter() - start))
print("سه بار شمارش :", counts)
print("هر سه یکی‌اند؟", counts[0] == counts[1] == counts[2])
print("سه بار زمان  :", [round(t, 3) for t in times])
print("هر سه یکی‌اند؟", times[0] == times[1] == times[2])
```

```text-approx
سه بار شمارش : [319600, 319600, 319600]
هر سه یکی‌اند؟ True
سه بار زمان  : [11.401, 11.472, 11.592]
هر سه یکی‌اند؟ False
```

<div dir="rtl">

**دلیلش را در یک جمله می‌شود گفت: شمارش خاصیتِ خودِ الگوریتم است و ثانیه خاصیتِ الگوریتم به‌علاوهٔ ماشین به‌علاوهٔ لحظه.**

پس از این به بعد دو ابزار داریم و **هر کدام سؤالِ خودشان را جواب می‌دهند:**

- **شمارنده** می‌گوید الگوریتم **چقدر کار می‌کند** و شکلِ رشدش چیست. تکرارپذیر، بدونِ نویز، مستقل از ماشین.
- **ساعت** می‌گوید آن کار روی **این ماشین** چقدر طول می‌کشد. تنها ابزاری که به سؤالِ «کاربر چقدر صبر می‌کند؟» جواب می‌دهد.

**هیچ‌کدام جایگزینِ دیگری نیست** و از این به بعد هر جا بتوانیم، هر دو را می‌گیریم.

## ۴. شمارنده مجانی نیست

آن خطِ `comparisons += 1` هم خودش یک عمل است و وقت می‌گیرد.

</div>

```python
ids = rng.sample(range(40_000), 4_000)
plain = clock(lambda: first_duplicate(ids), repeat=3)
counted = clock(lambda: counted_duplicate(ids), repeat=3)
print(f"بدونِ شمارنده : {1000 * plain:>7.1f} ms")
print(f"با شمارنده   : {1000 * counted:>7.1f} ms")
print(f"شمارنده کد را {counted / plain:.2f} برابر کند کرد")
```

```text-approx
بدونِ شمارنده :   278.6 ms
با شمارنده   :   415.7 ms
شمارنده کد را 1.49 برابر کند کرد
```

<div dir="rtl">

**نسخهٔ شمارنده‌دار حدودِ یک‌ونیم برابر کندتر است. و این هیچ اهمیتی ندارد** — به شرطی که بدانی چرا.

شمارنده را **برای اندازه‌گیریِ زمان به‌کار نمی‌بریم**؛ برای شمردنِ عملیات به‌کارش می‌بریم، و آن عدد از کند شدنِ کد اثر نمی‌گیرد: `319,600` مقایسه، `319,600` مقایسه می‌ماند.

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

## ۵. شمردنِ عملِ اشتباه

حالا فرض کن کسی عملیاتِ اصلی را بد انتخاب کرده باشد: به‌جای مقایسه‌ها، **دورهای حلقهٔ بیرونی** را بشمارد.

</div>

```python
def counted_outer_only(values):
    """فقط دورهای حلقهٔ بیرونی را می‌شمارد — انتخابِ غلطِ عملیاتِ اصلی."""
    rounds = 0
    for i in range(len(values)):
        rounds += 1
        for j in range(i + 1, len(values)):
            if values[i] == values[j]:
                return values[i], rounds
    return None, rounds


rows = [(n, counted_outer_only(inputs[n])[1]) for n in COUNT_SIZES]
table(rows, "دورِ حلقهٔ بیرونی", ",d")
```

```text
         n دورِ حلقهٔ بیرونی     نسبت به سطر قبل
       100               100                   —
       200               200                2.00
       400               400                2.00
       800               800                2.00
```

<div dir="rtl">

**این جدول بی‌نقص است. ستونِ نسبتش از جدولِ درست هم صاف‌تر است — دقیقاً `2.00` در هر سه سطر. و کاملاً گمراه‌کننده است.**

اگر فقط این جدول را می‌دیدی، می‌گفتی هزینه با `n` جلو می‌رود و بی‌خیالِ کد می‌شدی. **در حالی که همان کد، در همان بازه، کارش چهار برابر می‌شود.**

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

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

> 🔧 **اگر کار نکرد:** نسخهٔ شمارنده‌دار دو چیز برمی‌گرداند، نه یکی. اگر فراموشش کنی، پایتون سرِ اولین کاری که با جواب بکنی گیر می‌دهد:

</div>

```python
try:
    answer = counted_duplicate(inputs[100])
    print(answer + 1)
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: can only concatenate tuple (not "int") to tuple
```

<div dir="rtl">

پیام صریح است: `answer` یک `tuple` است، نه عدد. **درستش `answer, comparisons = counted_duplicate(...)` است.** اگر تعدادِ متغیرهای سمتِ چپ با تعدادِ چیزهای برگشتی نخواند، پیامِ دیگری می‌گیری: `ValueError: too many values to unpack (expected 2)`.

## ۶. چیزی که شمارش نمی‌گوید

شمارنده یک چیزِ مهم را **نمی‌داند: هر عمل چقدر گران است.**

`319,600` مقایسهٔ عدد با عدد یک چیز است؛ `319,600` مقایسهٔ رشتهٔ صدنویسه‌ای چیزِ دیگری است. **هر دو در شمارنده یک عدد می‌دهند و در ساعت دو عددِ کاملاً متفاوت.**

**پس شمارنده و ساعت با هم کار می‌کنند، نه به‌جای هم.** این نکته در فصلِ ۹ به یک نتیجهٔ عملیِ عجیب می‌رسد: الگوریتمی که **کارِ بیشتری** می‌شمارد، می‌تواند روی داده‌های واقعیِ تو **زودتر** تمام شود.

> 🤖 **از دستیارت بپرس:** «چرا تعدادِ مقایسه‌های یک حلقهٔ دوتایی روی `n` عضو برابرِ `n(n-1)/2` است؟» بعد این را هم بپرس: **«اگر همان الگوریتم را طوری بنویسم که هر جفت را دو بار مقایسه کند، شمارش چه می‌شود و کدام نتیجه‌گیریِ من عوض می‌شود؟»** — جوابِ درست این است که شمارش دو برابر می‌شود ولی **ستونِ نسبت هیچ تغییری نمی‌کند**، و همین شروعِ درسِ فصلِ ۷ است.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| primary operation | پرایمری آپریشن | کاری که با بزرگ شدنِ `n` تعدادش زیاد می‌شود و بقیه دنبالش می‌آیند |
| operation count | آپریشن کانت | تعدادِ دفعاتِ انجامِ عملیاتِ اصلی، مستقل از ماشین |
| deterministic | دترمینیستیک | چیزی که در هر اجرا دقیقاً همان جواب را می‌دهد |
| instrumentation | اینسترومنتیشن | افزودنِ کدِ اندازه‌گیری به برنامه، با هزینهٔ خودش |
| arithmetic series | آریتمتیک سریز | جمعِ `1 + 2 + … + m`، که با استدلالِ جفت‌کردن `m(m+1)/2` می‌شود |

<div dir="rtl">

## تمرین‌ها

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

**تمرینِ اجباری:** ورودی را از بدترین حالت به یک حالتِ متوسط ببر: فهرستی بساز که **دقیقاً یک جفت تکراری در وسطش** داشته باشد. جدولِ شمارشِ بخشِ ۲ را با همین ورودی بساز. **دو سؤال:** ستونِ نسبت هنوز نزدیکِ چهار است یا نه، و **عددِ شمارش چند برابر کوچک‌تر از بدترین حالت شد؟** جوابت باید توضیح بدهد چرا نسبت و عدد، دو چیزِ متفاوت‌اند.

**تمرینِ ستاره‌دار ⭐:** یک شمارندهٔ دوم به `counted_duplicate` اضافه کن که **خواندنِ خانهٔ فهرست** (`values[i]` و `values[j]`) را بشمارد. حالا جدولی با **دو ستونِ شمارش** بساز. **سؤالِ اصلی: نسبتِ این دو ستون به هم در چهار اندازه ثابت می‌ماند؟** اگر ثابت ماند، توضیح بده چرا انتخابِ اینکه کدام‌شان را «عملیاتِ اصلی» بنامیم، بر ستونِ نسبت اثری ندارد — و بر چه چیزی **هست**.

## در فصل بعد

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

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t1/s04-count-operations (یادستان, Yaadestan)
