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

فصل ۹ از ۹

پیشرفت ترم
۰٪

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

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

یک انبارِ رکورد داریم و باید در آن دنبالِ کد بگردیم. سه راه می‌سازیم که جوابِ کاملاً یکسان می‌دهند، برای هر سه جدولِ رشد می‌گیریم، و یک تصمیمِ مستند می‌نویسیم. در n = 16,000 میانگینِ گامِ روشِ اول 7,807.5 است و روشِ دوم 13.06.

ولی نتیجهٔ اصلی در آن جدول نیست: پرسشی پیدا می‌کنیم که سریع‌ترین ساختار اصلاً نمی‌تواند جوابش را بدهد و ۱۶٬۰۰۰ گام برمی‌دارد، در حالی که ساختارِ «کندتر» با ۳۲۲ گام تمامش می‌کند.

سه میزِ جست‌وجو کنارِ هم: یکی قفسهٔ بی‌ترتیب، یکی قفسهٔ شماره‌دارِ مرتب، یکی جعبهٔ کلید

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

  • سه ساختارِ جست‌وجو را روی یک مسئله بسنجی و برابریِ جوابشان را ثابت کنی
  • هزینهٔ ساختِ اولیه را از هزینهٔ هر پرسش جدا کنی
  • تشخیص بدهی کِی «سریع‌ترین» ساختار جوابِ مسئلهٔ تو را ندارد
  • یک تصمیمِ مستند بنویسی که شرطِ باطل شدنش هم در آن نوشته باشد

قبل از شروع#

از ترمِ ۳ فصلِ ۵: dict و هزینهٔ ثابتِ جست‌وجویش. از فصلِ ۷: bisect و نقطهٔ سربه‌سر.

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

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

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

هر رکورد یک کدِ یکتا دارد و یک شهر. کدها بی‌ترتیب می‌آیند. دو پرسش داریم:

  1. پرسشِ نقطه‌ای: شهرِ این کد چیست؟
  2. پرسشِ بازه‌ای: کدهای بینِ این دو عدد کدام‌اند؟

الگوی دسترسی، قبل از هر کدی: انبار یک بار ساخته می‌شود و بعد بارها پرسیده می‌شود. پس هزینهٔ ساخت یک بار پرداخت می‌شود و هزینهٔ هر پرسش q بار — و این تنها چیزی است که تصمیم را تعیین می‌کند.

from bisect import bisect_left

CITIES = ("shiraz", "tabriz", "rasht", "yazd", "ahvaz", "kerman", "mashhad", "sari")
LOW, HIGH = 100_000, 1_100_000           # بازهٔ کدها، مستقل از n


def make_records(n, seed=SEED):
    """n رکوردِ (کد، شهر) با کدِ یکتا و بی‌ترتیب."""
    rng = random.Random(seed)
    codes = rng.sample(range(LOW, HIGH), n)
    return [(code, rng.choice(CITIES)) for code in codes]


for row in make_records(6):
    print(row)
(915965, 'shiraz')
(562141, 'tabriz')
(222526, 'tabriz')
(107855, 'kerman')
(195046, 'yazd')
(1055227, 'shiraz')

بازهٔ کدها ثابت است و به n بستگی ندارد — وگرنه جدول‌ها دو چیز را هم‌زمان عوض می‌کردند و از رویشان هیچ چیزی فهمیده نمی‌شد.

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

def city_linear(records, code):
    """روشِ ۱ — از اول تا آخر."""
    for c, city in records:
        if c == code:
            return city
    return None


def build_sorted(records):
    """روشِ ۲ — یک بار مرتب می‌کنیم و کدها را جدا نگه می‌داریم."""
    ordered = sorted(records)
    return ordered, [c for c, _ in ordered]


def city_binary(ordered, codes, code):
    i = bisect_left(codes, code)
    if i < len(codes) and codes[i] == code:
        return ordered[i][1]
    return None


def build_index(records):
    """روشِ ۳ — یک dict."""
    return {c: city for c, city in records}


