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

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

הכיוון הראשון שעבד נראה כך:

input_range = range(145852, 616942)
total = 0

for candidate in input_range:
    flag_all_up = True
    flag_same = False
    cand_str = str(candidate)
    for i in range(5):
        if cand_str[i] == cand_str[i+1]:
            flag_same = True
        elif cand_str[i] > cand_str[i+1]:
            flag_all_up = False
            break

    if flag_all_up and flag_same:
        total += 1

print(total)

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

def all_up(candidate):
    cand_str = str(candidate)
    for i in range(5):
        if cand_str[i] > cand_str[i+1]:
            return False

    return True

def has_two_adjacent_digits(candidate):
    cand_str = str(candidate)
    for i in range(5):
        if cand_str[i] == cand_str[i+1]:
            return True
    return False

total = sum(
        map(lambda candidate: all_up(candidate) and has_two_adjacent_digits(candidate),
            input_range))
print(total)

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

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

class TwoAdjacentDigitsPredicate:
    def __init__(self):
        self.result = False

    def process(self, a, b):
        if a == b:
            self.result = True

class AllUpPredicate:
    def __init__(self):
        self.result = True

    def process(self, a, b):
        if a > b:
            self.result = False

def apply_predicates(val, *predicates):
    val = str(val)
    for i in range(5):
        for p in predicates:
            p.process(val[i], val[i+1])
    return all([p.result for p in predicates])

total = filter(lambda candidate: apply_predicates(
            candidate,
            TwoAdjacentDigitsPredicate(), AllUpPredicate()), input_range)

print(sum(1 if x else 0 for x in total))

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

יש לכם כבר ניחוש מה זמני הריצה לכל גירסא? הנה זה בא:

# First version - single function
python3 aoc.py  0.81s user 0.02s system 85% cpu 0.965 total

# Second version - multiple functions
python3 aoc.py  0.54s user 0.01s system 97% cpu 0.568 total

# Third version - Object Oriented
python3 aoc.py  2.52s user 0.04s system 83% cpu 3.072 total

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

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

והמסקנה? בביצועים כמו בביצועים כדאי לבדוק כל דבר. תכנות מונחה עצמים כמעט תמיד יאט אתכם (אבל לפעמים הוא שווה את המחיר) ובכל מקרה מומלץ לא ליצור יותר מדי אוביקטים.

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

input_range = range(145852, 616942)

def isbig(num):
    flag = False
    while num > 0:
        last_digit, digit_before = num % 10, (num % 100) // 10
        if last_digit < digit_before:
            return False
        if last_digit == digit_before:
            flag = True

        num //= 10

    return flag

print(sum([1 for i in input_range if isbig(i)]))

וזמן סיום המשימה בגירסא זו הגיע לשיא של:

python3 a.py  0.30s user 0.01s system 97% cpu 0.316 total