# فصل ۰۱ — آرایه: چرا رفتن به خانهٔ هزارم گران‌تر از خانهٔ دوم نیست

<div dir="rtl">

# فصل ۰۱ — آرایه: چرا رفتن به خانهٔ هزارم گران‌تر از خانهٔ دوم نیست

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

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

بعد همان `list` را جور دیگری می‌خوانیم — همان تعداد خانه، فقط با ترتیبِ به‌هم‌ریخته — و **چند برابر کندتر می‌شود**. همان داده، همان تعداد دسترسی، همان ماشین. تفاوت فقط در این است که خانه‌های پشتِ‌سرِ هم کنارِ هم‌اند و خانه‌های تصادفی نیستند.

![برشی از یک ردیفِ طولانی خانه‌های هم‌اندازه که همه در یک نوار پیوسته کنارِ هم چیده شده‌اند](/lesson-assets/t2-s01-contiguous-memory/prompt/01-image-contiguous-cells.png)

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

- بگویی چرا `values[999_999]` به‌اندازهٔ `values[1]` طول می‌کشد
- آدرسِ خانهٔ `i` را با یک ضرب و یک جمع حساب کنی
- تفاوتِ «رفتن با اندیس» و «گشتن دنبالِ مقدار» را با عدد نشان بدهی
- نشان بدهی نزدیکیِ داده‌ها در حافظه یک هزینهٔ واقعیِ اندازه‌گیری‌شدنی است

## قبل از شروع

**از ترمِ ۱:** `clock` و `table` (فصل‌های ۲ و ۵)، ستونِ نسبت و خواندنِ مرتبه از رویش (فصلِ ۵)، و اینکه هر ادعا جدول می‌خواهد.

این ترم دربارهٔ **ظرف‌های ترتیبی** است: `list`، `deque`، `array`. اولین سؤالش هم ساده‌ترینشان است — **رسیدن به خانهٔ شمارهٔ `i` چقدر خرج دارد؟**

</div>

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

<div dir="rtl">

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

## ۱. سه خانه، در چهار اندازه

> 🤔 **اول حدس بزن:** یک `list` با `n` عضو داریم و می‌خواهیم مقدارِ یک خانه را بخوانیم. بنویس: خواندنِ خانهٔ آخر نسبت به خانهٔ اول چند برابر طول می‌کشد؟ و وقتی `n` دو برابر شود، این عدد چه می‌شود؟

</div>

```python
LADDER = [100_000, 200_000, 400_000, 800_000]
data = {n: list(range(n)) for n in LADDER}
TOUCH = 500_000


def touch(values, index):
    """TOUCH بار به همان خانه سر می‌زند و مقدارش را کنار می‌گذارد."""
    seen = None
    for _ in range(TOUCH):
        seen = values[index]
    return seen


for label, pick in (("خانهٔ اول", lambda n: 0),
                    ("خانهٔ وسط", lambda n: n // 2),
                    ("خانهٔ آخر", lambda n: n - 1)):
    print(f"— {label}")
    table([(n, 1000 * clock(lambda values=data[n], i=pick(n): touch(values, i), repeat=3))
           for n in LADDER])
    print()
```

```text-approx
— خانهٔ اول
         n         زمان (ms)     نسبت به سطر قبل
   100,000              10.4                   —
   200,000              10.4                1.00
   400,000              10.4                1.00
   800,000               9.9                0.95

— خانهٔ وسط
         n         زمان (ms)     نسبت به سطر قبل
   100,000               9.9                   —
   200,000               9.9                1.00
   400,000              10.0                1.02
   800,000               9.9                0.99

— خانهٔ آخر
         n         زمان (ms)     نسبت به سطر قبل
   100,000              10.3                   —
   200,000              10.6                1.02
   400,000              10.1                0.96
   800,000               9.9                0.98
```

<div dir="rtl">

**دوازده عدد، و همه‌شان تقریباً یکی.** ستونِ نسبت در هر سه جدول نزدیکِ `1.00` است، و از قاعدهٔ فصلِ ۵ ترمِ ۱ می‌دانیم این یعنی: **هزینه به `n` بستگی ندارد.** مرتبه‌اش `O(1)` است.

تفاوتِ کوچکِ بینِ سه جدول — کمتر از یک میلی‌ثانیه — **از پراکندگیِ خودِ اندازه‌گیری بزرگ‌تر نیست و نباید جدی گرفته شود**؛ در بزرگ‌ترین اندازه هر سه عددِ یکسان دادند. عددهای تو فرق می‌کنند؛ **ستونِ نسبت نباید فرق کند**.

## ۲. چرا؟ چون آدرس را حساب می‌کند، نمی‌گردد

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

</div>

