Εισαγωγή
Αναδρομή ουράς
Όταν κάνεις αναδρομή μέσα από απαριθμήσιμα (λίστες, bitstrings, συμβολοσειρές), υπάρχουν συχνά δύο ζητήματα:
- πόση μνήμη χρειάζεται για να αποθηκευτεί το ίχνος των αναδρομικών κλήσεων συναρτήσεων
- πώς να χτίσεις τη λύση αποδοτικά
Για να αντιμετωπίσεις αυτά τα ζητήματα, μπορείς να χρησιμοποιήσεις έναν συσσωρευτή.
Ο συσσωρευτής είναι μια μεταβλητή που περνιέται μαζί με τα δεδομένα. Χρησιμοποιείται για να μεταφέρει την τρέχουσα κατάσταση της εκτέλεσης της συνάρτησης, από κλήση σε κλήση, μέχρι να φτάσουμε στη βασική περίπτωση. Στη βασική περίπτωση, ο συσσωρευτής χρησιμοποιείται για να επιστραφεί η τελική τιμή της αναδρομικής κλήσης της συνάρτησης.
Οι συσσωρευτές πρέπει να αρχικοποιούνται από τον συγγραφέα της συνάρτησης, όχι από τον χρήστη της. Για να το πετύχεις αυτό, δήλωσε δύο συναρτήσεις: μια δημόσια συνάρτηση που παίρνει ως ορίσματα μόνο τα απαραίτητα δεδομένα και αρχικοποιεί τον συσσωρευτή, και μια ιδιωτική συνάρτηση που παίρνει κι αυτή έναν συσσωρευτή. Στην Elixir, είναι συνηθισμένο μοτίβο να βάζεις το πρόθεμα do_ στο όνομα της ιδιωτικής συνάρτησης.
# Count the length of a list without an accumulator
def count([]), do: 0
def count([_head | tail]), do: 1 + count(tail)
# Count the length of a list with an accumulator
def count(list), do: do_count(list, 0)
defp do_count([], count), do: count
defp do_count([_head | tail], count), do: do_count(tail, count + 1)
Η χρήση ενός συσσωρευτή μάς επιτρέπει να μετατρέψουμε αναδρομικές συναρτήσεις σε συναρτήσεις αναδρομής ουράς. Μια συνάρτηση είναι αναδρομική ουράς αν το τελευταίο πράγμα που εκτελείται μέσα της είναι μια κλήση στον εαυτό της.
Οδηγίες
Στο εργαστήριο έρευνας DNA σου, έχεις δοκιμάσει διάφορους τρόπους συμπίεσης των ερευνητικών δεδομένων σου για να εξοικονομήσεις χώρο αποθήκευσης. Ένας συνεργάτης σου προτείνει να μετατρέψεις τα δεδομένα DNA σε δυαδική αναπαράσταση:
| Νουκλεϊκό οξύ |
Κωδικός |
| ένα κενό |
0000 |
| A |
0001 |
| C |
0010 |
| G |
0100 |
| T |
1000 |
Το σκέφτεσαι, καθώς ενδέχεται να μειώσει στο μισό το απαιτούμενο κόστος αποθήκευσης δεδομένων, αλλά εις βάρος της αναγνωσιμότητας από τον άνθρωπο. Αποφασίζεις να γράψεις ένα module για κωδικοποίηση και αποκωδικοποίηση των δεδομένων σου, ώστε να αξιολογήσεις την εξοικονόμηση.
1. Κωδικοποίησε νουκλεϊκό οξύ σε δυαδική τιμή
Υλοποίησε τη συνάρτηση encode_nucleotide/1 ώστε να δέχεται το σημείο κώδικα για το νουκλεϊκό οξύ και να επιστρέφει την ακέραια τιμή του κωδικοποιημένου κωδικού.
DNA.encode_nucleotide(?A)
# => 1
# (which is equal to 0b0001)
2. Αποκωδικοποίησε τη δυαδική τιμή σε νουκλεϊκό οξύ
Υλοποίησε τη συνάρτηση decode_nucleotide/1 ώστε να δέχεται την ακέραια τιμή του κωδικοποιημένου κωδικού και να επιστρέφει το σημείο κώδικα για το νουκλεϊκό οξύ.
DNA.decode_nucleotide(0b0001)
# => 65
# (which is equal to ?A)
3. Κωδικοποίησε μια λίστα χαρακτήρων DNA
Υλοποίησε τη συνάρτηση encode/1 ώστε να δέχεται μια λίστα χαρακτήρων που αντιπροσωπεύει νουκλεϊκά οξέα και κενά και να επιστρέφει ένα bitstring με τα κωδικοποιημένα δεδομένα.
DNA.encode(~c"AC GT")
# => <<18, 4, 8::size(4)>>
4. Αποκωδικοποίησε ένα bitstring DNA
Υλοποίησε τη συνάρτηση decode/1 ώστε να δέχεται ένα bitstring που αντιπροσωπεύει νουκλεϊκά οξέα και κενά και να επιστρέφει τα αποκωδικοποιημένα δεδομένα ως λίστα χαρακτήρων.
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
Άσκηση εκμάθησης
