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

فصل ۵ از ۹

پیشرفت ترم
۰٪

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

merge sort سریع بود ولی برای هر ادغام یک list تازه می‌ساخت. این فصل الگوریتمی می‌سازد که همان مرتبه را در جای خودِ داده می‌گیرد — بدونِ ساختنِ حتی یک فهرستِ کمکی.

و بعد خرابش می‌کنیم. روی فهرستی که از قبل مرتب است، همین کد به RecursionError می‌خورد. وقتی آن را با یک stack صریح درست می‌کنیم، عددِ واقعی بیرون می‌آید: در n = 2,000 تعدادِ مقایسه 1,999,000 است و ستونِ نسبت 4.00 — یعنی دقیقاً همان selection sort فصلِ ۳. بعد با یک خط تغییر، همان عدد روی همان ورودی به حدودِ 24,000 برمی‌گردد.

میله‌ای که یک دستهٔ کارت را حولِ یک کارتِ نشانه‌گذاری‌شده به دو گروهِ کوچک‌تر و بزرگ‌تر می‌راند

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

  • افرازِ یک فهرست حولِ یک pivot را با دست انجام بدهی
  • quicksort را in-place بنویسی و درستی‌اش را ثابت کنی
  • بدترین حالتش را بسازی و با شمارش نشانش بدهی
  • بگویی pivot تصادفی دقیقاً چه چیزی را عوض می‌کند و چه چیزی را نه

قبل از شروع#

از فصلِ ۱: بازنویسیِ یک recursion به حلقه — بخشِ ۴ این فصل واقعاً به آن احتیاج پیدا می‌کند.

از ترمِ ۳ فصلِ ۴: ورودیِ خصمانه، و اینکه بدترین حالتِ یک ساختار وقتی خطرناک است که کسِ دیگری ورودی را انتخاب کند. quicksort نمونهٔ کلاسیکِ همین حرف است.

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

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

۱. افراز، با دست#

ایدهٔ quicksort از طرفِ دیگرِ «تقسیم و حل» می‌آید. merge sort کورکورانه از وسط می‌شکست و کارِ سخت را در ادغام انجام می‌داد. quicksort برعکس است: کارِ سخت را در خودِ شکستن انجام می‌دهد، و بعد هیچ ادغامی لازم نیست.

یک عضو را pivot می‌گیریم و فهرست را طوری می‌چینیم که هر چیزِ کوچک‌ترش سمتِ چپش باشد و هر چیزِ بزرگ‌ترش سمتِ راستش. آن‌وقت pivot سرِ جای نهایی‌اش است و دو طرفش دو مسئلهٔ مستقل‌اند.

def partition(a, lo, hi, stats):
    """همهٔ عضوهای کوچک‌تر از a[lo] را سمتِ چپ می‌برد و جای نهاییِ pivot را برمی‌گرداند."""
    pivot = a[lo]
    i = lo + 1
    for j in range(lo + 1, hi + 1):
        stats["comparisons"] += 1
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[lo], a[i - 1] = a[i - 1], a[lo]    # pivot به جای نهایی‌اش می‌رود
    return i - 1


demo = [29, 10, 14, 37, 13, 25, 11, 18]
box = {"comparisons": 0}
work = list(demo)
place = partition(work, 0, len(work) - 1, box)
print("ورودی        :", demo)
print("pivot        :", demo[0])
print("بعد از افراز :", work)
print("جای نهاییِ pivot:", place, "· مقایسه:", box["comparisons"])
print("سمتِ چپ همه کوچک‌ترند؟", all(x < demo[0] for x in work[:place]))
print("سمتِ راست همه بزرگ‌ترند؟", all(x >= demo[0] for x in work[place + 1:]))
ورودی        : [29, 10, 14, 37, 13, 25, 11, 18]
pivot        : 29
بعد از افراز : [18, 10, 14, 13, 25, 11, 29, 37]
جای نهاییِ pivot: 6 · مقایسه: 7
سمتِ چپ همه کوچک‌ترند؟ True
سمتِ راست همه بزرگ‌ترند؟ True

هشت عضو، هفت مقایسه، و هیچ فهرستِ تازه‌ای ساخته نشد — فقط عضوها داخلِ همان list جابه‌جا شدند. اسمِ این کار in-place است.

