חידה

[DadleFish]

חידה

מה לא טוב מבחינת ביצועים בקוד הבא?

#include <vector> #include <iostream> using namespace std; class Test { public: Test() {} ~Test() {} Test(const Test& rhs) {} }; int main() { vector<Test> v; Test a; for (int i = 0; i < 1023; i++) { v.push_back( a); } return 0; }​

 

[Pembelton]

הפתרון: (v.reserve(1024

 

[galh]

../images/Emo31.gif למה בכותרת?! ../images/Emo46.gif

 

[Pembelton]

צודק. החיפזון מן השטן

 

[DadleFish]

אתה מתכוון, החילזון מהשפן.

 

[galh]

צריך להיות i++, לא? ../images/Emo6.gif

שני דברים. הראשון, העובדה שה- vector מכיל את האובייקט ולא רפרנס או פויינטר גורם להעתקת האובייקט. השני, כדאי לעשות reserve לוקטור לפני הכניסה ללולאה. מספיק או שיש עוד?

 

[Pembelton]

זה לא כל כך מצחיק

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

 

[DadleFish]

אתה טועה.

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

 

[galh]

אין מה לעשות, חוש הומור של מתכנת.

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

 

[DadleFish]

אכן,

לגבי ה-i, לא, זה לא נכון לגבי primitives - רק לגבי אובייקטים. ה-reserve הוא הבעיה המרכזית. בהיעדרו, לפחות ב-VS, מתבצעות 1023 העתקות מיותרות לאובייקט הזה. לגבי רפרנס/פוינטר: קודם כל, איך תעשה וקטור של רפרנס? ושנית, פוינטר הוא פתרון טוב בחלק מהמקרים. במקרה הזה הוא לא יעזור לך, אלא אם כמובן תעשה push_back לכתובת של a, ולא תייצר אובייקטים חדשים (שרק יאטו אותך, אגב).

 

[galh]

יש תפוז צוחק! לא שמת לב?!

אני לא עושה שום דבר, רק מבקר את הקוד שלך.

 

[DadleFish]

תופס תחת, אה? ../images/Emo3.gif

 

[galh]

כן, כבר לא צריך להתחנף אליך. ../images/Emo13.gif

 

[galh]

יש תפוז צוחק! לא שמת לב?!

אני לא עושה שום דבר, רק מבקר את הקוד שלך.

 

[DadleFish]

אגב,

ארבע גרסאות, הבדלים רציניים:

#include <windows.h> #include <vector> #include <iostream> #define LIMIT 1024 using namespace std; class Test { public: Test() {} ~Test() {} Test(const Test& rhs) {} }; void f() { vector<Test> v; Test a; for (int i = 0; i < LIMIT-1; i++) { v.push_back(a); } } void g() { vector<Test *> v; v.reserve(LIMIT); Test a; for (int i = 0; i < LIMIT-1; i++) { v.push_back(&a); } } void h() { vector<Test> v; v.reserve(LIMIT); Test a; for (int i = 0; i < LIMIT-1; i++) { v.push_back(a); } } void j() { vector<Test *> v; v.reserve(LIMIT); Test a; for (int i = 0; i < LIMIT-1; i++) { v.push_back(new Test(a)); } } int main() { const unsigned int n = 1000; int i; DWORD dwStart1 = GetTickCount(); for (i = 0; i < n; i++) { f(); } DWORD dwEnd1 = GetTickCount(); DWORD dwStart2 = GetTickCount(); for (i = 0; i < n; i++) { g(); } DWORD dwEnd2 = GetTickCount(); DWORD dwStart3 = GetTickCount(); for (i = 0; i < n; i++) { h(); } DWORD dwEnd3 = GetTickCount(); DWORD dwStart4 = GetTickCount(); for (i = 0; i < n; i++) { j(); } DWORD dwEnd4 = GetTickCount(); cout << "f:" << dwEnd1-dwStart1 << " g:" << dwEnd2-dwStart2 << " h:" << dwEnd3-dwStart3 << " j:" << dwEnd4-dwStart4 << endl; }​

בבדיקה אצלי, התוצאות היו: F (אובייקט רגיל בלי RESERVE) לקחה 1844 מילי G (מצביע עם RESERVE) לקחה 1000 מילי H (אובייקט רגיל עם RESERVE) לקחה 1234 מילי J (מצביע עם RESERVE ועם NEW) לקחה 1657 מילי מסקנות: 1. המעבר למצביע חוסכת לפחות 20% מהזמן (ההפרש בין G לבין H) אבל רק אם הכתובת ידועה מראש. אם צריך לייצר אותה - זה מאט ב-30%. לפחות 20% מהזמן, כי במקרה הנ"ל ה-copy ctor ריק. אם היו בו פעולות, זה היה מאט יותר, כמובן. 2. ההבדל הכי גדול הוא כמובן בגלל/בזכות ה-RESERVE. אם ידוע גדול הוקטור, או אפילו יש השערה מבוססת - צריך להשתמש ב-RESERVE. החסכון הוא 30-40% לפחות - שוב, אם מבוצעות פעולות ב-copy ctor ההבדל יגדל כמובן.

 

[galh]

עוד גרסא.

תוספת של memory pool (ממומש בצורה פרימיטיבית לצורך הדוגמא!):

void k() { vector<Test *> v; v.reserve(LIMIT); Test a; Test *b = new Test[LIMIT]; for (int i = 0; i < LIMIT-1; i++) { b = a; v.push_back(b); } }​

נתן לי את תוצאה שעומדת בין הזמנים של h ו- g (שלא עושה כלום).

 

[חובבן]

אם אני זוכר נכון אתה יכול להעביר את

הגודל של הוקטור באיתחול שלו, ולא רק ע"י reserve.

 

[DadleFish]

כן, גם לי זכור משהו כזה.

 

[עידו123456]

קצת רמאות אבל בכל זאת

הגרסא הבאה השיגה אצלי את התוצאות הטובות ביותר:

void k() { Test a; vector<Test *> v(LIMIT,&a); }​

רמאות אמנם, אבל עומד בתנאי התרגיל

 

[DadleFish]

זו לא בדיקה פרקטית

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