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

فصل ۲ از ۶

پیشرفت ترم
۰٪

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

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

اول، خودِ جدول را با اندازه‌گیری راستی‌آزمایی می‌کند: هفت خانه، یک ورودی، یک اجرا، یک ماشین. دوم، ستونی را نشان می‌دهد که هیچ جدولِ هزینه‌ای ندارد — و همان یک ستون کافی است که خانه‌ای با نمادِ درست، تصمیمِ غلط بسازد: O(1) در برابرِ O(n) در n = 100 فقط ۱٫۶ برابر درمی‌آید و در n = 100,000 نزدیکِ سی برابر. و سوم، خانه‌هایی را نام می‌برد که این دوره هرگز اندازه‌شان نگرفته و پرکردنشان از حافظه، بدترین کاری است که می‌شود با یک جدول کرد.

جدولِ شبکه‌ای که چند خانه‌اش با ابزار سنجیده می‌شود و چند خانه‌اش خالی مانده

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

  • جدولِ یکپارچهٔ هزینه را برای شش ساختارِ این دوره بخوانی
  • هر خانه‌اش را با یک benchmarkِ واحد راستی‌آزمایی کنی
  • بگویی چرا نمادِ درست در یک خانه، تصمیمِ درست تولید نمی‌کند
  • خانهٔ اندازه‌گیری‌نشده را از خانهٔ اندازه‌گیری‌شده تشخیص بدهی و خالی رهایش کنی

قبل از شروع#

از ترمِ ۲ فصلِ ۸: جدولِ هزینه برای ظرف‌های ترتیبی. از ترمِ ۱ فصلِ ۹: ثابتِ پنهان و نقطهٔ تقاطع. از فصلِ ۱: برگهٔ شکلِ مسئله.

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

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

۱. جدولِ یکپارچه#

هر خانه یک مرتبه دارد و شمارهٔ فصلی که آن را اندازه گرفته. ✗ یعنی این ساختار اصلاً چنین عملیاتی ندارد، و نسنجیده یعنی این دوره اندازه‌اش نگرفته — که با «ارزان است» یکی نیست.

ساختار خواندن با اندیس «هست یا نه؟» افزودن افزودن در ابتدا حذف کوچک‌ترین عضو پرسشِ بازه‌ای
list O(1) ت۲ف۱ O(n) ت۳ف۱ O(1) amortised ت۲ف۳ O(n) ت۲ف۴ از انتها O(1) · از ابتدا O(n) ت۲ف۴ · با مقدار O(n) همین فصل نسنجیده O(n) ت۴ف۹
deque O(n) ت۲ف۸ نسنجیده O(1) ت۲ف۷ O(1) ت۲ف۷ از هر دو سر O(1) ت۲ف۷ نسنجیده ✗
فهرستِ مرتب + bisect O(1) ت۲ف۱ O(log n) ت۴ف۷ O(n) ت۲ف۴ O(n) ت۲ف۴ O(n) ت۲ف۴ نسنجیده O(log n) + خروجی ت۴ف۹
set / dict ✗ O(1) ت۳ف۵ O(1) ت۳ف۳ ✗ O(1) همین فصل نسنجیده O(n) ت۴ف۹
BST ✗ O(log n) / منحرف O(n) ت۵ف۳ O(log n) / منحرف O(n) ت۵ف۳ · روی n کلیدِ مرتب، کلِ ساخت O(n²) ت۵ف۳ ✗ نسنجیده نسنجیده نسنجیده
heap ✗ نسنجیده O(log n) بدترین · O(1) حالتِ متوسط · روی ورودیِ نزولی n درج O(n log n) ت۵ف۴ ✗ ریشه O(log n) ت۵ف۴ O(1) ت۵ف۴ ✗

سطرِ BST دو مرتبه در یک خانه دارد و این غلطِ چاپی نیست. ترمِ ۵ نشان داد که همان درخت روی ورودیِ مرتب منحرف می‌شود و O(log n)اش به O(n) می‌رسد. خانه‌ای که به شکلِ ورودی بند است، بدونِ گفتنِ آن شکل نوشته نمی‌شود.

