פרוייקט "התלמיד והמחשב", בעיה 9

בעיה 9 בספר היא בעיית המיון. או ליתר דיוק, בספר מתעסקים במיון רשימות באורך המרשים של 2 ו-3 מספרים, באמצעות שרשרת של if-ים; אני כמובן לא מוכן לעשות את זה ותחת זאת אציג מיון של מערך כללי. מיון, כזכור, פירושו לקחת מערך של איברים עם סדר כלשהו עליהם (כלומר, אפשר להשוות כל שני איברים) ולסדר אותו מהקטן לגדול. יש לי כבר פוסטים על מיונים שמתחילים כאן; לכן לא אחזור על הכל. שיטות המיון שבחרתי להשתמש בהן הן כאלו שנותנות לי אפשרות להציג דברים שאני רוצה להציג מתוך השפות, לא יותר מכך.

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

הנה הקוד:

# puts "After sorting the list #{ARGV.join(", ")} we get #{ARGV.collect{|x| x.to_i}.sort.join(", ")}"
list = ARGV.collect{|x| x.to_i}
sorted_list = []
while not list.empty?
  current_element = list.pop
  current_index = 0
  while current_index < sorted_list.length and sorted_list[current_index] < current_element
    current_index = current_index + 1
  end
  sorted_list.insert(current_index, current_element)
end
puts "After sorting the list #{ARGV.join(", ")} we get #{sorted_list.join(", ")}"

מה קורה פה? בשורה 2 אנחנו ממירים את הרשימה לרשימה של מספרים. בשורה 3 אנחנו מגדירים רשימה חדשה, ריקה, שתכיל את התוצאה הממוינת. בשורה 4 אנחנו כותבים while ולאחר מכן תנאי – זוהי תמיד ההתחלה של לולאת while. לאחר ה-while מופיע בלוק שמסתיים ב-end שבשורה 11, והרעיון ב-while הוא שכל עוד התנאי שנכתב בו מתקיים, כאשר הבלוק מגיע לסופו הוא ישוב להתחלה. ייתכן שהתנאי לא יתקיים אפילו בפעם הראשונה שבה אנחנו מגיעים ללולאה ואז הבלוק שלה פשוט לא יופעל.

התנאי במקרה שלנו הוא שהרשימה שקלטנו היא ריקה. אפשר לבדוק שהיא ריקה על ידי בדיקה שאורכה הוא 0, אבל לצורכי קריאות רובי מספקת לנו פונקציה שעושה את זה בשבילנו – הפונקציה ?empty. שימו לב – סימן השאלה הוא חלק מהשם של הפונקציה, ואם לא נכתוב אותו, הפונקציה לא תפעל. זו אחת מהמוזריות של רובי שאני מחבב והרבה אנשים שונאים לפיה אפשר להשתמש בסימני שאלה וקריאה בסוף שמות של פונקציות (המוסכמה היא שסימני שאלה משמשים לציין פונקציות שמבצעות בדיקה ומחזירות ערך בוליאני ואילו סימני קריאה משמשים לציון פונקציה עם פעולה "הרסנית", אבל אין חוקים קשיחים שמגבילים מתי אפשר ומתי אי אפשר להשתמש בהם).

בשורה 5 אנחנו מוציאים איבר מסוף הרשימה ומכניסים אותו למשתנה current_element. השם pop מגיע מהשמות הרגילים לפעולה על מבנה הנתונים מחסנית (יש גם פקודת push תואמת). בשורה 6 אנחנו מתחילים את הנסיון למצוא לאן ברשימה החדשה לדחוף את current_element; ברירת המחדל שלנו היא התא שבאינדקס 0. כעת, בשורה 7 אנחנו מתחילים לולאת while חדשה בתוך הלולאה הקיימת (קוראים לזה "קינון" לולאות), שמגדילה את האינדקס שלנו כל עוד הוא אינו מצביע אל מעבר לסוף הרשימה הנוכחית וכל עוד האיבר שהוא מצביע עליו גדול מהאיבר שאנחנו רוצים לדחוף לרשימה. לבסוף, כשאנחנו סגורים על האינדקס שלנו, בשורה 10 אנחנו דוחפים את האיבר החדש לרשימה עם הפקודה insert שמקבלת שני פרמטרים: הראשון אומר איפה לדחוף את האיבר החדש, והשני הוא האיבר עצמו. ייתכן שאתם תוהים מה יקרה אם בתור המקום לדחוף אליו את האיבר החדש אני אתן מספר גדול הרבה יותר מאורך הרשימה. למשל, מה קורה אם אני דוחף איבר חדש למקום 10 ברשימה שיש בה רק 4 איברים? התשובה היא שבמקום 10 ברשימה (שמתאים לאיבר ה-11 בה; זכרו שהאינדוקס מתחיל מ-0) יידחף האיבר החדש, ובמקומות החל מ-4 ועד 9 יידחף nil, שמציין תא ריק (בשפות אחרות הייתה עלולה להתרחש שגיאה תחת זאת).

