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

فصل ۷ از ۹

پیشرفت ترم
۰٪

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

فصلِ قبل گفت مرتب کردن گران است. این فصل می‌گوید چه چیزی می‌خرد: در n = 8,000، پرسشِ «هست یا نه؟» که با جست‌وجوی خطی به‌طورِ متوسط ۴٬۰۰۰ گام می‌خواست، با ۱۳ گام جواب می‌گیرد. و بعد نقطهٔ سربه‌سر را حساب می‌کنیم: از q = 24 پرسش به بعد، یک بار مرتب کردن به‌صرفه است.

ولی مهم‌ترین بخشِ این فصل جدولش نیست. binary search مشهورترین الگوریتمی است که برنامه‌نویس‌ها غلط می‌نویسند — و بدترین شکلِ غلط نوشتنش هیچ خطایی نمی‌دهد. نسخه‌ای که این‌جا می‌بینی برای ۴۸۹ عضو از ۱٬۰۰۰ عضوی که واقعاً در فهرست هستند می‌گوید «پیدا نشد» و آبی از آب تکان نمی‌خورد.

خط‌کشی که در هر گام نیمی از بازه را کنار می‌گذارد و دو گیرهٔ متحرک دارد

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

  • binary search را با ناوردای بازه بنویسی و مرزهایش را توجیه کنی
  • خطای یکی‌کم‌یکی‌زیاد را با آزمونِ کامل پیدا کنی، نه با نگاه کردن
  • bisect را درست به‌کار ببری
  • نقطهٔ سربه‌سرِ «مرتب کردن در برابرِ جست‌وجوی خطی» را برای nِ خودت حساب کنی

قبل از شروع#

از ترمِ ۳ فصلِ ۱: جست‌وجوی خطی و هزینه‌اش.

از فصلِ ۴: شمارشِ مقایسه‌های merge sort — بخشِ ۶ برای حسابِ نقطهٔ سربه‌سر به همان عدد احتیاج دارد و کدش این‌جا فشرده تکرار می‌شود.

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

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

۱. هفت عضو، با دست#

ایده در یک جمله: وسط را نگاه کن. اگر جوابت نبود، نصفِ بی‌فایده را دور بریز.

def binary_search_traced(values, target):
    """اندیسِ target یا -1، با چاپِ بازه در هر گام."""
    lo, hi = 0, len(values) - 1
    step = 0
    while lo <= hi:
        step += 1
        mid = (lo + hi) // 2
        print(f"گام {step}: بازه [{lo}..{hi}]  ->  mid={mid}  values[mid]={values[mid]}")
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


row = [10, 11, 13, 14, 18, 25, 29]
print("فهرستِ مرتب:", row)
print("دنبالِ 25 :", binary_search_traced(row, 25))
print()
print("دنبالِ 12 :", binary_search_traced(row, 12))
فهرستِ مرتب: [10, 11, 13, 14, 18, 25, 29]
گام 1: بازه [0..6]  ->  mid=3  values[mid]=14
گام 2: بازه [4..6]  ->  mid=5  values[mid]=25
دنبالِ 25 : 5

گام 1: بازه [0..6]  ->  mid=3  values[mid]=14
گام 2: بازه [0..2]  ->  mid=1  values[mid]=11
گام 3: بازه [2..2]  ->  mid=2  values[mid]=13
دنبالِ 12 : -1

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

ناوردای این حلقه یک جمله است و کلِ درستیِ الگوریتم روی آن سوار است: «اگر target در فهرست باشد، حتماً بینِ lo و hi است.» قبل از اولین دور درست است (بازه کلِ فهرست است) و هر دور هم درست می‌ماند، چون فقط تکه‌ای دور ریخته می‌شود که ثابت کرده‌ایم نمی‌تواند شاملش باشد. وقتی بازه خالی شود، همان جمله می‌گوید target در فهرست نیست.

۲. گام‌ها: log n در برابرِ n#

🤔 اول حدس بزن: با دو برابر شدنِ n، بیشترین تعدادِ گامِ binary search چند برابر می‌شود؟ و برای جست‌وجوی خطی؟ دو عدد بنویس، بعد جدول را ببین.

def binary_search(values, target):
    """(اندیس یا -1، تعدادِ گام)"""
    lo, hi = 0, len(values) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if values[mid] == target:
            return mid, steps
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, steps


def linear_search(values, target):
    """(اندیس یا -1، تعدادِ گام)"""
    for i, v in enumerate(values):
        if v == target:
            return i, i + 1
    return -1, len(values)


LADDER = [1_000, 2_000, 4_000, 8_000]
rows = {n: list(range(0, 2 * n, 2)) for n in LADDER}


def worst_steps(fn, values):
    """بیشترین گام روی همهٔ عضوهای موجود."""
    return max(fn(values, v)[1] for v in values)


def average_steps(fn, values):
    return sum(fn(values, v)[1] for v in values) / len(values)


print("جوابِ دو روش یکی است؟",
      all(binary_search(rows[1_000], v)[0] == linear_search(rows[1_000], v)[0]
          for v in rows[1_000]))
print("\n— binary search: بیشترین گام")
table([(n, worst_steps(binary_search, rows[n])) for n in LADDER], "گام", ",d")
print("\n— linear search: میانگینِ گام")
table([(n, average_steps(linear_search, rows[n])) for n in LADDER], "گام", ",.1f")
جوابِ دو روش یکی است؟ True

— binary search: بیشترین گام
         n               گام     نسبت به سطر قبل
     1,000                10                   —
     2,000                11                1.10
     4,000                12                1.09
     8,000                13                1.08

— linear search: میانگینِ گام
         n               گام     نسبت به سطر قبل
     1,000             500.5                   —
     2,000           1,000.5                2.00
     4,000           2,000.5                2.00
     8,000           4,000.5                2.00

10، 11، 12، 13 — هر دو برابر شدنِ n دقیقاً یک گام اضافه می‌کند. ستونِ نسبت 1.08 است و رو به یک. این O(log n) است و همان شکلی است که ترمِ ۱ فصلِ ۵ در تابعِ halve_down دید.

جدولِ دوم 2.00 است: O(n). و فاصلهٔ عملی‌شان را در سطرِ آخر ببین — 13 در برابرِ 4,000.

۳. دو مرز، دو شکستِ متفاوت#

حالا بدترین بخشِ این الگوریتم. مرزهای lo و hi سه جا نوشته می‌شوند — مقدارِ اولیه، شرطِ حلقه، و دو خطِ به‌روزرسانی — و این سه باید با هم بخوانند. اگر نخوانند، دو اتفاق ممکن است بیفتد.

def search_bad_loud(values, target):
    """اشتباهِ اول: hi را برابرِ طول گرفته‌ایم، نه طول منهای یک."""
    lo, hi = 0, len(values)
    while lo <= hi:
        mid = (lo + hi) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


try:
    search_bad_loud([10, 11, 13, 14], 99)
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
IndexError: list index out of range

این یکی خوش‌شانسی است. hi = len(values) یعنی بازه یک خانهٔ بیرونی هم دارد، و mid بالاخره روی همان خانه می‌افتد: IndexError. خطا صریح است و همان‌جا اصلاح می‌شود.

حالا نوعِ دوم:

def search_bad_quiet(values, target):
    """اشتباهِ دوم: شرطِ حلقه lo < hi است ولی بازه طوری کوچک می‌شود
    که آخرین نامزد هیچ‌وقت نگاه نمی‌شود."""
    lo, hi = 0, len(values) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


sample = rows[1_000]
missed = [v for v in sample if search_bad_quiet(sample, v) == -1]
print("عضوهایی که وجود دارند ولی «پیدا نشد» گرفتند:", len(missed))
print("ده تای اول:", missed[:10])
print("هیچ خطایی داد؟ نه — فقط جوابِ غلط.")
عضوهایی که وجود دارند ولی «پیدا نشد» گرفتند: 489
ده تای اول: [2, 6, 10, 14, 18, 22, 26, 30, 34, 38]
هیچ خطایی داد؟ نه — فقط جوابِ غلط.

