عمل بشمار، نه ثانیه

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

دو فصل با نویز جنگیدیم و بهترین کاری که توانستیم بکنیم رساندنِ پراکندگی به حدودِ دو درصد بود. این فصل ساعت را کنار می‌گذارد.

به‌جای ثانیه، مقایسه‌ها را می‌شماریم. جدولی که درمی‌آید این است — ۴٬۹۵۰، ۱۹٬۹۰۰، ۷۹٬۸۰۰، ۳۱۹٬۶۰۰ — و این چهار عدد روی ماشینِ تو، روی ماشینِ من و در هر اجرایی دقیقاً همین‌ها هستند. پراکندگی صفر است، نه دو درصد.

بعد هزینه‌اش را هم می‌پردازیم: خودِ شمارنده کد را حدودِ یک‌ونیم برابر کند می‌کند — و می‌بینیم چرا این اصلاً اهمیتی ندارد.

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

• عملیاتِ اصلیِ یک تکه کد را انتخاب کنی و بگویی چرا همان
• شمارنده را طوری بنویسی که جوابِ تابع را عوض نکند
• بگویی چرا شمارش تکرارپذیر است و ثانیه نیست
• بفهمی شمردنِ عملِ اشتباه چطور جدولی می‌سازد که کاملاً درست به‌نظر می‌رسد و کاملاً غلط است

قبل از شروع#

از فصلِ ۳: پراکندگی و آستانهٔ باور. از فصلِ ۱: first_duplicate و بدترین ورودی.

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

۱. کدام عمل را بشماریم#

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

عملیاتِ اصلی آن کاری است که با بزرگ شدنِ n تعدادش زیاد می‌شود و بقیه دنبالش می‌آیند. در first_duplicate این کار روشن است: مقایسهٔ values[i] == values[j]. هر بار که این مقایسه انجام می‌شود، چند کارِ ریزِ دیگر هم انجام می‌شود — ولی همه‌شان به‌ازای همان یک مقایسه هستند، پس تعدادشان ضریبی از همان است.

انتخابِ عملیاتِ اصلی یک تصمیم است و باید نوشته شود. در بخشِ ۵ می‌بینی اگر بد انتخاب شود چه بلایی سرِ نتیجه می‌آید.

۲. تابعی که جوابش را با هزینه‌اش می‌دهد#

🤔 اول حدس بزن: قبل از اجرا بنویس — اگر n را دو برابر کنیم، تعدادِ مقایسه‌ها چند برابر می‌شود؟ و آیا انتظار داری ستونِ نسبت از ستونِ نسبتِ جدولِ زمانیِ فصلِ ۱ صاف‌تر باشد یا ناهموارتر؟

COUNT_SIZES = [100, 200, 400, 800]


def counted_duplicate(values):
    """جوابِ تابع، به‌علاوهٔ تعدادِ مقایسه‌هایی که برای رسیدن به آن انجام شد."""
    comparisons = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            comparisons += 1
            if values[i] == values[j]:
                return values[i], comparisons
    return None, comparisons


rng = random.Random(SEED)
inputs = {n: rng.sample(range(10 * n), n) for n in COUNT_SIZES}
rows = []
for n in COUNT_SIZES:
    answer, comparisons = counted_duplicate(inputs[n])
    rows.append((n, comparisons))
table(rows, "مقایسه", ",d")

         n            مقایسه     نسبت به سطر قبل
       100             4,950                   —
       200            19,900                4.02
       400            79,800                4.01
       800           319,600                4.01

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

4,950 عددِ من نیست؛ عددِ خودِ الگوریتم است. برای فهرستی با 100 عضو که هیچ تکراری ندارد، دقیقاً 100 × 99 ÷ 2 مقایسه لازم است، هر که اجرایش کند و هر جا اجرایش کند. و این عدد از یک جمعِ ساده درمی‌آید که تا آخرِ دوره بارها برمی‌گردد، پس همین‌جا از صفر می‌سازیمش.

