Ασκήσεις αλγορίθμων: γραμμική/δυαδική αναζήτηση και συχνότητες — DedSec Project

Ασκήσεις αλγορίθμων: γραμμική/δυαδική αναζήτηση και συχνότητες Γραμμική αναζήτηση Reference implementation (Python 3) Μηχανισμός Εξετάζουμε τη λίστα από δείκτη 0. Στην αρχή κάθε βήματος i…

Γραμμική αναζήτηση

Reference implementation (Python 3)

def find_index(items, target):
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1
assert find_index([4, 8, 2], 8) == 1
assert find_index([], 8) == -1

Μηχανισμός

Εξετάζουμε τη λίστα από δείκτη 0. Στην αρχή κάθε βήματος i ξέρουμε ότι κανένα προηγούμενο στοιχείο δεν ταίριαξε· επομένως η άμεση επιστροφή εγγυάται την πρώτη εμφάνιση. Η τιμή -1 σημαίνει «δεν βρέθηκε», όχι έγκυρος δείκτης Python για προσπέλαση. Στη χειρότερη περίπτωση γίνονται n συγκρίσεις, δηλαδή O(n) χρόνος και O(1) επιπλέον μνήμη.

Κώδικας αναφοράς

Το ίδιο πρόγραμμα υπάρχει ως 01_linear_search.py με εκτελέσιμες assertions. Λειτουργεί και σε μη ταξινομημένα δεδομένα. Η ταξινόμηση μόνο για μία αναζήτηση επιβαρύνει το κόστος και ενδέχεται να αλλάξει αρχικούς δείκτες.

Πρακτικές δοκιμές

Για [] και στόχο 8 παίρνουμε -1 χωρίς καμία σύγκριση.
Για [8,8,3] και στόχο 8 παίρνουμε 0, όχι 1. Τα duplicates ελέγχουν το συμβόλαιο πρώτης θέσης.
Για [4,8,2] και στόχο 2 παίρνουμε 2, αφού σαρωθεί όλη η λίστα.
Πρόσθεσε μετρητή συγκρίσεων για πρώτη, τελευταία και ανύπαρκτη τιμή με 10, 100 και 1000 στοιχεία· σύγκρινε την αύξηση.
Εξήγησε πώς επηρεάζουν οι κανόνες ισότητας της Python τις τιμές None, strings και integers.

Επόμενη επιλογή

Για πολλές αναζητήσεις μπορείς να δημιουργήσεις index που αποθηκεύει την πρώτη θέση κάθε κλειδιού. Κοστίζει χρόνο και μνήμη O(n) και απαιτεί ανανέωση αν αλλάξει η συλλογή. Κράτησε μετρήσεις, περιπτώσεις duplicates και αποτελέσματα πραγματικής εκτέλεσης των assertions πριν θεωρήσεις την εργασία ολοκληρωμένη.

Δυαδική αναζήτηση

Reference implementation (Python 3)

def binary_search(items, target):
    lo, hi = 0, len(items)
    while lo < hi:
        mid = (lo + hi) // 2
        if items[mid] < target: lo = mid + 1
        else: hi = mid
    return lo if lo < len(items) and items[lo] == target else -1
assert binary_search([1, 3, 5, 7], 5) == 2

Απαραίτητη συνθήκη

Η υλοποίηση εξετάζει διάστημα [lo, hi), όπου το hi δεν περιλαμβάνεται. Διατηρεί τη θέση της πρώτης τιμής που δεν είναι μικρότερη από τον στόχο. Αν items[mid] < target, η λύση είναι μετά το mid και μετακινούμε το lo. Αλλιώς το hi πηγαίνει στο mid. Όταν lo=hi γίνεται τελικός έλεγχος ισότητας.

Ορθότητα και πολυπλοκότητα

Κάθε βήμα μειώνει περίπου στο μισό το εύρος, άρα O(log n) συγκρίσεις και O(1) επιπλέον μνήμη. Προϋπόθεση είναι αύξουσα ταξινόμηση και σταθερός τρόπος σύγκρισης. Στα duplicates επιστρέφεται ο αριστερότερος δείκτης, επειδή στην ισότητα μετακινείται το hi.

Συγκεκριμένες δοκιμές

[1,3,5,7] με στόχο 5 δίνει 2. Κατάγραψε lo, hi, mid σε κάθε βήμα.
[2,2,2] με στόχο 2 δίνει 0 και όχι τυχαία μεσαία θέση.
Κενή λίστα ή στόχος μεγαλύτερος όλων δίνει -1.
Για στόχο μικρότερο του πρώτου στοιχείου, το insertion position είναι 0 αλλά το search αποτέλεσμα -1.
Παράδωσε σκόπιμα [3,1,2]. Έχει παραβιαστεί η προϋπόθεση ταξινόμησης· όποιο αποτέλεσμα προκύψει δεν αποτελεί απόδειξη ορθότητας.

