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

فصل ۵ از ۷

پیشرفت ترم
۰٪

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

سه فصل با دست کار کردیم تا بدانیم پشتِ set و dict چه می‌گذرد. حالا سراغِ خودشان می‌رویم و همان پرسشِ فصلِ ۱ را می‌پرسیم: صد هزار پرسش، و ظرفی که هر بار دو برابر می‌شود.

جدولِ list ستونِ نسبتِ نزدیکِ 2 می‌دهد و جدولِ set ستونِ نسبتِ نزدیکِ 1 — و در بزرگ‌ترین اندازه، اختلافشان چند صد برابر است. بعد شمارش و گروه‌بندی را با dict انجام می‌دهیم. ولی مهم‌ترین بخشِ فصل جای دیگری است: ساختنِ set خودش خرج دارد، و برای یکی دو پرسش، list واقعاً برنده است. نقطهٔ سربه‌سرش را با عدد پیدا می‌کنیم.

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

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

  • عضویت، شمارش و گروه‌بندی را با هزینهٔ ثابت انجام بدهی
  • defaultdict را جای KeyError بگذاری
  • نقطهٔ سربه‌سرِ set و جست‌وجوی خطی را برای مسئلهٔ خودت پیدا کنی

قبل از شروع#

از فصلِ ۳: hash table، load factor و اینکه هزینهٔ یک جست‌وجو به تعدادِ کلیدها بند نیست. set و dict در پایتون همان ایده‌اند: جای کلید از hashش می‌آید و جدول با پر شدن بزرگ می‌شود. فرقشان در برخورد است: زنجیری در کار نیست و کلیدِ دوم به خانهٔ خالیِ دیگری داخلِ خودِ جدول می‌رود.

از فصلِ ۱: جست‌وجوی خطی و هزینهٔ O(n)ش.

از ترمِ ۱ فصلِ ۹: نقطهٔ تقاطع — الگوریتمِ با مرتبهٔ بدتر که در n کوچک برنده است. این فصل یک نمونهٔ دیگرش را می‌سازد.

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

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

۱. یک تابع، دو ظرف#

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

rng = random.Random(SEED)
LADDER = [250, 500, 1_000, 2_000]
ASKS = 100_000
base = [f"user-{rng.randrange(10 ** 9)}" for _ in range(2_000)]
pools = {n: base[:n] for n in LADDER}
known = {n: set(base[:n]) for n in LADDER}
questions = [base[rng.randrange(250)] if i % 4 == 0
             else f"user-{rng.randrange(10 ** 9)}" for i in range(ASKS)]


def hits_in(container, asked):
    """به همهٔ پرسش‌ها جواب می‌دهد؛ ظرف هر چه باشد، کد یکی است."""
    hits = 0
    for q in asked:
        if q in container:
            hits += 1
    return hits


print("list و set یک جواب می‌دهند؟",
      all(hits_in(pools[n], questions) == hits_in(known[n], questions) for n in LADDER))
print("تعدادِ پرسش:", len(questions), "· تعدادِ جوابِ «بله»:", hits_in(known[250], questions))
list و set یک جواب می‌دهند؟ True
تعدادِ پرسش: 100000 · تعدادِ جوابِ «بله»: 25000

سطرِ اول اجباری است. دو ظرفی که جوابِ متفاوت بدهند، دو مسئلهٔ متفاوت‌اند نه دو راه‌حل برای یک مسئله. یک‌چهارمِ پرسش‌ها جوابِ «بله» می‌گیرند و بقیه «نه» — و «نه» گران‌ترین حالتِ جست‌وجوی خطی است، چون کلِ ظرف دیده می‌شود.

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

print("— پرسیدن از list")
table([(n, 1000 * clock(lambda c=pools[n]: hits_in(c, questions), repeat=2))
       for n in LADDER], "زمان (ms)", ",.1f")
print("\n— پرسیدن از set")
table([(n, 1000 * clock(lambda c=known[n]: hits_in(c, questions), repeat=3))
       for n in LADDER], "زمان (ms)", ",.1f")
