جدولِ دوبرابری: `n` را دو برابر کن و نگاه کن

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

چهار تابع می‌سازیم و هر چهارتا را با شمارندهٔ فصلِ قبل روی یک نردبانِ دوبرابری می‌بریم. ستونِ نسبتِ هر کدام یک عددِ متفاوت می‌دهد و هر چهار عدد بلافاصله می‌گویند کد چه شکلی رشد می‌کند: 1.00، 1.10، 2.00، 4.00.

بعد یک تلهٔ واقعی را باز می‌کنیم. همان یک تابع، همان شمارنده: در nهای ۱۰ تا ۸۰ ستونِ نسبت 1.03 می‌دهد و در nهای ۵۰۰ تا ۴۰۰۰ می‌دهد 3.99. اگر فقط جدولِ اول را دیده بودی، دربارهٔ آن کد نتیجه‌ای می‌گرفتی که صد در صد غلط بود.

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

• جدولِ دوبرابری بسازی: چهار اندازه که هر بار دو برابر می‌شوند، به‌علاوهٔ ستونِ نسبت
• از روی ستونِ نسبت بگویی هزینه چه شکلی با n می‌رود
• بگویی چرا دوبرابری، و نه مثلاً «هر بار هزار تا اضافه کن»
• تشخیص بدهی جدولی که در nهای کوچک گرفته شده کِی دروغ می‌گوید
• lambdaی جدول‌سازت را طوری بنویسی که هر سطر واقعاً nِ خودش را بسنجد

قبل از شروع#

از فصلِ ۴: شمارندهٔ عملیات، و اینکه شمارش قطعی است.

از فصلِ ۱: جدولی که ستونِ نسبت دارد. همان ستون، از این فصل به بعد ابزارِ اصلیِ ماست.

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

۱. چرا دوبرابری، و نه چیزِ دیگری#

می‌شد نردبانِ اندازه‌ها را جمعی ساخت: 1000، 2000، 3000، 4000. ولی آن نردبان ستونِ نسبتِ بی‌معنایی می‌دهد، چون فاصلهٔ سطرها یکسان نیست: از 1000 به 2000 دو برابر شده‌ای و از 3000 به 4000 فقط یک‌سومِ بیشتر.

با نردبانِ ضربی — هر بار دقیقاً دو برابر — سؤالِ هر سطر همیشه یکی است: «n دو برابر شد؛ کار چند برابر شد؟» و چون سؤال ثابت است، جواب‌ها با هم قابلِ مقایسه‌اند.

🌱 ریشه‌اش کجاست: دو برابر کردنِ پیاپی همان چیزی است که در ریشه ترمِ ۱ فصل ۸ با نامِ توان ساخته می‌شود: چهار بار دو برابر کردن یعنی ضرب در 2⁴. نردبانِ ما هم دقیقاً یک نردبانِ توانی است، و همین باعث می‌شود با چهار سطرِ کوتاه بتوانی بازهٔ هشت برابری از n را پوشش بدهی.

۲. چهار شکلِ رشد، با شمارنده#

چهار تابع می‌نویسیم که هر کدام کارِ متفاوتی می‌کنند. هر چهارتا شمارندهٔ خودشان را دارند، پس عددها قطعی‌اند.

🤔 اول حدس بزن: برای هر یک از این چهار تابع بنویس با دو برابر شدنِ n تعدادِ عملیات چند برابر می‌شود. مخصوصاً برای halve_down حدس بزن، چون دشوارترینشان است.

LADDER = [500, 1_000, 2_000, 4_000]


def look_first(values):
    """فقط به اولین عضو نگاه می‌کند."""
    return values[0], 1


def total(values):
    """همهٔ عضوها را یکی‌یکی جمع می‌زند."""
    ops = 0
    running = 0
    for v in values:
        running += v
        ops += 1
    return running, ops


def halve_down(values):
    """هر بار نصفِ بازه را کنار می‌گذارد تا یک عضو بماند."""
    ops = 0
    size = len(values)
    while size > 1:
        size //= 2
        ops += 1
    return size, ops


