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

فصل ۵ از ۸

پیشرفت ترم
۰٪

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

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

ولی این آزادی یک هزینهٔ فوری دارد: باید تصمیم بگیری یال‌ها را چطور ذخیره کنی. دو راهِ استاندارد هست و در یک گرافِ ۴٬۰۰۰ گره‌ای یکی 16,261,048 بایت می‌گیرد و دیگری 627,864 بایت. ولی این یک برندهٔ همیشگی نیست: از چگالیِ 0.107 به بعد ورق برمی‌گردد و برنده عوض می‌شود.

شبکه‌ای از گره‌ها با یال‌های متقاطع در کنارِ یک جدولِ مربعیِ خانه‌های پر و خالی

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

  • یک گراف را با فهرستِ مجاورت و با ماتریسِ مجاورت بسازی
  • حافظهٔ هر دو را با عددِ واقعی اندازه بگیری، نه با حدس
  • نقطهٔ سربه‌سرشان را پیدا کنی و بگویی به چه چیزی بند است
  • بگویی جهت‌دار و بی‌جهت در کد دقیقاً چه فرقی دارند

قبل از شروع#

از ترمِ ۲ فصلِ ۸: bytearray وقتی حافظه مهم است. این فصل ماتریس را با همان می‌سازد — یک یال یا هست یا نیست، و یک بایت برایش کافی است.

از ترمِ ۲ فصلِ ۲: sys.getsizeof و اینکه اندازهٔ یک ظرف را از خودِ ظرف بپرسی، نه از حدس.

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

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

۱. کوچک‌ترین نسخهٔ ممکن: فهرستِ مجاورت#

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

جاده دوطرفه است، پس هر یال دو بار ثبت می‌شود — یک بار در فهرستِ هر سرش. این همان تفاوتِ بی‌جهت و جهت‌دار است و کلِ فرقش همین دو خط است: اگر رابطه یک‌طرفه بود (مثلِ «این صفحه به آن صفحه لینک داده»)، فقط یکی از دو خط را می‌نوشتی.

CITIES = ["ahvaz", "isfahan", "karaj", "mashhad", "shiraz", "tabriz"]
ROADS = [("ahvaz", "isfahan"), ("isfahan", "karaj"), ("isfahan", "shiraz"),
         ("karaj", "tabriz"), ("mashhad", "tabriz"), ("karaj", "mashhad")]

adjacency = {city: [] for city in CITIES}
for a, b in ROADS:
    adjacency[a].append(b)
    adjacency[b].append(a)
for city in adjacency:
    adjacency[city].sort()

for city in CITIES:
    print(f"{city:>8}: {adjacency[city]}")
print("\nتعدادِ گره:", len(CITIES), "· تعدادِ یال:", len(ROADS))
   ahvaz: ['isfahan']
 isfahan: ['ahvaz', 'karaj', 'shiraz']
   karaj: ['isfahan', 'mashhad', 'tabriz']
 mashhad: ['karaj', 'tabriz']
  shiraz: ['isfahan']
  tabriz: ['karaj', 'mashhad']

تعدادِ گره: 6 · تعدادِ یال: 6

خطِ sort تزئینی نیست و باید بماند. ترتیبِ همسایه‌ها در فهرست، ترتیبِ بازدید در فصلِ بعد را تعیین می‌کند؛ اگر مرتبشان نکنی، خروجیِ پیمایشت به ترتیبِ درجِ یال‌ها بند است و هر بار که فایلِ ورودی‌ات کمی جابه‌جا شود، جوابت هم عوض می‌شود. این ارزان‌ترین بیمهٔ تکرارپذیری در کلِ این ترم است.

۲. همان گراف، نمایشِ دوم: ماتریسِ مجاورت#

راهِ دیگر این است که یک جدولِ مربعی بسازی: سطرِ i و ستونِ j، و در هر خانه یک بیت — یال هست یا نیست. گره‌ها باید شماره داشته باشند، پس اول یک dict می‌سازیم که اسم را به شماره تبدیل کند.

