الگوریتمِ بدتری که در اندازهٔ واقعیِ تو برنده است

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

دو الگوریتم برای یک مسئلهٔ واحد می‌نویسیم. یکی حلقهٔ تودرتوی O(n²) است و دیگری مرتبهٔ خیلی بهتری دارد — ولی یک سربارِ راه‌اندازیِ سنگین می‌پردازد که به n هیچ ربطی ندارد.

در شمارشِ عملیات، نقطهٔ تقاطعشان دقیقاً n = 449 است و این عدد روی هر ماشینی همین است. روی ساعت، تقاطع در n = 550 افتاد — و آن عدد مالِ همین ماشین است.

زیرِ آن نقطه، الگوریتمِ «بدتر» برنده است. و اگر nِ واقعیِ تو زیرِ آن نقطه باشد، انتخابِ الگوریتمِ «بهتر» یک اشتباهِ مهندسی است، نه یک تصمیمِ اصولی.

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

• ثابتِ پنهانِ پشتِ یک نماد O(...) را با اندازه‌گیری بیرون بکشی
• نقطهٔ تقاطعِ دو الگوریتم را پیدا کنی، هم در شمارش و هم در زمان
• بگویی چرا این دو عدد یکی نیستند
• nِ واقعیِ خودت را بخشی از صورتِ مسئله بدانی، نه یک جزئیاتِ فرعی
• وقتی هزینه دو اندازه دارد، دو نردبان بسازی — یکی را ثابت بگیری و دیگری را دو برابر کنی

قبل از شروع#

از فصلِ ۷: ثابت‌ها که Big-O نمی‌بیندشان. از فصلِ ۵: آماده‌سازیِ ثابت و اینکه چطور در nهای کوچک غالب می‌شود.

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

۱. یک مسئله، دو راه#

مسئله: در فهرستی از کدهای محصول، چند جفت کد وجود دارد که مجموعشان دقیقاً برابرِ یک عددِ هدف باشد؟

راهِ اول هر جفت را می‌بیند. راهِ دوم اول یک جدولِ شمارش به‌اندازهٔ کلِ بازهٔ کدها می‌سازد و بعد یک بار رویش می‌رود — پس هزینه‌اش به n تقریباً بی‌ربط است و به بزرگیِ بازه بند است.

LIMIT = 100_000          # کدها عددی بینِ ۰ و LIMIT منهای یک هستند
TARGET = 90_000


def pairs_double_loop(values, target):
    """هر جفت را می‌بیند."""
    found = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] + values[j] == target:
                found += 1
    return found


def pairs_by_bucket(values, target):
    """اول یک جدولِ شمارش به‌اندازهٔ کلِ بازهٔ کدها می‌سازد، بعد یک بار رویش می‌رود."""
    counts = [0] * LIMIT
    for v in values:
        counts[v] += 1
    found = 0
    for v in range(LIMIT):
        w = target - v
        if w < v or w < 0 or w >= LIMIT:
            continue
        if w == v:
            found += counts[v] * (counts[v] - 1) // 2
        else:
            found += counts[v] * counts[w]
    return found


rng = random.Random(SEED)
sample = rng.choices(range(LIMIT), k=2_000)
a = pairs_double_loop(sample, TARGET)
b = pairs_by_bucket(sample, TARGET)
print("جوابِ حلقهٔ تودرتو:", a)
print("جوابِ جدولِ شمارش :", b)
print("دو جواب یکی‌اند؟  ", a == b)

جوابِ حلقهٔ تودرتو: 14
جوابِ جدولِ شمارش : 14
دو جواب یکی‌اند؟   True

آن سطرِ آخر اختیاری نیست. تا وقتی دو نسخه جوابِ یکسان ندهند، مقایسهٔ سرعتشان هیچ معنایی ندارد — چون کدِ سریع‌ترِ غلط، بهینه‌سازی نیست.

۲. شمارش، برای هر دو#

🤔 اول حدس بزن: ستونِ نسبتِ هر کدام را حدس بزن. برای حلقهٔ تودرتو راحت است؛ برای جدولِ شمارش دقت کن و بنویس چه عددی انتظار داری.

def counted_double_loop(values):
    ops = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            ops += 1
    return ops


def counted_bucket(values):
    ops = 0
    counts = [0] * LIMIT
    for v in values:
        counts[v] += 1
        ops += 1
    for v in range(LIMIT):
        ops += 1
    return ops


LADDER = [200, 400, 800, 1_600]
inputs = {n: rng.choices(range(LIMIT), k=n) for n in LADDER}
print("— حلقهٔ تودرتو")
table([(n, counted_double_loop(inputs[n])) for n in LADDER], "عملیات", ",d")
print("\n— جدولِ شمارش")
table([(n, counted_bucket(inputs[n])) for n in LADDER], "عملیات", ",d")
print("\nراستی‌آزماییِ فرمول‌ها در n = 800:")
print("  n(n-1)/2 =", 800 * 799 // 2, "· شمارشِ واقعی:",
      counted_double_loop(inputs[800]))
print("  n + LIMIT =", 800 + LIMIT, "· شمارشِ واقعی:", counted_bucket(inputs[800]))

— حلقهٔ تودرتو
         n            عملیات     نسبت به سطر قبل
       200            19,900                   —
       400            79,800                4.01
       800           319,600                4.01
     1,600         1,279,200                4.00

— جدولِ شمارش
         n            عملیات     نسبت به سطر قبل
       200           100,200                   —
       400           100,400                1.00
       800           100,800                1.00
     1,600           101,600                1.01

راستی‌آزماییِ فرمول‌ها در n = 800:
  n(n-1)/2 = 319600 · شمارشِ واقعی: 319600
  n + LIMIT = 100800 · شمارشِ واقعی: 100800

ستونِ نسبتِ جدولِ شمارش 1.00 است — و این نه یعنی مجانی، یعنی ثابت. هزینه‌اش صد هزار عمل است، چه n دویست باشد چه هزار و ششصد.

و همان‌جا کلِ ماجرا پیداست: در n = 200، حلقهٔ تودرتو 19,900 عمل می‌کند و جدولِ شمارش 100,200. الگوریتمِ «بهتر» پنج برابر بدتر است.

۳. نقطهٔ تقاطع، در شمارش#

دو فرمول را راستی‌آزمایی کردیم، پس می‌شود رویشان حساب کرد: کوچک‌ترین nی را می‌گردیم که در آن جدولِ شمارش جلو می‌افتد.

n = 2
while n * (n - 1) // 2 < n + LIMIT:
    n += 1
print(f"نقطهٔ تقاطع در شمارشِ عملیات: n = {n:,}")
print(f"  در n = {n - 1:,} → حلقهٔ تودرتو {(n - 1) * (n - 2) // 2:,}"
      f" در برابرِ جدولِ شمارش {n - 1 + LIMIT:,}")
print(f"  در n = {n:,} → حلقهٔ تودرتو {n * (n - 1) // 2:,}"
      f" در برابرِ جدولِ شمارش {n + LIMIT:,}")

نقطهٔ تقاطع در شمارشِ عملیات: n = 449
  در n = 448 → حلقهٔ تودرتو 100,128 در برابرِ جدولِ شمارش 100,448
  در n = 449 → حلقهٔ تودرتو 100,576 در برابرِ جدولِ شمارش 100,449

449. عددی قطعی، بدونِ نویز، یکسان روی هر ماشینی.

🌱 ریشه‌اش کجاست: کاری که این حلقه با جست‌وجو انجام داد، همان چیزی است که با جبر هم می‌شود انجام داد: دو طرف را برابر بگذار و برای n حل کن. شکلِ «مجهول در هر دو طرفِ تساوی» در ریشه ترمِ ۳ فصل ۳ ساخته می‌شود. ما اینجا عمداً با جست‌وجو حلش کردیم، چون در کارِ واقعی معمولاً فرمولِ دقیقِ دو طرف را نداری — ولی جدولِ اندازه‌گیری را داری.

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

۴. نقطهٔ تقاطع، روی ساعت#

