در این فصل چه یاد میگیری#
هفت فصلِ این ترم را پشتِ سر گذاشتیم. این فصل یکی از ساختارهایشان را انتخاب میکند و کارِ کامل را انجام میدهد: یک شبکه با 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 — و بعد یک جدولِ تصمیمِ یکپارچه که همهٔ اندازهگیریهای این پنج ترم را کنارِ هم میگذارد و خانههای خالیاش را هم نشان میدهد.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.