```python
BASE = 1_000          # نوارِ خانه‌ها از این بایت شروع می‌شود
CELL = 8              # هر خانه هشت بایت است

print(f"{'اندیس':>10}{'حساب':>26}{'آدرس':>14}")
for i in (0, 1, 2, 999, 799_999):
    print(f"{i:>10,}{f'{BASE} + {i:,} × {CELL}':>26}{BASE + i * CELL:>14,}")
```

```text
     اندیس                      حساب          آدرس
         0              1000 + 0 × 8         1,000
         1              1000 + 1 × 8         1,008
         2              1000 + 2 × 8         1,016
       999            1000 + 999 × 8         8,992
   799,999        1000 + 799,999 × 8     6,400,992
```

<div dir="rtl">

**یک ضرب و یک جمع، برای هر پنج سطر.** برای `i = 2` همان‌قدر کار است که برای `i = 799,999`. **این تمامِ توضیحِ جدولِ بخشِ قبل است.**

و همین‌جا یک قاعدهٔ فرمول‌شده:

</div>

```text
address(i) = base + i * cell_size
```

<div dir="rtl">

- `base` — آدرسِ اولین خانه
- `i` — اندیس
- `cell_size` — اندازهٔ هر خانه بر حسبِ بایت، **که در یک آرایه برای همهٔ خانه‌ها یکسان است**

آن شرطِ آخر همان چیزی است که کلِ ماجرا را ممکن می‌کند. اگر خانه‌ها اندازه‌های متفاوتی داشتند، برای رسیدن به خانهٔ هزارم باید از نهصد و نود و نه خانهٔ قبلی رد می‌شدی — و آن‌وقت جدولِ بخشِ ۱ ستونِ نسبتِ `2.00` می‌داد، نه `1.00`.

> 💡 **نکته:** در `list` پایتون هر خانه خودِ مقدار را نگه نمی‌دارد، **یک ارجاع به مقدار** را نگه می‌دارد — و ارجاع‌ها هم‌اندازه‌اند. برای همین یک `list` می‌تواند هم‌زمان عدد و رشته و `list` دیگری داشته باشد و باز هم `values[i]` هزینهٔ ثابت بماند.

## ۳. رفتن با اندیس، در برابرِ گشتن دنبالِ مقدار

اندیس ارزان است. **ولی اگر اندیس را نداشته باشی و فقط مقدار را بدانی، داستان کاملاً عوض می‌شود.**

> 🤔 **اول حدس بزن:** `values.index(x)` مقدارِ `x` را در `list` پیدا می‌کند و اندیسش را برمی‌گرداند. بنویس ستونِ نسبتش با دو برابر شدنِ `n` چه عددی می‌شود.

</div>

```python
JUMPS = 200_000
SEARCHES = 20


def by_index(values, index):
    seen = None
    for _ in range(JUMPS):
        seen = values[index]
    return seen


def by_value(values, wanted):
    seen = None
    for _ in range(SEARCHES):
        seen = values.index(wanted)
    return seen


print("— رفتن با اندیس")
table([(n, 1e6 * clock(lambda v=data[n], i=n - 1: by_index(v, i), repeat=3) / JUMPS)
       for n in LADDER], "µs هر دسترسی", ",.4f")
print("\n— گشتن دنبالِ همان خانه")
table([(n, 1e6 * clock(lambda v=data[n], w=n - 1: by_value(v, w), repeat=3) / SEARCHES)
       for n in LADDER], "µs هر جست‌وجو", ",.1f")
```

```text-approx
— رفتن با اندیس
         n      µs هر دسترسی     نسبت به سطر قبل
   100,000            0.0196                   —
   200,000            0.0197                1.00
   400,000            0.0195                0.99
   800,000            0.0197                1.01

— گشتن دنبالِ همان خانه
         n     µs هر جست‌وجو     نسبت به سطر قبل
   100,000             749.2                   —
   200,000           1,470.0                1.96
   400,000           3,285.2                2.23
   800,000           6,550.0                1.99
```

<div dir="rtl">

**`1.00` در برابرِ `2.00`.** ستونِ چپ می‌گوید اندیس `O(1)` است و ستونِ راست می‌گوید جست‌وجو `O(n)`.

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

> ✅ **چک کن:** `w=n - 1` را به `w=0` تغییر بده و فقط جدولِ دوم را دوباره بگیر. **باید تقریباً صفر بشود و ستونِ نسبتش `1.00`**، چون `index` از ابتدا شروع می‌کند و بلافاصله جواب را پیدا می‌کند. اگر همچنان `2.00` دیدی، یعنی `w` را عوض نکرده‌ای — بدترین حالت و بهترین حالتِ همین یک تابع دو دنیای متفاوت‌اند.

## ۴. نزدیکی در حافظه یک هزینهٔ واقعی است

