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

فصل ۴ از ۶

پیشرفت ترم
۰٪

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

سه فصل ابزارِ بهینه‌سازی ساختیم. این فصل تنها فصلی است که می‌گوید دست نگه دار، با سه معیار که هر کدام به‌تنهایی کافی‌اند.

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

چراغی که سه کلیدِ توقفِ جداگانه دارد و هر کدام به‌تنهایی خاموشش می‌کند

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

  • معیارِ توقف را قبل از شروعِ بهینه‌سازی بنویسی
  • تشخیص بدهی کِی یک بهبود از نوسانِ اندازه‌گیریِ خودت کوچک‌تر است
  • سقفِ یک بهینه‌سازی را قبل از انجامش حساب کنی
  • هزینه‌ای را ببینی که هیچ جدولِ زمانی نشان نمی‌دهد

قبل از شروع#

از ترمِ ۱ فصلِ ۳: پراکندگیِ اندازه‌گیری و آستانهٔ باور. از ترمِ ۱ فصلِ ۹: ثابتِ پنهان. از فصلِ ۱: برگهٔ شکلِ مسئله.

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

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

۱. معیارِ توقف، پیش از اولین خط کد#

مسئله: از یک سیاههٔ رویداد، تعدادِ رکوردِ هر شهر را بشمار.

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

و یک سطرِ چهارم که فقط این فصل اضافه‌اش می‌کند — معیارِ توقف:

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

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

CITIES = ("shiraz", "tabriz", "rasht", "yazd", "ahvaz", "kerman", "mashhad", "sari")
N = 20_000


def make_log(n, seed=SEED):
    """هر سطر هفت فیلدِ جداشده با tab؛ شهر فیلدِ دوم است."""
    rng = random.Random(seed)
    return ["\t".join((f"{i:07d}", rng.choice(CITIES), f"{rng.randrange(1000)}",
                       "ok", f"{rng.randrange(100)}", "-", "-"))
            for i in range(n)]


def v1(rows):
    """نسخهٔ اول — سطر را کامل می‌شکند."""
    counts = {}
    for line in rows:
        city = line.split("\t")[1]
        counts[city] = counts.get(city, 0) + 1
    return counts


log = make_log(N)
print("یک سطرِ نمونه:", repr(log[0]))
print("شمارش:", sorted(v1(log).items())[:3], "...")
یک سطرِ نمونه: '0000000\tsari\t119\tok\t0\t-\t-'
شمارش: [('ahvaz', 2479), ('kerman', 2545), ('mashhad', 2531)] ...

۲. نسخهٔ دوم: بردی که واقعی است#

split("\t") هر سطر را به هفت تکه می‌شکند و ما فقط تکهٔ دوم را می‌خواهیم. split("\t", 2) بعد از دو جدایی می‌ایستد.

def v2(rows):
    """نسخهٔ دوم — فقط تا فیلدِ دوم بشکن."""
    counts = {}
    for line in rows:
        city = line.split("\t", 2)[1]
        counts[city] = counts.get(city, 0) + 1
    return counts


def pieces_built(rows, limit=-1):
    """چند رشتهٔ تازه ساخته می‌شود — عددی قطعی، مستقل از ماشین."""
    return sum(len(line.split("\t", limit)) for line in rows)


print("جوابِ دو نسخه یکی است؟", v1(log) == v2(log))
print("— رشته‌های ساخته‌شده، نسخهٔ اول")
table([(n, pieces_built(make_log(n))) for n in (5_000, 10_000, 20_000, 40_000)],
      "رشته", ",d")
print("\n— رشته‌های ساخته‌شده، نسخهٔ دوم")
table([(n, pieces_built(make_log(n), 2)) for n in (5_000, 10_000, 20_000, 40_000)],
      "رشته", ",d")
جوابِ دو نسخه یکی است؟ True
— رشته‌های ساخته‌شده، نسخهٔ اول
         n              رشته     نسبت به سطر قبل
     5,000            35,000                   —
    10,000            70,000                2.00
    20,000           140,000                2.00
    40,000           280,000                2.00

— رشته‌های ساخته‌شده، نسخهٔ دوم
         n              رشته     نسبت به سطر قبل
     5,000            15,000                   —
    10,000            30,000                2.00
    20,000            60,000                2.00
    40,000           120,000                2.00

هر دو O(n) — ستونِ نسبت دقیقاً 2.00 — و ثابتشان فرق دارد: هفت رشته در برابرِ سه. این همان تفکیکِ ترمِ ۱ فصلِ ۹ است: مرتبه عوض نشد، ثابت عوض شد.

for name, fn in (("نسخهٔ ۱", v1), ("نسخهٔ ۲", v2)):
    print(f"{name}: {1000 * clock(lambda f=fn: f(log), repeat=7):>6.3f} ms")