ولی به خروجی خوب نگاه کن: دو طرفِ pivot مرتب نیستند، فقط تفکیک شده‌اند. و همین کافی است، چون هر طرف را می‌شود با همان روش حل کرد.

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

۲. quicksort روی ورودیِ تصادفی#

def quicksort(values):
    """نسخه‌ای با recursion، in-place روی یک کپی."""
    a = list(values)
    stats = {"comparisons": 0, "depth": 0}

    def go(lo, hi, depth):
        stats["depth"] = max(stats["depth"], depth)
        if lo >= hi:                     # حالتِ پایه: صفر یا یک عضو
            return
        p = partition(a, lo, hi, stats)
        go(lo, p - 1, depth + 1)
        go(p + 1, hi, depth + 1)

    go(0, len(a) - 1, 1)
    return a, stats


rng = random.Random(SEED)
BIG = [1_000, 2_000, 4_000, 8_000]
shuffled = {n: rng.sample(range(10 * n), n) for n in BIG}
out, stats = quicksort(shuffled[1_000])
print("با sorted یکی است؟", out == sorted(shuffled[1_000]))
print("مقایسه:", stats["comparisons"], "· عمق:", stats["depth"])
با sorted یکی است؟ True
مقایسه: 10150 · عمق: 20

🤔 اول حدس بزن: ستونِ نسبتِ مقایسه‌ها چه عددی می‌دهد؟ و عمق چطور؟ دو عدد بنویس، بعد جدول را ببین.

print("— ورودیِ تصادفی: مقایسه")
table([(n, quicksort(shuffled[n])[1]["comparisons"]) for n in BIG], "مقایسه", ",d")
print("\n— ورودیِ تصادفی: عمقِ recursion")
table([(n, quicksort(shuffled[n])[1]["depth"]) for n in BIG], "عمق", ",d")
— ورودیِ تصادفی: مقایسه
         n            مقایسه     نسبت به سطر قبل
     1,000            10,150                   —
     2,000            26,066                2.57
     4,000            55,429                2.13
     8,000           124,001                2.24

— ورودیِ تصادفی: عمقِ recursion
         n               عمق     نسبت به سطر قبل
     1,000                20                   —
     2,000                25                1.25
     4,000                26                1.04
     8,000                31                1.19

نسبت‌ها حولِ 2.2 — همان امضای O(n log n) فصلِ ۴. عددِ مطلقشان هم نزدیکِ merge sort است: در n = 8,000 عددِ 124,001 در برابرِ 93,704.

ولی ستونِ عمق فرقِ مهمی با فصلِ ۴ دارد. آن‌جا عمق دقیقاً log₂ n بود و از 11 به 14 رفت. این‌جا از 20 به 31 می‌رود — حدودِ دو برابرِ log₂ n، و لرزان. دلیلش همان چیزی است که در بخشِ ۱ دیدیم: merge sort همیشه دقیقاً از وسط می‌شکند و quicksort هر جا که pivot بیفتد.

و همین «هر جا که بیفتد» جای زخم است.

۳. بدترین حالت را بساز#

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

و ساختنِ این حالت هیچ زحمتی ندارد: کد ما همیشه عضوِ اول را pivot می‌گیرد، پس کافی است فهرست از قبل مرتب باشد.

climbing = sorted(shuffled[2_000])
print("ورودی از پیش مرتب است؟", climbing == sorted(climbing))
try:
    quicksort(climbing)
except RecursionError as err:
    print(f"{type(err).__name__}: {err}")
ورودی از پیش مرتب است؟ True
RecursionError: maximum recursion depth exceeded

🔧 اگر کار نکرد: این خطا این‌جا یک علامت است، نه یک باگ. عمقِ recursion برابرِ n شده و از سقفِ پایتون رد کرده. وسوسهٔ اول این است که سقف را بالا ببری — و آن دقیقاً کارِ غلط است، چون مسئله عمق نیست، مسئله این است که تقسیم اصلاً انجام نمی‌شود. سقف را که بالا ببری، برنامه به‌جای یک استثنای تمیز، ساعت‌ها کار می‌کند یا نشست را می‌کشد.

راهِ درست، برداشتنِ recursion است. فصلِ ۱ گفت هر recursion را می‌شود به حلقه برگرداند؛ این‌جا جایی است که واقعاً باید این کار را بکنی.

۴. همان الگوریتم، با یک stack صریح#