— پرسیدن از list
         n         زمان (ms)     نسبت به سطر قبل
       250             236.4                   —
       500             452.7                1.91
     1,000             914.4                2.02
     2,000           1,648.1                1.80

— پرسیدن از set
         n         زمان (ms)     نسبت به سطر قبل
       250               2.8                   —
       500               2.6                0.91
     1,000               2.9                1.13
     2,000               2.6                0.91

ستونِ بالا نزدیکِ 2 و ستونِ پایین نزدیکِ 1.

ستونِ بالا یعنی هزینهٔ هر پرسش با n بالا می‌رود: O(n). ستونِ پایین یعنی هزینهٔ هر پرسش به n هیچ کاری ندارد: O(1). عددهای set حولِ یک عددِ ثابت بالا و پایین می‌روند و همان بالا و پایین رفتن هم نویزِ ترمِ ۱ فصلِ ۳ است، نه یک روند.

n = 2_000
slow = clock(lambda: hits_in(pools[n], questions), repeat=2)
fast = clock(lambda: hits_in(known[n], questions), repeat=3)
print(f"n = {n:,} و {ASKS:,} پرسش  ·  list: {1000 * slow:,.1f} ms"
      f"  ·  set: {1000 * fast:,.1f} ms  ·  نسبت: {slow / fast:,.0f}")
n = 2,000 و 100,000 پرسش  ·  list: 1,694.9 ms  ·  set: 3.0 ms  ·  نسبت: 572

چند صد برابر، با یک list که فقط دو هزار عضو دارد. و عددِ ثانیه روی ماشینِ تو فرق می‌کند؛ نسبت است که نباید فرق کند.

و مهم‌تر: این نسبت خودش با n بزرگ می‌شود. روی یک list صد هزارتایی همین کد حدودِ پنجاه برابرِ این‌جا طول می‌کشد و set تقریباً همان‌قدر می‌ماند که حالا هست.

۲. ولی ساختنِ set رایگان نیست#

در جدولِ بالا set را از قبل ساخته بودیم. در کارِ واقعی باید ساختش را هم حساب کرد، و ساختن یعنی n بار hash گرفتن و n بار درج کردن.

big = [f"user-{rng.randrange(10 ** 9)}" for _ in range(200_000)]
table([(n, 1000 * clock(lambda v=big[:n]: set(v), repeat=3))
       for n in (25_000, 50_000, 100_000, 200_000)], "زمانِ ساخت (ms)", ",.1f")
         n   زمانِ ساخت (ms)     نسبت به سطر قبل
    25,000               1.3                   —
    50,000               1.9                1.47
   100,000               5.2                2.77
   200,000              12.8                2.47

نسبت‌ها حولِ 2 می‌چرخند و هیچ‌کدام 2.00 نیستند — یعنی ساخت خطی است، ولی با ثابتی که در اندازه‌های بزرگ‌تر کمی بدتر می‌شود. این بالا رفتنِ ملایم Big-O نیست؛ از حافظه می‌آید: جدولِ کوچک در حافظهٔ نزدیکِ پردازنده جا می‌شود و جدولِ بزرگ نه — همان چیزی که ترمِ ۲ فصلِ ۱ با خواندنِ به‌هم‌ریخته نشانش داد.

۳. نقطهٔ سربه‌سر#

حالا سؤالی که در عمل باید بپرسی: اگر فقط چند پرسش داری، آیا ارزشش را دارد که کلِ set را بسازی؟ ظرف را ثابت نگه می‌داریم و تعدادِ پرسش‌ها را دو برابر می‌کنیم.

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

print(f"{'تعدادِ پرسش':>12}{'list (ms)':>12}{'set (ms)':>12}{'برنده':>8}")
for m in (1, 2, 4, 8, 16, 32):
    asked = [f"user-{rng.randrange(10 ** 9)}" for _ in range(m)]
    with_list = 1000 * clock(lambda: hits_in(big, asked), repeat=3)
    with_set = 1000 * clock(lambda: hits_in(set(big), asked), repeat=3)
    print(f"{m:>12}{with_list:>12.2f}{with_set:>12.2f}"
          f"{('list' if with_list < with_set else 'set'):>8}")
 تعدادِ پرسش   list (ms)    set (ms)   برنده
           1        2.41       12.25    list
           2        4.84       12.90    list
           4        9.94       12.42    list
           8       21.30       12.92     set
          16       38.71       12.22     set
          32       79.00       12.59     set

