DedSec Project

Χρόνος ζωής δεδομένων και επιλογή δομών — DedSec Project

Χρόνος ζωής δεδομένων και επιλογή δομών Προχωρημένα εργαστήρια μηχανικής Χρόνος εκτέλεσης, στοίβα κλήσεων, σωρός και διάρκεια ζωής Το πρόγραμμα δεν είναι μόνο πηγαίος κώδικας. Κατά την…

Προχωρημένα εργαστήρια μηχανικής

Χρόνος εκτέλεσης, στοίβα κλήσεων, σωρός και διάρκεια ζωής

Το πρόγραμμα δεν είναι μόνο πηγαίος κώδικας. Κατά την εκτέλεση χρειάζεται μνήμη, είσοδο/έξοδο, χρονοπρογραμματισμό και περιβάλλον εκτέλεσης. Μια κλήση συνάρτησης δημιουργεί συνήθως πλαίσιο στη στοίβα με το σημείο επιστροφής, τις παραμέτρους και τις τοπικές μεταβλητές. Τα δυναμικά αντικείμενα συχνά αποθηκεύονται στον σωρό· η διαχείρισή τους μπορεί να γίνεται χειροκίνητα, με μετρητές αναφορών ή με συλλογή απορριμμάτων.

Παράδειγμα (Python)

def factorial(n: int) -> int:
    if n < 0: raise ValueError('n must be nonnegative')
    result = 1
    for value in range(2, n + 1):
        result *= value
    return result
assert factorial(5) == 120

Η επαναληπτική λύση χρησιμοποιεί O(1) βοηθητική μνήμη, ενώ η αναδρομική O(n) πλαίσια κλήσεων χωρίς εγγυημένη βελτιστοποίηση ουραίας αναδρομής.

Σφάλματα και συμβιβασμοί

Το MemoryError διαφέρει από την υπερχείλιση στοίβας. Στη C/C++ εσφαλμένη ιδιοκτησία μνήμης δημιουργεί δείκτες σε άκυρα δεδομένα ή διπλή αποδέσμευση. Σε γλώσσες με αυτόματη διαχείριση, αντικείμενα που παραμένουν προσβάσιμα μπορούν να διατηρούνται άσκοπα.

Ασκήσεις

  1. Σύγκρινε αναδρομικό και επαναληπτικό Fibonacci για n=30.
  2. Παρακολούθησε τον χρόνο ζωής μιας λίστας.
  3. Εξήγησε γιατί η επιστροφή δείκτη σε τοπική μεταβλητή της C είναι επικίνδυνη.

Επιλογή δομών δεδομένων ανάλογα με το κόστος λειτουργιών

Η επιλογή δομής δεδομένων επηρεάζει περισσότερο την απόδοση από πολλές μικροβελτιστοποιήσεις. Η λίστα έχει O(1) πρόσβαση με δείκτη, αλλά γραμμική αναζήτηση O(n). Ένας πίνακας κατακερματισμού προσφέρει μέση αναζήτηση O(1) με επιπλέον μνήμη. Ο σωρός προτεραιότητας προσφέρει O(log n) εισαγωγή και αφαίρεση. Η ουρά διπλού άκρου επιτρέπει O(1) προσθήκη/αφαίρεση στα άκρα.

Παράδειγμα

from collections import deque
pending = deque(['A','B'])
pending.append('C')
assert pending.popleft() == 'A'

Ασκήσεις

  1. Επίλεξε δομή για ένα εκατομμύριο ελέγχους συμμετοχής.
  2. Υλοποίησε αναίρεση ενεργειών με στοίβα.
  3. Σχεδίασε χρονοπρογραμματιστή με προθεσμίες.
  4. Σκέψου πότε η σταθερή σειρά διευκολύνει τις δοκιμές.

Τεχνικές σημειώσεις πεδίου