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

فصل ۸ از ۹

پیشرفت ترم
۰٪

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

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

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

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

دستگاهی که یک نوارِ درهم را مرتب می‌کند و بخش‌های از قبل مرتبِ نوار را دست‌نخورده رد می‌کند

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

  • با key= بر اساسِ هر چیزی که بخواهی مرتب کنی
  • بگویی پایداری چیست و مرتب‌سازیِ چندکلیدی را با آن بنویسی
  • مقایسه‌های خودِ sorted را بشماری و رفتارش را روی ورودی‌های مختلف نشان بدهی
  • بگویی چرا در اندازه‌های کوچک، الگوریتمِ «بدتر» انتخابِ درست است

قبل از شروع#

از فصلِ ۳: insertion sort و اینکه روی ورودیِ از پیش مرتب خطی می‌شود.

از فصلِ ۴: merge sort و شمارشِ مقایسه‌هایش — کدش این‌جا فشرده تکرار می‌شود.

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

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

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

۱. key=: بر اساسِ چه چیزی مرتب شود#

sorted به‌طورِ پیش‌فرض خودِ عضوها را مقایسه می‌کند. با key= می‌گویی از هر عضو چه چیزی را برای مقایسه بردارد.

people = [("سارا", 1997, "شیراز"), ("رضا", 2001, "تبریز"), ("نیما", 1997, "رشت"),
          ("مینا", 2004, "یزد"), ("کیان", 2001, "اهواز"), ("دارا", 1997, "کرمان")]

print("بر اساسِ سالِ تولد:")
for row in sorted(people, key=lambda p: p[1]):
    print("  ", row)

print("\nبر اساسِ طولِ نام، بعد سالِ تولد:")
for row in sorted(people, key=lambda p: (len(p[0]), p[1])):
    print("  ", row)
بر اساسِ سالِ تولد:
   ('سارا', 1997, 'شیراز')
   ('نیما', 1997, 'رشت')
   ('دارا', 1997, 'کرمان')
   ('رضا', 2001, 'تبریز')
   ('کیان', 2001, 'اهواز')
   ('مینا', 2004, 'یزد')

بر اساسِ طولِ نام، بعد سالِ تولد:
   ('رضا', 2001, 'تبریز')
   ('سارا', 1997, 'شیراز')
   ('نیما', 1997, 'رشت')
   ('دارا', 1997, 'کرمان')
   ('کیان', 2001, 'اهواز')
   ('مینا', 2004, 'یزد')

key برای هر عضو دقیقاً یک بار صدا زده می‌شود، نه برای هر مقایسه. پس حتی اگر تابعِ key گران باشد، هزینه‌اش O(n) است و به n log n مقایسه اضافه نمی‌شود.

و وقتی key یک tuple برمی‌گرداند، مقایسه از چپ به راست انجام می‌شود: اول عضوِ اول، و فقط اگر برابر بودند، عضوِ دوم. این کلِ مرتب‌سازیِ چندکلیدی است.

۲. پایداری: چیزی که تعریفش کسل‌کننده است و کاربردش نه#

sorted پایدار است، یعنی عضوهایی که کلیدشان برابر است، ترتیبِ اولیه‌شان را نگه می‌دارند.

by_year = sorted(people, key=lambda p: p[1])
print("ترتیبِ ورودیِ متولدانِ ۱۹۹۷:", [p[0] for p in people if p[1] == 1997])
print("ترتیبِ خروجیِ متولدانِ ۱۹۹۷:", [p[0] for p in by_year if p[1] == 1997])

two_passes = sorted(sorted(people, key=lambda p: p[2]), key=lambda p: p[1])
one_key = sorted(people, key=lambda p: (p[1], p[2]))
print("\nدو پاس و کلیدِ مرکب یک جواب می‌دهند؟", two_passes == one_key)
for row in one_key:
    print("  ", row)
