Συνεχίζουμε σήμερα από το σημείο που σταματήσαμε την προηγούμενη Πέμπτη. Έχουμε λύσει το πρόβλημα του βέλτιστου πολλαπλασιασμού πινάκων με μια αναδρομική συνάρτηση. Σήμερα βλέπουμε το πώς μπορούμε να μετατρέψουμε, με σχετικά απλά βήματα, αυτή την αναδρομική συνάρτηση σε μια μέθοδο δυναμικού προγραμματισμού. Η διαφορά είναι ότι τώρα θα αποθηκεύουμε τα ενδιάμεσα αποτελέσματα ώστε να αποφεύγουμε τον επανυπολογισμό τους.
Αρχίζουμε επαναλαμβάνοντας το πρόγραμμά μας από την προηγούμενη φορά. Οι αναφορές μέσα στα σχόλια είναι προς την προηγούμενη διάλεξη.
def findbest(dimension):
"""
Ποιος είναι ο βέλτιστος χρόνος πολλαπλασιασμού πινάκων με διαστάσεις
μ x ν0, ν0 x ν1, ν1 x ν2, ... , v(n-2) x v(ν-1), όπου η λίστα dimension περιέχει τα
μ, ν0, ν1, ν2, ..., ν(n-1)
"""
print "findbest({l})".format(l=dimension) # τυπώνουμε ενημερωτικό μήνυμα
n = len(dimension)-1 # πόσοι πίνακες είναι
# Στις παρακάτω δύο περιπτώσεις το μεσαίο στοιχείο της λίστας δεν έχει νόημα και περνάμε κάτι στην τύχη
if n==1: # μόνο ένας πίνακας
return [0, 0, "[{x}x{y}]".format(x=dimension[0],y=dimension[1])]
if n==2: # δύο πίνακες. μόνο ένας τρόπος υπάρχει
return [dimension[0]*dimension[1]*dimension[2], 1,
"([{x}x{y}] [{y}x{z}])".format(x=dimension[0],y=dimension[1],z=dimension[2])]
# Από εδώ και κάτω ψάχνουμε να βρούμε το βέλτιστο i
tm = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το δεξί μέλος της (R) παραπάνω
ll = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το αποτέλεσμα της 1ης κλήσης της findbest στην (R)
lr = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το αποτέλεσμα της 2ης κλήσης της findbest στην (R)
for i in range(n-1):
l1 = findbest(dimension[:i+2]) # 1η κλήση της findbest όπως περιγράφεται στην (R)
ll.append(l1)
l2 = findbest(dimension[i+1:]) # 2η κλήση της findbest όπως περιγράφεται στην (R)
lr.append(l2)
s1 = l1[0] # Πρώτος όρος T(..) στην (R)
s2 = l2[0] # Δεύτερος όρος T(..) στην (R)
s3 = dimension[0]*dimension[i+1]*dimension[n] # τρίτος προσθετέος στην (R)
tm.append(s1+s2+s3)
mm = min(tm) # Αυτό υπολογίζει το βέλτιστο χρόνο
ind = tm.index(mm) # και αυτό το για ποιο i συμβαίνει αυτός ο βέλτιστος χρόνος
return [mm, ind, "({sl} {sr})".format(sl=ll[ind][2], sr=lr[ind][2])] # επιστρέφει τις τιμές που χρειάζεται
print findbest([2,3,4,2,5])
Η πρώτη μετατροπή που κάνουμε, ως προετοιμασία γι' αυτό που θα ακολουθήσει, είναι ότι δεν περνάμε πλέον ολόκληρη τη λίστα ως όρισμα στη συνάρτησή μας. Αντίθετα αποθηκεύουμε τη λίστα σε μια global μεταβλητή dim και απλά περνάμε το δείκτη του πρώτου και του τελευταίου στοιχείου στη λίστα αυτή αντί να περνάμε την υπολίστα ολόκληρη.
Η μετατροπή είναι πολύ εύκολη και, αν γίνει με το σωστό τρόπο, ο κώδικάς μας αλλάζει σε ελάχιστα σημεία.
Εφόσον ο κώδικάς μας είναι ήδη γραμμένος περιμένοντας ότι οι διαστάσεις των πινάκων είναι στη λίστα dimension δημιουργούμε μια τοπική μεταβλητή με αυτόι το όνομα, τη γεμίζουμε από τη global λίστα dim με την εντολή
dimension = dim[first:last+1]και ο κώδικάς μας τρέχει κανονικά. Η μόνη άλλη αλλαγή που χρειάζεται είναι εκεί που καλείται αναδρομικά η findbest μια και τώρα έχει αλλάξει ο τρόπος κλήσης της. Τα αποτελέσματα είναι φυσικά τα ίδια με πριν όπως μπορείτε να δείτε.
def findbest(first, last):
"""
Ποιος είναι ο βέλτιστος χρόνος πολλαπλασιασμού πινάκων με διαστάσεις
μ x ν0, ν0 x ν1, ν1 x ν2, ... , v(n-2) x v(ν-1), όπου η λίστα dim[first:last+1] περιέχει τα
μ, ν0, ν1, ν2, ..., ν(n-1)
"""
global dim
dimension = dim[first:last+1]
#print "findbest({l})".format(l=dimension) # τυπώνουμε ενημερωτικό μήνυμα
n = len(dimension)-1 # πόσοι πίνακες είναι
# Στις παρακάτω δύο περιπτώσεις το μεσαίο στοιχείο της λίστας δεν έχει νόημα και περνάμε κάτι στην τύχη
if n==1: # μόνο ένας πίνακας
return [0, 0, "[{x}x{y}]".format(x=dimension[0],y=dimension[1])]
if n==2: # δύο πίνακες. μόνο ένας τρόπος υπάρχει
return [dimension[0]*dimension[1]*dimension[2], 1,
"([{x}x{y}] [{y}x{z}])".format(x=dimension[0],y=dimension[1],z=dimension[2])]
# Από εδώ και κάτω ψάχνουμε να βρούμε το βέλτιστο i
tm = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το δεξί μέλος της (R) παραπάνω
ll = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το αποτέλεσμα της 1ης κλήσης της findbest στην (R)
lr = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το αποτέλεσμα της 2ης κλήσης της findbest στην (R)
for i in range(n-1):
l1 = findbest(first, first+i+1) # 1η κλήση της findbest όπως περιγράφεται στην (R)
ll.append(l1)
l2 = findbest(first+i+1, last) # 2η κλήση της findbest όπως περιγράφεται στην (R)
lr.append(l2)
s1 = l1[0] # Πρώτος όρος T(..) στην (R)
s2 = l2[0] # Δεύτερος όρος T(..) στην (R)
s3 = dimension[0]*dimension[i+1]*dimension[n] # τρίτος προσθετέος στην (R)
tm.append(s1+s2+s3)
mm = min(tm) # Αυτό υπολογίζει το βέλτιστο χρόνο
ind = tm.index(mm) # και αυτό το για ποιο i συμβαίνει αυτός ο βέλτιστος χρόνος
return [mm, ind, "({sl} {sr})".format(sl=ll[ind][2], sr=lr[ind][2])] # επιστρέφει τις τιμές που χρειάζεται
dim = [2,3,4,2,5]
print findbest(0, len(dim)-1)
Η επόμενη (και τελευταία μετατροπή που κάνουμε) είναι ότι φροντίζουμε πλέον να αποθηκεύσουμε τα ενδιάμεσα αποτελέσματα. Αν δηλ. κληθεί η findbest για δεύτερη φορά με τα ίδια ορίσματα first και last τότε θα βρει το αποτέλεσμα αποθηκευμένο κάπου και δε χρειάζεται να το υπολογίσει ξανά. Αυτό κάνει τεράστια διαφορά στο χρόνο (δοκιμάστε να τρέξετε την επόμενη version και την προηγούμενη στην ίδια μεγάλη λίστα και η διαφορά θα είναι οφθαλμοφανής).
Τα ενδιάμεσα αποτελέσματα (ένα για κάθε ζεύγος first και last) τα κρατάμε σε ένα πίνακα του οποίου τα στοιχεία είναι λίστες τριών πραγμάτων (αφού τέτοια είναι τα αποτελέσματα μιας κλήσης της findbest). Ο πίνακας (για την ακρίβεια μια λίστα από λίστες στοιχείων) είναι ο findbest.res (προτιμούμε να τον έχουμε ως μια μεταβλητή που είναι attribute του ονόματος findbest αντί να τον δηλώσουμε ως global μεταβλητή όπως θα μπορούσαμε). Χρησιμοποιούμε επίσης το attribute findbest.firsttime για να ξέρουμε πότε είναι η πρώτη φορά που καλείται η συνάρτησή μας και να κάνουμε τότε και μόνο τότε την αρχικοποίηση του πίνακα findbest.res. Τη μεταβλητή findbest.res τη θέτουμε True από το κυρίως πρόγραμμα πριν από οποιαδήποτε κλήση στη findbest και μέσα στη findbest, την πρώτη φορά που καλείται τη θέτουμε ίση με False. Με αυτό τον τρόπο εξασφαλίζουμε ότι ένα κομμάτι κώδικα θα εκτελεστεί μόνο την πρώτη φορά που καλείται η findbest.
Πριν μπούμε στο μεγάλο loop ελέγχουμε αν έχουμε ήδη υπολογίσει το αποτέλεσμα και στην περίπτωση αυτή απλά το επιστρέφουμε.
Αν μπούμε τελικά στο μεγάλο loop τότε πριν επιστρέψουμε το αποτέλεσμα που βρήκαμε το αποθηκεύουμε στον πίνακα findbest.res.
def findbest(first, last):
"""
Ποιος είναι ο βέλτιστος χρόνος πολλαπλασιασμού πινάκων με διαστάσεις
μ x ν0, ν0 x ν1, ν1 x ν2, ... , v(n-2) x v(ν-1), όπου η λίστα dim[first:last+1] περιέχει τα
μ, ν0, ν1, ν2, ..., ν(n-1)
"""
global dim
if findbest.firsttime: # Αυτός ο κώδικας θα τρέξει μόνο την πρώτη φορά που θα κληθεί η findbest
findbest.firsttime = False
findbest.res = [ [ [] for j in range(last+1) ] for i in range(last+1) ] # δημιουργούμε ένα διδιάστατο πίνακα
# από κενές λίστες
dimension = dim[first:last+1]
n = len(dimension)-1 # πόσοι πίνακες είναι
# Στις παρακάτω δύο περιπτώσεις το μεσαίο στοιχείο της λίστας δεν έχει νόημα και περνάμε κάτι στην τύχη
if n==1: # μόνο ένας πίνακας
return [0, 0, "[{x}x{y}]".format(x=dimension[0],y=dimension[1])]
if n==2: # δύο πίνακες. μόνο ένας τρόπος υπάρχει
return [dimension[0]*dimension[1]*dimension[2], 1,
"([{x}x{y}] [{y}x{z}])".format(x=dimension[0],y=dimension[1],z=dimension[2])]
if len(findbest.res[first][last])>0: # αν αποτέλεσμα για τα first και last έχει ήδη υπολογιστεί απλά το επιστρέφουμε
return findbest.res[first][last] # και δεν κάνουμε τίποτα άλλο παρακάτω
# εδώ γίνεται η εξοικονόμηση του χρόνου
# Από εδώ και κάτω ψάχνουμε να βρούμε το βέλτιστο i
tm = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το δεξί μέλος της (R) παραπάνω
ll = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το αποτέλεσμα της 1ης κλήσης της findbest στην (R)
lr = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το αποτέλεσμα της 2ης κλήσης της findbest στην (R)
for i in range(n-1):
l1 = findbest(first, first+i+1) # 1η κλήση της findbest όπως περιγράφεται στην (R)
ll.append(l1)
l2 = findbest(first+i+1, last) # 2η κλήση της findbest όπως περιγράφεται στην (R)
lr.append(l2)
s1 = l1[0] # Πρώτος όρος T(..) στην (R)
s2 = l2[0] # Δεύτερος όρος T(..) στην (R)
s3 = dimension[0]*dimension[i+1]*dimension[n] # τρίτος προσθετέος στην (R)
tm.append(s1+s2+s3)
mm = min(tm) # Αυτό υπολογίζει το βέλτιστο χρόνο
ind = tm.index(mm) # και αυτό το για ποιο i συμβαίνει αυτός ο βέλτιστος χρόνος
findbest.res[first][last] = [mm, ind, "({sl} {sr})".format(sl=ll[ind][2], sr=lr[ind][2])]
# στην προηγούμενη γραμμή αποθηκεύουμε στον πίνακα `findbest.res` το αποτέλεσμα που μόλις βρήκαμε
# για να χρησιμοποιηθεί ξανά αργότερα όποτε το χρειαστούμε
# στην επόμενη γραμμή επιστρέφουμε αυτό.
return findbest.res[first][last] # επιστρέφει τις τιμές που χρειάζεται
dim = [2,3,4,2,5]
findbest.firsttime = True
print findbest(0, len(dim)-1)