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

فصل ۷ از ۹

پیشرفت ترم
۰٪

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

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

stack آخرین ورودی را اول برمی‌دارد و queue اولین ورودی را اول. همان داده، همان ظرف، فقط قاعدهٔ برداشتن فرق می‌کند — و همین یک تفاوت باعث می‌شود یکی از این دو با list عالی کار کند و دیگری با list یک فاجعهٔ درجه‌دو باشد. در n = 80,000 فاصله‌شان چند ده برابر است.

دیسپنسرِ فنری که فقط بشقابِ رویی را می‌دهد، کنارِ ریلی که بشقابِ اولی را

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

  • LIFO و FIFO را روی یک مثالِ هشت‌تایی با دست دنبال کنی
  • یک stack با list بسازی و یک queue با deque
  • با عدد بگویی چرا queue با list ساخته نمی‌شود

قبل از شروع#

از فصلِ ۴: pop() در برابرِ pop(0)، و اینکه deque هر دو سر را ارزان می‌کند.

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

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

۱. دو انضباط، با دست#

stack و queue ساختارِ داده نیستند؛ انضباط‌اند — قاعده‌هایی دربارهٔ اینکه اجازه داری از کجا اضافه کنی و از کجا برداری.

  • stack — اضافه در انتها، برداشتن از انتها. آخرین چیزی که گذاشتی، اولین چیزی است که برمی‌داری: LIFO.
  • queue — اضافه در انتها، برداشتن از ابتدا. اولین چیزی که گذاشتی، اولین چیزی است که برمی‌داری: FIFO.

هشت حرف را از هر دو رد می‌کنیم و ترتیبِ خروج را نگاه می‌کنیم.

from collections import deque

letters = ["a", "b", "c", "d", "e", "f", "g", "h"]

stack = []
out_stack = []
for x in letters:
    stack.append(x)
while stack:
    out_stack.append(stack.pop())

queue = deque()
out_queue = []
for x in letters:
    queue.append(x)
while queue:
    out_queue.append(queue.popleft())

print("ورودی       :", " ".join(letters))
print("stack (LIFO):", " ".join(out_stack))
print("queue (FIFO):", " ".join(out_queue))
ورودی       : a b c d e f g h
stack (LIFO): h g f e d c b a
queue (FIFO): a b c d e f g h

stack ترتیب را برعکس می‌کند و queue نگهش می‌دارد. این تمامِ تفاوتشان است و همین تفاوت تعیین می‌کند کدامشان به کدام کار می‌خورد: stack وقتی خوب است که «آخرین کارِ نیمه‌تمام» را می‌خواهی و queue وقتی که «قدیمی‌ترین کارِ منتظر» را.

۲. stack با list#

stack با list هیچ مشکلی ندارد، چون هر دو عملیاتش در انتهاست: append و pop(). و هر دو را در فصل‌های ۳ و ۴ اندازه گرفتیم.

🤔 اول حدس بزن: ستونِ نسبتِ «n بار push و بعد n بار pop» چه عددی می‌دهد؟

def run_stack(n):
    st = []
    for i in range(n):
        st.append(i)
    total = 0
    while st:
        total += st.pop()
    return total


STACK = [100_000, 200_000, 400_000, 800_000]
print("جوابِ درست است؟", run_stack(1_000) == sum(range(1_000)))
table([(n, 1000 * clock(lambda k=n: run_stack(k), repeat=3)) for n in STACK])
جوابِ درست است؟ True
         n         زمان (ms)     نسبت به سطر قبل
   100,000               7.3                   —
   200,000              16.8                2.32
   400,000              32.7                1.94
   800,000              68.0                2.08

نسبتِ 2: کلِ 2n عملیات روی هم O(n) است، یعنی هر عمل به‌طورِ amortised ثابت. برای stack، list ظرفِ درست است و لازم نیست دنبالِ چیزِ دیگری بگردی.

۳. یک کاربردِ واقعیِ stack#

قبل از رفتن سراغِ queue، یک نمونهٔ کوتاه که نشان می‌دهد stack چرا اصلاً وجود دارد: بررسیِ اینکه پرانتزها درست بسته شده‌اند یا نه.

