על רקורסיה והטעות הקריטית בקוד של ”מאסטר שף”

מאיה גרשוביץ בר מסבירה למה סרטון ”מאסטר שף” של מיקרוסופט הוא פשוט דוגמה לאיך לא לכתוב קוד רקורסיבי ואיך אפשר להפוך אותו לפחות גרוע

אני מאמינה שרובכן ראיתן את סרטון ה”מאסטר שף” של מיקרוסופט ששטף את הרשתות החברתיות לאחרונה.

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

כדי שלא תוציא לעצמכן את העיניים, הנה הקוד שמופיע במחשב של יונתן.

public static int Fib(int n1)
    if (n1 <= 2) 
    {
        return 1;
    }
    else
    {
        return Fib(n1 - 1) + Fib(n1 -2 )
    }

למה הקוד הזה גרוע כל כך?

הדוגמא של סדרת פיבונאצ’י היא דוגמא מפורסמת לקוד רקורסיבי, מכיוון שההגדרה של סדרת פיבונאצ’י היא הגדרה רקורסיבית. המספר ה-n בסדרת פיבונאצ’י הוא סכום שני המספרים הקודמים בסדרה.

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

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

שימו לב, במספרים “קצת יותר גדולים” אני לא מדברת על מיליונים, אנחנו נגיע לשם מאוד מהר.

רציתי לבדוק מתי בדיוק זה יקרה, אז הרצתי את הקוד ובדקתי. החישוב של Fib(30) במחשב שלי לקח פחות משנייה, החישוב של Fib(40) לקח 22 שניות. החישוב של Fib(60) כבר לא חזר.

העליתי את הקוד, ואתן יכולות לבדוק אותו גם במחשב שלכן.

אז למה זה קורה?

צורת הכתיבה הזו של רקורסיית פיבונאצ’י יוצרת הרבה עבודה מיותרת, וקוראת שוב ושוב לאותם החישובים. בואו נסתכל על הריצה של הקוד בתור עץ של קריאות.

אנחנו רואות ש-fib(5) קורא ל-fib(4) ו-fib(3).

לאחר מכן fib(4) גם הוא קורא ל-fib(3) כך שהחישוב של fib(3) מחושב פעמייים בצורה זהה.

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

איך אפשר לעשות את הקוד פחות גרוע?

יש שלוש דרכים טובות יותר למצוא את האיבר ה-n בסדרת פיבונאצ’י.

  1. להשתמש בנוסחה. למזלכן (ולמזלי) לבלוג ‘לא מדויק’ יש פוסט בנושא הזה בדיוק.
  2. להשתמש ברקורסיית זנב, שזהו סוג הרקורסיה האהוב עליי, והפוסט הבא יוקדש לו.
  3. לטייב קצת את הקוד המקורי בעזרת memoization

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

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

אני אוסיף cache כזה לקוד המקורי –

def memoized_fib(n):
    results_cache = {}
 
    def fib(num):
        if num in results_cache:
            return results_cache[num]
        else:
            if num <= 2:
                res = 1
            else:
                res = fib(num - 1) + fib(num - 2)
 
            results_cache[num] = res
            return res
 
    return fib(n)

הקוד החדש נראה דומה לקוד הקודם. הוא עדיין קורא שוב ושוב לחישובים שכבר בוצעו, אבל בזכות השימוש ב-cache אנחנו מורידות מהעץ את כל החישובים הכפולים, ונשארות עם כמות עבודה לינארית.
כעת החישובים רצים הרבה יותר מהר – Fib(500) לוקח פחות משנייה.

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

במקרה של הקוד שלי, ב-Fib(1000) פייתון כבר התחיל לצעוק עלי שמספיק עם הרקורסיה הזאת והוא לא הסכים לשחק יותר.

בבעיה הזו נטפל במאמר הבא

מי אמרה stack overflow ולא קיבלה?

 

למאמרים נוספים של מאיה גרשוביץ בר

 

מאיה גרשוביץ בר

מתכנתת, גיקית, כותבת הבלוג "מאיה כותבת אלגוריתמים"

הגב

59 תגובות על "על רקורסיה והטעות הקריטית בקוד של ”מאסטר שף”"

avatar
Photo and Image Files
 
 
 
Audio and Video Files
 
 
 
Other File Types
 
 
 

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

סידור לפי:   חדש | ישן | הכי מדורגים
בלשן
Guest

למה הכתבה כתובה בלשון נקבה? אם תמשיכו כך, גם את הכתבות הבאות לא אקרא.

המציאות
Guest