حالا آزمایشی که بیشترِ کتاب‌ها فقط توصیفش می‌کنند. **همان `list`، همان تعدادِ دسترسی، فقط ترتیب فرق می‌کند:** یک بار از اول تا آخر، یک بار با ترتیبِ به‌هم‌ریخته.

> 🤔 **اول حدس بزن:** تعدادِ دسترسی‌ها در هر دو حالت دقیقاً یکی است. بنویس نسبتِ زمانشان چقدر می‌شود: ۱؟ ۲؟ بیشتر؟

</div>

```python
BIG = 1_000_000
values = list(range(BIG))
rng = random.Random(SEED)
in_order = list(range(BIG))
shuffled = list(range(BIG))
rng.shuffle(shuffled)


def walk(order):
    total = 0
    for i in order:
        total += values[i]
    return total


print("دو نسخه یک جواب می‌دهند؟", walk(in_order) == walk(shuffled))
t_order = clock(lambda: walk(in_order), repeat=3)
t_shuffle = clock(lambda: walk(shuffled), repeat=3)
print(f"به‌ترتیب      : {1000 * t_order:8.1f} ms")
print(f"به‌هم‌ریخته    : {1000 * t_shuffle:8.1f} ms")
print(f"نسبت          : {t_shuffle / t_order:8.2f} برابر")
del values, in_order, shuffled          # حافظه را آزاد کن؛ اندازه‌گیریِ بعدی نباید زیرِ فشار باشد
```

```text-approx
دو نسخه یک جواب می‌دهند؟ True
به‌ترتیب      :     43.0 ms
به‌هم‌ریخته    :    266.7 ms
نسبت          :     6.20 برابر
```

<div dir="rtl">

**شش برابر، برای کاری که از نظرِ شمارشِ عملیات دقیقاً یکسان است.**

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

شمارندهٔ فصلِ ۴ ترمِ ۱ برای هر دو نسخه عددِ یکسانی می‌داد: یک میلیون خواندن. **و شمارنده اشتباه نمی‌کرد؛ فقط چیزی را نمی‌دید که ساعت می‌بیند.**

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

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

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک `list` ثابت، با یک میلیون خواندن، دو بار — یک بار به‌ترتیبِ اندیس و یک بار با ترتیبِ به‌هم‌ریختهٔ همان اندیس‌ها؛ جوابِ دو نسخه با `==` برابر تأیید شد. **در کدام بازهٔ `n`؟** فقط یک اندازه، `n = 1,000,000` — چون ادعای این آزمایش دربارهٔ رشد نیست، دربارهٔ **ترتیبِ دسترسی** است. **با چند تکرار، و کمینه یا میانگین؟** سه تکرار به‌علاوهٔ یک گرم‌کننده، همیشه کمینه.

## ۵. اعلام، پیش‌بینی، و خطا

جدولِ بخشِ ۱ می‌گوید هزینهٔ دسترسی با اندیس `O(1)` است. **حالا طبقِ پروتکلِ فصلِ ۸ ترمِ ۱، پیش‌بینی می‌کنیم و اجرا می‌کنیم.**

</div>

```python
TOLERANCE = 20.0                       # معیارِ پذیرش، پیش از اجرا نوشته شد
NEXT = 2 * LADDER[-1]

baseline = 1e6 * clock(lambda: touch(data[LADDER[-1]], LADDER[-1] - 1), repeat=5) / TOUCH
print(f"مرتبهٔ اعلام‌شده : O(1)")
print(f"اندازه‌گیریِ n = {LADDER[-1]:,}: {baseline:.4f} µs هر دسترسی")
print(f"معیارِ پذیرش     : خطای کمتر از {TOLERANCE:.0f} درصد")
print(f"پیش‌بینی n = {NEXT:,}   : {baseline:.4f} µs هر دسترسی (همان عدد)")

bigger = list(range(NEXT))
actual = 1e6 * clock(lambda: touch(bigger, NEXT - 1), repeat=5) / TOUCH
error = 100 * abs(baseline - actual) / actual
print(f"اندازه‌گیریِ واقعی : {actual:.4f} µs هر دسترسی")
print(f"خطای نسبی        : {error:.1f} درصد  →",
      "قبول" if error < TOLERANCE else "رد")
```

```text-approx
مرتبهٔ اعلام‌شده : O(1)
اندازه‌گیریِ n = 800,000: 0.0196 µs هر دسترسی
معیارِ پذیرش     : خطای کمتر از 20 درصد
پیش‌بینی n = 1,600,000   : 0.0196 µs هر دسترسی (همان عدد)
اندازه‌گیریِ واقعی : 0.0198 µs هر دسترسی
خطای نسبی        : 0.9 درصد  → قبول
```

<div dir="rtl">