۴۸۹ عضو از ۱٬۰۰۰ عضوِ موجود، «پیدا نشد». یک نویسه اختلاف — <= به < — و هیچ استثنایی، هیچ هشداری، هیچ چیزی.

found = [v for v in sample if search_bad_quiet(sample, v) != -1]
print("درست جواب داد برای:", len(found), "عضو از", len(sample))
print("\nروی هشت عضو، دستی:")
tiny = [10, 11, 13, 14, 18, 25, 29, 31]
for v in tiny:
    print(f"  {v:>3} -> درست: {binary_search(tiny, v)[0]:>2}"
          f"   ·  معیوب: {search_bad_quiet(tiny, v):>2}")
درست جواب داد برای: 511 عضو از 1000

روی هشت عضو، دستی:
   10 -> درست:  0   ·  معیوب: -1
   11 -> درست:  1   ·  معیوب:  1
   13 -> درست:  2   ·  معیوب: -1
   14 -> درست:  3   ·  معیوب:  3
   18 -> درست:  4   ·  معیوب: -1
   25 -> درست:  5   ·  معیوب:  5
   29 -> درست:  6   ·  معیوب:  6
   31 -> درست:  7   ·  معیوب: -1

🔧 اگر کار نکرد: با while lo < hi، حلقه وقتی lo و hi به هم برسند می‌ایستد — بدونِ اینکه آن یک خانهٔ باقی‌مانده را نگاه کرده باشد. پس هر عضوی که جست‌وجو تا آخرین خانه دنبالش برود، «پیدا نشد» می‌گیرد.

و راهِ گرفتنش هم در همین خروجی است: کلِ فهرست را آزمون کن. اگر فقط دو سه عدد را امتحان می‌کردی — مثلاً 11 و 14 — کد سالم به‌نظر می‌رسید. آزمونی که همهٔ عضوها را می‌سنجد یک خط بیشتر نیست و این ردهٔ خطا را کاملاً می‌گیرد.

دو نسخهٔ سالم وجود دارد و باید یکی‌شان را انتخاب کنی و به آن وفادار بمانی: یا hi = len - 1 با while lo <= hi و hi = mid - 1، یا hi = len با while lo < hi و hi = mid. قاطیِ این دو، همان چیزی است که این‌جا دیدی.

۴. bisect: نسخه‌ای که لازم نیست بنویسی#

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

from bisect import bisect_left, insort

haystack = [10, 11, 13, 14, 18, 25, 29]


def find(values, target):
    """جای درستِ استفاده از bisect برای پرسشِ «هست یا نه؟»"""
    i = bisect_left(values, target)
    if i < len(values) and values[i] == target:
        return i
    return -1


for target in (25, 12, 10, 29, 40):
    print(f"find({target:>2}) = {find(haystack, target):>2}"
          f"   ·  binary_search = {binary_search(haystack, target)[0]:>2}")

fresh = []
for v in [29, 10, 14, 37, 13]:
    insort(fresh, v)
print("\nساختنِ فهرستِ مرتب با insort:", fresh)
find(25) =  5   ·  binary_search =  5
find(12) = -1   ·  binary_search = -1
find(10) =  0   ·  binary_search =  0
find(29) =  6   ·  binary_search =  6
find(40) = -1   ·  binary_search = -1

ساختنِ فهرستِ مرتب با insort: [10, 13, 14, 29, 37]

bisect دقیقاً همان جواب‌ها را می‌دهد — و سه سطرِ آخر نشان می‌دهد که مرزها را هم درست می‌گیرد: هم عضوِ اول، هم عضوِ آخر، هم مقداری بزرگ‌تر از همه.

