# فصل ۰۹ — پروژه: یک سیاههٔ بزرگ، دو بار

<div dir="rtl">

# فصل ۰۹ — پروژه: یک سیاههٔ بزرگ، دو بار

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

هیچ مفهومِ تازه‌ای. **این فصل هشت فصلِ قبل را روی یک مسئلهٔ واقعی به‌کار می‌برد.**

یک سیاههٔ بزرگ داریم و باید روی یک **پنجرهٔ لغزان** از سطرهایش گزارش بسازیم. دو نسخه می‌نویسیم که **خروجیِ کاملاً یکسان** می‌دهند: یکی با ظرف‌های بد، یکی با ظرف‌های درست. بعد یک جدولِ دوبرابری برای هر دو.

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

![نوارِ بلندِ کاغذی که از دو ماشینِ متفاوت رد می‌شود و دو خروجیِ یکسان می‌دهد](/lesson-assets/t2-s09-project-log-stream/prompt/01-image-tape-run-twice.png)

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

- الگوی دسترسیِ یک مسئلهٔ واقعی را قبل از نوشتنِ کد بنویسی
- دو نسخه بسازی، برابریِ خروجیشان را ثابت کنی و مرتبه‌شان را اعلام کنی
- **سهمِ هر تصمیم را جدا اندازه بگیری** به‌جای اینکه حدس بزنی کدام مقصر است

## قبل از شروع

**از فصلِ ۴ و ۷:** `pop(0)` در برابرِ `popleft`. **از فصلِ ۵:** `items = items + [x]`. **از فصلِ ۸:** الگوی دسترسی و جدولِ تصمیم.

</div>

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

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-2-arrays-and-lists/session-09-project-log-stream.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. صورتِ مسئله و الگوی دسترسی

سیاههٔ ما `n` سطر دارد و هر سطر یک شمارهٔ ترتیبی، یک سطحِ اهمیت و یک نامِ واحد دارد. هر سطح یک **وزن** دارد.

**کاری که باید انجام شود:** برای هر سطر، مجموعِ وزنِ **`k` سطرِ آخر** را گزارش کن — یعنی یک پنجرهٔ لغزان به طولِ `k`. اندازهٔ پنجره را یک‌دهمِ کلِ سیاهه می‌گیریم، چون در کارِ واقعی هم پنجره معمولاً با حجمِ داده بزرگ می‌شود.

**الگوی دسترسی، قبل از هر کدی:**

1. سطرها یکی‌یکی و به‌ترتیب می‌آیند — هیچ خواندنِ تصادفی‌ای لازم نیست.
2. در هر گام یک عضو به **انتهای** پنجره اضافه می‌شود و یک عضو از **ابتدا** بیرون می‌رود.
3. خروجی فقط به انتها اضافه می‌شود.

**بندِ دوم می‌گوید پنجره یک `queue` است و بندِ سوم می‌گوید خروجی فقط `append` لازم دارد.** جدولِ فصلِ ۸ برای هر دو یک ظرف نام می‌برد — و ما عمداً اول نسخه‌ای می‌نویسیم که هیچ‌کدام را رعایت نکند.

</div>

```python
LEVELS = ("INFO", "WARN", "ERROR")
COST = {"INFO": 1, "WARN": 5, "ERROR": 25}


def make_log(n, seed=SEED):
    rng = random.Random(seed)
    return [f"{i:07d} {rng.choice(LEVELS)} unit-{rng.randrange(50)}" for i in range(n)]


def weight(line):
    return COST[line.split(" ", 2)[1]]


sample = make_log(5)
for line in sample:
    print(line, "->", weight(line))
```

```text
0000000 WARN unit-7 -> 5
0000001 INFO unit-5 -> 1
0000002 ERROR unit-2 -> 25
0000003 ERROR unit-44 -> 25
0000004 INFO unit-6 -> 1
```

<div dir="rtl">

**داده با `SEED` ساخته می‌شود، پس روی ماشینِ تو هم دقیقاً همین پنج سطر است.**

## ۲. دو نسخه

نسخهٔ اول دو تصمیمِ بد دارد و هر دو کاملاً طبیعی به‌نظر می‌رسند: پنجره یک `list` است که از ابتدایش `pop(0)` می‌شود، و خروجی با `out = out + [x]` ساخته می‌شود.

نسخهٔ دوم هر دو را عوض می‌کند: پنجره یک `deque` با `maxlen` است — که خودش عضوِ اضافه را از ابتدا بیرون می‌اندازد — و خروجی با `append` ساخته می‌شود.

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

</div>

```python
from collections import deque


def summarise_slow(lines):
    """پنجره یک list است و از ابتدایش pop(0) می‌شود؛ خروجی با + ساخته می‌شود."""
    k = max(1, len(lines) // 10)
    window = []
    running = 0
    out = []
    for line in lines:
        w = weight(line)
        window.append(w)
        running += w
        if len(window) > k:
            running -= window.pop(0)
        out = out + [running]
    return out


def summarise_fast(lines):
    """پنجره یک deque با maxlen است؛ خروجی با append ساخته می‌شود."""
    k = max(1, len(lines) // 10)
    window = deque(maxlen=k)
    running = 0
    out = []
    for line in lines:
        w = weight(line)
        if len(window) == k:
            running -= window[0]
        window.append(w)
        running += w
        out.append(running)
    return out


check = make_log(2_000)
print("دو نسخه دقیقاً یک خروجی می‌دهند؟", summarise_slow(check) == summarise_fast(check))
print("طولِ خروجی:", len(summarise_fast(check)), "· ده مقدارِ اول:",
      summarise_fast(check)[:10])
```

```text
دو نسخه دقیقاً یک خروجی می‌دهند؟ True
طولِ خروجی: 2000 · ده مقدارِ اول: [5, 6, 31, 56, 57, 62, 63, 64, 89, 94]
```

<div dir="rtl">

**سطرِ اول اجباری است و بدونِ آن بقیهٔ فصل بی‌معنا بود.** دو نسخه‌ای که خروجیِ متفاوت می‌دهند، دو الگوریتمِ متفاوت‌اند، نه دو پیاده‌سازیِ یک چیز.

## ۳. جدولِ اندازه‌گیری

</div>

```python
LOGS = [2_000, 4_000, 8_000, 16_000]
logs = {n: make_log(n) for n in LOGS}
print("— نسخهٔ اول (ظرف‌های بد)")
table([(n, 1000 * clock(lambda v=logs[n]: summarise_slow(v), repeat=2)) for n in LOGS],
      "زمان (ms)", ",.2f")
print("\n— نسخهٔ دوم (ظرف‌های درست)")
table([(n, 1000 * clock(lambda v=logs[n]: summarise_fast(v), repeat=2)) for n in LOGS],
      "زمان (ms)", ",.2f")
print(f"\n{'n':>10}{'نسخهٔ اول ÷ نسخهٔ دوم':>24}")
for n in LOGS:
    a = clock(lambda v=logs[n]: summarise_slow(v), repeat=2)
    b = clock(lambda v=logs[n]: summarise_fast(v), repeat=2)
    print(f"{n:>10,}{a / b:>24.1f}")
```

```text-approx
— نسخهٔ اول (ظرف‌های بد)
         n         زمان (ms)     نسبت به سطر قبل
     2,000              4.39                   —
     4,000             15.73                3.58
     8,000             65.97                4.20
    16,000            274.58                4.16

— نسخهٔ دوم (ظرف‌های درست)
         n         زمان (ms)     نسبت به سطر قبل
     2,000              0.62                   —
     4,000              1.20                1.94
     8,000              2.41                2.00
    16,000              4.82                2.01

         n   نسخهٔ اول ÷ نسخهٔ دوم
     2,000                     7.0
     4,000                    12.6
     8,000                    26.5
    16,000                    46.6
```

<div dir="rtl">

**ستونِ نسخهٔ اول نزدیکِ `4` و ستونِ نسخهٔ دوم نزدیکِ `2`** — `O(n²)` در برابرِ `O(n)`، با خروجیِ کاملاً یکسان. و ستونِ آخر همان چیزی است که فصلِ ۷ هم نشان داد: **نسبت خودش با `n` بزرگ می‌شود**، از چند برابر تا چند ده برابر. **روی سیاههٔ واقعیِ یک میلیون سطری، همین کد اصلاً تمام نمی‌شود.**

## ۴. کدام تصمیم مقصر بود؟

**تا اینجا فقط می‌دانیم نسخهٔ اول کند است. نمی‌دانیم کدام‌یک از دو تصمیمِ بدش مقصر است** — و «حدس می‌زنم `pop(0)`» یک جواب نیست.

پس دو نسخهٔ ترکیبی می‌سازیم و هر چهار حالت را می‌سنجیم.

</div>

```python
def summarise_mixed_window(lines):
    """پنجرهٔ بد، خروجیِ خوب."""
    k = max(1, len(lines) // 10)
    window = []
    running = 0
    out = []
    for line in lines:
        w = weight(line)
        window.append(w)
        running += w
        if len(window) > k:
            running -= window.pop(0)
        out.append(running)
    return out


def summarise_mixed_output(lines):
    """پنجرهٔ خوب، خروجیِ بد."""
    k = max(1, len(lines) // 10)
    window = deque(maxlen=k)
    running = 0
    out = []
    for line in lines:
        w = weight(line)
        if len(window) == k:
            running -= window[0]
        window.append(w)
        running += w
        out = out + [running]
    return out


n = 16_000
data = logs[n]
variants = (("هر دو بد", summarise_slow),
            ("فقط پنجرهٔ بد", summarise_mixed_window),
            ("فقط خروجیِ بد", summarise_mixed_output),
            ("هر دو خوب", summarise_fast))
print("هر چهار نسخه یک خروجی می‌دهند؟",
      len({tuple(fn(check)) for _, fn in variants}) == 1)
print(f"\nn = {n:,}\n")
print(f"{'نسخه':>18}{'زمان (ms)':>14}{'نسبت به بهترین':>18}")
times = [(name, 1000 * clock(lambda f=fn: f(data), repeat=2)) for name, fn in variants]
best = min(t for _, t in times)
for name, t in times:
    print(f"{name:>18}{t:>14.2f}{t / best:>18.1f}")
```

```text-approx
هر چهار نسخه یک خروجی می‌دهند؟ True

n = 16,000

              نسخه     زمان (ms)    نسبت به بهترین
          هر دو بد        272.42              53.0
     فقط پنجرهٔ بد          6.91               1.3
     فقط خروجیِ بد        267.35              52.0
         هر دو خوب          5.14               1.0
```

<div dir="rtl">

**این نتیجه خلافِ چیزی است که تقریباً همه حدس می‌زنند.**

`pop(0)` روی پنجره — همان تلهٔ آشکارِ فصلِ ۴ — تقریباً هیچ سهمی ندارد. `items = items + [x]` روی خروجی — همان خطی که هیچ‌کس دو بار نگاهش نمی‌کند — تقریباً تمامِ اختلاف را می‌سازد.

**و دلیلش کاملاً قابلِ توضیح است، به شرطی که بعد از دیدنِ عدد دنبالش بگردی:**

- پنجره `n/10` عضو دارد، پس هر `pop(0)` حدودِ `n/10` خانه را جابه‌جا می‌کند — ولی این جابه‌جایی یک انتقالِ پیوسته است که سخت‌افزار برایش ساخته شده و فصلِ ۱ نشان داد چقدر ارزان است.
- `out + [x]` هر بار **کلِ خروجیِ تا اینجا** را در یک ظرفِ تازه کپی می‌کند: هم به‌اندازهٔ `n` کار، هم `n` بار ساختنِ ظرفِ تازه و دور ریختنِ قبلی. **کارِ حافظه، نه فقط کارِ کپی.**

> ⚠️ **مواظب باش:** این ترتیب به **اندازهٔ پنجره** بند است. کارِ جابه‌جاییِ پنجره `k(n−k)` است: با `k = n/10` حدودِ ۲۳ میلیون خانه، و با `k = n/2` نزدیکِ ۶۴ میلیون — نزدیکِ سه برابر بیشتر. سهمِ پنجره بزرگ‌تر می‌شود، ولی ترتیب برعکس نمی‌شود: در `n = 16,000` و `k = n/2` پنجرهٔ بد روی همین ماشین حدودِ هشت میلی‌ثانیه گرفت و خروجیِ بد حدودِ ۲۵۰ میلی‌ثانیه. و اگر `k` را برابرِ خودِ `n` بگذاری، هیچ `pop(0)`ی اصلاً اجرا نمی‌شود و پنجره رایگان می‌شود. **این دقیقاً معنیِ «`n`ِ خودت را بگو» است — و این‌جا `k`ِ خودت را هم.**

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** چهار نسخه از یک تابع که فقط در دو تصمیمِ ظرف با هم فرق دارند، و هر چهار خروجیِ یکسان می‌دهند — با `==` تأییدشده. **در کدام بازهٔ `n`؟** جدولِ رشد در ۲٬۰۰۰ تا ۱۶٬۰۰۰ با پنجرهٔ `n/10`، و تفکیکِ مقصر در یک اندازهٔ ثابت `n = 16,000`. **با چند تکرار، و کمینه یا میانگین؟** دو تکرار به‌علاوهٔ گرم‌کننده، کمینه، و همان دادهٔ ثابت برای هر چهار نسخه.

> ✅ **چک کن:** در `summarise_fast` عبارتِ `deque(maxlen=k)` را به `deque()` تغییر بده و **بدونِ هیچ تغییرِ دیگری** جدول را بگیر. **خروجی غلط می‌شود** — چون پنجره دیگر خودش را کوتاه نمی‌کند و `window[0]` قدیمی‌ترین عضوِ کلِ سیاهه می‌ماند. سطرِ مقایسهٔ `==` باید `False` بدهد. **این نشان می‌دهد چرا آن سطر در هر آزمایشی اول می‌آید، نه آخر.**

## ۵. گزارشِ نهایی

**این پنج بند همان چیزی است که فصلِ ۱۰ ترمِ ۱ خواست، این بار برای یک انتخابِ ظرف:**