و خانهٔ «افزودن»ِ heap سه چیز می‌گوید، نه یکی، چون ت۵ف۴ اندازه گرفت که n درج روی ورودیِ تصادفی خطی است و روی ورودیِ نزولی O(n log n). پس آن O(1) حالتِ متوسط است، نه amortised: amortisedِ ت۲ف۳ تضمینی روی هر دنبالهٔ عملیات است، ولی حالتِ متوسط میانگینی روی ورودیِ تصادفی است که یک ورودیِ خاص می‌تواند از آن بیرون بزند. تنها خانهٔ amortisedِ این جدول، «افزودن»ِ list است.

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

۲. چرا این جدول هنوز قابلِ اعتماد نیست#

خانه‌های جدولِ بالا از دوازده فصلِ مختلف جمع شده‌اند. هر خانه روی ورودیِ متفاوت، در اندازهٔ متفاوت و در نشستِ متفاوتی از Colab اندازه گرفته شده — یعنی هیچ دو خانه‌ای مستقیماً با هم قابلِ مقایسه نیستند.

پس یک benchmarkِ واحد می‌سازیم: یک مجموعه کلید، یک مجموعه پرسش، سه ظرف که از همان کلیدها ساخته می‌شوند، و همه در یک اجرا.

from bisect import bisect_left
from collections import deque

BENCH = [4_000, 8_000, 16_000, 32_000]
QUERIES = 200
rng = random.Random(SEED)
box = {}
for n in BENCH:
    keys = rng.sample(range(10 * n), n)
    asks = [rng.choice(keys) for _ in range(QUERIES)]
    box[n] = (keys, sorted(keys), set(keys), asks)

print("اندازه‌ها:", ", ".join(f"{n:,}" for n in BENCH), "· پرسش در هر اندازه:", QUERIES)
print("هر سه ظرف از کلیدهای یکسان ساخته شده‌اند؟",
      all(set(box[n][0]) == box[n][2] == set(box[n][1]) for n in BENCH))
اندازه‌ها: 4,000, 8,000, 16,000, 32,000 · پرسش در هر اندازه: 200
هر سه ظرف از کلیدهای یکسان ساخته شده‌اند؟ True

آن سطرِ دوم همان کاری است که ترمِ ۳ فصلِ ۷ با == می‌کرد: تا وقتی سه ظرف واقعاً یک چیز را نگه ندارند، مقایسهٔ هزینهٔ خواندنشان بی‌معناست.

۳. راستی‌آزماییِ خانه‌ها با شمارشِ گام#

اول با شمارنده، چون شمارش به ماشین بند نیست و روی نوت‌بوکِ تو هم همین عددها درمی‌آید.

🤔 اول حدس بزن: ستونِ نسبت را برای هر دو جدول بنویس. جدولِ O(n) باید 2 بدهد و جدولِ O(log n) باید 1ِ چیزی بدهد. حدس بزن آن «چیزی» چقدر است — و اینکه با هر دو برابر شدنِ n، bisect چند گامِ اضافه برمی‌دارد.

def linear_steps(items, asks):
    """گامِ «هست یا نه؟» روی list: تا پیدا شدن، یکی‌یکی."""
    total = 0
    for a in asks:
        for value in items:
            total += 1
            if value == a:
                break
    return total / len(asks)


def bisect_steps(ordered, asks):
    """گامِ همان پرسش روی فهرستِ مرتب: هر گام بازه را نصف می‌کند."""
    total = 0
    for a in asks:
        lo, hi = 0, len(ordered) - 1
        while lo <= hi:
            total += 1
            mid = (lo + hi) // 2
            if ordered[mid] == a:
                break
            if ordered[mid] < a:
                lo = mid + 1
            else:
                hi = mid - 1
    return total / len(asks)


print("— «هست یا نه؟» روی list")
table([(n, linear_steps(box[n][0], box[n][3])) for n in BENCH], "گام", ",.1f")
print("\n— «هست یا نه؟» روی فهرستِ مرتب با bisect")
table([(n, bisect_steps(box[n][1], box[n][3])) for n in BENCH], "گام", ",.2f")
— «هست یا نه؟» روی list
         n               گام     نسبت به سطر قبل
     4,000           2,094.4                   —
     8,000           3,934.2                1.88
    16,000           7,671.2                1.95
    32,000          15,056.5                1.96

— «هست یا نه؟» روی فهرستِ مرتب با bisect
         n               گام     نسبت به سطر قبل
     4,000             11.10                   —
     8,000             12.05                1.09
    16,000             13.19                1.09
    32,000             14.05                1.07

