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

فصل ۷ از ۷

پیشرفت ترم
۰٪

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

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

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

دو دسته سندِ یکسان که یکی برگ‌به‌برگ با همه مقایسه می‌شود و دیگری با یک مهرِ کوتاه دسته‌بندی می‌شود

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

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

قبل از شروع#

از فصلِ ۱: جست‌وجوی خطی. از فصلِ ۵: 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 ثابت. با چند تکرار، و کمینه یا میانگین؟ دو تا چهار تکرار به‌علاوهٔ گرم‌کننده، کمینه، و همان پیکرهٔ ثابت برای همه.

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

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

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

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

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

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

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

تمرین‌ها

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

در فصل بعد#

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

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

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

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

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