פורסם 2010 בפברואר 1815 שנים שאלה כללית: אם נעשה פונקציה לגלות איבר בסדרת פיבונצ'י (זה שכל איבר שווה לסכום השניים שלפניו) המבוססת על רקורסיה, נסו לחשב את האיבר ה90...לי יש 6GB ומעבד i920, באיבר ה40 הוא כבר מתחיל לחשב ממש לאט ולהעלות תוצאות בקצב של פעם בחצי דקה ואחר עולה לפעם בדקה.. ועולה ועולה בקיצור לאט פחד.לכאורה אני מניח שהמחשב ממש מתאמץ, אבל מבחינה בtask manager רק 2.35GB זיכרון בשימוש, וניצול המעבד הוא רק 12%-14%.מה שווה כל ההתפתחות הטכנולוגית בחומרה אם היא פשוט לא יודעת מתי עליה לפעול בשיא הכוח?
פורסם 2010 בפברואר 1815 שנים אם כתבת את זה כמו שצריך אין סיבה שזה ייקח כ"כ הרבה זמן.בעצם, מכיוון שבשביל להגיע לאיבר ה-90 צריך לעשות כ-90 פעולות חיבור אז אין סיבהשזה ייקח יותר מאיזה 5 מילי-שניות. (טוב נו, גם הרבה קריאות לפונקציה, אבל זה עדיין לא מצדיק זמן של חצי דקה לתוצאה)אולי תשים כאן את הקוד שכתבת וננסה לראות מה לא בסדר בו?
פורסם 2010 בפברואר 1915 שנים דווקא אם התכנית נכתבה ברקורסיה, כלומר משהו כזה:int fibo(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibo(n-1) + fibo(n-2);}אז היא באמת אמורה לקחת הרבה זמן (הנוסחה לחישוב זמן הריצה היא בעצמה אותה הנוסחה לחישוב האיבר בסדרת פיבונאצי, וזו סיבוכיות אקספוננציאלית).יש הרבה סיבות שהמעבד לא נמצא בניצול מקסימלי:דבר ראשון, התכנית שלך כנראה לא כתובה באופן מקבילי. מה שאומר שהמעבד יכול להריץ אותה רק על ליבה אחת (מתוך 4 הליבות שלו) ולכן הוא לא יעבור את ה-25% ניצול.חוץ מזה, יכול להיות שהתוכנה פשוט לא מוגדרת לעבוד ב-priority גבוה, וייתכן שהמעבד הוא לא צוואר הבקבוק של התכנית, אלא רכיב אחר (נניח הזכרון).
פורסם 2010 בפברואר 1915 שנים לפעמים יותר זה פחות (כשמערכת לא כתוב נכון לרבוי מעבדים)מענין מה קורה אם אתה מריץ רק על core 1 ? או על 2 ?אפשר לגדיר afinity מה TASK MANAGER בשביל ליבדוק.
פורסם 2010 בפברואר 1915 שנים טעות שלי.שניצל אכן צודק, ובאמת זה אמור לקחת לא מעט זמן, אם כי אפשר לבצע אופטימיזציות עבור ריבוי-מעבדים.עם זאת,אם רוצים לכתוב משהו שיחשב מספרי פיבונאצ'י בצורה מהירה,אפשר לשמור מערך או טבלה כלשהי של המספרים שכבר חישבנו וככהלהוריד את זמן החישוב לאפס (בערך).אני השתמשתי בטבלת Hash בשביל לשמור את המספרים שהתוכנה כבר מצאהוככה הצלחתי להגיע לאיבר ה-90 בסדרה ב-1 מילישניות (#C אגב).והפונקציה שלי עדיין רקורסיבית, אם כי צריך לשמור אוסף מספרים במקום חיצוני כלשהו.
פורסם 2010 בפברואר 1915 שנים לא צריך להשתמש בטבלאות, יש דרכים יותר יעילות.קודם כל, אפשר להשתמש בלולאה במקום רקורסיה, וזה כבר יותר מהיר:int fibo(int n) { int a = 0, b = 1; for (int i = 1 ; i < n ; i++) { int t = a; b = a+b; a = t; } return b;}(ייתכן שיש לי טעות קטנה באינדקסים, אבל הבנתם את העקרון)חוץ מזה, יש דרך יותר יעילה מזו, שעובדת בסיבוכיות (O(logn.
פורסם 2010 בפברואר 2015 שנים זה אמור לתת לך פתרון דיי יעיל לפיבונצי long fib1(int n) { int i, *arr = (int*)malloc((n+1)*sizeof(int)); for (i=0; i<=n; i++) arr[i]=0; arr[1]=1; return fib_int(n,arr);}long fib_int(int n, int arr[]){ if (n <= 1) return n; if (arr[n]) return arr[n]; arr[n] = fib_int(n-1, arr) + fib_int(n-2, arr); return arr[n];}ועוד דבר קח בחשבון שהסיבוכיות זמן של הפתרון הפשוט של פיבונצי זה 2 בחזקת N למצוא את המספר ה90 צריך הרבה הרבה חישובים
פורסם 2010 בפברואר 2015 שנים אלוהים אדירים, למה להסתבך כל כך? אפשר לעשות פתרון יעיל באותה מידה באופן איטרטיבי ולא רקורסיה, ואז גם לא צריך לשמור שום זכרון (זה בדיוק הפתרון שכתבתי בהודעה הקודמת שלי).אגב, לתכנית שלך יש דליפת זכרון.
פורסם 2010 בפברואר 2015 שנים הוא רצה עם רקורסיה..... ברור שהכי פשוט איטרטיבי.......כן ברור צריך להוסיף FREE ....
פורסם 2010 בפברואר 2115 שנים חשבתי בהתחלה שזה בעיה בקוד אבל אם הוא נראה כמו מה ששניצל שלח זה 2 בחזקת N איטרציות שיכול להיות קטלני לכל מעבד. כשN הוא 40 אז אתה מחשב את 39 ו את 38 שזה 824.6 מילארד איטרציות. הפתרון של trex די טוב רק צריך להפתר מהmemory leak בפונקציה הראשית כמו ששניצל אמר . מה שקורה בפתרון הזה הוא שבגלל שהקריאה הראשונה לפונקציה מחשבת את כל הערכים בדרך הקריאה השניה הופכת ל O(1( ואני חושב שזה מוריד את הסיבוכיות ל O (N) . זה הופך את הבעיה הרקורסיבית לאיטרטיבית.
פורסם 2010 בפברואר 2115 שנים למעשה הסיבוכיות היא לא 2 בחזקת N, אלא פי (phi) בחזקת N. זה יוצא יותר יעיל (אבל עדיין אקספוננציאלי).
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.