عضوِ اول با 99 عضوِ بعدی مقایسه می‌شود، عضوِ دوم با 98 تا، … و عضوِ یکی‌مانده‌به‌آخر با 1 تا. پس کلِ کار 1 + 2 + … + 99 است. برای بستنِ این جمع یک ترفندِ سه‌خطی هست: همان جمع را یک بار برعکس زیرِ خودش بنویس و ستون‌ها را جمع بزن.

   1  +   2  +   3  + … +  98  +  99
  99  +  98  +  97  + … +   2  +   1
 ---   ---   ---         ---   ---
 100  + 100  + 100  + … + 100  + 100

هر ستون 100 می‌شود و 99 ستون داریم، پس دو برابرِ جمع برابرِ 99 × 100 است و خودِ جمع نصفش. همین را با کد وارسی می‌کنیم:

m = 99                                   # عضوِ اول با ۹۹ عضوِ بعدی مقایسه می‌شود
forward = list(range(1, m + 1))
backward = list(range(m, 0, -1))
columns = [a + b for a, b in zip(forward, backward)]
print("سه ستونِ اول:", columns[:3], "· همه یکی‌اند؟", len(set(columns)) == 1)
print(f"دو برابرِ جمع = {m} ستونِ {columns[0]}تایی = {m * columns[0]:,}")
print("پس خودِ جمع   =", m * columns[0] // 2)
print("جمعِ مستقیم    =", sum(range(1, m + 1)))
print("فرمولِ n(n-1)/2 در n = 100 =", 100 * 99 // 2)

سه ستونِ اول: [100, 100, 100] · همه یکی‌اند؟ True
دو برابرِ جمع = 99 ستونِ 100تایی = 9,900
پس خودِ جمع   = 4950
جمعِ مستقیم    = 4950
فرمولِ n(n-1)/2 در n = 100 = 4950

سه راه، یک عدد. با n به‌جای 100 همین استدلال n(n-1)/2 می‌دهد — و این فرمول از این‌جا به بعد سه بار دیگر لازم می‌شود: فصلِ ۸ ثابتِ برازشش 0.5 است چون همین فرمول تقریباً n²/2 است، فصلِ ۹ نقطهٔ تقاطع را از حلِ همین فرمول درمی‌آورد، و ترمِ ۲ فصلِ ۵ همین را برای 1 + 2 + … + n تکرار می‌کند.

و ستونِ نسبت هم صاف است: 4.02، 4.01، 4.01. هیچ‌کدام دقیقاً 4 نیستند و این هم دقیق است، نه نویز — عدد کمی از چهار بیشتر است چون فرمول n(n-1)/2 است، نه n²/2. با بزرگ‌تر شدنِ n این اختلاف کوچک‌تر می‌شود.

✅ چک کن: 4950 * 4 می‌شود 19800 ولی جدول 19900 می‌گوید. اگر این صد واحد اختلاف را دیدی و برایت سؤال شد، دقیقاً همان چیزی را دیده‌ای که باید: نسبتِ دوبرابری در ابتدا کمی بزرگ‌تر از چهار است و آرام‌آرام به چهار نزدیک می‌شود. با n = 100_000 نسبت به 4.00 می‌رسد.

۳. شمارش تکرار می‌شود، ثانیه نه#

def first_duplicate(values):
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] == values[j]:
                return values[i]
    return None


big = inputs[800]
counts = [counted_duplicate(big)[1] for _ in range(3)]
times = []
for _ in range(3):
    start = time.perf_counter()
    first_duplicate(big)
    times.append(1000 * (time.perf_counter() - start))
print("سه بار شمارش :", counts)
print("هر سه یکی‌اند؟", counts[0] == counts[1] == counts[2])
print("سه بار زمان  :", [round(t, 3) for t in times])
print("هر سه یکی‌اند؟", times[0] == times[1] == times[2])

سه بار شمارش : [319600, 319600, 319600]
هر سه یکی‌اند؟ True
سه بار زمان  : [11.401, 11.472, 11.592]
هر سه یکی‌اند؟ False

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

پس از این به بعد دو ابزار داریم و هر کدام سؤالِ خودشان را جواب می‌دهند:

• شمارنده می‌گوید الگوریتم چقدر کار می‌کند و شکلِ رشدش چیست. تکرارپذیر، بدونِ نویز، مستقل از ماشین.
• ساعت می‌گوید آن کار روی این ماشین چقدر طول می‌کشد. تنها ابزاری که به سؤالِ «کاربر چقدر صبر می‌کند؟» جواب می‌دهد.

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

۴. شمارنده مجانی نیست#

آن خطِ comparisons += 1 هم خودش یک عمل است و وقت می‌گیرد.

ids = rng.sample(range(40_000), 4_000)
plain = clock(lambda: first_duplicate(ids), repeat=3)
counted = clock(lambda: counted_duplicate(ids), repeat=3)
print(f"بدونِ شمارنده : {1000 * plain:>7.1f} ms")
print(f"با شمارنده   : {1000 * counted:>7.1f} ms")
print(f"شمارنده کد را {counted / plain:.2f} برابر کند کرد")

بدونِ شمارنده :   278.6 ms
با شمارنده   :   415.7 ms
شمارنده کد را 1.49 برابر کند کرد

نسخهٔ شمارنده‌دار حدودِ یک‌ونیم برابر کندتر است. و این هیچ اهمیتی ندارد — به شرطی که بدانی چرا.

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

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

۵. شمردنِ عملِ اشتباه#

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

def counted_outer_only(values):
    """فقط دورهای حلقهٔ بیرونی را می‌شمارد — انتخابِ غلطِ عملیاتِ اصلی."""
    rounds = 0
    for i in range(len(values)):
        rounds += 1
        for j in range(i + 1, len(values)):
            if values[i] == values[j]:
                return values[i], rounds
    return None, rounds


rows = [(n, counted_outer_only(inputs[n])[1]) for n in COUNT_SIZES]
table(rows, "دورِ حلقهٔ بیرونی", ",d")

         n دورِ حلقهٔ بیرونی     نسبت به سطر قبل
       100               100                   —
       200               200                2.00
       400               400                2.00
       800               800                2.00

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

اگر فقط این جدول را می‌دیدی، می‌گفتی هزینه با n جلو می‌رود و بی‌خیالِ کد می‌شدی. در حالی که همان کد، در همان بازه، کارش چهار برابر می‌شود.

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

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

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

try:
    answer = counted_duplicate(inputs[100])
    print(answer + 1)
except TypeError as err:
    print(f"{type(err).__name__}: {err}")

TypeError: can only concatenate tuple (not "int") to tuple

پیام صریح است: answer یک tuple است، نه عدد. درستش answer, comparisons = counted_duplicate(...) است. اگر تعدادِ متغیرهای سمتِ چپ با تعدادِ چیزهای برگشتی نخواند، پیامِ دیگری می‌گیری: ValueError: too many values to unpack (expected 2).

۶. چیزی که شمارش نمی‌گوید#

شمارنده یک چیزِ مهم را نمی‌داند: هر عمل چقدر گران است.

319,600 مقایسهٔ عدد با عدد یک چیز است؛ 319,600 مقایسهٔ رشتهٔ صدنویسه‌ای چیزِ دیگری است. هر دو در شمارنده یک عدد می‌دهند و در ساعت دو عددِ کاملاً متفاوت.

پس شمارنده و ساعت با هم کار می‌کنند، نه به‌جای هم. این نکته در فصلِ ۹ به یک نتیجهٔ عملیِ عجیب می‌رسد: الگوریتمی که کارِ بیشتری می‌شمارد، می‌تواند روی داده‌های واقعیِ تو زودتر تمام شود.

🤖 از دستیارت بپرس: «چرا تعدادِ مقایسه‌های یک حلقهٔ دوتایی روی n عضو برابرِ n(n-1)/2 است؟» بعد این را هم بپرس: «اگر همان الگوریتم را طوری بنویسم که هر جفت را دو بار مقایسه کند، شمارش چه می‌شود و کدام نتیجه‌گیریِ من عوض می‌شود؟» — جوابِ درست این است که شمارش دو برابر می‌شود ولی ستونِ نسبت هیچ تغییری نمی‌کند، و همین شروعِ درسِ فصلِ ۷ است.

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

در فصل بعد#

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