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

فصل ۶ از ۹

پیشرفت ترم
۰٪

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

سه فصل الگوریتم نوشتیم و هیچ‌کدام از n log n جلوتر نرفت. این فصل نشان می‌دهد چرا هیچ‌وقت نمی‌رود — و استدلالش هیچ ربطی به الگوریتم ندارد؛ فقط شمردن است.

بعد عددش را می‌گیریم: در n = 8,000 کمترین تعدادِ مقایسهٔ ممکن 92,193 است و merge sort ما 93,704 می‌کند. نسبتِ 1.02 — یعنی الگوریتمی که خودمان نوشتیم، دو درصد با مرزِ نظری فاصله دارد.

و آخرش الگوریتمی می‌آوریم که از این مرز رد می‌شود، چون اصلاً مقایسه نمی‌کند. اندازه می‌گیریم که کجا برنده است — ۷۱ برابر سریع‌تر از merge sort ما — و کجا ۱۹۷ برابر بازنده.

ترازویی که در هر توزین یک دستهٔ ممکن را نصف می‌کند، کنارِ قفسه‌ای از خانه‌های شماره‌دار

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

  • بگویی چرا n! ترتیبِ ممکن، مرزی برای تعدادِ مقایسه‌ها می‌سازد
  • فاصلهٔ الگوریتمِ خودت با آن مرز را حساب کنی
  • counting sort را بنویسی و بگویی چه شرطی دارد
  • با عدد بگویی آن شرط کِی به‌صرفه است و کِی فاجعه

قبل از شروع#

از فصلِ ۴: merge sort و شمارشِ مقایسه‌هایش — کدش این‌جا دوباره، فشرده، می‌آید تا فصل خودبسنده باشد.

از ترمِ ۱ فصلِ ۶: خانوادهٔ منحنی‌های رشد، و مخصوصاً اینکه log n چقدر کند بالا می‌رود.

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

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

۱. چند جوابِ ممکن وجود دارد؟#

مرتب کردن یعنی پیدا کردنِ یک ترتیبِ خاص از بینِ همهٔ ترتیب‌های ممکن. پس اولین سؤال این است: چند ترتیب ممکن است؟

import math
from itertools import permutations

for n in (3, 4, 5, 10, 20):
    print(f"n = {n:>2}   ترتیب‌های ممکن = {math.factorial(n):,}")

print("\nهمهٔ ترتیب‌های سه عضو:")
for p in permutations("abc"):
    print("  ", "".join(p))
n =  3   ترتیب‌های ممکن = 6
n =  4   ترتیب‌های ممکن = 24
n =  5   ترتیب‌های ممکن = 120
n = 10   ترتیب‌های ممکن = 3,628,800
n = 20   ترتیب‌های ممکن = 2,432,902,008,176,640,000

همهٔ ترتیب‌های سه عضو:
   abc
   acb
   bac
   bca
   cab
   cba

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

🌱 ریشه‌اش کجاست: «چند جور می‌شود n چیز را پشتِ سرِ هم چید» همان جایگشت است و در ریشه ترمِ ۶ فصل ۱ با اصلِ ضرب ساخته می‌شود: برای جای اول n انتخاب داری، برای جای دوم n-1 تا، و همین‌طور تا آخر. حاصل‌ضربشان می‌شود n! — و همان فصل نشان می‌دهد این عدد چقدر زود از هر عددِ آشنایی بزرگ‌تر می‌شود.

۲. هر مقایسه چه چیزی به تو می‌دهد#

حالا سؤالِ دوم: یک مقایسه چقدر از این ابهام را کم می‌کند؟

جوابش «کمی» نیست، یک عددِ دقیق است. هر مقایسه دو جوابِ ممکن دارد — بله یا نه. پس بعد از k مقایسه، حداکثر 2^k مسیرِ متفاوت طی کرده‌ای، و هر مسیر فقط می‌تواند به یک ترتیب ختم شود.

پس برای اینکه الگوریتم بتواند هر n! ترتیب را از هم تشخیص بدهد، باید 2^k دستِ‌کم به n! برسد.

print(f"{'مقایسه':>8}{'حالتِ قابلِ تفکیک (2^k)':>26}{'برای ۳ عضو کافی است؟':>24}")
for k in range(1, 4):
    print(f"{k:>8}{2 ** k:>26,}{str(2 ** k >= math.factorial(3)):>24}")
  مقایسه   حالتِ قابلِ تفکیک (2^k)    برای ۳ عضو کافی است؟
       1                         2                   False
       2                         4                   False
       3                         8                    True

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

