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

فصل ۸ از ۸

پیشرفت ترم
۰٪

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

هفت فصلِ این ترم را پشتِ سر گذاشتیم. این فصل یکی از ساختارهایشان را انتخاب می‌کند و کارِ کامل را انجام می‌دهد: یک شبکه با 4,000 گره و 11,994 یال، انتخابِ نمایش با عدد، پیمایش، تأییدِ V + 2E، و آخر از همه اعلامِ صریحِ چیزی که حساب نکردیم.

آخرین قسمت مهم‌ترینش است. قطرِ دقیقِ این شبکه 111,952,000 گام می‌خواهد؛ ما با 55,976 گام یک حدِ پایین می‌گیریم — و در یکی از دو اندازه‌ای که جوابِ دقیق را داریم، آن حدِ پایین یک واحد کمتر از جوابِ درست درمی‌آید. همان را هم گزارش می‌کنیم.

شبکه‌ای با چند گرهِ بسیار پرارتباط که بقیهٔ گره‌ها دورشان حلقه زده‌اند

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

  • یک شبکهٔ تکرارپذیر بسازی و توزیعِ درجه‌اش را نگاه کنی
  • نمایش را با عدد انتخاب کنی، نه با عادت
  • فاصله‌ها و مؤلفه‌ها را با BFS بگیری و هزینه‌اش را تأیید کنی
  • محدودیتِ گزارشت را با عدد بنویسی، نه با «تقریباً»

قبل از شروع#

از فصلِ ۵: فهرستِ مجاورت در برابرِ ماتریس، sys.getsizeof و چگالی. از فصلِ ۶: BFS، مجموعهٔ دیده‌شده‌ها، مؤلفه‌ها و شمارندهٔ V + 2E. از فصلِ ۷: اینکه بعضی سؤال‌ها را نباید پرسید.

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

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

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

۱. شبکه، و شکلش#

from collections import deque

LINKS = 3


def make_network(node_count, seed=SEED):
    """هر گرهِ تازه سه پیوند می‌سازد، و گرهی که از قبل پرپیوندتر است شانسِ بیشتری دارد."""
    rng = random.Random(seed)
    pool = []
    edges = set()
    for a in range(LINKS):
        for b in range(a + 1, LINKS):
            edges.add((a, b))
            pool.append(a)
            pool.append(b)
    for node in range(LINKS, node_count):
        chosen = set()
        while len(chosen) < LINKS:
            chosen.add(rng.choice(pool))
        for other in sorted(chosen):
            edges.add((other, node))
            pool.append(other)
            pool.append(node)
    graph = {node: [] for node in range(node_count)}
    for a, b in sorted(edges):
        graph[a].append(b)
        graph[b].append(a)
    for node in graph:
        graph[node].sort()          # ترتیبِ ثابت، تا هر اجرا همان جواب را بدهد
    return graph, sorted(edges)


network, links = make_network(4_000)
degrees = sorted((len(nbrs) for nbrs in network.values()), reverse=True)
print(f"V = {len(network):,}  ·  E = {len(links):,}")
print("پنج درجهٔ اول :", degrees[:5])
print("پنج درجهٔ آخر :", degrees[-5:])
print("میانگینِ درجه :", f"{2 * len(links) / len(network):.2f}")
print("گره‌هایی با درجهٔ ۳ یا کمتر:", f"{sum(1 for d in degrees if d <= 3):,}")
V = 4,000  ·  E = 11,994
پنج درجهٔ اول : [229, 222, 145, 105, 101]
پنج درجهٔ آخر : [3, 3, 3, 3, 3]
میانگینِ درجه : 6.00
گره‌هایی با درجهٔ ۳ یا کمتر: 1,596

میانگینِ درجه 6.00 است و هیچ چیزی دربارهٔ این شبکه نمی‌گوید. پرارتباط‌ترین گره 229 همسایه دارد — بیش از سی و هشت برابرِ میانگین — و 1,596 گره، یعنی حدودِ چهار دهمِ کلِ شبکه، فقط سه همسایه دارند.

این همان درسِ ترمِ ۳ فصلِ ۴ است، این بار روی یک گراف: میانگین به‌تنهایی شکلِ توزیع را پنهان می‌کند. و این‌جا پنهان کردنش گران است، چون کلِ رفتارِ پیمایش به همان چند گرهِ پرترافیک بند است.

