יעילות

[assaf990]

מה יותר יעיל (אם בכלל):

א)

if( a || b) return 1;

ב)

if (a) return 1;
if (b) return 1;

כיצד ניתן להוכיח את התשובה למשל ב C++

(לקחת חתימות של זמן? איך?)

[Jaman]

ב C יש short circuit (אם ככה קוראים לזה) לאופרטורים, שזה אומר שאם a=TRUE, אז זה מדלג על בדיקת b.

אם b זה פונקציה מורכבת זה בהחלט יכול לעזור ליעל את התוכנית.

בשפות שאין בהם short circuit אפשר לעשות את אותו דבר עם לוגיקה פשוטה.

[שניצל]

אין תשובה חד משמעית, כי היא תלויה בסיכוי ש-a ו-b יהיו אמת או שקר.

נניח, אם ברוב המקרים a הוא שלילי, אז אופציה ב' תיקח כנראה יותר זמן.

מעשית זה כנראה יהיה הבדל חסר משמעות.

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

[Jaman]

אין תשובה חד משמעית' date=' כי היא תלויה בסיכוי ש-a ו-b יהיו אמת או שקר.

נניח, אם ברוב המקרים a הוא שלילי, אז אופציה ב' תיקח כנראה יותר זמן.

[/quote']

הדוגמאות שהוא הביא לא שקולות?

בדוגמה הראשונה אם a אמת אז זה ידלג על בדיקת b, וגם בדוגמה השניה זה יהיה כך (רק בגלל שיש return).

בדוגמה הראשונה אם a שקר אז זה יבדוק את b, וגם בדומה השניה זה יהיה כך.

[שניצל]

מעשית, בדוגמה הראשונה יש רק if אחד, ובשנייה יש שני ifים.

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

[assaf990]

מעשית, בדוגמה הראשונה יש רק if אחד, ובשנייה יש שני ifים.

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

א) זה מה שחיפשתי! כל IF בכל שפה הוא לא יעיל?

ב) כשאני מנסה לעטוף את הקוד בשעון של שניות אז אני לא רואה הבדל. יש שעות של מילישניות?

[שניצל]

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

חוץ מזה, הפונקציה clock מחזירה הערכה של מספר הקלוקים שעברו מתחילת ריצת התכנית. אם אתה מחלק את המספר הזה ב-CLOCKS_PER_SEC, תקבל הערכה של מספר השניות שעברו (בדיוק לא רע של מילישניות).

[assaf990]

פונקצית clock מהיכן?

[שניצל]

תגיד לי אתה.

http://www.google.com/search?q=c+clock

[exercise]

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

    if (a || b)
 804825d:    83 7d f4 00       cmpl  $0x0,-0xc(%ebp)
 8048261:    75 06          jne  8048269 <main+0x2d>
 8048263:    83 7d f8 00       cmpl  $0x0,-0x8(%ebp)
 8048267:    74 09          je   8048272 <main+0x36>
     return 1;
 8048269:    c7 45 e8 01 00 00 00  movl  $0x1,-0x18(%ebp)
 8048270:    eb 25          jmp  8048297 <main+0x5b>

    if (a)
 8048272:    83 7d f4 00       cmpl  $0x0,-0xc(%ebp)
 8048276:    74 09          je   8048281 <main+0x45>
     return 1;
 8048278:    c7 45 e8 01 00 00 00  movl  $0x1,-0x18(%ebp)
 804827f:    eb 16          jmp  8048297 <main+0x5b>
    if (b)
 8048281:    83 7d f8 00       cmpl  $0x0,-0x8(%ebp)
 8048285:    74 09          je   8048290 <main+0x54>
     return 1;
 8048287:    c7 45 e8 01 00 00 00  movl  $0x1,-0x18(%ebp)
 804828e:    eb 07          jmp  8048297 <main+0x5b>

[Component]

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

[EAD]

לא יודע בוודאות לגבי C, אבל בJAVA בהחלט זה אותו הדבר !

הקומפיילר יעשה את העבודה לבד

לדעתי גם בC וC++ זה ככה

[bla7]

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

[exercise]

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

804825d: cmpl  $0x0,-0xc(%ebp)
8048261: jne  8048269 <main+0x2d>
8048263: cmpl  $0x0,-0x8(%ebp)
8048267: je   8048272 <main+0x36>
8048269: movl  $0x1,-0x18(%ebp)
8048270: jmp  8048297 <main+0x5b>

8:  iload_0
9:  ifne  16
12: iload_1
13: ifeq  18
16: iconst_1
17: ireturn

8048272: cmpl  $0x0,-0xc(%ebp)
8048276: je   8048281 <main+0x45>
8048278: movl  $0x1,-0x18(%ebp)
804827f: jmp  8048297 <main+0x5b>
8048281: cmpl  $0x0,-0x8(%ebp)
8048285: je   8048290 <main+0x54>
8048287: movl  $0x1,-0x18(%ebp)
804828e: jmp  8048297 <main+0x5b>

18: iload_0
19: ifeq  24
22: iconst_1
23: ireturn
24: iload_1
25: ifeq  30
28: iconst_1
29: ireturn

ft]

[sniff]

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

אני חייב לחזק את הבחור ולציין ציטוטים חמודים (http://en.wikipedia.org/wiki/Optimization_(computer_science)#Quotes)

הציטוטים האהובים עלי:

The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet. - Michael A. Jackson

More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity. - W.A. Wulf

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. - Knuth, paraphrasing Hoare

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