# فصل ۰۷ — پروژه: تکراری‌ها در یک پیکرهٔ بزرگ

<div dir="rtl">

# فصل ۰۷ — پروژه: تکراری‌ها در یک پیکرهٔ بزرگ

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

هیچ مفهومِ تازه‌ای. **این فصل شش فصلِ قبل را روی یک مسئلهٔ واقعی به‌کار می‌برد.**

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

![دو دسته سندِ یکسان که یکی برگ‌به‌برگ با همه مقایسه می‌شود و دیگری با یک مهرِ کوتاه دسته‌بندی می‌شود](/lesson-assets/t3-s07-project-dedup/prompt/01-image-duplicate-piles.png)

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

- سه راهِ حذفِ تکراری را بسنجی و برابریِ جوابشان را ثابت کنی
- هزینهٔ حافظهٔ راهِ سریع را هم گزارش کنی، نه فقط زمانش را
- تشخیص بدهی کِی یک «بهینه‌سازی» جوابِ مسئله را عوض کرده

## قبل از شروع

**از فصلِ ۱:** جست‌وجوی خطی. **از فصلِ ۵:** `set` و نقطهٔ سربه‌سرش. **از فصلِ ۶:** کلیدِ مرکب با `tuple`.

</div>

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

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-3-hashing/session-07-project-dedup.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. صورتِ مسئله

هر سند یک **شناسهٔ یکتا** دارد و یک **متن**. شناسه‌ها هرگز تکرار نمی‌شوند؛ متن‌ها گاهی. سؤال: **چند متنِ یکتا داریم؟**

**الگوی دسترسی، قبل از هر کدی:** سندها یکی‌یکی می‌آیند و هر متن یک بار پرسیده می‌شود. **پس این عضویت است با `n` پرسش — و فصلِ ۵ گفت در این بازه ساختن به‌صرفه است.**

</div>

```python
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))
```

```text
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
```

<div dir="rtl">

**سندِ `00000` و سندِ `00002` متنِ یکسان دارند و شناسهٔ متفاوت.** داده با `SEED` ساخته می‌شود، پس روی ماشینِ تو هم همین سطرهاست.

</div>

```python
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))
```

```text
ValueError: too many values to unpack (expected 2)
شناسه: 00012 · تعدادِ نویسهٔ متن: 12
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** پیام دقیق است: سه تکه درآمده و تو دو نام گذاشته‌ای. **راهِ حل `split("\t", 1)` است** — «فقط یک بار جدا کن، بقیه‌اش هر چه بود مالِ متن» — و سطرِ دوم نشان می‌دهد جواب داد. اگر به‌جایش سطرهای «خراب» را کنار بگذاری، **بی‌صدا بخشی از پیکره را انداخته‌ای دور.**

## ۲. سه روش، یک جواب

</div>

```python
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))
```

```text
هر سه روش یک جواب می‌دهند؟ True
متنِ یکتا از ۲٬۰۰۰ سند: 1500
```

<div dir="rtl">

**این سطر اول می‌آید، نه آخر.** سه روشی که جوابِ متفاوت بدهند، سه مسئلهٔ متفاوت‌اند.

**و به روشِ ۱ و ۲ دقت کن: الگوریتمشان دقیقاً یکی است** — هر دو فهرستِ دیده‌شده‌ها را از ابتدا می‌گردند؛ فقط در روشِ ۲ آن حلقه داخلِ `not in` است. **مرتبه‌شان باید یکی باشد و ثابتشان نه** — همان ثابتِ پنهانِ ترمِ ۱ فصلِ ۹.

> 🤔 **اول حدس بزن:** برای هر سه روش ستونِ نسبت را بنویس. بعد این را هم حدس بزن: **روشِ ۲ چند برابرِ روشِ ۱ سریع است؟**

## ۳. سه جدول، هر کدام در بازهٔ خودش

**بازهٔ هر جدول را عمداً متفاوت گرفته‌ایم**: بازه‌ای که برای روشِ ۱ قابلِ تحمل است، برای روشِ ۳ زیرِ حدِ تفکیکِ ساعت می‌افتد و ستونِ نسبتش فقط نویز می‌شود.

</div>

```python
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")
```

```text-approx
— روشِ ۱: مقایسهٔ دستی
         n         زمان (ms)     نسبت به سطر قبل
       500               1.3                   —
     1,000               5.1                3.92
     2,000              20.6                4.07
     4,000              82.2                3.99