دو خانهٔ جدول تأیید شدند. ستونِ اول به 2 نزدیک می‌شود — O(n) — و اینکه دقیقاً 2.00 نشد، چون هر پرسش در جای تصادفی‌ای از فهرست پیدا می‌شود و میانگینِ دویست پرسش هنوز کمی نوسان دارد.

ستونِ دوم 1.07 تا 1.09 است و جالب‌ترین چیزِ این جدول در ستونِ گام است، نه ستونِ نسبت: از 11.10 به 12.05 به 13.19 به 14.05. هر بار که n دو برابر می‌شود، حدودِ یک گام اضافه می‌شود — و این دقیقاً تعریفِ O(log n) است.

✅ چک کن: یک اندازهٔ پنجم به BENCH اضافه کن — 64_000 — بعد سلولِ ساختِ box و جدولِ bisect را دوباره بگیر. گامِ سطرِ تازه باید حدودِ یکی بیشتر از 32,000 باشد، نه دو برابر. اگر دو برابر شد، ورودی را مرتب نداده‌ای و bisect دارد روی داده‌ای کار می‌کند که پیش‌شرطش را ندارد.

حالا خانه‌ای از ستونِ تازه. values.remove(x) دو کار پشتِ سرِ هم می‌کند: می‌گردد تا مقدار را پیدا کند، و بعد بقیه را یک خانه عقب می‌کشد.

🤔 اول حدس بزن: ستونِ نسبت را بنویس — و مهم‌تر: حدس بزن گامِ حذف به محلِ مقدار در فهرست بستگی دارد یا نه.

victim_rng = random.Random(SEED)
DROPS = 2_000
victims = {n: victim_rng.sample(box[n][0], DROPS) for n in BENCH}


def remove_steps(items, dying):
    """گامِ list.remove(x) با دست: تا پیدا شدن بگرد، بعد بقیه را یک خانه عقب بکش."""
    work = list(items)
    total = 0
    for v in dying:
        i = 0
        while work[i] != v:
            total += 1
            i += 1
        total += 1 + (len(work) - i - 1)
        del work[i]
    return total / len(dying)


print("— حذفِ یک مقدار از list · گام به‌ازای هر حذف")
table([(n, remove_steps(box[n][0], victims[n][:QUERIES])) for n in BENCH], "گام", ",.1f")
— حذفِ یک مقدار از list · گام به‌ازای هر حذف
         n               گام     نسبت به سطر قبل
     4,000           3,900.5                   —
     8,000           7,900.5                2.03
    16,000          15,900.5                2.01
    32,000          31,900.5                2.01

نسبت 2.00 — یعنی O(n) — ولی عددِ خودِ ستونِ گام جالب‌تر است: 3,900.5 روی فهرستی با 4,000 عضو.

گامِ هر حذف تقریباً برابرِ طولِ فهرست است، هر جای فهرست که آن مقدار باشد. اگر مقدار در خانهٔ i باشد، گشتن i گام می‌خورد، خودِ پیدا کردنش یک گام، و جابه‌جایی n - i - 1 گام؛ جمعشان همیشه n است و جای مقدار فقط سهمِ گشتن و جابه‌جایی را عوض می‌کند. (عددِ 3,900.5 به‌جای 4,000 است چون فهرست در طولِ همین دویست حذف کوچک می‌شود.) خانهٔ «حذف»ِ سطرِ list دیگر نقلِ قول نیست.

۴. همان خانه‌ها روی ساعت#

def ask_all(container, asks):
    hits = 0
    for a in asks:
        if a in container:
            hits += 1
    return hits


def ask_bisect(ordered, asks):
    hits = 0
    for a in asks:
        i = bisect_left(ordered, a)
        if i < len(ordered) and ordered[i] == a:
            hits += 1
    return hits


for label, pick in (("list", 0), ("مرتب + bisect", None), ("set", 2)):
    print(f"— {label} · µs به‌ازای هر پرسش")
    if pick is None:
        rows = [(n, 1e6 * clock(lambda k=n: ask_bisect(box[k][1], box[k][3]),
                                repeat=3) / QUERIES) for n in BENCH]
    else:
        rows = [(n, 1e6 * clock(lambda k=n, i=pick: ask_all(box[k][i], box[k][3]),
                                repeat=3) / QUERIES) for n in BENCH]
    table(rows, "µs", ",.3f")
    print()
— list · µs به‌ازای هر پرسش
         n                µs     نسبت به سطر قبل
     4,000            13.247                   —
     8,000            26.668                2.01
    16,000            54.971                2.06
    32,000           105.782                1.92

— مرتب + bisect · µs به‌ازای هر پرسش
         n                µs     نسبت به سطر قبل
     4,000             0.211                   —
     8,000             0.232                1.10
    16,000             0.266                1.15
    32,000             0.290                1.09

— set · µs به‌ازای هر پرسش
         n                µs     نسبت به سطر قبل
     4,000             0.033                   —
     8,000             0.030                0.89
    16,000             0.033                1.10
    32,000             0.030                0.92

سه ستونِ نسبت، سه مرتبه: نزدیکِ 2، کمی بالای 1، و 1. O(n) و O(log n) و O(1)، همان‌طور که جدول ادعا کرده بود.

و در n = 32,000، همان سه خانه روی ساعتِ این ماشین این‌اند: 106 میکروثانیه، 0.29 و 0.030. نسبتِ list به set بیش از سه هزار برابر درآمد — و چنین عددی در هیچ خانه‌ای از جدولِ بخشِ ۱ نوشته نشده، چون جدول ثابت‌ها را نمی‌بیند.

و حالا خانهٔ «حذف»ِ set، که شمارنده نمی‌تواند بگیردش: گامِ bisect را می‌شد شمرد چون کدش مالِ خودمان بود، ولی داخلِ set را از بیرون نمی‌شود شمرد. پس این یکی فقط با ساعت به دست می‌آید — و حذف ظرفش را عوض می‌کند، همان تلهٔ ترمِ ۱ فصلِ ۳. راهِ حل همان است: یک بار «کپی + حذف» را بسنج، یک بار «فقط کپی»، و تفریق کن.

def drop_from_list(items, dying):
    for v in dying:
        items.remove(v)
    return len(items)


def drop_from_set(bag, dying):
    for v in dying:
        bag.discard(v)
    return len(bag)


list_rows, set_rows = [], []
for n in BENCH:
    keys, _, bag, _ = box[n]
    dying = victims[n]
    copy_list = clock(lambda k=keys: list(k), repeat=5)
    copy_set = clock(lambda b=bag: set(b), repeat=5)
    with_list = clock(lambda k=keys, d=dying: drop_from_list(list(k), d), repeat=5)
    with_set = clock(lambda b=bag, k=keys: drop_from_set(set(b), k), repeat=5)
    list_rows.append((n, 1e6 * (with_list - copy_list) / DROPS))
    set_rows.append((n, 1e6 * (with_set - copy_set) / n))

print("— حذف با مقدار از list · µs به‌ازای هر حذف")
table(list_rows, "µs", ",.3f")
print("\n— حذف از set · µs به‌ازای هر حذف")
table(set_rows, "µs", ",.3f")
print(f"\nدر n = 32,000 نسبتشان {list_rows[-1][1] / set_rows[-1][1]:,.0f} برابر است.")
— حذف با مقدار از list · µs به‌ازای هر حذف
         n                µs     نسبت به سطر قبل
     4,000            12.170                   —
     8,000            28.119                2.31
    16,000            63.235                2.25
    32,000           135.498                2.14

— حذف از set · µs به‌ازای هر حذف
         n                µs     نسبت به سطر قبل
     4,000             0.051                   —
     8,000             0.039                0.75
    16,000             0.031                0.80
    32,000             0.035                1.12

در n = 32,000 نسبتشان 3,908 برابر است.

ستونِ list نزدیکِ 2 است و ستونِ set حولِ 1 می‌لرزد: O(n) در برابرِ O(1). خانهٔ «حذف»ِ سطرِ set دیگر «نسنجیده» نیست.

