פרוייקט "התלמיד והמחשב", בעיה 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. זה לא הכרחי - יכלתי להגדיר את הפונקציה הזו גם בחוץ, אבל אז הייתי צריך לתת לה שם, וזה לעתים קרובות סתם מסורבל. כאן הפונקציה היא אנונימית - מקבלים אותה ואפשר להשתמש בה, אבל כשאני כותב אותה אני לא צריך לטרוח לתת לה שם במיוחד. בשפות כמו רובי קל מאוד לכתוב פונקציות כאלו בצורה קומפקטית ומנגנון הבלוקים הופך את העסק לאלגנטי יחסית ועוד נראה זאת בהמשך; בג’אווהסקריפט, לטעמי, זה נראה פשוט איום ונורא. אבל עושים את זה כל הזמן. גם אני.