همین شرط را برای n بزرگ می‌نویسیم: از 2^k ≥ n! نتیجه می‌شود که k دستِ‌کم log₂(n!) است.

def log2_factorial(n):
    """log2(n!) بدونِ ساختنِ خودِ n! — جمعِ لگاریتم‌ها."""
    return sum(math.log2(i) for i in range(2, n + 1))


for n in (10, 100, 1_000):
    print(f"n = {n:>5}   مرزِ پایین = {math.ceil(log2_factorial(n)):>7,} مقایسه"
          f"   ·   n × log2(n) = {n * math.log2(n):>9,.0f}")
n =    10   مرزِ پایین =      22 مقایسه   ·   n × log2(n) =        33
n =   100   مرزِ پایین =     525 مقایسه   ·   n × log2(n) =       664
n =  1000   مرزِ پایین =   8,530 مقایسه   ·   n × log2(n) =     9,966

ستونِ دوم و سوم همیشه در همان حدودِ هم می‌مانند — نسبتشان از 0.66 به 0.86 می‌رود و به یک نزدیک‌تر می‌شود. یعنی log₂(n!) و n log₂ n از یک خانواده‌اند و همان O(n log n) را می‌گویند. پس مرزِ پایینِ مرتب‌سازیِ مقایسه‌ای از مرتبهٔ n log n است، و این را با شمردن ثابت کردیم، نه با اندازه‌گیری.

۳. الگوریتمِ ما چقدر با مرز فاصله دارد؟#

مرزِ پایین می‌گوید «کمتر از این ممکن نیست». ولی نمی‌گوید کسی به آن می‌رسد. حالا اندازه می‌گیریم.

🤔 اول حدس بزن: به‌نظرت merge sort چند برابرِ مرزِ پایین مقایسه می‌کند؟ یک عدد بنویس — دو برابر؟ ده برابر؟ — بعد جدول را ببین.

def merge_sort(values):
    """merge sort فصلِ ۴، فشرده، با شمارشِ مقایسه."""
    comparisons = 0

    def go(vals):
        nonlocal comparisons
        if len(vals) <= 1:
            return vals
        mid = len(vals) // 2
        left, right = go(vals[:mid]), go(vals[mid:])
        out = []
        i = j = 0
        while i < len(left) and j < len(right):
            comparisons += 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:])
        return out

    return go(list(values)), comparisons


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}
print("merge sort درست کار می‌کند؟",
      merge_sort(shuffled[1_000])[0] == sorted(shuffled[1_000]))
print()
print(f"{'n':>8}{'مرزِ پایین':>14}{'merge sort':>14}{'نسبت':>10}")
for n in LADDER:
    floor_ = math.ceil(log2_factorial(n))
    got = merge_sort(shuffled[n])[1]
    print(f"{n:>8,}{floor_:>14,}{got:>14,}{got / floor_:>10.2f}")
merge sort درست کار می‌کند؟ True

       n    مرزِ پایین    merge sort      نسبت
   1,000         8,530         8,709      1.02
   2,000        19,053        19,415      1.02
   4,000        42,100        42,781      1.02
   8,000        92,193        93,704      1.02

1.02 در هر چهار سطر. یعنی merge sort — الگوریتمی که خودمان در یک فصل نوشتیم — دو درصد با بهترین چیزی که نظریه اجازه می‌دهد فاصله دارد، و این فاصله با بزرگ‌تر شدنِ n باز نمی‌شود.

این جدول دو خبر دارد. خبرِ خوب اینکه merge sort تقریباً بهینه است. خبرِ مهم‌تر اینکه دنبالِ الگوریتمِ مقایسه‌ایِ بهتر گشتن، اتلافِ وقت است — حتی یک الگوریتمِ کامل و بی‌نقص هم فقط دو درصد بهتر می‌شود.

