מיטוב אלגוריתמים

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

ערך מחפש מקורות

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

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

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

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

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

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

בתוכנות מסדי נתונים מקובל לעשות אופטימיזציה של שאילתות SQL, כך שייקחו פחות זמן (למשל, שימוש באינדקסים של הטבלה) אולם בניגוד למצב בהידור, במסד נתונים לא נעשה הדבר מראש (למרות שמסדי נתונים רבים תומכים בפרוצדורות שמורות, דבר המאפשר לעשות את האופטימיזציה מראש^{[דרושה הבהרה]}), מצב אשר גורם לכך שהאופטימיזציה דווקא מאריכה את זמן הביצוע. במצב כזה, ישנה אפשרות שחיפוש הדרך היעילה ביותר לבצע את השאילתא יביא למעשה לזמן ביצוע ארוך יותר! בעיה זו הביאה לפיתוח של אלגוריתמים מורכבים יותר לביצוע אופטימיזציה, כך שלא תארך זמן רב יותר מאשר השאילתא המקורית. העובדה כי האופטימיזציה נעשית פעמים רבות הביאה גם להוספת תמיכה באפשרות לתת רמזים לתוכנת האופטימיזציה, כך שגם התוכניתן מסוגל להשפיע על הצורה בה השאילתא מבוצעת בפועל.

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