شمارش می‌گوید 449. ولی شمارش فرض می‌کند هر عمل هزینهٔ یکسانی دارد، و این فرض غلط است: یک دورِ حلقهٔ تودرتو یک جمع و یک مقایسه است، و یک دورِ حلقهٔ جدولِ شمارش یک تفریق، سه مقایسه و یک ضرب.

print(f"{'n':>8}{'حلقهٔ تودرتو (ms)':>22}{'جدولِ شمارش (ms)':>22}{'برنده':>16}")
crossing = None
for n in range(200, 1_801, 200):
    values = rng.choices(range(LIMIT), k=n)
    t_loop = 1000 * clock(lambda: pairs_double_loop(values, TARGET), repeat=3)
    t_bucket = 1000 * clock(lambda: pairs_by_bucket(values, TARGET), repeat=3)
    winner = "حلقهٔ تودرتو" if t_loop < t_bucket else "جدولِ شمارش"
    if crossing is None and t_bucket < t_loop:
        crossing = n
    print(f"{n:>8,}{t_loop:>22.1f}{t_bucket:>22.1f}{winner:>16}")
print(f"\nروی این ماشین، جدولِ شمارش از n = {crossing:,} به بعد برنده شد.")

       n     حلقهٔ تودرتو (ms)      جدولِ شمارش (ms)           برنده
     200                   0.8                   6.3    حلقهٔ تودرتو
     400                   3.5                   6.3    حلقهٔ تودرتو
     600                   8.4                   6.5     جدولِ شمارش
     800                  15.2                   6.5     جدولِ شمارش
   1,000                  26.4                   6.4     جدولِ شمارش
   1,200                  35.0                   6.4     جدولِ شمارش
   1,400                  47.5                   6.7     جدولِ شمارش
   1,600                  64.5                   6.4     جدولِ شمارش
   1,800                  86.5                   7.0     جدولِ شمارش

ستونِ جدولِ شمارش تقریباً صاف است و ستونِ حلقهٔ تودرتو منفجر می‌شود. جایی بینِ 400 و 600 از هم رد می‌شوند. بیایید دقیق‌ترش کنیم:

print(f"{'n':>8}{'حلقهٔ تودرتو (ms)':>22}{'جدولِ شمارش (ms)':>22}{'برنده':>16}")
first = None
for n in range(400, 701, 50):
    values = rng.choices(range(LIMIT), k=n)
    t_loop = 1000 * clock(lambda: pairs_double_loop(values, TARGET), repeat=5)
    t_bucket = 1000 * clock(lambda: pairs_by_bucket(values, TARGET), repeat=5)
    winner = "حلقهٔ تودرتو" if t_loop < t_bucket else "جدولِ شمارش"
    if first is None and t_bucket < t_loop:
        first = n
    print(f"{n:>8,}{t_loop:>22.1f}{t_bucket:>22.1f}{winner:>16}")
print(f"\nنقطهٔ تقاطعِ زمانی روی این ماشین: n = {first:,}")

       n     حلقهٔ تودرتو (ms)      جدولِ شمارش (ms)           برنده
     400                   3.3                   6.0    حلقهٔ تودرتو
     450                   4.2                   5.9    حلقهٔ تودرتو
     500                   5.3                   6.0    حلقهٔ تودرتو
     550                   6.4                   5.9     جدولِ شمارش
     600                   7.8                   5.9     جدولِ شمارش
     650                   9.0                   5.9     جدولِ شمارش
     700                  10.7                   6.4     جدولِ شمارش

نقطهٔ تقاطعِ زمانی روی این ماشین: n = 550

550 روی ساعت، در برابرِ 449 در شمارش.

اختلافشان همان ثابتِ پنهان است: هر عملِ جدولِ شمارش گران‌تر از هر عملِ حلقهٔ تودرتوست، پس نقطهٔ سربه‌سر دیرتر می‌رسد.