```

```python
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")
```

```text-approx
— روشِ ۲: 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
```

```python
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")
```

```text-approx
— روشِ ۳: 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
```

<div dir="rtl">

**دو جدولِ اول حولِ `4` و جدولِ سوم حولِ `2`:** `O(n²)` در برابرِ `O(n)`، با جوابِ کاملاً یکسان. **جدولِ سوم کمی بالای `2` است** چون `set` بزرگ از حافظهٔ نزدیکِ پردازنده بیرون می‌زند (ترمِ ۲ فصلِ ۱). **این `Big-O` نیست؛ اگر بود، نسبت با هر سطر بزرگ‌تر می‌شد.**

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

</div>

```python
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}")
```

```text-approx
n =  2,000  ·  روشِ ۱:    22.5 ms  ·  روشِ ۲:    13.3 ms  ·  نسبت:    1.7
n = 16,000  ·  روشِ ۲:   812.8 ms  ·  روشِ ۳:     3.5 ms  ·  نسبت:    233
```

<div dir="rtl">

**سطرِ اول حدسِ خیلی‌ها را رد می‌کند:** بردنِ حلقه به داخلِ `not in` فقط حدودِ **دو برابر** سریع‌تر شد، نه ده برابر — چون کارِ داخلِ حلقه یک مقایسهٔ رشته است که در هر دو نسخه یکسان انجام می‌شود و **تنها چیزی که حذف می‌شود سربارِ گردشِ حلقه است.** ثابت عوض شد، مرتبه نه.

**سطرِ دوم عوض کردنِ مرتبه است:** بیش از دویست برابر، در `n`ی که برای یک پیکرهٔ واقعی اصلاً بزرگ نیست. **و این نسبت خودش با `n` بزرگ می‌شود** — کاری که سطرِ اول هرگز نمی‌کند.

## ۴. هزینه‌ای که در جدولِ زمان دیده نمی‌شود

روشِ سوم رایگان نیست: یک `set` می‌سازد که تا آخرِ کار زنده می‌ماند. **پس گزارش باید حافظه را هم بگوید.**

</div>

```python
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,} بایت")
```

```text
تعدادِ متنِ یکتا: 12000
sys.getsizeof(list):    107,896 بایت
sys.getsizeof(set) :    524,504 بایت
```

<div dir="rtl">

**برای همان دوازده هزار متن، `set` نزدیک به پنج برابرِ `list` جا می‌گیرد.**

دلیلش همان چیزی است که فصلِ ۳ ساخت: **`set` عمداً خالی نگه داشته می‌شود.** `load factor` پایین یعنی برخوردِ کمتر، و برخوردِ کمتر یعنی `lookup` ارزان. **این معامله است: حافظهٔ بیشتر، در برابرِ زمانِ کمتر.** (هر دو عدد فقط ظرف را می‌شمارند، نه خودِ رشته‌ها را؛ `sys.getsizeof` را ترمِ ۲ فصلِ ۲ باز کرده بود.)

## ۵. بهینه‌سازی‌ای که جوابِ مسئله را عوض کرد

حالا وسوسه‌ای که در هر پروژهٔ واقعی سراغت می‌آید: **مقایسهٔ متنِ کامل گران است؛ چرا از یک «امضای» کوتاه استفاده نکنیم؟**

</div>

```python
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
```

```text
متنِ یکتا با متنِ کامل  : 12000
متنِ یکتا با امضای ارزان: 3213

یک امضا، دو متنِ متفاوت:
  kappa delta beta epsilon eta gamma theta iota
  kappa delta beta epsilon eta kappa mu epsilon
