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

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

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

  • מדוע HashTable לא באמת פועל ב (Θ(1?
  • מדוע עבודה על איברים בודדים במערך ממוין – מהירה יותר מעבודה על מערך לא ממוין?
  • כיצד Regular Expressions עלולים להוסיף סיבוכיות מיותרת?
  • מהו אלגוריתם המיון היעיל והנפוץ ביותר – שאתם כנראה לא מכירים?
בואו נתחיל!
לא כל ה hashtables נולדו שווים. זמני הכנסה של מיליוני איברים.

מיתוס: HashTable מכניס ושולף איברים ב (Θ(1

בקורס מבני-נתונים כנראה ולימדו אותנו ש HashTable מכניס/מוחק/שולף איברים בזמן קבוע – ולכן ניתן להסיק שזה זמן טוב מאוד.

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

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

זמן הריצה של ה hash function איננו אפסי. פונקציית hash אורכות זמן, בד"כ כפונקציה יחסית לקלט.
אם נניח, לצורך הפשטות, שהמפתח (key) ב HashTable הוא מחרוזת, אזי יהיה נכון לומר שזמן הכנסה של איבר הוא (Θ(k כאשר הוא k תלוי באופן ישיר באורך המחרוזת. זמן הביצוע תלוי גם בפונקציית ה hash הספציפית שנבחרה, ופונקציות hash "איכותיות" המספקות פיזור קרוב יותר לאחיד – רצות לאורך זמן רב יותר.

במקרה והמפתח של ה HashTable הוא אובייקט מורכב – ייתכן וזמן הריצה יהיה משמעותי.

חשוב לזכור שאת פונקציית ה hash לא מחשבים רק בהכנסה של איבר, אלא גם בכל שליפה.
כאשר יש התנגשויות (collisions) אזי יש לקחת בחשבון גם n קטן של השוואות.

נניח ועלינו לשלוף מתוך סט של M איברים – כ m איברים. עומדות לפנינו 2 ברירות:

  • לשלוף m איברים מתוך HashTable, בזה אחר זה.
  • לסרוק את כל המערך בגודל M ולמצוא את האיברים.
    • להזכיר: ה HashTable משתמש במערך, מאחורי הקלעים.

בהסתכלות נאיבית נראה שהבחירה היא בין (Θ(M לבין (Θ(m (כאשר M > m) – בחירה קלה למדי.

בפועל הבחירה היא בין (Θ(M לבין (Θ(m*k, כאשר סביר להניח ש k (זמן הריצה של ה hash function כתלות באורך הקלט) יהיה גדול בעשרת מונים, לכל הפחות, מפעולת שליפה של איבר בודד ממערך.
בסריקה סדרתית של המערך, כפי שאנו יודעים – אנו נהנים גם Data locality של הנתונים. בלוקי-הזיכרון יובאו לזיכרון פעם אחת, וינוצלו במלואם.

אפשר לומר שאם M/m < 10 – אזי בוודאי עדיף לסרוק את המערך.
הדבר עשוי להיות נכון גם ל M/m < 100 ואולי אף יותר – יש לבדוק כל מקרה לגופו.

מכאן, כדאי לזכור:

  • כאשר יש לנו בעיות ביצועים, במיוחד בלולאה ששולפת ומכניסה ל HashTable – אל תניחו שזמן השליפה מתוך ה HashTable הוא זניח.
  • שימוש באובייקט עסקי (למשל: Customer) בתור מפתח ל HashTable עשוי להיות מיפוי עסקי מבריק.
    • כאשר חוק המספרים הקטנים פועל – אין בעיה.
    • כאשר אנו נדרשים לספק ביצועים גבוהים על כמויות גדולות של נתונים – אובייקט גדול כמפתח עשוי להיות רעה חולה.
  • שווה גם להזכיר את העניין הידוע בג'אווה שאם אתם דורסים את מתודת ()equals עליכם לדרוס גם את ()hashCode, וליהפך.
Benchmark פשוט שהרצתי כמה פעמים בכדי להראות שהכנסה ל HashTable היא לא כמו הכנסה ל ArrayList. להמחשה בלבד.

חזרה ל Data Locality

נושא מרכזי שעסקתי בו בפוסט הקודם היה Data Locality: איזו יתרון יש, בארכיטקטורת מחשבים בת-זמננו, לגישה לזיכרון רציף כך שהנתונים יוגשו מה Caches הקרובים ביותר (L1>L2>L3). אנו רוצים לצמצם ככל האפשר גישות לזיכרון הראשי או (חס וחלילה!) לדיסק.

כ 85% משטח ה CPU המודרני מוקצה ל Caches, וכמעט כל השטח קשור באופן ישיר לאכסון או העברה יעילה של נתונים. Data Locality איננו פרט שולי – אלא עקרון מרכזי בארכיטקטורה של מעבדים מודרנים.

הנה הרצאה של Herb Sutter (מחבר סדרת הספרים ++Exceptional C) בנושא.
עוד מקור מוצלח הוא המצגת Pitfalls of OO Programming – המיועדת במקור למפתחי מנועי משחקי-מחשב, היכן שהשיקולים הללו הם מלאכה יום-יומית.

החשיבה על Data Locality איננה נכונה רק למבני-נתונים, אלא לכל רצף ארוך של פעולות שאנו מבצעים. פעולות כאלו לרוב יכללו מבני-נתונים – אך לא תמיד.

עקרון ה Locality מגיע בשני אופנים:

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

למשל: כשעוברים על מערך דו-מימדי עדיף הרבה יותר לעבור שורה-שורה (כלומר: על איברים במערך הפנימי ברצף) מאשר לעבור על הטורים ו"לקפוץ" כל פעם בין המערכים הרציפים שהוקצו.

יעילות ה cache בשני מימושים דומים. סדר הגישה העדיף כמובן תלוי במימוש הספציפי של שפת התכנות / סביבת הריצה שאנו עובדים בה.


דוגמה עדכנית נוספת יכולה להיות Streams:

  • כל הפעולות ב Stream יפעלו ברצף איבר-איבר. הדבר מאפשר מקומיות זמנית ברמה הגבוהה ביותר של caching, ב registers של המעבד (ה cache המהיר ביותר) – מה ברוב הפעמים יתרום לביצועים.
  • כאשר יש ברצף הפעולות פעולות "רוחביות" (כגון sorting) אזי דווקא עדיף להשתמש ב collection ולא ב stream – בכדי ליהנות ממקומיות מרחבית.
בשפת קוטלין ברירת המחדש היא עבודה ב collections, ועל מנת לבחור ב stream יש להשתמש ב ()asSequence.
כמובן שכל היתרונות הללו בטלים בשישים – כאשר מדובר בחוק המספרים הקטנים. כלומר: אל תחשבו עליהם אפילו – אם מדובר במאות איברים או פחות.
כאשר אנו עובדים על כמות קטנה של נתונים – הם ככל הנראה יתאימו ל cache, גם אם יוגשו מעשרות בלוקים שונים של זיכרון. הדבר כן עשוי לידי ביטוי אם אנו מבצעים את הפעולה הזו שוב ושוב – עבור נתונים שונים.

מדוע עבודה על איברים בודדים במערך ממוין – מהירה יותר מעבודה על מערך לא ממוין?

כמובן שזה לא המקרה תמיד, אבל זה בהחלט עשוי לקרות.

הביטו שניה בקוד הבא ונסו לחשוב כיצד הדבר קורה:

העניין פה הוא אופטימיזציה ברמת המעבד הנקראת Branch Prediction.

בגדול, ה CPU עובד ב pipeline ארוך של פעולות. כלומר: הפעלת רצף פעולות יעלה רק מעט יותר מהפעלה של פעולה בודדת.
כאשר יש להמתין לתשובה בבחירת הפעולה הבאה – הרצף נשבר, והיתרון בהפעלה של pipeline ״באוטומט״ – אובד.

מתי זה שימושי?
למשל כאשר יש משפטי if בולאנים ולאחריהם פעולה פשוטה. בזמן שממתינים לתוצאה של תנאי ה if – המעבד יכול לבצע כבר פעולה נוספת באותו ה pipeline.

במקרה שלנו יש Branch prediction על הפעולה : (if (data[c] >= 128.
השורה העוקבת היא פעולה פשוטה שהמעבד יכול להפעיל בזמן שהוא ממתין לתוצאת ה if. האלטרנטיבה (תחילת איטרציה חדשה) – היא כבר פעולה כבדה יותר. מכאן סביר שהמעבד יבחר בשורה העוקבת ו״ידחוף״ אותה ל pipeline.

אם הוא צדק בניחוש – הוא ייקח את תוצאת החישוב שאליה הגיע (התוצאה של הפעלת ()data[c].toLong)  – וישתמש בה.
אם טעה – לא נורא. הוא "יזרוק" את מה שהכין – וימשיך ב branch השני (במקרה הזה – קידום הלולאה). בכל מקרה הוא לא היה מסוגל לפעול מהר יותר.

כאשר המערך ממוין, ובמיוחד במקרה כמו שלנו בו יש טווח מאוד מצומצם של 256*2 ערכים אפשריים – הניחושים של ה CPU עומדים להיות טובים מאוד (אפשר לומר: על סף האופטימליים).

לכן, כאשר המערך ממוין, הטרנספורמציה ל long מתרחשת בתוך אותו ה pipeline כמעט תמיד ובעלות זניחה, בעוד כאשר המערך לא ממוין, זה יקרה רק לפעמים (כ 50% מהמקרים).
כפי שניתן לראות – הפערים בזמני הביצוע הם משמעותיים למדי (ב ++C הפערים מגיעים לכמעט פי 10).

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

מילה על Regular Expression

Regex אינם מבני-נתונים. מה הם עושים כאן בפוסט?!

הכללתי את הנושא, כי הוא כולל אלמנטים משיקים.
פגשתי לא פעם אנשי-תוכנה שהיו משוכנעים שאם הם יגדירו ביטוי כ Regex ו״יעברו שלב קומפילציה" (בניית ה matcher) – אזי מובטח להם שה Regex יהיה יעיל יותר מקוד שיכתבו.

Regex הוא בגדול כלי productivity: לכתוב ביטוי Regex ייקח, ברוב הפעמים, פחות זמן מלכתוב קוד מקביל שיבצע פעולה דומה.
זמני הריצה של ה RegEx תלויים מאוד בביטוי, כאשר ביטויים מסוימים מחושבים ב (O(1, אחרים ב (O(n, אולי (O(n^2 ועד סיבוכיות שלא ניתן לתאר. הם בהחלט לא חייבים להיות (O(n.

למשל, לפני זמן לא רב נתקלתי ב Unit Test שזמן הריצה שלו עלה מ ms בודדים – לשלוש דקות בגלל הרצה של Regex מסובך למדי.
הנה סיפור על Regex שרץ לאורך 5 יממות – והוחלף ע"י כלי אחר שעשה את העבודה ב 15 דקות (פשוט ירידה בסיבוכיות – אין כאן קסמים).

בקיצור:

  • אל תניחו שזמן הריצה של Regex הוא לינאי או קרוב לכך. הכל תלוי בביטוי הספציפי.
  • כש Regex הופך לבעיה, בדקו כיצד ניתן לשפר את הביטוי בכדי לקבל סיבוכיות מסדר גודל קטן יותר.
  • תמיד יש את האופציה הלגיטימית לכתוב custom code – ברמת סיבוכיות ואופטימיזציה גבוהה יותר.

בקצרה: מבני-נתונים ואלגוריתמים מקובלים – שכדאי להיות מודעים אליהם

מיון

שתי שפות התכנות הנפוצות ביותר בעולם כיום הן, ככל הנראה: ג'אווה ופייטון [א].

מה אלגוריתם החיפוש של הספריה הסטנדרטית שלהן?

  • QuickSort (היה נכון פעם ל ++C) – לא.    עדכון: פרמיטיביים בג'אווה ממוינים בעזרת DualPivotQuicksort. יש לו עניין של instability – אך זה לא רלוונטי לפרמיטביים.
  • MergeSort (פעם היה בג'אווה) – לא.
  • BubbleSort? – אל תהיו מצחיקים!
אז מה? איזה אלגוריתם חיפוש הוא, אחד הרצים בעולם ואחד המוכרים פחות?
TimSort!
אל תתביישו אם לא שמעתם עליו – אבל כדאי להכיר.
בתיאוריה, קיימת הוכחה מתמטית לפיה כל אלגוריתם מיון שאין לו ידע על התפלגות הקלט (למשל: רק מספרים בטווח מסוים) לא יוכל להיות יעיל יותר מ (Θ(n*lgn.
לא קל להגיע לזמן ביצוע של (Θ(n*lgn – ובד"כ זה בא במחירים אחרים. למשל: זיכרון (כמו MergeSort).
TimSort מצליח "לנצח" את התאוריה במקרים מסוימים (Best Case), ובממוצע להציג שיפור לא רע, בזכות הנחה מעניינת אך בסיסית על הפלגות הנתונים: שהיא לא אקראית לחלוטין. ככל שהיא תהיה פחות אקראית – כך הביצועים שלו יהיו טובים יותר.
TimSort (שקרוי על שם מי שפיתח אותו, טים פיטר, ממפתחי פייטון – זה לא אלגוריתם שהגיע מהאקדמיה) בבסיסו מריץ MergeSort (אלגוריתם שלרוב מבצע טוב מהרגיל) בעוד הוא משתמש ב batches קטנים ב Insertion Sort (גרסה משופרת של ה BubbleSort) – היעיל במיוחד למיון קבוצות קטנות של נתונים.
בנתונים מהעולם האמיתי המידע לא מפוזר באופן אקראי לחלוטין. בעצם: קשה מאוד לייצר נתונים אקראיים לחלוטין. בנתונים ״רגילים״ של מערכים יש בו רצפים, גדולים או קטנים, של איברים ממוינים.
TimSort פועל בגדול באופן הבא:
  1. סריקה של הנתונים ואיתור רצפים עולים ורצפים יורדים. אם הרצף יורד – הוא פשוט יהפוך אותו.
    1. הנתונים כבר ממוינים? סיימנו ב (O(n. לא נשמע חוכמה, אבל QuickSort ו MergeSort יבזבזו כאן (O(n*lgn, זה יכול להתתרגם לפי 10 או פי 100 – יותר זמן ריצה.
  2. קבוצות של עד 64 איברים – ממיינים בעזרת Insertion Sort, היעיל לקבוצות קטנות של נתונים וגם נהנה מ Data Locality.
  3. שימוש ב Merge Sort על מנת למיין את הקבוצות הממוינות – כאשר נשמר איזון בין הקבוצות בעקבות המיון המוקדם.
שווה להכיר בקיומו: KD-TreeKD-Tree הוא מבנה נתונים דיי שימושי (אני השתמשתי כמה פעמים) המאפשר לאנדקס נתונים בכמה מימדים.
בעיקרון הוא מקרה כללי של Binary Search Tree (הרץ על מימד אחד), אבל מאפשר לרוץ על כמה מימדים.
אם אנו רוצים לאנדקס 2 מימדים – אז כל שכבה זוגית תבצע חיתוך על ציר x וכל שכבה אי-זוגית על ציר y.
את אותו רעיון אפשר להרחיב ל 3, 4 מימדים ויותר.

במקרה הזה הצומת הראשי מפצל את המרחב על ציר x, ואז הקודוד מתחתיו את ציר y, וחוזר חלילה.

KD-Trees משמשים בבסיסי נתונים, ובכלל, לאינדוקס מרחבים geospatial ("גאוגרפיים"). עצי KD-Tree מסדר 2 מתארים מרחב גאוגרפי (x ו y), בעוד עד מדרגה 3 למשל, עשוי לתאר מרחב + זמן (למשל: היכן הייתה כל מונית בכל רגע נתון).

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

מבנה נתונים מקביל ל KD-Tree הוא ה R-Tree. בניגוד ל KD-Tree שבו כל node חוצה מרחב, ב R-Tree כל node מתאם מרחב תחום (Rectangle, ומכאן השם) ומכאן למרחבים שלו יכולים להיות חפיפות.

שווה להכיר בקיומו: Skip List

רשימת דילוג (Skip List) היא וריאציה של LinkedList הדומה יותר לעץ מאוזן (כמו עץ אדום-שחור או AVL) – אך המימוש שלה פשוט יותר.

מימוש פשוט לא מעניין אותנו כשיש שיתוף קוד (אחד כותב – רבים משתמשים). כמן כן, למדנו כבר להיזהר ממבני-נתונים עוייני cache כמו רשימות משורשרות ועצים. אז מה הטעם בו?

הייחודיות של ה Skip List היא ביכולת שלו לשרת כמבנה נתונים מוצלח למדי לעבודה מקבילית – תחום שהולך והופך חשוב ושימושי עם ריבוי ה cores בתעשייה.

בבסיס, רשימת דילוג היא כמו רשימה משורשרת. התבוננו רק על הרמה הראשונה (L1) – זו ממש רשימה משורשרת.
מה הבעיה ברשימה משורשרת (מלבד עוינות ל caches)? – שמציאת איבר ברשימה אורכת (O(n וזה יכול להיות יותר מדי.

הפתרון הוא להוסיף רמות דלילות לרשימה – שיאפשרו התקדמות מהירה בעת "סריקת" הרשימה.

הנה תסריט "צמיחת הרמה השנייה": כאשר אנו מוסיפים nodes לרשימה, אנו מבצעים הגרלה של 1:2 כמו הטלת מטבע. אם יצא "עץ" (במקור: "heads") נוסיף node גם ברמה השניה. כך תיווצר לנו רמה שניה דלילה יותר.
באופן דומה אם יש לנו 3 רמות, node שנוסף והוגרל להיות חבר ברמה 2, יוגרל שוב ביחס 1:2 להיות חבר גם ברמה 3.

מספר הרמות ברשימת הדילוג, ייקבע ביחס למספר האיברים שבה. גם ההגרלה (״רמת הדלילות״) לא חייבת להיות 1:2. היא יכולה, למשל, להיות 1:4 – רשימה דלילה יותר.

כאשר אנו מחפשים איבר, למשל בתרשים למעלה את מספר 8, אנו מתחילים מהרמה הגבוהה ביותר, ומבצעים חיפוש דומה מאוד לעץ בינארי. אם ה node הבא גדול מהערך שאני מחפש – נרד רמה ונבקש שם את ה node הבא – עד שמצאנו אותו (או בדוגמה לעיל – 8 לא נמצא ברשימה ולכן לא נמצא).

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

מקביליות

מכיוון שההחלטה כמה רמות להוסיף ל node חדש היא מבוססת על אקראיות (ולא תלויה בשאר המבנה של הרשימה) ל SkipList יש יתרון בהכנסה מקבילית של איברים, שבאמת יכולות להיות פעולה מקבילית ברמה גבוהה (כלומר: לאפשר הרבה מקביליות). במימוש בג'אווה (ConcurrentSkipListMap) משתמשים ב AtomicReference על מנת להגן על הקשר לשאר הרשימה – היכן שיכול להיות race condition. מעבר לכך אין צורך בשימוש ב synchronization או מנעולים (שמגבילים מאוד את כמות המקביליות).

חשוב לציין שהמבנה הזה אינו אידאלי לכל תסריט מקבילי. בג'אווה ה ConcurrentHashMap – מימוש HashTable עם מנעולים על טווחים על המערך שמאחורי-הקלעים, אולי לא יכול לעמוד באותה כמות מקבילית של הכנסות, אך שליפה של איבר היא פעולה מהירה בהרבה (O(k (מול (O(lgn ברשימת הדילוג).
אם למשל, המקביליות היא רק בקריאה – אזי HashMap רגיל יהיה היעיל ביותר.
בקיצור: מקביליות היא עניין מורכב, ולא נכסה אותו כאן…

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

סיכום

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

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

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

—–

[א] נכון, גם ג׳אווהסקריפט נפוצה מאוד – אבל קשה לי להתייחס לאלגוריתם המיון המובנה שבה ברצינות.

ראשית הוא ממיין ע״פ סדר לקסיקוגרפי, גם מערך של מספרים:

[7, 44, 3].sort() = [3, 44, 7]
עד ממש לאחרונה, מנוע V8 הסופר-פופולארי לא היה יציב. כלומר: הוא עשוי היה, באופן אקראי, להחליף בין ערכים שהם זהים. זה לא מפריע במספרים – אך עשוי להפריע באובייקטים מורכבים.
דוגמה אחרונה, וחמורה למדי, היא זו:

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

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

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

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

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

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

גם "Data Science בשקל" – יכול להיות שווה הרבה! (על Tableau)

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

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

למשל:

  • למצוא קשרים לא-צפויים בין נתונים, למשל: הידע שכרטיסי אשראי עם מאפיינים מסוימים אחראים לפי-19 הונאות משימוש בכרטיסים אחרים – הוא ידע שניתן להפוך אותו ליתרון עסקי.
  • היכולת לזהות שתקלה או מצב עומד להתרחש בעזרת סדרה של נתונים מקדימים.
  • היכולת לזהות שמקרה קצה מסוים לא מתרחש או כמעט ולא מתרחש – הוא הזדמנות לקחת החלטה במערכת ולא לתמוך במקרה הזה / לבצע אופטימיזציה עסקית או של ביצועי המערכת.
הדרך להשיג ידע שכזה היא לא קלה, ולרבות מההצלחות להשיג תובנה משמעותית – קודמים כמות ניסיונות כושלים.
בעקבות הטרנדים החמים היום של "Big Data" ושל "AI/ML" – מפתחים רבים מחליטים להשקיע ולהעשיר את הידע שלהם בכיוונים של Data Science.
לפעמים זה ידע תאורטי, לפעמים זו התנסות בסיסית ביצירת רשת ניורונים או Random forest.
בעזרת הטכנולוגיות הללו, נעשים בעולם דברים מדהימים – ואותם אנשי-תוכנה מקווים להגיע להישגים באזורים שלהם.
אני חושב שזו טעות טקטית נפוצה:

  • Data Science, בעיקרML ובמיוחד Deep Learning – הם תחומים עם עקומת למידה תלולה למדי, עדיין.
    • איש תוכנה יכול להשקיע עשרות ומאות שעות בלמידה ופיתוח skill – שעדיין יהיה בסיסי מאוד, יחסית למי שעוסק בתחום במשרה מלאה. לא יהיה לאיש התוכנה יתרון יחסי ברור מול איש-מקצוע ב Data Science, במיוחד לא כזה עם ניסיון לא-מבוטל.
    • אני מעריך שככל שהזמן יעבור – יהיה קל יותר ללמוד וליישם פתרונות Data Science, כך שייתכן ש 100 שעות למידה היום – יהפכו ל 20 שעות למידה בעוד 5 שנים. חלקים רבים מהידע שנלמד היום – יהפכו לכמעט-לא-חשובים, עבור מגוון נפוץ של יישומים / בעיות.
  • דווקא שיטות "פחות-מתוחכמות" של Data Science עשויות להניב לאיש התוכנה יתרון יחסי: שיטות כגון שאילתות SQL, סקריפטים שמעבדים ומנתחים נתונים, או כלי ויזואליזציה.
    • התחומים / שיטות הללו מפותחים כבר מאוד – קל ללמוד אותם מהר, ויש מגוון רחב מאוד של כלים ופרקטיקות שתומכים בהם.
    • יש כאן יתרון יחסי ברור של איש תוכנה המכיר את המערכת מקרוב:
      • הוא מבין את הנתונים (או לפחות חלקים מהם) – בצורה עמוקה.
      • נתון שאינו מכיר – הוא יכול למצוא את הקוד וללמוד בדיוק כיצד הוא מתנהג.
      • הוא יכול להוסיף נתונים ולטייב נתונים, ולהבין בצורה מהירה מה המורכבות של שיפור / טיוב נתונים שכאלו.
        • מה הבעיה ללכת לקוד ולבצע עוד כמה בדיקות / להזיז מקום את הקוד שאוסף נתונים – כך שיהיה מדויק יותר? – לאיש Data Science זוהי מלאכה קשה מאוד.
ארצה להציג דוגמה לשימוש בכלי Data Science "פשוט", שאינו קשור ללמידת מכונה או "Big Data". ספציפית, אסקור כלי בשם Tableau שאני משתמש בו לאחרונה.
Workbook לדוגמה מ Tableau Public
מקור: https://public.tableau.com/en-us/s/gallery/books-made-movies

למה טאבלו (Tableau)?

טוב, אז יש מגוון רחב של כלים לשליפה והצגת נתונים.
הכלי הבסיסי ביותר הוא client (למשל SequelPro או HeidiSql) – שאני מניח שכולנו עובדים איתו, מידי פעם.

אין דרך טובה לנהל את השאילות, ורבים מאיתנו מנהלים קובץ בצד שבו רשומות שאילתות SQL שאנו מעתיקים ומדביקים בכדי להריץ.

אין תחליף לכלי להרצת SQL (או שפה אחרת של בסיס הנתונים) – אבל כאשר אנחנו רוצים לחזור לנתונים, או לשתף אותם – זה לא מספיק טוב.

השלב הבא או כלים שינהלו את השאילתות עבורנו, יריצו אותם מדי פעם, וגם יאפשרו לשתף את התוצאה עם אנשים אחרים.

כלים דיי ידועים הם MyDBR או Redash (הישראלי / של יוצא GetTaxi) – שהם טובים ופשוטים, וקל מאוד להתחיל לעבוד איתם בזמן קצר.

אני אכתוב על Tableau שהוא "כלי BI", כלומר שהוא יקר יותר (תשלום ע"פ מספר משתמשים, 30-70 דולר בחודש למשתמש), וההטמעה שלו היא מורכבת יותר.

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

בחרתי לדבר דווקא על Tableau כי זה כלי שנבחר לעבודה במקום העבודה הנוכחי שלי. יש לנו גם Redash – אבל בטאבלו אפשר לעשות יותר.
יש עוד סדרה של כלים דומים ל Tableau, כמו MicroStrategy, Qlik, או SiSense (גם חברה ישראלית). הכלים הללו, כמובן, הם לא שקולים לגמרי – ולכל כלי יש את החוזקות היחסיות שלו.

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

לטאבלו יש כמה גרסאות, אך אני רוצה לציין את החשובות שבהן:

  • Tableau Desktop – אפליקציית Desktop לזריזות וגמישות מרביים. זה הרישיון היקר יותר.
  • Tableau Server – גרסה וובית ומצומצמת יותר של גרסת ה Desktop. השיתוף הוא קל יותר – והרישיון עולה כחצי מחיר. רישיון של Tableau Desktop כולל גם רישיון ל Tableau Server על מנת לשתף את המידע.
  • Tableau Public – גרסה חינמית של ה Desktop, שניתן להשתמש בה רק מול שרת ציבורי של טאבלו בו הנתונים יהיו נגישים לכל העולם, וכמות מוגבלת של נתונים (15 מיליון רשומות).

ב Tableau Public אתם יכולים להגביל את הגישה של משתמשים אחרים לנתונים / לקוד המקור (ה Workbook) – אם כי משתמשים רבים מתירים את ההורדה.

בכל מקרה, זו בהחלט לא סביבה מתאימה להעלות מידע רגיש עסקית – כי בעקבות תקלה מישהו יוכל לגשת למידע הזה, ורמת האבטחה – לא מובטחת.

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

כמה טיפים חשובים על טאבלו שיאפשרו לכם כניסה מהירה יותר

Undo הוא חברכם הטוב 

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

להבין את ההבדל בין Measures ל Dimension

זה קצת מבלבל בהתחלה:

  • Measure הוא נתון שאנו רוצים להציג אותו, או בד"כ – Aggregation שלו (כמו SUM, AVG, אחוזון מסוים, וכו'). מכירות, אחוז הצלחה, וזמן ריצה – הם measures קלאסיים.
  • Dimension הוא נתון שלפיו אנחנו רוצים לפלח את הנתונים ולהציג אותם כשורה / עמודה / אזור בגרף.
    למשל: תאריך (שנה / חודש / יום), מיקום גאוגרפי, קטגוריה, סטטוס (הצלחה / כישלון) וכו' – הם dimension קלאסיים.
איך יודעים מה זה מה? – זה לא כ"כ חד משמעי.

טאבלו ינחש בצורה "תבונית" מה הוא מה – ויקטלג לכם אותם ב Data pane:
טאבלו יטעה מדי פעם – ויהיה עליכם לתקן אותו, ע"י פעולות ה"Convert to Measure" או "Convert to Dimension".
Measures יהיו בד"כ מספרים – עליהם באמת אפשר לבצע Aggregations.
Dimension יהיו בד"כ מחרוזות ותאריכים.
אבל מה אם אני רוצה להשתמש בנתון מספרי טהור, כמו זמן ריצה – כ dimension? לדומה להציג תהליכים מהירים ואטיים בנפרד?
במקרה הזה עליכם ליצור Bins (בתפריט של פריט המידע: …create/bins), שהוא בעצם שדה חדש המקטלג טווחים של הנתון (הרציף, עם אינספור ערכים) שבחרתם.
בטאבלו, כחצי מהזמן שמשקיעים בויזואליזציה יהיה בארגון הנתונים בצורה שטאבלו ידע לעבוד איתם בצורה נכונה. זה תהליך של ניסוי-וטעיה, שמתרחש תוך כדי בניית הויזואליזציה.

לטובת טאבלו שלאחר שרוכשים קצת מיומנות, ובהנחה שמכירים את הנתונים – בשעה של עבודה אפשר ליצור Dashboard אטרקטיבי ושימושי על מידע דיי מורכב.

להבין את ההבדל בין Columns, Rows, ל Marks

גם זה מאוד בסיסי, אם כי מעט מבלבל בהתחלה.

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

באופן הזה מאוד קל לחשוב על טורים ועמודות כמימדים שונים בהם אתם עושים חישוב – ו marks – כנתונים (measures) שאותם נרצה להציג:

טור ושורה הם שני מימדים שמאוד קל להבין במבנה של טבלה.
הרבה פעמים נרצה 3 ויותר מימדים.

הנה הוספתי לטבלה הנ"ל עוד שני מימדים נוספים:

ההפרדה בין עמודות ושורות היא פחות חשובה, ההפרדה החשובה היא בין מימדים ל Marks, שלרוב יהיו גם מימדים ו measures.

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

Customer הוא אחד ה Segments, ומתחתיו ניתן לראות את השנים.

בויזואליזציות אחרות, הם ההבחנה בין טור ועמודה – עשויים להיראות קצת אחרת.

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

הנה אותה הטבלה בדיוק, כאשר אני מציג כ 3 measures כ marks שונים:

  • סכום העסקאות – כגדול הסימון (עיגול).
  • מספר העסקאות – כטקסט (label). הביטוי CNTD הוא קיצור של Count Distinct.
  • אחוז הרווח – כצבע (gradient), כאשר כחול הוא רווח, וכתום הוא הפסד. כתום גדול = הפסד גדול!

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

עוד Marks שניתן להשתמש בהם הוא סוג הצורה (בשימוש ב Shapes) או tool-tip שמופיע ב popup כאשר מצביעים על האיבר.

Show Me הוא כלי חשוב – לא רק למתחילים!

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

בפינה הימנית עליונה נמצא כפתור Show Me – שעוזר לי לדעת למה אני זקוק.
עבור היסטוגרמה, אומרים לספק measure אחד (קל!) – ומודיעים לי שטאבלו ייצור bin field מתאים. יש גם אזהרה שלא כל measure יעבוד.

אני זורק את ה measure של Sales לאחד המימדים (עמודות או שורות – לא משנה) – טאבלו אוטומטית מנחש שאני רוצה לעשות לו aggregation של Sum.
אח"כ אני לוחץ ב Show Me על גרף ההיסטוגרמה – ומקבל את התוצאה הבאה:

הערה: שיניתי את השנתות של ציר ה Y ל logarithmic scale – אחרת היה קשה להבחין בערכים השונים.

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

מה הצבעים ירוק וכחול אומרים?

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

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

למשל: אם ציר ה X שלכם הוא חודש בשנה, ומופיעות שנתות לערכים 0 ו 13 – זה בגלל שהתאריך הוא שדה רציף. הפכו אותו לבדיד – וזה יסתדר.

השתמשו ב Calculated Fields

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

למשל, הנה סקריפט פשוט שיוצר מימד חדש מכמה שדות (שמותיהם – בכתום):

היה לי קשה יותר לבנות את המימד הזה בדרך אחרת / SQL query.

לטאבלו יש רשימה של פונקציות זמינות, ותחביר שמזכיר כתיבת פונקציות ב SQL – בהם ניתן להשתמש ב calculated fields. שימו לב שחלק מהפונקציות זמין רק מול data sources ספציפיים כמו Hive או Google BigQuery (המספקים את הפונקציות בצורה טבעית)

עבור חישובים מורכבים יותר אפשר להשתמש בשפת R – שפת תכנות לכל דבר ועניין.
כדי לכתוב Calculated Fields בשפת R יש להתקין מנוע חישובי בשם RServe המריץ את R. טאבלו ישלח את הנתונים ל RServe – שיבצע את החישוב של השדה הנתון – ויחזיר את התוצאות.

SCRIPT_STR(`substr(.arg1, regexpr(" ", .arg1) -1 )`, ATTR([Business Name ]))

הפונקציה SCRIPT_STR שולחת ל R ביטוי בשפה העטוף במירכאות + פריט המידע שאותו יש לעבד – ומחזירה תשובה מסוג מחרוזת. האינטגרציה היא סבירה – אבל לא מצוינת. למשל: איתור תקלות היה יכול להיות פשוט בהרבה.

השתמשו ב Filters

בכל ויזואליזציה – ניתן "לגרור" שדות לאזור ה "filters" ולסנן לפי ערכים מסוימים של השדה הזה. זה שימוש אחד ויעיל ל Filters.

שימוש נוסף חשוב הוא ב Dashboards, כאשר אני מצרף כמה ויזואליזציות ובמקום אחד יכול לפלטר את כולם באותה הצורה. מה שנחמד שה Filters ב Dashboard מופיעים ב View Mode (אם לא סילקנו אותם משם) – וכך הקהל הרחב של המשתמשים יכול להשתמש בהם, מבלי להכנס לעומק ה Data Model.

הנה דוגמה של Dashboard פשוט שיצרתי מ-2 הויזואליזציות הנ"ל:

הוספתי Filter דרך אחד מהויזואליזציות (תפריט = חץ למטה/filters – מציג לי את כל המימדים / measures שבשימוש ולכן ניתן לפלטר לפיהם).

בשלב הבא, אני משייך את הפילטר (דרך התפריט שלו) – לכל הנתונים על ה Dashboard:

עכשיו אפשר לראות שצמצום השנים בעזרת הפילטר – משפיע על כל הנתונים ב Dashboard. איזה יופי!

סיכום

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

הוא כלי רב-עוצמה, אך לא מורכב כ"כ לשימוש.

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

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

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