و یک نکتهٔ صداقتی: این دو ستون با تعدادِ حذفِ متفاوت گرفته شده‌اند — دو هزار حذف برای list و n حذف برای set — چون دو هزار حذف از یک set آن‌قدر ارزان است که زیرِ نویزِ تفریق می‌رود و عددِ منفی می‌دهد. هر دو ستون بر تعدادِ حذفِ خودشان تقسیم شده‌اند، پس واحدشان یکی است؛ ولی کسی که این جدول را بازتولید می‌کند باید این را بداند.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک پرسشِ واحد — «این کلید هست یا نه؟» — روی سه ظرف که از کلیدهای یکسان ساخته شده‌اند، با همان دویست پرسشِ ثابت؛ و بعد یک حذفِ واحد روی دو ظرف از همان کلیدها. در کدام بازهٔ n؟ ۴٬۰۰۰ تا ۳۲٬۰۰۰ کلید، با کلیدهایی در بازه‌ای ده برابرِ n تا نسبتِ پیدا شدن ثابت بماند. با چند تکرار، و کمینه یا میانگین؟ جدول‌های گام یک اجرا و قطعی؛ جدول‌های زمان سه تا پنج تکرار به‌علاوهٔ گرم‌کننده، کمینه، و جدولِ حذف با تفریقِ هزینهٔ کپی.

۵. ستونی که جدول ندارد#

جدولِ بخشِ ۱ می‌گوید خواندن با اندیس روی list هزینهٔ ثابت دارد و روی deque هزینهٔ O(n). هر دو درست‌اند. حالا ببین آن «درست» در عمل چقدر است.

🤔 اول حدس بزن: ستونِ نسبتِ list و ستونِ نسبتِ deque را جدا بنویس — و مخصوصاً حدس بزن deque از همان سطرِ اول عددِ 2 می‌دهد یا نه.

READS = 2_000
picker = random.Random(SEED)
LADDER = [4_000, 8_000, 16_000, 32_000]
shelf = {}
for n in LADDER + [100, 100_000]:
    shelf[n] = (list(range(n)), deque(range(n)),
                [picker.randrange(n) for _ in range(READS)])


def read_all(container, idxs):
    total = 0
    for i in idxs:
        total += container[i]
    return total


print("— list · ns به‌ازای هر خواندن")
table([(n, 1e9 * clock(lambda k=n: read_all(shelf[k][0], shelf[k][2]), repeat=5) / READS)
       for n in LADDER], "ns", ",.1f")
print("\n— deque · ns به‌ازای هر خواندن")
table([(n, 1e9 * clock(lambda k=n: read_all(shelf[k][1], shelf[k][2]), repeat=5) / READS)
       for n in LADDER], "ns", ",.1f")
— list · ns به‌ازای هر خواندن
         n                ns     نسبت به سطر قبل
     4,000              32.7                   —
     8,000              35.2                1.08
    16,000              35.3                1.01
    32,000              37.5                1.06

— deque · ns به‌ازای هر خواندن
         n                ns     نسبت به سطر قبل
     4,000              58.7                   —
     8,000              78.8                1.34
    16,000             123.1                1.56
    32,000             224.5                1.82

ستونِ deque از 1.34 شروع می‌شود و به 1.82 می‌رسد — نه از همان اول 2. دلیلش همان ثابتِ پنهانِ ترمِ ۱ فصلِ ۹ است: هر خواندن یک هزینهٔ ثابت دارد که به n ربطی ندارد، و در nهای کوچک آن ثابت هنوز بخشِ بزرگی از عدد است. مرتبه با بزرگ شدنِ n خودش را نشان می‌دهد، نه در سطرِ اول.

حالا همان دو خانه، این بار با ستونی که هیچ جدولِ هزینه‌ای ندارد:

print(f"{'n':>10}{'list (ns)':>12}{'deque (ns)':>13}{'چند برابر':>12}")
for n in [100] + LADDER + [100_000]:
    fast = 1e9 * clock(lambda k=n: read_all(shelf[k][0], shelf[k][2]), repeat=5) / READS
    slow = 1e9 * clock(lambda k=n: read_all(shelf[k][1], shelf[k][2]), repeat=5) / READS
    print(f"{n:>10,}{fast:>12.1f}{slow:>13.1f}{slow / fast:>12.1f}")
         n   list (ns)   deque (ns)   چند برابر
       100        22.8         36.2         1.6
     4,000        28.3         51.9         1.8
     8,000        29.2         69.9         2.4
    16,000        33.2        117.0         3.5
    32,000        35.6        201.1         5.6
   100,000        37.7       1029.9        27.3

