מה *לא* לימדו אותנו באוניברסיטה על מבני-נתונים?

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

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

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

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


הכלל הראשון שארצה להדגיש הוא זה:

כלל חשוב לחיים המקצועיים!

כדי להסביר את הכלל, אפתח בדוגמה משעשעת של אלגוריתם חיפוש בשם Sleep Sort:

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

אם רשימת המקור היא 2, 4, ו 3 אזי האיבר 2 יכנס לרשימת היעד לאחר שתי שניות, האיבר ארבע לאחר 4 שניות, והאיבר 3 - לאחר 3 שניות. והנה ביצענו מיון!

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

למשל, עבור קלט של המספרים 2 ו 1,000,000,000 האלגוריתם ירוץ במשך כמעט 32 שנים - מה שבהחלט פחות יעיל אפילו מ Bubble Sort. 


מה היה לנו כאן? מחיר אמיתי מאוד, ומשמעותי מאוד, שלא לקחנו בחשבון בהערכת הזמן של האלגוריתם. יכולנו בהתאם לשכלל את התאוריה שלנו ולנסח זמן ריצה בנוסח:
(O(max(item_size) * sec) +n - כאשר בעיקרון אפשר להזניח את n.



באופן דומה (והרבה פחות קיצוני) ניתן לומר שיש מחירים נוספים ומשמעותיים שלא נלקחים בחשבון בחלק גדול ממבני-הנתונים שלמדנו עליהם:

• HashTable
• LinkedList
• Binary Search Tree
• Graphs

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

חוק המספרים הקטנים

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


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

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

כלומר: אם אתם עוסקים בעשרות, מאות, או אפילו אלפי איברים - סיבוכיות האלגוריתם לא ממש משנה. כל גישה בודדת לדיסק או לרשת - תעלה הרבה יותר.

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


חשוב לציין שלא כל "פקודת מחשב" מתבצעת ע"י cycle בודד של מעבד. ליהפך: תנאי if פשוט לכאורה, עלול בקלות להתתרגם לעשרות ומאות CPU cycles. כאמצעי ביטחון אפשר לחשוב על ה CPU כמבצע עשרות-מיליוני פעולות בשנייה בלבד.

"מספרים שכל מתכנת חייב להכיר" (2012). איפה הייתם בקורס מבני-נתונים?!

המחיר הנוסף

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

• גישה לדיסק היא מאוד מאוד יקרה (לפני עידן ה SSD היא הייתה מאוד מאוד מאוד יקרה).
• גישה לזיכרון היא יקרה, ובהחלט לא אקראית - על אף השם "Random Access Memory = RAM". 
• נתונים, גם מהרשת, גם מהדיסק, וגם משכבות הזיכרון השונות מוגשות בבלוקים רציפים. העלות להביא את הבלוק היא החלק היקר, בעוד ההבדל בין סריקה של בית בודד או את כל הבלוק - הוא לרוב משני עד זניח.
• אפשר לראות את ההתנהגות הזו בנתונים למעלה, כאשר קריאה של בית בודד מ SSD תיקח 0.15ms בעוד קריאה של מיליון בתים מ SSD (עשרות עד מאות בלוקים) - תיקח רק מעט יותר: כ 1.0ms.
• שווה מאוד לקרוא ולטפל בנתונים ברציפות, ולא בסדר אקראי
• למעבדים יש היררכיה של זיכרונות Cache. נתון שלא נמצא ב Cache יובא קודם ל L3 ואז ל L2 ואז ל L1, ולכל הבאה שכזו, יקדם חיפוש ברחבי ה Cache Level שהנתון אכן לא שם.
• זה בזבוז להביא מילה בודדת בזיכרון, ולכן כל פעם מביאים בלוק זיכרון רציף. גודל הבלוק - תלוי בארכיטקטורת המעבד.

נתחיל בתכלס, ונראה איך זה משפיע עלינו.

קרב ראשון: Vector/ArrayList מול LinkedList

אנחנו מעונינים להוסיף דינאמית איברית לרשימה. איזה מבנה-נתונים הכי מתאים? Vector (אשתמש בשם הקדום ב ++C) או רשימה משורשרת?

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

רשימה משורשרת פשוט מוסיפה עוד ועוד ערכים במחיר (O(1 לכל פעולה.

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

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

בואו נראה מה קורה בפועל:

הממ... לא בדיוק.

הכנסה באמצע הרשימה יקרה משמעותית ברשימה משורשרת, למרות שבאופן תאורטי לוקטור יש דווקא עלות נוספת (העתקת המערך) בכל גדילה. מה קרה פה?!

• כל אלמנט ברשימה המשורשרת תופס יותר זיכרון: צריך להכניס לזיכרון גם את הערך וגם את המצביע לאלמנט הבא. כנ"ל אם הערך הוא מצביע לאובייקט ולא Int. זה אותו הדבר.
• בתאוריה: העתקה של מרחבי זיכרון רציפים היא עלות (O(n או משהו יקר אחר.
  בפועל: במעבדים מודרניים יש פקודה יעילה למדי להעתקה של בלוקים של זיכרון. זו איננה פעולה יקרה כ"כ.
• חיפוש המקום להכנסה ברשימה משורשרת הוא הנקודה החלשה הבולטת של הרשימה המשורשרת: ה nodes של הרשימה מפוזרים אקראית במרחב הזיכרון. כשאנו סורקים את הרשימה (בממוצע n/4 איברים בכל פעם) אנחנו "חוטפים" עוד ועוד cache misses הדורשים לעדכן את זיכרון המטמון.
• כאשר אנחנו סורקים את הוקטור, ככמט כל בלוק של זיכרון שנביא ל cache - ינוצל במלואו.
• במקרה של שימוש ב virtual memory (לא נכלל בגרף) - המקרה גרוע הרבה יותר: ייתכן ובגלל קפיצות בין דפים שונים של ה main memory "נחטוף" Page Fault ויהיה עלינו להביא את דף הזיכרון מהדיסק, רחמנא ליצלן! 

שיפור עמודות לטובת הרשימה-המשורשרת

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

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

עד כמה עומדת הרשימה המשורשרת למחוץ את הוקטור? בתיאוריה זה אמור להיות אכזרי כלפי הוקטור. בואו נראה בפועל:

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

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

אין כמעט תסריטים של scale בהם הרשימה המשורשרת יכולה לנצח את הוקטור בעולם האמיתי. רק כאשר גודל האלמנט בכל node הוא גדול מאוד (מאות בתים, למשל) ואז גם ה cache מתרפרש מהר בכל מקרה וגם התקורה של ה next-pointer של הרשימה המשורשרת הופכת לזניחה.

בעולם הג'אווה - המשחק משתנה

הדוגמאות מלמעלה הן ב ++C, וכנראה מייצגות גם את מה שמתרחש ב Rust או Go. שפות שעובדות עם הזיכרון מול מערכת ההפעלה ומושפעות ישירות מארכיטקטורת המעבד.

בג'אווה (או #C) ואולי גם בפייטון / רובי - הדברים מעט שונים. יש מפרשן או JVM/CLR שנמצאים בין מערכת ההפעלה לקוד. יש שימוש מאסיבי ב Heap - שאינו רציף.

איך הדברים נראים בג'אווה? אולי שם ההבדל בין וקטור לרשימה משורשרת נמחק?

בואו נבדוק שוב את המקרה של הכנסת איבר למקום הממוין ברשימה.

אין לי גרף מתאים (הנה המקור לנתונים), אבל מאיסוף ידני של הנתונים ממבחן ב ++C, ב 20,000 איברים היו התוצאות 617 מילישניות לרשימה משורשרת, ו 234 מילישניות לוקטור - שזה יחס דומה.

ה DynamicIntArray, אם תהיתם, הוא מימוש של ArrayList המאחסן איברים מסוג int (פרמיטיב) ולא ב Integer (אובייקט) - ולכן הוא ידידותי באמת ל cache. הנתונים באמת שמורים במערך רציף (כמו ב ++C) והם לא reference לאובייקט שתלוי ב Heap (שאותו ג'אווה אכן משתדלת למלא בצורה רציפה).


המבחנים הנ"ל בוצעו על חומרה ישנה בת כמעט עשור. בואו נראה מה קורה על חומרה עדכנית:

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


את זה לא סיפרו לי בקורס מבני-נתונים!

סיכום ביניים

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

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


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

מה עושים?

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

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

מפתחים של בסיסי נתונים משתמשים ב B-Tree (או B+Tree - וריאציה מעט שונה) כדרך קבע כעצי חיפוש למשל: בשימוש באינקסים.


פעם נתקלתי במימוש שבאמת הייתה בו חשיבות לשימוש ברשימה משורשרת. מה עשינו? הקצנו את הזיכרון עבור כל הרשימה בצורה רציפה (כמו וקטור) והשתמשנו רק בו. דבר דומה עשה חבר שדיברתי איתו - מה שגרם לי להבין שזה common sense ולא המצאה גדולה. חיפוש פשוט בגוגל העלה מימוש שכזה כקוד פתוח.
אלטרנטיבה אחרת, וקצת יותר ידועה: Unrolled Linked List.

מה עושים בגרפים? אני לא מכיר באופן אישי, אבל אני מניח שגם Neo4J או AWS Neptune מצאו את הדרך שלהם לבנות את מבנה הנתונים החשוב והנהדר הזה Graph - בצורה שאיננה עוינת לזיכרון. או לפחות: עוינת פחות ככל האפשר.


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

שיהיה בצלחה!

קישורים רלוונטיים:

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