2018-10-27

דפוס עיצוב: מתכון [מהקשור?]


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


מתכון


כיצד כדאי לתאר פעולה שחוזרת על עצמה מספר פעמים, ומכילה הוראות עבודה - בצורה הטובה ביותר לצריכה (consumption)?

הנה דוגמה:


"אלוהים ישמור! מתכון ב Excel?!"

ובכן.. אני מציע לכם לנסות כאן מעט גמישות מחשבתית. כמה הסברים על הפורמט:
  1. הרכיבים רשומים כשורות, בעוד הפעולות (על מקבץ רכיבים) מופיעים כעמודות נוספות (B עד E - בדוגמה הזו).
    1. פעולות מקדימות ארוכות מצוינות על שורה מלאה לפני שאר הרכיבים. (לדוגמה: שורה 3).
    2. הפורמט מאפשר לתאר בצורה אינטואטיבית פעולות שניתן לבצע במקביל (למשל: מנה עיקרית ורוטב). 
  2. כמה כללים נוספים:
    1. הקפידו ששם הרכיב יהיה בתחילת המשפט (עמודה A) - ולא באמצע או בסוף. כך קל יותר לאתר אותו בסריקה מהירה.
      1. את הכמויות (מספרים) ניתן לציין גם בסוף. אם הם מופיעות בהתחלה - עדיף להשתמש בספרות ולא במילים (יקל על המוח לדלג עליהם בזמן הבישול)
    2. השתדלו לציין כמויות בצורה מדידה ומדויקת. אם חוזרים למתכון לאחר זמן ארוך, ביטויים כגון "בנדיבות" עשויים להתפרש לגמרי אחרת.
    3. הציבו את ההכנות הארוכות בפעולה לפני ההכנות הקשות בפעולה. למשל: "לקצוץ שום" היא בהחלט פעולה ארוכה יותר להכנה מאשר "הוספת מים". 
    4. תקנו את המתכון ושפרו אותו. כמובן.


מה היתרונות, של דפוס העיצוב (/שימוש) הנ"ל?
  • מתכון משמש אותנו ב-2 תסריטים: 1. קניית הרכיבים   2. הבישול עצמו. 
    • בשני התסריטים הללו אין לנו הרבה זמן וטקסט ארוך מגביר את הסיכוי ל"פספוסים".  הפורמט הנ"ל משפר את הקריאות ויכולת המעקב, גם כשיש לנו מעט קשב. כלומר: הוא read optimized.
  • מתכון (מוצלח) נכתב פעם אחת, אך נקרא עשרות פעמים. כאשר מתכון מוכיח את עצמו כמוצלח - שווה להעביר אותו לפורמט הנ"ל (השקעה שתחזיר את עצמה לאורך זמן).
    • ברור שתיאור מתכון בפורמט הנ"ל ידרוש השקעה של כמה דקות.
  • כמובן שיש כאן אלמנט ברור של DRY. כאשר כותבים את שמות הרכיבים גם ברשימת הקניות וגם מתוך התפריט אז:
    • זה גם גוזל יותר מקום (בקטנה)
    • כאשר מבצעים שינויים / מציעים רכיבים חלופיים - ציון שלהם רק במקום אחד עשוי להיות מבלבל. מניסיון.


סיכום


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

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

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

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

שיהיה בהצלחה!



2018-10-20

Slack It!

בפוסט הקצרצר הזה ארצה לתת כמה טיפים לשימוש ב Slack. כלי שרובנו (כולנו?) משתמשים בו על בסיס יומי, אבל אולי לא מנצלים אותו ב 100%.

למי יש בכלל זמן ללכת ולהתעמק בכלי עבודה... שמשתמשים בו רק כמה עשרות פעמים ביום?!





סלאק אמור להיות כיפי


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

אצלנו, למשל, משתמשים הרבה ב Giphy. זו ממש תרבות. כשקורה משהו מעניין, מתחילים להופיע animated gifs על הערוץ. פשוט מקלידים: <giphy <keywords/ ואז אפשר לדפדף בין כמה אופציות, ובלחיצה להוסיף לערוץ:


זה נחמד ומוסיף (בד״כ. נא לא להגזים!).

יש גם את songg שמככב בערוץ team_music#, למרות שמוזיקה קצת פחות מיינסטרים - הוא מתקשה לעתים למצוא (מה כ״כ קשה ב Misa Criolla? או ב Crusify your mind של רודריגז?)

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



הערוץ הפרטי


כשאתם לא בטוחים איך plugin או עריכה של טקסט תעבוד בסלאק, פשוט תנסו!
לשם כך, יש לכל אחד ערוץ פרטי:


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



החיפוש עובד!

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

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

 in: from: has: before: after: on: during: 

על מנת לצמצם בצורה יעילה יותר את התוצאות.

