שלום לכולם,

יצרתי רשימה מקושרת טמפלטית ומיון מיזוג מתאים, אני מקבל stack overflow כאשר הרשימה מכילה +5000 איברים.

המיון עובד כמו שצריך עבור 2000 למשל.

כיצד ניתן לפתור את הבעיה?

תודה

template <class T>
Node<T>* LinkedList<T>::merge_sort(Node<T>* head)
{

  Node<T>* head_one;
  Node<T>* head_two;


  if((head == NULL) || (head->get_next() == NULL)) 
   return head;

  head_one = head;
  head_two = head->get_next();

  while ((head_two != NULL) && (head_two->get_next() != NULL))
  {
    head = head->get_next();
    head_two = head->get_next()->get_next();
  }
  head_two = head->get_next();
  head->set_next(NULL);

  return merge(merge_sort(head_one), merge_sort(head_two));
}



template <class T>
Node<T>* LinkedList<T>::merge(Node<T>* head_one, Node<T>* head_two)
{
  Node<T>* head_three;

  if(head_one == NULL)
    return head_two;

  if(head_two == NULL)
    return head_one;

  if (*(head_one->get_data()) < *(head_two->get_data()))
  {
    head_three = head_one;
    head_three->set_next(merge(head_one->get_next() , head_two));
  }
  else
  {
    head_three = head_two;
    head_three->set_next(merge(head_one, head_two->get_next()));
  }
  return head_three;
}

ערוך בבקשה את הכותרת כך שתכיל את תמצית השאלה.

stack overflow קורה כאשר יש לך יותר מדי קריאות לפונקציה בתוך פונקציה בתוך פונקציה וכו'. בד"כ זה קורה כאשר הרקורסיה עמוקה מדי. תחשוב מה עומק הרקורסיה שלך ואיך מטפלים בזה (רמז: עדיף להימנע מקריאות רקורסיביות כשאפשר).

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

הפונקציה merge לא צריכה להיות רקורסיבית. נסה לחשוב איך להחליף את המימוש שלה בלולאה.

מימשתי בלולאה ואני עדיין מקבל stack overflow

template <class T>
Node<T>* LinkedList<T>::merge(Node<T>* head_one, Node<T>* head_two)
{
  Node<T>* head_three;
  Node<T>* tmp_ptr;

  if(head_one == NULL)
    return head_two;

  if(head_two == NULL)
    return head_one;
  if (*(head_one->get_data()) < *(head_two->get_data()))
  {
    head_three = head_one;
    while(head_one->get_next() != NULL)
    {
      if(*(head_one->get_data()) < *(head_two->get_data()))
        head_one = head_one->get_next();
      else
      {
        tmp_ptr = head_two->get_next();
        head_two->set_next(head_one->get_next());
        head_one->set_next(head_two);
        head_two = tmp_ptr;
        head_one = head_one->get_next();
      }
    }
    head_one->set_next(head_two);
  }
  else
  {
    head_three = head_two;
    while(head_two->get_next() != NULL)
    {
      if(*(head_two->get_data()) < *(head_one->get_data()))
        head_two = head_two->get_next();
      else
      {
        tmp_ptr = head_one->get_next();
        head_one->set_next(head_two->get_next());
        head_two->set_next(head_one);
        head_one = tmp_ptr;
        head_two = head_two->get_next();
      }
    }
    head_two->set_next(head_one);
  return head_three;
  }

אז ייתכן שיש לך באג ב-merge. תבדוק שהיא עובדת נכון (מחוץ ל-merge_sort).

המיון עובד טוב ל-2000 בערך אך עבור 5000 לא עובד.

כרגע המצב הוא שהמרג' סורט רקורסיבי כמו שאמור להיות והמרג' איטרטיבי, לא יודע למה זה לא עובד.

יש לך עצה נוספת?

אין לי רעיון... ניסית לעקוב בדיבאגר?

כן, אבל בגלל שזה לא שגיאת בקוד ה-stack overflow מתרחש כל פעם בריצה אחרת, שמתי את ה-breakpoint hit count, ופעם זה קורה בריצה ה-4000 ופעם בריצה ה-5000, זה כל פעם משתנה

אז תנסה גישה אחרת לדיבוג. breakpoint זו רק דרך אחת.

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

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

"השגיאה" בקוד היא שאתה עושה יותר מדי רקורסיה.

גודל המחסנית סופי.

עומק הרקורסיה ב-merge sort נכון ב-C הוא logN כך שלא אמורה להיות בעיה עם 5000 איברים וגם לא עם מיליון.

תכתוב לנו בפסודו קוד את האלגוריתם שאתה מממש, ונתחיל משם.

זאת השגיאה: ב-merge_sort

head_two = head->get_next()->get_next();

אמור להיות:

head_two = head_two->get_next()->get_next();

כרגע עובד עבור merge איטרטיבי, אבל עדיין לא עובד עבור merge רקורסיבי (stack overflow - עבור 10000 אבל כן עובד עבור 5000) , האם יש רעיון שיעבוד עבור merge רקורסיבי?

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

למה לך בכלל להשתמש ב-merge רקורסיבי? בעיקרון עדיף להימנע מרקורסיה כשאפשר, בדיוק בגלל הבעיות האלה.

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

סיבוכיות מקום של merge רקורסיבי היא O(N) ושל איטרטיבי הוא O(1).