Αλγόριθμοι και συλλογές: hashing, ουρές και ταξινόμηση — DedSec Project
Αλγόριθμοι και συλλογές: hashing, ουρές και ταξινόμηση Λεξικά κατακερματισμού και σύνολα Μηχανισμός και όρια Τα hash maps αντιστοιχίζουν κλειδιά σε τιμές, ενώ sets κρατούν membership. Μέσο…
Λεξικά κατακερματισμού και σύνολα
Μηχανισμός και όρια
Τα hash maps αντιστοιχίζουν κλειδιά σε τιμές, ενώ sets κρατούν membership. Μέσο lookup συχνά O(1), αλλά equality/hash rules και collisions επηρεάζουν απόδοση.
Παράδειγμα υλοποίησης
from collections import Counter
counts=Counter(['red','blue','red'])
assert counts['red']==2
assert {'red','blue'}==set(counts)
Αναπαραγωγή και έλεγχος
Φτιάξε duplicate detection με set και σύγκρινε με nested list search. Δοκίμασε list ως key και διάβασε TypeError.
Απαραίτητα τεκμήρια
Για Hash maps and sets, κατέγραψε ποια είσοδος αλλάζει το αποτέλεσμα, ποια πράξη ευθύνεται και ένα test που θα αποκάλυπτε λάθος. Μέτρησε μνήμη ή χρόνο όταν επηρεάζουν τον ισχυρισμό και μην θεωρείς ένα demo απόδειξη για όλες τις εισόδους.
Στοίβες και ουρές
Μηχανισμός και όρια
Stack επεξεργάζεται νεότερο στοιχείο πρώτα (LIFO), queue παλαιότερο (FIFO). DFS χρησιμοποιεί stack, BFS queue· η αντικατάσταση αλλάζει σειρά αναζήτησης.
Παράδειγμα υλοποίησης
from collections import deque
s=[1,2]; q=deque([1,2]);
assert s.pop()==2
assert q.popleft()==1
Αναπαραγωγή και έλεγχος
Έλεγξε parentheses με stack και σειρά εργασιών με deque. Γιατί list.pop(0) έχει διαφορετικό κόστος από deque.popleft();
Απαραίτητα τεκμήρια
Για Stacks and queues, κατέγραψε ποια είσοδος αλλάζει το αποτέλεσμα, ποια πράξη ευθύνεται και ένα test που θα αποκάλυπτε λάθος. Μέτρησε μνήμη ή χρόνο όταν επηρεάζουν τον ισχυρισμό και μην θεωρείς ένα demo απόδειξη για όλες τις εισόδους.
Ταξινόμηση και σταθερή σειρά
Μηχανισμός και όρια
Stable sorting διατηρεί τη σχετική σειρά ισοδύναμων στοιχείων. Επιτρέπει multi-key sorting με passes από λιγότερο σημαντικό προς πιο σημαντικό κριτήριο.
Παράδειγμα υλοποίησης
rows=[('Ada',2),('Bob',1),('Carl',2)]
result=sorted(rows,key=lambda r:r[1]);
assert result==[('Bob',1),('Ada',2),('Carl',2)]
Αναπαραγωγή και έλεγχος
Αντιστροφή equal-score rows και έλεγχος σταθερότητας. Πρόσθεσε sort ονόματος και μετά score· εξήγησε τη σημασία σειράς passes.
Απαραίτητα τεκμήρια
Για Sorting and stable ordering, κατέγραψε ποια είσοδος αλλάζει το αποτέλεσμα, ποια πράξη ευθύνεται και ένα test που θα αποκάλυπτε λάθος. Μέτρησε μνήμη ή χρόνο όταν επηρεάζουν τον ισχυρισμό και μην θεωρείς ένα demo απόδειξη για όλες τις εισόδους.
Πρόσθετη τεχνική ανάλυση
Η ταξινομημένη διάσχιση χρειάζεται μοναδικό κριτήριο ισοπαλίας ακόμη κι αν hash map βρίσκει αποτελεσματικά εγγραφές. Σε σελιδοποιημένα αποτελέσματα αποθήκευσε ολόκληρο το κλειδί σειράς στον cursor. Έτσι διαχωρίζεις ταυτότητα αναζήτησης από σειρά διάσχισης όταν πολλά συμβάντα μοιράζονται μία χρονική τιμή.