۲. انتخابِ نمایش، با عدد#

def list_bytes(graph):
    return sys.getsizeof(graph) + sum(sys.getsizeof(nbrs) for nbrs in graph.values())


def matrix_bytes(node_count):
    rows = [bytearray(node_count) for _ in range(node_count)]
    return sys.getsizeof(rows) + sum(sys.getsizeof(row) for row in rows)


chosen_bytes = list_bytes(network)
other_bytes = matrix_bytes(len(network))
print(f"فهرستِ مجاورت : {chosen_bytes:>12,} بایت")
print(f"ماتریسِ مجاورت: {other_bytes:>12,} بایت")
print(f"نسبت          : {other_bytes / chosen_bytes:>12.0f} برابر")
print(f"چگالیِ این شبکه: {len(links) / (len(network) * (len(network) - 1) / 2):.5f}")
فهرستِ مجاورت :      613,624 بایت
ماتریسِ مجاورت:   16,261,048 بایت
نسبت          :           27 برابر
چگالیِ این شبکه: 0.00150

تصمیم و دلیلش، در دو سطر: چگالیِ این شبکه 0.00150 است و نقطهٔ سربه‌سرِ فصلِ ۵ روی 0.107 بود. هفتاد برابر زیرِ آن آستانه‌ایم، پس فهرستِ مجاورت. بیست و هفت برابر کم‌حافظه‌تر، و اگر گراف بزرگ‌تر شود این نسبت فقط بدتر می‌شود.

۳. پیمایش: مؤلفه‌ها و فاصله‌ها#

def bfs_distances(graph, start):
    dist = {start: 0}
    waiting = deque([start])
    while waiting:
        node = waiting.popleft()
        for nbr in graph[node]:
            if nbr not in dist:
                dist[nbr] = dist[node] + 1
                waiting.append(nbr)
    return dist


def sweep(graph):
    """تعدادِ مؤلفه‌ها و کارِ شمرده‌شدهٔ یک پیمایشِ کامل."""
    seen = set()
    components = 0
    work = 0
    for start in sorted(graph):
        if start in seen:
            continue
        components += 1
        seen.add(start)
        waiting = deque([start])
        while waiting:
            node = waiting.popleft()
            work += 1
            for nbr in graph[node]:
                work += 1
                if nbr not in seen:
                    seen.add(nbr)
                    waiting.append(nbr)
    return components, work


hub = max(network, key=lambda node: (len(network[node]), -node))
dist = bfs_distances(network, hub)
print("پرپیوندترین گره:", hub, "با درجهٔ", len(network[hub]))
print("چند گره از آن دیده می‌شود؟", len(dist), "از", len(network))
print(f"\n{'فاصله':>8}{'تعدادِ گره':>14}")
for step in range(max(dist.values()) + 1):
    print(f"{step:>8}{sum(1 for d in dist.values() if d == step):>14,}")
پرپیوندترین گره: 0 با درجهٔ 229
چند گره از آن دیده می‌شود؟ 4000 از 4000

   فاصله    تعدادِ گره
       0             1
       1           229
       2         1,654
       3         2,011
       4           105

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

این همان خاصیتی است که پیمایشِ شبکه‌های بزرگ را ممکن می‌کند: با درجهٔ متوسطِ ۶، تعدادِ گره‌های قابلِ دسترس در هر قدم چند برابر می‌شود، پس فاصله‌ها خیلی کندتر از تعدادِ گره‌ها بزرگ می‌شوند. بخشِ ۵ همین را در دو اندازه نشان می‌دهد: قطرِ V = 500 و V = 1,000 هر دو 6 است.

۴. هزینه، دوباره تأییدشده#

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

parts, work = sweep(network)
print("مؤلفه‌ها:", parts, "· کارِ شمرده‌شده:", f"{work:,}")
print("برابرِ V + 2E است؟", work == len(network) + 2 * len(links))

SIZES4 = [500, 1_000, 2_000, 4_000]
table([(v, sweep(make_network(v)[0])[1]) for v in SIZES4], "کار", ",d")
مؤلفه‌ها: 1 · کارِ شمرده‌شده: 27,988
برابرِ V + 2E است؟ True
         n               کار     نسبت به سطر قبل
       500             3,488                   —
     1,000             6,988                2.00
     2,000            13,988                2.00
     4,000            27,988                2.00

