Οι προγραμματιστές Java χρησιμοποιούν δομές δεδομένων για την αποθήκευση και την οργάνωση δεδομένων και χρησιμοποιούμε αλγόριθμους για τον χειρισμό των δεδομένων σε αυτές τις δομές. Όσο περισσότερο καταλαβαίνετε για τις δομές δεδομένων και τους αλγορίθμους και πώς λειτουργούν μαζί, τόσο πιο αποτελεσματικά θα είναι τα προγράμματα Java.
Αυτό το σεμινάριο ξεκινά μια σύντομη σειρά που εισάγει δομές δεδομένων και αλγόριθμους. Στο Μέρος 1, θα μάθετε τι είναι μια δομή δεδομένων και πώς ταξινομούνται οι δομές δεδομένων. Θα μάθετε επίσης τι είναι ένας αλγόριθμος, πώς αντιπροσωπεύονται οι αλγόριθμοι και πώς να χρησιμοποιείτε τις λειτουργίες πολυπλοκότητας χρόνου και χώρου για τη σύγκριση παρόμοιων αλγορίθμων. Μόλις αποκτήσετε αυτά τα βασικά, θα είστε έτοιμοι να μάθετε σχετικά με την αναζήτηση και την ταξινόμηση με μονοδιάστατους πίνακες, στο Μέρος 2.
Τι είναι η δομή δεδομένων;
Οι δομές δεδομένων βασίζονται σε αφηρημένους τύπους δεδομένων (ADT), τους οποίους ορίζει η Wikipedia ως εξής:
[A] μαθηματικό μοντέλο για τύπους δεδομένων όπου ένας τύπος δεδομένων ορίζεται από τη συμπεριφορά του (σημασιολογία) από την άποψη ενός χρήστη των δεδομένων, συγκεκριμένα όσον αφορά τις πιθανές τιμές, τις πιθανές λειτουργίες σε δεδομένα αυτού του τύπου και τη συμπεριφορά αυτών των εργασιών.Ένα ADT δεν ενδιαφέρεται για την αναπαράσταση της μνήμης των τιμών του ή για τον τρόπο υλοποίησης των λειτουργιών του. Είναι σαν μια διεπαφή Java, η οποία είναι ένας τύπος δεδομένων που αποσυνδέεται από οποιαδήποτε εφαρμογή. Αντίθετα, α δομή δεδομένων είναι μια συγκεκριμένη εφαρμογή ενός ή περισσότερων ADT, παρόμοια με τον τρόπο με τον οποίο οι κλάσεις Java εφαρμόζουν διεπαφές.
Παραδείγματα ADT περιλαμβάνουν υπαλλήλους, όχημα, συστοιχία και λίστα. Εξετάστε το List ADT (γνωστό και ως Sequence ADT), το οποίο περιγράφει μια ταξινομημένη συλλογή στοιχείων που έχουν κοινό τύπο. Κάθε στοιχείο αυτής της συλλογής έχει τη δική του θέση και επιτρέπονται διπλά στοιχεία. Οι βασικές λειτουργίες που υποστηρίζονται από το List ADT περιλαμβάνουν:
- Δημιουργία νέας και κενής λίστας
- Προσθήκη τιμής στο τέλος της λίστας
- Εισαγωγή τιμής στη λίστα
- Διαγραφή τιμής από τη λίστα
- Επανάληψη στη λίστα
- Καταστρέφοντας τη λίστα
Οι δομές δεδομένων που μπορούν να εφαρμόσουν το List ADT περιλαμβάνουν μονόστατες συστοιχίες σταθερού μεγέθους και δυναμικού μεγέθους και λίστες μεμονωμένες συνδέσεις. (Θα εισαχθείτε σε πίνακες στο Μέρος 2 και σε συνδεδεμένες λίστες στο Μέρος 3.)
Ταξινόμηση δομών δεδομένων
Υπάρχουν πολλά είδη δομών δεδομένων, που κυμαίνονται από μεμονωμένες μεταβλητές έως πίνακες ή συνδεδεμένες λίστες αντικειμένων που περιέχουν πολλά πεδία. Όλες οι δομές δεδομένων μπορούν να ταξινομηθούν ως αρχικά ή συγκεντρωτικά στοιχεία, και ορισμένες ταξινομούνται ως κοντέινερ.
Πρωτόγονες έναντι αδρανών
Το απλούστερο είδος δομής δεδομένων αποθηκεύει μεμονωμένα στοιχεία δεδομένων. Για παράδειγμα, μια μεταβλητή που αποθηκεύει μια τιμή Boolean ή μια μεταβλητή που αποθηκεύει έναν ακέραιο. Αναφέρομαι σε τέτοιες δομές δεδομένων όπως πρωτόγονα.
Πολλές δομές δεδομένων είναι σε θέση να αποθηκεύουν πολλά στοιχεία δεδομένων. Για παράδειγμα, ένας πίνακας μπορεί να αποθηκεύσει πολλά στοιχεία δεδομένων στις διάφορες υποδοχές του και ένα αντικείμενο μπορεί να αποθηκεύσει πολλά στοιχεία δεδομένων μέσω των πεδίων του. Αναφέρομαι σε αυτές τις δομές δεδομένων ως αδρανή.
Όλες οι δομές δεδομένων που θα εξετάσουμε σε αυτήν τη σειρά είναι συγκεντρωτικά.
Εμπορευματοκιβώτια
Οτιδήποτε από το οποίο αποθηκεύονται και ανακτώνται στοιχεία δεδομένων θα μπορούσε να θεωρηθεί δομή δεδομένων. Στα παραδείγματα περιλαμβάνονται οι δομές δεδομένων που προέρχονται από τους ADT υπαλλήλων, οχημάτων, συστοιχιών και λιστών.
Πολλές δομές δεδομένων έχουν σχεδιαστεί για να περιγράψουν διάφορες οντότητες. Παρουσιάσεις ενός Υπάλληλος τάξη είναι δομές δεδομένων που υπάρχουν για να περιγράψουν διάφορους υπαλλήλους, για παράδειγμα. Αντιθέτως, ορισμένες δομές δεδομένων υπάρχουν ως γενικά δοχεία αποθήκευσης για άλλες δομές δεδομένων. Για παράδειγμα, ένας πίνακας μπορεί να αποθηκεύσει πρωτόγονες τιμές ή αναφορές αντικειμένων. Αναφέρομαι σε αυτήν την τελευταία κατηγορία δομών δεδομένων ως εμπορευματοκιβώτια.
Εκτός από τα συγκεντρωτικά στοιχεία, όλες οι δομές δεδομένων που θα εξετάσουμε σε αυτήν τη σειρά είναι κοντέινερ.
Δομές δεδομένων και αλγόριθμοι στις Συλλογές Java
Το Java Συλλογές Πλαίσιο υποστηρίζει πολλά είδη δομών δεδομένων προσανατολισμένων σε κοντέινερ και συναφών αλγορίθμων. Αυτή η σειρά θα σας βοηθήσει να κατανοήσετε καλύτερα αυτό το πλαίσιο.
Σχέδια σχεδιασμού και δομές δεδομένων
Έχει γίνει αρκετά συνηθισμένο να χρησιμοποιείς μοτίβα σχεδιασμού για να εισάγεις φοιτητές σε δομές δεδομένων. Μια εφημερίδα Brown University ερευνά διάφορα σχέδια σχεδίασης που είναι χρήσιμα για το σχεδιασμό δομών δεδομένων υψηλής ποιότητας. Μεταξύ άλλων, το χαρτί δείχνει ότι το μοτίβο προσαρμογέα είναι χρήσιμο για το σχεδιασμό στοίβων και ουρών. Ο κωδικός επίδειξης εμφανίζεται στη λίστα 1.
Λίστα 1. Χρήση του μοτίβου προσαρμογέα για στοίβες και ουρές (DequeStack.java)
δημόσια τάξη Το DequeStack εφαρμόζει το Stack {Deque D; // κρατά τα στοιχεία της στοίβας δημόσια DequeStack () {D = new MyDeque (); } @Override δημόσιο int μέγεθος () {return D.size (); } @Override public boolean isEmpty () {return D.isEmpty (); } @Override public void push (Object obj) {D.insertLast (obj); } @Override public Object top () ρίχνει StackEmptyException {δοκιμάστε {return D.lastElement (); } catch (DequeEmptyException err) {ρίξτε νέο StackEmptyException (); }} Το @Override public Object pop () ρίχνει το StackEmptyException {δοκιμάστε {return D.removeLast (); } catch (DequeEmptyException err) {ρίξτε νέο StackEmptyException (); }}}Στη λίστα 1 αποσπάσματα της εφημερίδας Brown University DequeStack κλάση, η οποία δείχνει το μοτίβο προσαρμογέα. Σημειώστε ότι Σωρός και Ντεκ είναι διασυνδέσεις που περιγράφουν Stack και Deque ADTs. MyDeque είναι μια τάξη που εφαρμόζει Ντεκ.
Παράκαμψη μεθόδων διεπαφής
Ο αρχικός κώδικας στον οποίο βασίζεται η καταχώριση 1 δεν παρουσίασε τον πηγαίο κώδικα Σωρός, Ντεκ, και MyDeque. Για λόγους σαφήνειας, έχω εισαγάγει @Καταπατώ σχολιασμούς για να δείξει ότι όλα DequeStackΟι μέθοδοι που δεν είναι κατασκευαστές παρακάμπτουν Σωρός μεθόδους.
DequeStack προσαρμόζεται MyDeque έτσι ώστε να μπορεί να εφαρμοστεί Σωρός. Ολα DequeStackΗ μέθοδος είναι κλήσεις μιας γραμμής στο Ντεκ μεθόδους διεπαφής. Ωστόσο, υπάρχει μια μικρή ρυτίδα στην οποία Ντεκ εξαιρέσεις μετατρέπονται σε Σωρός εξαιρέσεις.
Τι είναι ο αλγόριθμος;
Ιστορικά χρησιμοποιούνται ως εργαλείο για μαθηματικούς υπολογισμούς, οι αλγόριθμοι συνδέονται βαθιά με την επιστήμη των υπολογιστών και ειδικότερα με τις δομές δεδομένων. Ενα αλγόριθμος είναι μια ακολουθία οδηγιών που ολοκληρώνει μια εργασία σε μια πεπερασμένη χρονική περίοδο. Οι ποιότητες ενός αλγορίθμου έχουν ως εξής:
- Λαμβάνει μηδενικές ή περισσότερες εισόδους
- Παράγει τουλάχιστον μία έξοδο
- Αποτελείται από σαφείς και σαφείς οδηγίες
- Τερματίζει μετά από έναν πεπερασμένο αριθμό βημάτων
- Είναι αρκετά βασικό ώστε ένα άτομο να μπορεί να το πραγματοποιήσει χρησιμοποιώντας ένα μολύβι και χαρτί
Σημειώστε ότι ενώ τα προγράμματα μπορεί να έχουν αλγοριθμικό χαρακτήρα, πολλά προγράμματα δεν τερματίζονται χωρίς εξωτερική παρέμβαση.
Πολλές ακολουθίες κώδικα χαρακτηρίζονται ως αλγόριθμοι. Ένα παράδειγμα είναι μια ακολουθία κώδικα που εκτυπώνει μια αναφορά. Πιο διάσημα, ο αλγόριθμος του Euclid χρησιμοποιείται για τον υπολογισμό του μαθηματικού μεγαλύτερου κοινού διαιρέτη. Θα μπορούσε ακόμη να γίνει μια υπόθεση ότι οι βασικές λειτουργίες μιας δομής δεδομένων (όπως τιμή αποθήκευσης σε υποδοχή πίνακα) είναι αλγόριθμοι. Σε αυτήν τη σειρά, ως επί το πλείστον, θα επικεντρωθώ σε αλγόριθμους υψηλότερου επιπέδου που χρησιμοποιούνται για την επεξεργασία δομών δεδομένων, όπως οι αλγόριθμοι Binary Search και Matrix Multiplication.
Διαγράμματα ροής και ψευδοκώδικας
Πώς αντιπροσωπεύετε έναν αλγόριθμο; Η σύνταξη κώδικα πριν κατανοήσετε πλήρως τον υποκείμενο αλγόριθμό του μπορεί να οδηγήσει σε σφάλματα, οπότε ποια είναι η καλύτερη εναλλακτική λύση; Δύο επιλογές είναι διαγράμματα ροής και ψευδοκώδικας.
Χρήση διαγραμμάτων ροής για την αναπαράσταση αλγορίθμων
ΕΝΑ ΔΙΑΓΡΑΜΜΑ ΡΟΗΣ είναι μια οπτική αναπαράσταση της ροής ελέγχου ενός αλγορίθμου. Αυτή η αναπαράσταση απεικονίζει δηλώσεις που πρέπει να εκτελεστούν, αποφάσεις που πρέπει να ληφθούν, λογική ροή (για επανάληψη και άλλους σκοπούς), και τερματικά που υποδεικνύουν σημεία έναρξης και λήξης. Το σχήμα 1 αποκαλύπτει τα διάφορα σύμβολα που χρησιμοποιούν τα διαγράμματα ροής για την απεικόνιση αλγορίθμων.
Σκεφτείτε έναν αλγόριθμο που αρχικοποιεί έναν μετρητή στο 0, διαβάζει χαρακτήρες μέχρι μια νέα γραμμή (\ n) εμφανίζεται ο χαρακτήρας, αυξάνει τον μετρητή για κάθε ψηφίο χαρακτήρα που έχει διαβαστεί και εκτυπώνει την τιμή του μετρητή μετά την ανάγνωση του χαρακτήρα γραμμής. Το διάγραμμα ροής στο σχήμα 2 απεικονίζει τη ροή ελέγχου αυτού του αλγορίθμου.
Η απλότητα ενός διαγράμματος ροής και η ικανότητά του να παρουσιάζει οπτικά τη ροή ελέγχου ενός αλγορίθμου (έτσι ώστε να είναι εύκολο να ακολουθηθεί) είναι τα κύρια πλεονεκτήματά του. Τα διαγράμματα ροής έχουν επίσης πολλά μειονεκτήματα, ωστόσο:
- Είναι εύκολο να εισαγάγετε σφάλματα ή ανακρίβειες σε πολύ λεπτομερή διαγράμματα ροής λόγω του μέσου που σχετίζεται με την σχεδίασή τους.
- Χρειάζεται χρόνος για να τοποθετήσετε, να επισημάνετε και να συνδέσετε τα σύμβολα ενός διαγράμματος ροής, ακόμη και χρησιμοποιώντας εργαλεία για να επιταχύνετε αυτήν τη διαδικασία. Αυτή η καθυστέρηση μπορεί να επιβραδύνει την κατανόηση ενός αλγορίθμου.
- Τα διαγράμματα ροής ανήκουν στην εποχή του δομημένου προγραμματισμού και δεν είναι τόσο χρήσιμα σε ένα αντικειμενοστρεφές πλαίσιο. Αντίθετα, το Unified Modeling Language (UML) είναι καταλληλότερο για τη δημιουργία αντικειμενοστρεφών οπτικών αναπαραστάσεων.
Χρήση του ψευδοκώδικα για την αναπαράσταση αλγορίθμων
Μια εναλλακτική λύση για τα διαγράμματα ροής είναι ψευδοκώδικας, που είναι μια αναπαράσταση κειμένου ενός αλγορίθμου που προσεγγίζει τον τελικό πηγαίο κώδικα. Ο ψευδοκώδικας είναι χρήσιμος για τη γρήγορη καταγραφή της αναπαράστασης ενός αλγορίθμου. Επειδή η σύνταξη δεν προκαλεί ανησυχία, δεν υπάρχουν σκληροί και γρήγοροι κανόνες για τη σύνταξη ψευδοκώδικα.
Θα πρέπει να προσπαθείτε για συνέπεια κατά τη σύνταξη ψευδοκώδικα. Το να είσαι συνεπής θα διευκολύνει τη μετάφραση του ψευδοκώδικα σε πραγματικό πηγαίο κώδικα. Για παράδειγμα, εξετάστε την ακόλουθη αναπαράσταση ψευδοκώδικα του προηγούμενου διαγράμματος ροής αντίθετου προσανατολισμού:
DECLARE CHARACTER ch = "DECLARE INTEGER count = 0 DO READ ch IF ch GE '0" AND ch LE' 9 "THEN count = count + 1 END IF UNTIL ch EQ" \ n "PRINT count ENDΟ ψευδοκώδικας παρουσιάζει πρώτα δύο ΔΗΛΩΝΩ δηλώσεις που εισάγουν μεταβλητές χρ και μετρώ, αρχικοποιήθηκε σε προεπιλεγμένες τιμές. Στη συνέχεια παρουσιάζει ένα ΚΑΝΩ βρόχος που εκτελεί ΜΕΧΡΙχρ περιέχει \ n (ο χαρακτήρας νέας γραμμής), σε ποιο σημείο τελειώνει ο βρόχος και a ΤΥΠΩΝΩ εξόδους δήλωσης μετρώαξία.
Για κάθε επανάληψη βρόχου, ΑΝΑΓΝΩΣΗ προκαλεί την ανάγνωση ενός χαρακτήρα από το πληκτρολόγιο (ή ίσως ένα αρχείο - σε αυτήν την περίπτωση δεν έχει σημασία τι αποτελεί την υποκείμενη πηγή εισόδου) και εκχωρείται σε χρ. Εάν αυτός ο χαρακτήρας είναι ψηφίο (ένα από τα 0 διά μέσου 9), μετρώ αυξάνεται από 1.
Επιλέγοντας τον σωστό αλγόριθμο
Οι δομές δεδομένων και οι αλγόριθμοι που χρησιμοποιείτε επηρεάζουν κριτικά δύο παράγοντες στις εφαρμογές σας:
- Χρήση μνήμης (για δομές δεδομένων).
- Χρόνος CPU (για αλγόριθμους που αλληλεπιδρούν με αυτές τις δομές δεδομένων).
Ακολουθεί ότι πρέπει να προσέχετε ιδιαίτερα τους αλγόριθμους και τις δομές δεδομένων που χρησιμοποιείτε για εφαρμογές που θα επεξεργάζονται πολλά δεδομένα. Αυτές περιλαμβάνουν εφαρμογές που χρησιμοποιούνται για μεγάλα δεδομένα και το Διαδίκτυο των πραγμάτων.
Εξισορρόπηση μνήμης και CPU
Όταν επιλέγετε μια δομή δεδομένων ή έναν αλγόριθμο, μερικές φορές θα ανακαλύψετε ένα αντίστροφη σχέση μεταξύ της χρήσης μνήμης και του χρόνου της CPU: όσο λιγότερη μνήμη χρησιμοποιεί μια δομή δεδομένων, τόσο περισσότεροι αλγόριθμοι που σχετίζονται με τον χρόνο CPU πρέπει να επεξεργάζονται τα στοιχεία δεδομένων της δομής δεδομένων. Επίσης, όσο περισσότερη μνήμη χρησιμοποιεί μια δομή δεδομένων, τόσο λιγότεροι αλγόριθμοι που σχετίζονται με τον χρόνο CPU θα χρειαστεί να επεξεργαστούν τα στοιχεία δεδομένων - οδηγώντας σε ταχύτερα αποτελέσματα αλγορίθμων.
Όσο το δυνατόν περισσότερο, πρέπει να προσπαθήσετε να εξισορροπήσετε τη χρήση της μνήμης με το χρόνο της CPU. Μπορείτε να απλοποιήσετε αυτήν την εργασία αναλύοντας αλγόριθμους για να προσδιορίσετε την αποτελεσματικότητά τους. Πόσο καλά αποδίδει ένας αλγόριθμος έναντι άλλου παρόμοιας φύσης; Η απάντηση σε αυτήν την ερώτηση θα σας βοηθήσει να κάνετε καλές επιλογές δεδομένης της επιλογής μεταξύ πολλαπλών αλγορίθμων.
Μέτρηση της αποτελεσματικότητας του αλγορίθμου
Ορισμένοι αλγόριθμοι έχουν καλύτερη απόδοση από άλλους. Για παράδειγμα, ο αλγόριθμος Binary Search είναι σχεδόν πάντα πιο αποτελεσματικός από τον αλγόριθμο Linear Search - κάτι που θα δείτε μόνοι σας στο Μέρος 2. Θέλετε να επιλέξετε τον πιο αποτελεσματικό αλγόριθμο για τις ανάγκες της εφαρμογής σας, αλλά αυτή η επιλογή μπορεί να μην είναι τόσο προφανής όπως θα νομίζατε.
Για παράδειγμα, τι σημαίνει εάν ο αλγόριθμος επιλογής ταξινόμησης (που παρουσιάζεται στο Μέρος 2) διαρκεί 0,4 δευτερόλεπτα για να ταξινομήσει 10.000 ακέραιους αριθμούς σε ένα συγκεκριμένο μηχάνημα; Αυτό το σημείο αναφοράς ισχύει μόνο για τη συγκεκριμένη μηχανή, τη συγκεκριμένη εφαρμογή του αλγορίθμου και για το μέγεθος των δεδομένων εισαγωγής.
Ως επιστήμονας υπολογιστών, χρησιμοποιούμε την πολυπλοκότητα του χρόνου και την πολυπλοκότητα του χώρου για να μετρήσουμε την αποτελεσματικότητα ενός αλγορίθμου, αποστάζοντας τους λειτουργίες πολυπλοκότητας να αφαιρέσετε λεπτομέρειες εφαρμογής και περιβάλλοντος χρόνου εκτέλεσης. Οι λειτουργίες πολυπλοκότητας αποκαλύπτουν τη διακύμανση των απαιτήσεων χρόνου και χώρου ενός αλγορίθμου με βάση την ποσότητα των δεδομένων εισαγωγής:
- ΕΝΑ συνάρτηση χρόνου-πολυπλοκότητας μετρά έναν αλγόριθμο χρονική πολυπλοκότητα- σημαίνει πόσος χρόνος χρειάζεται για να ολοκληρωθεί ένας αλγόριθμος.
- ΕΝΑ συνάρτηση διαστήματος-πολυπλοκότητας μετρά έναν αλγόριθμο πολυπλοκότητα του χώρου- σημαίνει το ποσό της γενικής μνήμης που απαιτείται από τον αλγόριθμο για την εκτέλεση της εργασίας του.
Και οι δύο λειτουργίες πολυπλοκότητας βασίζονται στο μέγεθος της εισόδου (ν), που αντικατοπτρίζει κατά κάποιο τρόπο την ποσότητα των δεδομένων εισαγωγής. Εξετάστε τον ακόλουθο ψευδοκώδικα για εκτύπωση πίνακα:
ΔΗΛΩΣΗ INTEGER i, x [] = [10, 15, -1, 32] FOR i = 0 TO LENGTH (x) - 1 PRINT x [i] NEXT i ENDΛειτουργίες πολυπλοκότητας χρόνου και πολυπλοκότητας χρόνου
Μπορείτε να εκφράσετε την πολυπλοκότητα αυτού του αλγορίθμου καθορίζοντας τη συνάρτηση χρονικής πολυπλοκότητας τ (ν) = αν+ β, όπου ένα (ένας σταθερός πολλαπλασιαστής) αντιπροσωπεύει το χρονικό διάστημα για την ολοκλήρωση της επανάληψης ενός βρόχου, και σι αντιπροσωπεύει τον χρόνο ρύθμισης του αλγορίθμου. Σε αυτό το παράδειγμα, η πολυπλοκότητα του χρόνου είναι γραμμική.