و insort چیزی است که در بخشِ ۶ به آن برمی‌گردیم: یک عضوِ تازه را در جای درستش درج می‌کند. پیدا کردنِ جا O(log n) است، ولی خودِ درج O(n) — چون list باید همه را جابه‌جا کند، همان‌طور که ترمِ ۲ فصلِ ۴ اندازه گرفت.

۵. پیش‌شرط، و چیزی که نقضش می‌کند#

scrambled = [29, 10, 14, 37, 13, 25, 11, 18]
print("فهرستِ بی‌ترتیب:", scrambled)
missed = [v for v in scrambled if binary_search(scrambled, v)[0] == -1]
print("عضوهایی که پیدا نشدند:", len(missed), "از", len(scrambled))
print("کدام‌ها:", missed)
فهرستِ بی‌ترتیب: [29, 10, 14, 37, 13, 25, 11, 18]
عضوهایی که پیدا نشدند: 5 از 8
کدام‌ها: [29, 13, 25, 11, 18]

پنج عضو از هشت عضوِ موجود گم شدند، با کدِ کاملاً سالم. چون ناوردای بخشِ ۱ روی یک فرض ایستاده بود: «تکه‌ای که دور می‌ریزم نمی‌تواند شاملش باشد». روی فهرستِ بی‌ترتیب این فرض دروغ است و کلِ استدلال فرو می‌ریزد.

⚠️ مواظب باش: این ردهٔ خطا در کدِ واقعی معمولاً وقتی پیدا می‌شود که کسی جایی به فهرست عضو اضافه کرده و مرتب‌بودنش را نگه نداشته. binary search هیچ راهی ندارد که بفهمد ورودی‌اش مرتب نیست — بررسی کردنش خودش O(n) است و کلِ صرفه‌جویی را از بین می‌برد. پس مرتب‌بودن یک قرارداد است که کدِ دیگری باید نگهش دارد، و در بازبینیِ کد باید صریح دنبالش بگردی.

۶. مرتب کردن چقدر خرج دارد و از کجا به‌صرفه می‌شود#

حالا سؤالِ مهندسیِ فصل: یک بار مرتب کردن گران است. از چند پرسش به بعد جبران می‌شود؟

def merge_sort_comparisons(values):
    """merge sort فصلِ ۴، فقط برای شمردنِ هزینهٔ مرتب‌کردن."""
    comparisons = 0

    def go(vals):
        nonlocal comparisons
        if len(vals) <= 1:
            return vals
        mid = len(vals) // 2
        left, right = go(vals[:mid]), go(vals[mid:])
        out = []
        i = j = 0
        while i < len(left) and j < len(right):
            comparisons += 1
            if left[i] <= right[j]:
                out.append(left[i])
                i += 1
            else:
                out.append(right[j])
                j += 1
        out.extend(left[i:])
        out.extend(right[j:])
        return out

    go(list(values))
    return comparisons


rng = random.Random(SEED)
N = 8_000
pool = rng.sample(range(10 * N), N)
sort_cost = merge_sort_comparisons(pool)
in_order = sorted(pool)
targets = [rng.choice(in_order) for _ in range(200)]
per_linear = sum(linear_search(pool, t)[1] for t in targets) / len(targets)
per_binary = sum(binary_search(in_order, t)[1] for t in targets) / len(targets)
print(f"n = {N:,}")
print(f"  هزینهٔ یک بار مرتب کردن : {sort_cost:>9,} مقایسه")
print(f"  هر جست‌وجوی خطی        : {per_linear:>9,.1f} گام")
print(f"  هر binary search       : {per_binary:>9,.1f} گام")
n = 8,000
  هزینهٔ یک بار مرتب کردن :    93,580 مقایسه
  هر جست‌وجوی خطی        :   3,997.2 گام
  هر binary search       :      12.0 گام
print(f"{'q':>8}{'خطی':>16}{'مرتب + binary':>22}{'برنده':>20}")
for q in (1, 5, 10, 20, 25, 50, 100):
    plain = q * per_linear
    smart = sort_cost + q * per_binary
    print(f"{q:>8,}{plain:>16,.0f}{smart:>22,.0f}"
          f"{('خطی' if plain < smart else 'مرتب + binary'):>20}")