یک مؤلفه، و V + 2E دقیق. (ستونِ n این جدول تعدادِ گره‌هاست، یعنی همان V.)

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

۵. چیزی که حساب نکردیم#

قطرِ یک شبکه، یعنی بلندترین کوتاه‌ترین‌مسیرِ بینِ هر دو گره، جوابِ دقیقش یک BFS از هر گره می‌خواهد. راهِ ارزان‌تر «دو پیمایش» است: از یک گره BFS بزن و دورترین گره را پیدا کن، بعد از آن یکی BFS بزن. جوابش یک حدِ پایین است، نه قطر.

def double_sweep(graph, start):
    """حدِ پایینِ قطر: دورترین گره از start، بعد دورترین گره از آن."""
    first = bfs_distances(graph, start)
    far = max(first, key=lambda node: (first[node], -node))
    second = bfs_distances(graph, far)
    end = max(second, key=lambda node: (second[node], -node))
    return second[end], far, end


guess, a, b = double_sweep(network, 0)
print(f"حدِ پایینِ قطر: {guess}  ·  بین گرهٔ {a} و گرهٔ {b}")

exact_from = [500, 1_000]
for v in exact_from:
    part = make_network(v)[0]
    worst = 0
    for node in sorted(part):
        worst = max(worst, max(bfs_distances(part, node).values()))
    approx = double_sweep(part, 0)[0]
    print(f"V = {v:>5,}  ·  قطرِ دقیق {worst}  ·  حدِ پایین {approx}"
          f"  ·  {v} بار BFS به‌جای ۲ بار")
حدِ پایینِ قطر: 6  ·  بین گرهٔ 777 و گرهٔ 1622
V =   500  ·  قطرِ دقیق 6  ·  حدِ پایین 5  ·  500 بار BFS به‌جای ۲ بار
V = 1,000  ·  قطرِ دقیق 6  ·  حدِ پایین 6  ·  1000 بار BFS به‌جای ۲ بار

در V = 500 تقریب 5 داد و جوابِ درست 6 بود؛ در V = 1,000 هر دو 6 شدند. یعنی این روش گاهی درست است و گاهی یک واحد کم می‌آورد — و ما هیچ راهی نداریم بفهمیم روی شبکهٔ ۴٬۰۰۰ گره‌ای کدامش اتفاق افتاده.

cost_one = len(network) + 2 * len(links)
print(f"یک BFS روی این شبکه: {cost_one:,} گام")
print(f"قطرِ دقیق ({len(network):,} بار BFS): {len(network) * cost_one:,} گام")
print(f"حدِ پایین (۲ بار BFS)          : {2 * cost_one:,} گام")
print(f"نسبت                           : {len(network) // 2:,} برابر")
یک BFS روی این شبکه: 27,988 گام
قطرِ دقیق (4,000 بار BFS): 111,952,000 گام
حدِ پایین (۲ بار BFS)          : 55,976 گام
نسبت                           : 2,000 برابر

دو هزار برابر، برای عددی که ممکن است یکی کمتر باشد. این یک معاملهٔ آگاهانه است و کلِ فرقش با یک اشتباه، این است که نوشته شده باشد.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک پیمایشِ کامل با شمارندهٔ دستی در برابرِ فرمولِ V + 2E، و قطرِ تقریبی در برابرِ قطرِ دقیق روی دو اندازه‌ای که دقیقش قابلِ محاسبه بود. در کدام بازهٔ n؟ ۵۰۰ تا ۴٬۰۰۰ گره با E ≈ 3V. با چند تکرار، و کمینه یا میانگین؟ یک اجرا؛ همه‌چیز شمارش است و با SEED ثابت قطعی. هیچ عددِ ثانیه‌ای در این فصل نیست.