و همین‌جا یک بدهیِ ترمِ ۱ پرداخت می‌شود. فصلِ ۷ آن ترم Θ و Ω را در چند خط تعریف کرد و از آن به بعد هیچ‌جا به‌کار نرفتند — چون تا امروز فقط سقف داشتیم. این تنها جای کلِ دوره است که هر دو نصفه را با هم در دست داری: فصلِ ۴ سقفِ merge sort را داد (O(n log n)، با جدول) و بخشِ ۲ کفِ هر الگوریتمِ مقایسه‌ای را (Ω(n log n)، با شمردن). وقتی سقف و کف یکی باشند، دیگر می‌شود Θ نوشت: مرتب‌سازیِ مقایسه‌ای Θ(n log n) است، و ستونِ 1.02 نشان می‌دهد که این فقط یک ادعای نمادین نیست — فاصلهٔ سقف و کف روی داده‌های واقعیِ ما دو درصد است.

پس اگر می‌خواهی واقعاً سریع‌تر شوی، باید از بازیِ مقایسه بیرون بروی.

۴. الگوریتمی که هیچ دو عضوی را با هم مقایسه نمی‌کند#

فرض کن می‌دانی همهٔ عضوها عددِ صحیحِ بینِ 0 و k-1 هستند. آن‌وقت لازم نیست بپرسی کدام بزرگ‌تر است؛ فقط باید بشماری هر عدد چند بار آمده.

def counting_sort(values, k):
    """بدونِ حتی یک مقایسه بینِ دو عضو. شرط: هر عضو عددِ صحیحِ ۰ تا k-1."""
    counts = [0] * k
    for v in values:
        counts[v] += 1                   # فقط شمردن، نه مقایسه
    out = []
    for value in range(k):
        out.extend([value] * counts[value])
    return out


small = [5, 2, 9, 2, 0, 5, 5]
print("ورودی :", small)
print("خروجی :", counting_sort(small, 10))
print("با sorted یکی است؟", counting_sort(small, 10) == sorted(small))
ورودی : [5, 2, 9, 2, 0, 5, 5]
خروجی : [0, 2, 2, 5, 5, 5, 9]
با sorted یکی است؟ True

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

پس مرزِ پایینِ بخشِ ۲ به این الگوریتم اصلاً مربوط نیست. آن استدلال دربارهٔ الگوریتم‌هایی بود که تنها ابزارشان مقایسه است. مرز باطل نشد؛ این الگوریتم از قلمروش بیرون است.

هزینه‌اش را می‌شماریم: n بار شمردن، k بار پیمودنِ خانه‌ها، و n بار نوشتن.

🤔 اول حدس بزن: با ثابت ماندنِ k و دو برابر شدنِ n، ستونِ نسبت چه می‌شود؟ و با ثابت ماندنِ n و دو برابر شدنِ k چه؟ دو عدد بنویس.

def counting_steps(values, k):
    """گام‌های واقعیِ counting sort — شمرده، نه حساب‌شده."""
    counts = [0] * k
    steps = 0
    for v in values:
        counts[v] += 1
        steps += 1
    for value in range(k):
        steps += 1 + counts[value]
    return steps


K_SMALL = 256
COUNT_LADDER = [25_000, 50_000, 100_000, 200_000]
bytes_ = {n: [rng.randrange(K_SMALL) for _ in range(n)] for n in COUNT_LADDER}
print("جواب با sorted یکی است؟",
      counting_sort(bytes_[25_000], K_SMALL) == sorted(bytes_[25_000]))
print("\n— گام‌ها، با k ثابت روی ۲۵۶")
table([(n, counting_steps(bytes_[n], K_SMALL)) for n in COUNT_LADDER], "گام", ",d")
جواب با sorted یکی است؟ True

— گام‌ها، با k ثابت روی ۲۵۶
         n               گام     نسبت به سطر قبل
    25,000            50,256                   —
    50,000           100,256                1.99
   100,000           200,256                2.00
   200,000           400,256                2.00
FIXED = bytes_[100_000]
print("— گام‌ها، با n ثابت روی ۱۰۰٬۰۰۰ و k دو برابر شونده")
print(f"{'k':>12}{'گام':>14}{'نسبت به سطر قبل':>20}")
previous = None
for k in (200_000, 400_000, 800_000, 1_600_000):
    steps = counting_steps(FIXED, k)
    ratio = "—" if not previous else f"{steps / previous:.2f}"
    print(f"{k:>12,}{steps:>14,}{ratio:>20}")
    previous = steps
