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

فصل ۲ از ۹

پیشرفت ترم
۰٪

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

فصلِ قبل تابعی داشت که در هر فراخوانی یک بار خودش را صدا می‌زد. این فصل تابعی می‌سازد که دو بار صدا می‌زند — و همان یک تفاوت کافی است تا یک ورودیِ کوچکِ ۲۴تایی ۱۵۰٬۰۴۹ فراخوانی بخواهد.

بعد می‌فهمیم چرا: در آن درخت، fib(2) دقیقاً ۲۸٬۶۵۷ بار حساب می‌شود، هر بار از صفر. با یک dict جلوی این تکرار را می‌گیریم و همان ۱۵۰٬۰۴۹ به ۴۷ می‌رسد. در n = 30 فاصله بازتر است: ۲٬۶۹۲٬۵۳۷ در برابرِ ۵۹.

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

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

  • درختِ فراخوانیِ یک recursion را بکشی و گره‌هایش را بشماری
  • تشخیص بدهی کِی یک recursion دارد کارِ تکراری انجام می‌دهد
  • با یک dict دستی، memoisation بنویسی و اثرش را با شمارش نشان بدهی
  • بگویی چرا حتی نسخهٔ سریع هم یک هزینهٔ حافظه دارد که در جدولِ زمان دیده نمی‌شود

قبل از شروع#

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

از ترمِ ۱ فصلِ ۵: قاعدهٔ خواندنِ ستونِ نسبت — و مخصوصاً آخرین سطرش: «بزرگ‌تر از 4 و رو به انفجار: نسبت خودش هم با n بزرگ می‌شود». این فصل اولین جایی است که آن سطر را در یک کدِ واقعی می‌بینی.

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

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

۱. یک تابع، و دو فراخوانی به‌جای یکی#

دنبالهٔ فیبوناچی خودش را در تعریفِ خودش به‌کار می‌برد: هر عدد جمعِ دو عددِ قبلی است، و دو عددِ اول ۰ و ۱ هستند. این تعریف را مو به مو به کد تبدیل می‌کنیم.

def fib(n):
    """تعریفِ خودِ دنباله، مو به مو."""
    if n < 2:                            # حالتِ پایه
        return n
    return fib(n - 1) + fib(n - 2)       # دو گامِ بازگشتی، نه یکی


def fib_traced(n, depth=0):
    """همان تابع، با چاپِ درختِ فراخوانی."""
    print("  " * depth + f"fib({n})")
    if n < 2:
        return n
    return fib_traced(n - 1, depth + 1) + fib_traced(n - 2, depth + 1)


print("fib(0..9):", [fib(k) for k in range(10)])
print()
fib_traced(5)
fib(0..9): [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1)
    fib(2)
      fib(1)
      fib(0)
  fib(3)
    fib(2)
      fib(1)
      fib(0)
    fib(1)

این شکل یک درخت است و اسمش هم همین است: درختِ فراخوانی. هر گره یک فراخوانی است و فرزندانش فراخوانی‌هایی که خودش راه انداخته.

حالا با چشم بشمار: fib(3) دو بار در این درخت هست و fib(2) سه بار. هر کدامشان هم شاخه‌های خودشان را دوباره از صفر می‌سازند. هیچ چیزی نگه داشته نمی‌شود، چون هیچ‌جا گفته نشده نگه داشته شود.

۲. شمردنِ گره‌ها#

🤔 اول حدس بزن: اگر n را دو برابر کنیم، تعدادِ فراخوانی چند برابر می‌شود؟ یک عدد بنویس، بعد جدول را ببین. (اگر گفتی «۲ یا ۴»، درست همان جایی هستی که این فصل می‌خواهد.)

def fib_calls(n):
    """جواب، و تعدادِ فراخوانی‌ای که برای رسیدن به آن انجام شد."""
    calls = 0

    def go(k):
        nonlocal calls
        calls += 1
        if k < 2:
            return k
        return go(k - 1) + go(k - 2)

    return go(n), calls


print("fib(5) =", fib_calls(5)[0], "· فراخوانی:", fib_calls(5)[1])
table([(n, fib_calls(n)[1]) for n in (3, 6, 12, 24)], "فراخوانی", ",d")
fib(5) = 5 · فراخوانی: 15
         n          فراخوانی     نسبت به سطر قبل
         3                 5                   —
         6                25                5.00
        12               465               18.60
        24           150,049              322.69