پایتون فراخوانی‌های تمام‌نشده را روی call stack نگه می‌داشت. ما همان کار را با یک list انجام می‌دهیم — همان stackی که ترمِ ۲ فصلِ ۷ ساخت، با همان انضباطِ LIFO. به‌جای فراخوانی، بازه‌های کارنکرده را در آن می‌ریزیم.

def quicksort_stack(values, pick=None):
    """همان الگوریتم، با یک stack صریح به‌جای call stack."""
    a = list(values)
    stats = {"comparisons": 0, "max_todo": 0}
    todo = [(0, len(a) - 1)]
    while todo:
        stats["max_todo"] = max(stats["max_todo"], len(todo))
        lo, hi = todo.pop()
        if lo >= hi:
            continue
        if pick is not None:                 # pivot را عوض کن
            k = pick(lo, hi)
            a[lo], a[k] = a[k], a[lo]
        p = partition(a, lo, hi, stats)
        todo.append((lo, p - 1))
        todo.append((p + 1, hi))
    return a, stats


check = shuffled[1_000]
one = quicksort(check)
two = quicksort_stack(check)
print("دو نسخه یک جواب می‌دهند؟", one[0] == two[0] == sorted(check))
print("و یک تعداد مقایسه؟",
      one[1]["comparisons"] == two[1]["comparisons"], "·",
      two[1]["comparisons"])
print("روی ورودیِ از پیش مرتب هم کار می‌کند؟",
      quicksort_stack(climbing)[0] == climbing)
دو نسخه یک جواب می‌دهند؟ True
و یک تعداد مقایسه؟ True · 10150
روی ورودیِ از پیش مرتب هم کار می‌کند؟ True

همان جواب، همان تعدادِ مقایسه، و این بار روی ورودیِ مرتب هم تمام می‌شود. حالا می‌شود بدترین حالت را واقعاً اندازه گرفت.

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

SORTED_LADDER = [250, 500, 1_000, 2_000]
climb = {n: list(range(n)) for n in SORTED_LADDER}
print("— ورودیِ از پیش مرتب، pivot = عضوِ اول")
table([(n, quicksort_stack(climb[n])[1]["comparisons"]) for n in SORTED_LADDER],
      "مقایسه", ",d")
— ورودیِ از پیش مرتب، pivot = عضوِ اول
         n            مقایسه     نسبت به سطر قبل
       250            31,125                   —
       500           124,750                4.01
     1,000           499,500                4.00
     2,000         1,999,000                4.00

4.00 — یعنی O(n²). و عددهایش سطر به سطر دقیقاً همان عددهای selection sort فصلِ ۳ هستند: 31,125، 124,750، 499,500، 1,999,000.

این تصادف نیست. وقتی هر افراز فقط یک عضو را جدا می‌کند، مجموعِ مقایسه‌ها (n-1) + (n-2) + … + 1 می‌شود — همان جمعی که selection sort هم می‌سازد. الگوریتمی که اسمش quick است، روی مرتب‌ترین ورودیِ ممکن، به سادگی‌ترین الگوریتمِ ممکن تبدیل شد.

۵. یک خط تغییر#

اشکال در الگوریتم نیست، در قاعدهٔ انتخابِ pivot است. «همیشه عضوِ اول» یک قاعدهٔ ثابت است و هر قاعدهٔ ثابتی یک ورودیِ بد دارد. پس pivot را تصادفی برمی‌داریم.

🤔 اول حدس بزن: همان ورودیِ از پیش مرتب، فقط با pivot تصادفی. ستونِ نسبت را بنویس — و یک عددِ دوم هم بنویس: در n = 2,000 مقایسه‌ها از 1,999,000 به چند می‌رسند؟ مرتبه و عدد دو حدسِ متفاوت‌اند و هر دو را می‌خواهیم.

print("— همان ورودیِ مرتب، pivot تصادفی")
picker = random.Random(SEED)
table([(n, quicksort_stack(climb[n], lambda lo, hi: picker.randrange(lo, hi + 1))[1]["comparisons"])
       for n in SORTED_LADDER], "مقایسه", ",d")
— همان ورودیِ مرتب، pivot تصادفی
         n            مقایسه     نسبت به سطر قبل
       250             2,653                   —
       500             4,571                1.72
     1,000            10,032                2.19
     2,000            23,938                2.39