def all_pairs(values):
    """هر جفتِ ممکن را دقیقاً یک بار می‌بیند."""
    ops = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            ops += 1
    return None, ops


data = {n: list(range(n)) for n in LADDER}
for name, fn in (("look_first", look_first), ("halve_down", halve_down),
                 ("total", total), ("all_pairs", all_pairs)):
    print(f"— {name}")
    table([(n, fn(data[n])[1]) for n in LADDER], "عملیات", ",d")
    print()

— look_first
         n            عملیات     نسبت به سطر قبل
       500                 1                   —
     1,000                 1                1.00
     2,000                 1                1.00
     4,000                 1                1.00

— halve_down
         n            عملیات     نسبت به سطر قبل
       500                 8                   —
     1,000                 9                1.12
     2,000                10                1.11
     4,000                11                1.10

— total
         n            عملیات     نسبت به سطر قبل
       500               500                   —
     1,000             1,000                2.00
     2,000             2,000                2.00
     4,000             4,000                2.00

— all_pairs
         n            عملیات     نسبت به سطر قبل
       500           124,750                   —
     1,000           499,500                4.00
     2,000         1,999,000                4.00
     4,000         7,998,000                4.00

چهار عددِ متفاوت در ستونِ نسبت، و هر کدام یک داستانِ متفاوت.

به halve_down بیشتر دقت کن، چون تنها موردی است که با حدسِ شهودی جور در نمی‌آید. با دو برابر شدنِ n، تعدادِ عملیات فقط یکی اضافه می‌شود: 8، 9، 10، 11. منطقش ساده است: یک بار دو برابر کردنِ ورودی، فقط یک نصف‌کردنِ اضافه لازم دارد. برای همین نسبتش نه ثابت است و نه دو؛ عددی کمی بالای یک است که با بزرگ‌تر شدنِ n به یک نزدیک‌تر هم می‌شود.

✅ چک کن: LADDER را به [4_000, 8_000, 16_000, 32_000] ببر و فقط halve_down را دوباره بگیر. ستونِ نسبت باید از 1.10 به چیزی مثلِ 1.08 برود. اگر نرفت، احتمالاً size //= 2 را به size -= 2 تبدیل کرده‌ای — و آن‌وقت نسبت 2.00 می‌شود، چون کارِ کاملاً متفاوتی است.

۳. قاعدهٔ خواندنِ ستونِ نسبت#

حالا می‌شود یک قاعدهٔ عملی نوشت. n را دو برابر کن و به نسبت نگاه کن:

• نزدیکِ 1 — کار به اندازهٔ ورودی تقریباً کاری ندارد. look_first مثالِ خالصش است.
• کمی بالای 1 و رو به کاهش — با هر دو برابر شدنِ n فقط یک قدم اضافه می‌شود. این شکلِ halve_down است.
• نزدیکِ 2 — کار پابه‌پای n جلو می‌رود: دو برابر داده، دو برابر کار.
• کمی بالای 2 و رو به کاهش — پابه‌پای n جلو می‌رود، به‌علاوهٔ یک لایهٔ نصف‌کردن. این شکل را در فصلِ بعد می‌بینی.
• نزدیکِ 4 — کار با مربعِ n می‌رود: دو برابر داده، چهار برابر کار.
• بزرگ‌تر از 4 و رو به انفجار — نسبت خودش هم با n بزرگ می‌شود. این بدترین حالت است و فصلِ بعد نشانت می‌دهد چقدر بد.

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

و مهم‌ترین نکتهٔ این قاعده: هیچ‌کدام از این عددها به ثانیه، ماشین یا زبانِ برنامه‌نویسی بند نیستند. نسبت را ادعا کن، نه ثانیه را — این دومین قاعدهٔ ثابتِ گزارش‌نویسی در این دوره.

۴. اندازه‌های کوچک دروغ می‌گویند#

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