index = {city: i for i, city in enumerate(CITIES)}
matrix = [bytearray(len(CITIES)) for _ in CITIES]
for a, b in ROADS:
    matrix[index[a]][index[b]] = 1
    matrix[index[b]][index[a]] = 1

print(f"{'':>8}", " ".join(f"{city[:3]:>3}" for city in CITIES))
for city in CITIES:
    print(f"{city:>8}", " ".join(f"{x:>3}" for x in matrix[index[city]]))
print("\nماتریس متقارن است؟",
      all(matrix[i][j] == matrix[j][i] for i in range(6) for j in range(6)))
print("جادهٔ ahvaz–karaj هست؟", matrix[index['ahvaz']][index['karaj']] == 1,
      "·", "karaj" in adjacency["ahvaz"])
         ahv isf kar mas shi tab
   ahvaz   0   1   0   0   0   0
 isfahan   1   0   1   0   1   0
   karaj   0   1   0   1   0   1
 mashhad   0   0   1   0   0   1
  shiraz   0   1   0   0   0   0
  tabriz   0   0   1   1   0   0

ماتریس متقارن است؟ True
جادهٔ ahvaz–karaj هست؟ False · False

تقارنِ ماتریس، همان بی‌جهت‌بودن است. در گرافِ جهت‌دار این تقارن از بین می‌رود و ماتریس دیگر آینه ندارد.

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

۳. حافظه: V² در برابرِ V + E#

حالا هر دو را بزرگ می‌کنیم. گراف‌های آزمایش تُنُک‌اند: به‌ازای هر گره سه یال، که برای شبکه‌های واقعی نسبتِ کاملاً معمولی‌ای است.

🌱 ریشه‌اش کجاست: حافظهٔ ماتریس با مربعِ تعدادِ گره‌ها می‌رود، چون جدولی V در V است — و «دو برابر شدنِ ضلع، چهار برابر شدنِ مساحت» همان شهودی است که ریشه ترمِ ۵ فصل ۵ با مساحت و محیط می‌سازد. فهرستِ مجاورت اما محیط را می‌شمارد، نه مساحت را: فقط جفت‌هایی که واقعاً یال‌اند.

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

def make_graph(node_count, edge_count, seed=SEED):
    """گرافِ بی‌جهتِ ساده: بدونِ یالِ تکراری و بدونِ یال از گره به خودش."""
    rng = random.Random(seed)
    edges = set()
    while len(edges) < edge_count:
        a = rng.randrange(node_count)
        b = rng.randrange(node_count)
        if a != b:
            edges.add((min(a, b), max(a, b)))
    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 sorted(edges), graph


def list_bytes(graph):
    """حافظهٔ خودِ ظرف‌ها: dict به‌علاوهٔ همهٔ فهرست‌های مجاورت."""
    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)


V = [500, 1_000, 2_000, 4_000]
print("تخمینِ حافظهٔ بزرگ‌ترین ماتریس پیش از ساختن:",
      f"{4_000 * 4_000 / 1_000_000:.0f} مگابایت")
sparse = {v: make_graph(v, 3 * v) for v in V}
print("گرافِ ۵۰۰ گره‌ای — درجهٔ گرهِ صفر:", len(sparse[500][1][0]),
      "· سه همسایه‌اش:", sparse[500][1][0][:3])
تخمینِ حافظهٔ بزرگ‌ترین ماتریس پیش از ساختن: 16 مگابایت
گرافِ ۵۰۰ گره‌ای — درجهٔ گرهِ صفر: 5 · سه همسایه‌اش: [30, 83, 87]

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

print("— ماتریسِ مجاورت")
table([(v, matrix_bytes(v)) for v in V], "بایت", ",d")
print("\n— فهرستِ مجاورت، همان گراف (E = 3V)")
table([(v, list_bytes(sparse[v][1])) for v in V], "بایت", ",d")
— ماتریسِ مجاورت
         n              بایت     نسبت به سطر قبل
       500           282,716                   —
     1,000         1,065,856                3.77
     2,000         4,130,184                3.87
     4,000        16,261,048                3.94

