מבנה נתונים

מבני נתונים שכל מפתח חייב להכיר

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

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

רשימה (List)

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

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

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

int[] build_array() {
    List<int> list = new List<int>();
    // fill the list with values
    return list.ToArray();
}

מילון (Dictionary)

ללא ספק הזוכה הבלתי מעורער בתואר מבנה הנתונים האהוב עליי ביותר. מילון (לעתים נקרא גם Map או Associative Array) הינו אוסף של זוגות מפתח-ערך (key-value), ולרוב מאפשר ערך יחיד לכל מפתח. יתרונותיו העיקריים הינם הכנסה ושליפה יעילים:

d = dict()
d["hello"] = "world"
d["bye"] = "bye"
print d["hello"] // prints "world"
print "bye" in d // prints True
for key, value in d.iteritems():
    print key, "=>", value

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

מילון ממומש לרוב באמצעות טבלת גיבוב (Hash Table), ולכן המפתחות שלו הם מסוג Immutable (לא ניתנים לשינוי, ראו בהמשך), למשל מספרים או מחרוזות ולא מחלקות או רשימות. בנוסף יש שפות תכנות בהן הטיפוס של המפתחות והערכים הם קבועים ומוגדרים מראש (C#, Java, C++ ועוד).

בעוד שרוב שפות התכנות העיליות מספקות מימוש של מילון כחלק מהספרייה הסטנדרטית שלהן, לא כולן כאלו (C++ לדוגמה). מקרה מעניין הוא שפת Javascript, אשר לא מכילה מימוש של מילון במדוייק, אבל הטיפוס הבסיסי בה, Object, משמש בפועל כסוג של מילון שהמפתחות שלו הן מחרוזות:

var obj = {};
obj[1] = "value";
alert(obj["1"]); // "value"

קבוצה (Set)

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

Set<String> processed_names = new HashSet<String>();

for (String name : name_array) {
    if (!processed_names.contains(name)) {
        System.out.println(name);
    }
    processed_names.add(name);
}

דוגמה נוספת בשפת python היא מחיקת כפילויות מרשימה בשורה אחת:

list_without_duplicates = list(set(list_with_duplicates))

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

בדומה למילון, גם קבוצה לרוב משתמשת בפונקציית hash על האיברים, ולכן הם חייבים להיות Immutables (ראו בהמשך).

תור (Queue)

מקרה פרטי של מערך, המאפשר הכנסה מהירה מצד אחד (push) ושליפה מהירה מצד שני (pop). בדומה לשמו, תור משתמש רבות לייצוג "תור" של משימות לביצוע. ייתרון נוסף של תור הוא שבחלק משפות התכנות הוא ממומש באופן thread-safe, כלומר בטוח לשימוש ב-threads שונים במקביל (ולפעמים אף בתהליכים שונים במקביל).

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

Immutables

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

  1. חישוב hash על מבנה הנתונים ושימוש כמפתח במילון או איבר בקבוצה1.
  2. ביצוע השוואה בזמן קבוע בין שני מופעים של מבנה הנתונים ע"י שימוש ב-hash.
  3. מניעת שינוי הערכים בטעות.
  4. חיסכון במשאבים ע"י שימוש חוזר במבני נתונים נעולים.

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

בחלק משפות התכנות קיימים מבני נתונים מקבילים לאלו שסקרנו, שההבדל היחיד ביניהם הוא שלא ניתן לשנות את הערכים שלהם לאחר היצירה הראשונית. למשל בשפת python, רשימה מסוג immutable נקראת tuple, וסט מסוג immutable נקרא frozenset. שפת Javascript לדוגמה לא מכילה אף מבנה נתונים כזה, אך קיימת ספרייה בשם Immutable.js המכילה מימושים של מבני נתונים רבים שכולם לא ניתנים לשינוי.

מבני נתונים נוספים

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

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

טבלה מסכמת

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

Java Python C++ Ruby Javascript C#
מערך Array array Array Array Array Array
רשימה LinkedList list* std::list Array* Array* List
מילון HashMap dict std::map Hash Object Dictionary
קבוצה HashSet set std::set Set HashSet
תור LinkedList / PriorityQueue Queue std::queue Queue Queue
מערך Immutable ImmutableList (Guava) tuple freeze(Array) Immutable.js ImmutableArray

* רשימה בשפת python ממומשת באמצעות מערך דינאמי. בשפות Ruby ו-Javascript ניתן להשתמש במערך, למרות שהוא איננו ממומש כרשימה.

סיכום

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

 

 

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

10 תגובות בנושא “מבני נתונים שכל מפתח חייב להכיר”

כתיבת תגובה

האימייל לא יוצג באתר. (*) שדות חובה מסומנים