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

فصل ۴ از ۹

پیشرفت ترم
۰٪

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

سه فصل دربارهٔ انتهای ظرف حرف زدیم. این فصل به ابتدای ظرف نگاه می‌کند و همه‌چیز عوض می‌شود.

دو جدولِ دوبرابری می‌گیریم: یکی برای append و یکی برای insert(0, x). ستونِ اولی نزدیکِ 2 است و دومی نزدیکِ 4. همان کار، همان تعداد عضو، فقط سرِ دیگرِ ظرف. بعد ظرفِ دیگری معرفی می‌شود که هزینهٔ ابتدای ظرف را دوباره صاف می‌کند — و آن هم با جدول ثابت می‌شود.

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

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

  • بگویی چرا insert(0, x) و pop(0) هزینهٔ O(n) دارند و append و pop() ندارند
  • هزینهٔ درج و حذف را بر حسبِ محلش در ظرف گزارش کنی
  • با collections.deque هزینهٔ ابتدای ظرف را صاف کنی و با جدول ثابتش کنی

قبل از شروع#

از فصلِ ۱: خانه‌های پیوسته و هم‌اندازه. از فصلِ ۳: append هزینهٔ O(1)ِ amortised دارد.

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

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

۱. چرا ابتدای ظرف فرق دارد#

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

در انتها هیچ‌کدام از این‌ها لازم نیست: خانهٔ خالیِ بعدی همان‌جاست و هیچ اندیسی عوض نمی‌شود.

این را می‌شود بدونِ ساعت شمرد. دو تابع می‌نویسیم که کارِ نوشتن در خانه‌ها را دستی انجام می‌دهند و می‌شمارند.

🤔 اول حدس بزن: ستونِ نسبت برای هرکدام چه عددی می‌دهد؟

def writes_append(n):
    """n بار در انتها: هر بار فقط یک خانه نوشته می‌شود."""
    slots = []
    written = 0
    for i in range(n):
        slots.append(None)
        slots[len(slots) - 1] = i
        written += 1
    return written


def writes_insert_front(n):
    """n بار در ابتدا: هر بار همهٔ خانه‌های قبلی یکی به جلو می‌روند."""
    slots = []
    written = 0
    for i in range(n):
        slots.append(None)
        for j in range(len(slots) - 1, 0, -1):
            slots[j] = slots[j - 1]
            written += 1
        slots[0] = i
        written += 1
    return written


