Τμήμα Μαθηματικών

Πληροφορική Ι

Εβδομάδα 4 · Ο Βρόχος For και Λίστες

(Οδηγίες χρήσης του διαδραστικού κώδικα: δείτε την αρχική σελίδα.)

1 Ο Βρόχος For

1.1 Η εντολή `for`

Ο βρόχος for επαναλαμβάνεται για συγκεκριμένο αριθμό επαναλήψεων — είναι βρόχος ελεγχόμενος με μετρητή (count-controlled loop):

for μεταβλητή in [τιμή1, τιμή2, ...]:
    εντολές

Πολύ συχνά χρησιμοποιείται μαζί με τη συνάρτηση range, που δημιουργεί μια αλληλουχία τιμών:

range(x): τιμές από 0 έως x-1.
range(x, y): τιμές από x έως y-1.
range(x, y, z): τιμές από x έως το πολύ y-1 (ή y+1 αν z<0), με βήμα z.

Δύο ιδιότητες της for αξίζει να θυμόμαστε:

αν αλλάξουμε τη μεταβλητή-μετρητή μέσα στο σώμα του βρόχου, αυτό δεν επηρεάζει την επόμενη επανάληψη — θα πάρει ούτως ή άλλως την επόμενη τιμή από το range·
η μεταβλητή-μετρητής συνεχίζει να υπάρχει και μετά τον βρόχο, με την τελευταία τιμή που πήρε.

Ένθετα for (βρόχος μέσα σε βρόχο) χρησιμοποιούνται π.χ. για δισδιάστατα μοτίβα:

1.2 Οι εντολές `break` και `continue`

Μέσα σε έναν βρόχο, η break σταματάει αμέσως την επανάληψη (βγαίνει εντελώς από τον βρόχο), ενώ η continue παραλείπει την υπόλοιπη τρέχουσα επανάληψη και προχωράει κατευθείαν στην επόμενη τιμή. Η break είναι ιδιαίτερα χρήσιμη σε αλγορίθμους αναζήτησης: μόλις βρούμε αυτό που ψάχνουμε, δεν έχει νόημα να συνεχίσουμε να ελέγχουμε τα υπόλοιπα στοιχεία:

Η continue, αντίθετα, χρησιμοποιείται όταν θέλουμε να αγνοήσουμε συγκεκριμένες τιμές, χωρίς να σταματήσουμε ολόκληρο τον βρόχο:

2 Λίστες και Πλειάδες

2.1 Δημιουργία και προσπέλαση λιστών

Μια λίστα (list) είναι μια δυναμική δομή δεδομένων που περιέχει πολλαπλά στοιχεία υπό ένα κοινό όνομα. Σε αντίθεση με τους πίνακες πολλών άλλων γλωσσών, το μέγεθος μιας λίστας στην Python μπορεί να αυξομειώνεται κατά την εκτέλεση. Κάθε στοιχείο έχει έναν δείκτη (index), με αρίθμηση που ξεκινά από το 0:

Η προσπέλαση των στοιχείων μιας λίστας γίνεται είτε με for (όταν μας ενδιαφέρουν μόνο οι τιμές), είτε με δείκτες (όταν μας ενδιαφέρει και η θέση):

Οι αρνητικοί δείκτες μετρούν από το τέλος: values[-1] είναι το τελευταίο στοιχείο, values[-2] το προτελευταίο, κ.ο.κ. Η χρήση μη έγκυρου δείκτη προκαλεί σφάλμα IndexError.

2.2 Τεμαχισμός (slicing)

Ο τελεστής : επιτρέπει την απομόνωση τμημάτων μιας λίστας: λίστα[αρχή:τέλος:βήμα]. Αν παραλειφθεί η αρχή, θεωρείται 0· αν παραλειφθεί το τέλος, θεωρείται το τέλος της λίστας:

2.3 Χαρακτηριστικό της Python: λίστες με κατανόηση (list comprehensions)