گزارشِ نهاییِ این پروژه، در چهار خط:

  • نمایش: فهرستِ مجاورت. دلیل: چگالی 0.00150، هفتاد برابر زیرِ نقطهٔ سربه‌سرِ 0.107؛ حافظه 613,624 بایت به‌جای 16,261,048.
  • پیمایش: یک BFS کامل، 27,988 گام، دقیقاً V + 2E، ستونِ نسبتِ 2.00 روی چهار اندازه.
  • یافته: یک مؤلفه، درجهٔ بیشینه 229 در برابرِ میانگینِ 6.00، همه‌چیز در حداکثر چهار قدم از پرترافیک‌ترین گره.
  • محدودیت: قطر اندازه‌گیری نشده؛ فقط یک حدِ پایینِ 6 داریم که در یکی از دو آزمونِ کنترلی یک واحد کم آورد. جوابِ دقیق 111,952,000 گام می‌خواست.

✅ چک کن: LINKS را از 3 به 2 تغییر بده و بخش‌های ۱، ۳ و ۴ را دوباره بگیر. تعدادِ مؤلفه‌ها باید 1 بماند — چون هر گره باز هم به شبکه وصل می‌شود — ولی E باید به 7,997 برسد، کارِ شمرده‌شده به 19,994، و جدولِ فاصله‌ها یک سطر بلندتر شود (تا فاصلهٔ ۵ به‌جای ۴). اگر مؤلفه‌ها بیشتر از یک شد، جای دیگری را دست زده‌ای. و LINKS = 1 را امتحان نکن: آن حلقهٔ اولِ make_network هیچ یالی نمی‌سازد، pool خالی می‌ماند و rng.choice روی فهرستِ خالی IndexError می‌دهد.

🔧 اگر کار نکرد: پرتکرارترین خطای این پروژه پیدا کردنِ «پرترافیک‌ترین گره» است. max روی یک dict کلیدها را می‌دهد و روی .values() مقدارها را — و اگر اشتباهی دومی را بگیری، یک list دستت می‌آید که فکر می‌کنی یک گره است:

try:
    busiest = max(network.values(), key=len)
    print(bfs_distances(network, busiest))
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
print("راهِ درست:", max(network, key=lambda node: (len(network[node]), -node)))
TypeError: unhashable type: 'list'
راهِ درست: 0

همان TypeError ترمِ ۳ فصلِ ۶، در یک لباسِ تازه. bfs_distances می‌خواهد گره را کلیدِ یک dict کند و list نمی‌تواند کلید باشد. و key=lambda node: (len(network[node]), -node) یک جزئیاتِ اضافه هم دارد که عمدی است: آن -node گرهِ کوچک‌ترشماره را در حالتِ تساوی برنده می‌کند، تا در هر اجرا همان گره انتخاب شود.

🤖 از دستیارت بپرس: گزارشِ چهارخطیِ بالا را جلویش بگذار و بپرس: «چه چیزی در این گزارش کم است؟» — جوابِ خوب باید سراغِ چیزی برود که ما نگفته‌ایم، نه چیزی که گفته‌ایم. بعد این را هم بپرس: «اگر بخواهم قطرِ دقیق را روی یک شبکهٔ یک‌میلیون‌گره‌ای بگیرم، چند گام می‌شود؟» و جوابش را با جدولِ فصلِ ۷ بسنج.

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

کلمه تلفظ به حروف فارسی یعنی چه
hub هاب گرهی که درجه‌اش خیلی بیشتر از میانگین است
degree distribution دِگری دیستریبیوشن توزیعِ درجه: اینکه چند گره چه تعداد همسایه دارند
diameter دایامتر قطر: بلندترین کوتاه‌ترین‌مسیرِ بینِ هر دو گره
lower bound لوئر باند حدِ پایین: عددی که جوابِ واقعی حتماً از آن کمتر نیست

تمرین‌ها

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

در فصل بعد#

ترمِ ۵ تمام شد. برای هر ساختاری که این پنج ترم ساختی یک جدول داری — و هنوز یک بار هم بینِ دو تای آن‌ها با نوشتنِ شکلِ مسئله انتخاب نکرده‌ای.

ترمِ بعد دقیقاً همین است: الگوی دسترسی، نسبتِ خواندن به نوشتن، بازهٔ واقعیِ n — و بعد یک جدولِ تصمیمِ یکپارچه که همهٔ اندازه‌گیری‌های این پنج ترم را کنارِ هم می‌گذارد و خانه‌های خالی‌اش را هم نشان می‌دهد.

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

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