5.00، بعد 18.60، بعد 322.69. ستونِ نسبت به عددی نمی‌رسد که آن‌جا بماند؛ خودش هم منفجر می‌شود. این دقیقاً همان امضایی است که ترمِ ۱ فصلِ ۵ برای رشدِ نمایی نوشت، و تنها مرتبه‌ای است که این شکل را دارد.

نردبانِ ضربی این‌جا حرفش را زد، ولی نردبانِ جمعی چیزِ دیگری هم نشان می‌دهد:

table([(n, fib_calls(n)[1]) for n in (20, 21, 22, 23, 24)], "فراخوانی", ",d")
         n          فراخوانی     نسبت به سطر قبل
        20            21,891                   —
        21            35,421                1.62
        22            57,313                1.62
        23            92,735                1.62
        24           150,049                1.62

هر بار که فقط یکی به n اضافه می‌شود، کار در 1.62 ضرب می‌شود — و این عدد در هر چهار سطر یکی است. رشدِ نمایی همین است: در هر قدم، ضرب در یک عددِ ثابت. پایه‌اش این‌جا اتفاقاً 2 نیست، 1.62 است؛ ولی شکلِ رشد همان است و همان‌قدر هم بی‌رحم.

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

۳. چرا: همان کار، بارها#

عدد 150,049 از جایی نیامده. آن را می‌شود شکافت.

from collections import Counter


def fib_who(n):
    """چند بار هر fib(k) صدا زده می‌شود."""
    seen = Counter()

    def go(k):
        seen[k] += 1
        if k < 2:
            return k
        return go(k - 1) + go(k - 2)

    go(n)
    return seen


counts = fib_who(24)
print("در fib(24):")
for k in (24, 23, 22, 20, 15, 10, 5, 2):
    print(f"  fib({k:>2}) صدا زده شد: {counts[k]:>6,} بار")
در fib(24):
  fib(24) صدا زده شد:      1 بار
  fib(23) صدا زده شد:      1 بار
  fib(22) صدا زده شد:      2 بار
  fib(20) صدا زده شد:      5 بار
  fib(15) صدا زده شد:     55 بار
  fib(10) صدا زده شد:    610 بار
  fib( 5) صدا زده شد:  6,765 بار
  fib( 2) صدا زده شد: 28,657 بار

fib(2) جوابش همیشه 1 است و ۲۸٬۶۵۷ بار از صفر حساب می‌شود.

منشأِ انفجار همین است، نه خودِ recursion. تابعِ فصلِ ۱ هم recursion داشت و خطی درآمد، چون هر فراخوانی مسئلهٔ تازه‌ای حل می‌کرد. این‌جا شاخهٔ چپ و شاخهٔ راست بخشِ بزرگی از کارشان مشترک است و هیچ‌کدام از دیگری خبر ندارد.

۴. memoisation: هر جواب فقط یک بار#

راهِ حل به اندازهٔ مسئله ساده است: هر جوابی که حساب شد، در یک dict نگه دار؛ قبل از حساب کردن، اول آن‌جا را نگاه کن. اسمِ این کار memoisation است و کلِ ابزارش یک dict است.

💡 نکته: پایتون ابزارِ آماده‌ای هم دارد که همین کار را خودکار می‌کند. این دوره عمداً سراغش نمی‌رود و آن را دستی می‌نویسد، چون درسِ این فصل خودِ dict و خودِ شمارش است، نه یک تزئینِ آماده. آن ابزار موضوعِ دورهٔ داربست است.

sys.setrecursionlimit(6_000)             # همان احتیاطِ فصلِ ۱


def fib_memo(n, memo=None):
    """همان تعریف، فقط جوابِ هر k یک بار حساب و در dict نگه داشته می‌شود."""
    if memo is None:
        memo = {}
    if n in memo:                        # قبلاً حسابش کرده‌ایم
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


