פרוייקט "התלמיד והמחשב", בעיות 12-13-14

בעיה מס' 12

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

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

puts "Board area: #{(8*ARGV[0].to_i)**2}, total lines length: #{2*ARGV[0].to_i*8*9}"

הדבר היחיד כאן שאולי חדש הוא השימוש ב-** (כוכבית כפולה) על מנת לתאר פעולת חזקה.

בואו נעבור עכשיו לדברים מעניינים יותר.

בעיות 13 ו-14

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

נתחיל בכל זאת מהפתרון הפשוט. ברובי אפשר למצוא מחלקים בשורה אחת:

(1..n).find_all{|k| n % k == 0}

אין כאן משהו שלא ראינו קודם. עכשיו, איך אפשר לבדוק ראשוניות? הדבר המתבקש לבדוק הוא שהתוצאה של הפעלת השורה לעיל היא רשימה באורך 2 בדיוק (כי כאמור, כל רשימה כזו תכיל לפחות את 1 ואת n). אבל למה לכתוב שוב את השורה הזו אם כבר כתבתי אותה פעם אחת? תחת זאת אפשר לתת לה שם בעל משמעות ולהשתמש מכאן ואילך בשם הזה. זה, על קצה המזלג, הרעיון מאחורי אחד המושגים המרכזיים ביותר בתכנות - פונקציה.

אם אתם עוקבים אחרי מה שאני עושה עם הסקל, זה כמובן לא חדש לכם; בהסקל הכל מבוסס על פונקציות. ברובי, לעומת זאת, טרם השתמשתי בהן, ועכשיו זו הזדמנות מצויינת להתחיל. פונקציה בשפות תכנות בכלל כוללת את המרכיבים הבאים: יש לה שם; היא מקבלת קלט; יש את הקוד שמתאר מה היא עושה; והיא מחזירה פלט. כחלק מהקוד של הפונקציה היא יכולה לבצע אפקטים צדדיים (באנגלית זה Side effects; בעברית אני לא בטוח איך לתרגם את זה טוב). אפקט צדדי הוא פעולה שהפונקציה מבצעת ומשפיע על התוכנית גם לאחר סיום הפונקציה, אבל הוא לא חלק מהפלט שלה. למשל, הדפסת שורה למסך המחשב, או שינוי הערך של אחד מהקלטים. ייתכן שפונקציה לא תחזיר בכלל פלט ונריץ אותה רק בשביל האפקטים הצדדיים שלה; יש שפות שבהן מבצעים הפרדה חדה בין פונקציות שמחזירות פלט וכאלה שלא (לעתים קוראים בשם פרוצדורות לפונקציות שלא מחזירות פלט) ויש כאלו שמציינות במפורש שפונקציה אינה מחזירה פלט (למשל, ב-C משתמשים במילה void כדי לתאר מה מחזירה פונקציה שלא מחזירה כלום). ברובי אין את כל ההבחנות הללו. לא כחלק מהשפה עצמה.

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

אם כן, הנה הקוד:

def divisors(n)
  (1..n).find_all{|k| n % k == 0}
end

def is_prime?(n)
  divisors(n).length == 2
end

n = ARGV[0].to_i
puts "Divisors of #{n}: #{divisors(n).join(", ")}"
puts "#{n} is#{(is_prime?(n))?(""):(" not")} prime"

הפונקציה divisors מחזירה מערך, והפונקציה ?is_prime מחזירה ערך בוליאני. כאן אולי חלקכם מרימים גבה, בפרט אלו מכם שיש לו נסיון בתכנות - בדרך כלל סימן שאלה הוא לא חלק לגיטימי משם של פונקציה. ברובי סימני שאלה וסימני קריאה הן סיומות לגיטימיות לשמות של פונקציה ואמורים לרמוז על התפקיד שלהן - פונקציה שמסתיימת ב-? בדרך כלל מבצעת בדיקה ומחזירה ערך בוליאני; פונקציה שמסתיימת ב-! היא בעלת side effect רציני שהמתכנת צריך להתחשב בו. בשני המקרים מדובר על קונבנציה, לא על דרישה אבסולוטית מהקוד; אין חוקים שקובעים מתי מותר ולא מותר להשתמש בסימנים הללו. אפשר גם לוותר עליהם לחלוטין אם הם מעצבנים אתכם (אבל אין מה לעשות - יש פונקציות ספריה שמשתמשות בהם, ועוד נראה את זה בהמשך).

אז למה כדאי להשתמש בפונקציות? הקוד שלעיל ממחיש שתי סיבות. ראשית, זה יותר קומפקטי - אפשר לכתוב את is_prime באמצע שורת ההדפסה ואז לבצע חישוב מסובך בלי לכתוב את הקוד של כולו בתוך השורה; עבור פונקציות שהן לא מאורך שורה אחת אלא כמה עשרות שורות, היתרון ברור עוד יותר. פרט לכך, הסיבה השניה לפיה כדאי להשתמש בפונקציות גם בקוד פשוט כמו זה היא שיפור הקריאות. תחשבו שהייתם באים לקרוא את הקוד שלי בלי לדעת עליו שום דבר - אם הייתם רואים רק את השורה של הקוד של divisors הייתם צריכים להתחיל לחשוב מה לעזאזל אני עושה שם. עכשיו אתם לא צריכים - כדי להבין את השורה הזו מספיק לראות שהיא בתוך פונקציה עם שם ברור (יחסית) ומכאן להסיק מה היא עושה; וכשמשתמשים בה בתוך הקוד, למשל ב-is_prime בכלל לא צריך לחשוב על השורה הזו; במקום זאת אנחנו רואים divisors ומבינים מה הכוונה. הקוד של is_prime הוא “האם מספר המחלקים של n הוא 2?” ולא “האם %#$#^$% של n הוא 2?” כאשר %#$#^$% הוא משהו שהקורא צריך לחשוב קצת כדי להבין מה הוא. ושוב אזכיר לכם - אתם כותבים קוד לא רק עבור עצמכם כרגע, אלא גם עבור מי שיקרא את הקוד עוד שבועיים - וזה יכול להיות מישהו אחר אבל יכול להיות גם אתם עצמכם שכבר לא זוכרים מה לעזאזל עשיתם שם.

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

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