نسخهٔ ۱:  5.067 ms
نسخهٔ ۲:  4.205 ms

5.07 به 4.21 — حدودِ ۱٫۲ برابر، و عدد زیرِ پنج میلی‌ثانیه آمد.

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

۳. معیارِ دوم: بهبودی که از نوسان کوچک‌تر است#

نسخهٔ سوم یک ترفندِ کوچک می‌زند: به‌جای counts.get(city, 0) + 1، مستقیم counts[city] += 1 و except KeyError برای بارِ اول. چون شهرها فقط هشت تا هستند، آن except تقریباً هرگز اجرا نمی‌شود.

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

def v3(rows):
    """نسخهٔ سوم — همان کار، با try/except به‌جای get."""
    counts = {}
    for line in rows:
        city = line.split("\t", 2)[1]
        try:
            counts[city] += 1
        except KeyError:
            counts[city] = 1
    return counts


print("جوابِ نسخهٔ ۳ با نسخهٔ ۲ یکی است؟", v2(log) == v3(log))
runs2 = [1000 * clock(lambda: v2(log), repeat=5) for _ in range(15)]
runs3 = [1000 * clock(lambda: v3(log), repeat=5) for _ in range(15)]
for name, runs in (("نسخهٔ ۲", runs2), ("نسخهٔ ۳", runs3)):
    print(f"{name}: کمینه {min(runs):.3f} · بیشینه {max(runs):.3f} ms"
          f" · پراکندگی {100 * (max(runs) - min(runs)) / min(runs):>5.1f} درصد")
print(f"بهبودِ اسمیِ نسخهٔ ۳ نسبت به نسخهٔ ۲: "
      f"{100 * (min(runs2) - min(runs3)) / min(runs2):.1f} درصد")
print("دو بازه روی هم می‌افتند؟",
      min(runs2) <= max(runs3) and min(runs3) <= max(runs2))
جوابِ نسخهٔ ۳ با نسخهٔ ۲ یکی است؟ True
نسخهٔ ۲: کمینه 4.189 · بیشینه 4.263 ms · پراکندگی   1.8 درصد
نسخهٔ ۳: کمینه 4.107 · بیشینه 4.232 ms · پراکندگی   3.0 درصد
بهبودِ اسمیِ نسخهٔ ۳ نسبت به نسخهٔ ۲: 1.9 درصد
دو بازه روی هم می‌افتند؟ True

سطرِ آخر تصمیم را می‌گیرد: دو بازه روی هم می‌افتند. نسخهٔ سوم در بدترین اجرایش کندتر از بهترین اجرای نسخهٔ دوم است، پس آن «بهبودِ اسمیِ» یکی-دو درصدی هیچ چیزی را ثابت نمی‌کند — تفاوتی که از پراکندگیِ خودِ اندازه‌گیریِ تو کوچک‌تر است، تفاوت نیست (ترمِ ۱ فصلِ ۳، که وعدهٔ همین فصل را داده بود).

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

✅ چک کن: pieces_built(log, 1) را صدا بزن. باید دقیقاً 40000 بدهد — دو تکه در هر سطر، ضربدرِ بیست هزار سطر. اگر عددِ دیگری داد، limit را به split پاس نداده‌ای و شمارنده دارد نسخهٔ اول را می‌شمارد.

۴. معیارِ سوم: سقف#

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

def loop_only(rows):
    for line in rows:
        pass


def split_only(rows):
    for line in rows:
        line.split("\t", 2)[1]


empty = clock(lambda: loop_only(log), repeat=7)
splitting = clock(lambda: split_only(log), repeat=7)
whole = clock(lambda: v2(log), repeat=7)
print(f"حلقهٔ خالی        : {1000 * empty:>6.3f} ms")
print(f"حلقه + split      : {1000 * splitting:>6.3f} ms")
print(f"کلِ نسخهٔ ۲        : {1000 * whole:>6.3f} ms")
print(f"سهمِ split         : {100 * (splitting - empty) / whole:>4.0f} درصد")
print(f"سهمِ شمارش         : {100 * (whole - splitting) / whole:>4.0f} درصد")
print(f"\nسقفِ هر بهینه‌سازیِ شمارش: {100 * (whole - splitting) / whole:.0f} درصد")
حلقهٔ خالی        :  0.099 ms
حلقه + split      :  2.232 ms
کلِ نسخهٔ ۲        :  4.486 ms
سهمِ split         :   48 درصد
سهمِ شمارش         :   50 درصد

سقفِ هر بهینه‌سازیِ شمارش: 50 درصد

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

و حالا آخرین حساب، که تصمیم را قطعی می‌کند:

gain = min(runs2) - min(runs3)
print(f"صرفه‌جویی در هر فایل      : {gain:.3f} ms")
print(f"صرفه‌جویی در یک شبانه‌روز : {gain * 60 * 24 / 1000:.2f} ثانیه")
print(f"برای صرفه‌جوییِ یک ثانیه در یک اجرا، n باید "
      f"{N * (1000 / gain) / 1_000_000:,.0f} میلیون سطر شود")
print(f"بازهٔ اعلام‌شدهٔ n         : حداکثر {N:,} سطر")
صرفه‌جویی در هر فایل      : 0.081 ms
صرفه‌جویی در یک شبانه‌روز : 0.12 ثانیه
برای صرفه‌جوییِ یک ثانیه در یک اجرا، n باید 246 میلیون سطر شود
بازهٔ اعلام‌شدهٔ n         : حداکثر 20,000 سطر

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

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ سه نسخه از یک تابع روی یک سیاههٔ یکسان، با جوابِ برابرِ تأییدشده. در کدام بازهٔ n؟ جدولِ رشد ۵٬۰۰۰ تا ۴۰٬۰۰۰ سطر؛ بقیهٔ اندازه‌گیری‌ها در n = 20,000، همان بازهٔ اعلام‌شده. با چند تکرار، و کمینه یا میانگین؟ پنج تا هفت تکرار به‌علاوهٔ گرم‌کننده، کمینه — و برای پراکندگی، پانزده گزارشِ کاملِ پروتکل، چون خودِ نوسان موضوعِ اندازه‌گیری بود.

۵. هزینه‌ای که در هیچ جدولِ زمانی نیست#

نسخهٔ چهارم آخرین وسوسه است: شناسه همیشه هفت رقم است، پس شهر همیشه از نویسهٔ هشتم شروع می‌شود. پس اصلاً split نکن.

def v4(rows):
    """نسخهٔ چهارم — بدونِ split، با تکیه بر جای ثابتِ فیلدها."""
    counts = {}
    for line in rows:
        city = line[8:line.index("\t", 8)]
        try:
            counts[city] += 1
        except KeyError:
            counts[city] = 1
    return counts


print(f"نسخهٔ ۲: {1000 * clock(lambda: v2(log), repeat=7):>6.3f} ms")
print(f"نسخهٔ ۴: {1000 * clock(lambda: v4(log), repeat=7):>6.3f} ms")
نسخهٔ ۲:  4.556 ms
نسخهٔ ۴:  4.196 ms

باز هم کمی جلوتر است. حالا روزی که شناسه‌ها یک رقم بلندتر شوند:

print("روی همین سیاهه، جوابِ نسخهٔ ۴ با نسخهٔ ۱ یکی است؟", v1(log) == v4(log))
longer = ["\t".join((f"{i:08d}", "shiraz", "1", "ok", "2", "-", "-")) for i in range(5)]
print("سیاهه‌ای با شناسهٔ هشت‌رقمی:")
print("  نسخهٔ ۱:", v1(longer))
print("  نسخهٔ ۴:", v4(longer))
print("  برابرند؟", v1(longer) == v4(longer))
روی همین سیاهه، جوابِ نسخهٔ ۴ با نسخهٔ ۱ یکی است؟ True
سیاهه‌ای با شناسهٔ هشت‌رقمی:
  نسخهٔ ۱: {'shiraz': 5}
  نسخهٔ ۴: {'': 5}
  برابرند؟ False

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

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

🔧 اگر کار نکرد: نسخهٔ چهارم روی سطرِ خراب همیشه هم ساکت نیست — گاهی می‌شکند، و آن حالتِ بهترش است:

broken = ["0000001shiraz"]
try:
    v4(broken)
except ValueError as err:
    print(f"{type(err).__name__}: {err}")
try:
    v1(broken)
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
ValueError: substring not found
IndexError: list index out of range

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

🤖 از دستیارت بپرس: خروجیِ بخشِ ۳ را جلویش بگذار و بپرس: «آیا نسخهٔ سوم بهتر است؟» — جوابِ درست باید بگوید با این پراکندگی نمی‌شود گفت. بعد بپرس «چطور مطمئن شوم؟» و ببین آیا هزینهٔ همان اطمینان را هم حساب می‌کند یا نه.

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

کلمه تلفظ به حروف فارسی یعنی چه
stopping criterion استاپینگ کرایتریون شرطی که پیش از شروع نوشته می‌شود و می‌گوید کِی کار تمام است
improvement ceiling ایمپروومنت سیلینگ بیشترین بهبودی که یک تغییر می‌تواند بدهد، حتی اگر بی‌نهایت خوب باشد
silent wrong answer سایلنت رانگ آنسر جوابِ غلطی که هیچ خطایی همراهش نیست

تمرین‌ها

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

در فصل بعد#

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

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

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

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