Ας αρχίσουμε σήμερα γράφοντας μια συνάρτηση anapoda η οποία παίρνει ένα όρισμα τύπου string και επιστρέφει την ίδια λέξη γραμμένη ανάποδα. Βλέπουμε εδώ ότι μπορούμε να διανύσουμε τα γράμματα ενός string ακριβώς όπως διανύουμε τα στοιχεία μιας λίστας.
Ξεκινάμε ορίζοντας μια μεταβλητή ret μέσα στη συνάρτηση που να είναι αρχικά ίση με την κενή λέξη ("" ή ''). Στη συνέχεια διανύουμε τη λέξη από τα αριστερά προς τα δεξιά και για κάθε γράμμα x της λέξης που παίρνουμε το προσθέτουμε στη μεταβλητή ret από μπροστά με την εντολή ret = x + ret. Έτσι στο τέλος της ανακύκλωσης το ret έχει μέσα τα περιεχόμενα του ορίσματος s αλλά γραμμένα ανάποδα.
def anapoda(s):
"Γυρνάει το string s γραμμένο ανάποδα"
ret=""
for x in s:
ret = x + ret
return ret
print anapoda("o58763")
Εδώ προσθέσαμε στο προηγούμενο πρόγραμμα μια εντολή στο τέλος, print ret, δοκιμάζοντας να τυπώσουμε τη μεταβλητή ret που χρησιμοποιείται στη συνάρτηση anapoda. Παρατηρούμε ότι το πρόγραμμα βγάζει σφάλμα, NameError: name 'ret' is not defined.
Αυτό το σφάλμα σημαίνει ότι πάμε να χρησιμοποιήσουμε τη μεταβλητή ret (να την τυπώσουμε) χωρίς να έχει αυτή η μεταβλητή οριστεί, να έχει δηλ. ήδη πάρει τιμή κάπου.
Αυτό φαίνεται περίεργο μια και όταν εκτελείται η εντολή print ret η συνάρτηση anapoda έχει ήδη εκτελεστεί και η μεταβλητή ret έχει ήδη πάρει τιμή.
Η εξήγηση γι' αυτό είναι η εξής.
Στην python το κάθε όνομα (μεταβλητής, συνάρτησης, κλπ) χρησιμεύει ως αναφορά προς ένα αντικείμενο που είναι αποθηκευμένο στη μνήμη. Έτσι λοιπόν υπάρχει μια αντιστοιχία ονόματος, αντικειμένου (namespace, symbol table) όσο εκτελείται το πρόγραμμά μας και η αντιστοιχία αυτή χρησιμοποιείται από τον python interpreter για να βρει το αντικείμενο στη μνήμη στο οποίο αναφέρεται ένα όνομα και είτε να διαβάσει την τιμή του είτε να την αλλάξει.
Όμως υπάρχουν παραπάνω από μια τέτοιες αντιστοιχίσεις.
Στο πρόγραμμα που έχουμε εδώ υπάρχει η αντιστοίχιση που χρησιμοποιεί το κυρίως πρόγραμμα (καθολική ή global) αλλά όταν εκτελείται η συνάρτηση anapoda έχει και αυτή τη δικιά της αντιστοίχιση ονομάτων, αντικειμένων (τοπική ή local). Ένα όνομα εισάγεται σε μια αντιστοίχιση την πρώτη φορά που του δίνουμε τιμή. Επίσης όταν η python δει ένα όνομα του οποίου η τιμή ζητείται τότε πάει και το ψάχνει πρώτα στην τοπική αντιστοίχιση (αν υπάρχει) και μετά στην καθολική αντιστοίχιση.
Ας δούμε λοιπόν λεπτομερώς το γιατί εμφανίζεται το σφάλμα αυτό.
Όταν αρχίζει να εκτελείται το κυρίως πρόγραμμα το πρώτο πράγμα που κάνει είναι να καλέσει τη συνάρτηση anapoda("o58763"). Μέχρι στιγμής το μόνο όνομα που έχει μπει στην καθολική αντιστοίχιση είναι το όνομα anapoda, το οποίο η python έχει καταγράψει στην καθολική αντιστοίχιση ως όνομα που αναφέρεται σε μια συνάρτηση. Μόλις μεταφερθεί ο έλεγχος στη συνάρτηση anapoda ανοίγει η νέα τοπική ανιστοίχιση της συνάρτησης αυτής, αρχικά κενή, και μπαίνει μέσα πρώτα το όνομα s το οποίο είναι το όνομα της παραμέτρου. Όταν αρχίσει η κλήση της anapoda στην πρώτη εντολή παίρνει τιμή η μεταβλητή ret. Τότε η python εισάγει την ret στην τρέχουσα αντιστοίχιση, η οποία είναι η αντιστοίχιση της συνάρτησης anapoda και όχι η καθολική αντιστοίχιση. Μόλις αρχίσει να εκτελείται η ανακύκλωση τότε εισάγεται και το όνομα x στην αντιστοίχιση και δεν εισάγονται άλλα. Λίγο πριν τελειώσει δηλ. η κλήση της συνάρτησης anapoda και επιστρέψει ο έλεγχος στο κυρίως πρόγραμμα η τοπική αντιστοίχιση ονομάτων,αντικειμένων της συνάρτησης anapoda περιλαμβάνει τα ονόματα s, x και ret, ενώ η καθολική αντιστοίχιση περιλαμβάνει μόνο το όνομα anapoda.
Αφού επιστρέψει ο έλεγχος στο κυρίως πρόγραμμα (λίγο πριν τυπωθεί το αποτέλεσμα που επιστρέφει η συνάρτηση) η τοπική αντιστοίχιση της συνάρτησης anapoda διαγράφεται από τη μνήμη. Τώρα πλέον υπάρχει μόνο η καθολική αντιστοίχιση και αυτή δεν περιέχει μέσα καμία αναφορά στο όνομα ret. Έτσι, όταν στην επόμενη εντολή αναζητείται η τιμή της ret ώστε να εκτυπωθεί, τότε αυτή δε μπορεί να βρεθεί στην υπάρχουσα αντιστοίχιση και έτσι προκύπτει το σφάλμα.
def anapoda(s):
"Γυρνάει το string s γραμμένο ανάποδα"
ret=""
for x in s:
ret = x + ret
return ret
print anapoda("o58763")
print ret
Στο επόμενο βλέπουμε μια παραλλαγή του παραπάνω προγράμματος.
Εδώ ορίζουμε πρώτα την μεταβλητή name την οποία χρησιμοποιούμε μέσα στη συνάρτηση anapoda για να τυπώσουμε ένα μήνυμα.
Μετά την εντολή name="Mihalis" (κυρίως πρόγραμμα) ο καθολικός πίνακας αντιστοίχισης ονομάτων, αντικειμένων περιέχει μόνο το όνομα name. Επίσης μπαίνει και το όνομα anapoda και δείχνει προς τον ορισμό της συνάρτησης. Η εκτέλεση του κυρίως προγράμματος συνεχίζει με την εντολή print anapoda("sdfsdf") η οποία καλεί τη συνάρτηση anapoda. Μόλις αρχίσει η εκτέλεση της συνάρτησης αυτής δημιουργείται η τοπική αντιστοίχιση ονομάτων, αντικειμένων. Σε αυτή την αντιστοίχιση μπαίνει το όνομα s, της παραμέτρου της συνάρτησης και επίσης τα ονόματα x και ret, μεταβλητές στις οποίες η συνάρτηση δίνει τιμές (αυτό πάντα συνεπάγεται ότι μια τέτοια μεταβλητή μπαίνει στην τοπικκή αντιστοίχιση). Η πρώτη εντολή της συνάρτησης που εκτελείται είναι η print "Hello",name. Εκεί η python συναντάει το όνομα name, του οποίου την τιμή θα πρέπει να αναζητήσει. Η αρχή γίνεται από την τοπική αντιστοίχιση όπου όμως το όνομα name δεν υπάρχει και έτσι συνεχίζει η python να ψάχνει το όνομα στην αμέσως ανώτερη αντιστοίχιση, την καθολική, όπου και βρίσκει το όνομα και την τιμή του (Mihalis). Η τιμή αυτή τυπώνεται και η εκτέλεση της συνάρτησης συνεχίζει όπως και στο προηγούμενο παράδειγμα.
Έπειτα εκτελείται η εντολή name="Manolis" στο κυρίως πρόγραμμα και η συνάρτηση ξανακαλείται με τα αποτελέσματα που βλέπετε.
name="Mihalis"
def anapoda(s):
"Γυρνάει το string s γραμμένο ανάποδα"
print "Hello",name
ret=""
for x in s:
ret = x + ret
return ret
print anapoda("sdfsdf")
name="Manolis"
print anapoda("sdfsdf")
Προσέξτε τι γίνεται αν η εντολή name = "Manolis" μεταφερθεί μέσα στη συνάρτηση anapoda από το κυρίως πρόγραμμα όπου βρισκόταν. Αφελώς περιμένουμε ότι με αυτή την αλλαγή αυτό που θα συμβεί είναι ότι στην πρώτη κλήση της anapoda η τιμή της μεταβλητής name θα είναι "Mihalis" και στη δεύτερη "Manolis", αφού η τιμή της name θα έχει αλλάξει στην πρώτη κλήση της anapoda.
Όμως αυτό δε συμβαίνει και το πρόγραμμα βγάζει σφάλμα. Παρατηρείστε το μήνυμα παρακάτω:
UnboundLocalError: local variable 'name' referenced before assignment
Για τη μεταβλητή name, μας λέει το μήνυμα, αναζητούμε πρώτα την τιμή της (referenced) πριν της δώσουμε τιμή. Επίσης η python θεωρεί ότι η μεταβλητή name είναι τοπική.
Γιατι γίνεται αυτό; Γιατί δεν καταλαβαίνει η python ότι αναφερόμαστε στην καθολική μεταβλητή name που ορίστηκε ήδη στην πρώτη γραμμή του προγράμματος; Η απάντηση είναι ότι είναι ο κανόνας στην python όποτε πάμε να δώσουμε τιμή σε μια μεταβλητή μέσα σε μια συνάρτηση τότε αυτή η τιμή δίνεται στη μεταβλητή όπως αυτή φαίνεται στην τοπική αντιστοίχιση και αν η μεταβλητή αυτή δεν υπάρχει στην τοπική αντιστοίχιση τότε δημιουργείται μια νέα αναφορά σε αυτό το όνομα στην τοπική αντιστοίχιση. Η τοπική αντιστοίχιση της συνάρτησης anapoda δημιουργείται με την κλήση της συνάρτησης και η συνάρτηση διαβάζεται από την python πριν εκτελεστεί. Δημιουργείται δηλ. η πλήρης αντιστοίχιση της συνάρτησης anapoda πριν η συνάρτηση εκτελεστεί. Αφού υπάρχει ανάθεση στη μεταβλητή name μέσα στη συνάρτηση ο κανόνας της python μας κάνει να τη θεωρούμε τοπική μεταβλητή. Άρα η αναφορά στη name στην εντολή print "Hello",name θεωρείται αναφορά στην τοπική μεταβλητή name, η οποία όμως δεν έχει ακόμη πάρει τιμή, εξ ου και το σφάλμα.
name="Mihalis"
def anapoda(s):
"Γυρνάει το string s γραμμένο ανάποδα"
print "Hello",name
name = "Manolis"
ret=""
for x in s:
ret = x + ret
return ret
print anapoda("sdfsdf")
print anapoda("sdfsdf")
Στο επόμενο βλέπουμε πώς διορθώνεται το πρόβλημα που παρατηρήσαμε στο προηγούμενο κελλί.
Υπάρχει τρόπος μέσα σε μια συνάρτηση να δηλώσουμε ρητά ότι μια μεταβλητή δεν είναι τοπική αλλά καθολική, ώστε αυτή να αναζητηθεί στην καθολική αντιστοίχιση. Η εντολή αυτή είναι η global name μέσα στη συνάρτηση anapoda. Τώρα το πρόγραμμα τρέχει κανονικά.
name="Mihalis"
def anapoda(s):
"Γυρνάει το string s γραμμένο ανάποδα"
global name
print "Hello",name
name = "Manolis"
ret=""
for x in s:
ret = x + ret
return ret
print anapoda("sdfsdf")
print anapoda("sdfsdf")
Εδώ βλέπουμε πώς μπορούμε να εντάξουμε σε μια συνάρτηση ένα μηχανισμό με τον οποίο μετράμε το πόσες φορές καλέστηκε η συνάρτηση, από οπουδήποτε. Χρησιμοποιούμε μια καθολική μεταβλητή numcalls, την οποία δηλώνουμε ως global μέσα στη συνάρτηση και την οποία αυξάνουμε κατά ένα κάθε φορά που εκτελείται η συνάρτηση αυτή.
numcalls = 0
def anapoda(s):
"Γυρνάει το string s γραμμένο ανάποδα"
global numcalls
numcalls += 1
ret=""
for x in s:
ret = x + ret
return ret
print anapoda("o58763")
print anapoda("43856945")
print "Function was called",numcalls,"times"
Εδώ βλέπουμε το πώς η τροποποίηση της μεταβλητής x μέσα στη συνάρτηση f αφήνει αμετάβλητη την καθολική μεταβλητή x. Εφόσον μέσα στη συνάρτηση ανατίθεται τιμή στην x, και αυτή δεν έχει δηλωθεί global, η x θεωρείται τοπική μεταβλητή και η ανάθεση x=2 μέσα στην f δεν επηρεάζει την τιμή της καθολικής μεταβλητής x που είναι αυτή που τυπώνεται με την εντολή print x.
def f(x):
x=2
return x
x=5
f(x)
print x
Όπως και στο προηγούμενο παράδειγμα βλέπουμε πώς η συνάρτηση g δεν επηρεάζει την καθολική μεταβλητή x.
def g(x):
x += 1
return
x=2
g(x)
print x
Στο επόμενο κελλί βλέπουμε ένα πρόγραμμα του οποίου σκοπός είναι η προσεγγιστική εύρεση μιας ρίζας της εξίσωσης cos(x) = sin^2(x). Αν γράψουμε f(x) = cos(x) - sin^2(x) τότε ψάχνουμε για ένα x στο διάστημα [0,π/2] έτσι ώστε f(x)=0. Η συνάρτηση f(x) είναι συνεχής και f(0) = 1, f(π/2) = -1, άρα σίγουρα υπάρχει μια ρίζα στο διάστημα [0, π/2] από το Θεώρημα Ενδιάμεσης Τιμής.
Σημαντικό είναι να τονίσουμε ότι δεν ψάχνουμε για ακριβή αλλά για προσεγγιστική λύση. Σε μη γραμμικές εξισώσεις αυτό είναι η συνηθισμένη κατάσταση. Ακόμη και για πολύ απλές εξισώσεις, όπως η x^2-2=0, η ρίζα δεν είναι καθόλου απαραίτητο ότι μπορεί να παρασταθεί ακριβώς στον υπολογιστή ως αριθμός κινητής υποδιαστολής (floating point number, αυτή είναι η συνηθισμένη παράσταση πραγματικών αριθμών στον υπολογιστή).
Το να βρούμε λοιπόν τη ρίζα της εξίσωσης f(x) = 0 σημαίνει ότι θα βρούμε ένα αριθμό x ο οποίος είναι εγγυημένα κοντά σε μια πραγματική ρίζα. Πόσο κοντά είναι σε μας να το προσδιορίσουμε και στο πρόγραμμα παρακάτω έχουμε θέσει ως σκοπό να μην είμαστε μακρύτερα από 1e-9 (10 στη δύναμη -9).
Το πρόγραμμα δουλεύει ως εξής. Ξεκινάμε από ένα διάστημα [a,b] = [0,π/2] το οποίο σίγουρα περιέχει μια ρίζα της f(x). Επανειλημμένως χωρίζουμε το διάστημα [a,b] σε δύο ίσα διαστήματα, το αριστερό και το δεξί μισό. Εφόσον τα πρόσημα της f(x) είναι διαφορετικά στα δύο άκρα του [a,b] είμαστε σίγουροι ότι ένα από τα δύο αυτά μισά διαστήματα έχει επίσης ετερόσημες τιμές της f(x) στα δύο άκρα του και άρα περιέχει ρίζα της f(x). Το κάνουμε αυτό συνεχώς έως ότου το μήκος του διαστήματος γίνει μικρότερο από 1e-9. Έχουμε σε αυτό το σημείο βρει ένα διάστημα που περιέχει μια ρίζα της f(x) και άρα οποιοδήποτε σημείο του διαστήματος αυτού, π.χ. το αριστερό του άκρο, αποτελεί ικανοποιητική προσέγγιση μιας ρίζας της f(x).
Στην πρώτη γραμμή του προγράμματος κάνουμεimport τη βιβλιοθήκη math την οποία χρειαζόμαστε για τις συναρτήσεις cos και sin. Η πρώτη συνάρτηση που ορίζουμε είναι ακριβώς η f(x) της οποίας μια ρίζα ψάχνουμε.
Η συνάρτηση newinterval που ορίζεται μετά παίρνει δύο ορίσματα, τους αριθμούς A, B που πρέπει πάντα να είναι το αριστερό και το δεξί άκρο ενός διαστήματος στα άκρα του οποίου η f(x) παίρνει ετερόσημες τιμές. Η συνάρτηση αυτή επιστρέφει τα δύο άκρα ενός νέου διαστήματος με τις ίδιες ιδιότητες αλλά με το μισό μήκος. Το διάστημα αυτό είναι είτε το αριστερό μισό είτε το δεξί μισό του διαστήματος [A,B]. Στη συνάρτηση newinterval πρώτα το μέσο του διαστήματος με την εντολή middle = (A+B)/2.0 και έπειτα υπολογίζουμε τις τιμές της f(x) στο αριστερό άκρο (leftvalue) και στο μέσο (midvalue). Αν οι δύο αυτές τιμές είναι ετερόσημες (αυτό ελέγχεται στοif ελέγχοντας αν το γινόμενό τους είναι <=0) τότε επιστρέφουμε το αριστερό διάστημα με την πρώτη εντολή return, αλλιώς επιστρέφουμε το δεξί μισό διάστημα (σίγουρα σε ένα από τα δύο μισά διαστήματα θα έχουμε ετερόσημες τιμές στα άκρα). Προσέξτε ότι η συνάρτηση επιστρέφει δύο τιμές, το αριστερό και το δεξί άκρο του νέου διαστήματος.
Στο κυρίως πρόγραμμα θέτουμε κατ' αρχήν το αρχικό μας διάστημα να είναι το [0, π/2] με τις δύο πρώτες εντολές. Αυτό που κάνουμε στην ανακύκλωση while είναι ότι όσο το διάστημα στο οποίο έχουμε εγκλωβίσει τη ρίζα έχει μήκος b-a μεγαλύτερο από το 1e-9 καλούμε τη συνάρτηση newinterval και βρίσκουμε το νέο μας διάστημα (με μισό μήκος κάθε φορά) το οποίο επίσης αποθηκεύουμε στις ίδιες μεταβλητές a, b. Όταν η ανακύκλωση σταματήσει τυπώνουμε τα δύο άκρα του διαστήματος που βρήκαμε.
Τυπώνουμε επίσης τη μεταβλητή numfcalls η οποία μετράει το πόσες φορές καλέσαμε τη συνάρτηση f(x) σε όλον αυτό τον υπολογισμό. Η μεταβλητή numfcalls δηλώνεται ως global μέσα στην f(x) όπου και αυξάνεται κατά 1 κάθε φορά που η συνάρτηση καλείται. Η συνάρτηση καλέστηκε 62 φορές.
import math
numfcalls = 0
def f(x):
"Υπολογίζει τη συνάρτηση f(x) της οποίας μια ρίζα ψάχνουμε"
global numfcalls
numfcalls += 1
return math.cos(x)-math.sin(x)**2
def newinterval(A, B):
"Επιστρέφει νέο διάστημα. Απαιτείται στα A, B να έχει διαφορετικά πρόσημα η f"
middle = (A+B)/2.0
leftvalue = f(A)
midvalue = f(middle)
if leftvalue*midvalue <= 0:
return A, middle
return middle, B
a=0
b=math.pi/2
while b-a > 1e-9:
a,b = newinterval(a,b)
print "a=",a,"b=",b
print "f was called", numfcalls, "times"
Τώρα αλλάζουμε λιγάκι το προηγούμενο πρόγραμμα με σκοπό να ελαττώσουμε όσο γίνεται τον αριθμό των κλήσεων στη συνάρτηση f(x). Ο λόγος είναι ότι σε πολλές περιπτώσεις η συνάρτηση αυτή μπορεί να είναι εξαιρετικά "ακριβή" στον υπολογισμό της, μας κοστίζει δηλ. πολύ χρόνο για να την υπολογίσουμε, οπότε θέλουμε να μην το κάνουμε αν δεν είναι απαραίτητο.
Η βασική παρατήρηση που κάνουμε στο προηγούμενο πρόγραμμα είναι ότι στη συνάρτηση newinterval πολλές φορές υπολογίζουμε την f(x) σε σημεία που την έχουμε ήδη υπολογίσει σε προηγούμενα βήματα. Συγκεκριμένα ο υπολογισμός leftvalue = f(A) που κάνουμε για να υπολογίσουμε τη συνάρτηση στο αριστερό άκρο του διαστήματος είναι σίγουρα ένας υπολογισμός που μπορεί με κάποιο τρόπο να αποφευχθεί μια και η τιμή αυτή έχει ήδη υπολογιστεί σε προηγούμενο βήμα.
Η λύση που δίνουμε είναι ότι αλλάζουμε τον ορισμό της συνάρτησης newinterval και τώρα παίρνει ως ορίσματα όχι μόνο τα άκρα του διαστήματος αλλά και τις τιμές της f(x) στα δύο αυτά άκρα. Η συνάρτηση τώρα επίσης επιστρέφει τις νέες τιμές με τον ίδιο τρόπο, δηλ. τα δύο άκρα και τις δύο τιμές της f(x). Σε κάθε εκτέλεση της newinterval τώρα η συνάρτηση f(x) καλείται μόνο μια φορά ενώ πριν καλούνταν δύο.
Παρατηρείστε ότι το αποτέλεσμα είναι το ίδιο με πριν αλλά με πολύ λιγότερες (περίπου τις μισές) κλήσεις στην f(x).
import math
numfcalls = 0
def f(x):
global numfcalls
numfcalls += 1
return math.cos(x)-math.sin(x)**2
def newinterval(A, B, fA, fB):
"""
Απαιτείται στα A, B να έχει διαφορετικά πρόσημα η f.
fA πρέπει να ισούται με την τιμή της f στο A, και fB η τιμή στο B.
Επιστρέφει το αριστερό ή το δεξί μισό του διαστήματος και τις αντίστοιχες τιμές της
f στα δύο νέα άκρα. Στο διάστημα που επιστρέφει η f(x) έχει ετερόσημες τιμές στα άκρα.
"""
middle = (A+B)/2.0
leftvalue = fA
midvalue = f(middle)
rightvalue = fB
if leftvalue*midvalue <= 0:
return A, middle, fA, midvalue
return middle, B, midvalue, fB
a=0
b=math.pi/2
fa = f(a)
fb = f(b)
while b-a > 1e-9:
a,b,fa,fb = newinterval(a,b,fa,fb)
print "a=",a,"b=",b
print "f was called", numfcalls, "times"