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

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

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

def isprime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return 0

    return 1

השורה הבאה מריצה את הפונקציה על כל המספרים בין 1 למיליון ומדפיסה את סכום התוצאות - כלומר כמה מספרים ראשוניים יש שם:

print(sum(map(isprime, range(1, 1_000_000))))

אצלי על המחשב התוצאה:

78499

real    0m5.403s
user    0m5.259s
sys 0m0.049s

2. איך מוצאים מספרים ראשוניים במקביל

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

pool = multiprocessing.Pool()
results = pool.map(isprime, range(1, 1_000_000))
print(sum(results))

ונקבל את התוצאה:

78499

real    0m3.048s
user    0m9.895s
sys 0m0.147s

אותו סכום והפעם עם חיסכון של שתי שניות שהן 40% מזמן הריצה. נחמד לא?

3. עכשיו בואו נשב לעבוד

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

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

import math
n = 1_000_000

bag = { i: 1  for i in range(2, n) }

for i in range(2, int(math.sqrt(n) + 1)):
    if i not in bag: continue

    for j in range(i * i, n, i):
        try:
            del(bag[j])
        except KeyError:
            pass

print(len(bag))

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

$ time python3 countprimes.py
78498

real    0m1.130s
user    0m0.989s
sys 0m0.069s

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

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