در این فصل چه یاد میگیری#
هیچ مفهومِ تازهای. این فصل هشت فصلِ قبل را روی یک مسئلهٔ واقعی بهکار میبرد.
یک انبارِ رکورد داریم و باید در آن دنبالِ کد بگردیم. سه راه میسازیم که جوابِ کاملاً یکسان میدهند، برای هر سه جدولِ رشد میگیریم، و یک تصمیمِ مستند مینویسیم. در n = 16,000 میانگینِ گامِ روشِ اول 7,807.5 است و روشِ دوم 13.06.
ولی نتیجهٔ اصلی در آن جدول نیست: پرسشی پیدا میکنیم که سریعترین ساختار اصلاً نمیتواند جوابش را بدهد و ۱۶٬۰۰۰ گام برمیدارد، در حالی که ساختارِ «کندتر» با ۳۲۲ گام تمامش میکند.

آخر این فصل میتوانی:
- سه ساختارِ جستوجو را روی یک مسئله بسنجی و برابریِ جوابشان را ثابت کنی
- هزینهٔ ساختِ اولیه را از هزینهٔ هر پرسش جدا کنی
- تشخیص بدهی کِی «سریعترین» ساختار جوابِ مسئلهٔ تو را ندارد
- یک تصمیمِ مستند بنویسی که شرطِ باطل شدنش هم در آن نوشته باشد
قبل از شروع#
از ترمِ ۳ فصلِ ۵: dict و هزینهٔ ثابتِ جستوجویش. از فصلِ ۷: bisect و نقطهٔ سربهسر.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. صورتِ مسئله#
هر رکورد یک کدِ یکتا دارد و یک شهر. کدها بیترتیب میآیند. دو پرسش داریم:
- پرسشِ نقطهای: شهرِ این کد چیست؟
- پرسشِ بازهای: کدهای بینِ این دو عدد کداماند؟
الگوی دسترسی، قبل از هر کدی: انبار یک بار ساخته میشود و بعد بارها پرسیده میشود. پس هزینهٔ ساخت یک بار پرداخت میشود و هزینهٔ هر پرسش 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). اول باید ستونِ «نسبت» را امن کنی، چون تقسیم بر صفر میشود: در همان خطِs1 / s2بنویس(s1 / s2 if s2 else float("inf")). حالا ستونِbisectباید صفر شود و ستونِ پیمایشِ کامل هنوزnبماند. و همانZeroDivisionErrorخودش جوابِ سؤال است: وقتی جوابی نیست، فهرستِ مرتب هیچ گامی برنمیدارد.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ سه ساختار روی یک انبارِ واحد و یک مجموعه پرسشِ واحد، با جوابِ برابرِ تأییدشده در هر دو جنسِ پرسش (بازهای با
assert). در کدام بازهٔn؟ ۲٬۰۰۰ تا ۱۶٬۰۰۰ رکورد، ۲۰۰ پرسش در هر اندازه، بازهٔ کدِ ثابت. با چند تکرار، و کمینه یا میانگین؟ جدولهای گام یک اجرا و قطعی؛ جدولهای زمان سه تکرار بهعلاوهٔ گرمکننده، کمینه.
۶. گزارشِ نهایی#
این شش بند تصمیمِ مستندِ این پروژهاند:
- الگوی دسترسی: یک بار ساخت،
qبار پرسش؛ دو جنسِ پرسش — نقطهای و بازهای. - بازهٔ
n: ۲٬۰۰۰ تا ۱۶٬۰۰۰ رکورد، با کدهای یکتا در یک بازهٔ ثابت. - مرتبهٔ اعلامشده: پرسشِ نقطهای — روشِ ۱
O(n)، روشِ ۲O(log n)، روشِ ۳O(1)؛ هر سه از ستونِ نسبت. پرسشِ بازهای — روشِ ۳O(n)، روشِ ۲ به اندازهٔ تعدادِ جوابها. - درستی: جوابِ هر سه روش در هر دو پرسش برابر تأیید شد، با کدهای ناموجود در نمونه.
- هزینهٔ پذیرفتهشده: ساختِ اولیه — روشِ ۲ گرانترین، و از حدودِ بیست پرسش به بعد جبران میشود (فصلِ ۷).
- تصمیم: اگر فقط پرسشِ نقطهای داری، روشِ ۳. اگر حتی یک پرسشِ بازهای هم داری، روشِ ۲ — و اگر
qاز حدودِ بیست کمتر است، روشِ ۱ و هیچ ساختاری.
بندِ ششم شرطش را نوشته و بندِ سوم دو سطر دارد، نه یکی. تصمیمی که فقط یک جنسِ پرسش را دیده باشد، برای پرسشِ دوم بیاعتبار است.
🤖 از دستیارت بپرس: جدولِ بخشِ ۵ را جلویش بگذار: «چرا
dictبرای پرسشِ بازهای بد است؟» بعد بپرس: «چه ساختاری هر دو پرسش را ارزان جواب میدهد؟» — جواب باید ساختاری را نام ببرد که هم ترتیب را نگه میدارد و هم درج را ارزان میکند. این موضوعِ ترمِ بعد است.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| point query | پوینت کوئری | پرسش دربارهٔ یک کلیدِ مشخص |
| range query | رِینج کوئری | پرسش دربارهٔ همهٔ کلیدهای بینِ دو مقدار |
| index | ایندکس | ساختاری که از قبل ساخته میشود تا پرسشها ارزان شوند |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
ترمِ چهار تمام شد: recursion، سه الگوریتمِ مرتبسازی، مرزِ پایین، و binary search.
و آخرین جدولِ همین فصل، ترمِ بعد را باز میکند. برای پرسشِ نقطهای بهترین ساختار ترتیب را دور میریزد و برای پرسشِ بازهای بهترین ساختار به ترتیب نیاز دارد. فهرستِ مرتب هم کامل نیست: جستوجویش O(log n) است ولی درجش O(n).
ترمِ پنج ساختاری میسازد که ترتیب را نگه میدارد و درجش هم ارزان است — درخت — و همانجا اندازهاش میگیرد: n درج ستونِ نسبتِ 2.24 میدهد در برابرِ 3.94ِ insort. ولی همان فصل شرطش را هم نشان میدهد، چون این ارزانی روی ورودیِ از پیش مرتب کاملاً برعکس میشود. بعد سراغِ گراف میرود. پرسشِ بازهای روی درخت را همانجا هم اندازه نمیگیریم؛ ترمِ ۶ فصلِ ۲ آن خانه را «نسنجیده» علامت میزند و میگوید چرا.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.