def balanced(text):
    """آیا هر پرانتزِ باز، با همان نوعِ خودش و به ترتیبِ درست بسته شده؟"""
    pairs = {")": "(", "]": "[", "}": "{"}
    st = []
    for ch in text:
        if ch in "([{":
            st.append(ch)
        elif ch in pairs:
            if not st or st.pop() != pairs[ch]:
                return False
    return not st


for sample in ["(a[b]{c})", "(a[b)c]", "((()", "", "a(b)c"]:
    print(f"{sample!r:>12} -> {balanced(sample)}")
 '(a[b]{c})' -> True
   '(a[b)c]' -> False
      '((()' -> False
          '' -> True
     'a(b)c' -> True

آخرین پرانتزِ باز، اولین پرانتزی است که باید بسته شود — و این دقیقاً LIFO است. کلِ الگوریتم یک stack است و یک حلقه، و هزینه‌اش O(n) روی طولِ متن.

✅ چک کن: st.pop() را به st.pop(0) تغییر بده و همان پنج نمونه را بزن. "(a[b)c]" باید از False به True برود — یعنی جوابِ غلط. queue کردنِ یک stack این‌جا فقط کند نمی‌کند، جواب را عوض می‌کند.

۴. queue با list در برابرِ queue با deque#

queue از ابتدا برمی‌دارد. با list این یعنی pop(0) — و فصلِ ۴ نشان داد که چه هزینه‌ای دارد.

🤔 اول حدس بزن: دو جدول می‌گیریم: queue با list و queue با deque. ستونِ نسبتِ هر کدام را حدس بزن، و بعد حدس بزن در n = 80,000 چند برابر با هم فاصله دارند.

def run_queue_list(n):
    q = []
    for i in range(n):
        q.append(i)
    total = 0
    while q:
        total += q.pop(0)
    return total


def run_queue_deque(n):
    q = deque()
    for i in range(n):
        q.append(i)
    total = 0
    while q:
        total += q.popleft()
    return total


QUEUE = [10_000, 20_000, 40_000, 80_000]
print("دو نسخه یک جواب می‌دهند؟", run_queue_list(1_000) == run_queue_deque(1_000))
print("\n— queue با list و pop(0)")
table([(n, 1000 * clock(lambda k=n: run_queue_list(k), repeat=2)) for n in QUEUE],
      "زمان (ms)", ",.2f")
print("\n— queue با deque و popleft()")
table([(n, 1000 * clock(lambda k=n: run_queue_deque(k), repeat=2)) for n in QUEUE],
      "زمان (ms)", ",.2f")
دو نسخه یک جواب می‌دهند؟ True

— queue با list و pop(0)
         n         زمان (ms)     نسبت به سطر قبل
    10,000              5.02                   —
    20,000             21.25                4.23
    40,000             96.69                4.55
    80,000            447.14                4.62

— queue با deque و popleft()
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.65                   —
    20,000              1.32                2.04
    40,000              2.76                2.09
    80,000              5.86                2.12

4 در برابرِ 2. queue با list درجه‌دو است و با deque خطی.

و حالا عددِ صریحِ فاصله، که همان چیزی است که ردیفِ این فصل در نقشهٔ درسی وعده داده:

print(f"{'n':>10}{'list (ms)':>14}{'deque (ms)':>14}{'list ÷ deque':>16}")
for n in QUEUE:
    a = 1000 * clock(lambda k=n: run_queue_list(k), repeat=2)
    b = 1000 * clock(lambda k=n: run_queue_deque(k), repeat=2)
    print(f"{n:>10,}{a:>14.2f}{b:>14.2f}{a / b:>16,.1f}")
         n     list (ms)    deque (ms)    list ÷ deque
    10,000          6.33          0.62            10.3
    20,000         25.11          1.22            20.6
    40,000         85.07          2.77            30.7
    80,000        501.66          5.79            86.6

