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

فصل ۴ از ۹

پیشرفت ترم
۰٪

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

فصلِ قبل دو الگوریتم داشت که در n = 2,000 به حدودِ دو میلیون مقایسه می‌رسیدند. این فصل الگوریتمی می‌سازد که در n = 8,000 — چهار برابرِ آن — فقط 93,704 مقایسه می‌خواهد، و ستونِ نسبتش به‌جای 4.00 عددِ 2.19 است.

ایده‌اش یک جمله است: نصف کن، هر نصف را مرتب کن، دو نصفِ مرتب را ادغام کن. و بعد می‌شماریم که این سرعت با چه چیزی خریده شده: در n = 8,000، صد و سه هزار و هشتصد عضو کپی می‌شود — حافظه‌ای که insertion sort اصلاً لازم نداشت.

درختی که یک دستهٔ کارت را دو به دو می‌شکند و در راهِ برگشت، هر دو دستهٔ مرتب را به هم می‌بافد

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

  • دو دنبالهٔ مرتب را با یک بار عبور ادغام کنی
  • merge sort را از صفر بنویسی و درستی‌اش را ثابت کنی
  • با عدد نشان بدهی که کار در هر سطح n است و تعدادِ سطح‌ها log n
  • حافظهٔ کمکی‌اش را بشماری و بگویی چرا رایگان نیست

قبل از شروع#

از فصلِ ۱: حالتِ پایه، گامِ بازگشتی، و عمقِ call stack.

از فصلِ ۳: شمردنِ مقایسه‌ها، و اینکه selection sort در n = 2,000 عددِ 1,999,000 می‌دهد. همان عدد معیارِ مقایسهٔ این فصل است.

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

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

۱. ادغام: هستهٔ کلِ الگوریتم#

قبل از هر recursionی، این را حل کن: دو فهرست داری که هرکدام جداگانه مرتب‌اند. یک فهرستِ مرتب از هر دو بساز.

جوابش هیچ ربطی به مرتب‌سازی ندارد. کوچک‌ترینِ نتیجه حتماً یکی از دو عضوِ اول است، پس فقط کافی است هر بار کوچک‌ترِ آن دو را برداری و جلو بروی.

def merge(left, right):
    """دو دنبالهٔ مرتب را با یک بار عبور، به یک دنبالهٔ مرتب می‌چسباند."""
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])                 # هر چه از یک طرف مانده، مرتب است
    out.extend(right[j:])
    return out


a = [10, 14, 29, 37]
b = [11, 13, 18, 25]
print("چپ  :", a)
print("راست:", b)
print("ادغام:", merge(a, b))
print("مقایسه‌های لازم: حداکثر", len(a) + len(b) - 1)
چپ  : [10, 14, 29, 37]
راست: [11, 13, 18, 25]
ادغام: [10, 11, 13, 14, 18, 25, 29, 37]
مقایسه‌های لازم: حداکثر 7

هشت عضو، حداکثر هفت مقایسه. هر مقایسه دقیقاً یک عضو را نهایی می‌کند، و آخرین عضو اصلاً مقایسه نمی‌خواهد. پس ادغام O(n) است — یک بار عبور از هر دو فهرست، و نه بیشتر.

تمامِ merge sort روی همین یک تابع سوار است. بقیه‌اش فقط این است که از کجا دو فهرستِ مرتب بیاوریم.

۲. و جواب: از خودمان#

def merge_sort_traced(values, depth=0):
    """نصف کن، هر نصف را مرتب کن، دو نصفِ مرتب را ادغام کن."""
    pad = "  " * depth
    if len(values) <= 1:                 # حالتِ پایه: یک عضو، خودش مرتب است
        print(f"{pad}{values} <- پایه")
        return values
    mid = len(values) // 2
    print(f"{pad}{values} -> {values[:mid]} + {values[mid:]}")
    left = merge_sort_traced(values[:mid], depth + 1)
    right = merge_sort_traced(values[mid:], depth + 1)
    joined = merge(left, right)
    print(f"{pad}ادغام -> {joined}")
    return joined


print(merge_sort_traced([29, 10, 14, 37, 13, 25, 11, 18]))
[29, 10, 14, 37, 13, 25, 11, 18] -> [29, 10, 14, 37] + [13, 25, 11, 18]
  [29, 10, 14, 37] -> [29, 10] + [14, 37]
    [29, 10] -> [29] + [10]
      [29] <- پایه
      [10] <- پایه
    ادغام -> [10, 29]
    [14, 37] -> [14] + [37]
      [14] <- پایه
      [37] <- پایه
    ادغام -> [14, 37]
  ادغام -> [10, 14, 29, 37]
  [13, 25, 11, 18] -> [13, 25] + [11, 18]
    [13, 25] -> [13] + [25]
      [13] <- پایه
      [25] <- پایه
    ادغام -> [13, 25]
    [11, 18] -> [11] + [18]
      [11] <- پایه
      [18] <- پایه
    ادغام -> [11, 18]
  ادغام -> [11, 13, 18, 25]
ادغام -> [10, 11, 13, 14, 18, 25, 29, 37]
[10, 11, 13, 14, 18, 25, 29, 37]

اسمِ این الگو «تقسیم و حل» است و سه قدم دارد: مسئله را به دو نیمهٔ مستقل بشکن، هر نیمه را به همان روش حل کن، و جوابِ دو نیمه را به هم بچسبان.

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

۳. شمردن، در دو جهت#

حالا همان کد را با چهار شمارنده می‌نویسیم: مقایسه، عمق، مقایسه در هر سطح، و عضوِ کپی‌شده.

from collections import Counter


def merge_sort(values, stats=None, depth=1):
    """مرتب‌شده، به‌همراهِ شمارشِ مقایسه، عمق، مقایسه در هر سطح و عضوِ کپی‌شده."""
    if stats is None:
        stats = {"comparisons": 0, "depth": 0, "per_level": Counter(), "copied": 0}
    stats["depth"] = max(stats["depth"], depth)
    if len(values) <= 1:
        return values, stats
    mid = len(values) // 2
    left = merge_sort(values[:mid], stats, depth + 1)[0]
    right = merge_sort(values[mid:], stats, depth + 1)[0]
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        stats["comparisons"] += 1
        stats["per_level"][depth] += 1
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    stats["copied"] += len(out)
    return out, stats


rng = random.Random(SEED)
LADDER = [1_000, 2_000, 4_000, 8_000]
shuffled = {n: rng.sample(range(10 * n), n) for n in LADDER}
result, stats = merge_sort(shuffled[1_000])
print("با sorted یکی است؟", result == sorted(shuffled[1_000]))
print("مقایسه:", stats["comparisons"], "· عمق:", stats["depth"])
با sorted یکی است؟ True
مقایسه: 8709 · عمق: 11

۸٬۷۰۹ مقایسه برای هزار عضو. selection sort در همین n عددِ 499,500 می‌داد — پنجاه‌وهفت برابر بیشتر.

۴. چرا n log n: کار در هر سطح، و تعدادِ سطح‌ها#

عددِ 8,709 را می‌شود شکافت، و شکافتنش کلِ استدلالِ این الگوریتم است.

print("سطح   تعدادِ مقایسه در این سطح")
for level in sorted(stats["per_level"]):
    print(f"{level:>4}   {stats['per_level'][level]:>10,}")
print(f"جمع    {stats['comparisons']:>10,}   (n = 1,000)")
سطح   تعدادِ مقایسه در این سطح
   1          998
   2          990
   3          996
   4          984
   5          974
   6          947
   7          870
   8          800
   9          662
  10          488
جمع         8,709   (n = 1,000)

هر سطح حدودِ 1,000 مقایسه دارد — یعنی حدودِ n. و دلیلش روشن است: در هر سطح، تکه‌ها با هم روی هم کلِ فهرست را می‌پوشانند، و ادغامِ هر تکه به اندازهٔ خودش کار دارد. پس کارِ هر سطح O(n) است، فارغ از اینکه به چند تکه شکسته شده باشد.

سطح‌های پایین‌تر کمی کمترند چون در تکه‌های کوچک، احتمالِ اینکه یک طرف زودتر تمام شود بیشتر است و باقیمانده بدونِ مقایسه کپی می‌شود. سطحِ ۱۱ هم اصلاً در جدول نیست، چون آن‌جا تکه‌ها تک‌عضوی‌اند و ادغامی در کار نیست.

می‌ماند سؤالِ دوم: چند سطح؟ هر سطح طولِ تکه‌ها را نصف می‌کند، پس تعدادِ سطح‌ها همان تعدادِ دفعاتی است که n را می‌شود نصف کرد تا به ۱ برسد.

🌱 ریشه‌اش کجاست: «چند بار می‌شود n را نصف کرد تا به ۱ برسد» تعریفِ log₂ n است، و ریشه ترمِ ۴ فصل ۸ آن را به‌عنوانِ وارونهٔ توان می‌سازد. نتیجه‌ای که آن‌جا ساخته می‌شود و این‌جا به‌کار می‌آید یک جمله است: log بی‌رحمانه کند رشد می‌کند — با هزار برابر شدنِ n، فقط حدودِ ده واحد بالا می‌رود. جدولِ عمقِ پایین دقیقاً همین را نشان می‌دهد.

🤔 اول حدس بزن: ستونِ نسبتِ مقایسه و ستونِ نسبتِ عمق را جدا حدس بزن. دو عدد بنویس، بعد جدول را ببین.

def sorted_stats(n):
    return merge_sort(shuffled[n])[1]


