Σημειωματάριο Τρίτης 20/10/2015: Λίστες. Ανακύκλωση for.

Λίστες και πώς κάνουμε διάφορες πράξεις σε αυτές

Στο επόμενο βλέπετε ένα παράδειγμα λίστας. Τα στοιχεία της δε χρειάζεται να είναι ομοιογενή όπως βλέπετε.

In [1]: 
l = [1, 2, 3, 'abc', 1.1]
print l

[1, 2, 3, 'abc', 1.1]

Κάποια στοιχεία μιας λίστας μπορούν να είναι ακόμη και άλλες λίστες. Το τελευταίο στοιχείο της λίστας l είναι η λίστα [0.1, 2.3].

In [2]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]
print l

[1, 2, 3, 'abc', 1.1, [0.1, 2.3]]

Το παρακάτω κάνει την ίδια δουλειά με το προηγούμενο, απλά χρησιμοποιεί μια ενδιάμεση μεταβλητή ll για να ορίσει τη λίστα [0.1, 2.3].

In [3]: 
ll = [0.1, 2.3]
l = [1, 2, 3, 'abc', 1.1, ll ]
print l

[1, 2, 3, 'abc', 1.1, [0.1, 2.3]]

Εδώ βλέπετε μια κενή λίστα, και βλέπετε επίσης ότι το μήκος της είναι 0. Κενές λίστες χρησιμοποιούνται συχνά ως αρχικές τιμές σε μια μεταβλητή τύπου λίστας που σιγά-σιγά μεγαλώνει προσθέτοντας στοιχεία σε αυτή.

In [5]: 
e = []
print e
print len(e)

[]
0

Εδώ βλέπουμε πώς χρησιμοποιούμε slices (φέτες) σε λίστες για να πάρουμε μια υπολίστα αυτών. Τα slices γράφονται ακριβώς όπως και στα strings.

In [7]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]
x = l[2:5]
print x

[3, 'abc', 1.1]
In [8]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]
x = l[2:5:2]
print x

[3, 1.1]
In [14]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]
x = l[:5:2]
print x
x = l[2::2]
print x
x = l[::-1]
print x

[1, 3, 1.1]
[3, 1.1]
[[0.1, 2.3], 1.1, 'abc', 3, 2, 1]

Βλέπουμε εδώ πώς μπορούμε να φτιάξουμε αντίγραφο μιας λίστας. Η εντολή y = x[:] αντιγράφει τη λίστα στην οποία δείχνει η μεταβλητή x σε μια νέα περιοχή στη μνήμη και βάζει τη μεταβλητή y να δείχνει σε αυτήν. Έτσι μια οποιαδήποτε αλλαγή στη λίστα x (όπως η αμέσως επόμενη εντολή x[0] = 10 που αλλάζει το πρώτο στοιχείο της λίστας x σε 10) δεν έχει καμιά επίπτωση στη λίστα y, όπως φαίνεται και από το τι τυπώνεται.

Αν στο παρακάτω πρόγραμμα αντικαταστήσετε την εντολή y = x[:] με την εντολή y = x (η οποία κάνει το όνομα y να δείχνει όπου και το όνομα x) το αποτέλεσμα θα είναι διαφορετικό (δοκιμάστε το). Η αλλαγή που κάνουμε στη λίστα x θα συμβεί και στη λίστα y, αφού και τα δύο ονόματα δείχνουν στις ίδιες θέσεις στη μνήμη.

In [2]: 
x = [1, 2, 3]

y = x[:]

x[0] = 10

print x
print y

[10, 2, 3]
[1, 2, 3]

Στο παρακάτω βλέπουμε τη χρήση αρνητικών δεικτών σε μια λίστα. Αν L είναι το μήκος (πλήθος στοιχείων) μιας λίστας τότε ο δείκτης -1 είναι το ίδιο με τον L-1, ο δείκτης -2 ίδιος με το δείκτη L-2 κλπ. Έτσι το τελευταίο στοιχείο της λίστας l μπορεί να γραφεί είτε ως l[L-1] είτε ως l[-1] (όπου L είναι το μήκος της l).