نسبت خودش با n بزرگ می‌شود: از حدودِ ده برابر به چند ده برابر. این امضای مقایسهٔ یک O(n²) با یک O(n) است — فاصله ثابت نیست، خودش رشد می‌کند. اگر همین جدول را تا n = 640,000 ادامه بدهی، نسبت هم هشت برابرِ سطرِ آخر می‌شود.

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

۵. deque چه چیزی را در ازایش می‌دهد#

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

بهایش هم دقیقاً از همین‌جا می‌آید: رفتن به خانهٔ شمارهٔ i دیگر یک ضرب و یک جمع نیست.

BIG = 200_000
lst = list(range(BIG))
dq = deque(range(BIG))
READS = 20_000


def read_at(box, pos, times=READS):
    seen = None
    for _ in range(times):
        seen = box[pos]
    return seen


print(f"{'موقعیت':>10}{'list (µs)':>14}{'deque (µs)':>14}")
for name, pos in (("ابتدا", 0), ("وسط", BIG // 2), ("انتها", BIG - 1)):
    a = 1e6 * clock(lambda p=pos: read_at(lst, p), repeat=3) / READS
    b = 1e6 * clock(lambda p=pos: read_at(dq, p), repeat=3) / READS
    print(f"{name:>10}{a:>14.4f}{b:>14.4f}")
    موقعیت     list (µs)    deque (µs)
     ابتدا        0.0196        0.0303
       وسط        0.0215        6.4095
     انتها        0.0200        0.0287

در دو سرِ deque خواندن به‌ارزانیِ list است و در وسطش صدها برابر گران‌تر. list هر سه موقعیت را یکسان می‌خواند — همان O(1)ِ فصلِ ۱.

پس قاعدهٔ انتخاب یک جملهٔ ساده است: اگر فقط با دو سرِ دنباله کار داری، deque؛ اگر با اندیس‌های وسط کار داری، list. فصلِ بعد این جمله را به یک جدولِ کامل تبدیل می‌کند.

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

try:
    deque().popleft()
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
try:
    deque([1, 2, 3]).pop(0)
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
IndexError: pop from an empty deque
TypeError: deque.pop() takes no arguments (1 given)

پیامِ دوم خیلی گویاست: deque.pop اصلاً اندیس قبول نمی‌کند. این یک محدودیتِ سلیقه‌ای نیست — deque عمداً کاری را که نمی‌تواند ارزان انجام بدهد، اصلاً پیشنهاد نمی‌کند. اگر کدِ listی‌ات را به deque منتقل کردی و این خطا را گرفتی، همان‌جا فهمیده‌ای که یک pop(0)ِ پنهان داشته‌ای.

🤖 از دستیارت بپرس: «تفاوتِ LIFO و FIFO را با یک مثالِ روزمره توضیح بده.» بعد این را هم بپرس: «چرا در پایتون برای queue از deque استفاده می‌کنیم ولی برای stack از list کافی است؟» — جوابِ درست باید بگوید هر دو عملیاتِ stack در انتهای ظرف‌اند و queue یک سرِ دیگر هم لازم دارد.

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

کلمه تلفظ به حروف فارسی یعنی چه
stack استَک انضباطی که آخرین ورودی را اول برمی‌دارد
queue کیو انضباطی که اولین ورودی را اول برمی‌دارد
LIFO لایفو آخرین ورودی، اولین خروجی
FIFO فایفو اولین ورودی، اولین خروجی

تمرین‌ها

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

در فصل بعد#

سه ظرف داریم و هر کدام در جایی برنده‌اند. فصلِ بعد به‌جای یک ظرفِ تازه، یک جدول می‌سازد: هزینهٔ هر عملیاتِ اصلی، روی هر ظرف، اندازه‌گیری‌شده نه نقل‌شده. بعد نشان می‌دهد که با عوض کردنِ نسبتِ خواندن به نوشتن در یک بارِ کاریِ ثابت، برنده کاملاً جابه‌جا می‌شود — در یک حالت list بیش از ده برابر جلو است و در حالتِ دیگر deque صدها برابر. و آخر، دو ظرفِ تازه برای وقتی که حافظه دیوار است: array و bytearray.

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

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