⚠️ مواظب باش: عددِ 550 مالِ این ماشین است و عددِ 449 مالِ هیچ ماشینی نیست — مالِ خودِ الگوریتم است. روی CPUِ دیگری، یا حتی روی همین CPU در ساعتِ شلوغ، عددِ زمانی جابه‌جا می‌شود. ولی وجودِ تقاطع جابه‌جا نمی‌شود: تا وقتی یک الگوریتم سربارِ ثابت دارد و دیگری ندارد، حتماً یک نقطهٔ سربه‌سر هست. و به سطرِ 500 نگاه کن: 5.3 در برابرِ 6.0 — اختلافشان سیزده درصد است و در n = 550 به هشت درصد می‌رسد؛ یعنی دو منحنی این‌جا خیلی کم‌شیب از هم رد می‌شوند و نردبانِ ما هم پنجاه‌تا پنجاه‌تا جلو می‌رود. پس درست‌تر این است که بگوییم تقاطع «جایی بینِ ۵۰۰ و ۶۰۰» است، نه دقیقاً یک عدد.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ دو الگوریتم برای یک مسئله، روی یک ورودیِ یکسان در هر n — و جوابشان با == برابر تأیید شد. در کدام بازهٔ n؟ ۲۰۰ تا ۱٬۸۰۰ برای دیدنِ روند، و ۴۰۰ تا ۷۰۰ برای پیدا کردنِ تقاطع. با چند تکرار، و کمینه یا میانگین؟ سه تکرار در جدولِ درشت و پنج تکرار در جدولِ ریز، همیشه کمینه — چون هر اختلالِ بیرونی فقط زمان را زیاد می‌کند.

۵. nِ خودت بخشی از صورتِ مسئله است#

اگر فهرست‌های تو همیشه دویست‌تایی‌اند، حلقهٔ تودرتو نه فقط قابلِ قبول، بلکه انتخابِ درست است: هشت برابر سریع‌تر است، هفت خط کمتر دارد و صد هزار خانه حافظه هم نمی‌گیرد.

و اگر فهرست‌هایت ده هزارتایی‌اند، همان کد فاجعه است.

پس هر گزارشی که در این دوره می‌نویسی، سه چیز دارد و هر سه اجباری‌اند: بازهٔ nِ واقعی، معیارِ اندازه‌گیری، و ماشین. این همان قانونِ سومِ دوره است — «nِ خودت را بگو» — و حالا می‌دانی چرا از دوتای دیگر مهم‌تر است.

🔧 اگر کار نکرد: جدولِ شمارش یک فرضِ نانوشته دارد که اگر بشکند، بی‌صدا نمی‌شکند:

try:
    pairs_by_bucket([5, LIMIT + 3], TARGET)
except IndexError as err:
    print(f"{type(err).__name__}: {err}")

IndexError: list index out of range

هزینهٔ این الگوریتم به LIMIT بند است، و درستی‌اش هم. اگر کدی بیرونِ بازه بیاید، counts[v] می‌شکند. حلقهٔ تودرتو چنین فرضی ندارد و با هر عددی کار می‌کند. این هم بخشی از معامله است و باید در گزارش بیاید — «الگوریتمِ ب سریع‌تر است» بدونِ «به شرطی که همهٔ کدها زیرِ صد هزار باشند» یک جملهٔ ناقص است.

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

۶. وقتی n یکی نیست#

فصلِ ۱ در همان بخشِ دوم گفت که «ممکن است دو اندازه داشته باشی» و مثالش ردیف و ستونِ یک جدول بود. این فصل اولین جایی است که واقعاً دو اندازه دارد — n و LIMIT — و هزینهٔ pairs_by_bucket به هر دو بند است.

و یک جدول برای دو پارامتر کافی نیست. جدولِ بخشِ ۲ ستونِ نسبتِ 1.00 داد و ما از آن نتیجه گرفتیم «هزینه ثابت است». آن نتیجه فقط با LIMITِ ثابت درست است و خودِ جدول این شرط را هیچ‌جا نمی‌نویسد.

روشش ساده است و از این‌جا به بعدِ دوره همه‌جا به‌کار می‌آید: یکی را ثابت بگیر، دیگری را دو برابر کن. دو نردبان، دو جدول.

🤔 اول حدس بزن: همان شمارنده، دو بار. یک بار LIMIT ثابت و n دو برابر؛ یک بار n ثابت و LIMIT دو برابر. برای هر کدام ستونِ نسبت را بنویس، بعد جدول‌ها را ببین.