In [16]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]
print l[-1]

[0.1, 2.3]

Για να προσθέσουμε ένα στοιχείο στο τέλος μιας λίστας χρησιμοποιούμε τη μέθοδο append.

In [3]: 
lista = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]
lista.append("Mihalis")
print lista

[1, 2, 3, 'abc', 1.1, [0.1, 2.3], 'Mihalis']

Για να συγκολλήσουμε δύο λίστες μπορούμε να χρησιμοποιήσουμε τον τελεστή +.

In [23]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]

l = l+['a', 'b', 'c']
print l

[1, 2, 3, 'abc', 1.1, [0.1, 2.3], 'a', 'b', 'c']

Για να προσθέσουμε μια ολόκληρη λίστα στο τέλος μιας λίστας χρησιμοποιούμε τη μέθοδο extend.

In [20]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]
ll = ['a', 'b', 'c']
l.extend(ll)
print l

[1, 2, 3, 'abc', 1.1, [0.1, 2.3], 'a', 'b', 'c']

Για να εισαγάγουμε ένα στοιχείο σε μια θέση της λίστας χρησιμοποιούμε τη μέθοδο insert και ως πρώτο όρισμα στην insert δίνουμε το δείκτη που θέλουμε να έχει το στοιχείο που θέλουμε να εισαγάγουμε (δεύτερο όρισμα στην insert).

In [25]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]
l.insert(4, "Mihalis")
print l

[1, 2, 3, 'abc', 'Mihalis', 1.1, [0.1, 2.3]]

Αντί για insert στη θέση 0 μπορούμε να χρησιμοποιήσουμε τον τελεστή + όπως φαίνεται στο επόμενο.

In [26]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]
l = ['Mihalis'] + l
print l

['Mihalis', 1, 2, 3, 'abc', 1.1, [0.1, 2.3]]

Ο τελεστής in χρησιμοποιείται για να ελέγξουμε αν ένα στοιχείο είναι στοιχείο μιας λίστας ή όχι.

In [28]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]

print 4 in l

False

Αν γνωρίζουμε ότι ένα στοιχείο είναι σε μια λίστα τότε μπορούμε να μάθουμε την πρώτη θέση του στη λίστα (μπορεί να εμφανίζεται παραπάνω από μια φορά) με τη μέθοδο index. Αν το στοιχείο με το οποίο καλούμε την index δεν είναι στη λίστα τότε δημιουργείται σφάλμα, οπότε πρέπει πρώτα να χρησιμοποιούμε τον τελεστή in για να ελέγχουμε αν κάτι είναι μέσα στη λίστα πριν αναζητήσουμε τη θέση του.

In [29]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]

print l.index('abc')

3
In [30]: 
l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]

print l.index('abcd')

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-30-623680bffdfd> in <module>()
      1 l = [1, 2, 3, 'abc', 1.1, [0.1, 2.3] ]
      2 
----> 3 print l.index('abcd')

ValueError: 'abcd' is not in list

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

In [4]: 
L = input("Give me a list: ")
x = int(raw_input("Give an integer: "))

if x in L:
    n = L.index(x)
    print "The number %d is in the list. First location %d." % (x, n)
else:
    print "The number %d is not in the list." % (x)

Give me a list: [1, 2, 3, 3, 2, 1]
Give an integer: 3
The number 3 is in the list. First location 2.

Με τη μέθοδο remove διαγράφουμε από τη λίστα ένα στοιχείο της, δίνοντας το όνομα (όχι τη θέση) του στοιχείου. Διαγράφεται μόνο η πρώτη εμφάνιση του στοιχείου στη λίστα. Αν το στοιχείο δεν είναι στη λίστα δημιουργείται σφάλμα.

In [8]: 
l = [1, 2, 3, 'abc', 2, [0.1, 2.3] ]

l.remove('abc')

print l

[1, 2, 3, 2, [0.1, 2.3]]

Ενώ με την εντολή del διαγράφουμε ένα στοιχείο από τη λίστα δίνοντας τη θέση του.

In [39]: 
l = [1, 2, 3, 'abc', 2, [0.1, 2.3] ]