Επέκταση

Αν χρειάζεται θέση εισαγωγής, σχεδίασε ξεχωριστή λειτουργία lower_bound. Δοκίμασε ζυγό/μονό πλήθος στοιχείων και μέτρησε συγκρίσεις σε σχέση με linear search. Ειδικές τιμές όπως NaN απαιτούν ξεκάθαρο κανόνα διάταξης.

Μετρητής συχνοτήτων

Reference implementation (Python 3)

from collections import Counter
counts = Counter('banana')
assert counts['a'] == 3
print(counts)

Ερώτημα

Για κάθε ξεχωριστή τιμή θέλουμε το πλήθος εμφανίσεων. Το αρχείο αναφοράς χρησιμοποιεί collections.Counter στη συμβολοσειρά banana: το a εμφανίζεται 3 φορές, το n δύο και το b μία. Συνήθως ο χρόνος είναι O(n) με hash map, ενώ η πρόσθετη μνήμη O(k) για k διαφορετικά κλειδιά.

Ερμηνεία

Η Python διασχίζει code points των strings και όχι υποχρεωτικά ορατά grapheme clusters. Άλλη ερώτηση είναι η συχνότητα UTF-8 bytes, άλλη λέξεων και άλλη lowercase κειμένου. Πρέπει πρώτα να ορίσεις τι μετράς. Για ανύπαρκτο κλειδί η Counter επιστρέφει μηδέν χωρίς να καταχωρήσει κλειδί, σε αντίθεση με απλή προσπέλαση ενός dict.

Δοκιμές

Επιβεβαίωσε counts['a']==3 και counts['z']==0. Τα διαφορετικά κλειδιά είναι τρία.
Σύγκρινε Counter('Aa') με Counter('Aa'.casefold()). Η δεύτερη συγχωνεύει την περίπτωση ASCII.
Μέτρησε 10000 επαναλήψεις του a. Εξήγησε γιατί το πλήθος διαφορετικών κλειδιών καθορίζει το μέγεθος του χάρτη.
Εφάρμοσε τον αλγόριθμο σε log statuses ['ok','fail','ok'] και έλεγξε άγνωστες τιμές.
Υλοποίησε ισοδύναμη λύση με dict.get(key,0)+1 και σύγκρινε αποτελέσματα πριν μιλήσεις για επιδόσεις.

Απόδειξη

Για μεγάλα logs προτίμησε streaming και κατέγραψε αν κρατάς όλη την είσοδο στη μνήμη. Σε μη έμπιστα inputs περιόρισε το μέγεθος και πλήθος διαφορετικών κλειδιών. Κράτησε αρχικές τιμές αν η normalization πρέπει να είναι ελέγξιμη.

01 linear search — έλεγχος ορίων

Όταν υπάρχουν διπλότυπα, επιστρέφεται η πρώτη θέση. Το -1 σημαίνει απουσία ενώ η θέση 0 είναι έγκυρη· μην ελέγχεις το αποτέλεσμα με if index:. Η ισότητα εξαρτάται από τον τύπο δεδομένων.

Δοκίμασε [9,9] με στόχο 9 (απάντηση 0), κενή λίστα (-1) και τιμή που λείπει. Δεν απαιτείται ταξινόμηση.

02 binary search — έλεγχος ορίων

Απαιτείται αύξουσα ταξινόμηση. Το διάστημα είναι ημιανοικτό [lo,hi) και κρατά όλες τις υποψήφιες θέσεις. Όταν τελειώσει, το lo είναι θέση εισαγωγής και μπορεί να ισούται με len(items).

Δοκίμασε [1,2,2,2,4] με στόχο 2: πρώτη θέση 1. Για στόχο 3 επέστρεψε -1, όχι τη θέση εισαγωγής.

03 frequency map — έλεγχος ορίων

Ο πίνακας συχνοτήτων μετρά εμφανίσεις χωρίς επαναλαμβανόμενη σάρωση. Τα κλειδιά πρέπει να είναι hashable. Σε κείμενο αποφάσισε πρώτα αν κεφαλαία, τόνοι και κενά θεωρούνται ίδιες τιμές.

Φτιάξε Counter('aabbc'): a=2, b=2, c=1. Η Counter επιστρέφει μηδέν για άγνωστο κλειδί. Η μνήμη αυξάνεται με τις διαφορετικές τιμές.