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

فصل ۶ از ۶

پیشرفت ترم
۰٪

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

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

دو نامزد می‌سازیم که جوابِ کاملاً یکسان می‌دهند. نامزدِ اول هر پرسش را در حدودِ یک‌دهم میکروثانیه جواب می‌دهد و حافظه‌اش با n اصلاً بزرگ نمی‌شود؛ نامزدِ دوم صدها برابر کندتر است و حافظه‌اش خطی رشد می‌کند.

و نامزدِ اول انتخابِ غلط است. نه چون کند است و نه چون گران است — چون برای پرسشی که کاربرِ واقعی می‌پرسد، بی‌صدا فهرستِ خالی برمی‌گرداند.

دو ماشینِ پیشنهاددهنده کنارِ هم، یکی با کشوهای از پیش پرشده و یکی با یک ریلِ مرتب

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

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

قبل از شروع#

از فصلِ ۱: برگهٔ شکلِ مسئله. از فصلِ ۳: معاملهٔ حافظه و زمان. از فصلِ ۵: نُه بندِ گزارش. از ترمِ ۴ فصلِ ۷: bisect روی فهرستِ مرتب.

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

📓 نوت‌بوک: نوت‌بوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

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

سیاههٔ جست‌وجوی یک سایت را داریم: هر عبارت با تعدادِ دفعاتی که جست‌وجو شده. کاربر شروع به تایپ می‌کند و ما باید پنج عبارتِ پرتکرارِ شروع‌شونده با آنچه تا حالا تایپ کرده را نشان بدهیم.

برگهٔ شکلِ مسئله، قبل از هر کدی:

  1. الگوی دسترسی: ساختار یک بار شبانه ساخته می‌شود و بعد میلیون‌ها بار پرسیده می‌شود؛ هیچ درجِ زنده‌ای نداریم.
  2. نسبتِ خواندن به نوشتن: به‌شدت خواندن‌محور — پس طبقِ فصلِ ۱، پیش‌محاسبه صرف می‌کند.
  3. بازهٔ واقعیِ n: ده هزار تا هشتاد هزار عبارتِ یکتا.

و یک قیدِ چهارم که هیچ‌کدام از این سه نمی‌گویدش: کاربر از حرفِ اول تایپ می‌کند و نمی‌ایستد — پس طولِ پیشوند هر عددی می‌تواند باشد.

from bisect import bisect_left

LETTERS = "abcdefghij"
PREFIX = 3
TOP = 5
LADDER = [10_000, 20_000, 40_000, 80_000]


def make_queries(n, seed=SEED):
    """n عبارتِ یکتا، هرکدام با تعدادِ دفعاتِ جست‌وجو."""
    rng = random.Random(seed)
    seen, out = set(), []
    while len(out) < n:
        phrase = "".join(rng.choice(LETTERS) for _ in range(rng.randint(5, 9)))
        if phrase not in seen:
            seen.add(phrase)
            out.append((phrase, rng.randrange(1, 10_000)))
    return out


data = {n: make_queries(n) for n in LADDER}
print("سه عبارتِ اول:", data[10_000][:3])
سه عبارتِ اول: [('babjabbf', 3880), ('aafjh', 7595), ('bcbaih', 4094)]

۲. دو نامزد، یک جواب#

نامزدِ الف برای هر پیشوندِ سه‌حرفیِ ممکن پنج عبارتِ برترش را از پیش حساب می‌کند و در یک dict می‌گذارد. نامزدِ ب فقط یک فهرستِ مرتب نگه می‌دارد و در هر پرسش با bisect جای شروعِ پیشوند را پیدا می‌کند و همان بازه را می‌خواند.

def build_table(pairs):
    """نامزد الف — پنج برترِ هر پیشوندِ سه‌حرفی، از پیش."""
    groups = {}
    for phrase, hits in pairs:
        groups.setdefault(phrase[:PREFIX], []).append((phrase, hits))
    return {p: sorted(v, key=lambda ph: (-ph[1], ph[0]))[:TOP]
            for p, v in groups.items()}


def build_sorted(pairs):
    """نامزد ب — یک فهرستِ مرتب، به‌علاوهٔ ستونِ عبارت‌ها برای bisect."""
    ordered = sorted(pairs)
    return ordered, [phrase for phrase, _ in ordered]


def top_by_table(ready, prefix):
    return ready.get(prefix, [])


def top_by_scan(ordered, phrases, prefix):
    i = bisect_left(phrases, prefix)
    box = []
    while i < len(phrases) and phrases[i].startswith(prefix):
        box.append(ordered[i])
        i += 1
    return sorted(box, key=lambda ph: (-ph[1], ph[0]))[:TOP]


