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

וזה עבד, לפחות עד שעליתי לפרודקשן.

1. סיבוכיות

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

אם רק הייתי יודע על סיבוכיות כשכתבתי את הקוד.

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

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

O(n)
O(n ^ 2)
O(logn)
O(n * n)

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

איך מחשבים סיבוכיות? אני שמח ששאלתם ואנסה לענות דרך דוגמה. באתגר Advent Of Code של אתמול (התחלנו את האתגרים של 2020, אז תתכוננו לחפירות AoC בחודש הקרוב) המשימה היתה למצוא זוגות של מספרים ברשימה שסכומם הוא 2020. לדוגמה ברשימה הזאת:

1721
979
366
299
675
1456

המספרים 1721 ו 299 מתאימים כיוון ש 1721 ועוד 299 נותן 2020.

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

def find_pair(data, requested_sum):
    return [(a, b) for a in data for b in data if a + b == requested_sum]


numbers = [1721, 979, 366, 299, 675, 1456]
print(find_pair(numbers, 2020))

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

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

def find_pair(data, requested_sum):
    dataset = set(data)
    for number in data:
        if (2020 - number) in dataset:
            return (number, 2020 - number)


numbers = [1721, 979, 366, 299, 675, 1456]
print(find_pair(numbers, 2020))

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

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

2. תיקון טעות

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

מבנה נתונים set בפייתון מנסה לארגן את המידע כך שבדיקה האם פריט מסוים קיים ב set תהיה מאוד מהירה, וברוב המקרים הוא מצליח טוב והבדיקה אכן מתבצעת בזמן קבוע. אבל יש קלטים שאותם ה set מתקשה לשמור בצורה מאוזנת וכך במקרה הגרוע ביותר אפשר ליצור קלט שיגרום ל set לעבוד הרבה יותר קשה ממה שהוא עובד באופן רגיל. המונחה המקצועי ליחס בין העבודה של מבנה הנתונים למבנה הקלט הוא Load Factor ואפשר לקרוא על Load Factor בהקשר של מילונים בפייתון בקישור הבא:
https://just-taking-a-ride.com/inside_python_dict/chapter4.html