Ένα πολύ συνηθισμένο μοτίβο είναι να φτιάχνουμε μια νέα λίστα εφαρμόζοντας κάποιον υπολογισμό σε κάθε στοιχείο μιας άλλης ακολουθίας. Η Python προσφέρει για αυτό μια συνοπτική, πολύ ιδιωματική (Pythonic) σύνταξη, τη λίστα με κατανόηση (list comprehension), που “συμπυκνώνει” έναν βρόχο for (και προαιρετικά μια συνθήκη if) μέσα σε μία έκφραση:

Μια στενά συγγενική έννοια είναι η γεννήτρια-έκφραση (generator expression): ίδια σύνταξη, αλλά με παρενθέσεις (...) αντί για αγκύλες [...].

Η διαφορά: μια γεννήτρια-έκφραση δεν κατασκευάζει ολόκληρη τη λίστα στη μνήμη — παράγει τις τιμές μία-μία, «τεμπέλικα» (lazily), μόνο όταν ζητηθούν. Είναι ιδανική όταν μας ενδιαφέρει μόνο ένα συγκεντρωτικό αποτέλεσμα (π.χ. ένα άθροισμα), όχι η ίδια η λίστα:

2.4 Μεταβλητότητα, μέθοδοι, και αντίγραφα

Οι λίστες είναι μεταβλητός (mutable) τύπος: μπορούμε να αλλάξουμε στοιχεία με λίστα[δείκτης] = νέα_τιμή.

Οι πιο χρήσιμες μέθοδοι:

Μέθοδος	Τι κάνει
`append(x)`	προσθέτει το `x` στο τέλος
`insert(θέση, x)`	εισάγει το `x` στη θέση
`remove(x)`	αφαιρεί την πρώτη εμφάνιση του `x`
`sort()` / `sort(reverse=True)`	ταξινομεί επί τόπου
`reverse()`	αντιστρέφει επί τόπου

Οι ενσωματωμένες συναρτήσεις min, max, sum, len δουλεύουν κατευθείαν πάνω σε λίστες:

Σημαντικό

Όταν εκχωρούμε μια λίστα σε άλλη μεταβλητή με list2 = list1, δεν δημιουργείται αντίγραφο — απλώς η ίδια λίστα αποκτά δύο ονόματα, και μια αλλαγή στη μία φαίνεται και στην άλλη! Για πραγματικό αντίγραφο, χρησιμοποιήστε list2 = list1[:] ή list2 = list(list1).

Το ίδιο ισχύει όταν μια λίστα δίνεται ως όρισμα σε συνάρτηση: αν η συνάρτηση τροποποιήσει στοιχεία της λίστας (π.χ. με append ή με εκχώρηση v[i] = ...), η αλλαγή είναι ορατή και έξω από τη συνάρτηση, γιατί το όνομα της λίστας είναι ουσιαστικά μια αναφορά στην ίδια θέση μνήμης.

2.5 Δισδιάστατες λίστες

Μια δισδιάστατη λίστα είναι μια λίστα της οποίας τα στοιχεία είναι κι αυτά λίστες — χρήσιμη για την αναπαράσταση πινάκων:

2.6 Πλειάδες (tuples)

Μια πλειάδα (tuple) μοιάζει με λίστα, αλλά είναι αμετάβλητη (immutable): δημιουργείται με παρενθέσεις αντί για αγκύλες, και τα στοιχεία της δεν μπορούν να αλλάξουν μετά τη δημιουργία της.

Τις χρησιμοποιούμε όταν θέλουμε μια σταθερή ομάδα τιμών που δεν πρέπει να αλλάξει κατά λάθος — συντεταγμένες ενός σημείου, ένα ζεύγος (ημερομηνία, θερμοκρασία), μια «εγγραφή» με τα στοιχεία ενός φοιτητή.

Δημιουργία: το κόμμα, όχι οι παρενθέσεις