— فهرستِ مجاورت، همان گراف (E = 3V)
         n              بایت     نسبت به سطر قبل
       500            78,960                   —
     1,000           157,432                1.99
     2,000           315,856                2.01
     4,000           627,864                1.99

3.94 در برابرِ 1.99. ستونِ اول رو به 4 می‌رود — یعنی V²، دقیقاً همان چیزی که ترمِ ۱ فصلِ ۵ برای «نسبتِ نزدیکِ ۴» گفت. ستونِ دوم 2 است — یعنی خطی، و چون در این گراف‌ها E = 3V است، خطی بودن نسبت به V و خطی بودن نسبت به V + E یک چیزند.

(ستونِ اول از 3.77 شروع می‌شود نه از 4.00، چون در اندازه‌های کوچک سربارِ ثابتِ هر bytearray هنوز سهمِ محسوسی از کل دارد. هرچه V بزرگ‌تر می‌شود سهمش کمتر و نسبت به 4 نزدیک‌تر می‌شود.)

در V = 4,000 ماتریس بیش از شانزده مگابایت می‌گیرد و فهرست کمتر از ششصد و سی کیلوبایت — بیست و پنج برابر. و مهم‌تر از خودِ عدد این است که این نسبت با بزرگ‌تر شدنِ گراف بدتر هم می‌شود، چون یک ستون با V می‌رود و دیگری با V².

۴. ولی این برندهٔ همیشگی نیست#

جدولِ بالا فقط دربارهٔ گرافِ تنک حرف می‌زند. حالا V را روی ۵۰۰ ثابت نگه می‌داریم و تعدادِ یال‌ها را دو برابر می‌کنیم. حافظهٔ ماتریس به یال‌ها هیچ کاری ندارد و ثابت می‌ماند؛ حافظهٔ فهرست پابه‌پای یال‌ها بالا می‌رود.

🤔 اول حدس بزن: با V ثابت و دو برابر شدنِ E، ستونِ نسبتِ حافظهٔ فهرست چه عددی می‌دهد؟ و مهم‌تر: حدس بزن این دو منحنی در چه چگالی‌ای همدیگر را قطع می‌کنند — یک‌دهم؟ یک‌سوم؟ نصف؟ عددت را بنویس، بعد جدول را ببین.

FIXED_V = 500
MAX_EDGES = FIXED_V * (FIXED_V - 1) // 2
DENSE = [7_800, 15_600, 31_200, 62_400]
dense = {e: make_graph(FIXED_V, e) for e in DENSE}

print(f"V = {FIXED_V} · بیشترین یالِ ممکن = {MAX_EDGES:,}"
      f" · حافظهٔ ماتریس = {matrix_bytes(FIXED_V):,} بایت (ثابت)")
print(f"\n{'E':>10}{'چگالی':>10}{'فهرست (بایت)':>18}{'نسبت به سطر قبل':>20}")
previous = None
for e in DENSE:
    size = list_bytes(dense[e][1])
    ratio = "—" if not previous else f"{size / previous:.2f}"
    print(f"{e:>10,}{e / MAX_EDGES:>10.3f}{size:>18,}{ratio:>20}")
    previous = size
V = 500 · بیشترین یالِ ممکن = 124,750 · حافظهٔ ماتریس = 282,716 بایت (ثابت)

         E     چگالی      فهرست (بایت)     نسبت به سطر قبل
     7,800     0.063           185,424                   —
    15,600     0.125           318,288                1.72
    31,200     0.250           583,856                1.83
    62,400     0.500         1,117,552                1.91

سطرِ دوم از عددِ ثابتِ ماتریس رد شده است. در E = 7,800 فهرست هنوز برنده است (185,424 در برابرِ 282,716)، و در E = 15,600 باخته (318,288). جایی بینِ این دو، برنده عوض می‌شود. پیدایش می‌کنیم:

