# فصل ۰۳ — معاملهٔ حافظه و زمان

<div dir="rtl">

# فصل ۰۳ — معاملهٔ حافظه و زمان

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

یک `index` می‌سازیم و پرسش‌ها را از حدودِ **دو میلی‌ثانیه** به کسری از **یک میکروثانیه** می‌رسانیم — بیش از بیست‌وپنج هزار برابر. **بعد قیمتش را به بایت اندازه می‌گیریم**، و می‌بینیم که هر عبارتِ اضافه حدودِ **۸٫۵ بایت** به آن اضافه می‌کند.

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

![دو کفهٔ ترازو که یکی ساعت و دیگری انبارِ قفسه‌دار روی آن است](/lesson-assets/t6-s03-space-time/prompt/01-image-space-time-scale.png)

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

- هزینهٔ حافظهٔ یک `index` را به بایت اندازه بگیری، نه حدس بزنی
- معامله را به‌شکلِ یک **نرخ** بنویسی و بگویی آن نرخ «به‌ازای هر چه» است
- تشخیص بدهی کِی دیوارِ مسئله حافظه است نه زمان
- ساختاری را رد کنی که سریع‌تر است ولی در بازهٔ `n`ِ تو ساخته نمی‌شود

## قبل از شروع

**از ترمِ ۳ فصلِ ۵:** `dict` و هزینهٔ ساختِ اولیه‌اش. **از ترمِ ۲ فصلِ ۸:** `sys.getsizeof` و اینکه `list` ارجاع نگه می‌دارد نه مقدار. **از فصلِ ۱:** برگهٔ شکلِ مسئله.

</div>

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

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-6-choose-and-defend/session-03-space-time.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. مسئله، و شکلش

فهرستی از عبارت داریم و پرسش این است: **«کدام عبارت‌ها با این سه حرف شروع می‌شوند؟»**

**شکلِ مسئله، قبل از هر کدی:** فهرست یک بار ساخته می‌شود و بعد `q` بار پرسیده می‌شود؛ هیچ درجی بعد از ساخت نداریم. **پس نسبتِ خواندن به نوشتن بالاست و — طبقِ فصلِ ۱ — این همان خانه‌ای است که تصمیم را تعیین می‌کند.** بازهٔ `n`: ده هزار تا هشتاد هزار عبارت.

</div>

```python
LETTERS = "abcdefghij"
PREFIX = 3


def make_terms(n, seed=SEED):
    """n عبارتِ یکتا از یک الفبای ده‌حرفی."""
    rng = random.Random(seed)
    seen, out = set(), []
    while len(out) < n:
        word = "".join(rng.choice(LETTERS) for _ in range(rng.randint(6, 10)))
        if word not in seen:
            seen.add(word)
            out.append(word)
    return out


LADDER = [10_000, 20_000, 40_000, 80_000]
terms = {n: make_terms(n) for n in LADDER}
print("سه عبارتِ اول:", terms[10_000][:3])
print("پیشوندِ سه‌حرفیِ ممکن:", len(LETTERS) ** PREFIX)
```

```text
سه عبارتِ اول: ['babjabbfd', 'aafjhj', 'cbcbaihdb']
پیشوندِ سه‌حرفیِ ممکن: 1000
```

<div dir="rtl">

**الفبا عمداً ده حرف است، نه بیست و شش:** با ده حرف تعدادِ پیشوندهای ممکن هزار تاست و هر پیشوند `bucket`ِ پُری دارد. با بیست و شش حرف بیشترِ `bucket`ها یک‌نفره می‌شدند و هیچ‌کدام از جدول‌های این فصل چیزی نشان نمی‌داد.

## ۲. دو نامزد، یک جواب

</div>

