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

فصل ۵ از ۶

پیشرفت ترم
۰٪

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

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

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

یک گزارشِ چاپی که کنارش همان آزمایش دوباره برپا شده تا نتیجه‌اش وارسی شود

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

  • نُه چیزی را که هر benchmark باید بگوید، از حفظ بنویسی
  • گزارشی بسازی که از خودِ اندازه‌گیری تولید شود، نه از حافظهٔ تو
  • بازتولیدپذیریِ ورودی را ثابت کنی، نه ادعا
  • نتیجه‌ای را که خلافِ انتظارت درآمده، همان‌طور که هست گزارش کنی

قبل از شروع#

از ترمِ ۱ فصلِ ۲ و ۳: پروتکلِ اندازه‌گیری، کمینه، و پراکندگی. از ترمِ ۳ فصلِ ۵: dict و Counter. از فصلِ ۱: برگهٔ شکلِ مسئله.

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

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

۱. ادعایی که نمی‌شود ردش کرد، ادعا نیست#

«روشِ الف دو برابر سریع‌تر است» یک جملهٔ بی‌فایده است. دو برابرِ چه؟ روی چه ورودی‌ای؟ در چه اندازه‌ای؟ با چند تکرار؟ و آیا اصلاً جوابشان یکی بود؟

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

۲. نُه چیزی که هر گزارش باید بگوید#

  1. شکلِ مسئله — سه خانهٔ فصلِ ۱: الگوی دسترسی، نسبتِ خواندن به نوشتن، بازهٔ واقعیِ n.
  2. نامزدها — دقیقاً کدام نسخه‌ها، با کد.
  3. ورودی — چطور ساخته شده و با کدام بذر.
  4. بازهٔ nی که اندازه‌گیری در آن انجام شده — نه بازهٔ آرزو.
  5. پروتکل — چند تکرار، گرم‌کننده، و کمینه یا میانگین.
  6. برابریِ جوابِ نامزدها، با ==.
  7. نتیجه به‌صورتِ نسبت، به‌علاوهٔ پراکندگی.
  8. شرطِ باطل شدن — چه چیزی اگر عوض شود، این تصمیم دیگر معتبر نیست.
  9. حافظهٔ هر نامزد، به بایت، با گفتنِ اینکه چه چیزی شمرده شده و چه چیزی نشده.

بندِ هشتم همان بندی است که گزارش را از تبلیغ جدا می‌کند.

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

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

۳. آزمایش: چهار راهِ شمردن#

مسئله: از یک جریانِ رویداد، تعدادِ رویدادِ هر کاربر را بشمار. شکلِ مسئله: همه‌چیز یک بار خوانده و یک بار شمرده می‌شود؛ بازهٔ n بیست و پنج هزار تا دویست هزار رویداد، با پنج هزار کاربرِ یکتا.

from collections import Counter, defaultdict

DISTINCT = 5_000
N = 200_000


def make_events(n, seed=SEED):
    """n رویداد از DISTINCT کاربر — کاملاً بازتولیدپذیر با همان بذر."""
    rng = random.Random(seed)
    return [f"u{rng.randrange(DISTINCT):05d}" for _ in range(n)]


def count_get(events):
    """راهِ ۱ — dict خالی و get با مقدارِ پیش‌فرض."""
    counts = {}
    for e in events:
        counts[e] = counts.get(e, 0) + 1
    return counts


def count_default(events):
    """راهِ ۲ — defaultdict(int)."""
    counts = defaultdict(int)
    for e in events:
        counts[e] += 1
    return dict(counts)


def count_bulk(events):
    """راهِ ۳ — Counter، یکجا روی کلِ فهرست."""
    return dict(Counter(events))


def count_step(events):
    """راهِ ۴ — Counter، دانه‌دانه."""
    counts = Counter()
    for e in events:
        counts[e] += 1
    return dict(counts)


WAYS = (("dict.get", count_get), ("defaultdict", count_default),
        ("Counter یکجا", count_bulk), ("Counter دانه‌ای", count_step))
events = make_events(N)
reference = count_get(events)
print("هر چهار راه یک جواب می‌دهند؟", all(fn(events) == reference for _, fn in WAYS))
print("رویداد:", f"{N:,}", "· کلیدِ یکتا:", f"{len(reference):,}")
هر چهار راه یک جواب می‌دهند؟ True
رویداد: 200,000 · کلیدِ یکتا: 5,000

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

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

baseline = None
for name, fn in WAYS:
    taken = clock(lambda f=fn: f(events), repeat=3)
    if baseline is None:
        baseline = taken
    print(f"{name:>16}  {1000 * taken:>8.2f} ms   نسبت به dict.get {taken / baseline:>5.2f}")
        dict.get     15.80 ms   نسبت به dict.get  1.00
     defaultdict     17.08 ms   نسبت به dict.get  1.08
    Counter یکجا     11.76 ms   نسبت به dict.get  0.74
 Counter دانه‌ای     33.23 ms   نسبت به dict.get  2.10

۴. نتیجهٔ خلافِ انتظار#

Counter هم سریع‌ترین است و هم کندترین. یکجا 0.74 برابرِ ساده‌ترین کد است و دانه‌دانه 2.10 برابر — یعنی همان ابزارِ مخصوصِ شمردن، در حالتِ دومش بیش از دو برابرِ یک dict خالی خرج برمی‌دارد.

دلیلش این است که Counter یک dict معمولی نیست: نوعی است که با پایتون روی dict ساخته شده، و پایتون میان‌بُری را که برای dict خالص دارد روی آن به‌کار نمی‌برد. این هزینه در تک‌تکِ دویست هزار افزایش پرداخته می‌شود، حتی وقتی همهٔ کلیدها از قبل در ظرف باشند؛ روی همین ماشین در آن حالت هم حدودِ ۱٫۶ برابر کندتر بود. وقتی یکجا صدایش می‌زنی، حلقه اصلاً در پایتون اجرا نمی‌شود.

و defaultdict هم غافلگیریِ کوچکِ خودش را دارد: کمی کندتر از dict.get درآمد، نه سریع‌تر — هرچند این هشت درصد آن‌قدر کوچک است که تا پراکندگی را نسنجیم، طبقِ فصلِ ۴ نمی‌شود رویش حساب کرد.

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

۵. مرتبه یکی است، ثابت نه#

قبل از هر ادعایی باید بدانیم این اختلاف ثابت است یا با n بزرگ می‌شود.

LADDER = [25_000, 50_000, 100_000, 200_000]
streams = {n: make_events(n) for n in LADDER}
for name, fn in (("dict.get", count_get), ("Counter دانه‌ای", count_step)):
    print(f"— {name}")
    table([(n, 1000 * clock(lambda k=n, f=fn: f(streams[k]), repeat=3))
           for n in LADDER], "زمان (ms)", ",.2f")
    print()
— dict.get
         n         زمان (ms)     نسبت به سطر قبل
    25,000              1.90                   —
    50,000              3.89                2.05
   100,000              7.86                2.02
   200,000             15.86                2.02

— Counter دانه‌ای
         n         زمان (ms)     نسبت به سطر قبل
    25,000              4.22                   —
    50,000              8.18                1.94
   100,000             18.81                2.30
   200,000             33.79                1.80

هر دو ستونِ نسبت حولِ 2 — هر دو O(n). پس اختلافشان یک ثابت است و با بزرگ شدنِ n بدتر نمی‌شود. این دقیقاً همان تفکیکی است که ترمِ ۱ فصلِ ۹ ساخت، و بدونِ این جدول، جملهٔ «دو برابر کندتر» می‌توانست به‌غلط به‌عنوان یک تفاوتِ مرتبه‌ای خوانده شود.

۶. بازتولیدپذیری، ثابت‌شده نه ادعاشده#

بندِ سومِ گزارش می‌گوید ورودی با کدام بذر ساخته شده. حالا نشان می‌دهیم که آن بذر واقعاً کار می‌کند:

first = make_events(50_000)
again = make_events(50_000)
other = make_events(50_000, 7)
print("همان بذر، همان ورودی؟", first == again)
print("بذرِ دیگر، ورودیِ دیگر؟", first != other)
print("امضای ورودی:", first[0], first[-1], f"کلیدِ یکتا {len(set(first)):,}")
همان بذر، همان ورودی؟ True
بذرِ دیگر، ورودیِ دیگر؟ True
امضای ورودی: u03610 u02188 کلیدِ یکتا 4,999

