יעילות – חלק ב'

נניח ויש לנו שני אלגוריתמים הפותרים את אותה בעיה,

כיצד נמדוד מי מביניהם יעיל יותר?

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

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

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

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

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

נבחין בדוגמא כיצד לשפר יעילות אלגוריתם:

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

1. חשב את הציון הגבוה ביותר ואחסן אותו ב MAX


2. כפול כל  ציון ב 100 וחלק ב MAX

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

Vector (וקטור) הוא מערך חד ממדי. וקטור באורך N הוא מערך המכיל N איברים.

אם רשימת הציונים נתונה בווקטור L(1), L(2), …………. L(n) ניתן לבצע את שני חלקי האלגוריתם באמצעות לולאות פשוטו העוברות על הווקטור. הראשונה תחפש את הציון המקסימלי באחת הדרכים המקובלות ואת השנייה נכתוב כך:

       2. עבור i מ 1 עד N בצע את הפעולות

           2.1. L(i) * 100/MAX   ß L(i)

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

100/MAX ß FACTOR (השמת 100/MAX במשתנה FACTOR)

בין שלב 1 לשלב 2, לכפול בתוך הלולאה את L(i) ב FACTOR. התוצאה שתתקבל היא זו:

1. חשב את הציון הגבוה ביותר ואחסן ב MAX


2. 100/MAX ß FACTOR


3. עבור i מ 1 עד N, בצע את הפעולות

3.1.                                                      L(i) * FACTOR ß L(i)

גוף הלולאה השנייה שהכיל במקור שתי פעולות חשבון מכיל כעת פעולת חשבון אחת בלבד ומכאן ששיפרנו את האלגוריתם ב 50% (!).

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

חיפוש לינארי

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

1. האם מצאנו את X?


2. האם הגענו לסוף הרשימה?

תשובה T (חיובית) לאחת משתי השאלות תעצור את האלגוריתם בהצלחה (בתנאי 1) וללא הצלחה בתנאי 2 (הגענו לסוף הרשימה ולא נמצא X). בדיקות אלו הן המרכיב הדומיננטי באלגוריתמי חיפוש.

את הבדיקה השנייה ניתן להוציא מחוץ ללולאה בעזרת התחבולה הבאה:

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

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

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

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

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

המשך במאמר הבא…