🤔 اول حدس بزن: همین تابع را روی دو نردبان می‌بریم — یکی 10 تا 80 و یکی 500 تا 4000. برای هر کدام یک عدد در ستونِ نسبت بنویس. و مهم‌ترین بخشِ حدست این باشد: آیا انتظار داری دو عدد یکی باشند؟

SETUP_COST = 5_000


def with_setup(values):
    """یک آماده‌سازیِ ثابت، بعد همان حلقهٔ جفت‌ها."""
    ops = 0
    for _ in range(SETUP_COST):          # به n بستگی ندارد
        ops += 1
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            ops += 1
    return ops


print("— اندازه‌های کوچک")
table([(n, with_setup(list(range(n)))) for n in (10, 20, 40, 80)], "عملیات", ",d")
print("\n— اندازه‌های بزرگ‌تر، همان تابع")
table([(n, with_setup(data[n])) for n in LADDER], "عملیات", ",d")

— اندازه‌های کوچک
         n            عملیات     نسبت به سطر قبل
        10             5,045                   —
        20             5,190                1.03
        40             5,780                1.11
        80             8,160                1.41

— اندازه‌های بزرگ‌تر، همان تابع
         n            عملیات     نسبت به سطر قبل
       500           129,750                   —
     1,000           504,500                3.89
     2,000         2,004,000                3.97
     4,000         8,003,000                3.99

یک تابع، یک شمارنده، دو جدول، دو نتیجهٔ کاملاً متضاد.

جدولِ اول می‌گوید «نسبت 1.03 است، پس اندازهٔ ورودی تقریباً بی‌اثر است». جدولِ دوم می‌گوید «نسبت 3.99 است، پس کار با مربعِ n می‌رود». هر دو جدول درست‌اند و فقط یکی‌شان به دردِ تصمیم می‌خورد.

دلیلش را می‌شود با یک تقسیم دید: در n = 10، آن 5,000 عملِ آماده‌سازی ۹۹ درصدِ کل است و حلقهٔ جفت‌ها 45 تا. در n = 4000، آماده‌سازی 5,000 از 8,003,000 است — کمتر از یک‌دهمِ درصد. بخشی که غالب است عوض شده، و ستونِ نسبت شکلِ همان بخشِ غالب را نشان می‌دهد.

قاعده‌ای که از این درمی‌آید و تا آخرِ دوره برقرار است: جدولت را در بازه‌ای بساز که به nِ واقعیِ خودت نزدیک باشد. جدولی که در n = 10 گرفته شده، دربارهٔ n = 4000 هیچ چیزی نمی‌گوید — و برعکس.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک تابعِ ثابت با خودش، در دو بازهٔ متفاوتِ n. در کدام بازهٔ n؟ ۱۰ تا ۸۰، و ۵۰۰ تا ۴۰۰۰ — و کلِ نتیجهٔ این بخش در همین یک سطر است. با چند تکرار، و کمینه یا میانگین؟ یک اجرا؛ شمارش قطعی است و تکرار چیزی اضافه نمی‌کند.

۵. همان جدول، این بار با ساعت#

شمارنده صاف است؛ حالا ببینیم ساعت همان شکل را نشان می‌دهد یا نه.

rows = [(n, 1000 * clock(lambda values=data[n]: all_pairs(values), repeat=3))
        for n in LADDER]
table(rows)

         n         زمان (ms)     نسبت به سطر قبل
       500               3.3                   —
     1,000              14.2                4.27
     2,000              63.4                4.47
     4,000             237.0                3.74

ستونِ زمان همان داستان را می‌گوید، ولی با لهجه‌ای لرزان: 4.27، 4.47، 3.74 به‌جای 4.00، 4.00، 4.00.

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

و حالا به یک تکه از همان خط نگاه کن که تا آخرِ دوره ده‌ها بار تکرار می‌شود: lambda values=data[n]: all_pairs(values).