نقطهٔ سربه‌سر بینِ چهار و هشت پرسش است.

ستونِ list دقیقاً دو برابر می‌شود، چون هر پرسش یک پویشِ کاملِ ظرف است. ستونِ set تقریباً ثابت می‌ماند، چون تقریباً تمامش هزینهٔ ساخت است و ساخت به تعدادِ پرسش‌ها کاری ندارد.

یعنی برای یک پرسشِ تنها روی یک list دویست هزارتایی، ساختنِ set حدودِ پنج برابر کندتر است. این همان نقطهٔ تقاطعِ ترمِ ۱ فصلِ ۹ است، این بار برای دو ظرف — و همان‌جا هم نوشتیم که nِ خودت را بگو؛ این‌جا باید mِ خودت را هم بگویی.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک تابعِ ثابت که فقط ظرفش عوض می‌شود — list در برابرِ set — با پرسش‌های کاملاً یکسان و جوابِ تأییدشدهٔ برابر. در کدام بازهٔ n؟ ظرفِ ۲۵۰ تا ۲٬۰۰۰ با صد هزار پرسشِ ثابت برای مرتبه، ظرفِ ۲۵٬۰۰۰ تا ۲۰۰٬۰۰۰ برای هزینهٔ ساخت، و ظرفِ ثابتِ ۲۰۰٬۰۰۰ با ۱ تا ۳۲ پرسش برای نقطهٔ سربه‌سر. با چند تکرار، و کمینه یا میانگین؟ دو تا سه تکرار به‌علاوهٔ گرم‌کننده، کمینه.

۴. شمارش با dict#

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

LEVELS = ("INFO", "WARN", "ERROR")
rng2 = random.Random(SEED)
log = [f"{i:06d} {rng2.choice(LEVELS)} unit-{rng2.randrange(20)}" for i in range(50_000)]
print(log[0])
print(log[1])

counts = {}
try:
    for line in log:
        counts[line.split(" ")[1]] += 1
except KeyError as err:
    print(f"{type(err).__name__}: {err}")
000000 WARN unit-3
000001 INFO unit-2
KeyError: 'WARN'

🔧 اگر کار نکرد: KeyError یعنی کلیدی خواسته‌ای که در dict نیست، و counts[k] += 1 اول می‌خواند و بعد می‌نویسد. دقت کن که خطا روی همان سطرِ اول افتاد، پس هیچ شمارشی انجام نشده. سه راهِ درست هست و ما وسطی را می‌گیریم: counts.get(k, 0) + 1، یا defaultdict(int)، یا Counter که از سرنخ می‌شناسی‌اش.

from collections import defaultdict

counts = defaultdict(int)
for line in log:
    counts[line.split(" ")[1]] += 1
for level in LEVELS:
    print(f"{level:>6}: {counts[level]:>7,}")
  INFO:  16,839
  WARN:  16,659
 ERROR:  16,502

defaultdict(int) یعنی «اگر کلید نبود، از صفر شروع کن». و کارِ مهم‌ترش این است که سه سطرِ شرطی را از حلقه بیرون می‌برد — هر سطری که از حلقه بیرون برود، هم کد را ساده‌تر می‌کند و هم یک جای کمتر برای اشتباه می‌گذارد.

و هزینه‌اش: پنجاه هزار سطر با یک عبور، بدونِ هیچ جست‌وجویی. با list باید برای هر سطر می‌گشتی که «این سطح را قبلاً دیده‌ام یا نه». با سه سطح این گشتن کوتاه است، ولی با کلیدهای زیاد همان O(n²)ی می‌شود که ترمِ ۲ فصلِ ۵ نشانش داد.

۵. گروه‌بندی با defaultdict(list)#

همان ایده، با یک list به‌جای یک عدد: به‌ازای هر کلید، همهٔ سطرهایش را جمع کن.

by_unit = defaultdict(list)
for line in log:
    parts = line.split(" ")
    by_unit[parts[2]].append(parts[1])
print("تعدادِ واحدها:", len(by_unit))
for unit in ("unit-0", "unit-1", "unit-19"):
    rows = by_unit[unit]
    print(f"{unit:>8}: {len(rows):>6,} سطر  ·  ERROR: {rows.count('ERROR'):>6,}")
تعدادِ واحدها: 20
  unit-0:  2,521 سطر  ·  ERROR:    865
  unit-1:  2,463 سطر  ·  ERROR:    787
 unit-19:  2,532 سطر  ·  ERROR:    824

یک عبور روی داده، و حالا هر پرسشی دربارهٔ هر واحد، یک lookup است. این الگو — یک بار ساختنِ یک index، بعد هزار بار پرسیدن از آن — همان چیزی است که در بخشِ ۳ نقطهٔ سربه‌سرش را پیدا کردیم.

✅ چک کن: در بخشِ ۱، known را از set(base[:n]) به list(base[:n]) تغییر بده و بدونِ هیچ تغییرِ دیگری جدولِ دوم را بگیر. جواب‌ها باید دقیقاً همان بمانند و ستونِ نسبت باید از 1 به 2 برود. اگر جواب‌ها هم عوض شدند، جایی برشِ [:n] را جا انداخته‌ای — و آن‌وقت داری دو ظرفِ متفاوت را با دو دادهٔ متفاوت می‌سنجی، که هیچ نتیجه‌ای ندارد.

⚠️ مواظب باش: set ترتیب ندارد و این را باید جدی گرفت:

units = {"unit-3", "unit-1", "unit-2"}
print("مرتب‌شده:", sorted(units))
try:
    print(units[0])
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
مرتب‌شده: ['unit-1', 'unit-2', 'unit-3']
TypeError: 'set' object is not subscriptable

پیام صریح است: set اندیس ندارد، چون جای هر عضو از hashش می‌آید نه از ترتیبِ ورودش. و یک نکتهٔ ظریف‌تر که فصلِ ۲ زمینه‌اش را ساخت: چون hash رشته‌ها بینِ دو اجرا عوض می‌شود، ترتیبِ چاپِ یک set از رشته‌ها هم بینِ دو اجرا عوض می‌شود. اگر خروجی‌ات باید تکرارپذیر باشد، sorted را جا نینداز. dict بر عکس، ترتیبِ درج را نگه می‌دارد و می‌شود به آن تکیه کرد.

🤖 از دستیارت بپرس: «چه وقت‌هایی list برای پرسشِ عضویت از set بهتر است؟» بعد این را هم بپرس: «اگر ظرفم صد هزار عضو دارد و فقط یک بار می‌پرسم، کدام را انتخاب کنم؟» — جوابِ درست باید هزینهٔ ساخت را جدا حساب کند؛ اگر دستیارت بدونِ چون‌وچرا گفت set، جدولِ بخشِ ۳ را جلویش بگذار.

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

کلمه تلفظ به حروف فارسی یعنی چه
defaultdict دیفالت‌دیکت dictی که برای کلیدِ تازه خودش یک مقدارِ اولیه می‌سازد
break-even point بریک-ایون پوینت تعدادِ پرسشی که از آن به بعد ساختنِ ساختار صرف می‌کند
index ایندکس ساختاری که یک بار ساخته می‌شود تا پرسش‌های بعدی ارزان شوند

تمرین‌ها

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

در فصل بعد#

تا حالا هر کلیدی که به set و dict داده‌ایم رشته یا عدد بوده. فصلِ بعد می‌پرسد چه چیزی اصلاً می‌تواند کلید باشد — و از یک خطای واقعی شروع می‌کند: TypeError: unhashable type: 'list'.

بعد قاعده‌ای را می‌بینی که پشتِ آن خطاست، و یک dict که سه بار درج می‌شود و آخرش یک عضو دارد. آخرِ فصل هم، با همان hash table دست‌سازِ فصلِ ۳، کلیدی را که بعد از درج عوض شده گم می‌کنیم — در حالی که خودش هنوز همان‌جا داخلِ bucket نشسته و دیده می‌شود.

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

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