מיון ומחול
24/12/2019
מיון, כלומר סידור קבוצת איברים לפי סדר כלשהו, הוא תהליך חשוב בעולם המחשבים ובחיים. אולם התהליך נראה לעיתים טכני ומשעמם. לכבוד החנוכה, חג הפסטיבלים והמופעים, נציג שתי שיטות מיונים, ונציע לבצען תוך כדי שירה וריקודים.
"שלום, שלום וגם להתראות; חבל נורא היה נעים מאוד; שלום ,שלום וגם ליל מנוחה; ליל מנוחה גם לך, וגם לך" קטע שיר זה לקוח מהסרט הקלאסי הנהדר "צלילי המוסיקה". בסצנה זו, הילדים שלמדו לשיר ולרקוד בסיוע האומנת המקסימה שלהם (ג'ולי אנדרוז) מופיעים לפני אביהם המופתע [1]. במהלך ההופעה עוזבים הם בהדרגה, מהגדול עד הקטנה, את חדר האורחים, תוך כדי שירה וריקודים.
חנוכה הגיע, חג הפסטיבלים, המופעים והחלטורות. נדמיין שאנו מאלתרים מופע בהשראת הסרט, בו משתתפים עשרה ילדים שרוקדים ושרים. במהלך ההופעה, הם צריכים לצאת מהבמה בצורה הדרגתית בהתאם לגובהם, מהגדול עד הקטן. אולם עומדים הם בשורה על הבמה, לא בהתאם לגובהם. מה ניתן לעשות כדי לסדר אותם?
הרעיון: נמיין אותם תוך כדי ריקוד. ראשית, נבקש מהילד הראשון מימין לרקוד עם הילדה משמאלו שנמצאת במקום השני בשורה. במהלך הריקוד, ישוו הם את הגובה של שניהם, ובסיומו יתארגנו מחדש: הנמוך מבין שניהם יתמקם במקום הראשון, והגבוה במקום השני בשורה. לאחר מכן, הגבוה שהתמקם במקום השני ירקוד עם מי שנמצא במקום השלישי. בתום ריקוד זה, הנמוך משניהם יתמקם במקום השני והגבוה במקום השלישי, וכך הלאה. נוכל להיווכח שאחרי תשעה ריקודים, הגבוה בחבורה יגיע למקום העשירי בשורה, ואז הוא יוכל לרדת מהבמה לצלילי המוסיקה. כעת, נותרים על הבמה רק תשעה ילדים. הילד הראשון מימין ירקוד עם מי שנמצא משמאלו, וכך ימשך התהליך שוב ושוב, עד שכולם ירדו מהבמה.
כמה קטעי ריקוד זוגיים יהיו בסך הכול ? בשלב הראשון שבו נמצאו על הבמה עשרה ילדים, יהיו תשעה קטעי מחול, בשלב השני שבו יש תשעה ילדים יהיו שמונה קטעי מחול, וכך הלאה. בשלב האחרון שבו נשארים רק שני ילדים, יבוצע קטע ריקוד אחד. לכן, מספר הריקודים יהיה: 1+ 2..+ 9+8+7+6. כמה זה ביחד? אם תחשבו, תגלו שהתוצאה 45.
האם נוכל לחשב זאת בלי לטרוח לחבר את תשעת המספרים? במקום לחבר מספרים, הניחו את הנרות שהכנתם לחנוכה על השולחן וספרו אותם. המספר שתקבלו הוא 44. קל לראות שהבעיה החישובית דומה: ביום הראשון מדליקים שני נרות, ביום השני שלושה נרות, וכולי, עד שביום השמיני מדליקים תשעה נרות. בסך הכל: 2+ 3...+ 9+8+7= 44 נרות.
אכן, ספירת כמות הנרות דומה לספירת מספר הריקודים. אולם, האם יש נוסחה כללית לחישוב סכום המספרים מ-1 עד n כלשהו, כדי שלא נצטרך להתאמץ לחבר? מספרים על המתמטיקאי המפורסם קרל פרידריך גאוס שהוא פתר את הבעיה בגיל שש. הוא הימם את המורה, כשמצא את השיטה והשתמש בה לחישוב מהיר של סכום המספרים מ-1 עד 100 ( כתבנו על זה פעם פוסט [2]). הנוסחה הכללית היא n+1)*n/2 ) , ובדוגמה שלנו: 2 / 9*10 = 45
הבעיה החישובית די פשוטה. לעומת זאת, תהליך מיון הרקדנים לפי הגובה מעניין יותר. הצגנו כאן אנלוגיה לאלגוריתם בסיסי במדעי המחשב הקרוי Bubble-sort המשמש למיון מערך בזיכרון המחשב. בכל שלב באלגוריתם, שולפים מהמערך בזיכרון שני איברים צמודים ("ילדים שכנים בשורה") , משווים ביניהם ("מבצעים ריקוד זוגי"), ומארגנים אותם מחדש כך שהגדול ימוקם בתא במערך בעל האינדקס הגבוה. נניח שיש n+1 איברים במערך. בסבב הראשון עושים n השוואות, מוצאים את האיבר המקסימלי ומוציאים אותו מהמערך. בסבב השני, יש צורך ב n פחות אחד השוואות, וכולי. בסך הכול, בהתאם לנוסחה שהצגנו יש צורך לעשות n+1)*n/2 ) פעולות השוואה.
כאן מתעוררת בעיה: עבור מערכים גדולים, מספר ההשוואות נהייה גדול מאוד ואיתו גם זמן הביצוע של האלגוריתם. עבור מערכים גדולים, אם מגדילים למשל את מספר האיברים פי עשר, זמן הביצוע יגדל בערך פי 100. כדי לפתור זאת, אנשי המחשבים פיתחו שיטות יעילות יותר למיון.
גם במופע המאולתר שלנו, כדאי לחפש דרכים מהירות יותר למיון, שכן הצפייה ב- 45 קטעי ריקודי זוגות תהייה חוויה מתישה לצופים. נשים לב כי יש חוסר יעילות בשיטה שהצגנו, שכן שבכל שלב רק זוג אחד רוקד ואילו שאר הילדים ממתינים לתורם. כדי לשפר את שיטת המיון, כדאי לאפשר לכמה שיותר זוגות לרקוד במקביל. כמו שמהנדסים אומרים: "צריך להשיג ניצול יעיל של חומרה מקבילית".
כדי לשפר את המצב, נשתמש באלגוריתם מיון שתוכנן עבור חומרה מקבילית [3] וקרוי bitonic-sort. לצורך הפשטות, נדגים אותו עבור ארבעה ילדים: בשלב ראשון ניתן לשני זוגות לרקוד במקביל. בשלב השני, ניקח את השניים שנמצאו הכי גבוהים בשלב הראשון, ונרקיד אותם. קל לראות שהילד שיצא הגבוה משניהם הוא הגבוה מבין כל חברי הקבוצה. במקביל, ניקח גם את השניים שנמצאו הכי נמוכים בשלב הראשון ונרקיד אותם. הנמוך ביניהם הוא הנמוך בקרב כל הקבוצה. בשלב האחרון, ניקח רק את שני אלו מהשלב הקודם שלא זכו להיות הגבוהים או הנמוכים ביותר, וניתן להם לרקוד. לפי התוצאה נדע מי נמצא במקומות השני והשלישי בדירוג הגובה. בסך הכל, עשינו רק שלושה שלבים של ריקודים, במקום 3+2+1=6 שלבים שהיינו עושים בשיטה הקודמת. בכך, קיצרנו את זמן המופע בחצי. עבור דוגמה אחרת עם 8 ילדים, הפתרון מכיל 6 שלבים במקום 28 שלבים שבשיטה הקודמת.
אכן, באמצעות שיטת מיון שפותחה לחומרה, למדנו כיצד לקצר את המופע. נראה שגם בפוסט הזה יש צורך לקצר, אז נוסיף רק: חג חנוכה שמח!
מקורות וקישורים:
מהנדס מחשבים, חוקר ויזם בתחום החינוך המתמטי.
