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

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

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

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

def find_primes(start, end):
    primes = set(range(start, end))
    k = 2

    while k < end:
        for number in set(primes) - set([k]):
            if (number % k) == 0:
                primes.remove(number)

        k += 1

    return primes

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

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

קל גם לראות את הבעיות במנגנון רק מתוך הקוד (או מתוך התיאור בעברית):

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

2. לא צריך להתקדם עם k עד סוף הטווח, מספיק להתקדם עד שורש של end.

3. לא צריך להתקדם כל פעם ב-1, אפשר לדלג על מספרים זוגיים ולקדם את k ב-2.

4. לא צריך ליצור set חדש כל איטרציה, אפשר למחוק תמיד מאותו set מקורי.

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

אחרי שחיברתי את כל האופטימיזציות הגעתי לקוד הבא:

def find_primes(start, end):
    k = start if start % 2 == 1 else start + 1
    primes = set(range(start, end)) - set(range(4, end, 2))

    while k < math.sqrt(end) + 1:
        i = 2 * k
        while i < end:
            if i in primes:
                primes.remove(i)
            i += k

        while True:
            k += 2
            if k in primes: break

    return primes

אני אוהב אותו. אולי אפשר לכתוב גירסא יותר קריאה אבל בגדול הוא די ממחיש את האלגוריתם אחרי כל האופטימיזציות וכמובן מבחינת מהירות עם זה כבר אפשר לעבוד. איתור כל 1229 המספרים הראשוניים עד 10,000 לקח 0.04 שניות, וגם כשעליתי לחפש את כל המספרים הראשוניים עד מיליון הצלחתי למצוא את כל 78,498 המספרים בפחות משניה (0.53 שניות למי שרוצה לדייק).

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

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