וואי וואי.. שמעתם גיקטיים? יש לנו פה קורא עם אגו שברירי במיוחד :(

קורא יקר, נא להישאר בכותלי ביתך וחלילה לא לצאת החוצה, שמא המציאות תכה על פניך ולפתע תבין שהשמש לא זורחת לך מהתחת.

גשש בלש
Guest

נעמיד פנים שהכותבת לא קראה לעצמה “המציאות” לפני רגע.

יוש
Guest

אוי חמוד, כל-כך קשה לך בעיניים? לא נורא, אל תקרא. למה לאמץ מח חמוד כל-כך?

חרדון מצוי
Guest

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

מה עוד אוכל לומר, אם זה מה שיעודד שוויון בין גברים ונשים שיבושם לכותבת המאמר

גשש בלש
Guest

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

משה
Guest

למה לא לרוץ פשוט על לולאה שמחזיקה מספר קטן של משתנים? – יוצא O של N בסיבוכיות חישוב ו- O של 1 בסיבוכיות מקום – בלי להפציץ את המחסנית..

סטודנט
Guest

אכן מספיק שני משתנים שזוכרים את שני המספרים האחרונים.

זוהר
Guest

משתנות ולא משתנים

jewd
Guest

אני חייב לציין את העובדה שיש בפייתון חבילה שנקראת functools
ובחבילה יש אופציה לשים מעל אותה פעולה לא יעילה “@cache”
וזה שומר את התוצאות הקודמות של הריקורסיה ובמקום להכנס שום לפעולה זה פשוט נותן את התוצאה שיצאה בפעם הקודמת.

סרטון הסברה: https://www.youtube.com/watch?v=DnKxKFXB4NQ

אחד שמבין בדברים
Guest
אחד שמבין בדברים

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

ASD
Guest

מה הקשר בין פוליטיקה לבין לכתוב בצורת נקבה?

בצל כחול
Guest

כי זאת אג’נדה פוליטית.
פוליטיקה זה לא רק “ביבי נגד לא ביבי”
מה גם שכתיבה בגוף נקבה אומרת שהכתבה מופנית רק לנשים.
אז לא רץ שהכתיבה (וגם הקריאה) מאולצת, היא גם לא נכונה.

ASD
Guest

אבל זו לא אג׳נדה פוליטית. גם אם אתה אומר שהיא כן.
אולי אג׳נדה חברתית, אבל לא פוליטית.

החלטת שפנייה נקבית היא רק לנשים ואתה יכול גם להחליט שהיא פונה לכולם כמו שהחלטת והסכמת שפנייה גברית פונה לכולם ולא רק לגברים.

בצל כחול
Guest

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

שפה היא אלסטית
Guest
שפה היא אלסטית

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

מיכל
Guest

מאמר סופר מעניין, מחכה לפוסט המובטח הבא!

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

הוא והיא
Guest

הםסקתי לקרוא באמצע. מעיק לגמריי

מישהו
Guest

אחלה מגניב אבל…
פיבונאצ׳י כותבים בלי רקורסיה. יש לזה פתרון לינארי.

אממ
Guest

החא דברה גם על הנוסחה הסגורה שזה אפילו פחות מלינארי

חרדון מצוי
Guest

כתבה ברמה של שיעור בתיכון – מביך

טרול
Guest

לכותבת תלמדי מזה tail recursion ובכללי תפסיקי להתנשא

tail
Guest

מתוך הכתבה:

“להשתמש ברקורסיית זנב, שזהו סוג הרקורסיה האהוב עליי, והפוסט הבא יוקדש לו.”

רקורסיית זנב = tail recursion

חלאס נו
Guest

הכתיבה בלשון נקבה הפריעה לי, לא אשקר.

חרדון מצוי
Guest

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

אבנר
Guest

יפה שלרגע עצרת לחשוב מה אישה חושבת או מרגישה, אבל אז אמרת לעצמך “לא, לא, אני כבר יודע מה הן מרגישות”.

amlout-of-touch-no-its-the-children-who-are-wrong-2936045.png
חרדון מצוי
Guest

זה שאתה כותב משהו לא הופך אותו לנכון. אמרתי שכל ילד וילדה יודעים מה זה “סתמי”

זוהר
Guest

כנראה שהיא חושבת שזה “סתמי” מלשון “סתמי ת’פה”…

נעמה
Guest

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

חרדון מצוי
Guest

כשיש זכר אחד בחדר צריך לדבר *אל הכלל* ומה לעשות שלפני 3000-4000 שנה החליטו שלשון זכר יהיה “סתמי”. עכשיו השאלה מה עושים עם זה – המוח שלנו כבר מחווט להתייחס ללשון זכר כ”סתמי”. לשון “רבות” לעומת זאת מהווה פנייה לנשים בלבד ואיננו פתרון לטעמי (יותר כמו “העדפה מתקנת” מעט מתריסה). כתיבה הכוללת את שני המינים מעייפת ומסרבלת.

לכן שאלתי איך נשים מרגישות עם גוף “רבים” שכידוע הוא “סתמי” ומופנה לשיני המינים (ומה שביניהם).

חרדון מצוי
Guest

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

אולי צריך להמציא גוף רבים-ניטרלי. למשל יכולים + יכולות = יכולית
וכולם יהיו מרוצים.

אבנר
Guest

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

אבנר
Guest

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

חרדון מצוי
Guest

שפה צריכה להיות גם יעילה ונוחה לקורא או לשומע – הפיתרון שאתה מציע מבלבל

אבנר
Guest

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

חרדון מצוי
Guest

לא נכון, המצב כרגע הוא כזה:
“רבות” – פניה לנשים בלבד
“רבים” – פניה לגברים בלבד או “סתמי”

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

אגב, אני מבין את התסכול הנשי ש”סתמי” הוא לשון “רבים” אבל יש בזה גם היגיון והוא פשטות (פעלים בעברית מורכבים דיים שכן פועל מרוכב מגוף + זמן + בניין)

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

זוהר
Guest

“נמאס לנו” ואוהווה…
תתחילי מרד.

HunkeyDory
Guest

נהנתי לקרוא! מחכה לפוסט הבא

גיל ג
Guest

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

שחר
Guest

מה זה ״צריך מאמר״?
לך חפש בגוגל
זה אתר חדשות לא בלוג תכנות

שחר
Guest
Ran Lupovich
Member

מעניין, תודה

גיא
Guest

הי מאיה,
מה עם המספר אפס, הוא/היא לא מודפס.

זוהר
Guest

מספרה ולא מספר

לא חשוב
Guest

מעניין (תתעלמי בבקשה משומרי המגדר).

שחר
Guest

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

יוסי
Guest

הפונקציה fib שלך גם לא טובה כי היא “מלוכלכת” (בניגוד ל”פונקציה טהורה”), משום שהיא משתמשת במשאבית חיצונית לה, המטמונית. אם מישהי מחוץ לפונקציה (נגיד פונקציה אחרת) תלכלך את המטמונית, התוצאות תהיינה לא נכונות.

אחד שלא יודע
Guest

הרגת אותי :)

