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

فصل ۹ از ۹

پیشرفت ترم
۰٪

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

هیچ مفهومِ تازه‌ای. این فصل هشت فصلِ قبل را روی یک مسئلهٔ واقعی به‌کار می‌برد.

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

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

نوارِ بلندِ کاغذی که از دو ماشینِ متفاوت رد می‌شود و دو خروجیِ یکسان می‌دهد

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

  • الگوی دسترسیِ یک مسئلهٔ واقعی را قبل از نوشتنِ کد بنویسی
  • دو نسخه بسازی، برابریِ خروجیشان را ثابت کنی و مرتبه‌شان را اعلام کنی
  • سهمِ هر تصمیم را جدا اندازه بگیری به‌جای اینکه حدس بزنی کدام مقصر است

قبل از شروع#

از فصلِ ۴ و ۷: pop(0) در برابرِ popleft. از فصلِ ۵: items = items + [x]. از فصلِ ۸: الگوی دسترسی و جدولِ تصمیم.

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

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

۱. صورتِ مسئله و الگوی دسترسی#

سیاههٔ ما n سطر دارد و هر سطر یک شمارهٔ ترتیبی، یک سطحِ اهمیت و یک نامِ واحد دارد. هر سطح یک وزن دارد.

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

الگوی دسترسی، قبل از هر کدی:

  1. سطرها یکی‌یکی و به‌ترتیب می‌آیند — هیچ خواندنِ تصادفی‌ای لازم نیست.
  2. در هر گام یک عضو به انتهای پنجره اضافه می‌شود و یک عضو از ابتدا بیرون می‌رود.
  3. خروجی فقط به انتها اضافه می‌شود.

بندِ دوم می‌گوید پنجره یک queue است و بندِ سوم می‌گوید خروجی فقط append لازم دارد. جدولِ فصلِ ۸ برای هر دو یک ظرف نام می‌برد — و ما عمداً اول نسخه‌ای می‌نویسیم که هیچ‌کدام را رعایت نکند.

LEVELS = ("INFO", "WARN", "ERROR")
COST = {"INFO": 1, "WARN": 5, "ERROR": 25}


def make_log(n, seed=SEED):
    rng = random.Random(seed)
    return [f"{i:07d} {rng.choice(LEVELS)} unit-{rng.randrange(50)}" for i in range(n)]


def weight(line):
    return COST[line.split(" ", 2)[1]]


sample = make_log(5)
for line in sample:
    print(line, "->", weight(line))
0000000 WARN unit-7 -> 5
0000001 INFO unit-5 -> 1
0000002 ERROR unit-2 -> 25
0000003 ERROR unit-44 -> 25
0000004 INFO unit-6 -> 1

داده با SEED ساخته می‌شود، پس روی ماشینِ تو هم دقیقاً همین پنج سطر است.

۲. دو نسخه#

نسخهٔ اول دو تصمیمِ بد دارد و هر دو کاملاً طبیعی به‌نظر می‌رسند: پنجره یک list است که از ابتدایش pop(0) می‌شود، و خروجی با out = out + [x] ساخته می‌شود.

نسخهٔ دوم هر دو را عوض می‌کند: پنجره یک deque با maxlen است — که خودش عضوِ اضافه را از ابتدا بیرون می‌اندازد — و خروجی با append ساخته می‌شود.

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

from collections import deque


