נושא: יעילות ב תיכנות

נשלח בתאריך: 13 November 2007 בשעה 13:27 | IP רשוּם

תשובה כללית: תלמד על תורת החישוביות ותורת הסיבוכיות.

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

נשלח בתאריך: 13 November 2007 בשעה 15:41 | IP רשוּם

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

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

נשלח בתאריך: 14 November 2007 בשעה 11:39 | IP רשוּם

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

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

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

תחשוב מה היית צריך לעשות אם היית רוצה לכפול למשל 512 * 512 ללא מחשבון ?

היית עושה כפל ארוך, ומתחיל להכפיל 2*2, 1*2, 5*2 ... נניח שכל תת-הכפלה כזאת מוגדרת כפעולה אחת, ואם מספר הספרות במספר הוא n, אז היית מבצע n^2 פעולות רק בשביל לחשב את הריבוע של המספר (קצת יותר אבל לשם הדוגמא נניח שזה ככה). 

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

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

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

מקווה שזה קצת הבהיר את הדברים - זה לא תחליף ללימוד מקיף יותר של התחום אבל זה רק על קצה המזלג...

נשלח בתאריך: 15 November 2007 בשעה 09:48 | IP רשוּם

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

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

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

אם אתה רוצה לדעת יותר בנושא, תקרא על P מול NP - זאת אחת השאלות הגדולות שמעסיקות את עולם המדע במאות ה-20-21, שאלה שאולי אין לה מענה.

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

נשלח בתאריך: 15 November 2007 בשעה 15:18 | IP רשוּם

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

נשלח בתאריך: 15 November 2007 בשעה 17:24 | IP רשוּם

1) לא בהכרח נכון - תקרא את כל הדיון מהתחלה ותראה שזה כבר נדון.

2) אחת הדרכים הטובות לדעת שיש פתרון טוב יותר היא למצוא אותו - אבל זאת לא הדרך היחידה.