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

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

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

היו שלוש משימות בסך הכל:

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

משימה 1. ClusterClient

היה צורך להציע אלגוריתם לבחירה יעילה של K מתוך N העתקים משוקללים של מערכת מבוזרת:

על הצוות שלך מוטלת המשימה לפתח ספריית לקוח עבור אשכול מבוזר מאסיבי של N צמתים. הספרייה תעקוב אחר מטא נתונים שונים הקשורים לצמתים (למשל, זמן האחזור שלהם, שיעורי תגובה של 4xx/5xx וכו') ותקצה להם משקלי נקודה צפה W1..WN. על מנת לתמוך באסטרטגיית הביצוע במקביל, הספרייה צריכה להיות מסוגלת לבחור K מתוך N צמתים באופן אקראי - הסיכוי להיבחר צריך להיות פרופורציונלי למשקל הצומת.

הצע אלגוריתם לבחירת צמתים ביעילות. הערך את המורכבות החישובית שלו באמצעות סימון O גדול.

למה הכל באנגלית?

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

קחו נייר ועיפרון, תחשבו, אל תמהרו לפתוח ספוילרים מיד 🙂

ניתוח הפתרון (וידאו)

החל מ-5:53, 4 דקות בלבד:

והנה איך החבר'ה עם הפליפצ'ר העלו את הפתרון שלהם:

ניתוח הפתרון (טקסט)

הפתרון הבא נמצא על פני השטח: סכם את המשקולות של כל ההעתקים, צור מספר אקראי מ-0 לסכום כל המשקולות, ולאחר מכן בחר עותק i כך שסכום משקלי העתק מ-0 עד (i-1) הוא קטן ממספר אקראי, וסכום המשקל של העתק מ-0 עד i-th - יותר ממנו. אז ניתן יהיה לבחור העתק אחד, וכדי לבחור את הבא, עליך לחזור על כל ההליך מבלי להתחשב בהעתק שנבחר. עם אלגוריתם כזה, המורכבות של בחירת העתק אחד היא O(N), המורכבות של בחירת העתקים של K היא O(N K) ~ O(N2).

המורכבות הריבועית היא גרועה, אך ניתן לשפר אותה. לשם כך, נבנה עץ מקטע עבור סכומי משקלים. יתקבל עץ בעומק lg N, שעליו יהיו משקולות העתק, ובשאר הצמתים - סכומים חלקיים, עד לסכום כל המשקולות בשורש העץ. לאחר מכן, אנו יוצרים מספר אקראי מ-0 לסכום כל המשקולות, מוצאים את ההעתק ה-i, מסירים אותו מהעץ וחוזרים על ההליך כדי למצוא את ההעתקים הנותרים. עם אלגוריתם זה, המורכבות של בניית עץ היא O(N), המורכבות של מציאת העתק ה-i והסרתו מהעץ היא O(lg N), המורכבות של בחירת העתקים של K היא O(N + K lg N) ~ O(N lg N) .

המורכבות של לוג ליניארי טובה יותר ממורכבות ריבועית, במיוחד עבור K גדול.

זה האלגוריתם הזה מיושם בקוד ספריות ClusterClient מהפרויקט "Оосток". (שם, העץ בנוי ב-O(N lg N), אבל זה לא משפיע על המורכבות הסופית של האלגוריתם.)

משימה 2. זברה

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

על הצוות שלך מוטלת המשימה לפתח מסד נתונים של מסמכים בזיכרון. עומס עבודה נפוץ יהיה בחירת N מסמכים ממוינים על פי שדה מספרי שרירותי (שאינו מצורף לאינדקס) מתוך אוסף בגודל M (בדרך כלל N < 100 << M). עומס עבודה מעט פחות נפוץ יהיה בחירת N העליון לאחר דילוג על מסמכי S מובילים (S ~ N).

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

ניתוח הפתרון (וידאו)

החל מ-34:50, 6 דקות בלבד:

ניתוח הפתרון (טקסט)

פתרון משטח: מיין את כל המסמכים (לדוגמה עם סידור מהיר), ואז קח מסמכי N+S. במקרה זה, מורכבות המיון היא בממוצע O(M lg M), במקרה הרע O(M2).

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

עם זאת, אתה יכול לעשות את זה אפילו יותר ביעילות - השתמש באלגוריתם הזרמת ערימה בינארית. במקרה זה, המסמכים הראשונים של N+S מתווספים ל-min- או max-heap (בהתאם לכיוון המיון), ואז כל מסמך הבא מושווה לשורש העץ, המכיל את המסמך המינימלי או המקסימלי הנוכחי, ומתווסף לעץ במידת הצורך. . במקרה זה, המורכבות במקרה הגרוע ביותר, כאשר אתה צריך כל הזמן לבנות מחדש את העץ, היא O(M lg M), המורכבות בממוצע היא O(M), כמו ב-quickselect.

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

משימה 3. חילופי מדינה

היה צורך להציע את האלגוריתם היעיל ביותר לשינוי מצבים:

על הצוות שלך מוטלת המשימה לפתח מנגנון חילופי מצבים מהודר עבור אשכול מבוזר של N צמתים. יש להעביר את מצב הצומת ה-I לצומת (i+1) הצומת, יש להעביר את מצב הצומת ה-N לצומת הראשון. הפעולה הנתמכת היחידה היא חילופי המצבים כאשר שני צמתים מחליפים את המצבים שלהם בצורה אטומית. ידוע שהחלפת מצב לוקחת M אלפיות שניות. כל צומת מסוגל להשתתף בהחלפת מצב בודדת בכל רגע נתון.

כמה זמן לוקח להעביר את המצבים של כל הצמתים באשכול?

ניתוח הפתרון (טקסט)

פתרון משטח: החלף את המצבים של האלמנט הראשון והשני, לאחר מכן הראשון והשלישי, לאחר מכן הראשון והרביעי וכן הלאה. לאחר כל החלפה, המצב של אלמנט אחד יהיה במיקום הרצוי. אתה צריך לעשות תמורות O(N) ולבלות זמן O(N M).

הזמן הליניארי הוא ארוך, אז אתה יכול להחליף את המצבים של אלמנטים בזוגות: הראשון עם השני, השלישי עם הרביעי, וכן הלאה. לאחר כל חילופי מדינה, כל אלמנט שני יהיה במיקום הנכון. אתה צריך לעשות תמורות O(lg N) ולבזבז זמן O(M lg N).

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

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

אהבתם פאזלים? מכירים פתרונות אחרים? שתפו בתגובות.

והנה כמה קישורים שימושיים בסופו של דבר:

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

מקור: www.habr.com