```python
def by_scan(items, prefix):
    """نامزد ۱ — هیچ ساختی، همهٔ عبارت‌ها را در هر پرسش ببین."""
    hits = []
    for term in items:
        if term.startswith(prefix):
            hits.append(term)
    return hits


def build_index(items):
    """نامزد ۲ — یک بار بساز: پیشوند به فهرستِ عبارت‌ها."""
    index = {}
    for term in items:
        index.setdefault(term[:PREFIX], []).append(term)
    return index


index = {n: build_index(terms[n]) for n in LADDER}
picker = random.Random(SEED)
asks = {n: [t[:PREFIX] for t in picker.sample(terms[n], 200)] for n in LADDER}
print("جوابِ دو نامزد در هر چهار اندازه یکی است؟",
      all(by_scan(terms[n], p) == index[n].get(p, []) for n in LADDER for p in asks[n]))
print("نمونه — تعدادِ عبارت با پیشوندِ", asks[80_000][0], ":",
      len(index[80_000][asks[80_000][0]]))
```

```text
جوابِ دو نامزد در هر چهار اندازه یکی است؟ True
نمونه — تعدادِ عبارت با پیشوندِ eji : 73
```

<div dir="rtl">

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

## ۳. جدولِ زمانِ پرسش

> 🤔 **اول حدس بزن:** ستونِ نسبتِ هر دو نامزد را بنویس. **برای پیمایش راحت است؛ برای `index` دقت کن** — `bucket`ها با `n` بزرگ‌تر می‌شوند، پس آیا زمانِ پرسش هم بزرگ‌تر می‌شود؟

</div>

```python
print("— ۲۰۰ پرسش با پیمایشِ کامل")
table([(n, 1000 * clock(lambda k=n: [by_scan(terms[k], p) for p in asks[k]], repeat=2))
       for n in LADDER], "زمان (ms)", ",.1f")
print("\n— ۲۰۰ پرسش با index")
table([(n, 1000 * clock(lambda k=n: [index[k].get(p, []) for p in asks[k]], repeat=3))
       for n in LADDER], "زمان (ms)", ",.4f")
```

```text-approx
— ۲۰۰ پرسش با پیمایشِ کامل
         n         زمان (ms)     نسبت به سطر قبل
    10,000              46.2                   —
    20,000              90.9                1.97
    40,000             181.5                2.00
    80,000             400.3                2.21

— ۲۰۰ پرسش با index
         n         زمان (ms)     نسبت به سطر قبل
    10,000            0.0131                   —
    20,000            0.0139                1.06
    40,000            0.0141                1.01
    80,000            0.0136                0.96
```

<div dir="rtl">

**`2.0` در برابرِ `1.0`: `O(n)` در برابرِ `O(1)`.** جوابِ `index` همان `bucket`ِ آماده را برمی‌گرداند و به بزرگی‌اش کاری ندارد، چون فهرست را نمی‌سازد — همان فهرست را که یک بار ساخته شده، تحویل می‌دهد.

در `n = 80,000` این یعنی `400.3` میلی‌ثانیه در برابرِ `0.0136` — روی این ماشین بیش از **بیست‌وپنج هزار برابر**. **و این نسبت با `n` بزرگ‌تر هم می‌شود**، چون ستونِ چپ رشد می‌کند و ستونِ راست نه.

**تا اینجا هیچ دلیلی برای انتخابِ پیمایش وجود ندارد.** حالا ستونی را اضافه می‌کنیم که در جدولِ زمان نیست.

## ۴. قیمت، به بایت

</div>

```python
def index_bytes(box):
    """خودِ dict، به‌علاوهٔ bucketهایش. رشته‌ها شمرده نمی‌شوند — چرا، پایین‌تر."""
    return sys.getsizeof(box) + sum(sys.getsizeof(v) for v in box.values())


print(f"{'n':>10}{'بایتِ index':>16}{'نسبت':>10}{'بایتِ هر عبارتِ اضافه':>24}")
last_n = last_b = None
for n in LADDER:
    size = index_bytes(index[n])
    ratio = "—" if last_b is None else f"{size / last_b:.2f}"
    marginal = "—" if last_b is None else f"{(size - last_b) / (n - last_n):.2f}"
    print(f"{n:>10,}{size:>16,}{ratio:>10}{marginal:>24}")
    last_n, last_b = n, size
```

```text
         n     بایتِ index      نسبت   بایتِ هر عبارتِ اضافه
    10,000         188,784         —                       —
    20,000         270,064      1.43                    8.13
    40,000         440,464      1.63                    8.52
    80,000         779,888      1.77                    8.49
```

<div dir="rtl">

