آرایه: چرا رفتن به خانهٔ هزارم گران‌تر از خانهٔ دوم نیست

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

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

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

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

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

قبل از شروع#

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

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

📓 نوت‌بوک: نوت‌بوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

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

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

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()

— خانهٔ اول
         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

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

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

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

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

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,}")

     اندیس                      حساب          آدرس
         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

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

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

address(i) = base + i * cell_size

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

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

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

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

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

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

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")

— رفتن با اندیس
         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

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

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

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

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

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

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

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          # حافظه را آزاد کن؛ اندازه‌گیریِ بعدی نباید زیرِ فشار باشد

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

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

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

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

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

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

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

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

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

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 "رد")

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

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

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

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

IndexError: list index out of range

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

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

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

در فصل بعد#

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

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