✅ چک کن: در make_events بذر را بردار — یعنی random.Random() بدونِ آرگومان — و همان سه سطر را دوباره بگیر. سطرِ اول باید False شود. این تنها خطِ گزارش است که با یک تغییرِ یک‌کلمه‌ای دروغ می‌شود، و به همین دلیل باید ثابت شود نه ادعا.

و حالا آزمونِ سخت‌ترِ بازتولیدپذیری: آیا نتیجه به همین یک بذر بند است؟

print(f"{'بذر':>8}{'dict.get (ms)':>16}{'Counter دانه‌ای (ms)':>24}{'نسبت':>8}")
for seed in (SEED, 7, 99):
    sample = make_events(N, seed)
    fast = clock(lambda: count_get(sample), repeat=3)
    slow = clock(lambda: count_step(sample), repeat=3)
    print(f"{seed:>8}{1000 * fast:>16.2f}{1000 * slow:>24.2f}{slow / fast:>8.2f}")
     بذر   dict.get (ms)    Counter دانه‌ای (ms)    نسبت
    1234           16.16                   33.51    2.07
       7           15.77                   33.15    2.10
      99           17.10                   38.05    2.22

ستونِ ثانیه‌ها تکان می‌خورد و ستونِ نسبت تقریباً نه: 2.07، 2.10، 2.22. این همان قاعدهٔ چهارمِ دوره است — نسبت را ادعا کن، نه ثانیه را — و اینجا با سه بذرِ متفاوت آزمونش دادیم.

۷. گزارش، تولیدشده از خودِ اندازه‌گیری#

گزارشی که با دست تایپ شود، از اندازه‌گیری واگرا می‌شود. پس می‌سازیمش:

def report(title, ways, data, sizes, seed, repeat):
    """نُه بندِ بخشِ ۲، همه از خودِ اندازه‌گیری."""
    biggest = data[max(sizes)]
    truth = ways[0][1](biggest)
    same = all(fn(biggest) == truth for _, fn in ways)
    timings = {name: clock(lambda f=fn: f(biggest), repeat=repeat) for name, fn in ways}
    memory = {name: sys.getsizeof(fn(biggest)) for name, fn in ways}
    best = min(timings, key=timings.get)
    print(f"گزارشِ «{title}»")
    print(f"  ۱. شکلِ مسئله   : یک بار خواندن، یک بار شمردن؛ هیچ پرسشِ بعدی")
    print(f"  ۲. نامزدها      : {'، '.join(name for name, _ in ways)}")
    print(f"  ۳. ورودی و بذر  : make_events، بذرِ {seed}، {len(truth):,} کلیدِ یکتا")
    print(f"  ۴. بازهٔ n      : {min(sizes):,} تا {max(sizes):,}")
    print(f"  ۵. پروتکل       : {repeat} تکرار به‌علاوهٔ گرم‌کننده، کمینه")
    print(f"  ۶. برابریِ جواب : {same}")
    print(f"  ۷. نتیجه        : برندهٔ {best}؛ "
          + "، ".join(f"{n} {timings[n] / timings[best]:.2f}×" for n, _ in ways))
    print(f"  ۸. شرطِ باطل شدن: بازهٔ n یا تعدادِ کلیدِ یکتا عوض شود، یا شمارش")
    print(f"                    دانه‌دانه لازم نباشد و بشود یکجا صدا زد")
    print(f"  ۹. حافظه        : "
          + "، ".join(f"{n} {memory[n]:,}" for n, _ in ways) + " بایت")
    print(f"                    (فقط خودِ dictِ خروجی شمرده شده؛ کلیدها و مقدارها نه،")
    print(f"                     چون هر چهار نامزد دقیقاً همان اشیاء را نگه می‌دارند)")


