streamalism.org

1. הקדמה

רשימה המקושרת יחידה היא רצף של צמתים מחוברים המסתיימים ב- ריק התייחסות. עם זאת, בתרחישים מסוימים, הצומת האחרון עשוי להצביע על צומת קודמת - וליצור למעשה מחזור.

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

2. איתור מחזור

בואו נבדוק כעת כמה אלגוריתמים לאיתור מחזורים ברשימות מקושרות.

2.1. כוח הברוט - O (n ^ 2) מורכבות הזמן

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

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

גילוי מחזור בולטי סטטי ציבורי (head node) {if (head == null) {return false; } צומת it1 = ראש; int nodesTraversedByOuter = 0; ואילו (it1! = null && it1.next! = null) {it1 = it1.next; nodesTraversedByOuter ++; int x = nodesTraversedByOuter; צומת it2 = ראש; int noOfTimesCurrentNodeVisited = 0; ואילו (x> 0) {it2 = it2.next; אם (it2 == it1) {noOfTimesCurrentNodeVisited ++; } אם (noOfTimesCurrentNodeVisited == 2) {return true; } איקס--; }} להחזיר שקר; }

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

2.2. Hashing - O (n) מורכבות החלל

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

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

גילוי מחזור בולטי סטטי ציבורי (head node) {if (head == null) {return false; } הגדר set = חדש HashSet (); צומת צומת = ראש; בעוד (node! = null) {if (set.contains (node)) {return true; } set.add (צומת); node = node.next; } להחזיר שקר; }

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

2.3. מצביעים מהירים ואיטיים

ניתן להסביר את האלגוריתם הבא למציאת מחזורים באמצעות מטאפורה.

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

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

לפיכך, אם שני האיטרטורים נפגשים בנקודה כלשהי, אנו יכולים להסיק שנפלנו על מחזור:

גילוי מחזור סטטי ציבורי CycleDetectionResult (ראש הצומת) {if (head == null) {להחזיר CycleDetectionResult חדש (false, null); } צומת איטי = ראש; צומת מהיר = ראש; ואילו (מהר! = null && fast.next! = null) {slow = slow.next; מהיר = fast.next.next; אם (איטי == מהיר) {להחזיר CycleDetectionResult חדש (נכון, מהיר); }} להחזיר CycleDetectionResult חדש (false, null); }

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

מחלקה ציבורית CycleDetectionResult {מחזור בוליאני קיים; צומת צומת; }

שיטה זו ידועה גם בשם 'אלגוריתם הצב והארנבה' או 'אלגוריתם מציאת מחזור זבובים'.

3. הוצאת מחזורים מרשימה

בואו נסתכל על כמה שיטות להסרת מחזורים. כל השיטות הללו מניחות ש'אלגוריתם מציאת מחזור Flyods 'שימש לזיהוי מחזור ובנוי עליו.

3.1. בכוח הזרוע

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

זה מסתיים מתי ptr מגיע לתחילת הלולאה מכיוון שזו הנקודה הראשונה כאשר היא נכנסת ללולאה והופכת לנגישה מנקודת המפגש.

לאחר תחילת הלולאה (bg) מתגלה, אז זה טריוויאלי למצוא את סוף המחזור (צומת ששדה הבא מצביע עליו bg). המצביע הבא של צומת קצה זה מוגדר לאחר מכן ריק להסרת המחזור:

מחלקה ציבורית CycleRemovalBruteForce {private static void removeCycle (Node loopNodeParam, head node) {Node it = head; ואילו (it! = null) {if (isNodeReachableFromLoopNode (it, loopNodeParam)) {Node loopStart = it; findEndNodeAndBreakCycle (loopStart); לשבור; } זה = it.next; }} בוליאני סטטי פרטי isNodeReachableFromLoopNode (צומת את זה, Node loopNodeParam) {Node loopNode = loopNodeParam; לעשות {if (it == loopNode) {להחזיר נכון; } loopNode = loopNode.next; } בעוד (loopNode.next! = loopNodeParam); להחזיר כוזב; } ריק סטטי פרטי findEndNodeAndBreakCycle (Node loopStartParam) {Node loopStart = loopStartParam; בעוד (loopStart.next! = loopStartParam) {loopStart = loopStart.next; } loopStart.next = null; }}

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

3.2. פתרון מותאם - ספירת צמתים

בואו נגדיר תחילה כמה משתנים:

• נ = גודל הרשימה
• k = המרחק מראש הרשימה לתחילת המחזור
• l = גודל המחזור

יש לנו הקשר הבא בין המשתנים הללו:

k + l = n

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

הנה מתווה האלגוריתם:

