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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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

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

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

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