כמקובל בחיפוש ניתן להשתמש ב:
  • מרכאות ״״ - על מנת לחפש אחר ביטוי מדויק
  • שלילת ביטוי ע״י הצבתו לאחר סימן מינוס -
  • שימוש ב * כ wildcard


בצד ימין של תוצאות החיפוש (לאחר שלחצתם Enter) - יש אופציות פילטור נוספות, שניתן להפעיל בקלות.
  • אם אתם מתכננים חיפוש פשוט, אתם יכולים להתחיל את החיפוש מתוך שורת ההודעה ע״י שימוש בפקודה s/ ולאחריה מילות החיפוש.
  • ע״י CMD+F ניתן לבצע חיפוש ב Channel הנוכחי
  • ע״י CMD+G ניתן לבצע חיפוש גלובאלי. תוצאות החיפוש האחרון יישמרו ל 5 דקות, ותוכלו לחזור אליהן בעזרת הקשה נוספת על CMD+G.



סלאק הוא Command Line tool, בעצם


כשאתם על ספידים, שימוש בעכבר רק מאט אתכם ועלול אף לקטוע את חוט המחשבה.
ישנם כמה קיצורים שיחסכו לכם עבודת עכבר מעצבנת. בעיקר (לטעמי האישי):
  • Cmd+K - מעבר ערוץ (dm או channel)
  • באותו הקשר: ]+Cmd - חזרה לערוץ הקודם שנבחר
  • fn + חצים למעלה ולמטה - מעבר מהיר בין ההודעות בערוץ.
  • : ולהתחיל להקליד - על מנת להגיע מהר ל emojis. הקיצור :1+: - הוא האהוב עלי. טאב יכול לקצר.
  • @ invite/ (בקיצור: i/ ואז טאב) - הוספת אדם לערוץ, וגם בלי ״ללכלך״ את הערוץ.
  • option+8 - הוספת bullet לטקסט
  • מתוך שורת ההודעה, חץ למעלה יערוך את ההודעה האחרונה. תיקון שגיאות כתיב וכאלו.
  • Option + Shift + חץ למטה - מעבר להודעה האחרונה שלא נקראה. רפרוף על הודעות אחרונות בזריזות.
  • msg @person text/ על מנת לשלוח הודעה מהירה למישהו, מבלי להחליף ערוץ / לאבד את ה context:




Formatting להודעה


כאן אני כנראה לא אחדש, אבל החלטתי בכל זאת:
  • הדגשה בעזרת כוכביות: *your text*
  • קו תחתון בעזרת.. קו תחתון: _your text_
  • ציטוט ע״י סימן ״גדול-מ״: your text <
    • ציטוט טקסט של מספר שורות ע״י שלושה סימני ״גדול-מ״: your text <<<
    • מעבר שורה הוא, כמובן, ע״י shift+Enter
  • הצגת טקסט ב monospace font ע״י עטיפה בגרש הפוך: `your text`
    • באופן דומה ניתן לעשות זאת לכמה שורות טקסט עם העטיפה ``` your text ```
  • לרוע המזל אין syntax highlighting, בתוך הודעות. יש להוסיף code snippet ע״י כפתור ה +:


    • code snippets חשובים כי בלעדיהם סלאק יחליף גרשיים ב״גרשיים מעוצבים״ שאינם בטווח ה ASCII. התנהגות מעצבנת - מכלי שנועד למפתחים.



Starring


כלי שימושי בסלאק הוא Starring (מעין ״bookmarks״) - סימון הערוצים וההודעות שחשוב לכם לחזור אליהן,

מתחת לשם הערוץ, בראש הדף יש כוכב כבוי. הדליקו אותו וקבלו גישה נוחה (בעזרת עכבר):





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


תוכלו לחזור אליה בקלות אח״כ ע״י הקלקה על סימן הכוכב בפינה הימנית העליונה של המסך, או ע״י הקיצור CMD+Shift+S.

רק אל תשכחו to unstar הודעות חשובות שקראתם כבר. אחרת יצטבר לכם צביר הודעות שלא תוכלו באמת לטפל בו.



הודעות מתפרצות


רוצים לעקוב מהר יותר אחרי מה שקורה בערוצים השונים?

אם מזכירים את שמכם בערוץ מסוים (או פונים ל here/@channel@) - תקבלו על כך הדגשה (badge).
אם אתם רוצים להקשיב לעוד מילות מפתח, אתם יכולים להגדיר אותן ב Preferences/Notification:





סיכום


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

הרגישו חופשיים להוסיף טריקים ושימושים בתגובות לפוסט.

שיהיה בהצלחה!



2018-10-13

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

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

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

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

לאחר כמעט 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 עמודים שמסביר הכל, אבל לא נראה לי שווה את ההשקעה. במיוחד כי דברים גם משתנים.