lambda را فصلِ ۲ ساخت: clock یک تابع می‌خواهد نه نتیجهٔ یک تابع. ولی آن values=data[n] چیزِ دیگری است و کارش این است که مقدار را همین حالا میخ کند. یک lambda مقدارِ متغیرهای بیرونی‌اش را موقعِ صدا زده شدن می‌خواند، نه موقعِ ساخته شدن؛ آرگومانِ پیش‌فرض برعکس است و موقعِ ساخته شدن حساب می‌شود. تا وقتی clock را در همان دورِ حلقه صدا بزنی، این تفاوت هیچ اثری ندارد. اولین باری که یک خط جابه‌جا شود، دارد.

🔧 اگر کار نکرد: اگر ستونِ نسبتت دقیقاً 1.00 درآمد، قبل از هر چیز به lambdaهایت نگاه کن. این‌جا همان کار را با شمارنده انجام می‌دهیم تا عددها قطعی بمانند — اول lambdaها را می‌سازیم و بعد صدایشان می‌زنیم، همان کاری که هر کسی موقعِ مرتب کردنِ کدش می‌کند:

DEMO = [250, 500, 1_000, 2_000]
demo_data = {n: list(range(n)) for n in DEMO}

loose = [lambda: all_pairs(demo_data[n]) for n in DEMO]
pinned = [lambda values=demo_data[n]: all_pairs(values) for n in DEMO]

print("— بدونِ پین کردن")
table([(n, job()[1]) for n, job in zip(DEMO, loose)], "عملیات", ",d")
print("\n— با پینِ آرگومانِ پیش‌فرض")
table([(n, job()[1]) for n, job in zip(DEMO, pinned)], "عملیات", ",d")

— بدونِ پین کردن
         n            عملیات     نسبت به سطر قبل
       250         1,999,000                   —
       500         1,999,000                1.00
     1,000         1,999,000                1.00
     2,000         1,999,000                1.00

— با پینِ آرگومانِ پیش‌فرض
         n            عملیات     نسبت به سطر قبل
       250            31,125                   —
       500           124,750                4.01
     1,000           499,500                4.00
     2,000         1,999,000                4.00

جدولِ اول هیچ خطایی نداد، هیچ هشداری نداد، و کاملاً غلط است. هر چهار lambdaی نسخهٔ اول موقعِ صدا زده شدن n را می‌خوانند و آن موقع n دیگر 2000 است — پس هر چهار سطر همان بزرگ‌ترین اندازه را می‌سنجند و ستونِ نسبت 1.00 می‌شود. و 1.00 در این دوره یک عددِ محترم است: یعنی O(1). یک جدولِ مرتب و باورپذیر که یک نتیجهٔ کاملاً ساختگی اعلام می‌کند.

قاعده، و از این‌جا به بعدِ دوره بی‌استثنا: هر lambdaیی که داخلِ حلقه یا list comprehension ساخته می‌شود، باید مقدارش را با آرگومانِ پیش‌فرض پین کند — lambda v=data[n]: ...، نه lambda: ... data[n] .... حتی وقتی همان‌جا صدایش می‌زنی و لازم نیست؛ چون عادت است که تو را نجات می‌دهد، نه دقت در یک لحظهٔ خاص.

و یک اشتباهِ رایج‌ترِ دیگر با table: قالبِ عدد را با نوعِ داده جور نکنی — زمانِ اعشاری را با قالبِ عددِ صحیح چاپ کنی:

try:
    table(rows, "زمان", ",d")
except ValueError as err:
    print(f"{type(err).__name__}: {err}")

         n              زمان     نسبت به سطر قبل
ValueError: Unknown format code 'd' for object of type 'float'

دقت کن که سطرِ عنوان چاپ شد و بعد کار خوابید — یعنی خطا وسطِ کار افتاده، نه اولِ کار. پیام هم صریح است: قالبِ d مالِ عددِ صحیح است. برای شمارشِ عملیات ",d" و برای زمان ",.1f" — که مقدارِ پیش‌فرضِ table هم همین است.

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

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

در فصل بعد#

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