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

1. איך אני מוצא מספרים ראשוניים

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

def is_prime(n: int) -> bool:
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

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

def primes_below_v2(n: int):
    return [p for p in range(2, n) if is_prime(p)]

2. איך ארסטוטנס מוצא מספרים ראשוניים

הנפה של ארסטוטנס היא שיטה טובה יותר למצוא קבוצות של מספרים ראשוניים. ארסטוטנס שם לב שמספר ראשונים זה מספר שלא מתחלק בשום דבר מלבד באחד ובעצמו, ולכן אם יש לך מספר ראשוני קל מאוד למצוא המון מספרים לא ראשוניים - פשוט תכפול את המספר הראשוני שכבר יש לך במספרים 2, 3, 4, 5 וכך הלאה. אם נתחיל לדוגמה עם 2 שהוא ראשוני אז ברור שכל המספרים הזוגיים אינם ראשוניים. 3 הוא ראשוני ולכן 6, 9, 12, 15 וכל שאר הכפולות של 3 אינם ראשוניים. את הנפה אפשר לקודד בפייתון באופן הבא:

def primes_below(n: int) -> Generator[int, None, None]:
    p = 2
    marked = set()
    while p < n:
        yield p
        marked.add(p)
        for i in range(n // p + 1):
            marked.add(i * p)
        while p in marked:
            p = p + 1

3. מי יותר מהיר

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

import cProfile

cProfile.run("list(primes_below(100))")
cProfile.run("list(primes_below_v2(100))")

ומריץ, והפעם מקבל את הפלט הבא על המסך:

 ~/tmp  python a.py
         250 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
       26    0.000    0.000    0.000    0.000 a.py:5(primes_below)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
      221    0.000    0.000    0.000    0.000 {method 'add' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         201 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 a.py:16(primes_below_v2)
        1    0.000    0.000    0.000    0.000 a.py:17(<listcomp>)
       98    0.000    0.000    0.000    0.000 a.py:19(is_prime)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
       98    0.000    0.000    0.000    0.000 {built-in method math.sqrt}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

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

 ~/tmp  python a.py
         3089206 function calls in 0.652 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.010    0.010    0.652    0.652 <string>:1(<module>)
    78499    0.367    0.000    0.642    0.000 a.py:5(primes_below)
        1    0.000    0.000    0.652    0.652 {built-in method builtins.exec}
  3010704    0.276    0.000    0.276    0.000 {method 'add' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


         2000001 function calls in 3.382 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001    3.382    3.382 <string>:1(<module>)
        1    0.000    0.000    3.381    3.381 a.py:16(primes_below_v2)
        1    0.116    0.116    3.381    3.381 a.py:17(<listcomp>)
   999998    3.216    0.000    3.265    0.000 a.py:19(is_prime)
        1    0.000    0.000    3.382    3.382 {built-in method builtins.exec}
   999998    0.049    0.000    0.049    0.000 {built-in method math.sqrt}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

הפעם השיטה שלי לקחה מעל 3 שניות בעוד שהשיטה של ארסטוטנס מצאה את כל המספרים בקצת יותר מחצי שניה. אחד הפיצ'רים שאני אוהב ב cPython הוא היכולת לכתוב את הסטטיסטיקות לקובץ במקום למסך באמצעות הוספת שם קובץ כפרמטר שני לקריאה:

cProfile.run("list(primes_below(1_000_000))", "stats1.profile")
cProfile.run("list(primes_below_v2(1_000_000))", "stats2.profile")

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