در این فصل چه یاد میگیری#
سه فصل با دست کار کردیم تا بدانیم پشتِ 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 نشسته و دیده میشود.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.