Τοπολογική ταξινόμηση — ασφαλής σειρά εργασιών με εξαρτήσεις

Παράδειγμα από πραγματική διαδικασία κατασκευής

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

Αρχεία και τέσσερις εκτελέσιμοι έλεγχοι

Εκτέλεσε python3 23_topological_sort.py. Κατόπιν αποθήκευσε το παρακάτω ως test_topo.py στον ίδιο κατάλογο και εκτέλεσε python3 test_topo.py. Η δοκιμή ελέγχει τη σωστή προτεραιότητα χωρίς να απαιτεί συγκεκριμένη τυχαία σειρά ανεξάρτητων εργασιών.

from runpy import run_path
topological = run_path("23_topological_sort.py")["topological"]
order = topological({
    "release": ["test"], "test": ["build"], "build": []
})
assert order.index("build") < order.index("test") < order.index("release")
assert topological({"release": ["test"]}) == ["test", "release"]
assert topological({}) == []
try:
    topological({"a": ["b"], "b": ["a"]})
except ValueError:
    pass
else:
    raise AssertionError("dependency cycle accepted")
print("PASS dependency order, inferred node, empty input and cycle")

Κατανόηση της υλοποίησης

Ο κώδικας συλλέγει κόμβους τόσο από τα κλειδιά του λεξικού όσο και από τις αναφερόμενες εξαρτήσεις. Επομένως, το topological({'release':['test']}) δημιουργεί έμμεσα έναν κόμβο test ακόμη και χωρίς ξεχωριστό ορισμό. Αυτή η πολιτική μπορεί να είναι χρήσιμη, αλλά σε εργαλείο build μπορεί να κρύβει τυπογραφικό λάθος ή ελλιπή εργασία. Η αρχική ουρά και τα παιδιά ταξινομούνται για επαναλήψιμη έξοδο με ονόματα που συγκρίνονται. Η βασική πολυπλοκότητα είναι O(V + E) χωρίς την ταξινόμηση· η επιπλέον ταξινόμηση προσθέτει κόστος συγκρίσεων ώστε να υπάρχει προβλέψιμη σειρά.

Ασκήσεις διάγνωσης

1. Πρόσθεσε ανεξάρτητο βήμα lint και έλεγξε ότι εμφανίζεται, παρότι μπορεί να υπάρχουν περισσότερες από μία έγκυρες σειρές.
2. Δημιούργησε κύκλο build -> test -> build. Εξήγησε γιατί η επιστροφή μερικής λίστας θα μπορούσε να παρακάμψει κρίσιμο έλεγχο.
3. Πρόσθεσε τυπογραφικό λάθος όπως biuld αντί build. Παρατήρησε ότι ο άγνωστος κόμβος προστίθεται σιωπηλά και σχεδίασε αυστηρή εκδοχή που απορρίπτει άγνωστα προαπαιτούμενα.
4. Γράψε δύο φορές την ίδια εξάρτηση. Η set(needs) τη μετρά μία φορά· αποφάσισε αν ο έλεγχος εισόδου πρέπει να απορρίπτει τις επαναλήψεις.
5. Δημιούργησε αλυσίδα χιλίων εργασιών και επιβεβαίωσε ότι κάθε προαπαιτούμενο προηγείται.

Παραδοτέα: PASS, σαφής απόρριψη κύκλου, έλεγχος άγνωστης εργασίας και καταγεγραμμένη πολιτική σειράς.