در این فصل چه یاد میگیری#
یک جملهٔ مسئله میگیریم — «پرتکرارترین برچسبها را نشان بده» — و دو راهِ حل برایش مینویسیم که جوابِ کاملاً یکسان میدهند.
بعد یک عدد را عوض میکنیم که در آن جمله اصلاً نیامده: اینکه هر چند رویداد یک بار جواب لازم است. برنده جابهجا میشود. در یک شکلِ مسئله، نسخهٔ «زنده» ۹۶ برابر کمکارتر است؛ در شکلِ دیگر، همان نسخهٔ زنده سیزده برابر بیشتر کار میکند و هیچ سودی نمیدهد.
پس این فصل دربارهٔ ساختارِ داده نیست. دربارهٔ برگهای است که قبل از انتخابِ ساختار پر میشود.
آخر این فصل میتوانی:
- الگوی دسترسیِ یک مسئله را در سه خانه بنویسی، پیش از آنکه هیچ ساختاری انتخاب کنی
- نسبتِ خواندن به نوشتن را بهعنوان یک عدد اندازه بگیری، نه یک احساس
- نشان بدهی که بدونِ بازهٔ واقعیِ
nهیچکدام از این دو عدد تصمیم نمیسازد - قیدی را پیدا کنی که تصمیم را تعیین میکند — همان یک خانهای که بهتنهایی جواب را عوض میکند
قبل از شروع#
از ترمِ ۲ فصلِ ۸: الگوی دسترسی و اینکه «کدام ظرف بهتر است؟» سؤالِ بیجوابی است. از ترمِ ۴ فصلِ ۸: sorted با key. از ترمِ ۳ فصلِ ۵: شمارش با dict.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | حدودِ یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. یک جملهٔ مسئله که تصمیم نمیسازد#
این جمله را به ده نفر بده و ده کدِ متفاوت تحویل بگیر:
«رویدادها میآیند، هر رویداد یک برچسب دارد. پنج برچسبِ پرتکرار را نشان بده.»
جمله کامل بهنظر میرسد. ورودی مشخص است، خروجی مشخص است، و هر کسی میتواند فوری کدش را بنویسد. ولی سه چیز در آن نیست و بدونِ هر سه، هر تصمیمی سلیقه است:
- الگوی دسترسی — چه عملیاتی، چند بار؟
- نسبتِ خواندن به نوشتن — بهازای هر چند رویداد، یک بار جواب لازم است؟
- بازهٔ واقعیِ
n— چند رویداد؟ صد؟ صد هزار؟
به این سه با هم میگوییم شکلِ مسئله، و قاعدهٔ سختِ این ترم همین است: تصمیمی که این سه را ننوشته باشد، سلیقه است نه مهندسی.
۲. داده و دو نامزد#
K = 5
def make_stream(n, seed=SEED):
"""n رویداد؛ دامنهٔ برچسبها با n بزرگ میشود و چند برچسب عمداً پرتکرارند."""
rng = random.Random(seed)
vocab = [f"tag-{i:05d}" for i in range(n // 2)]
hot = vocab[: max(1, n // 100)]
return [rng.choice(hot) if rng.random() < 0.30 else rng.choice(vocab)
for _ in range(n)]
sample = make_stream(12)
print("دوازده رویدادِ اول:", " ".join(t[4:] for t in sample))
print("برچسبِ یکتا در ۲٬۰۰۰ رویداد:", len(set(make_stream(2_000))))
دوازده رویدادِ اول: 00003 00000 00004 00000 00000 00000 00000 00004 00003 00000 00000 00001
برچسبِ یکتا در ۲٬۰۰۰ رویداد: 750
دامنهٔ برچسبها با n رشد میکند و این عمدی است: اگر دامنه ثابت میماند، هیچکدام از جدولهای این فصل چیزی نشان نمیداد.
حالا دو نامزد. نامزدِ «بازسازی» هر بار که جواب لازم است، از روی شمارندهها یک sorted کامل میگیرد. نامزدِ «زنده» یک فهرستِ پنجتایی از برترها را در هر رویداد بهروز نگه میدارد و موقعِ سؤال فقط آن را تحویل میدهد.
def answer_by_rebuild(stream, k, every):
"""نامزد ۱ — هر بار که جواب لازم است، کلِ شمارندهها را مرتب کن."""
counts, answer = {}, []
for i, tag in enumerate(stream, 1):
counts[tag] = counts.get(tag, 0) + 1
if i % every == 0:
answer = sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))[:k]
return answer
def answer_live(stream, k, every):
"""نامزد ۲ — یک فهرستِ k تایی از برترها را در هر رویداد زنده نگه دار."""
counts, top, answer = {}, [], []
for i, tag in enumerate(stream, 1):
counts[tag] = counts.get(tag, 0) + 1
if tag in top:
top.sort(key=lambda t: (-counts[t], t))
elif len(top) < k:
top.append(tag)
top.sort(key=lambda t: (-counts[t], t))
elif (-counts[tag], tag) < (-counts[top[-1]], top[-1]):
top[-1] = tag
top.sort(key=lambda t: (-counts[t], t))
if i % every == 0:
answer = [(t, counts[t]) for t in top]
return answer
streams = {n: make_stream(n) for n in SIZES}
print("جوابِ دو نامزد در هر چهار اندازه یکی است؟",
all(answer_by_rebuild(streams[n], K, 1) == answer_live(streams[n], K, 1)
for n in SIZES))
print("پنج برچسبِ برتر در n = 2,000:", answer_by_rebuild(streams[2_000], K, 1))
جوابِ دو نامزد در هر چهار اندازه یکی است؟ True
پنج برچسبِ برتر در n = 2,000: [('tag-00003', 40), ('tag-00009', 40), ('tag-00016', 37), ('tag-00010', 36), ('tag-00017', 35)]
این سطر اول میآید، نه آخر. دو نامزدی که جوابِ متفاوت بدهند، دو مسئلهٔ متفاوتاند و مقایسهٔ سرعتشان بیمعناست.
۳. واحدِ اندازهگیری: نگاه#
برای اینکه عددها به ماشین بند نباشند، بهجای ثانیه نگاه میشماریم: هر بار که برای تولیدِ جواب به یک عنصر نگاه میشود، یکی به شمارنده اضافه میشود. نامزدِ بازسازی در هر لحظهٔ سؤال به همهٔ شمارندههایش نگاه میکند؛ نامزدِ زنده در هر رویداد به فهرستِ کوچکِ برترهایش.
def looks_by_rebuild(stream, every):
counts, looks = {}, 0
for i, tag in enumerate(stream, 1):
counts[tag] = counts.get(tag, 0) + 1
if i % every == 0:
looks += len(counts)
return looks
def looks_live(stream, k):
counts, top, looks = {}, [], 0
for tag in stream:
counts[tag] = counts.get(tag, 0) + 1
looks += len(top)
if tag not in top:
if len(top) < k:
top.append(tag)
elif (-counts[tag], tag) < (-counts[top[-1]], top[-1]):
top[-1] = tag
top.sort(key=lambda t: (-counts[t], t))
return looks
print("نگاه در n = 2,000 · بازسازی در هر رویداد:", f"{looks_by_rebuild(streams[2_000], 1):,}")
print("نگاه در n = 2,000 · زنده :", f"{looks_live(streams[2_000], K):,}")
نگاه در n = 2,000 · بازسازی در هر رویداد: 956,399
نگاه در n = 2,000 · زنده : 9,985
نزدیکِ صد برابر اختلاف، در همان n و روی همان جریان. بخشِ بعد نشان میدهد این اختلاف با بزرگ شدنِ n چه میکند.
۴. شکلِ اول: جواب بعد از هر رویداد#
فرض کن این یک تابلوی زنده است و بعد از هر رویداد باید بهروز شود. پس نسبتِ خواندن به نوشتن یک به یک است.
🤔 اول حدس بزن: برای هر دو نامزد ستونِ نسبت را بنویس.
4یعنیO(n²)و2یعنیO(n)— و برای نامزدِ بازسازی دقت کن که در هر رویداد چند شمارنده وجود دارد.
print("— جواب بعد از هر رویداد · نامزدِ بازسازی")
table([(n, looks_by_rebuild(streams[n], 1)) for n in SIZES], "نگاه", ",d")
print("\n— جواب بعد از هر رویداد · نامزدِ زنده")
table([(n, looks_live(streams[n], K)) for n in SIZES], "نگاه", ",d")
— جواب بعد از هر رویداد · نامزدِ بازسازی
n نگاه نسبت به سطر قبل
1,000 238,597 —
2,000 956,399 4.01
4,000 3,756,857 3.93
8,000 15,108,144 4.02
— جواب بعد از هر رویداد · نامزدِ زنده
n نگاه نسبت به سطر قبل
1,000 4,985 —
2,000 9,985 2.00
4,000 19,985 2.00
8,000 39,985 2.00
4.01 در برابرِ 2.00: O(n²) در برابرِ O(n). در n = 8,000 این یعنی ۱۵ میلیون نگاه در برابرِ چهل هزار تا — نزدیکِ ۳۷۸ برابر، و این نسبت با هر دو برابر شدنِ n خودش دو برابر میشود.
نسبتِ 2.00ِ نامزدِ زنده هم دقیقاً همان چیزی است که انتظار میرفت: در هر رویداد حداکثر به پنج عنصر نگاه میکند، پس کلِ نگاهها حدودِ 5n است.
تا اینجا نتیجه روشن بهنظر میرسد. حالا فقط یک خانه از برگهٔ شکلِ مسئله را عوض میکنیم.
۵. شکلِ دوم: جواب فقط یک بار، در آخر#
فرض کن این یک گزارشِ شبانه است: رویدادها تمامِ روز میآیند و یک بار، آخرِ شب، جواب لازم است.
print("— جواب فقط یک بار در آخر · نامزدِ بازسازی")
table([(n, looks_by_rebuild(streams[n], n)) for n in SIZES], "نگاه", ",d")
print("\n— همان کار با نامزدِ زنده (به every بیربط است)")
table([(n, looks_live(streams[n], K)) for n in SIZES], "نگاه", ",d")
— جواب فقط یک بار در آخر · نامزدِ بازسازی
n نگاه نسبت به سطر قبل
1,000 379 —
2,000 750 1.98
4,000 1,500 2.00
8,000 3,027 2.02
— همان کار با نامزدِ زنده (به every بیربط است)
n نگاه نسبت به سطر قبل
1,000 4,985 —
2,000 9,985 2.00
4,000 19,985 2.00
8,000 39,985 2.00
هر دو ستونِ نسبت حالا 2 هستند — هر دو O(n) — و برنده عوض شده است.
در n = 8,000 نامزدِ بازسازی ۳٬۰۲۷ نگاه میکند و نامزدِ زنده ۳۹٬۹۸۵: بیش از سیزده برابر بیشتر، برای جوابی که فقط یک بار پرسیده میشود. نامزدِ زنده تمامِ روز فهرستِ برترها را بهروز نگه داشته و کسی حتی یک بار نگاهش نکرده.
همان دو کد، همان داده، همان n — و همان یک جملهٔ مسئله. تنها چیزی که فرق کرد، عددی بود که در جملهٔ مسئله نیامده بود.
✅ چک کن:
Kرا به1تغییر بده و فقطlooks_liveرا دوباره بگیر. عدد باید تقریباً برابرِ خودِnشود، چون در هر رویداد به یک عنصر نگاه میشود. اگر عوض نشد،Kرا جایی بهصورتِ عددِ ثابت نوشتهای.
۶. قیدی که تصمیم را تعیین میکند#
سه خانهٔ برگه هموزن نیستند. معمولاً یکی از آنها بهتنهایی جواب را تعیین میکند و بقیه فقط حاشیهاند. اینجا آن خانه نسبتِ خواندن به نوشتن است، و میشود نقطهٔ چرخشش را دقیق پیدا کرد.
N = 2_000
stream = streams[N]
live = looks_live(stream, K)
print(f"n = {N:,} · نگاهِ نامزدِ زنده ثابت است: {live:,}\n")
print(f"{'هر چند رویداد یک جواب':>24}{'بازسازی':>14}{'زنده':>12}{'برنده':>10}")
crossing = None
for every in (1, 10, 25, 50, 100, 200, 500, 1_000, 2_000):
rebuilt = looks_by_rebuild(stream, every)
if crossing is None and rebuilt < live:
crossing = every
print(f"{every:>24,}{rebuilt:>14,}{live:>12,}"
f"{('زنده' if live < rebuilt else 'بازسازی'):>10}")
print(f"\nنقطهٔ چرخش: از یک جواب در هر {crossing} رویداد به بعد، بازسازی کمکارتر است.")
n = 2,000 · نگاهِ نامزدِ زنده ثابت است: 9,985
هر چند رویداد یک جواب بازسازی زنده برنده
1 956,399 9,985 زنده
10 95,983 9,985 زنده
25 38,614 9,985 زنده
50 19,494 9,985 زنده
100 9,938 9,985 بازسازی
200 5,149 9,985 بازسازی
500 2,255 9,985 بازسازی
1,000 1,270 9,985 بازسازی
2,000 750 9,985 بازسازی
نقطهٔ چرخش: از یک جواب در هر 100 رویداد به بعد، بازسازی کمکارتر است.
100. زیرِ آن، نامزدِ زنده برنده است؛ بالایش، بازسازی. و این عددِ مالِ خودِ الگوریتمهاست: روی هر ماشینی همین است، چون از شمارش درآمده نه از ساعت.
روی ساعت چه میشود؟
print(f"{'هر چند رویداد یک جواب':>24}{'بازسازی (ms)':>16}{'زنده (ms)':>14}{'برنده':>10}")
for every in (1, 10, 100, 1_000, 2_000):
t_rebuild = 1000 * clock(lambda e=every: answer_by_rebuild(stream, K, e), repeat=2)
t_live = 1000 * clock(lambda e=every: answer_live(stream, K, e), repeat=2)
print(f"{every:>24,}{t_rebuild:>16.2f}{t_live:>14.2f}"
f"{('زنده' if t_live < t_rebuild else 'بازسازی'):>10}")
هر چند رویداد یک جواب بازسازی (ms) زنده (ms) برنده
1 349.17 1.62 زنده
10 35.28 1.24 زنده
100 3.80 0.94 زنده
1,000 0.75 1.19 بازسازی
2,000 0.67 1.26 بازسازی
نقطهٔ چرخشِ زمانی جایی بینِ ۱۰۰ و ۱٬۰۰۰ افتاد، نه روی ۱۰۰. دلیلش همان ثابتِ پنهانِ ترمِ ۱ فصلِ ۹ است: sorted کارش را در C انجام میدهد و نگهداشتنِ فهرستِ برترها را ما در پایتون نوشتهایم، پس هر «نگاهِ» بازسازی خیلی ارزانتر از هر «نگاهِ» زنده تمام میشود.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ دو نامزد برای یک مسئله، روی یک جریانِ یکسان، با جوابِ برابرِ تأییدشده در هر چهار اندازه. در کدام بازهٔ
n؟ ۱٬۰۰۰ تا ۸٬۰۰۰ رویداد برای جدولهای رشد، وn = 2,000برای پیدا کردنِ نقطهٔ چرخش. با چند تکرار، و کمینه یا میانگین؟ جدولهای نگاه یک اجرا و قطعیاند؛ جدولِ زمان دو تکرار بهعلاوهٔ گرمکننده، کمینه.
۷. سومین خانه: بازهٔ واقعیِ n#
دو خانه پر شده و هنوز تصمیم کامل نیست، چون هر دو عددِ بالا فقط میگویند کدام نسخه کمکارتر است — نه اینکه اصلاً فرقی میکند یا نه.
small = make_stream(500)
print(f"n = 500 · جواب بعد از هر رویداد")
print(f" بازسازی: {1000 * clock(lambda: answer_by_rebuild(small, K, 1), repeat=3):>7.2f} ms")
print(f" زنده : {1000 * clock(lambda: answer_live(small, K, 1), repeat=3):>7.2f} ms")
n = 500 · جواب بعد از هر رویداد
بازسازی: 16.99 ms
زنده : 0.44 ms
نامزدِ زنده اینجا هم برنده است — ولی بازندهٔ O(n²) روی این ماشین حدودِ هفده میلیثانیه طول کشید. اگر nِ واقعیِ تو هرگز از پانصد بالاتر نمیرود، آن هفده میلیثانیه یعنی مسئلهای وجود ندارد و سادهترین کدی که درست کار کند، انتخابِ درست است. عددِ ثانیه روی ماشینِ تو فرق میکند؛ چیزی که فرق نمیکند این است که با هر دو برابر شدنِ n این عدد چهار برابر میشود — ستونِ نسبتِ بخشِ ۴. از پانصد تا هشت هزار چهار بار دو برابر شدن است، پس همان هفده میلیثانیه به چند ثانیه میرسد.
پس برگهٔ کاملِ این مسئله سه سطر دارد:
- الگوی دسترسی: یک نوشتن بهازای هر رویداد، و یک خواندن بهازای هر
everyرویداد. - نسبتِ خواندن به نوشتن: نقطهٔ چرخش در شمارش
۱ به ۱۰۰است و روی ساعتِ این ماشین جایی بینِ۱ به ۱۰۰و۱ به ۱٬۰۰۰. - بازهٔ واقعیِ
n: زیرِ ۵۰۰ هیچکدام مهم نیست.
🔧 اگر کار نکرد: نامزدِ زنده یک حالتِ مرزی دارد که خیلیها اولین بار در آن میافتند — درخواستِ جواب قبل از رسیدنِ اولین رویداد:
counts = {}
try:
print(max(counts, key=counts.get))
except ValueError as err:
print(f"{type(err).__name__}: {err}")
print("جوابِ درست برای جریانِ خالی:", answer_live([], K, 1))
ValueError: max() iterable argument is empty
جوابِ درست برای جریانِ خالی: []
پیام دقیق است: چیزی برای بیشینه گرفتن وجود ندارد. جوابِ درستِ «پنج برچسبِ برتر از هیچ رویداد» یک خطا نیست، یک فهرستِ خالی است — و answer_live همین را میدهد. این هم بخشی از شکلِ مسئله است: اگر ننوشته باشی که جواب میتواند خالی باشد، هر دو نامزد را با یک حالتِ آزموننشده تحویل دادهای.
🤖 از دستیارت بپرس: «برای انتخابِ ساختارِ داده چه چیزهایی باید از مسئله بدانم؟» بعد این را هم بپرس: «اگر نگویم هر چند وقت یک بار جواب لازم دارم، میتوانی تصمیم بگیری؟» — جوابِ درست باید بگوید نه. اگر بدونِ پرسیدن یک ساختار را نام برد، جدولِ بخشِ ۶ را جلویش بگذار.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| problem shape | پرابلم شِیپ | سه خانهٔ الگوی دسترسی، نسبتِ خواندن به نوشتن و بازهٔ n |
| read/write ratio | ریدرایت رِیشو | چند خواندن بهازای هر نوشتن |
| binding constraint | بایندینگ کانسترینت | همان قیدی که بهتنهایی تصمیم را تعیین میکند |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
برگهٔ شکلِ مسئله سؤالها را میسازد. فصلِ بعد جدولی میسازد که جوابها را کنارِ هم میگذارد: هزینهٔ هر عملیاتِ اصلی روی هر ساختاری که این دوره ساخته، در یک جدول.
و همانجا سه چیز را هم میگوید که هیچ جدولِ هزینهای نمیگوید. اول: خانههایی که این دوره هرگز اندازهشان نگرفته. دوم: خانههایی که در فصلهای مختلف و روی ورودیهای مختلف اندازه گرفته شدهاند و کنارِ هم قابلِ مقایسه نیستند. و سوم، ستونی که در هیچ جدولِ هزینهای وجود ندارد و بزرگترین دروغش هم همان است.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.