def fib_memo_calls(n):
    """تعدادِ فراخوانیِ نسخهٔ memo، و بیشترین عمقی که به آن رسید."""
    calls = 0
    deepest = 0

    def go(k, memo, depth):
        nonlocal calls, deepest
        calls += 1
        deepest = max(deepest, depth)
        if k in memo:
            return memo[k]
        if k < 2:
            return k
        memo[k] = go(k - 1, memo, depth + 1) + go(k - 2, memo, depth + 1)
        return memo[k]

    return go(n, {}, 1), calls, deepest


print("جوابِ دو نسخه یکی است؟", fib(24) == fib_memo(24))
print("در n = 24  ·  با memo:", fib_memo_calls(24)[1],
      "· بدونِ memo:", f"{fib_calls(24)[1]:,}")
print("در n = 30  ·  با memo:", fib_memo_calls(30)[1],
      "· بدونِ memo:", f"{fib_calls(30)[1]:,}")
جوابِ دو نسخه یکی است؟ True
در n = 24  ·  با memo: 47 · بدونِ memo: 150,049
در n = 30  ·  با memo: 59 · بدونِ memo: 2,692,537

۵۹ در برابرِ ۲٬۶۹۲٬۵۳۷ — بیش از چهل‌وپنج هزار برابر کمتر، با جوابِ کاملاً یکسان. و به سطرِ اول دقت کن: تفاوت با بزرگ‌تر شدنِ n بازتر می‌شود، چون یکی خطی است و دیگری نمایی.

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

MEMO = [100, 200, 400, 800]
table([(n, fib_memo_calls(n)[1]) for n in MEMO], "فراخوانی", ",d")
         n          فراخوانی     نسبت به سطر قبل
       100               199                   —
       200               399                2.01
       400               799                2.00
       800             1,599                2.00

2.00 — یعنی O(n). از نمایی به خطی، فقط با یک dict. و منطقش را می‌شود در یک جمله نوشت: هر k بینِ ۰ و n دقیقاً یک بار واقعاً حساب می‌شود؛ بقیهٔ فراخوانی‌ها فقط از dict می‌خوانند.

۵. هزینه‌ای که در جدولِ فراخوانی دیده نمی‌شود#

نسخهٔ memo رایگان نیست. دو چیز نگه می‌دارد: خودِ dict، و عمقِ call stack.

table([(n, fib_memo_calls(n)[2]) for n in MEMO], "بیشترین عمق", ",d")
         n       بیشترین عمق     نسبت به سطر قبل
       100               100                   —
       200               200                2.00
       400               400                2.00
       800               800                2.00

عمق دقیقاً برابرِ n است و ستونِ نسبتش 2.00. یعنی حافظه‌ای که این تابع مصرف می‌کند با n خطی بالا می‌رود — و برخلافِ زمان، این هزینه سقفِ سخت دارد، چون call stack سقف دارد.

def fib_loop(n):
    """همان دنباله، بدونِ هیچ فراخوانی و بدونِ هیچ عمقی."""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


print("سه نسخه یک جواب می‌دهند؟", fib(24) == fib_memo(24) == fib_loop(24))
print("تعدادِ رقم‌های fib(10,000):", len(str(fib_loop(10_000))))
try:
    fib_memo(10_000)
except RecursionError as err:
    print(f"{type(err).__name__}: {err}")
سه نسخه یک جواب می‌دهند؟ True
تعدادِ رقم‌های fib(10,000): 2090
RecursionError: maximum recursion depth exceeded

حلقه fib(10,000) را می‌دهد — عددی با ۲٬۰۹۰ رقم — و نسخهٔ memo روی همان ورودی می‌شکند. نه چون کند است؛ چون عمیق است. memoisation مرتبهٔ زمان را درست کرد و به مرتبهٔ حافظه دست نزد.

✅ چک کن: MEMO را به [50, 100, 200, 400] ببر و هر دو جدولِ این بخش را دوباره بگیر. ستونِ نسبتِ عمق باید دقیقاً 2.00 بماند و ستونِ نسبتِ فراخوانی 2.01 یا 2.00 — چون تعدادِ فراخوانی 2n - 1 است و آن «منهای یک» در اندازه‌های کوچک‌تر خودش را در رقمِ دوم نشان می‌دهد. سطرِ اولِ جدولِ عمق باید 50 شود. اگر عمق ثابت ماند، احتمالاً depth + 1 را جایی depth نوشته‌ای و شمارنده اصلاً بالا نمی‌رود.