1. ברגע שמהיר והאיטרטורים האיטיים נפגשים, מצא את אורך המחזור. ניתן לעשות זאת על ידי שמירה על אחד האיטרטורים במקום תוך המשך האיטרטור השני (איטרציה במהירות רגילה, אחד אחד) עד שהוא מגיע לסמן הראשון, תוך שמירה על ספירת הצמתים שביקרו. זה נחשב כ l
2. קח שני איטרטורים (ptr1 ו ptr2) בתחילת הרשימה. הזז אחד מאיטרטור (ptr2) l צעדים
3. כעת חזרו על שני האיטרטורים עד שהם נפגשים בתחילת הלולאה, לאחר מכן, מצאו את סוף המחזור והצביעו עליו ריק

זה עובד בגלל ptr1 הוא k צעדים ספורים מהלולאה, ו ptr2, שמתקדם על ידי l צעדים, גם צרכים k צעדים כדי להגיע לסוף הלולאה (n - l = k).

והנה יישום פשוט ופוטנציאלי:

מחלקה ציבורית CycleRemovalByCountingLoopNodes {ריק סטטי פרטי removeCycle (Node loopNodeParam, ראש הצומת) {int cycleLength = calcCycleLength (loopNodeParam); צומת cycleLengthAdvancedIterator = ראש; צומת את זה = ראש; עבור (int i = 0; i <cycleLength; i ++) {cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } בעוד (it.next! = cycleLengthAdvancedIterator.next) {it = it.next; cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } cycleLengthAdvancedIterator.next = null; } int סטטי פרטי calcCycleLength (Node loopNodeParam) {Node loopNode = loopNodeParam; אורך int = 1; בעוד (loopNode.next! = loopNodeParam) {אורך ++; loopNode = loopNode.next; } אורך החזרה; }}

לאחר מכן, בואו נתמקד בשיטה בה נוכל אפילו לבטל את שלב חישוב אורך הלולאה.

3.3. פתרון אופטימלי - מבלי לספור את צמתי הלולאה

בואו נשווה את המרחקים שהמצביעים המהירים והאיטיים עברו מתמטית.

לשם כך, אנו זקוקים לעוד כמה משתנים:

• y = מרחק הנקודה בה נפגשים שני האיטרטורים, כפי שנראה מתחילת המחזור
• z = מרחק הנקודה בה נפגשים שני האיטרטורים, כפי שנראה מסוף המחזור (גם זה שווה ל- אני - y)
• M = מספר הפעמים שהאיטרטור המהיר השלים את המחזור לפני שהאיטרטור האיטי נכנס למחזור

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

• מרחק שעבר באמצעות מצביע איטי = k (מרחק המחזור מהראש) + y (נקודת מפגש בתוך מחזור)
• מרחק שעבר באמצעות מצביע מהיר = k (מרחק המחזור מהראש) + M (מספר פעמים מצביע מהיר השלים את המחזור לפני כניסה של מצביע איטי) * l (אורך מחזור) + y (נקודת מפגש בתוך מחזור)

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

k + m * l + y = 2 * (k + y)

אשר מעריך ל:

y = m * l - k

חיסור משני הצדדים מ l נותן:

l - y = l - m * l + k

או באופן שווה:

k = (m - 1) * l + z (כאשר, l - y הוא z כפי שהוגדר לעיל)

זה מוביל ל:

k = (m - 1) ריצות לולאה מלאה + מרחק נוסף z

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

1. השתמש ב'אלגוריתם איתור מחזור של Flyods 'כדי לזהות את הלולאה. אם קיימת לולאה, האלגוריתם הזה יסתיים בנקודה בתוך הלולאה (קרא לזה נקודת המפגש)
2. קח שני איטרטורים, אחד בראש הרשימה (זה 1) ואחת בנקודת המפגש (it2)
3. חצו את שני האיטרטורים באותה מהירות
4. מכיוון שמרחק הלולאה מהראש הוא k (כפי שהוגדר לעיל), האיטרטור שהתחיל מהראש יגיע למחזור לאחר מכן k צעדים
5. ב k צעדים, איטרטור it2 היה חוצה מ '- 1 מחזורי לולאה ומרחק נוסף z. מכיוון שהמצביע הזה כבר היה במרחק של z מתחילת המחזור, חוצה את המרחק הנוסף הזה z, היה מביא את זה גם בתחילת המחזור
6. שני האיטרטורים נפגשים בתחילת המחזור, לאחר מכן נוכל למצוא את סוף המחזור ולהצביע עליו ריק

ניתן ליישם זאת:

מחלקה ציבורית CycleRemovalWithoutCountingLoopNodes {ריק סטטי פרטי removeCycle (צומת MeetingPointParam, ראש צומת) {Node loopNode = MeetingPointParam; צומת את זה = ראש; ואילו (loopNode.next! = it.next) {it = it.next; loopNode = loopNode.next; } loopNode.next = null; }}

זוהי הגישה המותאמת ביותר לגילוי והסרת מחזורים מרשימה מקושרת.

4. מסקנה

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

לבסוף, הראינו גם שלוש שיטות להסרת מחזור, לאחר שהוא מתגלה באמצעות 'אלגוריתם מציאת מחזור Flyods'.

דוגמת הקוד המלא זמינה ב- Github.