در این فصل چه یاد میگیری#
هیچ مفهومِ تازهای. این فصل شش فصلِ قبل را روی یک مسئلهٔ واقعی بهکار میبرد.
یک پیکرهٔ بزرگ از سند داریم و باید بگوییم چند متنِ یکتا در آن هست. سه روش مینویسیم که جوابِ کاملاً یکسان میدهند، برای هر سه جدولِ رشد میگیریم، و آخرش یک تصمیمِ مستند مینویسیم. و نتیجهٔ اصلی در جدول نیست: یک «امضای هوشمند» میسازیم که از هر سه سریعتر است، هیچ خطایی نمیدهد، و از دوازده هزار متنِ یکتا فقط ۳٬۲۱۳تا را میبیند.

آخر این فصل میتوانی:
- سه راهِ حذفِ تکراری را بسنجی و برابریِ جوابشان را ثابت کنی
- هزینهٔ حافظهٔ راهِ سریع را هم گزارش کنی، نه فقط زمانش را
- تشخیص بدهی کِی یک «بهینهسازی» جوابِ مسئله را عوض کرده
قبل از شروع#
از فصلِ ۱: جستوجوی خطی. از فصلِ ۵: set و نقطهٔ سربهسرش. از فصلِ ۶: کلیدِ مرکب با tuple.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | حدودِ یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. صورتِ مسئله#
هر سند یک شناسهٔ یکتا دارد و یک متن. شناسهها هرگز تکرار نمیشوند؛ متنها گاهی. سؤال: چند متنِ یکتا داریم؟
الگوی دسترسی، قبل از هر کدی: سندها یکییکی میآیند و هر متن یک بار پرسیده میشود. پس این عضویت است با n پرسش — و فصلِ ۵ گفت در این بازه ساختن بهصرفه است.
WORDS = ("alpha", "beta", "gamma", "delta", "epsilon", "zeta",
"eta", "theta", "iota", "kappa", "lambda", "mu")
def make_corpus(n, seed=SEED):
"""n سند با شناسهٔ یکتا؛ یکچهارمشان متنی تکراری دارند."""
rng = random.Random(seed)
fresh = n * 3 // 4
texts = [" ".join(rng.choice(WORDS) for _ in range(8)) for _ in range(fresh)]
while len(texts) < n:
texts.append(texts[rng.randrange(fresh)])
rng.shuffle(texts)
return [f"{i:05d}\t{text}" for i, text in enumerate(texts)]
corpus = make_corpus(8)
for doc in corpus[:3]:
print(doc)
print("تعدادِ سند:", len(corpus))
00000 lambda kappa theta kappa theta gamma beta gamma
00001 beta beta zeta delta alpha alpha alpha zeta
00002 lambda kappa theta kappa theta gamma beta gamma
تعدادِ سند: 8
سندِ 00000 و سندِ 00002 متنِ یکسان دارند و شناسهٔ متفاوت. داده با SEED ساخته میشود، پس روی ماشینِ تو هم همین سطرهاست.
line = "00012\tگزارش\tروزانه"
try:
doc_id, text = line.split("\t")
except ValueError as err:
print(f"{type(err).__name__}: {err}")
doc_id, text = line.split("\t", 1)
print("شناسه:", doc_id, "· تعدادِ نویسهٔ متن:", len(text))
ValueError: too many values to unpack (expected 2)
شناسه: 00012 · تعدادِ نویسهٔ متن: 12
🔧 اگر کار نکرد: پیام دقیق است: سه تکه درآمده و تو دو نام گذاشتهای. راهِ حل
split("\t", 1)است — «فقط یک بار جدا کن، بقیهاش هر چه بود مالِ متن» — و سطرِ دوم نشان میدهد جواب داد. اگر بهجایش سطرهای «خراب» را کنار بگذاری، بیصدا بخشی از پیکره را انداختهای دور.
۲. سه روش، یک جواب#
def text_of(doc):
return doc.split("\t", 1)[1]
def unique_pairwise(docs):
"""روشِ ۱ — هر سند با هر سندِ یکتاییِ قبلی، با حلقهٔ خودمان."""
seen = []
for doc in docs:
text = text_of(doc)
is_new = True
for other in seen:
if other == text:
is_new = False
break
if is_new:
seen.append(text)
return len(seen)
def unique_list_in(docs):
"""روشِ ۲ — همان الگوریتم، ولی حلقهٔ داخلی را پایتون خودش میزند."""
seen = []
for doc in docs:
text = text_of(doc)
if text not in seen:
seen.append(text)
return len(seen)
def unique_set(docs):
"""روشِ ۳ — یک set."""
seen = set()
for doc in docs:
seen.add(text_of(doc))
return len(seen)
check = make_corpus(2_000)
answers = {unique_pairwise(check), unique_list_in(check), unique_set(check)}
print("هر سه روش یک جواب میدهند؟", len(answers) == 1)
print("متنِ یکتا از ۲٬۰۰۰ سند:", unique_set(check))
هر سه روش یک جواب میدهند؟ True
متنِ یکتا از ۲٬۰۰۰ سند: 1500
این سطر اول میآید، نه آخر. سه روشی که جوابِ متفاوت بدهند، سه مسئلهٔ متفاوتاند.
و به روشِ ۱ و ۲ دقت کن: الگوریتمشان دقیقاً یکی است — هر دو فهرستِ دیدهشدهها را از ابتدا میگردند؛ فقط در روشِ ۲ آن حلقه داخلِ not in است. مرتبهشان باید یکی باشد و ثابتشان نه — همان ثابتِ پنهانِ ترمِ ۱ فصلِ ۹.
🤔 اول حدس بزن: برای هر سه روش ستونِ نسبت را بنویس. بعد این را هم حدس بزن: روشِ ۲ چند برابرِ روشِ ۱ سریع است؟
۳. سه جدول، هر کدام در بازهٔ خودش#
بازهٔ هر جدول را عمداً متفاوت گرفتهایم: بازهای که برای روشِ ۱ قابلِ تحمل است، برای روشِ ۳ زیرِ حدِ تفکیکِ ساعت میافتد و ستونِ نسبتش فقط نویز میشود.
SMALL = [500, 1_000, 2_000, 4_000]
small = {n: make_corpus(n) for n in SMALL}
print("— روشِ ۱: مقایسهٔ دستی")
table([(n, 1000 * clock(lambda d=small[n]: unique_pairwise(d), repeat=4))
for n in SMALL], "زمان (ms)", ",.1f")
— روشِ ۱: مقایسهٔ دستی
n زمان (ms) نسبت به سطر قبل
500 1.3 —
1,000 5.1 3.92
2,000 20.6 4.07
4,000 82.2 3.99
MEDIUM = [2_000, 4_000, 8_000, 16_000]
medium = {n: make_corpus(n) for n in MEDIUM}
print("— روشِ ۲: not in روی list")
table([(n, 1000 * clock(lambda d=medium[n]: unique_list_in(d), repeat=3))
for n in MEDIUM], "زمان (ms)", ",.1f")
— روشِ ۲: not in روی list
n زمان (ms) نسبت به سطر قبل
2,000 12.2 —
4,000 50.2 4.12
8,000 197.1 3.93
16,000 877.5 4.45
LARGE = [32_000, 64_000, 128_000, 256_000]
large = {n: make_corpus(n) for n in LARGE}
print("— روشِ ۳: set")
table([(n, 1000 * clock(lambda d=large[n]: unique_set(d), repeat=3))
for n in LARGE], "زمان (ms)", ",.1f")
— روشِ ۳: set
n زمان (ms) نسبت به سطر قبل
32,000 7.7 —
64,000 17.6 2.27
128,000 39.3 2.24
256,000 75.8 1.93
دو جدولِ اول حولِ 4 و جدولِ سوم حولِ 2: O(n²) در برابرِ O(n)، با جوابِ کاملاً یکسان. جدولِ سوم کمی بالای 2 است چون set بزرگ از حافظهٔ نزدیکِ پردازنده بیرون میزند (ترمِ ۲ فصلِ ۱). این Big-O نیست؛ اگر بود، نسبت با هر سطر بزرگتر میشد.
حالا هر دو مقایسه را در یک اندازهٔ ثابت میگیریم، چون سه جدولِ بالا در سه بازهاند و از رویشان نمیشود مستقیم نسبت گرفت.
same = small[2_000]
one = clock(lambda: unique_pairwise(same), repeat=2)
two = clock(lambda: unique_list_in(same), repeat=2)
print(f"n = 2,000 · روشِ ۱: {1000 * one:>7,.1f} ms · روشِ ۲: {1000 * two:>7,.1f} ms"
f" · نسبت: {one / two:>6,.1f}")
same = medium[16_000]
two = clock(lambda: unique_list_in(same), repeat=2)
three = clock(lambda: unique_set(same), repeat=3)
print(f"n = 16,000 · روشِ ۲: {1000 * two:>7,.1f} ms · روشِ ۳: {1000 * three:>7,.1f} ms"
f" · نسبت: {two / three:>6,.0f}")
n = 2,000 · روشِ ۱: 22.5 ms · روشِ ۲: 13.3 ms · نسبت: 1.7
n = 16,000 · روشِ ۲: 812.8 ms · روشِ ۳: 3.5 ms · نسبت: 233
سطرِ اول حدسِ خیلیها را رد میکند: بردنِ حلقه به داخلِ not in فقط حدودِ دو برابر سریعتر شد، نه ده برابر — چون کارِ داخلِ حلقه یک مقایسهٔ رشته است که در هر دو نسخه یکسان انجام میشود و تنها چیزی که حذف میشود سربارِ گردشِ حلقه است. ثابت عوض شد، مرتبه نه.
سطرِ دوم عوض کردنِ مرتبه است: بیش از دویست برابر، در nی که برای یک پیکرهٔ واقعی اصلاً بزرگ نیست. و این نسبت خودش با n بزرگ میشود — کاری که سطرِ اول هرگز نمیکند.
۴. هزینهای که در جدولِ زمان دیده نمیشود#
روشِ سوم رایگان نیست: یک set میسازد که تا آخرِ کار زنده میماند. پس گزارش باید حافظه را هم بگوید.
texts = [text_of(d) for d in medium[16_000]]
as_list = []
as_set = set()
for t in texts:
if t not in as_set:
as_set.add(t)
as_list.append(t)
print("تعدادِ متنِ یکتا:", len(as_list))
print("sys.getsizeof(list):", f"{sys.getsizeof(as_list):>10,} بایت")
print("sys.getsizeof(set) :", f"{sys.getsizeof(as_set):>10,} بایت")
تعدادِ متنِ یکتا: 12000
sys.getsizeof(list): 107,896 بایت
sys.getsizeof(set) : 524,504 بایت
برای همان دوازده هزار متن، set نزدیک به پنج برابرِ list جا میگیرد.
دلیلش همان چیزی است که فصلِ ۳ ساخت: set عمداً خالی نگه داشته میشود. load factor پایین یعنی برخوردِ کمتر، و برخوردِ کمتر یعنی lookup ارزان. این معامله است: حافظهٔ بیشتر، در برابرِ زمانِ کمتر. (هر دو عدد فقط ظرف را میشمارند، نه خودِ رشتهها را؛ sys.getsizeof را ترمِ ۲ فصلِ ۲ باز کرده بود.)
۵. بهینهسازیای که جوابِ مسئله را عوض کرد#
حالا وسوسهای که در هر پروژهٔ واقعی سراغت میآید: مقایسهٔ متنِ کامل گران است؛ چرا از یک «امضای» کوتاه استفاده نکنیم؟
def cheap_signature(text):
"""امضای ارزان: طولِ متن و ده نویسهٔ اول."""
return (len(text), text[:10])
by_signature = set()
for t in texts:
by_signature.add(cheap_signature(t))
print("متنِ یکتا با متنِ کامل :", len(as_set))
print("متنِ یکتا با امضای ارزان:", len(by_signature))
groups = {}
for t in texts:
groups.setdefault(cheap_signature(t), []).append(t)
for signature, members in groups.items():
distinct = set(members)
if len(distinct) > 1:
pair = sorted(distinct)[:2]
print("\nیک امضا، دو متنِ متفاوت:")
print(" ", pair[0])
print(" ", pair[1])
break
متنِ یکتا با متنِ کامل : 12000
متنِ یکتا با امضای ارزان: 3213
یک امضا، دو متنِ متفاوت:
kappa delta beta epsilon eta gamma theta iota
kappa delta beta epsilon eta kappa mu epsilon
۱۲٬۰۰۰ در برابرِ ۳٬۲۱۳ — این کد سهچهارمِ متنهای یکتا را «تکراری» اعلام کرد و دور ریخت. بدونِ هیچ خطایی، و سریعتر از همه. تنها راهِ فهمیدنش مقایسهٔ جوابش با روشِ درست بود.
دو متنِ چاپشده را ببین: طول و ده نویسهٔ اولشان یکی است. امضا برای دو چیزِ نابرابر hash یکسان میدهد — که خودش اشکالی ندارد و اسمش برخورد است. اشکال این است که این کد بعد از یافتنِ امضای یکسان هیچوقت خودِ متنها را با == مقایسه نمیکند. set و dict همیشه میکنند؛ امضای دستساز نه.
⚠️ مواظب باش: امضای کوتاه فینفسه غلط نیست — ابزارهای واقعی دقیقاً همین کار را میکنند. غلط این است که امضا را جایگزینِ مقایسه بگیری، نه غربالِ اولِ آن: با امضا گروهبندی کن، بعد داخلِ هر گروه متنهای کامل را با
==بسنج.
✅ چک کن:
cheap_signatureرا غربالِ اول کن، نه جواب: با آن گروهبندی کن و داخلِ هر گروه یکsetاز متنِ کامل بساز. مجموعِ اندازهٔ آنsetها باید دقیقاً12000شود. اگر نشد، جایی هنوز امضا را بهجای متن درsetمیریزی.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ سه روشِ شمردنِ متنِ یکتا با جوابِ تأییدشدهٔ برابر، بهعلاوهٔ یک روشِ چهارم که جوابش برابر نبود. در کدام بازهٔ
n؟ ۵۰۰ تا ۴٬۰۰۰ برای روشِ ۱، ۲٬۰۰۰ تا ۱۶٬۰۰۰ برای روشِ ۲، ۳۲٬۰۰۰ تا ۲۵۶٬۰۰۰ برای روشِ ۳ — هر کدام در بازهای که حدودِ یک ثانیه تمام شود — بهعلاوهٔ دو مقایسه درnثابت. با چند تکرار، و کمینه یا میانگین؟ دو تا چهار تکرار بهعلاوهٔ گرمکننده، کمینه، و همان پیکرهٔ ثابت برای همه.
۶. گزارشِ نهایی#
این شش بند تصمیمِ مستندِ این پروژهاند:
- الگوی دسترسی:
nپرسشِ عضویت روی ظرفی که همزمان ساخته میشود؛ هیچ خواندنِ تصادفی، هیچ حذفی. - بازهٔ
n: ۵۰۰ تا ۲۵۶٬۰۰۰ سند، با یکچهارمِ متنها تکراری. - مرتبهٔ اعلامشده: روشِ ۱ و ۲ هر دو
O(n²)، روشِ ۳O(n)— هر سه از ستونِ نسبت. - درستی: جوابِ هر سه برابر تأیید شد؛ امضای ارزان رد شد، چون جوابش برابر نبود.
- هزینهٔ پذیرفتهشده: حافظهٔ
set، نزدیک به پنج برابرِ یکlistاز همان اعضا. - تصمیم: روشِ ۳، مشروط به اینکه پیکره در حافظه جا شود. اگر بزرگتر شد، این تصمیم باطل است.
بندِ ششم اختیاری نیست. تصمیمی که شرطش را ننوشته باشد، تصمیم نیست؛ عادت است.
🤖 از دستیارت بپرس: خروجیِ بخشِ ۵ را جلویش بگذار: «این امضا چرا سهچهارمِ متنها را از دست داد؟» بعد بپرس: «چطور امضایی بسازم که هیچوقت دو متنِ متفاوت را یکی نبیند؟» — جوابِ درست باید بگوید چنین چیزی ممکن نیست، به همان دلیلِ فصلِ ۲: خانهها محدودند و متنها نه.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| deduplication | ددوپلیکیشن | پیدا کردن و کنار گذاشتنِ تکراریها |
| signature | سیگنیچر | خلاصهٔ کوتاهی از یک داده، برای غربالِ سریع |
| false duplicate | فالس دوپلیکیت | دو چیزِ متفاوت که اشتباهاً تکراری اعلام میشوند |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
ترمِ سه تمام شد: یک hash table از صفر، سه پرسشِ بدترین و متوسط و واقعی، و هزینهای برای پرسشِ عضویت که خودت اندازه گرفتهای.
ولی همهٔ این ترم دربارهٔ پرسشِ «هست یا نه؟» بود. «کوچکترین عضو کدام است؟»، «عضوهای بینِ این دو عدد کداماند؟» — set برای اینها باید کلِ خودش را بگردد، چون ترتیب دقیقاً همان چیزی است که hash عمداً از بین میبرد.
ترمِ چهار همانجا شروع میشود: recursion، مرتبسازی، و binary search. merge sort و quicksort را خودت مینویسی، مرتبهشان را تأیید میکنی، و میبینی چرا در کارِ واقعی هیچکدام را نمینویسی.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.