break_even = 1
while break_even * per_linear < sort_cost + break_even * per_binary:
    break_even += 1
print("\nنقطهٔ سربه‌سر: از q =", break_even, "به بعد، مرتب کردن به‌صرفه است.")
       q             خطی         مرتب + binary               برنده
       1           3,997                93,592                 خطی
       5          19,986                93,640                 خطی
      10          39,972                93,700                 خطی
      20          79,945                93,821                 خطی
      25          99,931                93,881       مرتب + binary
      50         199,862                94,182       مرتب + binary
     100         399,723                94,783       مرتب + binary

نقطهٔ سربه‌سر: از q = 24 به بعد، مرتب کردن به‌صرفه است.

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

این همان نقطهٔ تقاطعِ ترمِ ۱ فصلِ ۹ است، این بار با q به‌جای n. و مثلِ آن‌جا، عددش به مسئلهٔ خودت بند است، نه به الگوریتم: با بزرگ‌تر شدنِ n هم هزینهٔ مرتب کردن بالا می‌رود و هم سودِ هر جست‌وجو، و این عدد آرام‌آرام جابه‌جا می‌شود.

✅ چک کن: N را به 1_000 تغییر بده و کلِ بخشِ ۶ را دوباره بگیر. نقطهٔ سربه‌سر باید کمی پایین بیاید و نزدیکِ 19 دربیاید — چون با کوچک شدنِ n هم هزینهٔ مرتب کردن پایین می‌آید و هم سودِ هر جست‌وجو. اگر عددت اصلاً تکان نخورد، احتمالاً in_order را به‌روز نکرده‌ای و binary search روی فهرستِ قدیمی می‌گردد.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ جست‌وجوی خطی روی فهرستِ بی‌ترتیب در برابرِ binary search روی همان داده پس از مرتب شدن، با جوابِ تأییدشدهٔ برابر — و هزینهٔ مرتب کردن با همان واحد (مقایسه) شمرده شد تا جمع کردنشان معنا داشته باشد. در کدام بازهٔ n؟ ۱٬۰۰۰ تا ۸٬۰۰۰ برای جدولِ گام، و n = 8,000 با ۲۰۰ پرسشِ نمونه برای نقطهٔ سربه‌سر. با چند تکرار، و کمینه یا میانگین؟ یک اجرا؛ همه‌چیزِ این فصل شمارش است و قطعی، و پرسش‌های نمونه هم با SEED ثابت‌اند.

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

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

کلمه تلفظ به حروف فارسی یعنی چه
binary search باینری سرچ یافتن با نصف کردنِ پیاپیِ بازهٔ جست‌وجو
off-by-one آف‌بای‌وان خطای یکی‌کم‌یکی‌زیاد در مرز یا شرطِ حلقه
bisect بایسکت ماژولِ استانداردِ پایتون برای جست‌وجو و درج در فهرستِ مرتب
break-even point بریک‌ایوِن پوینت تعدادِ پرسشی که از آن به بعد سرمایه‌گذاریِ اولیه جبران می‌شود

تمرین‌ها

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

در فصل بعد#

سه الگوریتمِ مرتب‌سازی نوشتیم و در کارِ واقعی هیچ‌کدامشان را نمی‌نویسی — sorted را صدا می‌زنی. فصلِ بعد می‌گوید چرا، و جوابش آن چیزی نیست که فکر می‌کنی.

مقایسه‌های sorted را می‌شماریم: در n = 80,000 عددِ 1,201,201 درمی‌آید و merge sort ما 1,203,739 — تقریباً یکی. یعنی الگوریتمش بهتر نیست. با این حال روی همان داده حدودِ سیزده برابر سریع‌تر است.

و یک کارِ دیگر هم می‌کند که ما بلد نبودیم: روی ورودیِ از پیش مرتب، همان 1,201,201 مقایسه به 79,999 می‌افتد و ستونِ نسبت 2.00 می‌شود.

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

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