ترتیبِ ورودیِ متولدانِ ۱۹۹۷: ['سارا', 'نیما', 'دارا']
ترتیبِ خروجیِ متولدانِ ۱۹۹۷: ['سارا', 'نیما', 'دارا']

دو پاس و کلیدِ مرکب یک جواب می‌دهند؟ True
   ('نیما', 1997, 'رشت')
   ('سارا', 1997, 'شیراز')
   ('دارا', 1997, 'کرمان')
   ('کیان', 2001, 'اهواز')
   ('رضا', 2001, 'تبریز')
   ('مینا', 2004, 'یزد')

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

در فصلِ ۴ یک ✅ چک کن بود که گفت <= را به < تغییر بده و «هیچ چیزی عوض نمی‌شود». این‌جا بدهی‌اش پرداخت می‌شود: آن یک نویسه دقیقاً همان چیزی است که merge sort را پایدار نگه می‌دارد. با <، وقتی دو عضو برابر باشند، عضوِ سمتِ راست اول برداشته می‌شود و ترتیبِ اولیه به هم می‌خورد. روی داده‌ای که عضوِ برابر ندارد هیچ اثری ندارد و برای همین موقعِ آزمون دیده نمی‌شود.

try:
    sorted(people, lambda p: p[1])
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
TypeError: sorted expected 1 argument, got 2

🔧 اگر کار نکرد: key باید با نام داده شود. پیام کمی گمراه‌کننده است — می‌گوید «یک آرگومان انتظار داشتم، دو تا گرفتم» — و دلیلش این است که sorted فقط یک آرگومانِ بی‌نام قبول می‌کند و بقیه اجباراً نام‌دارند. sorted(people, key=...) درست است و sorted(people, ...) غلط. همین قاعده برای list.sort و min و max هم برقرار است.

۳. مقایسه‌های خودِ sorted را بشمار#

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

و این تنها جای کلِ دوره است که یک class می‌نویسیم، فقط برای همین یک کار. پایتون برای مقایسهٔ دو چیز با < سراغِ __lt__ِ آن‌ها می‌رود — همان قاعده‌ای که ترمِ ۳ فصلِ ۶ برای __hash__ و __eq__ گفت. پس اگر __lt__ را خودمان بنویسیم، هر مقایسه‌ای که sorted انجام می‌دهد از دستِ ما رد می‌شود و می‌شود شمردش. class این‌جا فقط یک ظرف است، __init__ مقدارِ اولیه را می‌گیرد، و self یعنی «همان چیزی که دارد مقایسه می‌شود». فعلاً همین‌قدر بدان؛ این دوره جای دیگری class نمی‌سازد.

و یک کلمهٔ دیگر هم در همان کد هست: global. خواهرِ nonlocalِ فصلِ ۱ است و کارش همان است، یک پله بالاتر: nonlocal می‌گوید «متغیرِ تابعِ بیرونی را می‌خواهم عوض کنم» و global COMPARISONS می‌گوید «متغیرِ بالاترین سطحِ نوت‌بوک را می‌خواهم عوض کنم». بدونِ آن، COMPARISONS += 1 یک متغیرِ محلیِ تازه می‌سازد و شمارنده هیچ‌وقت بالا نمی‌رود. این‌جا لازمش داریم چون __lt__ تابعی است که sorted صدایش می‌زند، نه ما — پس هیچ راهی برای پس دادنِ شمارش از طریقِ خروجی‌اش نداریم.

COMPARISONS = 0


class Counted:
    """عددی که هر بار مقایسه‌شدنش را می‌شمارد — هیچ کارِ دیگری نمی‌کند."""

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        global COMPARISONS
        COMPARISONS += 1
        return self.value < other.value


def sort_comparisons(values):
    """تعدادِ مقایسه‌ای که خودِ sorted روی این ورودی انجام می‌دهد."""
    global COMPARISONS
    boxed = [Counted(v) for v in values]   # ساختنشان هیچ مقایسه‌ای ندارد
    COMPARISONS = 0
    sorted(boxed)
    return COMPARISONS


