לוגו אתר Fresh          
 
 
  אפשרות תפריט  ראשי     אפשרות תפריט  צ'אט     אפשרות תפריט  מבזקים     אפשרות תפריט  צור קשר     חץ שמאלה ‎print ‎"Hello World!"; if‎ ‎not rules.‎know ‎then rules.‎read(); חץ ימינה  

לך אחורה   לובי הפורומים > מחשבים > תכנות ובניית אתרים
שמור לעצמך קישור לדף זה באתרי שמירת קישורים חברתיים
תגובה
 
כלי אשכול חפש באשכול זה



  #1  
ישן 09-03-2010, 12:32
  Dark Knight Dark Knight אינו מחובר  
 
חבר מתאריך: 30.07.05
הודעות: 949
שלח הודעה דרך ICQ אל Dark Knight
אתגר מעניין, ++OOP\C

כעקרון, הכי נוח להסתכל על הבעיה הזו ב-++C שמאפשרת העמסת אופרטורים, אבל אפשר לייחס את הבעיה לכל שפה שתומכת ב-OOP ולא עובדת ב-reference semantics (כנראה שבג'ווה הדיון פה לא יהיה רלבנטי)

הבעיה היא כזו:
אופרטור\מתודה מתמטי\ת מוגדרים בד"כ בחתימה כזו (בשפת ++C) למשל:
קוד PHP:
 Type operator+(const Typeright) const 

או, אם השפה לא מאפשרת העמסת אופרטורים (תחביר דמוי ++C ה-& מסמן רפרנס, ה-const בסוף מצהיר שהמתודה לא תשנה את מצב האובייקט)
קוד PHP:
 Type Add(const Typeright) const 


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

כלומר, כאשר יש לנו ביטוי מהצורה A = B+C יווצרו 2 אובייקטים זמניים - אחד בתוך האופרטור, השני מחוץ לאופרטור, והאובייקט הזמני השני יועתק ל-A.

כאשר מדובר באובייקטים מתמטיים מורכבים יחסית, כמו וקטור או מטריצה, מדובר בתקורת ביצועים מאד רצינית: אם למשל יש לנו מטריצה של 1000*1000, מבחינה מתמטית מספיק להסתכל על התא ה-i,j של B, התא ה-i,j של C, לחבר אותם ולהציב את התוצאה ב-A (כלומר 3 גישות לכל אינדקס) לעומת מה שקורה בפועל הוא שניגשים לתא ב-B, לתא ב-C, מציבים בעותק, לאחר מכן יוצרים עותק של העותק בהחזרה - עוד גישה לכל תא בעותק הראשון ולכל תא בעותק השני, ורק לבסוף מציבים הכל בחזרה ב-A - כלומר עוד גישה לכל תא בעותק השני וגישה לכל תא ב-A => סה"כ 7 גישות לכל אינדקס

הבעיה חמורה בהרבה כאשר מבצעים תרגיל מתמטי מורכב יותר: A=B+C+D ונוצרים הרבה יותר עותקים בפנים - הפגיעה בביצועים היא ענקית. (גם אם בסופו של דבר הסיבוכיות לא משתנה כי מדובר בגורם כפלי..)

נשאלת השאלה - כיצד אפשר לפתור את הבעיה, מבלי לשנות את הסמנטיקה או הנכונות המתמטית?
איך אפשר לגרום לכך ש- A=B+C יחזיר את אותה התשובה, זאת מבלי לבצע את כל החישובים המיותרים באמצע? ע"י גישה אחת לכל אינדקס בכל מטריצה כזו?

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

תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #3  
ישן 09-03-2010, 17:00
  Dark Knight Dark Knight אינו מחובר  
 
חבר מתאריך: 30.07.05
הודעות: 949
שלח הודעה דרך ICQ אל Dark Knight
בתגובה להודעה מספר 2 שנכתבה על ידי פסטן שמתחילה ב "יש לך טעות בהנחות"

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

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

האמת, חשבתי בשלב כלשהו לכתוב שהאמור להעיל מתעלם מאופטימיזציות וויתרתי על המשפט הזה בסופו של דבר.. אולי חבל..
הפתרון שאני חשבתי עליו שונה מהגישה שהוצגה בכתבה שצרפת ומשתמש בעקרונות של OOP בצורה די אלגנטית, במקום לשלוח את האובייקט עצמו.. חוץ מזה, האם האופטימיזציה הייתה אפשרית במקרה של
(Matrix C(A+B?

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


נערך לאחרונה ע"י Dark Knight בתאריך 09-03-2010 בשעה 17:12.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #4  
ישן 14-03-2010, 17:47
צלמית המשתמש של פסטן
  פסטן פסטן אינו מחובר  
 
חבר מתאריך: 14.12.09
הודעות: 9,751
בתגובה להודעה מספר 3 שנכתבה על ידי Dark Knight שמתחילה ב "אני לא חושב שלהתעלם מהאפשרות..."

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

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

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

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

והעותק ה"זמני" הזה הוא שיוחזר מהפונקציה. ללא העתקה. הטענה שלך מראה שלא קראת (או שיש לך קשיים רציניים בהבנה).

ציטוט:
במקור נכתב על ידי Dark Knight
אני לא חושב שהאופטימיזציה האחרונה, זו שחוסכת את העותק הפנימי בכלל אפשרית במקרה הספציפי פה כשיש למשל שרשרת של הפעלות אופרטור,
היא תחסוך את ה-copy constructor-ים. מובן שאין לה השפעה על עצם זה שתוצאת האופרטור a+b מחזירה אובייקט חדש ולא משנה את a או את b. אבל האובייקט החדש לא יועתק, אלא יווצר היכן שצריך על ההתחלה.

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

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

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

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

ציטוט:
במקור נכתב על ידי Dark Knight
חוץ מזה, האם האופטימיזציה הייתה אפשרית במקרה של
(Matrix C(A+B?

לא בלי לשנות את הסמנטיקה...
זה בדיוק המצב בו האופטימיזציה פועלת. כדאי שתקרא קצת לפני שאתה מגיב. הפלט של הקוד הבא על VCPP EXPRESS 2008 במצב דיבאג:
קוד:
#include <iostream> class C { public: explicit C(int i) : m_i(i) { print("C::C(int)"); } C(const C& other) : m_i(other.m_i) { print("C::C(const C&)"); } C operator+(const C& right) { print("C::operator+(const C&)"); return C(m_i+right.m_i); } int get() { return m_i; } protected: int m_i; void print (const char * const text) { std::cout << text << std::endl; } }; int main() { C a(1); C b(2); C c(a+b); C d(C(3)+C(4)); C e(C(C(5)+C(6))+C(C(7)+C(8)+C(9))); std::cout << c.get() << std::endl; std::cout << d.get() << std::endl; std::cout << e.get() << " == " << (5+6+7+8+9) << std::endl; return 0; }

הוא:
קוד:
C::C(int) C::C(int) C::operator+(const C&) C::C(int) C::C(int) C::C(int) C::operator+(const C&) C::C(int) C::C(int) C::C(int) C::C(int) C::operator+(const C&) C::C(int) C::operator+(const C&) C::C(int) C::C(int) C::C(int) C::operator+(const C&) C::C(int) C::operator+(const C&) C::C(int) 3 7 35 == 35

או בקיצור - כן, זה בדיוק המצב עליו מדובר. למה אתה לא קורא?
וכמו ששמת לב - האופטימייזר כיסה את כל המקרים, גם במקרה המורכב, לא נקרא אפילו CC אחד!
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #25  
ישן 12-03-2010, 10:09
  Dark Knight Dark Knight אינו מחובר  
 
חבר מתאריך: 30.07.05
הודעות: 949
שלח הודעה דרך ICQ אל Dark Knight
בתגובה להודעה מספר 24 שנכתבה על ידי טוארג שמתחילה ב "אם מוחזר מצביע (שיכול להיות..."

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

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


נערך לאחרונה ע"י Dark Knight בתאריך 12-03-2010 בשעה 10:12.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #26  
ישן 12-03-2010, 16:21
  טוארג טוארג אינו מחובר  
 
חבר מתאריך: 13.02.09
הודעות: 365
בתגובה להודעה מספר 25 שנכתבה על ידי Dark Knight שמתחילה ב "אתה מתכוון שבתוך האופרטור..."

לא בדיוק. הרעיון הוא לבנות מחלקה שעוטפת את המצביע, ומיישמת (בין השאר) את הדברים הבאים:
<-operator (אשר מחזיר את המצביע)
*operator (אשר מחזיר reference: אם המצביע הוא p, יוחזר p*)
copy constructors (אשר שומרים את המצביע שהועבר ואם צריך מבצעים reference count)
=operator (כמה כאלה, בדומה ל copy consructors)

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

דוגמא בסיסית היא auto_ptr של STL, ראה פה: http://en.wikipedia.org/wiki/Auto_ptr. משוכלל יותר הוא shared_ptr של boost שסופר כמה משתמשים יש באובייקט ומוחק אותו כשמספר המשתמשים ירד לאפס, ראה פה: http://www.boost.org/doc/libs/1_42_.../shared_ptr.htm.

האם זה מספיק טוב לדרישות שלך בראש האשכול? מבחינת ביצועים כן. מבחינת נוחות אולי לא. אם יבוא מישהו עם רעיונות טובים (או שלך עצמך יש שפן בכובע) - אשמח ללמוד משהו חדש.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #27  
ישן 12-03-2010, 16:43
  Dark Knight Dark Knight אינו מחובר  
 
חבר מתאריך: 30.07.05
הודעות: 949
שלח הודעה דרך ICQ אל Dark Knight
בתגובה להודעה מספר 26 שנכתבה על ידי טוארג שמתחילה ב "לא בדיוק. הרעיון הוא לבנות..."

לי יש 2 פתרונות בראש, אחרת לא הייתי פותח את האשכול.
הפתרון שאליו אני מכוון באשכול הזה הוא הפתרון היותר יפה מבחינת השימוש ב-OOP, אבל הפחות יעיל, שפותר את הבעיה בזמן ריצה עם תקורת ביצועים קלה.
הפתרון השני, שדומה באופי אבל שונה מהותית בביצוע, פותר את הבעיה עוד בזמן קומפילציה ובאמת יוצר חיסכון אדיר מבחינת ביצועים, אולם הפתרון הזה הרבה יותר מכוון ++C...
ולא, אף אחד מהם לא דורש מצביעים, ושניהם מאפשרים לפתור תרגיל כמו A = (B+C)*D - E כפי שהוא כתוב וללא יצירה של עותקים מיותרים או פגיעה בסימנטיקה של השפה.
_____________________________________
חתימתכם הוסרה כיוון שלא עמדה בחוקי האתר. לפרטים נוספים לחצו כאן. תוכלו לקבל עזרה להתאמת החתימה לחוקים בפורום חתימות וצלמיות.


נערך לאחרונה ע"י Dark Knight בתאריך 12-03-2010 בשעה 16:48.
תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #28  
ישן 15-03-2010, 19:03
  Dark Knight Dark Knight אינו מחובר  
 
חבר מתאריך: 30.07.05
הודעות: 949
שלח הודעה דרך ICQ אל Dark Knight
בתגובה להודעה מספר 1 שנכתבה על ידי Dark Knight שמתחילה ב "אתגר מעניין, ++OOP\C"

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

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

תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #34  
ישן 15-03-2010, 20:54
  Dark Knight Dark Knight אינו מחובר  
 
חבר מתאריך: 30.07.05
הודעות: 949
שלח הודעה דרך ICQ אל Dark Knight
בתגובה להודעה מספר 33 שנכתבה על ידי טוארג שמתחילה ב ""

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

תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
  #36  
ישן 15-03-2010, 21:31
  Dark Knight Dark Knight אינו מחובר  
 
חבר מתאריך: 30.07.05
הודעות: 949
שלח הודעה דרך ICQ אל Dark Knight
בתגובה להודעה מספר 35 שנכתבה על ידי טוארג שמתחילה ב "סליחה, מחקתי את ההערה הקודמת..."

שמתי לב שערכת רק אחרי שפרסמתי את ההודעה שלי... (לקח זמן לכתוב את כל זה )

א. כן ולא... כשאתה מחבר int עם double אתה מקבל double בין אם int היה הפרמטר הראשון או השני. מדובר באופרטור שהוא חיצוני למחלקה, בסופו של דבר. יתרה מזאת, מבחינה לוגית המחלקה הזו מייצגת תוצאה של פעולת חשבון. אפשר להתווכח פה אם יש או אין שבירת סמנטיקה, אבל בכל מקרה מדובר על מקרה די מיוחד.
ב. המ... האובייקטים הללו מיועדים לחיים בתוך שורת קוד אחת... שינוי שלהם בתוך אותה שורת קוד אחת מחייב התנהלות בתהליכונים וזה כבר לא באמת משנה איזה מימוש תבחר - אם לא תשתמש במנגנון סנכרון לא תוכל לקבל הבטחה לנכונות החישוב בכל מקרה. הדבר נכון כפליים לגבי המקרה של מחיקת האובייקט לפני סיום החישובים...
ג. מספר החישובים קטן בצורה משמעותית: כל הבניה פה נעשית פחות או יותר בזמן קומפילציה. האובייקט מכיל רפרנסים, לא עותקים. גם בלי אופטימיזציה במקרה הגרוע נוצרים פה מספר אובייקטים ליניארי במספר המחוברים כאשר כל אובייקט מכיל 2 מצביעים לאובייקטים המחוברים. בנוסף, עבור כל אופרנד ניגשים לכל תא שלו רק פעם אחת - זאת בניגוד לכל מקרה אחר בו נוצרים עותקי ביניים שדורשים תוספת ביצועים רצינית.
עותק ביניים -> מוסיף אלמנט כפלי למספר הפעולות
הפתרון הנ"ל -> מוסיף אלמנט חיבורי (לכל היותר) למספר הפעולות. במקרה הטוב שעבור קומפיילר טוב מהווה גם המקרה הממוצע - כל התקורה תבוטל בזמן קומפילציה ותגיע למצב של הפעלת אופרטור [] פעם אחת לכל אופרנד.
ד. כל דבר מחייב זהירות, אבל הפתרון הנ"ל מתאים דווקא למקרים רבים. עד כמה שאני יודע ווריאציות שלו ממומשות בספריות מתמטיות רבות.
_____________________________________
חתימתכם הוסרה כיוון שלא עמדה בחוקי האתר. לפרטים נוספים לחצו כאן. תוכלו לקבל עזרה להתאמת החתימה לחוקים בפורום חתימות וצלמיות.

תגובה ללא ציטוט תגובה עם ציטוט חזרה לפורום
תגובה

כלי אשכול חפש באשכול זה
חפש באשכול זה:

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

מזער את תיבת המידע אפשרויות משלוח הודעות
אתה לא יכול לפתוח אשכולות חדשים
אתה לא יכול להגיב לאשכולות
אתה לא יכול לצרף קבצים
אתה לא יכול לערוך את ההודעות שלך

קוד vB פעיל
קוד [IMG] פעיל
קוד HTML כבוי
מעבר לפורום



כל הזמנים המוצגים בדף זה הם לפי איזור זמן GMT +2. השעה כעת היא 03:05

הדף נוצר ב 0.10 שניות עם 12 שאילתות

הפורום מבוסס על vBulletin, גירסא 3.0.6
כל הזכויות לתוכנת הפורומים שמורות © 2024 - 2000 לחברת Jelsoft Enterprises.
כל הזכויות שמורות ל Fresh.co.il ©

צור קשר | תקנון האתר