**ستونِ نسبت `1.43` است، بعد `1.63`، بعد `1.77` — به `2` نزدیک می‌شود ولی هیچ‌وقت نمی‌رسد.** دلیلش همان ثابتِ ترمِ ۱ فصلِ ۷ است، این بار روی حافظه: خودِ `dict` هزار کلید دارد و اندازه‌اش با `n` عوض نمی‌شود، و هر `bucket` هم یک سربارِ ثابت دارد. **مرتبهٔ حافظه `O(n)` به‌علاوهٔ یک ثابت است، و در این بازه ثابت هنوز دیده می‌شود.**

**ستونِ آخر تمیزتر از ستونِ نسبت حرف می‌زند:** `8.13`، `8.52`، `8.49`. هر عبارتِ اضافه حدودِ **هشت و نیم بایت** به `index` اضافه می‌کند و بس.

> 🌱 **ریشه‌اش کجاست:** ستونِ آخر یک **نرخ** است، و نرخ همیشه یک «به‌ازای هر چه؟» دارد — اینجا «به‌ازای هر عبارتِ اضافه». ساختنِ همین جمله و ثابت کردنِ یک طرفِ کسر برای اینکه دو چیزِ نابرابر قابلِ مقایسه شوند، در [ریشه ترمِ ۲ فصل ۸](/courses/risheh/lessons/term-2-fractions/session-08-rate-unit) ساخته می‌شود. **بدونِ آن «به‌ازای هر چه؟»، عددِ ۷۷۹٬۸۸۸ فقط بزرگ است — نه گران، نه ارزان.**

</div>

```python
big = index[80_000]
print("خودِ dict (هزار کلید)      :", f"{sys.getsizeof(big):>10,} بایت")
print("مجموعِ bucketها             :",
      f"{sum(sys.getsizeof(v) for v in big.values()):>10,} بایت")
print("فهرستِ اصلیِ عبارت‌ها        :", f"{sys.getsizeof(terms[80_000]):>10,} بایت")
print("مجموعِ خودِ رشته‌ها          :",
      f"{sum(sys.getsizeof(t) for t in terms[80_000]):>10,} بایت")
```

```text
خودِ dict (هزار کلید)      :     26,032 بایت
مجموعِ bucketها             :    753,856 بایت
فهرستِ اصلیِ عبارت‌ها        :    711,960 بایت
مجموعِ خودِ رشته‌ها          :  3,920,365 بایت
```

<div dir="rtl">

**رشته‌ها در حسابِ `index` نیامدند و این عمدی است:** `bucket`ها **همان اشیاء** را ارجاع می‌دهند که فهرستِ اصلی دارد، نه کپی‌شان. پس `index` سه مگابایتِ رشته را دوباره نمی‌خرد؛ فقط هشتاد هزار ارجاعِ تازه می‌سازد — و هشت بایتِ هر ارجاع دقیقاً همان `8.49`ِ ستونِ قبل است.

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

## ۵. نرخِ معامله: «به‌ازای هر چه؟»

سؤالِ «۷۸۰ کیلوبایت ارزشش را دارد؟» جواب ندارد. **سؤالی که جواب دارد این است: به‌ازای چند پرسش؟**

</div>

```python
n = 80_000
per_scan = clock(lambda: [by_scan(terms[n], p) for p in asks[n]], repeat=2) / 200
per_index = clock(lambda: [index[n].get(p, []) for p in asks[n]], repeat=3) / 200
saved = per_scan - per_index
cost = index_bytes(index[n])
print(f"n = {n:,} · صرفه‌جویی در هر پرسش: {1000 * saved:.3f} ms"
      f" · قیمتِ ثابت: {cost:,} بایت\n")
print(f"{'تعدادِ پرسش (q)':>18}{'کلِ صرفه‌جویی (ms)':>22}{'بایت به‌ازای هر ms':>22}")
for q in (1, 100, 10_000, 1_000_000):
    print(f"{q:>18,}{q * saved * 1000:>22,.1f}{cost / (q * saved * 1000):>22,.2f}")
```

```text-approx
n = 80,000 · صرفه‌جویی در هر پرسش: 1.811 ms · قیمتِ ثابت: 779,888 بایت

   تعدادِ پرسش (q)    کلِ صرفه‌جویی (ms)    بایت به‌ازای هر ms
                 1                   1.8            430,548.13
               100                 181.1              4,305.48
            10,000              18,113.8                 43.05
         1,000,000           1,811,384.0                  0.43
```

<div dir="rtl">

**همان ۷۸۰ کیلوبایت، و نرخ در چهار سطر شش مرتبه عوض می‌شود.**

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

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** دو نامزد برای یک پرسش، روی یک فهرستِ یکسان و همان دویست پیشوندِ ثابت، با جوابِ برابرِ تأییدشده. **در کدام بازهٔ `n`؟** ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ عبارت، با الفبای ده‌حرفی و پیشوندِ سه‌حرفی. **با چند تکرار، و کمینه یا میانگین؟** دو تا سه تکرار به‌علاوهٔ گرم‌کننده، کمینه؛ جدولِ حافظه یک اجرا و قطعی.

## ۶. وقتی دیوار حافظه است

تا اینجا `index` برنده بود. حالا پرسش را کمی سخت‌تر می‌کنیم: **«چند عبارت هم با این سه حرف شروع می‌شود و هم به آن سه حرف ختم؟»**

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

</div>

```python
K = len(LETTERS) ** PREFIX


def code_of(part):
    value = 0
    for ch in part:
        value = value * 10 + (ord(ch) - 97)
    return value


def build_cross(items, k=K):
    """برای هر جفتِ (پیشوند، پسوند) یک خانه."""
    grid = [[0] * k for _ in range(k)]
    for term in items:
        grid[code_of(term[:PREFIX])][code_of(term[-PREFIX:])] += 1
    return grid


grid = build_cross(terms[80_000])
grid_bytes = sys.getsizeof(grid) + sum(sys.getsizeof(row) for row in grid)
print(f"جدولِ متقاطع {K}×{K} = {K * K:,} خانه")
print(f"  حافظه            : {grid_bytes:,} بایت")
print(f"  به‌ازای هر خانه   : {grid_bytes / (K * K):.2f} بایت")
for wider in (10_000, 100_000):
    need = grid_bytes / (K * K) * wider * wider
    print(f"  با {wider:>7,} پیشوند: {wider * wider:>15,} خانه ≈ "
          f"{need / 1024 ** 3:>6.1f} گیگابایت")
```

```text
جدولِ متقاطع 1000×1000 = 1,000,000 خانه
  حافظه            : 8,064,856 بایت
  به‌ازای هر خانه   : 8.06 بایت
  با  10,000 پیشوند:     100,000,000 خانه ≈    0.8 گیگابایت
  با 100,000 پیشوند:  10,000,000,000 خانه ≈   75.1 گیگابایت
```

<div dir="rtl">

**هزار پیشوند: هشت مگابایت، ساخته شد. صد هزار پیشوند: هفتاد و پنج گیگابایت، ساخته نمی‌شود.**

و دقت کن که **هیچ‌کدام از این عددها به `n` ربطی ندارند.** جدولِ متقاطع به تعدادِ **پیشوندهای ممکن** بند است، نه به تعدادِ عبارت‌ها؛ با هزار عبارت هم همین هشت مگابایت را می‌گیرد. **مرتبه‌اش `O(K²)` است و `K` جایی در صورتِ مسئله پنهان شده که کسی نگاهش نمی‌کند: طولِ پیشوند.** یک حرف بیشتر یعنی `K` ده برابر و حافظه صد برابر.

**پس اینجا زمان اصلاً موضوع نیست.** برای این پرسشِ تازه دو نامزد داشتیم: جدولِ متقاطعِ کامل، و پیمایشِ کامل. اولی سریع‌ترین جوابِ ممکن را می‌دهد و در `K`های بزرگ **اصلاً ساخته نمی‌شود** — نه چون کند است، چون در حافظه جا نمی‌شود. دومی — همان نامزدی که در بخشِ ۳ بیست‌وپنج هزار برابر عقب بود — **به `K` هیچ کاری ندارد، چون هیچ چیزی نگه نمی‌دارد.** و نامزدی که وجود نداشته باشد، سرعتش موضوعیت ندارد.