ובכן, זה מימוש סטנדרטי של אלגוריתם סטנדרטי ולא יעיל במיוחד, אבל צריך להראות איך משתמשים ברובי ב-while מתישהו. בואו נעבור לדבר על הסקל, שהיא משמעותית הרבה יותר כיפית כאן. בפרט, הפתרון שאני רוצה להראות הוא אחד מהדברים הראשונים שנהוג להראות לאנשים כשמנסים להמיר את דתם להסקל – מימוש של מיון מהיר.

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

אבל רגע, איך זה פותר את הבעיה? צריך עדיין למיין את שתי הרשימות הקטנות יותר! ובכן, פשוט נפעיל גם עליהן את מיון מהיר! כלומר, יש לנו כאן פונקציה שמפעילה את עצמה. להפעלה עצמית כזו קוראים רקורסיה והיא מושג חשוב מאין כמותו בתכנות. הרעיון שמאחורי הרקורסיה כאן הוא שההפעלה העצמית הזו לא אמורה להימשך לנצח – בכל פעם אלגוריתם המיון מופעל על רשימות קטנות יותר ויותר, עד שבסוף הוא יקבל רשימה ריקה ואז אין מה למיין – פשוט מחזירים אותה כמות שהיא.

הנה איך כל זה נראה בהסקל:

import System.Environment

toIntArray :: [String] -> [Int]
toIntArray array = [read(x) | x <- array]

quickSort :: Ord a => [a] -> [a]
quickSort [] 		= []
quickSort (x:xs) 	= quickSort smaller ++ [x] ++ quickSort larger
  where
    smaller = [a | a <- xs, a < x]
    larger  = [b | b <- xs, b >= x]
  
main = do
  args <- getArgs
  putStrLn (show(quickSort(toIntArray args)))

המיון עצמו הוא בשורות 6-11. ראשית, אני מגדיר את quickSort באופן גנרי, שיוכל לפעול על כל רשימה של איברים מטיפוס שניתן להשוות אותו (אגב, ברובי לא שמים לב לכך אבל גם שם זה מתקיים). זו המשמעות של ה-" <= Ord a" שכתוב בהגדרת הפונקציה. בשורה 7 אני מגדיר שעל רשימה ריקה, quickSort יחזיר רשימה ריקה. בשורה 8 מגיע האקשן: אני מפרק את הרשימה לאיבר ראשון x ולכל יתר האיקסים, xs (נסו לקרוא את זה בקול!) ואז משרשר את המיון המהיר של smaller עם הרשימה שהאיבר היחיד שלה הוא איבר הציר x, עם המיון המהיר של larger. אבל מי הם smaller, larger? הם מוגדרים אחרי ה-where, באמצעות list comprehensions שראינו כבר בפוסט הקודם, כשכאן יש גם התניה, שמופיעה בצד ימין אחרי הפסיק.

מה שכל כך נחמד במימוש הזה הוא הקריאות שלו – הקוד כתוב בערך כמו שנראה תיאור מתמטי פורמלי של "מה האלגוריתם עושה". שימו לב – לא איך האלגוריתם עושה את זה, אלא מה הרעיון הכללי של האלגוריתם. במקרה הנוכחי זה כבר מספיק. בשפות אחרות, המימוש של מיון מהיר הוא עדיין פשוט יחסית, אבל קריא וברור הרבה פחות.

