4. חיפוש

מבנה נתונים ואלגוריתמים

 

 

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

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

 

4.1 חיפוש סידרתי

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

אנו מעונינים:

·        בזמן החיפוש הממוצע.

·        בזמן החיפוש הגרוע ביותר.

·        בזמן החיפוש הטוב ביותר.

 

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

 

אם ישנם n פריטים באוסף הנתונים, בין אם הוא מאוחסן כמערך או כרשימה מקושרת, אז ברור

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

 

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

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

במקרה הגרוע ביותר בתכנון המערכת, כי הוא מייצג את הביצוע המובטח ביותר.

 

4.2 חיפוש בינארי

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

 

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

 

כעת ניתן ליישם את פונקצית FindInCollection:

 

        static void *bin_search( collection c, int low, int high, void *key )

{

        int mid;

        /* Termination check */

        if (low > high) return NULL;

        mid = (high+low)/2;

  switch (memcmp(ItemKey(c->items[mid]),key,c->size))

{

          /* Match, return item found */

          case 0: return c->items[mid];

          /* key is less than mid, search lower half */

          case -1: return bin_search( c, low, mid-1, key);

          /* key is greater than mid, search upper half */

          case 1: return bin_search( c, mid+1, high, key );

          default : return NULL;

        }

}

void *FindInCollection( collection c, void *key ) 

{

        /* Find an item in a collection

        Pre-condition: 

               c is a collection created by ConsCollection

               c is sorted in ascending order of the key

               key != NULL

        Post-condition: returns an item identified by key

              if one exists, otherwise returns NULL

        */

               int low, high;

               low = 0; high = c->item_cnt-1;

               return bin_search( c, low, high, key );

        }

 

 

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

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

      העליון או התחתון של המערך, ואז היא קוראת לעצמה במחצית המתאימה של

       המערך.

            ב.   יש תנאי עצירה (למעשה יש שני תנאים!):

1)      אם low > high, אזי אין אלמנטים בחלק שבו נערך החיפוש.

2)      אם יש התאמה עם הפריט האמצעי בחלק המערך הנבדק, הוא מוחזר מייד.

ג.   AddToCollection זקוקה להתאמה שתבטיח כי כל פריט שמתווסף ממוקם

      במקומו הנכון במערך. ההליך היא פשוט:

1)      חפש במערך עד למציאת המקום המתאים להכנסת הפריט החדש.

2)      העבר את כל הפריטים הנמצאים לאחר מקום זה, מקום אחד קדימה.

3)      הכנס את הפריט החדש לתוך המקום הריק שנוצר.

ד.   bin_search מוצהר כ- static. זהוי פונקציה מקומית שלא נעשה בה שימוש

      מחוץ למחלקה זו. אם היא לא הייתה מוגדרת כ- static, היא הייתה מיוצאת

      וזמינה בכל חלקי התוכנית. הצהרת ה- static מאפשרת למחלקות אחרות

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

 

 

 

 

ניתוח

 

 

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

 

לכן זמן הריצה של חיפוש בינארי הוא יחסי ל- logn והאלגוריתם מכונה O(logn).

 

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

 

 

 

לכן עבור n גדול, logn הוא הרבה יותר קטן מאשר n, וכתוצאה מכך אלגוריתם של O(logn)

מהיר הרבה יותר מאשר אלגוריתם של O(n).

 

אנו נבחן התנהגות זו בצורה מפורטת יותר בהמשך. כעת, הבה נראה מה ניתן

לעשות בנושא פעולת ההכנסה (AddToCollection).

 

במקרה הגרוע ביותר, הכנסה עשויה לדרוש n פעולות על מנת להכניס פריט לרשימה ממוינת.

1.      ניתן למצוא את המקום של הפריט החדש ברשימה על ידי שימוש בחיפוש בינארי ב-  O(logn) פעולות.

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

 

ניתוח דומה יראה כי גם עבור הסרת פריט יש צורך ב- O(n) פעולות.

 

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

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

 

 

מושגים

 

O גדול

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

כלשהו.

חיפוש בינארי

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

 

 

המשך ל: עצים                                        חזור ל: תוכן עניינים