def crossover(node_count, low, high):
    """کوچک‌ترین تعدادِ یالی که از آن به بعد فهرست از ماتریس سنگین‌تر می‌شود."""
    target = matrix_bytes(node_count)
    while low < high:
        middle = (low + high) // 2
        if list_bytes(make_graph(node_count, middle)[1]) < target:
            low = middle + 1
        else:
            high = middle
    return low


point = crossover(FIXED_V, 1_000, MAX_EDGES)
print(f"نقطهٔ سربه‌سر: {point:,} یال  ·  چگالی {point / MAX_EDGES:.3f}")
print(f"حافظهٔ ماتریس {matrix_bytes(FIXED_V):,} بایت"
      f"  ·  حافظهٔ فهرست در همان نقطه {list_bytes(make_graph(FIXED_V, point)[1]):,} بایت")
نقطهٔ سربه‌سر: 13,404 یال  ·  چگالی 0.107
حافظهٔ ماتریس 282,716 بایت  ·  حافظهٔ فهرست در همان نقطه 282,768 بایت

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

و این دقیقاً همان نقطهٔ تقاطعِ ترمِ ۱ فصلِ ۹ است، فقط این بار محورش زمان نیست، حافظه است. جملهٔ «فهرستِ مجاورت بهتر است» بدونِ گفتنِ چگالی، همان‌قدر بی‌معناست که یک ادعای پیچیدگی بدونِ بازهٔ n.

۵. و یک هزینهٔ دیگر که فهرست می‌پردازد#

پرسشِ «آیا این یال هست؟» در ماتریس یک خواندن است. در فهرست، گشتنِ فهرستِ همسایه‌هاست — و آن فهرست در گرافِ چگال بلند است.

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

TRIALS = 2_000


def scan_cost(graph):
    """میانگینِ تعدادِ خانه‌ای که «آیا این یال هست؟» در فهرستِ مجاورت می‌خواند."""
    rng = random.Random(SEED)
    total = 0
    for _ in range(TRIALS):
        a = rng.randrange(len(graph))
        b = rng.randrange(len(graph))
        for neighbour in graph[a]:
            total += 1
            if neighbour == b:
                break
    return total / TRIALS


print("— فهرستِ مجاورت: میانگینِ خانه‌های خوانده‌شده در یک پرسشِ یال")
print(f"{'E':>10}{'میانگینِ خانه':>18}{'نسبت به سطر قبل':>20}")
previous = None
for e in DENSE:
    cost = scan_cost(dense[e][1])
    ratio = "—" if not previous else f"{cost / previous:.2f}"
    print(f"{e:>10,}{cost:>18,.1f}{ratio:>20}")
    previous = cost
print("\nهمان پرسش در ماتریس: همیشه یک خواندن، در هر چگالی.")
— فهرستِ مجاورت: میانگینِ خانه‌های خوانده‌شده در یک پرسشِ یال
         E     میانگینِ خانه     نسبت به سطر قبل
     7,800              16.4                   —
    15,600              32.1                1.95
    31,200              63.8                1.98
    62,400             126.1                1.98

همان پرسش در ماتریس: همیشه یک خواندن، در هر چگالی.

ستونِ نسبت 1.98 است: هزینهٔ این پرسش با تعدادِ یال‌ها خطی می‌رود — چون با ثابت ماندنِ V، دو برابر شدنِ یال‌ها یعنی دو برابر شدنِ درجهٔ متوسطِ هر گره. در برابرش، ماتریس در هر چهار سطر همان یک خواندن را دارد.