הדילמה עכשיו היא מה להראות בג'אווהסקריפט. כבר הראיתי מימוש של אלגוריתם נאיבי ברובי כדי להסביר איך לולאות עובדות, וכבר הראיתי מימוש מגניב של אלגוריתם מגניב בהסקל. בג'אווהסקריפט החלטתי להשתמש בפונקציית המיון שמובנית בשפה, אבל באופן לא טריוויאלי, כדי שנבין עד כמה חזקה הגישה של שפה מודרנית למושג המיון. הרעיון היא שבהינתן מערך של איברים, אין הכרח למיין אותו מהקטן לגדול על פי איזה סדר "טבעי" שקיים בין האיברים; תחת זאת, פונקציית המיון יכולה לקבל כקלט פונקציה שתפקידה הוא להשוות בין שני איברים ולהחליט מי מהם קטן ומי מהם גדול יותר. מקובל שהפונקציה הזו תקבל שלושה ערכים ותחזיר מספר שלם, שהוא קטן מאפס אם הערך הראשון "קטן" מהשני, אפס אם הם "זהים" (כלומר, פונקצית המיון שלנו לא רוצה לתעדף אף אחד על פני השני) וגדול מאפס אם הערך הראשון "גדול" מהשני. זה מאפשר לנו למיין דברים בצורות שונות ומשונות על פי מה שנוח לנו בזה הרגע.

מה קורה מאחורי הקלעים? מופעל אלגוריתם מיון רגיל לחלוטין שמבוסס על השוואות, כדוגמת מיון מהיר, אבל בכל פעם שבה צריך לבצע השוואה, קוראים לפונקציית ההשוואה שסופקה על ידי המשתמש. כמובן שגם ברובי ובהסקל אפשר לעשות דברים כאלו ועוד נראה זאת בהמשך.

מה שאני עושה בקוד הג'אווהסקריפט הנוכחי הוא לקבל מספרים טבעיים ולמיין אותם על פי הנורמה ה-2-אדית שלהם. מה זו למען השם נורמה 2-אדית? יש לי פוסט בנושא, אבל זה לא ממש חשוב כרגע מאיפה ההגדרה המוזרה הזו מגיעה – אני לוקח אותה בכוונה בגלל שהיא מוזרה. ההגדרה אומרת כך: הנורמה ה-2-אדית של מספר טבעי היא אחד חלקי החזקה הגבוהה ביותר של 2 שמחלקת את המספר. למשל, עבור 14, החזקה הגבוהה ביותר של 2 שמחלקת את 14 היא 2 עצמה (2 בחזקת 1) ולכן הנורמה שלו תהיה חצי; אבל עבור 28, החזקה הגבוהה ביותר של 2 שמחלקת את 28 היא 4 (2 בחזקת 2) ולכן הנורמה שלו תהיה רבע, וכן הלאה (שימו לב: אני מחלק בשתיים בחזקת משהו; אני לא מחלק רק ב"משהו").

הנה הקוד:

<html>
<head>
<title>Targil 9</title>
</head>
<body>
  <script type="text/javascript">
  var norm_2_adic = function(a){
	if (a == 0){
		return 0;
	}
	var norm = 1.0;
	while (a % 2 == 0){
		a /= 2;
		norm /= 2;
	}
	return norm;
  }
  
    sort_by_2_adic_norm = function(){
		var nums = document.getElementById("nums").value.split(" ");
		nums.sort(function(a,b) {
			var norm_a = norm_2_adic(parseInt(a));
			var norm_b = norm_2_adic(parseInt(b));
			if (norm_a < norm_b){
				return -1;
			}
			if (norm_a > norm_b){
				return 1;
			}
			return 0;
		});
		
		document.getElementById("sorted").value = nums.join(" ");
    }
  </script>
  List = <input type="textbox" id="nums" value = "0" onkeyup = "sort_by_2_adic_norm()"/>
  <br />
  Sorted = <input type="textbox" id="sorted" value = "0"/>
</body>
</html>

שימו לב לשיקוץ אחד שאני עושה כאן – אני מגדיר את הפונקציה ש-sort מקבלת בתוך הקריאה ל-sort. זה לא הכרחי – יכלתי להגדיר את הפונקציה הזו גם בחוץ, אבל אז הייתי צריך לתת לה שם, וזה לעתים קרובות סתם מסורבל. כאן הפונקציה היא אנונימית – מקבלים אותה ואפשר להשתמש בה, אבל כשאני כותב אותה אני לא צריך לטרוח לתת לה שם במיוחד. בשפות כמו רובי קל מאוד לכתוב פונקציות כאלו בצורה קומפקטית ומנגנון הבלוקים הופך את העסק לאלגנטי יחסית ועוד נראה זאת בהמשך; בג'אווהסקריפט, לטעמי, זה נראה פשוט איום ונורא. אבל עושים את זה כל הזמן. גם אני.