איך נכתוב את אותן פונקציות בהסקל? בקלות:

divisors :: Int -> [Int]
divisors n = [a | a <- [1..n], (n `mod` a) == 0]

is_prime :: Int -> Bool
is_prime n = length (divisors(n)) == 2

אין כאן משהו חדש או מרגש למי שכבר מכיר הסקל אז לא אתעכב על הקוד יותר מדי - הרעיון הוא בדיוק אותו רעיון כמו ברובי.

ומה עם ג’אווהסקריפט? ובכן, מכיוון שכאן הקוד ממילא לא הולך לצאת יפה, אני ארשה לעצמי להתפרע עם קצת אופטימיזציות. אם כבר מצאתי מחלק של n, אז אני יכול לקבל בחינם עוד מחלק של n - אני אחלק את n במחלק! כלומר, אם n=ab ומצאתי את המחלק a, אז אני אחלק את n ב-a ואקבל את b “בחינם”. ומתי אני אדע להפסיק לעבור על מספרים ולבדוק אם הם מחלקים את n? פשוט מאוד - כשאעבור את השורש של n, כלומר אגיע למספר a כך ש-a כפול עצמו גדול מ-n. נסו לשכנע את עצמכם שבשלב הזה אכן מצאתי את כל המחלקים האפשריים.

זה מוביל גם לבדיקת ראשוניות על פי אותו עיקרון - בודקים מחלקים רק עד השורש של n. האלגוריתם הזה, “עד השורש” שמו, הוא ככל הנראה אלגוריתם בדיקת הראשוניות הנאיבי הלא נאיבי הבסיסי ביותר. מה זאת אומרת “נאיבי לא נאיבי”? פירוש הדבר הוא שזה עדיין אלגוריתם מאוד, מאוד, מאוד פשטני, כפי שאסביר עוד מעט; אבל מבין האלגוריתם הפשטניים לפחות יש בו מידת-מה של תחכום.

הנה הקוד במלואו:

<html>
<head>
<title>Targil 13-14</title>
</head>
<body>
  <script type="text/javascript">
  var divisors = function(n){
	divisors_list = new Array();
	for (var a = 1; a*a <= n; a++){
		if (n % a == 0){
			divisors_list.push(a);
			if (n / a > a){
				divisors_list.push(n/a);
			}
		}
	}
	divisors_list.sort(function(a,b){return a-b});
	return divisors_list;
  }

  var is_prime = function(n){
	for (a = 2; a*a <= n; a++){
		if (n % a == 0){
			return false;
		}
	}
	return true;
  }

	var find_divisors_and_primality = function(){
		var n = parseInt(document.getElementById("n").value)
		document.getElementById("divisors").value = divisors(n).join(", ");
		document.getElementById("is_prime").value = is_prime(n);
	}
  </script>
  n = <input type="textbox" id="n" value = "0" onkeyup = "find_divisors_and_primality()"/>
  <br />
  Divisors = <input type="textbox" id="divisors" value = "0"/>
  <br />
  Is prime? <input type="textbox" id="is_prime" value = "0"/>
</body>
</html>

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

בואו נדבר על סיבוכיות

ברשותכם, דיון פרקטי יחסית באופיו. למי שרוצה, יש לי פוסט על אלגוריתמי מיון שגם מציג את הדיון על סיבוכיות זמן ריצה הרבה יותר בפירוט. כרגע אני רוצה להסביר מדוע אלגוריתמי הפירוק לגורמים ובדיקת הראשוניות שהצגתי כאן הם גרועים. נתחיל מזה שהם לא גרועים באופן אבסולוטי - הם אחלה! קל לתכנת אותם והם מחזירים תשובה נכונה על קלטים קטנים. כמה קטנים? נאמר, בני 10 ספרות? אולי קצת יותר. להרבה צרכים פרקטיים זה די והותר. אבל לא לכולם. למשל, הצפנה: במערכת הצפנה מודרנית כדוגמת RSA שמתבססת על מספרים ראשוניים, מדובר על מספרים בני מאות ספרות. עכשיו, פרופורציות: מספר השניות שחלפו מאז תחילת היקום הוא מסדר גודל של \( 10^{17} \). אז אם אני רוצה לבדוק האם מספר בן 100 ספרות הוא ראשוני ואני פשוט עובר על כל המספרים שקטנים ממנו, יהיה עלי לעבור על \( 10^{100} \) מספרים בערך. אפילו אם אניח שאני בודק \( 10^{20} \) מספרים בשניה, זה עדיין אומר \( 10^{80} \) שניות. ומה עם שיטת “עד השורש”? הו, היא מצויינת: היא חוסכת הרבה זמן. במקום לבדוק \( 10^{100} \) מספרים, יהיה צורך לבדוק רק \( 10^{50} \) מספרים. מה שיקח, בהערכה הנדיבה שלי, \( 10^{30} \) שניות. אופס, עדיין יותר מגיל היקום. וב-RSA עובדים עם מספרים בני הרבה יותר מ-100 ספרות.

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

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

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

בשורה התחתונה - אין שפת קסם אחת שטובה להכל, וכדאי להכיר את היתרונות והחסרונות של כל שפה. זו בדיוק הסיבה שאני מראה כאן שלוש!