def summarise_slow(lines):
    """پنجره یک list است و از ابتدایش pop(0) می‌شود؛ خروجی با + ساخته می‌شود."""
    k = max(1, len(lines) // 10)
    window = []
    running = 0
    out = []
    for line in lines:
        w = weight(line)
        window.append(w)
        running += w
        if len(window) > k:
            running -= window.pop(0)
        out = out + [running]
    return out


def summarise_fast(lines):
    """پنجره یک deque با maxlen است؛ خروجی با append ساخته می‌شود."""
    k = max(1, len(lines) // 10)
    window = deque(maxlen=k)
    running = 0
    out = []
    for line in lines:
        w = weight(line)
        if len(window) == k:
            running -= window[0]
        window.append(w)
        running += w
        out.append(running)
    return out


check = make_log(2_000)
print("دو نسخه دقیقاً یک خروجی می‌دهند؟", summarise_slow(check) == summarise_fast(check))
print("طولِ خروجی:", len(summarise_fast(check)), "· ده مقدارِ اول:",
      summarise_fast(check)[:10])
دو نسخه دقیقاً یک خروجی می‌دهند؟ True
طولِ خروجی: 2000 · ده مقدارِ اول: [5, 6, 31, 56, 57, 62, 63, 64, 89, 94]

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

۳. جدولِ اندازه‌گیری#

LOGS = [2_000, 4_000, 8_000, 16_000]
logs = {n: make_log(n) for n in LOGS}
print("— نسخهٔ اول (ظرف‌های بد)")
table([(n, 1000 * clock(lambda v=logs[n]: summarise_slow(v), repeat=2)) for n in LOGS],
      "زمان (ms)", ",.2f")
print("\n— نسخهٔ دوم (ظرف‌های درست)")
table([(n, 1000 * clock(lambda v=logs[n]: summarise_fast(v), repeat=2)) for n in LOGS],
      "زمان (ms)", ",.2f")
print(f"\n{'n':>10}{'نسخهٔ اول ÷ نسخهٔ دوم':>24}")
for n in LOGS:
    a = clock(lambda v=logs[n]: summarise_slow(v), repeat=2)
    b = clock(lambda v=logs[n]: summarise_fast(v), repeat=2)
    print(f"{n:>10,}{a / b:>24.1f}")
— نسخهٔ اول (ظرف‌های بد)
         n         زمان (ms)     نسبت به سطر قبل
     2,000              4.39                   —
     4,000             15.73                3.58
     8,000             65.97                4.20
    16,000            274.58                4.16

— نسخهٔ دوم (ظرف‌های درست)
         n         زمان (ms)     نسبت به سطر قبل
     2,000              0.62                   —
     4,000              1.20                1.94
     8,000              2.41                2.00
    16,000              4.82                2.01

         n   نسخهٔ اول ÷ نسخهٔ دوم
     2,000                     7.0
     4,000                    12.6
     8,000                    26.5
    16,000                    46.6

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

۴. کدام تصمیم مقصر بود؟#

تا اینجا فقط می‌دانیم نسخهٔ اول کند است. نمی‌دانیم کدام‌یک از دو تصمیمِ بدش مقصر است — و «حدس می‌زنم pop(0)» یک جواب نیست.

پس دو نسخهٔ ترکیبی می‌سازیم و هر چهار حالت را می‌سنجیم.

def summarise_mixed_window(lines):
    """پنجرهٔ بد، خروجیِ خوب."""
    k = max(1, len(lines) // 10)
    window = []
    running = 0
    out = []
    for line in lines:
        w = weight(line)
        window.append(w)
        running += w
        if len(window) > k:
            running -= window.pop(0)
        out.append(running)
    return out


def summarise_mixed_output(lines):
    """پنجرهٔ خوب، خروجیِ بد."""
    k = max(1, len(lines) // 10)
    window = deque(maxlen=k)
    running = 0
    out = []
    for line in lines:
        w = weight(line)
        if len(window) == k:
            running -= window[0]
        window.append(w)
        running += w
        out = out + [running]
    return out


n = 16_000
data = logs[n]
variants = (("هر دو بد", summarise_slow),
            ("فقط پنجرهٔ بد", summarise_mixed_window),
            ("فقط خروجیِ بد", summarise_mixed_output),
            ("هر دو خوب", summarise_fast))
print("هر چهار نسخه یک خروجی می‌دهند؟",
      len({tuple(fn(check)) for _, fn in variants}) == 1)
print(f"\nn = {n:,}\n")
print(f"{'نسخه':>18}{'زمان (ms)':>14}{'نسبت به بهترین':>18}")
times = [(name, 1000 * clock(lambda f=fn: f(data), repeat=2)) for name, fn in variants]
best = min(t for _, t in times)
for name, t in times:
    print(f"{name:>18}{t:>14.2f}{t / best:>18.1f}")
هر چهار نسخه یک خروجی می‌دهند؟ True

n = 16,000

              نسخه     زمان (ms)    نسبت به بهترین
          هر دو بد        272.42              53.0
     فقط پنجرهٔ بد          6.91               1.3
     فقط خروجیِ بد        267.35              52.0
         هر دو خوب          5.14               1.0

این نتیجه خلافِ چیزی است که تقریباً همه حدس می‌زنند.

pop(0) روی پنجره — همان تلهٔ آشکارِ فصلِ ۴ — تقریباً هیچ سهمی ندارد. items = items + [x] روی خروجی — همان خطی که هیچ‌کس دو بار نگاهش نمی‌کند — تقریباً تمامِ اختلاف را می‌سازد.

و دلیلش کاملاً قابلِ توضیح است، به شرطی که بعد از دیدنِ عدد دنبالش بگردی:

  • پنجره n/10 عضو دارد، پس هر pop(0) حدودِ n/10 خانه را جابه‌جا می‌کند — ولی این جابه‌جایی یک انتقالِ پیوسته است که سخت‌افزار برایش ساخته شده و فصلِ ۱ نشان داد چقدر ارزان است.
  • out + [x] هر بار کلِ خروجیِ تا اینجا را در یک ظرفِ تازه کپی می‌کند: هم به‌اندازهٔ n کار، هم n بار ساختنِ ظرفِ تازه و دور ریختنِ قبلی. کارِ حافظه، نه فقط کارِ کپی.

⚠️ مواظب باش: این ترتیب به اندازهٔ پنجره بند است. کارِ جابه‌جاییِ پنجره k(n−k) است: با k = n/10 حدودِ ۲۳ میلیون خانه، و با k = n/2 نزدیکِ ۶۴ میلیون — نزدیکِ سه برابر بیشتر. سهمِ پنجره بزرگ‌تر می‌شود، ولی ترتیب برعکس نمی‌شود: در n = 16,000 و k = n/2 پنجرهٔ بد روی همین ماشین حدودِ هشت میلی‌ثانیه گرفت و خروجیِ بد حدودِ ۲۵۰ میلی‌ثانیه. و اگر k را برابرِ خودِ n بگذاری، هیچ pop(0)ی اصلاً اجرا نمی‌شود و پنجره رایگان می‌شود. این دقیقاً معنیِ «nِ خودت را بگو» است — و این‌جا kِ خودت را هم.

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

✅ چک کن: در summarise_fast عبارتِ deque(maxlen=k) را به deque() تغییر بده و بدونِ هیچ تغییرِ دیگری جدول را بگیر. خروجی غلط می‌شود — چون پنجره دیگر خودش را کوتاه نمی‌کند و window[0] قدیمی‌ترین عضوِ کلِ سیاهه می‌ماند. سطرِ مقایسهٔ == باید False بدهد. این نشان می‌دهد چرا آن سطر در هر آزمایشی اول می‌آید، نه آخر.

۵. گزارشِ نهایی#

این پنج بند همان چیزی است که فصلِ ۱۰ ترمِ ۱ خواست، این بار برای یک انتخابِ ظرف:

  1. الگوی دسترسی: افزودن به انتها و حذف از ابتدا در پنجره؛ فقط افزودن به انتها در خروجی؛ هیچ خواندنِ تصادفی.
  2. بازهٔ n: ۲٬۰۰۰ تا ۱۶٬۰۰۰ سطر، با پنجرهٔ n/10.
  3. مرتبهٔ اعلام‌شده: نسخهٔ اول O(n²) و نسخهٔ دوم O(n)، هر دو از ستونِ نسبت.
  4. درستی: خروجیِ هر چهار نسخه با == برابر تأیید شد.
  5. نتیجهٔ خلافِ انتظار: تصمیمی که مقصرِ آشکار به‌نظر می‌رسید تقریباً بی‌اثر بود.

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

🔧 اگر کار نکرد: یکی از اشتباه‌های رایجِ انتقالِ کد از list به deque فوری خودش را نشان می‌دهد:

window = deque([1, 2], maxlen=3)
window.insert(1, 99)                     # هنوز جا دارد
print("پنجرهٔ نیمه‌پر:", window)
try:
    window.insert(1, 77)                 # حالا پر است
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
پنجرهٔ نیمه‌پر: deque([1, 99, 2], maxlen=3)
IndexError: deque already at its maximum size

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

🤖 از دستیارت بپرس: جدولِ بخشِ ۴ را جلویش بگذار و بپرس: «چرا pop(0) روی یک پنجرهٔ ۱٬۶۰۰تایی تقریباً رایگان است ولی out = out + [x] روی یک خروجیِ ۱۶٬۰۰۰تایی نیست؟» — جوابِ درست باید دو چیز را از هم جدا کند: تعدادِ خانه‌هایی که جابه‌جا می‌شوند، و تعدادِ ظرف‌هایی که ساخته و دور ریخته می‌شوند.

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

کلمه تلفظ به حروف فارسی یعنی چه
sliding window اسلایدینگ ویندو بازه‌ای به طولِ ثابت که روی دنباله جلو می‌رود
maxlen مکس‌لن سقفِ طولِ یک deque؛ عضوِ اضافه خودبه‌خود از سرِ دیگر بیرون می‌رود

تمرین‌ها

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

در فصل بعد#

ترمِ دو تمام شد و برای هر عملیاتِ یک ظرفِ ترتیبی هزینه‌ای داری که خودت اندازه گرفته‌ای. ولی یک سطر از جدولِ فصلِ ۸ خالی ماند: پرسشِ «هست یا نه؟»

ترمِ سه دقیقاً همان است. یک hash table را از صفر می‌سازی، می‌بینی set و dict چه معامله‌ای می‌کنند، و بدترین حالتشان را پیدا می‌کنی — چون این بار، بر خلافِ کلِ این ترم، هزینهٔ اعلام‌شده و هزینهٔ واقعی می‌توانند خیلی از هم دور باشند.

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

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