del l[4:6]

print l

[1, 2, 3, 'abc']

Με τη συνάρτηση range δημιουργούμε μια λίστα ακεραίων.

Με το range(N) δημιουργούμε τη λίστα [0, 1, ... , Ν-1].

Με το range(M, N) δημιουργούμε τη λίστα [Μ, Μ+1, ... , Ν-1].

Με το range(M, N, S) δημιουργούμε τη λίστα [M, M+S, M+2S, ...]. Η λίστα εκτείνεται όσο τα στοιχεία της είναι μικρότερα (αυστηρά) από N.

In [43]: 
print range(5)

print range(4, 8)

print range(4, 24, 3)

[0, 1, 2, 3, 4]
[4, 5, 6, 7]
[4, 7, 10, 13, 16, 19, 22]

Πολύ χρήσιμες συναρτήσεις για λίστες είναι και οι min, max και sum που υπολογίζουν το ελάχιστο στοιχείο, μέγιστο στοιχείο και άθροισμα στοιχείων μιας (αριθμητικής) λίστας.

In [45]: 
l = [1, 2, 3.1]
m = min(l)
M = max(l)
s = sum(l)
print m, M, s

1 3.1 6.1

Η ανακύκλωση for

Με την εντολή for x in L: διατρέχουμε με τη μεταβλητή x τα στοιχεία της λίστας L. Αυτό σημαίνει ότι οι εντολές που υπάγονται στο for (και είναι ακριβώς από κάτω και σπρωγμένες (indented) προς τα μέσα) θα εκτελεστούν μια φορά για κάθε στοιχείο της λίστας και σε κάθε τέτοια εκτέλεση η μεταβλητή x θα περιέχει ακριβώς το στοιχείο αυτό της λίστας.

Τη μεταβλητή της λίστας δεν την τροποποιούμε μέσα στην ανακύκλωση for παρά μόνο διαβάζουμε την τιμή της και τη χρησιμοποιούμε.

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

In [46]: 
L = ['Manolis', 'Mihalis', 'Yannis']

for x in L:
    print x

Manolis
Mihalis
Yannis

Στο επόμενο τυπώνουμε όλα τα τετράγωνα ακεραίων από 1 έως 10. Το κόμμα μετά το print σημαίνει ότι το print δε θα αλλάξει γραμμή.

In [48]: 
L = range(1,11)

for x in L:
    print x**2,

1 4 9 16 25 36 49 64 81 100

Το ίδιο κάνει και αυτό το πρόγραμμα μόνο που τυπώνει το \(x\) μαζί με το \(x^2\).

In [52]: 
for x in range(1, 11):
    print "The square of %d is %d." % (x, x**2)

The square of 1 is 1.
The square of 2 is 4.
The square of 3 is 9.
The square of 4 is 16.
The square of 5 is 25.
The square of 6 is 36.
The square of 7 is 49.
The square of 8 is 64.
The square of 9 is 81.
The square of 10 is 100.

Το πρόγραμμα που ακολουθεί είναι κατά πολύ το χρησιμότερο και δυσκολότερο που έχουμε γράψει μέχρι τώρα. Ζητάει από το χρήστη ένα φυσικό αριθμό \(n > 1\) και αποφασίζει αν ο αριθμός είναι πρώτος (δεν έχει γνήσιους διαιρέτες) ή όχι (γνήσιος διαιρέτης ενός αριθμού είναι κάθε διαιρέτης εκτός από τον εαυτό του και το 1).

Για να αποφασίσουμε αν ο \(n\) είναι πρώτος διατρέχουμε όλους τους ακεραίους από 2 έως \(n-1\) και ελέγχουμε αν κάποιος από αυτούς διαιρεί τον \(n\). Αν βρούμε έστω και έναν τότε ο αριθμός δεν είναι πρώτος (λέμε ότι είναι σύνθετος) αν δε βρούμε κανένα τότε είναι πρώτος.

