بنیاد — ساختمان داده و الگوریتم، با اندازه‌گیری واقعی

فصل ۲ از ۹

پیشرفت ترم
۰٪

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

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

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

کشویی با یک ردیف خانهٔ هم‌اندازه که نیمی پر است و نیمی از پیش ساخته و خالی مانده

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

  • تفاوتِ طول و ظرفیت یک list را بگویی و هر دو را اندازه بگیری
  • با sys.getsizeof پله‌های رشدِ یک list را ببینی
  • بشماری یک list برای رسیدن به n عضو چند بار بزرگ می‌شود
  • نشان بدهی که هزینهٔ کپیِ کاملِ داده O(n) است

قبل از شروع#

از فصلِ ۱: خانه‌های پیوسته و هم‌اندازه، و اینکه دسترسی با اندیس به همین پیوستگی بند است.

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

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

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

۱. تناقضِ ظاهری#

آرایه یعنی نوارِ پیوستهٔ خانه‌ها. نوارِ پیوسته را نمی‌شود کش داد، چون درست بعد از آخرین خانه‌اش ممکن است چیزِ دیگری نشسته باشد.

پس append چطور کار می‌کند؟ راهش این است که ظرف از اول بزرگ‌تر از چیزی که لازم دارد ساخته شود. یک list دو عددِ متفاوت دارد:

  • طول (len) — چند خانه واقعاً پر است
  • ظرفیت — چند خانه اصلاً ساخته شده

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

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

۲. پله‌های getsizeof#

🤔 اول حدس بزن: یک list خالی می‌سازیم و هجده بار append می‌کنیم و قبل از هر بار sys.getsizeof می‌گیریم. بنویس انتظار داری آن عدد چند بار عوض شود: یک بار؟ هجده بار؟ چند بار؟

CELL = 8                               # هر خانه یک ارجاعِ هشت‌بایتی است
EMPTY = sys.getsizeof([])


def capacity(values):
    """چند خانه ساخته شده — از روی بایت‌های خودِ ظرف."""
    return (sys.getsizeof(values) - EMPTY) // CELL


print("بایت‌های یک list خالی:", EMPTY)
print(f"\n{'طول':>6}{'بایت':>10}{'ظرفیت':>10}")
values = []
previous = 0
for i in range(18):
    cap = capacity(values)
    mark = "بزرگ شد" if cap != previous else ""
    print(f"{len(values):>6}{sys.getsizeof(values):>10}{cap:>10}   {mark}".rstrip())
    previous = cap
    values.append(i)
بایت‌های یک list خالی: 56

   طول      بایت     ظرفیت
     0        56         0
     1        88         4   بزرگ شد
     2        88         4
     3        88         4
     4        88         4
     5       120         8   بزرگ شد
     6       120         8
     7       120         8
     8       120         8
     9       184        16   بزرگ شد
    10       184        16
    11       184        16
    12       184        16
    13       184        16
    14       184        16
    15       184        16
    16       184        16
    17       248        24   بزرگ شد

عدد فقط در چهار سطر عوض شد، نه در هجده سطر. ظرفیت 4، بعد 8، بعد 16، بعد 24 — و بینِ هر دو پله، append هیچ خانهٔ تازه‌ای نمی‌سازد.

به سطرِ طول = 1 دقت کن: ظرفیت 4 است. سه خانهٔ خالیِ آماده، همان لحظه. این همان «تخصیصِ اضافی» است و دلیلِ وجودش دقیقاً این است که سه append بعدی مجانی باشند.

✅ چک کن: capacity(list(range(100))) را بگیر. عدد باید دقیقاً 100 باشد، نه بیشتر — وقتی پایتون از اول می‌داند چند تا عضو هست، هیچ خانهٔ اضافه‌ای نمی‌سازد. حالا capacity(list(x for x in range(100))) را هم بگیر: این یکی بیشتر از صد است، چون تعدادِ نهایی از قبل معلوم نیست. تخصیصِ اضافی هزینهٔ ندانستن است، نه یک عادت.

۳. چند بار بزرگ می‌شود؟#

حالا سؤالِ اصلی: برای رسیدن به n عضو، ظرف چند بار بزرگ می‌شود؟

🤔 اول حدس بزن: ستونِ نسبتِ این جدول را حدس بزن. اگر برای رسیدن به هزار عضو مثلاً بیست بار بزرگ شود، برای دو هزار عضو چند بار؟

def growth_events(n):
    """چند بار ظرفیتِ یک list در مسیرِ رسیدن به n عضو عوض می‌شود."""
    values = []
    events = 0
    cap = capacity(values)
    for i in range(n):
        values.append(i)
        new = capacity(values)
        if new != cap:
            events += 1
            cap = new
    return events


table([(n, growth_events(n)) for n in SIZES], "بزرگ‌شدن", ",d")
print("\nتفاضلِ سطرها:", [growth_events(2 * n) - growth_events(n) for n in SIZES[:-1]])
         n          بزرگ‌شدن     نسبت به سطر قبل
     1,000                28                   —
     2,000                33                1.18
     4,000                39                1.18
     8,000                45                1.15

تفاضلِ سطرها: [5, 6, 6]

ستونِ نسبت نزدیکِ 1.15 است — نه 2. یعنی با دو برابر شدنِ n، تعدادِ بزرگ‌شدن‌ها دو برابر نمی‌شود.

و سطرِ آخر دقیق‌ترش می‌کند: هر بار که n دو برابر می‌شود، فقط شش بزرگ‌شدنِ تازه اضافه می‌شود. این همان امضایی است که در فصلِ ۵ ترمِ ۱ برای halve_down دیدی، فقط برعکس: آن‌جا هر دوبرابر شدنِ n یک قدم اضافه می‌کرد، این‌جا شش قدم. هر دو O(log n) هستند؛ فقط پایهٔ لگاریتمشان فرق دارد.

از همین‌جا می‌شود گفت ظرفیت چطور بزرگ می‌شود: اگر هر بار در عددِ ثابتِ f ضرب شود، برای رسیدن به n تعدادِ پله‌ها همان چیزی است که در آن ضرب می‌شود تا n شود. و شش پله برای دو برابر شدن یعنی f حدودِ 1.12 است، نه 2. فصلِ بعد این عدد را مستقیماً اندازه می‌گیرد.

۴. هر بزرگ‌شدن یک کپیِ کامل است#

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

خودِ این کپی را می‌شود جدا اندازه گرفت، چون list(values) دقیقاً همان کار را می‌کند: یک نوارِ تازه و یک انتقالِ کامل.

🤔 اول حدس بزن: ستونِ نسبتِ زمانِ list(values) با دو برابر شدنِ n چه عددی می‌شود؟

COPY = [500_000, 1_000_000, 2_000_000, 4_000_000]
big = {n: [None] * n for n in COPY}        # ظرفِ خالی، بدونِ هیچ عددی داخلش
print("طول و ظرفیت برابرند؟", all(len(big[n]) == capacity(big[n]) for n in COPY))
table([(n, 1000 * clock(lambda v=big[n]: list(v), repeat=7)) for n in COPY],
      "زمان کپی (ms)", ",.2f")
del big
طول و ظرفیت برابرند؟ True
         n     زمان کپی (ms)     نسبت به سطر قبل
   500,000              1.37                   —
 1,000,000              2.98                2.18
 2,000,000              5.85                1.96
 4,000,000             12.08                2.06

ستونِ نسبت نزدیکِ 2 است: کپی O(n) است.

پس هر بار که یک list بزرگ می‌شود، کاری به‌اندازهٔ طولِ فعلی‌اش انجام می‌دهد. و همین‌جا یک نگرانیِ کاملاً بجا پیش می‌آید: اگر append گاهی O(n) است، پس ساختنِ یک list nتایی با n بار append باید O(n²) باشد.

این استدلال ظاهراً بی‌عیب است و جوابش غلط است. فصلِ بعد کلاً دربارهٔ همین است.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ هزینهٔ ساختنِ یک کپیِ کامل از یک list، با خودش در چهار اندازه. در کدام بازهٔ n؟ ۵۰۰٬۰۰۰ تا ۴٬۰۰۰٬۰۰۰ — عمداً بزرگ، چون کپی در اندازه‌های کوچک زیرِ نویز گم می‌شود. با چند تکرار، و کمینه یا میانگین؟ هفت تکرار به‌علاوهٔ یک گرم‌کننده، کمینه.

۵. ظرفیت مالِ list است، نه مالِ همه#

tuple هم یک نوارِ پیوسته است، ولی هیچ خانهٔ اضافه‌ای ندارد — چون قرار نیست هیچ‌وقت بزرگ شود.

for n in (0, 1, 4, 100):
    t = tuple(range(n))
    lst = list(range(n))
    print(f"n={n:>4}   tuple {sys.getsizeof(t):>5} بایت   ·   list {sys.getsizeof(lst):>5} بایت")
n=   0   tuple    40 بایت   ·   list    56 بایت
n=   1   tuple    48 بایت   ·   list    72 بایت
n=   4   tuple    72 بایت   ·   list    88 بایت
n= 100   tuple   840 بایت   ·   list   856 بایت

tuple کوچک‌تر است و همیشه دقیقاً به‌اندازهٔ طولش. این تنها تفاوتِ list و tuple نیست ولی مهم‌ترینِ تفاوت‌هایشان از نظرِ حافظه است.

🔧 اگر کار نکرد: اگر روی چیزی append بزنی که آرایهٔ پویا نیست، پیام صریح است:

try:
    (1, 2, 3).append(4)
except AttributeError as err:
    print(f"{type(err).__name__}: {err}")
AttributeError: 'tuple' object has no attribute 'append'

و این خطا یک واقعیتِ حافظه را لو می‌دهد، نه یک تصمیمِ سلیقه‌ای. tuple متدِ append ندارد چون خانهٔ خالی ندارد که پرش کند؛ برای اضافه کردن باید کلِ نوار دوباره ساخته شود — که همان t + (4,) است و یک tuple تازه می‌دهد، نه همان یکی.

🤖 از دستیارت بپرس: «تفاوتِ طول و ظرفیت در یک آرایهٔ پویا چیست؟» بعد این را هم بپرس: «چرا پایتون وقتی list(range(17)) می‌سازد ظرفیتِ اضافه نمی‌گیرد ولی وقتی هفده بار append می‌کنی می‌گیرد؟» — جوابش این است که در حالتِ اول طولِ نهایی از قبل معلوم است، و اگر بتوانی همین را بگویی، فهمیده‌ای تخصیصِ اضافی هزینهٔ ندانستن است.

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

کلمه تلفظ به حروف فارسی یعنی چه
dynamic array داینامیک اَرِی آرایه‌ای که با پر شدن، نوارِ بزرگ‌تری می‌سازد و داده را منتقل می‌کند
capacity کپسیتی تعدادِ خانه‌های ساخته‌شده، چه پر باشند چه خالی
over-allocation اُوِرالوکیشن ساختنِ خانهٔ بیشتر از چیزی که همین حالا لازم است
reallocation ری‌الوکیشن ساختنِ نوارِ تازه و کپیِ کاملِ داده به آن

تمرین‌ها

اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.

در فصل بعد#

این فصل با یک تناقضِ حل‌نشده تمام شد: اگر بعضی از appendها یک کپیِ کاملِ O(n) هستند، چرا ساختنِ یک list بزرگ با append سریع است؟

فصلِ بعد جوابش را با دو اندازه‌گیری می‌دهد. اول تک‌تکِ چهارصد هزار append را جداگانه می‌سنجد و گران‌ترین‌هایشان را پیدا می‌کند — که هزاران برابر گران‌تر از بقیه‌اند و دقیقاً روی همان لحظه‌های بزرگ‌شدن افتاده‌اند. بعد نشان می‌دهد که میانگینِ همان‌ها صاف است. اسمِ این پدیده amortised است، و همان‌جا می‌بینی که اگر ظرفیت به‌جای ضرب‌شدن، هر بار مقدارِ ثابتی اضافه می‌شد، کلِ ماجرا O(n²) می‌شد.

به آخر این فصل رسیدی!

اگر ساختی و جواب داد، این دکمه مال توست.