שאלה כללית: אם נעשה פונקציה לגלות איבר בסדרת פיבונצ'י (זה שכל איבר שווה לסכום השניים שלפניו) המבוססת על רקורסיה, נסו לחשב את האיבר ה90...

לי יש 6GB ומעבד i920, באיבר ה40 הוא כבר מתחיל לחשב ממש לאט ולהעלות תוצאות בקצב של פעם בחצי דקה ואחר עולה לפעם בדקה.. ועולה ועולה בקיצור לאט פחד.

לכאורה אני מניח שהמחשב ממש מתאמץ, אבל מבחינה בtask manager רק 2.35GB זיכרון בשימוש, וניצול המעבד הוא רק 12%-14%.

מה שווה כל ההתפתחות הטכנולוגית בחומרה אם היא פשוט לא יודעת מתי עליה לפעול בשיא הכוח?

אם כתבת את זה כמו שצריך אין סיבה שזה ייקח כ"כ הרבה זמן.

בעצם, מכיוון שבשביל להגיע לאיבר ה-90 צריך לעשות כ-90 פעולות חיבור אז אין סיבה

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

אולי תשים כאן את הקוד שכתבת וננסה לראות מה לא בסדר בו?

דווקא אם התכנית נכתבה ברקורסיה, כלומר משהו כזה:

int fibo(int n) {
 if (n == 0) return 0;
 if (n == 1) return 1;
 return fibo(n-1) + fibo(n-2);
}

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

יש הרבה סיבות שהמעבד לא נמצא בניצול מקסימלי:

דבר ראשון, התכנית שלך כנראה לא כתובה באופן מקבילי. מה שאומר שהמעבד יכול להריץ אותה רק על ליבה אחת (מתוך 4 הליבות שלו) ולכן הוא לא יעבור את ה-25% ניצול.

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

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

מענין מה קורה אם אתה מריץ רק על core 1 ? או על 2 ?

אפשר לגדיר afinity מה TASK MANAGER בשביל ליבדוק.

טעות שלי.

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

עם זאת,

אם רוצים לכתוב משהו שיחשב מספרי פיבונאצ'י בצורה מהירה,

אפשר לשמור מערך או טבלה כלשהי של המספרים שכבר חישבנו וככה

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

אני השתמשתי בטבלת Hash בשביל לשמור את המספרים שהתוכנה כבר מצאה

וככה הצלחתי להגיע לאיבר ה-90 בסדרה ב-1 מילישניות (#C אגב).

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

לא צריך להשתמש בטבלאות, יש דרכים יותר יעילות.

קודם כל, אפשר להשתמש בלולאה במקום רקורסיה, וזה כבר יותר מהיר:

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.

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

זה אמור לתת לך פתרון דיי יעיל לפיבונצי

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 צריך הרבה הרבה חישובים

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

אגב, לתכנית שלך יש דליפת זכרון.

הוא רצה עם רקורסיה..... ברור שהכי פשוט איטרטיבי.......

כן ברור צריך להוסיף FREE ....

חשבתי בהתחלה שזה בעיה בקוד אבל אם הוא נראה כמו מה ששניצל שלח זה 2 בחזקת N איטרציות שיכול להיות קטלני לכל מעבד. כשN הוא 40 אז אתה מחשב את 39 ו את 38 שזה 824.6 מילארד איטרציות.

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

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