Αυτό που κάνει μια πλειάδα δεν είναι οι παρενθέσεις αλλά το κόμμα. Οι παρενθέσεις είναι συχνά προαιρετικές — για πλειάδα ενός στοιχείου όμως το κόμμα είναι υποχρεωτικό:

Ξεπακετάρισμα (unpacking)

Μπορούμε να δώσουμε τα στοιχεία μιας πλειάδας (ή λίστας) σε πολλές μεταβλητές ταυτόχρονα. Το πλήθος πρέπει να ταιριάζει — εκτός αν βάλουμε * σε μία μεταβλητή για να «μαζέψει» όσα περισσεύουν:

Το ξεπακετάρισμα κάνει πολύ ευανάγνωστους τους βρόχους πάνω σε ζεύγη. Η enumerate δίνει (θέση, τιμή) πλειάδες, και η zip «ράβει» δύο ακολουθίες σε ζεύγη:

Σύγκριση και μετατροπές

Οι πλειάδες συγκρίνονται λεξικογραφικά, στοιχείο-στοιχείο (όπως οι συμβολοσειρές στην Εβδομάδα 3), και μετατρέπονται εύκολα από/προς λίστες:

2.7 f-strings και λίστες

Πολύ συχνά έχουμε μια λίστα (ή μια λίστα από πλειάδες) και θέλουμε να την τυπώσουμε καθαρά — όχι με το ακατέργαστο print(L), αλλά ως στοιχισμένες γραμμές ή ως μία γραμμή με διαχωριστικά. Οι f-strings (Εβδομάδα 2) μαζί με τον βρόχο for το κάνουν εύκολα.

Μία γραμμή με διαχωριστικά. Η μέθοδος str.join παίρνει μια ακολουθία από συμβολοσειρές και τις ενώνει· τους αριθμούς τούς μετατρέπουμε σε συμβολοσειρές πρώτα:

Πινακάκι με στοιχισμένες στήλες, από μια λίστα ζευγών (όνομα, βαθμός) — με ξεπακετάρισμα μέσα στον for:

Λίστες μέσα στα άγκιστρα. Μέσα σε { } μπαίνει οποιαδήποτε έκφραση — δείκτες, τεμαχισμός, len, κλήσεις μεθόδων:

2.8 Αλγόριθμοι σε λίστες: ταξινόμηση και αναζήτηση

Ο αλγόριθμος ταξινόμησης με επιλογή (selection sort) βρίσκει επαναληπτικά το ελάχιστο στοιχείο του “εναπομείναντος” τμήματος της λίστας και το τοποθετεί στη σωστή θέση:

Ο απλούστερος αλγόριθμος αναζήτησης είναι η γραμμική (ή σειριακή) αναζήτηση, που είδαμε στην Εβδομάδα 1 ως το πρώτο μας παράδειγμα αλγορίθμου: σαρώνουμε τη λίστα στοιχείο-στοιχείο και σταματάμε μόλις βρούμε αυτό που ψάχνουμε. Με return (ή break) μέσα στον for, η σάρωση κόβεται αμέσως — δεν χρειάζεται να φτάσουμε στο τέλος. Δουλεύει σε οποιαδήποτε λίστα, ταξινομημένη ή όχι:

Στη χειρότερη περίπτωση (το στοιχείο λείπει, ή βρίσκεται τελευταίο) η γραμμική αναζήτηση εξετάζει και τα \(n\) στοιχεία. Αν η λίστα είναι ήδη ταξινομημένη, μπορούμε να κάνουμε πολύ καλύτερα με τη δυαδική αναζήτηση (binary search), που κάθε φορά πετάει το μισό διάστημα αναζήτησης. Αυτή ταιριάζει φυσικά με τον βρόχο while — το πλήθος των επαναλήψεων δεν είναι γνωστό εκ των προτέρων — οπότε την ξαναβλέπουμε στην Εβδομάδα 5, όπως την είχαμε ήδη σκιαγραφήσει σε φυσική γλώσσα, διάγραμμα ροής και ψευδοκώδικα στην Εβδομάδα 1.