۶. دو اشتباهی که در نوشتنِ memo پیش می‌آید#

def count_no_put(n):
    """اشتباهِ اول: از memo می‌خواند ولی هیچ‌وقت چیزی در آن نمی‌گذارد."""
    calls = 0

    def go(k, memo):
        nonlocal calls
        calls += 1
        if k in memo:
            return memo[k]
        if k < 2:
            return k
        return go(k - 1, memo) + go(k - 2, memo)

    return go(n, {}), calls


answer, calls = count_no_put(24)
print("جوابش درست است؟", answer == fib(24))
print("فراخوانی با این «memo» :", f"{calls:,}")
print("فراخوانی بدونِ memo اصلاً:", f"{fib_calls(24)[1]:,}")


def fib_memo_broken(n, memo):
    """اشتباهِ دوم: بدونِ «اگر هست» مستقیم از memo می‌خواند."""
    if n < 2:
        return n
    return memo[n - 1] + memo[n - 2]


try:
    fib_memo_broken(10, {})
except KeyError as err:
    print(f"{type(err).__name__}: {err}")
جوابش درست است؟ True
فراخوانی با این «memo» : 150,049
فراخوانی بدونِ memo اصلاً: 150,049
KeyError: 9

🔧 اگر کار نکرد: اشتباهِ اول هیچ پیامی ندارد و بدترینشان است. کد if k in memo را دارد، جوابِ درست می‌دهد، و دقیقاً همان ۱۵۰٬۰۴۹ فراخوانیِ نسخهٔ بدونِ memo را انجام می‌دهد — چون memo هیچ‌وقت پر نمی‌شود. تنها راهِ گرفتنش همین است: شمارنده بگذار. اگر شمارنده نداشتی، فقط می‌گفتی «سریع نشد» و دنبالِ دلیلِ اشتباه می‌گشتی.

اشتباهِ دوم صریح است: KeyError: 9 یعنی سراغِ کلیدِ 9 رفته‌ای و آن‌جا نبوده. memo یک cache است، نه یک جدولِ آماده — قبل از خواندن باید یا مطمئن شوی هست، یا با .get جوابِ نبودنش را هم پیش‌بینی کنی.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ سه نسخه از یک تابعِ واحد — recursion ساده، recursion با memo، و حلقه — با جوابِ تأییدشدهٔ برابر. در کدام بازهٔ n؟ ۳ تا ۳۰ برای نسخهٔ بدونِ memo (بالاتر از آن در چند دقیقه هم تمام نمی‌شود) و ۱۰۰ تا ۸۰۰ برای نسخهٔ memo، که سقفش را عمقِ call stack تعیین کرده. با چند تکرار، و کمینه یا میانگین؟ یک اجرا برای همه؛ هر عددِ این فصل یک شمارش است، نه یک زمان — و شمارش قطعی است.

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

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

کلمه تلفظ به حروف فارسی یعنی چه
call tree کال‌تری درختِ همهٔ فراخوانی‌هایی که یک فراخوانی راه می‌اندازد
memoisation مموایزیشن نگه داشتنِ جوابِ هر ورودی تا دوباره حساب نشود
overlapping subproblems اورلپینگ ساب‌پرابلمز زیرمسئله‌هایی که بارها در درختِ فراخوانی تکرار می‌شوند

تمرین‌ها

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

در فصل بعد#

دو فصل شد که دربارهٔ خودِ recursion حرف زدیم. از فصلِ بعد سراغِ کاری می‌رویم که recursion در آن واقعاً برنده است — ولی اول باید ببینیم بدونش چه شکلی است.

فصلِ بعد دو مرتب‌سازی را با دست انجام می‌دهد و مقایسه‌هایشان را می‌شمارد. هر دو O(n²) هستند: در n = 2,000 یکی 1,999,000 مقایسه می‌کند و دیگری 1,022,176. ولی وقتی ورودی از پیش مرتب باشد، دومی به 1,999 می‌افتد و ستونِ نسبتش 2.00 می‌شود — و اولی هنوز همان 1,999,000 است.

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

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