print("مقایسه‌های sorted روی ۸ عددِ درهم:", sort_comparisons([29, 10, 14, 37, 13, 25, 11, 18]))
print("مقایسه‌های sorted روی ۸ عددِ مرتب:", sort_comparisons(sorted([29, 10, 14, 37, 13, 25, 11, 18])))
مقایسه‌های sorted روی ۸ عددِ درهم: 20
مقایسه‌های sorted روی ۸ عددِ مرتب: 7

بیست در برابرِ هفت، روی همان هشت عدد. sorted فهمید که ورودیِ دوم از قبل مرتب است — با هفت مقایسه، یعنی n - 1، یعنی فقط یک بار پشتِ سرِ هم چک کردنِ همسایه‌ها.

🤔 اول حدس بزن: برای هر سه حالتِ زیر ستونِ نسبت را بنویس: ورودیِ تصادفی، ورودیِ از پیش مرتب، و ورودیِ کاملاً وارونه. سه عدد، بعد جدول را ببین. (وارونه سخت‌ترینشان است.)

rng = random.Random(SEED)
LADDER = [10_000, 20_000, 40_000, 80_000]
shuffled = {n: rng.sample(range(10 * n), n) for n in LADDER}
climbing = {n: sorted(shuffled[n]) for n in LADDER}
falling = {n: sorted(shuffled[n], reverse=True) for n in LADDER}

print("— ورودیِ تصادفی")
table([(n, sort_comparisons(shuffled[n])) for n in LADDER], "مقایسه", ",d")
print("\n— ورودیِ از پیش مرتب")
table([(n, sort_comparisons(climbing[n])) for n in LADDER], "مقایسه", ",d")
print("\n— ورودیِ کاملاً وارونه")
table([(n, sort_comparisons(falling[n])) for n in LADDER], "مقایسه", ",d")
— ورودیِ تصادفی
         n            مقایسه     نسبت به سطر قبل
    10,000           120,122                   —
    20,000           260,362                2.17
    40,000           560,631                2.15
    80,000         1,201,201                2.14

— ورودیِ از پیش مرتب
         n            مقایسه     نسبت به سطر قبل
    10,000             9,999                   —
    20,000            19,999                2.00
    40,000            39,999                2.00
    80,000            79,999                2.00

— ورودیِ کاملاً وارونه
         n            مقایسه     نسبت به سطر قبل
    10,000             9,999                   —
    20,000            19,999                2.00
    40,000            39,999                2.00
    80,000            79,999                2.00

جدولِ اول 2.15 است — همان O(n log n) فصلِ ۴. ولی دو جدولِ دیگر 2.00 می‌دهند و عددشان دقیقاً n - 1 است: O(n).

و جدولِ سوم غافلگیرکننده‌تر از دومی است. ورودیِ وارونه بدترین ورودیِ ممکن به‌نظر می‌رسد و در insertion sort فصلِ ۳ دقیقاً همان بود. ولی sorted دنبالهٔ نزولی را هم به‌عنوان یک بخشِ مرتب می‌شناسد — با n - 1 مقایسه پیدایش می‌کند و بعد فقط وارونه‌اش می‌کند.

۴. و دادهٔ واقعی: نیمی مرتب#

دادهٔ واقعی نه کاملاً تصادفی است نه کاملاً مرتب. معمولاً تکه‌تکه مرتب است — یک سیاههٔ زمانی که چند بار به هم ریخته، یا فهرستی که به آن اضافه شده.

🤔 اول حدس بزن: نیمهٔ اول مرتب و نیمهٔ دوم درهم. بنویس تعدادِ مقایسه در n = 80,000 به کدام‌یک از دو عددِ بخشِ ۳ نزدیک‌تر می‌شود — 1,201,201 یا 79,999 — و آیا انتظار داری دقیقاً وسطشان بیفتد.