**پیش‌بینیِ یک مرتبهٔ `O(1)` عجیب‌ترین پیش‌بینیِ ممکن است: «هیچ اتفاقی نمی‌افتد».** و دقیقاً همین است که آزمون‌پذیرش می‌کند — اگر عدد جابه‌جا می‌شد، ادعای `O(1)` رد می‌شد.

> 🔧 **اگر کار نکرد:** پرتکرارترین خطای این فصل وقتی است که اندیس را از روی `n` حساب کنی و یکی زیادی بگیری:

</div>

```python
try:
    print(data[100_000][100_000])
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
IndexError: list index out of range
```

<div dir="rtl">

اندیس‌ها از صفر شروع می‌شوند، پس آخرین خانهٔ یک `list` صدهزارتایی `99_999` است. **و دقت کن که این خطا فوری و صریح است** — ظرف می‌داند طولش چقدر است و بیرون از آن اصلاً نمی‌گردد. همین «می‌داند طولش چقدر است» خودش یک ویژگیِ آرایه است: `len` هم `O(1)` است، چون طول یک عددِ ذخیره‌شده است نه چیزی که هر بار شمرده شود.

> 🤖 **از دستیارت بپرس:** «چرا دسترسی با اندیس در یک آرایه هزینهٔ ثابت دارد؟» بعد این را هم بپرس: **«اگر خانه‌های یک ظرف اندازه‌های متفاوتی داشته باشند، دسترسی با اندیس چه مرتبه‌ای پیدا می‌کند؟»** — جوابش `O(n)` است، و اگر بتوانی بگویی چرا، فرمولِ `base + i × cell_size` را واقعاً فهمیده‌ای.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| array | اَرِی | ردیفی از خانه‌های هم‌اندازه که پشتِ سرِ هم در حافظه‌اند |
| contiguous memory | کانتیگیواس مموری | حافظه‌ای که خانه‌هایش بدونِ فاصله کنارِ هم‌اند |
| random access | رندم اکسس | رفتن مستقیم به خانهٔ شمارهٔ `i`، بدونِ رد شدن از خانه‌های قبلی |
| locality | لوکَلیتی | نزدیکیِ خانه‌هایی که پشتِ سرِ هم لازم می‌شوند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا `values[999_999]` گران‌تر از `values[1]` نیست، و چرا `values.index(x)` هست؟

**تمرینِ اجباری:** آزمایشِ بخشِ ۴ را روی سه اندازهٔ `BIG` تکرار کن: `100_000`، `1_000_000` و — اگر حافظه اجازه داد — `4_000_000`. برای هر کدام **نسبتِ به‌هم‌ریخته به به‌ترتیب** را بنویس. **سؤالِ اصلی: آیا این نسبت با بزرگ‌تر شدنِ `n` ثابت می‌ماند یا رشد می‌کند؟** جوابت را در یک جمله توضیح بده و بگو این عدد آیا اصلاً یک «مرتبهٔ رشد» هست یا نه.

**تمرینِ ستاره‌دار ⭐:** تابعی بنویس که یک `list` و یک گامِ `step` بگیرد و خانه‌ها را با فاصلهٔ `step` بخواند (`0`، `step`، `2*step`، …) تا به آخر برسد و **همیشه دقیقاً ده هزار خانه بخواند** — یعنی طولِ `list` را از روی `step` انتخاب کن. حالا برای `step` برابرِ `1`، `2`، `4`، `8`، `16`، `64` و `1024` زمان بگیر. **قبل از اجرا پیش‌بینی کن از کدام `step` به بعد زمان دیگر بدتر نمی‌شود** و بنویس چرا. بعد اجرا کن. **اگر پیش‌بینی‌ات غلط بود، بنویس چه چیزی را دربارهٔ نحوهٔ آوردنِ همسایه‌ها جا انداخته بودی.**

## در فصل بعد

این فصل گفت خانه‌ها پشتِ سرِ هم‌اند و تعدادشان ثابت است. **ولی `list` پایتون `append` هم دارد** — یعنی تعدادِ خانه‌ها ثابت نیست. این دو حرف چطور با هم می‌سازند؟

فصلِ بعد جوابش را با یک ابزار می‌دهد که مستقیماً به حافظه نگاه می‌کند: `sys.getsizeof`. می‌بینی که یک `list` **بیشتر از طولش خانه دارد**، که این خانه‌های اضافی پله‌پله زیاد می‌شوند، و اینکه هر پله یک **کپیِ کاملِ داده** است. آخرِ فصل عددی می‌بینی که تا آن لحظه انتظارش را نداری: برای رسیدن به هشت هزار عضو، ظرف دقیقاً ۴۵ بار بزرگ می‌شود.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t2/s01-contiguous-memory (یادستان, Yaadestan)