def counted_bucket_two(values, limit):
    """همان شمارندهٔ بخشِ ۲، این بار limit را هم به‌عنوان ورودی می‌گیرد."""
    ops = 0
    counts = [0] * limit
    for v in values:
        counts[v] += 1
        ops += 1
    for v in range(limit):
        ops += 1
    return ops


SMALL = 25_000                       # کدها را در بازهٔ کوچک‌ترین LIMIT می‌سازیم
codes = {n: [rng.randrange(SMALL) for _ in range(n)] for n in LADDER}

print("— نردبانِ اول: LIMIT ثابت روی ۱۰۰٬۰۰۰، n دو برابر می‌شود")
table([(n, counted_bucket_two(codes[n], 100_000)) for n in LADDER], "عملیات", ",d")

print("\n— نردبانِ دوم: n ثابت روی ۸۰۰، LIMIT دو برابر می‌شود")
print(f"{'LIMIT':>10}{'عملیات':>18}{'نسبت به سطر قبل':>20}")
previous = None
for limit in (25_000, 50_000, 100_000, 200_000):
    ops = counted_bucket_two(codes[800], limit)
    ratio = "—" if not previous else f"{ops / previous:.2f}"
    print(f"{limit:>10,}{ops:>18,}{ratio:>20}")
    previous = ops

— نردبانِ اول: LIMIT ثابت روی ۱۰۰٬۰۰۰، n دو برابر می‌شود
         n            عملیات     نسبت به سطر قبل
       200           100,200                   —
       400           100,400                1.00
       800           100,800                1.00
     1,600           101,600                1.01

— نردبانِ دوم: n ثابت روی ۸۰۰، LIMIT دو برابر می‌شود
     LIMIT            عملیات     نسبت به سطر قبل
    25,000            25,800                   —
    50,000            50,800                1.97
   100,000           100,800                1.98
   200,000           200,800                1.99

یک تابع، یک شمارنده، و دو ستونِ نسبت که هیچ ربطی به هم ندارند: 1.00 و 1.99.

نردبانِ اول می‌گوید هزینه به n بی‌اعتناست. نردبانِ دوم می‌گوید هزینه با LIMIT خطی است. هر دو درست‌اند و هیچ‌کدام به‌تنهایی رفتارِ این تابع را توصیف نمی‌کند. جملهٔ کامل این است: O(n + LIMIT) — همان فرمولی که در بخشِ ۲ راستی‌آزمایی‌اش کردیم، حالا با دو جدول پشتش.

و همین‌جا معلوم می‌شود چرا نردبانِ تک‌پارامتری خطرناک است: اگر فقط نردبانِ اول را گرفته بودی و می‌نوشتی «این تابع O(1) است»، هیچ عددی در جدولت غلط نبود و نتیجه‌ات کاملاً غلط بود.

قاعدهٔ عملی، برای هر جای بقیهٔ این دوره: اگر هزینهٔ چیزی به بیش از یک اندازه بند است، هر پارامتر نردبانِ خودش را می‌خواهد — یکی را ثابت نگه دار، دیگری را دو برابر کن، و هر دو جدول را گزارش کن. این وضعیت اصلاً نادر نیست: ترمِ ۳ فصلِ ۵ (n کلید و q پرسش)، ترمِ ۴ فصلِ ۶ (n عضو و k بازهٔ مقادیر)، ترمِ ۵ فصلِ ۴ (n و k)، ترمِ ۵ فصلِ ۶ (V گره و E یال) و ترمِ ۶ فصلِ ۳ (n و q) همه دقیقاً همین شکل‌اند.

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

در فصل بعد#

نُه فصل ابزار ساختیم. فصلِ آخر هیچ ابزارِ تازه‌ای نمی‌سازد و همه‌شان را یکجا به‌کار می‌برد: چهار تابعِ ناشناس به تو داده می‌شود و باید مرتبهٔ هر کدام را اعلام کنی — با جدول، با پیش‌بینی، و با خطای گزارش‌شده. یکی از آن چهارتا عمداً طوری نوشته شده که در nهای کوچک، مرتبهٔ اشتباهی به تو نشان بدهد.