תכנות מתקדם ב-Java/מבני נתונים מתקדמים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
Johnny Zoo (שיחה | תרומות) |
אין תקציר עריכה |
||
שורה 2:
{{בעבודה}}
בפרק זה נלמד על נושאים שמתקרבים גם לענפים התיאורטיים יותר של מדעי המחשב, והם בעלי השלכות חשובות לתוכניות שתכתבו. נכיר כמה מושגים מעולם מדעי המחשב, ונראה כמה דרכים מתקדמות יותר לאחסון של מידע.
{{הארה|כל החישובים וההגדרות שמופיעים בפרק זה אינם פורמליים ומובאים אך ורק למטרת היכרות בסיסית עם הנושא. }}
==יעילות==
שורה 74 ⟵ 76:
המימוש של תורים ומחסניות אינו קבוע. התנאי הוא שכל מימוש חייב ליישם את הממשק שפורט למעלה (הכנסת איבר וכדומה). מימוש נפוץ הוא בעזרת רשימה מקושרת.
====יעילות====
תורים ומחסניות הם מבני נתונים מופשטים, שמימושם אינו קבוע. לכן, גם הסיבוכיות של השימוש בהם משתנה ותלויית מימוש. המימוש הנפוץ, בעזרת רשימה מקושרת (בתור - רשימה דו כיוונית), מאפשר הכנסה, הוצאה, ובדיקת ריקנות בעלות של <math dir="ltr">\displaystyle O(1)</math>.
===עצים בינאריים===
שורה 97 ⟵ 102:
* מצב בעייתי יותר הוא כאשר לאותו קדקוד יש צאצא אחד. במקרה זה, אפשר לפתור את הבעייה בעזרת החלפת האיבר שרצינו למחוק עם הצאצא שלו (חשבו: מדוע העץ נשאר מסודר?).
* המצב המסובך ביותר הוא כאשר לקדקוד אותו רצינו למחוק יש שני צאצאים. מבנה העץ הבינארי מבטיח לנו שהאיבר הבא בעץ, מבחינת הסדר שקבענו, הוא הצאצא השמאלי ביותר של הצאצא הימני של אותו איבר (כי הצאצא הימני וכל הצאצאים שלו גדולים מהאיבר שלנו, וידוע גם כי הצאצא השמאלי ביותר הוא גם הקטן ביותר). נחפש את אותו איבר, נחליף את ערכו של האיבר שרצינו למחוק בערכו של איבר זה, ואז נמחק אותו. באופן דומה, ניתן להשתמש גם באיבר הקודם בעץ (שהוא הצאצא הימני ביותר של הצאצא השמאלי).
=====מעבר על כל העץ=====
ישנן כמה שיטות למעבר על כל איברי העץ הבינארי (נניח - כאשר רוצים להדפיס את כל איברי העץ). הרעיון הוא לעבור באופן רקורסיבי על כל איבר בעץ, להדפיס אותו, ולהתקדם אל הצאצאים שלו. ההבדל בין השיטות נובע מסדר הפעולות - האם מבקרים קודם בתת העץ הימני, בתת העץ השמאלי, או שתחילה מדפיסים את תוכן התא.
====יעילות====
בפעולות של הכנסה, מחיקה, וחיפוש איבר בעץ, אפשר לראות שמתבצע מעבר על קדקודי העץ, מראש העץ ועד מציאת האיבר הרצוי (כמו שכבר הוסבר קודם, פעולת המחיקה אמנם עשויה לדרוש שני חיפושים ולא אחד, אך מבחינת הסיבוכיות אין הבדל). ההנחה היא שפעולות על הקדקודים כמו הדפסה, מחיקה, או מציאת הצאצאים (וההורה) של קדקוד מסויים מתבצעות בסיבוכיות של <math dir="ltr">\displaystyle O(1)</math>. אם כך, המקרה הגרוע ביותר עבורנו, בו כל קדקודי העץ ממוקמים בזה אחרי זה ידרוש מעבר על כל איברי העץ. אם n הוא גודל העץ, סיבוכיות המקרה הגרוע היא <math dir="ltr">\displaystyle O(n)</math>. עם זאת, זה לא מקרה נפוץ. במקרים רבים צורת העץ תהייה מאוזנת יותר, וכך נשיג סיבוכיות ממוצעת של <math dir="ltr">\displaystyle O(Log(n))</math>. כדי לשפר את ביצועי העצים הבינאריים, פותחו עצים מתקדמים יותר (למשל: עצים אדומים-שחורים), שבמחיר נמוך יחסית מבטיחים איזון של העץ. רוב המימושים הקיימים של עצים בינאריים מתבססים על עצים מאוזנים.
מעבר על כל העץ, מטבעו, דורש מעבר על כל האיברים בעץ, ולכן יעלה במחיר של <math dir="ltr">\displaystyle O(n)</math>.
===טבלת גיבוב===
[[w:he:טבלת גיבוב|טבלת גיבוב]] (Hash Table) היא מבנה נתונים המאפשר הכנסה ושליפה מהירה של נתונים, באופן הדומה למערך: עבור כל נתון (גם נתון שלא נמצא בטבלה) קיים מספר סידורי ידוע, אליו נכניס את הנתון, ואם נרצה לשלוף אותו - נדע ששם הוא צריך להיות. מסיבה זו, לפעמים מכונה טבלת גיבוב גם "מערך אסוציאיטיבי".
חלק קריטי בשימוש בטבלה כזו הוא מציאת הדרך בעזרתה נדע לחשב את אותו מספר סידורי עבור כל נתון. לשם כך, משתמשים בפונקציה מתמטית בשם "[[w:he:פונקציית גיבוב|פונקציית גיבוב]]", שבהינתן קלט מסויים - תדע להמיר אותו למספר. הערה: בהקשרים אחרים, הגדרת פונקציית גיבוב והשימושים בה רחבים יותר ממה שנראה כאן.
===פונקציית הגיבוב===
פונקציית הגיבוב היא פונקציה שמטרתה להפיק מספר סידורי מנתון. כדי להשיג פונקציה בה ניתן להשתמש, נדרוש שיתקיימו בה שתי תכונות:
* עבור שני נתונים זהים, הפונקציה תחזיר מספר זהה.
* במידת האפשר, עבור שני נתונים שונים, הפונקציה תחזיר מספר שונה.
לדוגמה: עבור מחרוזות, אפשר להחליט כי ערך המחרוזת יחושב באופן הבא: ערכה של כל אות יהיה שווה למיקומה בא"ב (למשל: א=1, ב=2, וכן הלאה) כפול גודל האלפבית בחזרת מיקומה במילה. למשל, נחשב את ערך המילה "שלום". מכיוון שמדובר באלפבית עברי, גודלו הוא 26 (כולל הסופיות).
* ש=21. האות הראשונה במילה, ערכה מוכפל ב-1.
* ל=12. האות השנייה במילה, ערכה מוכפל ב-26.
* ו=6. האות השלישית במילה, ערכה מוכפל ב-26*26 = 676.
* מ=13. האות השלישית במילה, ערכה מוכפל ב-26*26*26 = 17576.
סך הכל: 21 * 1 + 12 * 26 + 6 * 676 + 13 * 17576 = 232877.
התחום של פונקציות הגיבוב הוא תחום שניתן להעמיק בו רבות. בג'אווה, המחלקה Object מכילה את השיטה hashCode, וכל אובייקט קיים כבר מממש אותה, כך שאין צורך לכתוב אותה עבור מחלקות כמו String.
===השימוש בטבלת הגיבוב===
כאשר יש לנו פונקציית הגיבוב, שאר העבודה הוא פשוט למדי: כשנרצה להכניס נתון מסוים, נחשב את מספרו הסידורי בעזרת פונקציית הגיבוב, ולתא שזה מספרו נכניס את הנתון. כאשר נרצה לשלוף נתון, נחשב את מספרו הסידורי, ולפי זה ניגש לתא הרצוי ונשלוף משם את הנתון.
עם זאת, יש כאן בעייה נוספת: ייתכן שהמספר הסידורי שקיבלנו עובר את גודלה של הטבלה בה אנו משתמשים לאחסון. הפתרון הנפוץ: שימוש בפונקציית המודולו (שארית).
למשל: נניח שנרצה להכניס לטבלה בגודל 15 (לשם הפשטות, נניח שמספרי התאים הם 1 עד 15) את המספרים הסידוריים 13, 17, ו-33.
13 מודולו 15 שווה ל-13, ולכן נכניס אותו לתא מספר 13. 17 מודולו 15 שווה ל-2, לכן נכניס אותו לתא מספר 2. 33 מודולו 15 שווה ל-3, לכן נכניס אותו לתא מספר 3.
===ניהול התנגשויות===
כאן מתעוררת בעייה נוספת: ומה אם שני נתונים שונים יקבלו מספר זהה? את הבעייה הזו אפשר לפתור באחת משתי דרכים:
* '''טבלה פתוחה''' - כאשר אנו מנסים להכניס נתון חדש לטבלה ומגלים שהמקום הרצוי (כלומר, המקום שאת מספרו מצאה פונקציית הגיבוב) כבר תפוס, נמשיך לתאים הבאים עד שנמצא תא פנוי ובו נמקם את הנתון. כאשר נרצה לחפש נתון, נתחיל במקום בטבלה אליו תפנה פונקציית הגיבוב ונבדוק אם האיבר שרצינו למצוא נמצא שם. אם התא תפוס אך האיבר שלנו לא שם - נמשיך הלאה עד שנמצא אותו (או עד שנגיע לתא ריק ונוכל לדעת שהוא לא נמצא).
שורה 107 ⟵ 140:
כמו תמיד, יש יתרונות וחסרונות בכל אחת מהשיטות האלו.
====יעילות====
טבלת הגיבוב היא מבנה שיעיל במיוחד להכנסה ושליפה של נתונים בעלי מפתח ידוע. בהנחה שעלותה של פונקציית הגיבוב היא <math dir="ltr">\displaystyle O(1)</math>, נוכל להשיג עלות הכנסה, שליפה ומחיקה קרובות ל-<math dir="ltr">\displaystyle O(1)</math>.
====יתרונות וחסרונות====
יתרונה הגדול של טבלת הגיבוב הוא במהירות הגדולה של ביצוע הפעולות הבסיסיות - הכנסה, הוצאה, ושליפה. תכונה זו הופכת את טבלת הגיבוב למבנה נתונים מצויין במקרים רבים. עם זאת, גם טבלת גיבוב סובלת מחסרונות. החסרון הראשון הוא שכמות גדולה של נתונים פוגעת בביצועי הטבלה. למשל: אם בטבלה פתוחה שגודלה 10 נכניס 1000 נתונים, אז אפילו אם החלוקה טובה מאוד ובכל מקום בטבלה יהיו בדיוק 100 נתונים, עדיין - שליפה של כל נתון תעלה במחיר של מעבר לאורך רשימה באורך 100. זוהי בעייה שניתנת לפיתרון באמצעות הגדלת הטבלה כאשר כמות הנתונים חוצה רף מסויים.
בעייה אחרת של הטבלה היא המוגבלות של שליפת הנתונים. למשל: בספר טלפונים המבוסס על טבלת גיבוב, לא ניתן לחפש את כל האנשים ששמם מתחיל ב-"ד" (בלי לעבור על כל הרשומות בטבלה), או להדפיס את תוכן הספר על פי סדר האלפבית (מבלי להעתיק קודם את תוכן הספר למבנה נתונים אחר).
===
מבני נתונים הוא תחום רחב, ועם השנים פותחו הרבה מאוד מבני נתונים מעניינים, כאשר רבים מהם מבוססים, בצורה כזו או אחרת, על אלו שכבר ראיתם.
מומלץ מאוד להכיר מבני נתונים רבים, בנוסף לאלו שראיתם כאן, כיוון שעבור מצבים שונים מתאימים מבני נתונים שונים. שימוש במבנה נתונים נכון (שייתכן שתצטרכו לכתוב אותו בעצמכם!) יכול לגרום להבדל עצום בביצועים.
{{תכנות מתקדם ב-Java|מוגבל}}
| |||