3 Πρώτοι Αριθμοί

3.1 Έλεγχος πρώτων αριθμών

Ένας αριθμός \(n\) είναι πρώτος αν έχει ακριβώς δύο διαιρέτες: το 1 και τον εαυτό του. Με έναν βρόχο for μπορούμε να ελέγξουμε αν κάποιος αριθμός από το 2 έως το \(n-1\) διαιρεί τον \(n\):

3.2 Το κόσκινο του Ερατοσθένη

Ο παραπάνω έλεγχος είναι σπάταλος όταν θέλουμε όλους τους πρώτους μέχρι ένα όριο \(N\), αφού ξαναρχίζει τον έλεγχο από την αρχή για κάθε αριθμό ξεχωριστά. Το κόσκινο του Ερατοσθένη (3ος αιώνας π.Χ.) είναι ένας από τους αρχαιότερους γνωστούς αλγορίθμους, και βρίσκει όλους τους πρώτους αριθμούς από το \(2\) έως το \(N\) ταυτόχρονα, πολύ πιο αποδοτικά:

Γράψε όλους τους αριθμούς από το \(2\) έως το \(N\).
Ο πρώτος αριθμός που δεν έχει διαγραφεί είναι πρώτος· κύκλωσέ τον.
Διάγραψε όλα τα (γνήσια) πολλαπλάσιά του.
Επανάλαβε το βήμα 2, μέχρι να εξεταστούν όλοι οι αριθμοί μέχρι το \(\sqrt{N}\).

Η ιδέα υλοποιείται φυσικά με μια λίστα από True/False τιμές — μια για κάθε αριθμό:

Γιατί εξετάζουμε πιθανούς πρώτους μόνο μέχρι το \(\sqrt{N}\); Αν ένας αριθμός \(n \le N\) δεν είναι πρώτος, έχει σίγουρα κάποιον διαιρέτη \(\le \sqrt{n} \le \sqrt{N}\) — αλλιώς, αν όλοι οι διαιρέτες του ήταν \(> \sqrt{n}\), το γινόμενο δύο οποιωνδήποτε θα ξεπερνούσε το \(n\).

Αυτή η παρατήρηση μειώνει δραστικά τους υπολογισμούς. Δοκιμάστε να αυξήσετε το \(N\) σε 100000: το κόσκινο τους βρίσκει σχεδόν ακαριαία, πολύ πιο γρήγορα από \(N\) κλήσεις της is_prime.

4 Σύνοψη

Σε αυτή την εβδομάδα είδαμε:

Τον βρόχο for, τη συνάρτηση range, ένθετους βρόχους, και τις εντολές break/continue.
Λίστες: δημιουργία, πρόσβαση, τεμαχισμός, μεταβλητότητα, και τη διαφορά ανάμεσα σε αντιγραφή αναφοράς και πραγματικό αντίγραφο.
Λίστες/γεννήτριες-εκφράσεις με κατανόηση, δισδιάστατες λίστες.
Πλειάδες: το κόμμα που τις ορίζει, packing/unpacking, ανταλλαγή τιμών, enumerate/zip, λεξικογραφική σύγκριση.
Δομημένη εκτύπωση λιστών με f-strings: str.join, στοιχισμένα «πινακάκια» από λίστες ζευγών.
Θεμελιώδεις αλγορίθμους σε λίστες: ταξινόμηση με επιλογή και γραμμική αναζήτηση (η δυαδική αναζήτηση έρχεται με τον while, στην Εβδομάδα 5).
Δύο αλγορίθμους αποδοτικής απαρίθμησης: έλεγχο πρώτων αριθμών με βρόχο, και το κόσκινο του Ερατοσθένη.

⤺ Πίσω στην αρχική σελίδα / πρόγραμμα μαθήματος · Διαφάνειες αυτής της εβδομάδας