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

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

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

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

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

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

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

מיטוב פירושו לגרום לתוכנה לעבוד מהר יותר. (אופטימיזציה = שם בלועזית.)

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

המעבד יכול לזכור מה קרה לפני ולנבא מה יקרה אחר כך. זה מקצר זמן עבודה.

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

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

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

פרופיילר (כלי מדידה) מראה איפה בתוכנית מבלים הכי הרבה זמן. כך יודעים איפה לשפר.

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