1. **الگوی دسترسی:** افزودن به انتها و حذف از ابتدا در پنجره؛ فقط افزودن به انتها در خروجی؛ هیچ خواندنِ تصادفی.
2. **بازهٔ `n`:** ۲٬۰۰۰ تا ۱۶٬۰۰۰ سطر، با پنجرهٔ `n/10`.
3. **مرتبهٔ اعلام‌شده:** نسخهٔ اول `O(n²)` و نسخهٔ دوم `O(n)`، هر دو از ستونِ نسبت.
4. **درستی:** خروجیِ هر چهار نسخه با `==` برابر تأیید شد.
5. **نتیجهٔ خلافِ انتظار:** تصمیمی که مقصرِ آشکار به‌نظر می‌رسید تقریباً بی‌اثر بود.

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

> 🔧 **اگر کار نکرد:** یکی از اشتباه‌های رایجِ انتقالِ کد از `list` به `deque` فوری خودش را نشان می‌دهد:

</div>

```python
window = deque([1, 2], maxlen=3)
window.insert(1, 99)                     # هنوز جا دارد
print("پنجرهٔ نیمه‌پر:", window)
try:
    window.insert(1, 77)                 # حالا پر است
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
پنجرهٔ نیمه‌پر: deque([1, 99, 2], maxlen=3)
IndexError: deque already at its maximum size
```

<div dir="rtl">

`deque` متدِ `insert` دارد ولی وقتی ظرف پر باشد **اجازهٔ درج در وسط را نمی‌دهد**، چون معلوم نیست کدام سر باید قربانی شود. **هر بار که یک ظرف کاری را رد می‌کند، دارد چیزی دربارهٔ ساختِ خودش می‌گوید.**

> 🤖 **از دستیارت بپرس:** **جدولِ بخشِ ۴ را جلویش بگذار و بپرس:** «چرا `pop(0)` روی یک پنجرهٔ ۱٬۶۰۰تایی تقریباً رایگان است ولی `out = out + [x]` روی یک خروجیِ ۱۶٬۰۰۰تایی نیست؟» — جوابِ درست باید دو چیز را از هم جدا کند: تعدادِ خانه‌هایی که جابه‌جا می‌شوند، و تعدادِ ظرف‌هایی که ساخته و دور ریخته می‌شوند.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| sliding window | اسلایدینگ ویندو | بازه‌ای به طولِ ثابت که روی دنباله جلو می‌رود |
| `maxlen` | مکس‌لن | سقفِ طولِ یک `deque`؛ عضوِ اضافه خودبه‌خود از سرِ دیگر بیرون می‌رود |

<div dir="rtl">

## تمرین‌ها

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

**تمرینِ اجباری:** مسئله را عوض کن: به‌جای مجموع، **بیشترین وزن در پنجره** را گزارش کن. یک نسخهٔ ساده بنویس که در هر گام کلِ پنجره را می‌گردد، و جدولِ چهار اندازه‌ای‌اش را بگیر. **سؤالِ اصلی: چرا این نسخه حتی با `deque` هم `O(n²)` است؟** جوابت باید به قاعدهٔ تشخیصِ فصلِ ۵ برگردد و بگوید کدام عملِ `O(n)` داخلِ کدام حلقهٔ `n`تایی نشسته.

**تمرینِ ستاره‌دار ⭐:** کلِ خروجیِ نسخهٔ دوم را در حافظه نگه می‌داریم و برای `n = 1,000,000` این یعنی یک `list` یک‌میلیونی. **قبل از هر کدی، حجمِ تخمینی‌اش را با یک ضرب حساب کن** (فصلِ ۸ عددِ هر عضو را دارد). حالا نسخه‌ای بنویس که به‌جای برگرداندنِ کلِ خروجی، فقط **مجموع و بیشینه** را نگه دارد. **پیش‌بینی کن این تغییر روی زمان چه اثری دارد** — بهتر، بدتر، یا هیچ — بعد اندازه بگیر و خطای پیش‌بینی‌ات را بنویس. **و در آخر: چه چیزی را از دست دادی که در جدول دیده نمی‌شود؟**

## در فصل بعد

ترمِ دو تمام شد و برای هر عملیاتِ یک ظرفِ ترتیبی هزینه‌ای داری که **خودت** اندازه گرفته‌ای. **ولی یک سطر از جدولِ فصلِ ۸ خالی ماند: پرسشِ «هست یا نه؟»**

**ترمِ سه دقیقاً همان است.** یک `hash table` را از صفر می‌سازی، می‌بینی `set` و `dict` چه معامله‌ای می‌کنند، و بدترین حالتشان را پیدا می‌کنی — چون این بار، بر خلافِ کلِ این ترم، **هزینهٔ اعلام‌شده و هزینهٔ واقعی می‌توانند خیلی از هم دور باشند.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t2/s09-project-log-stream (یادستان, Yaadestan)