16 תגובות על הפוסט “פרוייקט "התלמיד והמחשב", בעיה 9

  1. לא עדיף להוסיף בהסקל את השורה quicksort [x] = [x] בשביל מהירות ריצה?

  2. עוזי,

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

  3. תחשוב על זה בתור אתגר לקורא – לא חייבים אותו כדי להבין את החלק בקוד שהוא מטרת הפוסט, והקורא יכול לנסות להבין אותו מההקשר, או לגגל. בערך כמו בלימוד שפה אמיתית שגם בה לא בהכרח יסבירו לך כל מילה.

  4. אני לא יודע אם קיימים בJavaScript אופרטורים שפועלים על הסיביות (bitwise operators) אבל אם כן אז מציאת הנורמה ה2-אדית של מספר היא משימה קלה מאוד (ששקולה למציאת הLSB של מספר) וניתן למצוא אותה כך:
    norm = 1.0 / (n & -n)

    אופטימיזציה קלילה שנובעת מטרחנות שלי ומובן שאינה רלוונטית לדברים אותם רצית להדגים.
    ארצה גם להוסיף כי אני מחבב מאוד את סדרת הפוסטים הזאת בפרט ואת הבלוג הזה בכלל.

  5. אני הכנתי אלגוריתם מיון מהיר בסוג-של-שפת-תכנות שנקראת סקראץ' (scratch). הוא עובד לא טוב, אבל אני לא מוצא את הבאגים.
    אין בגרסה הזאת של סקראץ' אפשרות ל-de-bug, אז אני פונה אליך, שאולי תסכים לעזור לי.
    הקוד עשוי מבלוקים ולא משורות אז אני אעתיק תרגום שלו לפסאודו-קוד (הקוד מתחיל כשכל הרשימות פרט לזו שצריך למיין, ריקות).
    בקוד יש את רשימות העזר התחלות, סופים, קטנים ו-גדולים (האינדקסים מתחילים מ-1) ואת המשתנים i, j, התחלה, סוף, איבר_ציר ו-ציר.
    והנה ה(פסאודו )קוד:
    הוסף 1 להתחלות
    הוסף אורך של הרשימה לסופים
    קרא לשגרה מיין

    מיין:
    מחק את כל הפריטים מתוך גדולים
    מחק את כל הפריטים מתוך קטנים
    קבע התחלה לפריט אחרון של התחלות
    קבע סוף לפריט אחרון של סופים
    אם סוף>התחלה אז:
    קבע ציר למספר אקראי בין התחלה לסוף
    קבע איבר_ציר לפריט ציר של הרשימה
    קבע i להתחלה
    חזור עד ש-i=ציר:
    אם איבר_ציר<פריט i של הרשימה אז:
    הוסף i לגדולים
    ואם לא:
    הוסף i לקטנים
    סיום אם
    שנה ערך i ב-1
    חזור
    שנה ערך i ב-1
    חזור עד ש-i<סוף:
    אם איבר_ציראורך של קטנים:
    הכנס פריט i של קטנים במקום j של הרשימה
    שנה ערך i ב-1
    שנה ערך j ב-1
    חזור
    הכנס את איבר_ציר במקום j של הרשימה
    קבע i ל-1
    שנה ערך j ב-1
    חזור עד שאורך של גדולים<i:
    הכנס פריט i של גדולים במקום j של הרשימה
    שנה ערך i ב-1
    שנה ערך j ב-1
    חזור
    הוסף ציר לסופים
    קרא למיין
    הוסף פריט אחרון של סופים להתחלות
    מחק פריט אחרון של סופים
    קרא למיין
    מחק פריט אחרון של התחלות
    סוף אם
    סוף שגרה

    אני מקווה שזה היה קריא ושתוכל למצוא מה הבאג

  6. "חזור עד ש-iסוף" ובין "אם איבר_ציר" לבין "אורך של קטנים" לא הועלו כמה שורות

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

  8. בסדר, אני מצאתי שגיאה בסוף אבל היא לא הספיקה ויש עדיין באגים.
    אני מנסה להיעזר באנשים אחרים

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

כתיבת תגובה

האימייל לא יוצג באתר.