ready = {n: build_table(data[n]) for n in LADDER}
lists = {n: build_sorted(data[n]) for n in LADDER}
picker = random.Random(SEED)
asks = {n: [phrase[:PREFIX] for phrase, _ in picker.sample(data[n], 200)]
        for n in LADDER}
print("جوابِ دو نامزد در هر چهار اندازه یکی است؟",
      all(top_by_table(ready[n], p) == top_by_scan(lists[n][0], lists[n][1], p)
          for n in LADDER for p in asks[n]))
print("نمونه برای پیشوندِ", asks[20_000][0], ":",
      top_by_scan(lists[20_000][0], lists[20_000][1], asks[20_000][0])[:2])
جوابِ دو نامزد در هر چهار اندازه یکی است؟ True
نمونه برای پیشوندِ fdf : [('fdfjahdbh', 8753), ('fdfebajf', 7676)]

برابریِ جواب اول می‌آید، نه آخر — و روی هر چهار اندازه، نه فقط یکی.

۳. جدولِ پرسش#

🤔 اول حدس بزن: ستونِ نسبتِ هر دو نامزد را بنویس. برای نامزدِ ب دقت کن: بازه‌ای که bisect پیدا می‌کند، با n بزرگ‌تر می‌شود یا نه؟

for name, fn in (("الف — جدولِ آماده",
                  lambda k: [top_by_table(ready[k], p) for p in asks[k]]),
                 ("ب — مرتب + bisect",
                  lambda k: [top_by_scan(lists[k][0], lists[k][1], p) for p in asks[k]])):
    print(f"— نامزد {name} · µs به‌ازای هر پرسش")
    table([(n, 1e6 * clock(lambda k=n, f=fn: f(k), repeat=3) / 200) for n in LADDER],
          "µs", ",.3f")
    print()
— نامزد الف — جدولِ آماده · µs به‌ازای هر پرسش
         n                µs     نسبت به سطر قبل
    10,000             0.093                   —
    20,000             0.097                1.04
    40,000             0.095                0.99
    80,000             0.095                1.00

— نامزد ب — مرتب + bisect · µs به‌ازای هر پرسش
         n                µs     نسبت به سطر قبل
    10,000             3.418                   —
    20,000             5.894                1.72
    40,000            11.890                2.02
    80,000            27.470                2.31

1.0 در برابرِ 2: O(1) در برابرِ O(n). و در n = 80,000 نامزدِ الف حدودِ سیصد برابر جلوتر است. برای فهمیدنِ اینکه چرا نامزدِ ب رشد می‌کند، گام‌هایش را می‌شماریم:

def scan_steps(phrases, prefix):
    """گامِ bisect، و اندازهٔ بازه‌ای که بعدش پیموده می‌شود."""
    lo, hi, steps = 0, len(phrases) - 1, 0
    while lo < hi:
        steps += 1
        mid = (lo + hi) // 2
        if phrases[mid] < prefix:
            lo = mid + 1
        else:
            hi = mid
    i, width = bisect_left(phrases, prefix), 0
    while i < len(phrases) and phrases[i].startswith(prefix):
        width += 1
        i += 1
    return steps, width


print(f"{'n':>10}{'گامِ bisect':>14}{'اندازهٔ بازه':>16}{'مجموع':>10}")
for n in LADDER:
    pairs = [scan_steps(lists[n][1], p) for p in asks[n]]
    jumps = sum(s for s, _ in pairs) / 200
    width = sum(w for _, w in pairs) / 200
    print(f"{n:>10,}{jumps:>14.2f}{width:>16.1f}{jumps + width:>10.1f}")
         n   گامِ bisect    اندازهٔ بازه     مجموع
    10,000         13.41            11.0      24.4
    20,000         14.30            20.9      35.2
    40,000         15.39            41.2      56.6
    80,000         16.37            79.8      96.2

دو ستونِ کاملاً متفاوت. ستونِ bisect با هر دو برابر شدنِ n یک گام اضافه می‌کند — O(log n) — و ستونِ بازه دو برابر می‌شود، چون تعدادِ پیشوندهای ممکن ثابت است و عبارت‌های بیشتر در همان هزار گروه جا می‌گیرند. رشدِ نامزدِ ب از جست‌وجو نمی‌آید، از خواندنِ بازه می‌آید.

۴. حافظه، و انتظاری که برعکس درمی‌آید#

فصلِ ۳ گفت پیش‌محاسبه با حافظه پرداخته می‌شود. اینجا برعکس است:

print(f"{'n':>10}{'الف (بایت)':>14}{'ب (بایت)':>14}{'نسبتِ ب':>10}{'الف/ب':>10}")
last = None
for n in LADDER:
    box = ready[n]
    small = sys.getsizeof(box) + sum(sys.getsizeof(v) for v in box.values())
    big = sys.getsizeof(lists[n][0]) + sys.getsizeof(lists[n][1])
    step = "—" if last is None else f"{big / last:.2f}"
    print(f"{n:>10,}{small:>14,}{big:>14,}{step:>10}{small / big:>10.2f}")
    last = big