```

<div dir="rtl">

**۱۲٬۰۰۰ در برابرِ ۳٬۲۱۳ — این کد سه‌چهارمِ متن‌های یکتا را «تکراری» اعلام کرد و دور ریخت.** بدونِ هیچ خطایی، و سریع‌تر از همه. **تنها راهِ فهمیدنش مقایسهٔ جوابش با روشِ درست بود.**

**دو متنِ چاپ‌شده را ببین:** طول و ده نویسهٔ اولشان یکی است. امضا برای دو چیزِ نابرابر `hash` یکسان می‌دهد — که **خودش اشکالی ندارد و اسمش برخورد است**. اشکال این است که این کد بعد از یافتنِ امضای یکسان **هیچ‌وقت خودِ متن‌ها را با `==` مقایسه نمی‌کند.** `set` و `dict` همیشه می‌کنند؛ **امضای دست‌ساز نه.**

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

> ✅ **چک کن:** `cheap_signature` را غربالِ اول کن، نه جواب: با آن گروه‌بندی کن و داخلِ هر گروه یک `set` از متنِ کامل بساز. **مجموعِ اندازهٔ آن `set`ها باید دقیقاً `12000` شود.** اگر نشد، جایی هنوز امضا را به‌جای متن در `set` می‌ریزی.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** سه روشِ شمردنِ متنِ یکتا با جوابِ تأییدشدهٔ برابر، به‌علاوهٔ یک روشِ چهارم که جوابش برابر **نبود**. **در کدام بازهٔ `n`؟** ۵۰۰ تا ۴٬۰۰۰ برای روشِ ۱، ۲٬۰۰۰ تا ۱۶٬۰۰۰ برای روشِ ۲، ۳۲٬۰۰۰ تا ۲۵۶٬۰۰۰ برای روشِ ۳ — هر کدام در بازه‌ای که حدودِ یک ثانیه تمام شود — به‌علاوهٔ دو مقایسه در `n` ثابت. **با چند تکرار، و کمینه یا میانگین؟** دو تا چهار تکرار به‌علاوهٔ گرم‌کننده، کمینه، و همان پیکرهٔ ثابت برای همه.

## ۶. گزارشِ نهایی

**این شش بند تصمیمِ مستندِ این پروژه‌اند:**

1. **الگوی دسترسی:** `n` پرسشِ عضویت روی ظرفی که هم‌زمان ساخته می‌شود؛ هیچ خواندنِ تصادفی، هیچ حذفی.
2. **بازهٔ `n`:** ۵۰۰ تا ۲۵۶٬۰۰۰ سند، با یک‌چهارمِ متن‌ها تکراری.
3. **مرتبهٔ اعلام‌شده:** روشِ ۱ و ۲ هر دو `O(n²)`، روشِ ۳ `O(n)` — هر سه از ستونِ نسبت.
4. **درستی:** جوابِ هر سه برابر تأیید شد؛ امضای ارزان **رد شد**، چون جوابش برابر نبود.
5. **هزینهٔ پذیرفته‌شده:** حافظهٔ `set`، نزدیک به پنج برابرِ یک `list` از همان اعضا.
6. **تصمیم:** روشِ ۳، **مشروط به اینکه پیکره در حافظه جا شود.** اگر بزرگ‌تر شد، این تصمیم باطل است.

**بندِ ششم اختیاری نیست.** تصمیمی که شرطش را ننوشته باشد، تصمیم نیست؛ عادت است.

> 🤖 **از دستیارت بپرس:** **خروجیِ بخشِ ۵ را جلویش بگذار:** «این امضا چرا سه‌چهارمِ متن‌ها را از دست داد؟» بعد بپرس: **«چطور امضایی بسازم که هیچ‌وقت دو متنِ متفاوت را یکی نبیند؟»** — جوابِ درست باید بگوید چنین چیزی ممکن نیست، به همان دلیلِ فصلِ ۲: خانه‌ها محدودند و متن‌ها نه.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| deduplication | ددوپلیکیشن | پیدا کردن و کنار گذاشتنِ تکراری‌ها |
| signature | سیگنیچر | خلاصهٔ کوتاهی از یک داده، برای غربالِ سریع |
| false duplicate | فالس دوپلیکیت | دو چیزِ متفاوت که اشتباهاً تکراری اعلام می‌شوند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا سطرِ مقایسهٔ برابری باید اولِ هر آزمایش بیاید و نه آخرش؟

**تمرینِ اجباری:** به‌جای **شمردنِ** یکتاها، **شناسهٔ** سندهای تکراری را برگردان. با `defaultdict` بنویسش و جدولِ چهار اندازه‌ای‌اش را بگیر. **سؤالِ اصلی: مرتبه‌اش با روشِ ۳ یکی است یا نه، و حافظه‌اش چطور؟** جوابت باید بگوید چه چیزِ تازه‌ای را مجبور شده‌ای نگه داری.

**تمرینِ ستاره‌دار ⭐:** پیکره را طوری بساز که **همهٔ متن‌ها طولِ یکسان و ده نویسهٔ اولِ یکسان داشته باشند**. **قبل از اجرا پیش‌بینی کن** امضای ارزان چه عددی می‌دهد و روشِ ۳ چه عددی، بعد اجرا کن و خطای پیش‌بینی‌ات را بنویس. **و در آخر: آیا این پیکره «غیرواقعی» است؟** جوابت باید به فصلِ ۴ برگردد و بگوید چه کسی می‌تواند ورودی را انتخاب کند.

## در فصل بعد

ترمِ سه تمام شد: یک `hash table` از صفر، سه پرسشِ بدترین و متوسط و واقعی، و هزینه‌ای برای پرسشِ عضویت که **خودت** اندازه گرفته‌ای.

**ولی همهٔ این ترم دربارهٔ پرسشِ «هست یا نه؟» بود.** «کوچک‌ترین عضو کدام است؟»، «عضوهای بینِ این دو عدد کدام‌اند؟» — `set` برای این‌ها باید کلِ خودش را بگردد، چون **ترتیب دقیقاً همان چیزی است که `hash` عمداً از بین می‌برد.**

**ترمِ چهار همان‌جا شروع می‌شود:** `recursion`، مرتب‌سازی، و `binary search`. `merge sort` و `quicksort` را خودت می‌نویسی، مرتبه‌شان را تأیید می‌کنی، و می‌بینی چرا در کارِ واقعی هیچ‌کدام را نمی‌نویسی.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t3/s07-project-dedup (یادستان, Yaadestan)