— گام‌ها، با n ثابت روی ۱۰۰٬۰۰۰ و k دو برابر شونده
           k           گام     نسبت به سطر قبل
     200,000       400,000                   —
     400,000       600,000                1.50
     800,000     1,000,000                1.67
   1,600,000     1,800,000                1.80

جدولِ اول 2.00 می‌دهد — با k ثابت، counting sort خطی است. هیچ logی در کار نیست.

جدولِ دوم چیزِ مهم‌تری می‌گوید: با ثابت ماندنِ n، بالا بردنِ k هم کار را زیاد می‌کند، و نسبتش رفته‌رفته به 2 نزدیک‌تر می‌شود — یعنی هرچه k بزرگ‌تر شود، k بخشِ غالبِ هزینه می‌شود و n دیگر تعیین‌کننده نیست. هزینه O(n + k) است و هیچ‌کدام از این دو حرف را نمی‌شود انداخت.

۵. حالا هر دو طرفِ معامله را اندازه بگیر#

big = [rng.randrange(K_SMALL) for _ in range(100_000)]
print("هر سه یک جواب می‌دهند؟",
      counting_sort(big, K_SMALL) == sorted(big) == merge_sort(big)[0])
mine = clock(lambda: merge_sort(big), repeat=2)
counting = clock(lambda: counting_sort(big, K_SMALL), repeat=3)
builtin = clock(lambda: sorted(big), repeat=3)
print(f"\nn = 100,000 · k = 256")
print(f"  merge sortِ ما (پایتونِ خالص): {1000 * mine:>8,.1f} ms")
print(f"  counting sort (پایتونِ خالص) : {1000 * counting:>8,.1f} ms")
print(f"  sorted (نوشته‌شده به C)       : {1000 * builtin:>8,.1f} ms")
print(f"\n  counting در برابرِ merge sortِ ما: {mine / counting:>5,.1f} برابر سریع‌تر")
print(f"  counting در برابرِ sorted        : {builtin / counting:>5,.1f} برابر سریع‌تر")
هر سه یک جواب می‌دهند؟ True

n = 100,000 · k = 256
  merge sortِ ما (پایتونِ خالص):    281.0 ms
  counting sort (پایتونِ خالص) :      3.9 ms
  sorted (نوشته‌شده به C)       :      8.9 ms

  counting در برابرِ merge sortِ ما:  71.6 برابر سریع‌تر
  counting در برابرِ sorted        :   2.3 برابر سریع‌تر

در مقایسهٔ منصفانه — دو الگوریتم، هر دو در پایتونِ خالص — counting sort حدودِ هفتاد برابر جلوتر است. این نتیجهٔ عوض شدنِ مرتبه است: O(n + k) در برابرِ O(n log n).

ولی نسبتِ دومی فقط 2.3 است، و همین عدد صادقانه‌ترین سطرِ این فصل است: الگوریتمی با مرتبهٔ بهتر، در برابرِ sorted که مرتبه‌اش بدتر است، فقط دو برابر جلو می‌افتد — چون sorted به زبانِ C نوشته شده و ثابتش ده‌ها برابر کوچک‌تر است. این همان ثابتِ پنهانِ ترمِ ۱ فصلِ ۹ است و فصلِ ۸ کاملاً بازش می‌کند.

حالا شرط را بشکن: همان n، ولی بازهٔ مقادیر خیلی بازتر.

K_WIDE = 5_000_000
wide = [rng.randrange(K_WIDE) for _ in range(20_000)]
print("جواب با sorted یکی است؟", counting_sort(wide, K_WIDE) == sorted(wide))
slow = clock(lambda: counting_sort(wide, K_WIDE), repeat=2)
ref = clock(lambda: sorted(wide), repeat=3)
print(f"\nn = 20,000 · k = 5,000,000")
print(f"  counting sort: {1000 * slow:>8,.1f} ms")
print(f"  sorted       : {1000 * ref:>8,.1f} ms")
print(f"  نسبت         : {slow / ref:>8,.0f} برابر به‌نفعِ sorted")
print(f"  حافظهٔ آرایهٔ شمارش: {sys.getsizeof([0] * K_WIDE) / 1024 / 1024:,.1f} مگابایت")
جواب با sorted یکی است؟ True

n = 20,000 · k = 5,000,000
  counting sort:    516.4 ms
  sorted       :      2.6 ms
  نسبت         :      197 برابر به‌نفعِ sorted
  حافظهٔ آرایهٔ شمارش: 38.1 مگابایت