sample = make_records(2_000)
ordered, codes = build_sorted(sample)
index = build_index(sample)
picker = random.Random(SEED)
probes = [picker.choice(sample)[0] for _ in range(200)] + [1, 2, 3]
print("هر سه روش یک جواب می‌دهند؟",
      all(city_linear(sample, p) == city_binary(ordered, codes, p) == index.get(p)
          for p in probes))
print("یک کدِ موجود   :", probes[0], "->", index.get(probes[0]))
print("یک کدِ ناموجود :", 1, "->", index.get(1))
هر سه روش یک جواب می‌دهند؟ True
یک کدِ موجود   : 359978 -> mashhad
یک کدِ ناموجود : 1 -> None

این سطر اول می‌آید، نه آخر — و کدهای ناموجود عمداً در نمونه‌ها هستند، چون خطاهای مرزی همان‌جا خودشان را نشان می‌دهند.

🤔 اول حدس بزن: برای هر سه روش ستونِ نسبتِ «گام به‌ازای هر پرسش» را بنویس. سه عدد، بعد جدول را ببین.

۳. جدولِ گام‌ها#

def linear_steps(records, code):
    for i, (c, _) in enumerate(records):
        if c == code:
            return i + 1
    return len(records)


def binary_steps(codes, code):
    lo, hi, steps = 0, len(codes) - 1, 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if codes[mid] == code:
            return steps
        if codes[mid] < code:
            lo = mid + 1
        else:
            hi = mid - 1
    return steps


LADDER = [2_000, 4_000, 8_000, 16_000]
sets = {}
for n in LADDER:
    rows = make_records(n)
    o, cs = build_sorted(rows)
    pick = random.Random(SEED)
    asked = [pick.choice(rows)[0] for _ in range(200)]
    sets[n] = (rows, o, cs, build_index(rows), asked)

print("— روشِ ۱: میانگینِ گام برای هر پرسش")
table([(n, sum(linear_steps(sets[n][0], p) for p in sets[n][4]) / 200)
       for n in LADDER], "گام", ",.1f")
print("\n— روشِ ۲: میانگینِ گام برای هر پرسش")
table([(n, sum(binary_steps(sets[n][2], p) for p in sets[n][4]) / 200)
       for n in LADDER], "گام", ",.2f")
— روشِ ۱: میانگینِ گام برای هر پرسش
         n               گام     نسبت به سطر قبل
     2,000             976.4                   —
     4,000           1,952.3                2.00
     8,000           3,904.0                2.00
    16,000           7,807.5                2.00

— روشِ ۲: میانگینِ گام برای هر پرسش
         n               گام     نسبت به سطر قبل
     2,000             10.13                   —
     4,000             10.97                1.08
     8,000             11.86                1.08
    16,000             13.06                1.10

2.00 در برابرِ 1.08: O(n) در برابرِ O(log n) — و در سطرِ آخر، 7,807.5 در برابرِ 13.06. روشِ ۳ ستونِ گام ندارد چون گامش همیشه یکی است.

for name, fn in (
    ("۱ خطی", lambda n: [city_linear(sets[n][0], p) for p in sets[n][4]]),
    ("۲ مرتب + binary", lambda n: [city_binary(sets[n][1], sets[n][2], p) for p in sets[n][4]]),
    ("۳ dict", lambda n: [sets[n][3].get(p) for p in sets[n][4]]),
):
    print(f"— روشِ {name}: زمانِ ۲۰۰ پرسش")
    table([(n, 1000 * clock(lambda k=n: fn(k), repeat=3)) for n in LADDER],
          "زمان (ms)", ",.3f")
    print()
— روشِ ۱ خطی: زمانِ ۲۰۰ پرسش
         n         زمان (ms)     نسبت به سطر قبل
     2,000             4.288                   —
     4,000             8.481                1.98
     8,000            17.361                2.05
    16,000            34.186                1.97

— روشِ ۲ مرتب + binary: زمانِ ۲۰۰ پرسش
         n         زمان (ms)     نسبت به سطر قبل
     2,000             0.061                   —
     4,000             0.070                1.16
     8,000             0.075                1.07
    16,000             0.081                1.08

