עבור לתוכן

stack overflow במיון מיזוג של רשימה מקושרת

Featured Replies

פורסם

שלום לכולם,

יצרתי רשימה מקושרת טמפלטית ומיון מיזוג מתאים, אני מקבל 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).

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים