Έγινε πριν λίγες μέρες Συνέδριο Ύδρας. Τα παιδιά από το JUG.ru Group προσκάλεσαν ονειρεμένους ομιλητές (Leslie Lamport! Cliff Click! Martin Kleppmann!) και αφιέρωσαν δύο ημέρες στα κατανεμημένα συστήματα και στους υπολογιστές. Ο Kontur ήταν ένας από τους τρεις εταίρους του συνεδρίου. Μιλήσαμε στο περίπτερο, μιλήσαμε για τον κατανεμημένο χώρο αποθήκευσης, παίξαμε μπίνγκο και λύσαμε γρίφους.

Αυτή είναι μια ανάρτηση με ανάλυση εργασιών στο περίπτερο Kontur από τον συγγραφέα του κειμένου τους. Ποιος ήταν στην Ύδρα - αυτός είναι ο λόγος σας για να θυμηθείτε την ευχάριστη εμπειρία, ποιος όχι - μια ευκαιρία να τεντώσετε τον εγκέφαλό σας μεγάλο Ο-σημειογραφία.

Υπήρχαν ακόμη και συμμετέχοντες που αποσυναρμολόγησαν το flipchart σε διαφάνειες για να καταγράψουν την απόφασή τους. Δεν αστειεύομαι - παρέδωσαν αυτή τη στοίβα χαρτί για επαλήθευση:

Συνολικά υπήρχαν τρεις εργασίες:

• σχετικά με την επιλογή αντιγράφων ανά βάρη για εξισορρόπηση φορτίου
• σχετικά με την ταξινόμηση των αποτελεσμάτων ερωτημάτων σε σχέση με μια βάση δεδομένων στη μνήμη
• σχετικά με τη μεταφορά κατάστασης σε ένα κατανεμημένο σύστημα με τοπολογία δακτυλίου

Εργασία 1. ClusterClient

Ήταν απαραίτητο να προταθεί ένας αλγόριθμος για την αποτελεσματική επιλογή Κ από Ν σταθμισμένα αντίγραφα ενός κατανεμημένου συστήματος:

Η ομάδα σας είναι επιφορτισμένη με την ανάπτυξη μιας βιβλιοθήκης πελατών για ένα μαζικά κατανεμημένο σύμπλεγμα N κόμβων. Η βιβλιοθήκη θα παρακολουθούσε διάφορα μεταδεδομένα που σχετίζονται με τους κόμβους (π.χ., τις καθυστερήσεις τους, τους ρυθμούς απόκρισης 4xx/5xx, κ.λπ.) και θα τους εκχωρούσε βάρη κινητής υποδιαστολής W1..WN. Προκειμένου να υποστηριχθεί η στρατηγική ταυτόχρονης εκτέλεσης, η βιβλιοθήκη θα πρέπει να μπορεί να επιλέγει τυχαία K από N κόμβους—η πιθανότητα επιλογής πρέπει να είναι ανάλογη με το βάρος ενός κόμβου.

Προτείνετε έναν αλγόριθμο για την αποτελεσματική επιλογή κόμβων. Υπολογίστε την υπολογιστική του πολυπλοκότητα χρησιμοποιώντας συμβολισμό μεγάλου Ο.

Γιατί είναι όλα στα αγγλικά;

Γιατί με αυτή τη μορφή οι συμμετέχοντες στο συνέδριο πολέμησαν μαζί τους και γιατί τα αγγλικά ήταν η επίσημη γλώσσα της Ύδρας. Οι εργασίες έμοιαζαν ως εξής:

Πάρτε χαρτί και μολύβι, σκεφτείτε, μην βιαστείτε να ανοίξετε σπόιλερ αμέσως 🙂

Ανάλυση της λύσης (βίντεο)

Έναρξη στις 5:53, μόνο 4 λεπτά:

Και να πώς τα παιδιά με το flipchart έθεσαν τη λύση τους:

Ανάλυση της λύσης (κείμενο)

Η ακόλουθη λύση βρίσκεται στην επιφάνεια: αθροίστε τα βάρη όλων των αντιγράφων, δημιουργήστε έναν τυχαίο αριθμό από το 0 στο άθροισμα όλων των βαρών και, στη συνέχεια, επιλέξτε ένα αντίγραφο i έτσι ώστε το άθροισμα των βαρών των αντιγράφων από 0 έως (i-1) ου είναι μικρότερος από έναν τυχαίο αριθμό και το άθροισμα των αντιγράφων βαραίνει από το 0 έως το i-ο - περισσότερο από αυτό. Έτσι, θα είναι δυνατό να επιλέξετε ένα αντίγραφο και για να επιλέξετε το επόμενο, πρέπει να επαναλάβετε ολόκληρη τη διαδικασία χωρίς να λάβετε υπόψη το επιλεγμένο αντίγραφο. Με έναν τέτοιο αλγόριθμο, η πολυπλοκότητα της επιλογής ενός αντιγράφου είναι 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) .

Η πολυπλοκότητα γραμμικού ημερολογίου είναι πιο ωραία από την τετραγωνική πολυπλοκότητα, ειδικά για μεγάλο Κ.

Αυτός είναι ο αλγόριθμος υλοποιείται σε κώδικα Βιβλιοθήκες ClusterClient από το έργο "Ανατολή". (Εκεί, το δέντρο είναι ενσωματωμένο σε O(N lg N), αλλά αυτό δεν επηρεάζει την τελική πολυπλοκότητα του αλγορίθμου.)

Εργασία 2. Ζέβρα

Ήταν απαραίτητο να προταθεί ένας αλγόριθμος για την αποτελεσματική ταξινόμηση των εγγράφων στη μνήμη από ένα αυθαίρετο μη ευρετηριασμένο πεδίο:

Η ομάδα σας είναι επιφορτισμένη με την ανάπτυξη μιας βάσης δεδομένων εγγράφων με κοινόχρηστη μνήμη. Ένας συνηθισμένος φόρτος εργασίας θα ήταν να επιλέξετε κορυφαία N έγγραφα ταξινομημένα με ένα αυθαίρετο (μη ευρετηριασμένο) αριθμητικό πεδίο από μια συλλογή μεγέθους M (συνήθως N < 100 << M). Ένας ελαφρώς λιγότερο συνηθισμένος φόρτος εργασίας θα ήταν να επιλέξετε το επάνω N μετά την παράλειψη των κορυφαίων εγγράφων S (S ~ N).

Προτείνετε έναν αλγόριθμο για την αποτελεσματική εκτέλεση τέτοιων ερωτημάτων. Υπολογίστε την υπολογιστική του πολυπλοκότητα χρησιμοποιώντας συμβολισμό μεγάλου Ο στη μέση περίπτωση και τα χειρότερα σενάρια.

Ανάλυση της λύσης (βίντεο)

Έναρξη στις 34:50, μόνο 6 λεπτά:

Ανάλυση της λύσης (κείμενο)

Επιφανειακή λύση: ταξινομήστε όλα τα έγγραφα (για παράδειγμα με γρήγορη ταξινόμηση), μετά πάρτε έγγραφα N+S. Σε αυτή την περίπτωση, η πολυπλοκότητα της ταξινόμησης είναι κατά μέσο όρο O(M lg M), στη χειρότερη O(M2).

Είναι προφανές ότι η ταξινόμηση όλων των εγγράφων M και στη συνέχεια η λήψη μόνο ενός μικρού μέρους τους είναι αναποτελεσματική. Για να μην ταξινομούνται όλα τα έγγραφα, είναι κατάλληλος ένας αλγόριθμος γρήγορη επιλογή, το οποίο θα επιλέξει N + S των επιθυμητών εγγράφων (μπορούν να ταξινομηθούν με οποιονδήποτε αλγόριθμο). Σε αυτή την περίπτωση, η πολυπλοκότητα θα μειωθεί στο O(M) κατά μέσο όρο, ενώ η χειρότερη περίπτωση θα παραμείνει ίδια.

Ωστόσο, μπορείτε να το κάνετε ακόμα πιο αποτελεσματικά - χρησιμοποιήστε τον αλγόριθμο δυαδική ροή σωρού. Σε αυτήν την περίπτωση, τα πρώτα έγγραφα N+S προστίθενται στο ελάχιστο ή μέγιστο σωρό (ανάλογα με την κατεύθυνση ταξινόμησης) και, στη συνέχεια, κάθε επόμενο έγγραφο συγκρίνεται με τη ρίζα του δέντρου, που περιέχει το τρέχον ελάχιστο ή μέγιστο έγγραφο, και προστίθεται στο δέντρο αν χρειάζεται. . Σε αυτήν την περίπτωση, η πολυπλοκότητα στη χειρότερη περίπτωση, όταν πρέπει να ξαναφτιάχνεις συνεχώς το δέντρο, είναι O(M lg M), η πολυπλοκότητα κατά μέσο όρο είναι O(M), όπως και με τη γρήγορη επιλογή.

Ωστόσο, η ροή σωρού αποδεικνύεται πιο αποτελεσματική λόγω του γεγονότος ότι στην πράξη τα περισσότερα από τα έγγραφα μπορούν να απορριφθούν χωρίς να ξαναδημιουργηθεί ο σωρός μετά από μία μόνο σύγκριση με το ριζικό στοιχείο του. Αυτή η ταξινόμηση υλοποιείται στη βάση δεδομένων εγγράφων στη μνήμη Zebra που αναπτύχθηκε και χρησιμοποιείται στο Kontur.

Εργασία 3. Ανταλλαγές κρατών

Ήταν απαραίτητο να προταθεί ο πιο αποτελεσματικός αλγόριθμος για τη μετατόπιση καταστάσεων:

Η ομάδα σας είναι επιφορτισμένη με την ανάπτυξη ενός φανταχτερού μηχανισμού ανταλλαγής καταστάσεων για ένα κατανεμημένο σύμπλεγμα Ν κόμβων. Η κατάσταση του i-ου κόμβου θα πρέπει να μεταφερθεί στον (i+1)-ο κόμβο, η κατάσταση του N-ου κόμβου θα πρέπει να μεταφερθεί στον πρώτο κόμβο. Η μόνη υποστηριζόμενη λειτουργία είναι η ανταλλαγή καταστάσεων όταν δύο κόμβοι ανταλλάσσουν τις καταστάσεις τους ατομικά. Είναι γνωστό ότι μια ανταλλαγή κατάστασης διαρκεί M χιλιοστά του δευτερολέπτου. Κάθε κόμβος είναι σε θέση να συμμετέχει σε μια ενιαία ανταλλαγή κατάστασης ανά πάσα στιγμή.

Πόσος χρόνος χρειάζεται για να μεταφερθούν οι καταστάσεις όλων των κόμβων σε ένα σύμπλεγμα;

Ανάλυση της λύσης (κείμενο)

Επιφανειακή λύση: ανταλλάξτε τις καταστάσεις του πρώτου και του δεύτερου στοιχείου, μετά το πρώτο και το τρίτο, μετά το πρώτο και το τέταρτο και ούτω καθεξής. Μετά από κάθε ανταλλαγή, η κατάσταση ενός στοιχείου θα βρίσκεται στην επιθυμητή θέση. Πρέπει να κάνετε μεταθέσεις O(N) και να ξοδέψετε χρόνο O(N M).

Ο γραμμικός χρόνος είναι μεγάλος, επομένως μπορείτε να ανταλλάξετε τις καταστάσεις των στοιχείων σε ζεύγη: το πρώτο με το δεύτερο, το τρίτο με το τέταρτο και ούτω καθεξής. Μετά από κάθε ανταλλαγή κράτους, κάθε δεύτερο στοιχείο θα βρίσκεται στη σωστή θέση. Πρέπει να κάνετε μεταθέσεις O(lg N) και να ξοδέψετε χρόνο O(M lg N).

Ωστόσο, είναι δυνατό να γίνει η μετατόπιση ακόμη πιο αποτελεσματική - όχι σε γραμμικό, αλλά σε σταθερό χρόνο. Για να γίνει αυτό, στο πρώτο βήμα, πρέπει να ανταλλάξετε την κατάσταση του πρώτου στοιχείου με το τελευταίο, το δεύτερο με το προτελευταίο κ.ο.κ. Η κατάσταση του τελευταίου στοιχείου θα είναι στη σωστή θέση. Και τώρα πρέπει να ανταλλάξουμε την κατάσταση του δεύτερου στοιχείου με το τελευταίο, του τρίτου με το προτελευταίο και ούτω καθεξής. Μετά από αυτόν τον γύρο ανταλλαγών, οι πολιτείες όλων των στοιχείων θα βρίσκονται στη σωστή θέση. Συνολικά θα υπάρχουν μεταθέσεις O(2M) ~ O(1).

Μια τέτοια λύση δεν θα εκπλήξει καθόλου έναν μαθηματικό που εξακολουθεί να θυμάται ότι μια περιστροφή είναι μια σύνθεση δύο αξονικών συμμετριών. Παρεμπιπτόντως, γενικεύεται επιπόλαια για μια μετατόπιση όχι κατά μία, αλλά κατά K < N θέσεις. (Γράψτε στα σχόλια πώς ακριβώς.)

Σας άρεσαν τα παζλ; Ξέρεις άλλες λύσεις; Κοινοποιήστε στα σχόλια.

Και εδώ είναι ορισμένοι χρήσιμοι σύνδεσμοι στο τέλος:

• Μάθε περισσότερα για ανάπτυξη υποδομών στο περίγραμμα
• δείτε εγγραφές εσωτερικών φυλλάδιο με αναφορές σχετικά με τα κατανεμημένα συστήματα
• παρακολουθήστε τη σειρά διαλέξεων βίντεοΑσυνήθιστοι αλγόριθμοι για απλούς ανθρώπους»
• εγγραφείτε στο δικό μας κανάλι στο Telegram

Πηγή: www.habr.com