— روشِ ۳ dict: زمانِ ۲۰۰ پرسش
         n         زمان (ms)     نسبت به سطر قبل
     2,000             0.012                   —
     4,000             0.012                1.06
     8,000             0.013                1.04
    16,000             0.013                1.01

سه ستونِ نسبت، سه مرتبه: 2.00، 1.08، 1.00. روشِ ۳ با هشت برابر شدنِ داده اصلاً تکان نخورد — O(1).

۴. هزینهٔ ساخت، که در جدولِ پرسش دیده نمی‌شود#

n = 16_000
rows = sets[n][0]
build_list = clock(lambda: list(rows), repeat=3)
build_sort = clock(lambda: build_sorted(rows), repeat=3)
build_dict = clock(lambda: build_index(rows), repeat=3)
print(f"n = {n:,} · هزینهٔ ساختِ اولیه (یک بار)")
print(f"  روشِ ۱ (هیچ ساختی)     : {1000 * build_list:>7,.2f} ms")
print(f"  روشِ ۲ (مرتب کردن)     : {1000 * build_sort:>7,.2f} ms")
print(f"  روشِ ۳ (ساختنِ dict)    : {1000 * build_dict:>7,.2f} ms")
n = 16,000 · هزینهٔ ساختِ اولیه (یک بار)
  روشِ ۱ (هیچ ساختی)     :    0.05 ms
  روشِ ۲ (مرتب کردن)     :    3.87 ms
  روشِ ۳ (ساختنِ dict)    :    1.09 ms

روشِ ۲ گران‌ترین ساخت را دارد و روشِ ۱ اصلاً ساختی ندارد. روی این ماشین، ساختِ روشِ ۲ حدودِ همان چیزی خرج برداشت که بیست پرسشِ خطی — همان نقطهٔ سربه‌سرِ فصلِ ۷، این بار با ساعت.

۵. پرسشی که dict جوابش را ندارد#

حالا پرسشِ دومِ بخشِ ۱: کدهای بینِ ۲۰۰٬۰۰۰ و ۲۲۰٬۰۰۰ کدام‌اند؟

dict جای هر کلید را از hash حساب می‌کند، و hash عمداً ترتیب را از بین می‌برد: دو کدِ نزدیک به هم در دو خانهٔ بی‌ربط می‌نشینند. پس این‌جا dict کاری جز دیدنِ همهٔ کلیدها نمی‌تواند بکند.

def range_by_scan(records, low, high):
    """با dict یا با فهرستِ خام: چاره‌ای جز دیدنِ همه نیست."""
    out = []
    steps = 0
    for c, _ in records:
        steps += 1
        if low <= c <= high:
            out.append(c)
    return sorted(out), steps


def range_by_bisect(codes, low, high):
    """روی فهرستِ مرتب: از جای شروع تا جای پایان، و نه یک گامِ بیشتر."""
    i = bisect_left(codes, low)
    out = []
    steps = 0
    while i < len(codes) and codes[i] <= high:
        out.append(codes[i])
        steps += 1
        i += 1
    return out, steps


WINDOW = (200_000, 220_000)
print("— پرسشِ «همهٔ کدهای بینِ ۲۰۰٬۰۰۰ و ۲۲۰٬۰۰۰»")
print(f"{'n':>8}{'پیدا شد':>10}{'پیمایشِ همه':>16}{'bisect':>10}{'نسبت':>10}")
for n in LADDER:
    rows, o, cs, idx, _ = sets[n]
    hit1, s1 = range_by_scan(rows, *WINDOW)
    hit2, s2 = range_by_bisect(cs, *WINDOW)
    assert hit1 == hit2
    print(f"{n:>8,}{len(hit1):>10,}{s1:>16,}{s2:>10,}{s1 / s2:>10,.0f}")
