Σάββατο 22 Απριλίου 2017

Αναθεώρηση 12 (Έκδοση 8.7) και δυναμικός προγραμματισμός

Έγιναν δυο διορθώσεις, μια σοβαρή (υπήρχε πρόβλημα στο συλλέκτη σκουπιδιών, και μπορούσε να κολήσει το πρόγραμμα και αντιμετωπίστηκε), και μια απλή βελτιστοποίση στην "απομνημόνευση" των ετικετών/αριθμών σε μπλοκ κώδικα (δεν άλλαξε η λειτουργία, απλά έγινε πιο απλός ο κώδικας, πιο γρήγορος).

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

Δοκιμάστε με διάφορα n όπως 2 ή 4

\\ Fibonacci Numbers with Dynamic Process

Global PickNew=0
F=lambda A=(1,1) (x) ->{
      PickNew<=False
      if x<=0 then =Array(A) : Exit
      if x<=Len(A) then =Array(A,x-1) : Exit
      PickNew<=True
      For i=Len(A) to x-1 {
            A=Cons(A,(Array(A,i-1)+Array(A,i-2),))
      }
      =Array(A,Len(A)-1)
}
n=1
For i=1 to 20 step n {
      Print i, F(i), PickNew
}
For i=1 to 20 step n {
      Print i, F(i), PickNew
}
M=F
For i=1 to 20 step n {
      Print i, M(i), PickNew
}



Μπορεί να γίνει και έτσι.

F=lambda A=(1,1) (x) ->{
      Link A to A()
      if x<=0 then =A(0) : Exit
      if x<=Len(A) then =A(x-1) : Exit
      For i=Len(A) to x-1 {
            A=Cons(A,(A(i-1)+A(i-2),))
      }
      =A(Len(A)-1)
}
n=1
For i=1 to 20 step n {
      Print i, F(i)
}
For i=1 to 20 step n {
      Print i, F(i)
}
M=F
For i=1 to 20 step n {
      Print i, M(i)
}

 

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου

You can feel free to write any suggestion, or idea on the subject.