אחד מהנושאים הראשונים שמתכנת מקצועי מתבלט מעל מתכנת מתחיל הוא השליטה במבני נתונים. כדי לפתור בעיות בצורה נכונה וביעילות, יש צורך לשלוט במבני נתונים ולהשתמש בהם נכון.
בפוסט זה נעבור בצורה קלילה מאד על מבני נתונים נפוצים בתכנות וכמו תמיד, תהיה הפנייה להמשך הרחבת ידע למי שצריך.
למה בכלל צריך להכיר מבני נתונים ?
כדי לפתור בעיה ביעילות נדרש אלגוריתם יעיל ומבני נתונים יעיל.
מבני נתונים משמש כלי לשמירת ידע בתוך הקוד בצורה שקל לאחסן בה וקל לשלוף ממנה מידע. במידה וזה לא כך, הקוד יצטרך לחפות על חיסרון מבנה הנתונים ולהיפך.
מתכנתים מתחילים נוטים לדחוף הכל לתוך מערכים פשוטים ולכתוב קוד שינהל את זה. זה אפשרי, אבל זה מכוער, לא מקצועי ולא יעיל.
כמו בחיים, אין מבנה נתונים מושלם. כמעט לכל מבנה נתונים יש חיסרון מסוים. לכן, חשוב לדעת איך להשתמש ולבחור את מבנה הנתונים הנכון.
באופן כללי, מבני נתונים לחלקים לשניים: Ordered ו- Unordered.
Ordered זה אומר שלאיברים במבנה הנתונים יש סדר קבוע ואם נרוץ בלולאה ונדפיס את כל האיברים - נקבל את אותו הפלט. לרוב, הסדר יהיה ע"פ אינדקס אך לא בהכרח.
Unordered זה אומר שאין חשיבות לסדר האיברים. כל האיברים קיימים במבנה לפי חלוקה כלשהי אך אין התחייבות לסדר מסויים עבור כל האיברים. אם נרוץ בלולאה על המבנה, נקבל בכל פעם סדר שונה לאיברים.
בנוסף, חלק ממבני הנתונים הם סטטים - הגודל שלהם נקבע בהגדרה שלהם והוא נשאר כך עד לסוף חיי המבנה. מבני נתונים אחרים הם דינאמיים והגודל שלהם ניתן לשינוי תוך כדי ריצה וניתן להוסיף או להוריד להם איברים לפי הצורך.
מערך - Array
מבנה הנתונים הבסיסי ביותר. הוא מצטיין בזמן גישה יעיל של (1)O לכל איבר במערך. קל מאד לסרוק אותו או להגיע לתחילתו או לסופו והוא יחסית תופס מעט מקום בזיכרון.
החיסרון שלו מתבטא בכך שהוא תופס מקום קבוע בזיכרון, גם אם אין צורך בכל המקום בו הוא משתמש. במילים אחרות, הוא לא דינמי אלא סטטי. הוא דורש מקום רציף בזיכרון בזמן האיתחול וכל המקום הזה יישאר מוקצה למערך עד לשיחרורו. בנוסף, כל תא במערך יכול להכיל רק ערך אחד מאותו type.
מערך דינמי - Dynamic Array
מערך משודרג עם תוספת של קוד מאחוריו שגורמת לו להגדיל את עצמו עם הוספת נתונים. זה נשמע טוב אך במציאות הגדלת המערך היא לא יעילה ודורשת הקצאה חדשה של מערך חדש והעתקת כל המידע מהמערך הישן לחדש.
נוכל להגיד שיעילות הוספת ערך למערך דינאמי היא (1)O אך רק בממוצע מכיון שמקובל להגדיל את המערך לפי 2 מגודלו בכל פעם שנגמר המקום - כך שמאורע הרחבת המערך אמור להיות נדיר.
רשימה מקושרת - Linked List
מבנה נתונים דינמי שכולל שרשרת איברים הקרואים לרוב Nodes המכילים ערך ומצביע לאיבר הבא. רשימה מאותחלת אינה חייבת להגדיר את כמות האיברים שלה וניתן להוסיף לה בקלות איברים חדשים לסוף הרשימה. כל איבר יכול להכיל כל ערך.
ניתן לשמור מצביע לתחילת הרשימה ולסופה, או במקרים מסויימים גם לאיבר הקודם, במקרה של רשימה דו-כיוונית אך בכך זה מסתיים. אין אפשרות פשוטה להגיע לאמצע הרשימה או לאיבר ספציפי בה, חוץ מלסרוק אותה לאורכה או לשמור מצביעים נוספים לכל מיקום רצוי.
מסיבה זו, קל להוסיף איברים לתחילת או לסוף הרשימה ביעילות גבוהה (1)O אך הוספה לכל מיקום אחר תעלה כבר O של n.
מחסנית - Stack
מבנה נתונים דומה לרשימה מקושרת, רק שכאן יש הגדרה קבועה לגבי צורת שליפת המידע מתוך מבנה הנתונים. ארגון המידע עובד בשיטת LIFO - מי שנכנס אחרון יוצא ראשון - בדומה למחסנית של כלי נשק.
הוספה והסרה מהמחסנית תעלה (1)O אך לחפש ערך מסוים במחסנית יעלה תמיד O של n.
תור - Queue
מבנה נתונים שעובד על אותו עיקרון כמו מחסנית, רק לפי כללי FIFO - מי שנכנס ראשון יוצא ראשון - בדומה לכל תור רגיל שאתם עומדים בו.
גם כאן - הוספה והסרה יהיו יעילים, אך כל חיפוש על התור ידרוש מעבר על כולו.
עץ בינארי - Binary Tree
'עצים' הם מבנה משודרג של רשימה מקושרת שמתחיל מצומת (node) שהוא ה-שורש (root) של העץ ומתפצל כלפי מטה. כאשר כל אחד מצמתי העץ מחזיק ערך יחיד ושני מצביעים שמצביעים על שני ערכים אחרים.
מקובל לצייר עץ מלמעלה למטה כאשר כל צומת מקושרת לצומת אחרת מימין או משמאל - לכן השם 'עץ' כיון שמבנה הנתונים המצויר מזכיר עץ.
עץ בינארי הוא רק דוגמא אחת לסוגי עצים רבים אחרים אבל מקובל להזכיר אותו מכיון שהוא שומר על יעילות של O של log n בחיפוש אחרי ערך ספציפי.
בעץ בינארי, הערכים אינם מוכנסים אחד אחרי השני כמו ברשימה אלא מסודרים ע"פ הערכים שבהם בתהליך ההכנסה ולכן הם נחשבים מבנה נתונים יעיל לחיפוש, בניגוד לרשימה מקושרת למשל.
טבלת גיבוב - Hash Table
טבלת גיבוב היא מימוש מתוחכם יותר שמשתמש בפונקציה כדי להכניס באופן דינאמי ערכים לתוך המבנה בזיכרון. הערך המאוחסן (value) יקבל ערך במבנה ע"פ מפתח (key) שלרוב יהיה פשוט string שייצג את הערך המאוחסן.
ישנם דרכי מימוש שונות לטבלה כזו, אך מקובל לתאר אותה כמערך רגיל שמאחסן את הערכים המוכנסים לטבלה, אך בניגוד למערך רגיל, בו המשתמש בוחר אינדקס לאחסון הערך - בטבלה האינדקס מנוהל ע"י פונקציה (פונקצית גיבוב) שדואגת שהערכים יפוזרו באופן אחיד ע"י המערך.
כאשר כל התאים מתמלאים במערך, או לחילופין כאשר הפונקציה מובילה שני ערכים לאותו מקום במערך, מתבצע תהליך שנקרא "טיפול בהתנגשות" שזה אומר שמערך הנתונים ישנה את עצמו כדי להכיל את הערך החדש בהתאם.
פתרון פשוט הוא להוסיף רשימה מקושרת לכל אחד מאינדקסי המערך כאשר כתובת ה-HEAD תאוחסן במערך. כן יווצר שילוב של קלות ניווט של מערך עם דינמיות של רשימה מקושרת בהוספה של ערכים.
אופציה נוספת, היא דילוג של מקום אחד קדימה במערך או דילוג של מספר רנדומלי של ערכים במערך אל המקום הפנוי הבא עד שהוא יימצא ויאוחסן בו הערך הרצוי.
כאשר תתבצע קריאה מהטבלה, תקרא שוב פונקצית הגיבוב שתקבל את ה-key ותחזיר את המקום במערך בו מאוחסן הערך הנדרש.
דוגמא פשוטה לפונקצית גיבוב פרימיטיבית היא mod עבור אורך המערך. כך כל ערך שיאחוסן יקבל אינדקס בתוך גבולות המערך. טיפול בהתנגשות פשוט יכול להיות קפיצה לאינדקס רנדומלי אחר כלשהו.
באופן תיאורטי, טבלה יכולה 'להתנפח' כך עם הנתונים המוכנסים אליה ללא הגבלה, כאשר הגבול העליון יהיה כמות הזיכרון שמערכת ההפעלה או הקומפיילר יכולים לנהל.
דוגמא שימושית בפייתון לטבלת גיבוב היא Dictionary.
קבוצה - Set
מבנה נתונים מסוג Unordered, כלומר שלא נשען על מבנה של אינדקסים, בדומה ל-Hash Table ולכן אין לו יכולת לסדר את הנתונים שלו לפי סדר קבוע.
היתרון שלו הוא בכך שקל להוסיף או להוריד נתונים ממנו, אך לא ניתן לבצע עליו חיפוש בלולאה, כמו במערך. השאלה היחידה שניתן לשאול לגבי Set הוא האם הערך נמצא או לא נמצא בפנים.
שאלה כזו תהיה יעילה ותעלה רק (1)O כמו הוספה והסרה.
כמו"כ לא ניתן לאחסן ערכים זהים, כך ש-Set נותן טיפול אוטומטי בכפילויות (יתרון או חיסרון, תלוי בצרכים).
Set לא דורש ערכי key כדי לאחסן ערכים אלא מכניס ומסיר את הערכים כפי שהם.
מקובל להשתמש ב-Set כאשר רוצים לבצע חיתוך או איחוד של ערכים רבים ולקבל תשובה בצורה יעילה.
למה צריך כל כך הרבה סוגים ?
כאשר תקבלו בעיה לפתרון, תצטרכו לבחור את מבנה הנתונים היעיל ביותר לפתרון שלכם.
כמו כל דבר בחיים, לכל מבנה נתונים - יתרון וחיסרון. לא קיים מבנה נתונים מנצח אחד עבור כולם.
למשל, מערך הוא מבנה נתונים יחסית יעיל, כיון שאפשר להגיע לכל אחד מהאיברים שלו בסיבוכיות מינימלית: (1)O וגם ניתן להחליף בין שני איברים באותה יעילות ללא בעיה.
הבעיה היא שמבנה נתונים תופס מקום רציף בזיכרון שמוקדש אך ורק עבורו. כמו"כ הגודל שלו הוא סטטי ולא ניתן להרחבה.
הערה
מתכנתי פייתון מתחילים עלולים להתבלבל בין List למערך - אך List הוא מערך דינמי שמזכיר יותר מחסנית עם אינדקס מאשר מערך קלאסי. מי שמעוניין לבדוק מערך סטנדרטי בפייתון, מוזמן לייבא את האובייקט array מתוך המודול array ולהתנסות.
אין תגובות:
הוסף רשומת תגובה