print("\nکلیدهای جدولِ الف:", len(ready[80_000]), "· پیشوندِ ممکن:",
      len(LETTERS) ** PREFIX)
         n    الف (بایت)      ب (بایت)   نسبتِ ب     الف/ب
    10,000       121,800       165,232         —      0.74
    20,000       122,032       333,072      2.02      0.37
    40,000       122,032       671,120      2.01      0.18
    80,000       122,032     1,352,016      2.01      0.09

کلیدهای جدولِ الف: 1000 · پیشوندِ ممکن: 1000

حافظهٔ نامزدِ الف با n بزرگ نمی‌شود. جدولش هزار کلید دارد و هر کلید فقط پنج عبارت — پس اندازه‌اش به تعدادِ پیشوندها بند است، نه به تعدادِ عبارت‌ها. ستونِ «نسبتِ ب» هم 2.01 است: حافظهٔ نامزدِ ب O(n) است و در n = 80,000 بیش از یازده برابرِ الف جا می‌گیرد.

پس نامزدِ الف هم سریع‌تر است و هم کم‌حافظه‌تر. ظاهراً تصمیم تمام است.

ولی این «کم‌حافظه‌تر» یک دلیلِ ساده دارد که همان دلیل، عیبش هم هست: نامزدِ الف بقیهٔ داده را دور می‌ریزد. او فقط پنج عبارتِ برترِ هر پیشوندِ سه‌حرفی را نگه داشته و هر چیزِ دیگری را فراموش کرده.

۵. پرسشی که نامزدِ الف بی‌صدا غلط جواب می‌دهد#

قیدِ چهارمِ بخشِ ۱: کاربر از حرفِ اول تایپ می‌کند.

ordered, phrases = lists[80_000]
print(f"{'پیشوند':>10}{'الف':>8}{'ب':>8}   نمونه از جوابِ ب")
for prefix in ("ab", "abc", "abcd"):
    a = top_by_table(ready[80_000], prefix)
    b = top_by_scan(ordered, phrases, prefix)
    print(f"{prefix:>10}{len(a):>8}{len(b):>8}   {b[:1]}")
    پیشوند     الف       ب   نمونه از جوابِ ب
        ab       0       5   [('abade', 9997)]
       abc       5       5   [('abccahhb', 9919)]
      abcd       0       5   [('abcdicaa', 8262)]

در طولِ سه، هر دو درست‌اند. در طولِ دو و چهار، نامزدِ الف فهرستِ خالی می‌دهد و هیچ خطایی هم نمی‌دهد.

کاربری که «abcd» تایپ کرده پنج پیشنهاد داشت و هیچ‌کدام را نمی‌بیند. از دیدِ برنامه هیچ اتفاقی نیفتاده: نه استثنایی، نه سطری در سیاهه. این همان دستهٔ عیبی است که ترمِ ۳ فصلِ ۷ و فصلِ ۴ همین ترم هم نشانش دادند، و تنها راهِ پیدا شدنش مقایسه با یک نسخهٔ درست بود.

و دقت کن که نامزدِ الف در جدولِ زمان و در جدولِ حافظه هر دو بُرد. هیچ‌کدام از آن دو جدول نمی‌توانستند این را نشان بدهند.

🔧 اگر کار نکرد: رایج‌ترین اشتباه در نوشتنِ نامزدِ ب این است که bisect را روی فهرستِ جفت‌ها بزنی، نه روی ستونِ عبارت‌ها:

try:
    bisect_left(ordered, "abc")
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
print("درستش:", bisect_left(phrases, "abc"))
TypeError: '<' not supported between instances of 'tuple' and 'str'
درستش: 953

پیام دقیق است: یک tuple با یک رشته مقایسه نمی‌شود. به همین دلیل build_sorted دو چیز برمی‌گرداند — خودِ جفت‌ها و ستونِ جداگانهٔ عبارت‌ها — و bisect فقط با دومی کار دارد.

✅ چک کن: PREFIX را به 4 تغییر بده و کلِ نوت‌بوک را از بالا اجرا کن. حالا سطرِ abcd جدولِ بخشِ ۵ باید برای نامزدِ الف هم جواب بدهد و سطرِ abc خالی شود — عیب جابه‌جا می‌شود، نه رفع. اگر هر دو سطر جواب دادند، PREFIX را جایی به‌صورتِ عددِ ثابت نوشته‌ای.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ دو نامزد روی یک سیاههٔ واحد و همان دویست پیشوندِ ثابت، با جوابِ برابرِ تأییدشده در هر چهار اندازه. در کدام بازهٔ n؟ ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ عبارتِ یکتا، الفبای ده‌حرفی، پیشوندِ سه‌حرفی. با چند تکرار، و کمینه یا میانگین؟ جدولِ گام و جدولِ حافظه یک اجرا و قطعی؛ جدولِ زمان سه تکرار به‌علاوهٔ گرم‌کننده، کمینه.

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

نُه بندِ فصلِ ۵، برای این پروژه:

  1. شکلِ مسئله: یک بار ساخت، میلیون‌ها پرسش، بدونِ درجِ زنده — به‌علاوهٔ قیدِ چهارم: طولِ پیشوند ثابت نیست.
  2. نامزدها: الف جدولِ از پیش ساخته برای پیشوندِ سه‌حرفی؛ ب فهرستِ مرتب با bisect.
  3. ورودی و بذر: make_queries با بذرِ ثابتِ همین دوره، عبارت‌های یکتا از الفبای ده‌حرفی.
  4. بازهٔ n: ۱۰٬۰۰۰ تا ۸۰٬۰۰۰.
  5. پروتکل: سه تکرار به‌علاوهٔ گرم‌کننده، کمینه؛ گام و حافظه قطعی.
  6. برابریِ جواب: فقط برای پیشوندِ سه‌حرفی تأیید شد. برای طول‌های دیگر برابر نیست.
  7. نتیجه: الف در زمان حدودِ سیصد برابر جلو، در حافظه بیش از یازده برابر کم‌خرج‌تر — و در پوششِ پرسش بازنده.
  8. تصمیم و شرطِ باطل شدنش: نامزدِ ب. الف فقط اگر پذیرفته شود که پیشوند همیشه دقیقاً سه حرف است، یا اگر برای هر طولِ ممکن جدولِ جداگانه ساخته شود — که چون جدولِ الف یک‌بُعدی است، حافظه‌اش با هر حرفِ اضافه ده برابر می‌شود، همان Kی که فصلِ ۳ نشان داد ده برابر می‌شود (آن‌جا جدول دوبُعدی بود و حافظه صد برابر می‌شد).
  9. حافظه، به بایت: در n = 80,000 الف 122,032 بایت و ب 1,352,016 بایت. چه چیزی شمرده شده: خودِ ظرف به‌علاوهٔ ظرف‌های داخلش. چه چیزی نشده: خودِ جفت‌ها و رشته‌های عبارت — چون نامزدها همان اشیاء را ارجاع می‌دهند و کپی‌شان نمی‌کنند (همان تفکیکی که فصلِ ۳ بخشِ ۴ گذاشت). با شمردنِ آن‌ها، الف با پنج هزار جفتش حدودِ ۸۲۰ کیلوبایت می‌شد و ب با هشتاد هزارتا حدودِ ۱۲٫۵ مگابایت، و نسبتشان از یازده به پانزده می‌رفت — پس این انتخاب روی نتیجه اثر دارد و باید نوشته شود.

بندِ ششم مهم‌ترین بندِ این گزارش است. «جوابِ دو نامزد یکی است» در بخشِ ۲ یک جملهٔ مشروط بود و شرطش تا بخشِ ۵ دیده نشد. گزارشی که آن شرط را ننویسد، دو صفحه عدد است که یک تصمیمِ غلط را ثابت می‌کند.

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

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

کلمه تلفظ به حروف فارسی یعنی چه
autocomplete اتوکامپلیت پیشنهادِ ادامهٔ عبارت هنگامِ تایپ
coverage کاوریج اینکه یک ساختار چه کسری از پرسش‌های ممکن را اصلاً می‌تواند جواب بدهد

تمرین‌ها

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

در فصل بعد#

دوره تمام شد. شش ترم و چهل و نه فصل، و همه‌شان دورِ یک جمله چرخیدند:

Big-O یک پیش‌بینی است، نه یک برچسب — و پیش‌بینی‌ای که آزمون نداده، حدس است.

ترمِ ۱ یاد داد صادقانه اندازه بگیری و مرتبه را از ستونِ نسبت بخوانی. ترم‌های ۲ تا ۵ ساختار ساختند و هزینهٔ هر عملیاتشان را خودت اندازه گرفتی. و این ترم سه خانه به هر تصمیم اضافه کرد: الگوی دسترسی، نسبتِ خواندن به نوشتن، و بازهٔ واقعیِ n.

چیزی که با خودت می‌بری یک جدولِ حفظ‌شده نیست، یک عادت است: قبل از انتخاب، شکلِ مسئله را بنویس؛ قبل از ادعا، اندازه بگیر؛ و کنارِ هر تصمیم، شرطی بنویس که با آن باطل می‌شود. کدی که این سه را داشته باشد، وقتی داده ده برابر شد هنوز کار می‌کند — و اگر نکرد، خودت از قبل می‌دانی چرا.

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

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