1,999,000 به 23,938 رسید — روی همان ورودی، با همان کدِ افراز. و ستونِ نسبت از 4.00 به حدودِ 2.2 برگشت: O(n log n).

picker2 = random.Random(SEED)
print("— ورودیِ مرتبِ بزرگ‌تر، pivot تصادفی")
table([(n, quicksort_stack(list(range(n)), lambda lo, hi: picker2.randrange(lo, hi + 1))[1]["comparisons"])
       for n in BIG], "مقایسه", ",d")
— ورودیِ مرتبِ بزرگ‌تر، pivot تصادفی
         n            مقایسه     نسبت به سطر قبل
     1,000            11,951                   —
     2,000            24,661                2.06
     4,000            55,531                2.25
     8,000           115,750                2.08

⚠️ مواظب باش: pivot تصادفی بدترین حالت را حذف نمی‌کند؛ فقط کاری می‌کند که کسی نتواند آن را سفارش بدهد. با بدشانسیِ محض هنوز ممکن است هر بار بدترین pivot انتخاب شود — احتمالش فقط آن‌قدر کوچک است که به آن فکر نمی‌کنیم.

و این دقیقاً همان پادزهری است که ترمِ ۳ فصلِ ۴ برای hash table دید: آن‌جا هم مسئله این بود که مهاجم قاعدهٔ ثابت را می‌داند، و راهِ حل تصادفی کردنِ همان قاعده بود. دو ساختارِ کاملاً متفاوت، یک الگوی دفاعیِ واحد.

۶. in-place رایگان نیست#

quicksort هیچ فهرستِ تازه‌ای برای داده نمی‌سازد. ولی بازه‌های کارنکرده جایی باید بمانند — روی call stack یا در todo. و آن جا هم حافظه است.

🤔 اول حدس بزن: بیشترین اندازهٔ todo را برای سه حالت حدس بزن: ورودیِ مرتب با pivot اول، همان ورودی با pivot تصادفی، و ورودیِ تصادفی. برای هر سه بنویس با هشت برابر شدنِ n چند برابر می‌شوند — و مخصوصاً بنویس آیا انتظار داری هر سه یک شکل باشند.

picker3 = random.Random(SEED)
print("— بیشترین اندازهٔ stackِ صریح (حافظهٔ کمکی)")
print(f"{'n':>8}{'مرتب، pivot اول':>20}{'مرتب، pivot تصادفی':>22}{'تصادفی':>12}")
for n in BIG:
    first = quicksort_stack(list(range(n)))[1]["max_todo"]
    rand = quicksort_stack(list(range(n)), lambda lo, hi: picker3.randrange(lo, hi + 1))[1]["max_todo"]
    mixed = quicksort_stack(shuffled[n])[1]["max_todo"]
    print(f"{n:>8,}{first:>20,}{rand:>22,}{mixed:>12,}")
— بیشترین اندازهٔ stackِ صریح (حافظهٔ کمکی)
       n     مرتب، pivot اول    مرتب، pivot تصادفی      تصادفی
   1,000               1,000                    14          12
   2,000               2,000                    16          18
   4,000               4,000                    18          17
   8,000               8,000                    20          18

ستونِ اول دقیقاً n است و دو ستونِ دیگر با هشت برابر شدنِ n فقط از 14 به 20 و از 12 به 18 می‌روند. یعنی حافظهٔ کمکیِ quicksort بینِ O(log n) و O(n) است و همان چیزی تعیینش می‌کند که مرتبهٔ زمانش را تعیین می‌کرد: کیفیتِ pivot.

(دلیلِ عددِ n در ستونِ اول این است که هر افراز یک بازهٔ خالی هم تولید می‌کند و کدِ ما آن را هم روی todo می‌گذارد. کنار گذاشتنِ بازه‌های خالی، تمرینِ اجباریِ همین فصل است.)

مقایسه‌اش با فصلِ ۴ را صریح بنویس: merge sort در n = 8,000 روی هم 103,808 عضو کپی می‌کرد و در هر لحظه به اندازهٔ n حافظهٔ اضافه داشت. quicksort روی ورودیِ تصادفی هجده جفت عدد نگه می‌دارد. این معاملهٔ اصلیِ بینِ این دو الگوریتم است.

print("— ورودیِ تصادفی (زمان)")
table([(n, 1000 * clock(lambda v=shuffled[n]: quicksort_stack(v), repeat=2))
       for n in BIG], "زمان (ms)", ",.1f")
same = climb[2_000]
slow = clock(lambda: quicksort_stack(same), repeat=2)
picker4 = random.Random(SEED)
fast = clock(lambda: quicksort_stack(same, lambda lo, hi: picker4.randrange(lo, hi + 1)), repeat=2)
print(f"\nورودیِ مرتب، n = 2,000  ·  pivot اول: {1000 * slow:,.1f} ms"
      f"  ·  pivot تصادفی: {1000 * fast:,.1f} ms  ·  نسبت: {slow / fast:,.0f}")
— ورودیِ تصادفی (زمان)
         n         زمان (ms)     نسبت به سطر قبل
     1,000               1.7                   —
     2,000               4.3                2.54
     4,000               8.6                1.98
     8,000              24.5                2.86

ورودیِ مرتب، n = 2,000  ·  pivot اول: 206.4 ms  ·  pivot تصادفی: 4.5 ms  ·  نسبت: 46

روی این ماشین، یک خط تغییر در انتخابِ pivot چهل‌وشش برابر شد. ولی به شمارشِ بخشِ ۴ و ۵ برگرد: آن‌ها روی همین n نسبتِ 1,999,000 به 23,938، یعنی حدودِ ۸۳ برابر می‌دادند. فاصلهٔ این دو عدد خودش یک درس است: نسخهٔ pivot تصادفی به‌ازای هر افراز یک عددِ تصادفی هم می‌سازد و یک جابه‌جاییِ اضافه می‌کند، پس هر مقایسه‌اش گران‌تر تمام می‌شود. چیزی که ماشین‌به‌ماشین کم‌تر تکان می‌خورد نسبتِ شمارش است؛ نسبتِ زمان همیشه از آن کم‌تر درمی‌آید.

✅ چک کن: به‌جای pivot تصادفی، میانهٔ سه عضو را بردار: اولین، وسطی و آخرینِ بازه را ببین و عضوِ میانی‌شان را با a[lo] جابه‌جا کن. حالا جدولِ بخشِ ۵ را دوباره بگیر. روی ورودیِ از پیش مرتب باید عددی نزدیکِ pivot تصادفی بدهد و ستونِ نسبتش حولِ 2 بماند. اگر باز 4.00 گرفتی، احتمالاً میانه را درست حساب نکرده‌ای و همچنان کوچک‌ترین را برمی‌داری.

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

🤖 از دستیارت بپرس: «چرا quicksort روی ورودیِ از پیش مرتب بدترین حالتش را نشان می‌دهد؟» بعد این را هم بپرس: «pivot تصادفی بدترین حالت را از بین می‌برد یا نه؟» — جوابِ درست باید بگوید نه، فقط دیگر کسی نمی‌تواند سفارشش بدهد. اگر دستیارت گفت «بدترین حالت دیگر ممکن نیست»، از او بخواه احتمالش را برایت حساب کند.

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

کلمه تلفظ به حروف فارسی یعنی چه
quicksort کوییک‌سورت مرتب‌سازی با افرازِ پیاپی حولِ یک عضوِ انتخاب‌شده
pivot پیوت عضوی که فهرست حولِ آن به کوچک‌تر و بزرگ‌تر تقسیم می‌شود
partition پارتیشن خودِ عملِ تقسیم کردن حولِ pivot
in-place این‌پلیس الگوریتمی که داده را در جای خودش جابه‌جا می‌کند

تمرین‌ها

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

در فصل بعد#

سه الگوریتم نوشتیم و هیچ‌کدام از n log n بهتر نشد. این یک تصادف نیست و فصلِ بعد ثابتش می‌کند — نه با اندازه‌گیری، با شمردن: تعدادِ ترتیب‌های ممکنِ n عضو n! است و هر مقایسه حداکثر آن را نصف می‌کند.

بعد عددش را می‌گیریم: در n = 8,000 کمترین تعدادِ مقایسهٔ ممکن 92,193 است و merge sort ما 93,704 می‌کند — نسبتِ 1.02. و آخرش الگوریتمی می‌آوریم که این مرز را می‌شکند، چون اصلاً مقایسه نمی‌کند — و همان‌جا اندازه می‌گیریم که کجا برنده است و کجا ۱۹۷ برابر بازنده.

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

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