پس تصمیم دو محور دارد، نه یکی: چگالی، و اینکه برنامه‌ات بیشتر «همسایه‌ها را بشمار» می‌پرسد یا «این یالِ مشخص هست؟». فهرست برای اولی ساخته شده و ماتریس برای دومی.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ دو نمایشِ یک گرافِ واحد، روی دو سؤال: حافظهٔ ظرف‌ها با sys.getsizeof، و تعدادِ خانه‌های خوانده‌شده در یک پرسشِ یال. در کدام بازهٔ n؟ ۵۰۰ تا ۴٬۰۰۰ گره با E = 3V، و V = 500 ثابت با ۷٬۸۰۰ تا ۶۲٬۴۰۰ یال. با چند تکرار، و کمینه یا میانگین؟ حافظه یک اجرا و قطعی؛ پرسشِ یال میانگینِ دو هزار پرسش که — چون با همان SEEDِ ساختِ گراف تولید شده‌اند — تقریباً همه‌شان روی یالِ موجود می‌افتند. پس این عدد هزینهٔ جست‌وجوی موفق است، و پرسشِ ناموفق تقریباً دو برابرِ آن خرج دارد چون تا ته فهرست می‌رود. مرتبه عوض نمی‌شود، عددِ ثابتش عوض می‌شود. هیچ عددِ ثانیه‌ای در این فصل نیست.

✅ چک کن: در matrix_bytes به‌جای bytearray(node_count) بنویس [0] * node_count و جدولِ بخشِ ۳ را دوباره بگیر. عددهای ماتریس باید حدودِ هشت برابر شوند و ستونِ نسبت همچنان حولِ 4 بماند — این بار حتی نزدیک‌تر به 4 (حدودِ 3.97 به بالا)، چون سربارِ ثابتِ هر سطر حالا سهمِ خیلی کمتری از یک سطرِ سنگین‌تر است. یعنی نقطهٔ سربه‌سر جابه‌جا می‌شود ولی مرتبه نه — همان تفکیکِ ثابت و مرتبه که کلِ ترمِ ۱ دربارهٔ آن بود.

🔧 اگر کار نکرد: رایج‌ترین خطای کار با فهرستِ مجاورت این است که سراغِ گره‌ای بروی که اصلاً در گراف نیست — یک غلطِ املایی در نامِ گره کافی است:

try:
    print(adjacency["yazd"])
except KeyError as err:
    print(f"{type(err).__name__}: {err}")
print("همسایه‌های یک گرهِ ناشناس، بدونِ خطا:", adjacency.get("yazd", []))
KeyError: 'yazd'
همسایه‌های یک گرهِ ناشناس، بدونِ خطا: []

و سطرِ دوم را با احتیاط به‌کار ببر. .get(node, []) خطا را خفه می‌کند و برای پیمایشی که ممکن است به گرهِ بی‌همسایه برسد مناسب است — ولی اگر گره واقعاً وجود نداشته باشد، به تو می‌گوید «همسایه ندارد» به‌جای «چنین گره‌ای نیست». دو جوابِ کاملاً متفاوت، با یک ظاهر. اگر پیمایشت ساکت شد و هیچ گره‌ای پیدا نکرد، اول همین را چک کن.

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

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

کلمه تلفظ به حروف فارسی یعنی چه
graph گراف مجموعه‌ای از گره‌ها و یال‌هایی که آن‌ها را به هم وصل می‌کنند
edge اِج یال: یک رابطه بینِ دو گره
degree دِگری درجهٔ یک گره: تعدادِ یال‌هایی که به آن وصل‌اند
adjacency list اَجِیسِنسی لیست فهرستِ مجاورت: برای هر گره، فهرستِ همسایه‌هایش
adjacency matrix اَجِیسِنسی ماتریکس ماتریسِ مجاورت: جدولی V در V از بودن یا نبودنِ یال
density دنسیتی چگالی: نسبتِ یال‌های موجود به همهٔ یال‌های ممکن

تمرین‌ها

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

در فصل بعد#

حالا گراف را داریم و هنوز هیچ کاری با آن نکرده‌ایم. فصلِ بعد دو پیمایشِ فصلِ ۲ را روی گراف می‌برد — همان queue و همان stack — و می‌بینی که یکی از این دو کوتاه‌ترین مسیر را می‌دهد و دیگری نمی‌دهد.

آن‌جا کدی می‌بینی که با یک کلمه تفاوت، به‌جای فاصلهٔ [0, 1, 3, 2, 3, 3, 2, 1] جوابِ [0, 1, 6, 5, 4, 3, 2, 1] می‌دهد — بدونِ هیچ خطایی، و با دیدنِ هر هشت گره.

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

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