Για το λόγο αυτό χρησιμοποιούμε μια λογική μεταβλητή isprime, κατ' αρχήν True, που αντικατοπτρίζει το τι πιστεύουμε για τον αριθμό \(n\) με βάση τα όσα έχουμε δει μέχρι κάποια χρονική στιγμή. Στην αρχή δεν έχουμε δει κάποιο λόγο να θεωρήσουμε το \(n\) σύνθετο οπότε αρχικά υποθέτουμε ότι είναι πρώτος. Αν κάποια στιγμή αργότερα βρούμε ένα διαιρέτη του \(n\) τότε η μεταβλητή αυτή γίνεται False και παραμένει False. Στο τέλος της ανακύκλωσης βρίσκεται στη μεταβλητή isprime η απάντηση στην ερώτηση αν το \(n\) είναι πρώτος ή όχι.

Στην ανακύκλωση

for k in range(2, n):
    if n % k == 0:
        isprime = False

διατρέχουμε όλους τους ακεραίους στη λίστα range(2,n), δηλ. στη λίστα [2, 3, 4, ... , n-1] και ελέγχουμε αν κάποιος από αυτούς τους αριθμούς διαιρεί το n. Αν αυτό συμβεί τότε η μεταβλητή isprime γίνεται False (αυτό μπορεί να συμβεί πολλές φορές, μια για κάθε διαιρέτη που βρίσκουμε).

Μετά την ανακύκλωση τυπώνουμε το ανάλογο μήνυμα.

Πρόβλημα για εσάς Εύκολα μπορεί κανείς να αποδείξει, με απαγωγή σε άτοπο, ότι ένας φυσικός αριθμός \(n\) που είναι σύνθετος έχει σίγουρα κάποιο γνήσιο διαιρέτη που είναι \(\le \sqrt{n}\). Αυτό σημαίνει ότι δε χρειάζεται να κάνουμε τόσους ελέγχους όσους κάνει το παραπάνω πρόγραμμα για να βεβαιωθούμε ότι ο \(n\) είναι πρώτος (το παραπάνω πρόγραμμα κάνει \(n-3\) ελέγχους). Γράψτε ένα παρόμοιο πρόγραμμα που εκμεταλλεύεται την ιδιότητα αυτή και άρα κάνει πολύ λιγότερους ελέγχους διαιρετότητας, μια διαφορά που μπορεί να έχει μεγάλες επιπτώσεις στο χρόνο τρεξίματος του προγράμματος αν το \(n\) είναι μεγάλο.

In [55]: 
n = int(raw_input("Give me a positive integer > 1: "))

isprime = True

for k in range(2, n):
    if n % k == 0:
        isprime = False

if isprime:
    print "The number %d is a prime." % (n)
else:
    print "The number %d is not a prime." % (n)

Give me a positive integer > 1: 31
The number 31 is a prime.

Το επόμενο πρόγραμμα είναι μια τροποποίηση του προηγούμενου που όχι μόνο μας λέει αν ο αριθμός \(n\) είναι πρώτος ή σύνθετος αλλά, στην περίπτωση που είναι σύνθετος, μας δίνει και τη λίστα των διαιρετών του \(n\).

Για το σκοπό χρησιμοποιούμε τη λίστα divisors, αρχικά κενή, στην οποία μέσα βάζουμε (με τη μέθοδο append) κάθε διαιρέτη που βρίσκουμε (με την εντολή divisors.append(k) που εκτελείται μόνο όταν εκτελεστεί το if που είναι μέσα στην ανακύκλωση.

Στο τέλος, στην περίπτωση που ο \(n\) είναι σύνθετος, τυπώνουμε όλους τους διαιρέτες του χρησιμοποιώντας και πάλι μια ανακύκλωση for για να διατρέξουμε τη λίστα divisors.

In [59]: 
n = int(raw_input("Give me a positive integer > 1: "))

isprime = True
divisors = []

for k in range(2, n):
    if n % k == 0:
        isprime = False
        divisors.append(k)

if isprime:
    print "The number %d is a prime." % (n)
else:
    print "The number %d is not a prime." % (n)
    print "The list of divisors is: ",
    for x in divisors:
        print x,

Give me a positive integer > 1: 15007
The number 15007 is not a prime.
The list of divisors is:  43 349