יחידה 6: מיון חיצוני

ברוכים הבאים לשיעור בנושא "מיון חיצוני" במסגרת הקורס "מערכות נתונים". יחידה זו עוסקת באחד האתגרים המרכזיים בעיבוד נתונים בקנה מידה גדול: מיון כמויות עצומות של מידע שאינו נכנס בשלמותו לזיכרון הראשי. נלמד מדוע מיון פנימי אינו מספיק, נכיר את האלגוריתמים המרכזיים למיון חיצוני, ונדגיש את חשיבות חישוב עלויות הקלט/פלט (I/O) כגורם המכריע בביצועים.

הצורך במיון חיצוני ועלויות I/O

כאשר גודל קובץ הנתונים (N) גדול משמעותית מגודל הזיכרון הראשי הזמין (M), אלגוריתמי מיון פנימיים (כמו Quicksort או Mergesort רגיל) אינם ישימים ישירות. במצב כזה, עלינו להשתמש במיון חיצוני, המנצל את הדיסק לאחסון זמני של נתונים.

האתגר המרכזי במיון חיצוני הוא לא מורכבות האלגוריתם מבחינת חישובים, אלא מספר פעולות הקלט/פלט (I/O) הנדרשות. פעולות דיסק איטיות בהרבה מפעולות זיכרון, ולכן עלות I/O היא המדד העיקרי ליעילות אלגוריתם מיון חיצוני.

אלגוריתם מיון מיזוג דו-שלבי (Two-Phase Merge Sort)

זהו האלגוריתם הבסיסי והנפוץ ביותר למיון חיצוני, והוא מורכב משני שלבים עיקריים:

שלב 1: יצירת ריצות ממוינות (Run Creation)

בשלב זה, אנו קוראים נתונים מהקובץ הלא ממוין לתוך הזיכרון הראשי בחלקים. כל חלק בגודל M בלוקים (או פחות, אם הקובץ קטן מ-M) נטען לזיכרון, ממוין באמצעות אלגוריתם מיון פנימי (לרוב Quicksort או Heapsort), ונכתב בחזרה לדיסק כ"ריצה" (Run) ממוינת. תהליך זה חוזר על עצמו עד שכל הקובץ המקורי מחולק לריצות ממוינות קטנות יותר.

• אם גודל הקובץ הוא N בלוקים, וגודל הזיכרון הוא M בלוקים, נקבל N/M ריצות ממוינות.
• עלות I/O של שלב זה: 2N בלוקים (N קריאות, N כתיבות).

שלב 2: מיזוג הריצות (Merging Runs)

בשלב זה, אנו ממזגים באופן חוזר ונשנה את הריצות הממוינות שנוצרו בשלב הראשון, עד שנקבל ריצה אחת גדולה וממוינת המכילה את כל הנתונים. המיזוג מתבצע באמצעות מיזוג רב-נתיבי (Multi-way Merge).

• אנו משתמשים בזיכרון הראשי כחיץ (buffer) עבור קריאה מ-k ריצות וכתיבה לריצה אחת.
• אם יש לנו M בלוקים של זיכרון, נוכל להקצות בלוק אחד כחיץ פלט, ואת M-1 הבלוקים הנותרים לחלוקה בין k חיצי קלט. לכן, נוכל למזג עד k = M-1 ריצות בו-זמנית.
• מספר המעברים (Passes) בשלב המיזוג הוא ⌈log_k(N/M)⌉.
• עלות I/O של כל מעבר מיזוג: 2N בלוקים (N קריאות, N כתיבות).

אופטימיזציות למיון חיצוני

מיזוג רב-נתיבי (Multi-way Merge)

כפי שצוין, מיזוג רב-נתיבי מאפשר למזג k ריצות בו-זמנית. ככל ש-k גדול יותר, כך מספר מעברי המיזוג קטן יותר, ובהתאם, עלות ה-I/O פוחתת. הגדלת k מוגבלת על ידי גודל הזיכרון הזמין (M).

בחירת החלפה (Replacement Selection)

טכניקה זו מאפשרת ליצור ריצות ראשוניות ארוכות יותר מגודל הזיכרון הראשי (M). במקום למיין את כל ה-M בלוקים בבת אחת, אנו משתמשים בערימת מינימום (Min-Heap) בזיכרון. אנו קוראים בלוקים, מוסיפים אותם לערימה, ומוציאים את האיבר המינימלי לעריצה. כאשר איבר מוצא, אנו מנסים להכניס איבר חדש מהקלט. אם האיבר החדש קטן מהאיבר האחרון שהוצא, הוא מסומן כ"קפוא" ואינו נכלל בריצה הנוכחית. בממוצע, שיטה זו מייצרת ריצות באורך 2M בלוקים.

שאלות לדיון

• נתון קובץ בגודל 1000 בלוקים וזיכרון ראשי בגודל 100 בלוקים. כמה ריצות ראשוניות ייווצרו בשיטת מיון מיזוג דו-שלבי רגילה? כמה מעברי מיזוג יידרשו? מהי עלות ה-I/O הכוללת?
• כיצד שימוש בבחירת החלפה ישפיע על התשובה לשאלה הקודמת? (הניחו יצירת ריצות באורך 2M).
• הסבירו מדוע עלות I/O היא המדד החשוב ביותר ליעילות אלגוריתם מיון חיצוני, ולא מורכבות הזמן של פעולות המעבד.
• אילו גורמים נוספים (מלבד גודל הקובץ והזיכרון) יכולים להשפיע על ביצועי מיון חיצוני?

נקודות לתשובת מודל

• הבנת המגבלה: מיון חיצוני נדרש כאשר N > M.
• שלבי האלגוריתם: יצירת ריצות ממוינות (שלב 1) ומיזוג ריצות (שלב 2).
• חישוב ריצות ראשוניות: N/M למיון פנימי רגיל, N/(2M) לבחירת החלפה.
• חישוב מספר מעברי מיזוג: ⌈log_k(מספר ריצות ראשוניות)⌉, כאשר k הוא מספר הריצות הממוזגות בו-זמנית (לרוב M-1).
• חישוב עלות I/O: (מספר מעברים כולל) * 2N. זכרו שכל מעבר קורא וכותב את כל הנתונים.
• אופטימיזציות: מיזוג רב-נתיבי (מגדיל k) ובחירת החלפה (מפחית את מספר הריצות הראשוניות).
• חשיבות I/O: פעולות דיסק איטיות בהרבה מפעולות זיכרון/מעבד, ולכן הן צוואר הבקבוק העיקרי.