همان دو خانه، همان دو نماد، و ستونِ آخر از 1.6 تا 27.3 می‌رود.

O(1) در برابرِ O(n) در نمادنویسی یک فاصلهٔ بی‌نهایت است. در n = 100 این فاصله کمتر از دو برابر است — یعنی عملاً هیچ. اگر مسئلهٔ تو همیشه صد عضو دارد، انتخابِ deque به‌جای list برای خواندن با اندیس اشتباهِ قابلِ اغماضی است؛ اگر صد هزار عضو دارد، نیست.

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

۶. خانه‌هایی که این دوره اندازه‌شان نگرفته#

در جدولِ بخشِ ۱ نُه خانه نسنجیده علامت خورده‌اند. این عمدی است و مهم‌ترین بخشِ آن جدول است:

  1. کوچک‌ترین عضو در BST — ساختنش آسان است (تا آخر به چپ برو) ولی این دوره اندازه‌اش نگرفت.
  2. پرسشِ بازه‌ای در BST — ترمِ ۵ درخت را ساخت و پیمایشش کرد، ولی «همهٔ کلیدهای بینِ این دو مقدار» را روی درخت اندازه نگرفت.
  3. حذف از BST — و این از دو تای بالا صریح‌تر است: این دوره حذف از BST را نه نوشت و نه اندازه گرفت. ترمِ ۵ فصلِ ۳ فقط bst_insert و bst_search را ساخت؛ حذف سه حالتِ متفاوت دارد (برگ، یک فرزند، دو فرزند) و هیچ‌کدام کد نشده‌اند. این خانه نه «گران» است و نه «ارزان»؛ خالی است.
  4. «هست یا نه؟» روی heap — heap فقط تضمین می‌کند ریشه کوچک‌ترین است؛ دربارهٔ بقیه هیچ ترتیبی ندارد، پس این پرسش باید کلِ ساختار را ببیند. این را هم اندازه نگرفتیم.
  5. کوچک‌ترین عضو در list، deque، فهرستِ مرتب و set/dict، و «هست یا نه؟» روی deque — پنج خانه‌ای که جوابشان بدیهی به‌نظر می‌رسد و دقیقاً به همین دلیل اندازه گرفته نشدند. «بدیهی است» همان جمله‌ای است که خانهٔ نقل‌شده را شبیهِ خانهٔ اندازه‌گیری‌شده می‌کند.

و یک خانه که اصلاً در جدول نیست: BSTِ متوازن. ترمِ ۵ گفت متوازن‌سازی چیزی است که وجود دارد؛ این دوره هیچ درختِ متوازنی نساخت و اندازه نگرفت. پس سطرِ BST فقط دربارهٔ درختی حرف می‌زند که ما ساختیم.

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

🔧 اگر کار نکرد: بعضی خانه‌های جدول نه «گران» بلکه اصلاً موجود نیستند، و پایتون این را با خطا می‌گوید:

try:
    deque(range(10))[3:5]
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
TypeError: sequence index must be integer, not 'slice'

deque برش ندارد. خانهٔ «پرسشِ بازه‌ای» در سطرِ deque با ✗ علامت خورده و این خطا همان ✗ است. تفاوتِ ✗ با یک عددِ بزرگ این است که ✗ وقتِ اجرا معلوم می‌شود، نه بعد از تحویل — و همین آن را از خانهٔ کند بهتر می‌کند، نه بدتر.

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

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

کلمه تلفظ به حروف فارسی یعنی چه
decision table دِسیژن تِیبل جدولی که هزینهٔ هر عملیات را در هر ساختار کنارِ هم می‌گذارد
benchmark harness بنچ‌مارک هارنس چارچوبی که همهٔ نامزدها را با یک ورودی و در یک اجرا می‌سنجد

تمرین‌ها

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

در فصل بعد#

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

فصلِ بعد همان معامله را باز می‌کند. یک index می‌سازیم که هر پرسش را از حدودِ دو میلی‌ثانیه به کمتر از یک‌دهمِ میکروثانیه می‌رساند، و قیمتِ دقیقش را به بایت اندازه می‌گیریم. بعد جایی می‌رویم که حافظه دیوار است نه زمان: جایی که یک indexِ کامل‌تر از آن اصلاً ساخته نمی‌شود، و انتخابِ «واضح» برمی‌گردد سرِ جای اول.

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

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