def half_sorted(n):
    """نیمهٔ اول مرتب، نیمهٔ دوم درهم — چیزی که در دادهٔ واقعی زیاد پیش می‌آید."""
    base = shuffled[n]
    return sorted(base[:n // 2]) + base[n // 2:]


print("— نیمی مرتب، نیمی درهم")
table([(n, sort_comparisons(half_sorted(n))) for n in LADDER], "مقایسه", ",d")
print()
n = 80_000
print(f"در n = {n:,}:")
print(f"  تصادفی    : {sort_comparisons(shuffled[n]):>9,} مقایسه")
print(f"  نیمی مرتب : {sort_comparisons(half_sorted(n)):>9,} مقایسه")
print(f"  کاملاً مرتب: {sort_comparisons(climbing[n]):>9,} مقایسه")
— نیمی مرتب، نیمی درهم
         n            مقایسه     نسبت به سطر قبل
    10,000            70,039                   —
    20,000           150,234                2.15
    40,000           320,340                2.13
    80,000           680,675                2.12

در n = 80,000:
  تصادفی    : 1,201,201 مقایسه
  نیمی مرتب :   680,675 مقایسه
  کاملاً مرتب:    79,999 مقایسه

نیمی از داده که از قبل مرتب باشد، بیش از پانصد هزار مقایسه را حذف می‌کند — 680,675 در برابرِ 1,201,201. این هدیه‌ای است که merge sort ما اصلاً نمی‌گیرد، چون کورکورانه همه‌چیز را از وسط می‌شکند، حتی تکه‌ای که از قبل مرتب است.

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

۵. پس چرا سریع‌تر است؟#

حالا سؤالِ اصلیِ فصل. مقایسه‌های sorted و merge sort ما را روی همان داده کنارِ هم می‌گذاریم.

def merge_sort(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

    return go(list(values)), comparisons


data = shuffled[80_000]
mine, mine_cmp = merge_sort(data)
print("جوابِ دو نسخه یکی است؟", mine == sorted(data))
print(f"مقایسهٔ merge sortِ ما : {mine_cmp:>9,}")
print(f"مقایسهٔ sorted        : {sort_comparisons(data):>9,}")
جوابِ دو نسخه یکی است؟ True
مقایسهٔ merge sortِ ما : 1,203,739
مقایسهٔ sorted        : 1,201,201

اختلافشان حدودِ دو در هزار است. روی ورودیِ تصادفی، sorted هیچ کارِ زیرکانه‌تری نمی‌کند؛ دقیقاً همان تعداد مقایسه را انجام می‌دهد.

ours = clock(lambda: merge_sort(data), repeat=2)
theirs = clock(lambda: sorted(data), repeat=3)
print(f"n = 80,000")
print(f"  merge sortِ ما: {1000 * ours:>8,.1f} ms")
print(f"  sorted        : {1000 * theirs:>8,.1f} ms")
print(f"  نسبت          : {ours / theirs:>8,.0f} برابر")
n = 80,000
  merge sortِ ما:    212.9 ms
  sorted        :     16.2 ms
  نسبت          :       13 برابر

همان تعداد مقایسه، سیزده برابر زمان. پس تفاوت در الگوریتم نیست، در ثابت است: هر مقایسهٔ ما یک دورِ حلقهٔ پایتون است و هر مقایسهٔ sorted چند دستورِ ماشین در کدِ C.

این دقیقاً همان ثابتِ پنهانی است که ترمِ ۱ فصلِ ۹ ساخت و Big-O عمداً نمی‌بیندش. و نتیجهٔ عملی‌اش یک قاعده است: مرتب‌سازی را ننویس، sorted را صدا بزن — نه چون الگوریتمت بد است، چون حلقه‌ات در پایتون می‌چرخد.

پس این چهار فصل بی‌فایده بود؟ برعکس: بدونِ آن‌ها نمی‌توانستی این جدول را بخوانی. جدولِ بالا فقط برای کسی معنا دارد که بداند «همان تعداد مقایسه» یعنی چه و چرا اهمیت دارد.

۶. و کجا sorted هم الگوریتم را عوض می‌کند#

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

🤔 اول حدس بزن: insertion sort که O(n²) است در برابرِ merge sort که O(n log n) است، در nهای ۸ تا ۲۵۶. یک عدد بنویس: نقطهٔ تقاطع کجاست؟ و اگر فکر می‌کنی تقاطعی در کار نیست، همان را بنویس — ترمِ ۱ فصلِ ۹ می‌گوید چرا حتماً هست.

def insertion_sort(values):
    a = list(values)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a


SMALL = [8, 16, 32, 64, 128, 256]
tiny = {n: rng.sample(range(10 * n), n) for n in SMALL}
print("هر دو یک جواب می‌دهند؟",
      all(insertion_sort(tiny[n]) == merge_sort(tiny[n])[0] for n in SMALL))
print()
print(f"{'n':>6}{'insertion (µs)':>18}{'merge (µs)':>14}{'برنده':>14}")
for n in SMALL:
    a = 1e6 * clock(lambda v=tiny[n]: insertion_sort(v), repeat=200)
    b = 1e6 * clock(lambda v=tiny[n]: merge_sort(v), repeat=200)
    print(f"{n:>6}{a:>18,.1f}{b:>14,.1f}{('insertion' if a < b else 'merge'):>14}")
هر دو یک جواب می‌دهند؟ True

     n    insertion (µs)    merge (µs)         برنده
     8               1.5           5.7     insertion
    16               4.7          12.8     insertion
    32              17.9          29.5     insertion
    64              57.8          69.0     insertion
   128             242.1         161.2         merge
   256             762.1         315.1         merge

روی این ماشین، نقطهٔ تقاطع بینِ 64 و 128 افتاد. زیرِ آن، الگوریتمِ O(n²) — که فصلِ ۳ «کند» صدایش زدیم — از الگوریتمِ O(n log n) سریع‌تر است، چون سربارِ شکستن و ساختنِ list تازه در تکه‌های کوچک بر همه‌چیز غالب است. عددِ تو ممکن است جابه‌جا شود؛ آنچه جابه‌جا نمی‌شود وجودِ تقاطع است.

و همین قاعده در خودِ sorted هم پیاده شده: روی تکه‌های کوچک سراغِ شکستنِ بیشتر نمی‌رود و از insertion sort استفاده می‌کند. این تصمیم دقیقاً همان چیزی است که ترمِ ۱ فصلِ ۹ با نقطهٔ تقاطعش نشان داد — و حالا در کدی می‌بینی‌اش که هر روز صدایش می‌زنی.

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

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

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

کلمه تلفظ به حروف فارسی یعنی چه
stable sort استیبل سورت مرتب‌سازی‌ای که ترتیبِ عضوهای هم‌کلید را نگه می‌دارد
key کی تابعی که می‌گوید از هر عضو چه چیزی مقایسه شود
run رَن بخشی از داده که از قبل مرتب است
multi-key sort مولتی‌کی سورت مرتب‌سازی بر اساسِ چند کلید، به ترتیبِ اولویت
global گلوبال اعلامِ اینکه یک تابع می‌خواهد متغیرِ بالاترین سطح را عوض کند، نه فقط بخواند

تمرین‌ها

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

در فصل بعد#

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

فصلِ آخر همه‌شان را روی یک مسئلهٔ واقعی می‌گذارد. یک انبارِ رکورد داریم و باید در آن دنبالِ کد بگردیم. سه راه می‌سازیم — جست‌وجوی خطی، مرتب کردن و bisect، و یک dict — و برای هر سه جدول می‌گیریم. در n = 16,000 میانگینِ گامِ روشِ اول 7,807.5 است و روشِ دوم 13.06.

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

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

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