> ⚠️ **مواظب باش:** در Colab وقتی از سقفِ حافظه رد می‌شوی معمولاً `MemoryError` نمی‌گیری؛ **نشست بدونِ هیچ پیامی ری‌استارت می‌شود و همهٔ متغیرهایت می‌روند.** پس قبل از ساختنِ هر ساختارِ بزرگی، مثلِ همین بخش، اول با یک ضرب و تقسیم حجمش را حساب کن. **عددی که با کاغذ حساب شده، جای نشستی را که از دست می‌رود نمی‌گیرد — ولی جلوی از دست رفتنش را می‌گیرد.**

> ✅ **چک کن:** خطِ `PREFIX = 2` را بالای همین سلولِ آخر بگذار و دوباره اجرایش کن. **`K` باید صد شود و حافظهٔ جدولِ متقاطع حدودِ صد برابر کمتر.** اگر فقط ده برابر کم شد، `K` را جایی به‌صورتِ عددِ ثابت نوشته‌ای، نه از روی `PREFIX`.

> 🔧 **اگر کار نکرد:** `index` برای پیشوندی که هیچ عبارتی ندارد **کلید ندارد**، و این تفاوتِ `[]` با خطا دادن است:

</div>

```python
try:
    index[10_000]["zzz"]
except KeyError as err:
    print(f"{type(err).__name__}: {err}")
print("با get:", index[10_000].get("zzz", []))
```

```text
KeyError: 'zzz'
با get: []
```

<div dir="rtl">

**پیمایشِ کامل چنین مشکلی ندارد** — فهرستِ خالی برمی‌گرداند و تمام. **این هم بخشی از قیمتِ `index` است و در هیچ جدولی دیده نمی‌شود:** هر ساختارِ پیش‌ساخته یک حالتِ «نداریم» دارد که باید صریح مدیریتش کنی، وگرنه یک پرسشِ بی‌جواب برنامه را می‌شکند.

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

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| space-time trade-off | اسپیس-تایم تِرِیداف | خریدنِ زمانِ کمتر با حافظهٔ بیشتر، یا برعکس |
| precomputation | پری‌کامپیوتیشن | حساب کردنِ جواب پیش از پرسیده شدنش |
| marginal cost | مارجینال کاست | هزینه‌ای که یک عضوِ اضافه می‌آورد، نه کلِ هزینه |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا مجموعِ خودِ رشته‌ها در حسابِ حافظهٔ `index` نیامد؟

**تمرینِ اجباری:** یک نامزدِ سوم بساز که به‌جای فهرستِ عبارت‌ها فقط **تعدادشان** را نگه دارد. **قبل از اجرا پیش‌بینی کن** حافظه‌اش چند برابرِ `index` است و ستونِ نسبتِ جدولِ رشدش چه عددی می‌دهد، بعد هر دو را اندازه بگیر و خطای پیش‌بینی‌ات را بنویس. **سؤالِ اصلی: این نامزد چه پرسشی را از دست داد؟**

**تمرینِ ستاره‌دار ⭐:** جدولِ متقاطع را با `PREFIX = 4` بساز — **ولی اول با کاغذ حساب کن چند گیگابایت می‌شود و اگر از حافظهٔ نشستت بیشتر بود، نسازش.** بعد نسخهٔ کم‌حافظه‌اش را با `dict` بنویس که فقط جفت‌های **موجود** را نگه می‌دارد. **دو سؤال:** حافظه‌اش چقدر شد و چرا این‌قدر کمتر است، و **چه پرسشی هست که جدولِ کاملِ `K²` جواب می‌دهد و نسخهٔ `dict` نمی‌دهد؟**

## در فصل بعد

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

**فصلِ بعد این فرض را می‌شکند** و سه معیار می‌سازد که هر کدام به‌تنهایی می‌گویند «بس است» — یکی‌شان همان چیزی است که ترمِ ۱ فصلِ ۳ ساخت و از همان‌جا وعده‌اش داده شده بود. **و بدترین حالتش را هم نشان می‌دهد:** نسخه‌ای که سریع‌تر است، هیچ خطایی نمی‌دهد، و جوابِ غلط برمی‌گرداند.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t6/s03-space-time (یادستان, Yaadestan)