print("— مقایسه")
table([(n, sorted_stats(n)["comparisons"]) for n in LADDER], "مقایسه", ",d")
print("\n— عمقِ recursion")
table([(n, sorted_stats(n)["depth"]) for n in LADDER], "عمق", ",d")
— مقایسه
         n            مقایسه     نسبت به سطر قبل
     1,000             8,709                   —
     2,000            19,415                2.23
     4,000            42,781                2.20
     8,000            93,704                2.19

— عمقِ recursion
         n               عمق     نسبت به سطر قبل
     1,000                11                   —
     2,000                12                1.09
     4,000                13                1.08
     8,000                14                1.08

2.19 و رو به پایین — این امضای O(n log n) است. ترمِ ۱ فصلِ ۵ همین را در قاعده‌اش نوشته بود: «کمی بالای 2 و رو به کاهش، یعنی پابه‌پای n به‌علاوهٔ یک لایهٔ نصف‌کردن». کمی بالای 2 است چون با دو برابر شدنِ n، هم کارِ هر سطح دو برابر می‌شود و هم یک سطحِ تازه اضافه می‌شود.

و جدولِ دوم آن «یک سطحِ تازه» را با چشم نشان می‌دهد: 11، 12، 13، 14 — هر دو برابر شدنِ n دقیقاً یکی به عمق اضافه می‌کند. این همان log₂ n است، بدونِ هیچ فرمولی.

حالا مدل را با اندازه‌گیری می‌سنجیم:

import math

print(f"{'n':>8}{'مقایسه':>12}{'n × log2(n)':>16}{'نسبت':>10}")
for n in LADDER:
    got = sorted_stats(n)["comparisons"]
    model = n * math.log2(n)
    print(f"{n:>8,}{got:>12,}{model:>16,.0f}{got / model:>10.2f}")
       n      مقایسه     n × log2(n)      نسبت
   1,000       8,709           9,966      0.87
   2,000      19,415          21,932      0.89
   4,000      42,781          47,863      0.89
   8,000      93,704         103,726      0.90

نسبت در هر چهار سطر بینِ 0.87 و 0.90 می‌ماند و خیلی آرام بالا می‌رود. یعنی شمارشِ واقعی متناسب با n log₂ n است، با ضریبی کمی کمتر از یک که با بزرگ شدنِ n آرام‌آرام به یک نزدیک می‌شود. همین ماندنِ نسبت در یک بازهٔ باریک، تأییدِ مدل است — اگر مرتبه O(n²) بود این ستون با هر دو برابر شدنِ n تقریباً دو برابر می‌شد و اگر O(n) بود در هر سطر حدودِ ده درصد پایین می‌آمد؛ این‌جا بالا می‌رود، پس نزدیک‌ترین شکل n log n است.

۵. حافظه‌ای که در جدولِ مقایسه دیده نمی‌شود#

merge یک list تازه می‌سازد. این یعنی merge sort — برخلافِ دو الگوریتمِ فصلِ ۳ — در جای خودِ داده کار نمی‌کند.

print("— عضوِ کپی‌شده در کلِ ادغام‌ها (حافظهٔ کمکی)")
table([(n, sorted_stats(n)["copied"]) for n in LADDER], "عضوِ کپی‌شده", ",d")
— عضوِ کپی‌شده در کلِ ادغام‌ها (حافظهٔ کمکی)
         n      عضوِ کپی‌شده     نسبت به سطر قبل
     1,000             9,976                   —
     2,000            21,952                2.20
     4,000            47,904                2.18
     8,000           103,808                2.17

ستونِ نسبتش هم 2.2 است — یعنی کلِ کپی‌ها هم O(n log n) است. برای هزار عضو، نزدیک به ده هزار عضو کپی می‌شود: در هر یک از ده سطح، یک بار کلِ فهرست.

ولی این عددِ کل است، نه عددی که در یک لحظه در حافظه داری. در هر لحظه فقط ادغام‌های یک شاخه باز هستند، پس بیشترین حافظهٔ هم‌زمان O(n) است، نه O(n log n). این تفاوت را در گزارش باید صریح نوشت، وگرنه هزینه را چند برابر بزرگ‌تر از واقع اعلام کرده‌ای.

✅ چک کن: در تابعِ merge_sort بخشِ ۳ — و در merge بخشِ ۱، تا هر دو یکی بمانند — علامتِ <= را به < تغییر بده و جدولِ مقایسهٔ بخشِ ۴ را دوباره بگیر. (جدولِ بخشِ ۴ از merge_sort می‌آید، که حلقهٔ ادغام را داخلِ خودش دارد؛ اگر فقط merge را عوض کنی هیچ اتفاقی نمی‌افتد.) جواب همچنان با sorted یکی درمی‌آید و ستونِ نسبت هم عوض نمی‌شود — چون داده‌های ما تکراری ندارند. این تغییر بی‌خطر به‌نظر می‌رسد و نیست: فصلِ ۸ نشان می‌دهد که همین یک نویسه، روی داده‌ای که عضوِ برابر دارد، خاصیتی را از بین می‌برد که کلِ مرتب‌سازیِ چندکلیدی روی آن سوار است.

۶. یک نویسه در شرطِ حلقه#

def merge_broken(left, right):
    """اشتباهِ کلاسیک: or به‌جای and در شرطِ حلقه."""
    out = []
    i = j = 0
    while i < len(left) or j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out


try:
    merge_broken([1, 3, 5], [2, 4, 6])
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
IndexError: list index out of range

🔧 اگر کار نکرد: and می‌گوید «تا وقتی هر دو طرف عضوی دارند»، or می‌گوید «تا وقتی دستِ‌کم یکی عضوی دارد». با or، به‌محضِ اینکه یک طرف تمام شود، خطِ بعدی هنوز left[i] و right[j] را با هم مقایسه می‌کند و یکی از آن دو از فهرست بیرون زده: IndexError.

و درسِ اصلی این است که چرا دو خطِ extend بعد از حلقه لازم‌اند. حلقه عمداً زود می‌ایستد، و آن دو خط کارِ باقی‌مانده را تمام می‌کنند. اگر یکی از آن دو را حذف کنی، هیچ خطایی نمی‌گیری و بی‌صدا عضو گم می‌کنی — تنها راهِ گرفتنش مقایسهٔ len ورودی و خروجی است.

۷. و روی ساعت#

print("— merge sort (زمان)")
table([(n, 1000 * clock(lambda v=shuffled[n]: merge_sort(v), repeat=2))
       for n in LADDER], "زمان (ms)", ",.1f")
— merge sort (زمان)
         n         زمان (ms)     نسبت به سطر قبل
     1,000               3.6                   —
     2,000               8.0                2.22
     4,000              17.6                2.21
     8,000              40.5                2.30

ساعت همان 2.2 شمارنده را می‌گوید. روی این ماشین، مرتب کردنِ ۸٬۰۰۰ عضو حدودِ چهل میلی‌ثانیه شد؛ selection sort در n = 2,000 — یک‌چهارمِ این داده — بیش از صد میلی‌ثانیه می‌خواست.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ merge sort با sorted برای درستی، و با اعدادِ selection sort فصلِ ۳ برای هزینه — روی همان جنسِ ورودی و همان شمارندهٔ مقایسه. در کدام بازهٔ n؟ ۱٬۰۰۰ تا ۸٬۰۰۰؛ چون merge sort ارزان است، بازه را نسبت به فصلِ ۳ چهار برابر بالا برده‌ایم. با چند تکرار، و کمینه یا میانگین؟ جدول‌های شمارش یک اجرا و قطعی؛ جدولِ زمان دو تکرار به‌علاوهٔ گرم‌کننده، کمینه.

🤖 از دستیارت بپرس: «چرا کارِ هر سطح در merge sort مستقل از تعدادِ تکه‌های آن سطح است؟» بعد این را هم بپرس: «اگر به‌جای دو نیمه، فهرست را به چهار تکه بشکنم، مرتبه عوض می‌شود؟» — جوابِ درست باید بگوید نه، چون تعدادِ سطح‌ها log₄ n می‌شود که فقط ضریبی از log₂ n است. اگر دستیارت گفت «چهار برابر سریع‌تر می‌شود»، جدولِ عمقِ بخشِ ۴ را جلویش بگذار و بپرس چند سطح کم می‌شود.

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

کلمه تلفظ به حروف فارسی یعنی چه
merge sort مرج سورت مرتب‌سازی با شکستن به دو نیمه و ادغامِ دو نیمهٔ مرتب
divide and conquer دیوایْد اند کانکِر حلِ مسئله با شکستنش به نسخه‌های کوچک‌ترِ مستقل
auxiliary memory آگزیلیری مموری حافظه‌ای که الگوریتم علاوه بر خودِ داده لازم دارد

تمرین‌ها

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

در فصل بعد#

merge sort سریع است ولی حافظهٔ کمکی می‌خواهد. فصلِ بعد الگوریتمی می‌آورد که همان مرتبه را بدونِ ساختنِ فهرستِ تازه می‌گیرد — و بهایش را جای دیگری می‌پردازد.

روی ورودیِ تصادفی عالی است. ولی همان کد روی فهرستی که از قبل مرتب باشد به RecursionError می‌خورد، و وقتی درستش کنیم می‌بینیم مقایسه‌هایش در n = 2,000 به 1,999,000 رسیده — دقیقاً همان عددِ selection sort فصلِ ۳. بعد با یک تغییرِ یک‌خطی همان عدد به حدودِ 24,000 برمی‌گردد.

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

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