— پرسشِ «همهٔ کدهای بینِ ۲۰۰٬۰۰۰ و ۲۲۰٬۰۰۰»
       n   پیدا شد     پیمایشِ همه    bisect      نسبت
   2,000        33           2,000        33        61
   4,000        80           4,000        80        50
   8,000       162           8,000       162        49
  16,000       322          16,000       322        50

فهرستِ مرتب دقیقاً به تعدادِ جواب‌ها گام برمی‌دارد و نه یکی بیشتر — ستونِ «پیدا شد» و ستونِ bisect یکی‌اند. پیمایشِ کامل همیشه n گام می‌خورد، حتی وقتی جواب خالی باشد.

و این کلِ درسِ پروژه است: «سریع‌ترین ساختار» یک صفتِ مطلق نیست. روشِ ۳ برای پرسشِ نقطه‌ای بی‌رقیب بود و برای پرسشِ بازه‌ای بدترینِ سه‌تاست. ساختار را پرسش انتخاب می‌کند، نه برعکس.

try:
    build_index([(1, "shiraz"), ([2], "yazd")])
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
TypeError: unhashable type: 'list'

🔧 اگر کار نکرد: dict هر کلیدی را قبول نمی‌کند — همان TypeError ترمِ ۳ فصلِ ۶. اگر کدها به‌جای عدد، listی از چند بخش باشند، روشِ ۳ اصلاً ساخته نمی‌شود و باید به tuple تبدیلشان کنی. دو روشِ دیگر بی‌سروصدا کار می‌کنند — پس این خطا دارد یک قیدِ واقعیِ روشِ ۳ را اعلام می‌کند.

✅ چک کن: WINDOW را به بازه‌ای ببر که هیچ کدی در آن نباشد — مثلاً (1_200_000, 1_300_000). اول باید ستونِ «نسبت» را امن کنی، چون تقسیم بر صفر می‌شود: در همان خطِ print، به‌جای s1 / s2 بنویس (s1 / s2 if s2 else float("inf")). حالا ستونِ bisect باید صفر شود و ستونِ پیمایشِ کامل هنوز n بماند. و همان ZeroDivisionError خودش جوابِ سؤال است: وقتی جوابی نیست، فهرستِ مرتب هیچ گامی برنمی‌دارد.

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

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

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

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

بندِ ششم شرطش را نوشته و بندِ سوم دو سطر دارد، نه یکی. تصمیمی که فقط یک جنسِ پرسش را دیده باشد، برای پرسشِ دوم بی‌اعتبار است.

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

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

کلمه تلفظ به حروف فارسی یعنی چه
point query پوینت کوئری پرسش دربارهٔ یک کلیدِ مشخص
range query رِینج کوئری پرسش دربارهٔ همهٔ کلیدهای بینِ دو مقدار
index ایندکس ساختاری که از قبل ساخته می‌شود تا پرسش‌ها ارزان شوند

تمرین‌ها

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

در فصل بعد#

ترمِ چهار تمام شد: recursion، سه الگوریتمِ مرتب‌سازی، مرزِ پایین، و binary search.

و آخرین جدولِ همین فصل، ترمِ بعد را باز می‌کند. برای پرسشِ نقطه‌ای بهترین ساختار ترتیب را دور می‌ریزد و برای پرسشِ بازه‌ای بهترین ساختار به ترتیب نیاز دارد. فهرستِ مرتب هم کامل نیست: جست‌وجویش O(log n) است ولی درجش O(n).

ترمِ پنج ساختاری می‌سازد که ترتیب را نگه می‌دارد و درجش هم ارزان است — درخت — و همان‌جا اندازه‌اش می‌گیرد: n درج ستونِ نسبتِ 2.24 می‌دهد در برابرِ 3.94ِ insort. ولی همان فصل شرطش را هم نشان می‌دهد، چون این ارزانی روی ورودیِ از پیش مرتب کاملاً برعکس می‌شود. بعد سراغِ گراف می‌رود. پرسشِ بازه‌ای روی درخت را همان‌جا هم اندازه نمی‌گیریم؛ ترمِ ۶ فصلِ ۲ آن خانه را «نسنجیده» علامت می‌زند و می‌گوید چرا.

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

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