גיא
Guest

גם אתה הרגת :)

אבנר
Guest

אבל ה-cache מוגדר ב-scope של memoized_fib וקיים רק בזמן הריצה של הפונקציה. אין כאן בעיה של functional purity כי היחידה הפונקציונלית הנקייה היא memoized_fib, ו-fib הפנימית היא רק implementation detail.

יוסי
Guest

כן אבל memoized_fib היא לא פונקציה רקורסיבית. היא לא קוראת לעצמה אלא היא קוראת לפונקציה fib שהיא הרקורסיבית.
fib קוראת לעצמה אבל משתמשת במשאב חיצוני לה.
כך שהרקורסיה במימוש הזה אינה טהורה.

אבנר
Guest

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

יוסי
Guest

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

אבנר
Guest

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

רועי
Guest

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

קורא
Guest
לדעתי זה שגוי לכתוב כתבות בלשון נקבה. ולכל אלו שאומרים “ואיך האישה מרגישה כשהיא קוראת בלשון גבר?” אז רק שתדעו שלפי חוקי הדקדוק של השפה העברית שכולנו כותבים ומדברים בה לשון גבר זו הצורה הסתמית והכללית של טקסט לרבים. כשכותבים טקסט ברבים אמורים לכתוב את זה בלשון זכר אלא אם כן הטקסט מופנה במיוחד לנשים ללא גברים בקבוצה, וכשכותבים כתבה אינטרנטית שמופנת לקהל רחב ולא ידוע חייב לכתוב בלשון זכר בדיוק מהסיבות הנ”ל. ובנוסף שינוי יסוד השפה העברית לא יעזור אפילו לא מעט לשוויון בין המינים ואפילו יחמיר את המצב ויכעיס את כל המין הגברי שבין כה וכה לא מחזיר… Read more »
גיל
Guest
כתבה משעשעת, תודה! לא ברור לי השימוש של כל הקוראים שנעלבו בטיעון “זה החוק שקבעה האקדמיה לעברית”. נקבעו לאורך ההסטוריה האנושית הרבה כללים וחוקים, בין מדובר בחוק שניתן לאכיפה ע”י המשטרה ובין אם מדובר ב”חוק” שהוא למעשה נורמה חברתית, ששיחקו תפקיד במידור, דיכוי ושנאת האחר. הכלל הזה כל כך חשוב לכם, בזמן שאני בטוח שאתם לא משתמשים בהטיות הנכונות בפנייה לרבות, עתיד, במבנה: _נא, כמו תבואנא, תתכנתנא וכו’. השפה השתנתה אינספור פעמים והיא תמשיך להשתנות, בין אם תהיו שותפים לשינוי ובין אם לא. בקיצור, זה טיעון שנראה “שכלתני” אבל הוא תפל וחסר תוכן. פשוט תגידו את האמת: זה פוגע בכם.… Read more »
משה
Guest

מעניין יהיה לראות בעיה (ופתרונה) שבאמת קשה לפתור בלי רקוסיה.

יוני
Guest

אז למה לא השקיעו בקוד במערכון? האם כתב אותו מתכנת הודי במיקור חוץ?

wpDiscuz

תגיות לכתבה: