streamalism.org

1. סקירה כללית

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

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

2. הצהרת בעיות

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

בערכה מסודרת של:

• מספר אי זוגי של מספרים שלמים, האלמנט האמצעי הוא החציון - בערכה המסודרת { 5, 7, 10 }, החציון הוא 7
• מספר זוגי שלם, אין אלמנט אמצעי; החציון מחושב כממוצע של שני האלמנטים האמצעיים - בסט המוזמן {5, 7, 8, 10}, החציון הוא (7 + 8) / 2 = 7.5

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

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

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

לדוגמה:

הוסף 5 // מיון-סט = {5}, גודל = 1 קבל חציון -> 5 הוסף 7 // מיון-סט = {5, 7}, גודל = 2 קבל חציון -> (5 + 7) / 2 = 6 הוסף 10 // מיון-סט = {5, 7, 10}, גודל = 3 קבל חציון -> 7 הוסף 8 // מיון-סט = {5, 7, 8, 10}, גודל = 4 קבל חציון -> ( 7 + 8) / 2 = 7.5 .. 

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

אנו יכולים לייצג את המשימות שלנו כפעולות הבאות בקוד:

בטל להוסיף (int num); כפול getMedian (); 

3. גישה נאיבית

3.1. מְמוּיָן רשימה

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

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

3.2. שיפור בגישה הנאיבית

ה לְהוֹסִיף הפעולה פועלת בזמן ליניארי, וזה לא אופטימלי. בואו ננסה להתייחס לכך בסעיף זה.

אנחנו יכולים לפצל את רשימה לשניים ממוינים רשימות – המחצית הקטנה יותר של המספרים השלמים ממוינת בסדר יורד, והחצי הגדול יותר של המספרים השלמים בסדר הולך וגדל. אנו יכולים להוסיף מספר שלם חדש למחצית המתאימה כך שגודל ה- רשימות שונה ב -1, לכל היותר:

אם האלמנט קטן מ- min. אלמנט של מחצית גדולה יותר: הכנס לחצי קטן יותר באינדקס המתאים אם מחצית קטנה יותר גדולה מחצי גדול יותר: הסר מקס. אלמנט של מחצית קטנה יותר והכנס בתחילת מחצית גדולה יותר (איזון מחדש) אחר הכנס למחצית גדולה יותר באינדקס המתאים: אם מחצית גדולה יותר בהרבה מחצי קטן יותר: הסר דק. אלמנט של מחצית גדולה יותר והכנס בתחילת מחצית קטנה יותר (איזון מחדש) 

כעת נוכל לחשב את החציון:

אם רשימות מכילות מספר שווה של אלמנטים: חציון = (אלמנט מקסימלי של מחצית קטנה + אלמנט של מחצית גדולה יותר) / 2 אחר אם מחצית קטנה יותר מכיל יותר אלמנטים: חציון = מקס. אלמנט של מחצית קטנה יותר אם מחצית גדולה יותר מכיל יותר אלמנטים: חציון = דקה. אלמנט של מחצית גדולה יותר

למרות ששיפרנו רק את מורכבות הזמן של לְהוֹסִיף פעולה על ידי גורם קבוע כלשהו, ​​התקדמנו.

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

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

4. ערימהגישה מבוססת

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

1. עלינו להכניס את האלמנט המינימלי / המקסימלי של מערך נתונים O (1) זְמַן
2. את האלמנטים לא צריך לשמור בסדר ממוין כל עוד אנו יכולים להשיג את האלמנט המינימלי / מקסימלי ביעילות
3. עלינו למצוא גישה להוספת אלמנט למערך הנתונים שעולה פחות מ- עַל) זְמַן

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

4.1. מבנה נתונים של ערימה

ערימה הוא מבנה נתונים המיושם בדרך כלל עם מערך אך ניתן לחשוב עליו כעץ בינארי.

הערמות מוגבלות על ידי רכוש הערימה:

4.1.1. מקסימום–נכס ערימה

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

4.1.2. דקה–נכס ערימה

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

בג'אווה, ה- PriorityQueue הכיתה מייצגת ערימה. בואו נתקדם לפיתרון הראשון שלנו באמצעות ערימות.

4.2. פיתרון ראשון

בואו נחליף את הרשימות בגישה הנאיבית שלנו בשתי ערימות:

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

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

אם גודל (minHeap)> size (maxHeap) + 1: הסר את אלמנט השורש של minHeap, הכנס ל- maxHeap אם גודל (maxHeap)> size (minHeap) + 1: הסר את אלמנט השורש של maxHeap, הכנס ל- minHeap

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

נשתמש ב- PriorityQueue בכיתה לייצג את הערימות. מאפיין הערימה המוגדר כברירת מחדל של PriorityQueue הוא מיני-ערימה. אנו יכולים ליצור ערימה מרבית באמצעות a Comparator.reverser סדר המשתמש בהיפוך הסדר הטבעי:

class MedianOfIntegerStream {תור פרטי minHeap, maxHeap; MedianOfIntegerStream () {minHeap = PriorityQueue חדש (); maxHeap = PriorityQueue חדש (Comparator.reverseOrder ()); } בטל להוסיף (int num) {if (! minHeap.isEmpty () && num minHeap.size () + 1) {minHeap.offer (maxHeap.poll ()); }} אחר {minHeap.offer (num); אם (minHeap.size ()> maxHeap.size () + 1) {maxHeap.offer (minHeap.poll ()); }}} כפול getMedian () חציון int; אם (minHeap.size () maxHeap.size ()) {חציון = minHeap.peek (); } אחר {חציון = (minHeap.peek () + maxHeap.peek ()) / 2; } חציון החזרה; }}

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

find-min / find-max O (1) delete-min / delete-max O (log n) insert O (log n) 

אז ה getMedian ניתן לבצע פעולה ב O (1) זמן כפי שהוא דורש את מצא-דק ו find-max פונקציות בלבד. מורכבות הזמן של לְהוֹסִיף הפעולה היא O (יומן n) שלוש לְהַכנִיס/לִמְחוֹק מתקשר לכל דורש O (יומן n) זְמַן.

4.3. פתרון משתנה בגודל הערמה

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

כפי שעשינו לפיתרון הקודם, אנו מתחילים בשתי ערמות - מיני ערימה וערימה מקסימלית. לאחר מכן, בואו נציג תנאי: גודל הערמה המקסימלית חייב להיות (n / 2) בכל עת, ואילו גודל הערימה המינימלית יכול להיות אחד או יותר (n / 2) אוֹ (n / 2) + 1, תלוי במספר האלמנטים הכולל בשתי הערימות. במילים אחרות, אנו יכולים לאפשר רק ל- min-heap להיות אלמנט נוסף, כאשר המספר הכולל של האלמנטים הוא אי זוגי.

בעזרת גודל הערימה שלנו, אנו יכולים לחשב את החציון כממוצע של יסודות השורש של שתי הערמות, אם הגודל של שתי הערמות הוא (n / 2). אחרת ה יסוד השורש של הערימה המינימלית הוא החציון.

כשאנחנו מוסיפים מספר שלם חדש, יש לנו שני תרחישים:

1. סה"כ של האלמנטים הקיימים הוא גודל אחיד (min-heap) == size (max-heap) == (n / 2) 2. סך הכל. של האלמנטים הקיימים הוא גודל מוזר (max-heap) == (n / 2) size (min-heap) == (n / 2) + 1 

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

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

בואו ניישם את הפתרון שלנו ב- Java באמצעות PriorityQueues:

class MedianOfIntegerStream {תור פרטי minHeap, maxHeap; MedianOfIntegerStream () {minHeap = PriorityQueue חדש (); maxHeap = PriorityQueue חדש (Comparator.reverseOrder ()); } בטל להוסיף (int num) {if (minHeap.size () == maxHeap.size ()) {maxHeap.offer (num); minHeap.offer (maxHeap.poll ()); } אחר {minHeap.offer (num); maxHeap.offer (minHeap.poll ()); }} כפול getMedian () חציון int; אם (minHeap.size ()> maxHeap.size ()) {חציון = minHeap.peek (); } אחר {חציון = (minHeap.peek () + maxHeap.peek ()) / 2; } חציון החזרה; }}

מורכבות הזמן של פעולותינו נותרות ללא שינוי: getMedian עלויות O (1) זמן, בזמן לְהוֹסִיף רץ בזמן O (יומן n) עם אותו מספר פעולות בדיוק.

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

5. סיכום

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

כרגיל, קוד המקור של כל הדוגמאות זמין ב- GitHub.