همان الگوریتم، همان جوابِ درست، و این بار ۱۹۷ برابر بازنده — چون برای بیست هزار عدد، پنج میلیون خانه ساخت و همه‌شان را پیمود. و حافظه‌اش هم از داده‌ای که مرتب می‌کند خیلی بزرگ‌تر شد.

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

۶. وقتی شرط برقرار نیست#

try:
    counting_sort([3, 1, 2], 2)
except IndexError as err:
    print(f"{type(err).__name__}: {err}")

try:
    counting_sort([1.5, 0.5], 3)
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
IndexError: list index out of range
TypeError: list indices must be integers or slices, not float

🔧 اگر کار نکرد: دو پیام، دو شکستِ شرط. IndexError یعنی عضوی بزرگ‌تر یا مساویِ k در داده بوده — k را از خودِ داده حساب کن (max(values) + 1)، نه از حدس. TypeError یعنی عضوها عددِ صحیح نیستند؛ counting sort روی اعشار اصلاً معنا ندارد، چون بینِ هر دو عددِ اعشاری بی‌نهایت عددِ دیگر هست و «خانهٔ شماره‌دار» بی‌معنا می‌شود.

هر دو خطا خبرِ خوبی‌اند. بدترین حالت این بود که کد بی‌صدا جوابِ غلط بدهد.

✅ چک کن: k را از داده حساب کن — counting_sort(values, max(values) + 1) — و روی [5, 2, 9, 2, 0, 5, 5] امتحانش کن. باید همان [0, 2, 2, 5, 5, 5, 9] را بدهد. حالا عددِ 9 را به 900000 تغییر بده و قبل از اجرا حساب کن آرایهٔ شمارش چند خانه می‌شود. اگر جوابت را نوشتی، فهمیده‌ای چرا k بخشی از صورتِ مسئله است، نه یک جزئیاتِ پیاده‌سازی.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ مرزِ پایینِ شمارشی با مقایسه‌های واقعیِ merge sort؛ و بعد counting sort با merge sort و با sorted، هر سه با جوابِ تأییدشدهٔ برابر. در کدام بازهٔ n؟ ۱٬۰۰۰ تا ۸٬۰۰۰ برای جدولِ مرز، ۲۵٬۰۰۰ تا ۲۰۰٬۰۰۰ برای گام‌های counting sort، و دو مقایسهٔ زمانی در n = 100,000 با k = 256 و در n = 20,000 با k = 5,000,000. با چند تکرار، و کمینه یا میانگین؟ جدول‌های شمارش یک اجرا و قطعی؛ مقایسه‌های زمانی دو تا سه تکرار به‌علاوهٔ گرم‌کننده، کمینه، و هر سه روی همان داده.

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

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

کلمه تلفظ به حروف فارسی یعنی چه
lower bound لوئر باوند کمترین کاری که هیچ الگوریتمی از آن پایین‌تر نمی‌رود
comparison sort کامپریزن سورت مرتب‌سازی‌ای که تنها ابزارش پرسیدنِ «کدام بزرگ‌تر است؟» است
counting sort کانتینگ سورت مرتب‌سازی با شمردنِ تکرارِ هر مقدار، بدونِ هیچ مقایسه‌ای
permutation پرمیوتیشن یکی از ترتیب‌های ممکنِ یک مجموعه

تمرین‌ها

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

در فصل بعد#

این فصل گفت مرتب کردن گران است — n log n، و کمتر از آن ممکن نیست. پس ارزشش را دارد؟

فصلِ بعد نشان می‌دهد داشتنِ یک فهرستِ مرتب چه چیزی می‌خرد: پرسشِ «هست یا نه؟» که با جست‌وجوی خطی در n = 8,000 حدودِ ۴٬۰۰۰ گام می‌خواست، با ۱۳ گام جواب می‌گیرد. و بعد نقطهٔ سربه‌سرش را حساب می‌کنیم: از q = 24 پرسش به بعد، مرتب کردن به‌صرفه است.

و همان‌جا بدترین ردهٔ خطا را هم می‌بینیم: نسخه‌ای از binary search که هیچ خطایی نمی‌دهد و برای ۴۸۹ عضو از ۱٬۰۰۰ عضوِ موجود می‌گوید «پیدا نشد».

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

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