יסודות מדעי המחשב — מרחב למידה אישי

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

מילונים (Dictionaries) – אחסון מפתח-ערך

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

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

מאפיינים עיקריים:

מפתחות ייחודיים: לא יכולים להיות שני מפתחות זהים במילון.
גישה מהירה: פעולות הכנסה, שליפה ומחיקה מתבצעות בדרך כלל בזמן ממוצע קבוע (O(1)).
סדר לא מובטח (באופן כללי): ברוב המימושים, סדר הוספת הפריטים אינו נשמר (אך ב-Python 3.7 ואילך, מילונים שומרים על סדר ההכנסה).
מפתחות ניתנים לגיבוב (Hashable): המפתחות חייבים להיות אובייקטים בלתי ניתנים לשינוי (immutable) ובעלי פונקציית גיבוב (hash function).

פעולות בסיסיות:

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

קבוצות (Sets) – אוספים ייחודיים

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

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

מאפיינים עיקריים:

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

פעולות בסיסיות:

הוספת איבר.
הסרת איבר.
בדיקת חברות (האם איבר קיים בקבוצה).
פעולות קבוצתיות: איחוד (union), חיתוך (intersection), הפרש (difference), הפרש סימטרי (symmetric difference).

ביצועים ומימוש: טבלאות גיבוב

היעילות הגבוהה של מילונים וקבוצות נובעת ממימושם באמצעות טבלאות גיבוב (Hash Tables).

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

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

האתגר המרכזי: התנגשויות (Collisions)

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

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

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

פתרון התנגשויות:

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

גורם עומס (Load Factor):

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

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

בחירת מבנה הנתונים הנכון

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

רשימה (List)

אוסף מסודר של איברים, עם אינדקסים מספריים. גישה לפי אינדקס היא O(1), אך חיפוש איבר או הכנסה/מחיקה באמצע הרשימה היא O(N).

מילון (Dictionary)

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

קבוצה (Set)

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

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

שאלות לדיון

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

נקודות לתשובת מודל

מילון מול רשימה: מילון יעיל לחיפוש/גישה לפי מפתח לא מספרי (למשל, שם), בעוד רשימה טובה לגישה לפי אינדקס מספרי. מילון מספק O(1) ממוצע לחיפוש, רשימה O(N).
פונקציית גיבוב גרועה: פונקציה שמחזירה את אותו אינדקס עבור רוב המפתחות (למשל, תמיד 0) תגרום לכל האיברים להצטבר באותו תא. זה יהפוך את טבלת הגיבוב למעשה לרשימה מקושרת ארוכה, וידרדר את ביצועי כל הפעולות ל-O(N).
פתרון התנגשויות:
- שרשור: כל תא הוא רשימה. יתרון: פשוט יותר למימוש, פחות רגיש לגורם עומס גבוה. חיסרון: דורש זיכרון נוסף למצביעים, גישה לכל רשימה היא O(k) כאשר k הוא אורך הרשימה.
- כתובות פתוחות: מחפשים תא פנוי בטבלה עצמה. יתרון: ניצול זיכרון טוב יותר (אין מצביעים), לוקליות טובה יותר. חיסרון: רגיש יותר לגורם עומס, דורש אסטרטגיית חיפוש מורכבת, בעיות אשכולות (clustering).
אובייקטים ניתנים לגיבוב: מפתחות חייבים להיות hashable מכיוון שפונקציית הגיבוב צריכה להחזיר ערך קבוע עבור אותו אובייקט. אובייקטים משתנים (mutable) כמו רשימות אינם hashable כברירת מחדל, כי שינוי בהם ישנה את ערך הגיבוב שלהם, מה שימנע מציאתם במילון. דוגמה: רשימה [1, 2] אינה יכולה להיות מפתח.
מטריצה דלילה: ניתן לייצג באמצעות מילון שבו המפתח הוא זוג קואורדינטות (שורה, עמודה) והערך הוא הערך בתא. לדוגמה: {(0, 2): 5, (1, 0): 3}. גישה לאיבר היא O(1) בממוצע, שכן המילון מאפשר גישה ישירה לפי המפתח (שורה, עמודה).

מצאתם טעות או שחסר משהו?