LADDER = [1_000, 2_000, 4_000, 8_000]
print("— نوشتن در انتها")
table([(n, writes_append(n)) for n in LADDER], "نوشتن در خانه", ",d")
print("\n— نوشتن در ابتدا")
table([(n, writes_insert_front(n)) for n in LADDER], "نوشتن در خانه", ",d")
print("\nراستی‌آزماییِ فرمول در n = 4000:  n =", 4_000,
      "·  n(n+1)/2 =", 4_000 * 4_001 // 2)
— نوشتن در انتها
         n     نوشتن در خانه     نسبت به سطر قبل
     1,000             1,000                   —
     2,000             2,000                2.00
     4,000             4,000                2.00
     8,000             8,000                2.00

— نوشتن در ابتدا
         n     نوشتن در خانه     نسبت به سطر قبل
     1,000           500,500                   —
     2,000         2,001,000                4.00
     4,000         8,002,000                4.00
     8,000        32,004,000                4.00

راستی‌آزماییِ فرمول در n = 4000:  n = 4000 ·  n(n+1)/2 = 8002000

2.00 در برابرِ 4.00، بدونِ یک ذره نویز. و فرمولِ سطرِ آخر دقیقاً همان عددِ ستونِ دومِ جدولِ پایینی است: 1 + 2 + 3 + … + n.

۲. حالا با ساعت#

شمارش می‌گوید O(n) در برابرِ O(n²). ساعت هم باید همین را بگوید — این بار روی متدهای واقعیِ خودِ پایتون.

def build_append(n):
    out = []
    for i in range(n):
        out.append(i)
    return out


def build_insert_front(n):
    out = []
    for i in range(n):
        out.insert(0, i)
    return out


TIMED = [10_000, 20_000, 40_000, 80_000]
print("جوابِ دو نسخه یکی است؟",
      build_append(500) == list(reversed(build_insert_front(500))))
print("\n— list.append(x)")
table([(n, 1000 * clock(lambda k=n: build_append(k), repeat=2)) for n in TIMED],
      "زمان (ms)", ",.2f")
print("\n— list.insert(0, x)")
table([(n, 1000 * clock(lambda k=n: build_insert_front(k), repeat=2)) for n in TIMED],
      "زمان (ms)", ",.2f")
جوابِ دو نسخه یکی است؟ True

— list.append(x)
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.26                   —
    20,000              0.49                1.91
    40,000              1.14                2.34
    80,000              2.24                1.96

— list.insert(0, x)
         n         زمان (ms)     نسبت به سطر قبل
    10,000             22.90                   —
    20,000             90.43                3.95
    40,000            357.84                3.96
    80,000          1,447.42                4.04

ستونِ نسبتِ append نزدیکِ 2 و ستونِ نسبتِ insert(0, x) نزدیکِ 4. ساعت و شمارنده یک چیز می‌گویند.

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

۳. همان داستان، برای حذف#

pop() عضوِ آخر را برمی‌دارد و pop(0) عضوِ اول را. از بیرون شبیهِ هم‌اند و از نظرِ هزینه دو دنیای متفاوت‌اند، دقیقاً به همان دلیل: برداشتنِ عضوِ اول یعنی همهٔ بقیه یک خانه عقب بروند.

🤔 اول حدس بزن: pop() و pop(0) هر دو یک عضو برمی‌دارند. بنویس ستونِ نسبتِ هر کدام چه عددی می‌دهد — و اگر فکر می‌کنی یکی‌اند، همان را بنویس.

def drain_back(values):
    while values:
        values.pop()


def drain_front(values):
    while values:
        values.pop(0)


DRAIN = [5_000, 10_000, 20_000, 40_000]
print("— pop()")
table([(n, 1000 * clock(lambda k=n: drain_back(list(range(k))), repeat=2))
       for n in DRAIN], "زمان (ms)", ",.2f")
print("\n— pop(0)")
table([(n, 1000 * clock(lambda k=n: drain_front(list(range(k))), repeat=2))
       for n in DRAIN], "زمان (ms)", ",.2f")
— pop()
         n         زمان (ms)     نسبت به سطر قبل
     5,000              0.16                   —
    10,000              0.33                2.00
    20,000              0.65                1.99
    40,000              1.39                2.13

— pop(0)
         n         زمان (ms)     نسبت به سطر قبل
     5,000              1.12                   —
    10,000              4.77                4.25
    20,000             19.17                4.02
    40,000             91.04                4.75

باز هم 2 در برابرِ 4.

⚠️ مواظب باش: هزینهٔ درج و حذف در یک list به محلش بند است، نه به خودِ عمل. insert(len(values), x) دقیقاً به‌ارزانیِ append است و insert(0, x) گران‌ترین حالتِ ممکن. درج در وسط هم نصفِ گران است — چون فقط نیمهٔ دوم جابه‌جا می‌شود. یک قاعدهٔ ساده: هزینه به‌اندازهٔ تعدادِ عضوهایی است که بعد از محلِ درج قرار دارند.

✅ چک کن: در build_insert_front عددِ 0 را به len(out) تغییر بده و دوباره بگیر. ستونِ نسبت باید از 4 به 2 بیفتد — همان تابع، همان متد، فقط محلِ درج عوض شده. اگر عوض نشد، احتمالاً هنوز 0 را جایی جا گذاشته‌ای؛ print(len(out)) را داخلِ حلقه بگذار و ببین اندیسی که به insert می‌دهی واقعاً با طولِ فعلی جلو می‌رود یا نه.

۴. ظرفی که هر دو سر را ارزان می‌کند#

اگر مسئله‌ات واقعاً ابتدای ظرف است، راهش این نیست که insert(0, x) را سریع‌تر بنویسی؛ راهش این است که ظرفِ دیگری برداری.

collections.deque دقیقاً برای همین ساخته شده: در هر دو سرش درج و حذفِ ارزان دارد. فعلاً همین‌قدر بدان که ساختنش با list فرق دارد؛ فصلِ ۷ کاملاً بازش می‌کند و همان‌جا نشان می‌دهد چه چیزی را در ازایش می‌دهد.

🤔 اول حدس بزن: deque ادعا می‌کند در هر دو سر ارزان است. ستونِ نسبتش را حدس بزن، و بنویس در n = 80,000 چند برابر از list.insert(0, x) جلو می‌زند.

ولی هیچ کدام از این‌ها ادعا نیست تا وقتی جدولش را نگرفته باشیم:

from collections import deque


def build_appendleft(n):
    out = deque()
    for i in range(n):
        out.appendleft(i)
    return out


def drain_popleft(values):
    while values:
        values.popleft()


print("همان ترتیبِ نهایی؟", list(build_appendleft(500)) == build_insert_front(500))
print("\n— deque.appendleft(x)")
table([(n, 1000 * clock(lambda k=n: build_appendleft(k), repeat=3)) for n in TIMED],
      "زمان (ms)", ",.2f")
print("\n— deque.popleft()")
table([(n, 1000 * clock(lambda k=n: drain_popleft(deque(range(k))), repeat=3))
       for n in DRAIN], "زمان (ms)", ",.2f")
همان ترتیبِ نهایی؟ True

— deque.appendleft(x)
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.48                   —
    20,000              0.62                1.28
    40,000              1.36                2.21
    80,000              2.88                2.12

— deque.popleft()
         n         زمان (ms)     نسبت به سطر قبل
     5,000              0.17                   —
    10,000              0.35                2.03
    20,000              0.73                2.09
    40,000              1.40                1.93

هر دو ستون نزدیکِ 2 — و سطرِ اول تأیید می‌کند که خروجی هم دقیقاً همان است. یعنی deque همان کار را می‌کند و مرتبه‌اش خطی است، نه درجه‌دو.

۵. سه ظرف، یک عمل، یک جدول#

آخرین اندازه‌گیریِ فصل: همان n، همان کار، سه راه.

N = 40_000
rows = (
    ("list.append", lambda: build_append(N)),
    ("list.insert(0, x)", lambda: build_insert_front(N)),
    ("deque.appendleft", lambda: build_appendleft(N)),
)
best = None
print(f"n = {N:,}\n")
print(f"{'روش':>20}{'زمان (ms)':>14}{'نسبت به بهترین':>18}")
results = [(name, 1000 * clock(fn, repeat=2)) for name, fn in rows]
best = min(t for _, t in results)
for name, t in results:
    print(f"{name:>20}{t:>14.2f}{t / best:>18,.0f}")
n = 40,000

                 روش     زمان (ms)    نسبت به بهترین
         list.append          0.99                 1
   list.insert(0, x)        359.91               365
    deque.appendleft          1.30                 1

سه خط کدِ تقریباً یکسان، و یکی از آن‌ها صدها برابر گران‌تر.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ سه راهِ ساختنِ یک دنبالهٔ nتایی، با خروجیِ برابرِ تأییدشده. در کدام بازهٔ n؟ جدول‌های رشد در ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ و جدولِ آخر در یک اندازهٔ ثابت، n = 40,000. با چند تکرار، و کمینه یا میانگین؟ دو یا سه تکرار به‌علاوهٔ گرم‌کننده، همیشه کمینه — و هر اجرا ظرفِ تازهٔ خودش را می‌سازد، چون این توابع ظرف را مصرف می‌کنند.

🔧 اگر کار نکرد: هر دو ظرف روی ظرفِ خالی خطا می‌دهند، ولی پیامشان یکی نیست و همین یک نویسه می‌گوید کدام ظرف را در دست داری:

for empty in ([], deque()):
    try:
        empty.pop()
    except IndexError as err:
        print(f"{type(err).__name__}: {err}")
IndexError: pop from empty list
IndexError: pop from an empty deque

اگر پیامِ دومی را گرفتی ولی فکر می‌کردی یک list داری، جایی در کدت ظرف عوض شده — و این از خواندنِ خودِ کد سخت‌تر پیدا می‌شود تا از خواندنِ پیامِ خطا.

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

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

کلمه تلفظ به حروف فارسی یعنی چه
shifting شیفتینگ جابه‌جا شدنِ همهٔ عضوهای بعد از محلِ درج یا حذف
deque دِک ظرفی که در هر دو سرش درج و حذفِ ارزان دارد

تمرین‌ها

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

در فصل بعد#

insert(0, x) یک تلهٔ آشکار است: اسمِ صریحی دارد و همین که ببینی‌اش می‌شود شک کرد.

فصلِ بعد دربارهٔ تله‌های نامرئی است. چهار تکه کد که هیچ‌کدام حلقهٔ تودرتوی آشکار ندارند و هر چهارتا می‌توانند O(n²) باشند. برای هر چهارتا جدول می‌گیریم — و یکی از آن‌ها بر خلافِ همهٔ کتاب‌ها خطی درمی‌آید — و آخرش یک قاعدهٔ تشخیص درمی‌آید که با آن می‌شود این تله را در کدِ خودت پیدا کرد، قبل از اینکه کاربر پیدایش کند.

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

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