report("چهار راهِ شمردن", WAYS, streams, LADDER, SEED, 3)
گزارشِ «چهار راهِ شمردن»
  ۱. شکلِ مسئله   : یک بار خواندن، یک بار شمردن؛ هیچ پرسشِ بعدی
  ۲. نامزدها      : dict.get، defaultdict، Counter یکجا، Counter دانه‌ای
  ۳. ورودی و بذر  : make_events، بذرِ 1234، 5,000 کلیدِ یکتا
  ۴. بازهٔ n      : 25,000 تا 200,000
  ۵. پروتکل       : 3 تکرار به‌علاوهٔ گرم‌کننده، کمینه
  ۶. برابریِ جواب : True
  ۷. نتیجه        : برندهٔ Counter یکجا؛ dict.get 1.52×، defaultdict 1.60×، Counter یکجا 1.00×، Counter دانه‌ای 3.10×
  ۸. شرطِ باطل شدن: بازهٔ n یا تعدادِ کلیدِ یکتا عوض شود، یا شمارش
                    دانه‌دانه لازم نباشد و بشود یکجا صدا زد
  ۹. حافظه        : dict.get 103,856، defaultdict 103,856، Counter یکجا 103,856، Counter دانه‌ای 103,856 بایت
                    (فقط خودِ dictِ خروجی شمرده شده؛ کلیدها و مقدارها نه،
                     چون هر چهار نامزد دقیقاً همان اشیاء را نگه می‌دارند)

هیچ عددی از این گزارش با دست نوشته نشده. اگر فردا یکی از توابع را عوض کنی، گزارش خودش عوض می‌شود — و این تنها راهی است که گزارش و واقعیت از هم دور نمی‌افتند.

بندِ نهم اینجا جوابِ کسل‌کننده‌ای می‌دهد و همان جواب مهم است: هر چهار نامزد 103,856 بایت. یعنی حافظه در این تصمیم هیچ نقشی ندارد — هر چهار راه در آخر همان یک dict با همان پنج هزار کلید را می‌سازند. ولی این را باید اندازه گرفت تا بشود گفتش. فصلِ ۳ نشان داد جایی که این عدد یکی نباشد، می‌تواند تنها چیزی باشد که تصمیم را تعیین می‌کند.

و یک نقص دارد که باید صریح گفته شود: بندِ هفتمِ فهرستِ بخشِ ۲ نسبت به‌علاوهٔ پراکندگی می‌خواست و این گزارش فقط نسبت را می‌دهد. پس هنوز نمی‌تواند بگوید فاصلهٔ 1.52 و 1.60 واقعی است یا نویز — دقیقاً همان چیزی که در فصلِ ۴ تصمیم را عوض کرد. تمرینِ ستاره‌دار همین را وصله می‌کند.

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

🔧 اگر کار نکرد: Counter و dict هر دو یک پیش‌شرطِ مشترک دارند، و اگر رویدادهایت به‌جای رشته چیزِ دیگری باشند همان‌جا می‌شکند:

try:
    Counter()[["u1", "u2"]] += 1
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
TypeError: unhashable type: 'list'

همان TypeError ترمِ ۳ فصلِ ۶. اگر کلیدِ شمارشت مرکب است، tuple بساز نه list. و این هم بندی از گزارش است: نتیجهٔ بالا فقط برای کلیدهای hashable معنا دارد.

🤖 از دستیارت بپرس: خروجیِ بخشِ ۳ را جلویش بگذار و بپرس: «چرا Counter دانه‌ای از یک dict ساده کندتر است؟» بعد بپرس «این نتیجه در چه شرایطی برعکس می‌شود؟» — جوابِ درست باید یکی از نُه بندِ گزارش را نام ببرد، نه یک قاعدهٔ کلی.

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

کلمه تلفظ به حروف فارسی یعنی چه
reproducibility ریپرودیوسیبیلیتی اینکه دیگری بتواند دقیقاً همان اندازه‌گیری را دوباره بگیرد
falsifiable claim فالسیفایبل کلیم ادعایی که راهِ غلط درآوردنش هم در خودش نوشته شده
invalidation condition این‌ولیدیشن کاندیشن شرطی که اگر عوض شود، تصمیم دیگر معتبر نیست

تمرین‌ها

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

در فصل بعد#

پنج فصل روش ساختیم و هیچ‌کدام یک مسئلهٔ کامل را از اول تا آخر نبردند.

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

و برنده‌اش آنی نیست که فکر می‌کنی: یکی از دو نامزد هم سریع‌تر است و هم کم‌حافظه‌تر — و انتخابِ غلط است.

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

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