Δομές δεδομένων και αλγόριθμοι στην Java, το Μέρος 2 εισήγαγε μια ποικιλία τεχνικών για αναζήτηση και ταξινόμηση μονοδιάστατων συστοιχιών, οι οποίες είναι οι απλούστεροι πίνακες. Σε αυτό το σεμινάριο θα εξερευνήσετε πολυδιάστατους πίνακες. Θα σας δείξω τους τρεις τρόπους δημιουργίας πολυδιάστατων συστοιχιών και, στη συνέχεια, θα μάθετε πώς να χρησιμοποιείτε τον αλγόριθμο Matrix Multiplication για τον πολλαπλασιασμό στοιχείων σε έναν δισδιάστατο πίνακα. Θα παρουσιάσω επίσης ragged συστοιχίες και θα μάθετε γιατί είναι δημοφιλείς για εφαρμογές μεγάλων δεδομένων. Τέλος, θα εξετάσουμε το ερώτημα εάν ένας πίνακας είναι ή δεν είναι ένα αντικείμενο Java.
Αυτό το άρθρο σας προετοιμάζει για το Μέρος 4, το οποίο εισάγει την αναζήτηση και την ταξινόμηση με λίστες που συνδέονται μεμονωμένα.
Πολυδιάστατες συστοιχίες
ΕΝΑ πολυδιάστατος πίνακας συσχετίζει κάθε στοιχείο του πίνακα με πολλά ευρετήρια. Η συνηθέστερα χρησιμοποιούμενη πολυδιάστατη συστοιχία είναι η δισδιάστατος πίνακας, επίσης γνωστό ως τραπέζι ή μήτρα. Ένας δισδιάστατος πίνακας συσχετίζει κάθε ένα από τα στοιχεία του με δύο ευρετήρια.
Μπορούμε να αντιληφθούμε μια δισδιάστατη συστοιχία ως ορθογώνιο πλέγμα στοιχείων που χωρίζονται σε σειρές και στήλες. Χρησιμοποιούμε το (σειρά, στήλη) σημείωση για την αναγνώριση ενός στοιχείου, όπως φαίνεται στο σχήμα 1.
Επειδή οι δισδιάστατες συστοιχίες χρησιμοποιούνται τόσο συχνά, θα επικεντρωθώ σε αυτές. Αυτό που μαθαίνετε για τις δισδιάστατες συστοιχίες μπορεί να γενικευτεί σε ανώτερες διαστάσεις.
Δημιουργία δισδιάστατων συστοιχιών
Υπάρχουν τρεις τεχνικές για τη δημιουργία ενός δισδιάστατου πίνακα στην Java:
- Χρησιμοποιώντας έναν αρχικοποιητή
- Χρήση της λέξης-κλειδιού
νέος - Χρήση της λέξης-κλειδιού
νέοςμε έναν αρχικοποιητή
Χρησιμοποιώντας έναν αρχικοποιητή για τη δημιουργία ενός δισδιάστατου πίνακα
Η προσέγγιση μόνο για αρχικοποιητή για τη δημιουργία ενός δισδιάστατου πίνακα έχει την ακόλουθη σύνταξη:
'{' [rowInitializer (',' rowInitializer)*] '}'rowInitializer έχει την ακόλουθη σύνταξη:
'{' [π.χ. (',' π.χ.)*] '}'Αυτή η σύνταξη δηλώνει ότι ένας δισδιάστατος πίνακας είναι μια προαιρετική, διαχωρισμένη με κόμμα λίστα αρχικοποιητών γραμμής που εμφανίζεται μεταξύ χαρακτήρων ανοιχτού και κλεισίματος αγκύλης. Επιπλέον, κάθε αρχικοποιητής σειράς είναι μια προαιρετική λίστα εκφράσεων διαχωρισμένων με κόμματα που εμφανίζονται μεταξύ χαρακτήρων ανοιχτού και κλεισίματος αγκύλης. Όπως οι μονοδιάστατοι πίνακες, όλες οι εκφράσεις πρέπει να αξιολογούνται σε συμβατούς τύπους.
Ακολουθεί ένα παράδειγμα δισδιάστατου πίνακα:
{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }Αυτό το παράδειγμα δημιουργεί έναν πίνακα με δύο σειρές και τρεις στήλες. Το Σχήμα 2 παρουσιάζει μια εννοιολογική προβολή αυτού του πίνακα μαζί με μια προβολή μνήμης που δείχνει πώς η Java εκθέτει αυτόν τον πίνακα (και κάθε) στη μνήμη.
Το Σχήμα 2 αποκαλύπτει ότι η Java αντιπροσωπεύει μια δισδιάστατη συστοιχία ως μια μονοδιάστατη σειρά σειρών των οποίων τα στοιχεία αναφέρονται σε μονοδιάστατες στήλες. Το ευρετήριο γραμμών προσδιορίζει τον πίνακα στηλών. το ευρετήριο στηλών προσδιορίζει το στοιχείο δεδομένων.
Δημιουργία νέας λέξης-κλειδιού
Η λέξη-κλειδί νέος εκχωρεί μνήμη για έναν δισδιάστατο πίνακα και επιστρέφει την αναφορά του. Αυτή η προσέγγιση έχει την ακόλουθη σύνταξη:
'νέος' τύπος '[' int_expr1 ']' '['int_expr2 ']'Αυτή η σύνταξη δηλώνει ότι ένας δισδιάστατος πίνακας είναι μια περιοχή (θετική) int_expr1 στοιχεία γραμμής και (θετικά) int_expr2 στοιχεία στήλης που μοιράζονται όλα τα ίδια τύπος. Επιπλέον, όλα τα στοιχεία είναι μηδενισμένα. Ακολουθεί ένα παράδειγμα:
νέο διπλό [2] [3] // Δημιουργήστε έναν πίνακα δύο γραμμών με τρεις στήλες.Νέα λέξη-κλειδί και δημιουργία αρχικοποιητή
Η λέξη-κλειδί νέος με μια προσέγγιση αρχικοποίησης έχει την ακόλουθη σύνταξη:
'νέος' τύπος '[' ']' [' ']' '{' [rowInitializer (',' rowInitializer)*] '}'όπου rowInitializer έχει την ακόλουθη σύνταξη:
'{' [π.χ. (',' π.χ.)*] '}'Αυτή η σύνταξη συνδυάζει τα δύο προηγούμενα παραδείγματα. Επειδή ο αριθμός των στοιχείων μπορεί να προσδιοριστεί από τις λίστες εκφράσεων που διαχωρίζονται με κόμμα, δεν παρέχετε int_expr μεταξύ των δύο αγκυλών. Εδώ είναι ένα παράδειγμα:
νέο διπλό [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3, -16.2}}Διάστατες συστοιχίες και μεταβλητές πίνακα
Από μόνη της, ένας νεοδιάστατος πίνακας δύο διαστάσεων είναι άχρηστος. Η αναφορά του πρέπει να ανατεθεί σε ένα μεταβλητή πίνακα συμβατού τύπου, είτε απευθείας είτε μέσω κλήσης μεθόδου. Οι ακόλουθες σύνταξη δείχνουν πώς θα δηλώσετε αυτήν τη μεταβλητή:
τύποςvar_name '[' ']' '[' ']' τύπος '[' ']' '[' ']' var_nameΚάθε σύνταξη δηλώνει μια μεταβλητή πίνακα που αποθηκεύει μια αναφορά σε έναν δισδιάστατο πίνακα. Είναι προτιμότερο να τοποθετήσετε τα τετράγωνα αγκύλια μετά τύπος. Εξετάστε τα ακόλουθα παραδείγματα:
διπλή [] [] θερμοκρασίες1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}}; διπλό [] [] θερμοκρασίες2 = νέο διπλό [2] [3]; διπλό [] [] θερμοκρασίες3 = νέο διπλό [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3, -16.2}};Όπως οι μονοδιάστατες μεταβλητές συστοιχιών, μια δισδιάστατη μεταβλητή πίνακα συσχετίζεται με ένα .μήκος ιδιότητα, η οποία επιστρέφει το μήκος του πίνακα σειρών. Για παράδειγμα, θερμοκρασίες 1. μήκος επιστρέφει 2. Κάθε στοιχείο γραμμής είναι επίσης μια μεταβλητή πίνακα με ένα .μήκος ιδιότητα, η οποία επιστρέφει τον αριθμό στηλών για τον πίνακα στηλών που έχει εκχωρηθεί στο στοιχείο γραμμής. Για παράδειγμα, θερμοκρασίες1 [0]. μήκος επιστρέφει 3.
Δεδομένης μιας μεταβλητής πίνακα, μπορείτε να αποκτήσετε πρόσβαση σε οποιοδήποτε στοιχείο σε δισδιάστατο πίνακα καθορίζοντας μια παράσταση που συμφωνεί με την ακόλουθη σύνταξη:
συστοιχία_var '[' row_index ']' '[' col_index ']'Και οι δύο δείκτες είναι θετικοί ints που κυμαίνεται από 0 έως ένα μικρότερο από την τιμή που επιστρέφεται από το αντίστοιχο .μήκος ιδιότητες. Εξετάστε τα επόμενα δύο παραδείγματα:
διπλή θερμοκρασία = θερμοκρασίες1 [0] [1]; // Λάβετε αξία. θερμοκρασίες1 [0] [1] = 75.0; // Ορίστε τιμή.Το πρώτο παράδειγμα επιστρέφει την τιμή στη δεύτερη στήλη της πρώτης σειράς (30.6). Το δεύτερο παράδειγμα αντικαθιστά αυτήν την τιμή με 75.0.
Εάν καθορίσετε ένα αρνητικό ευρετήριο ή ένα ευρετήριο που είναι μεγαλύτερο ή ίσο με την τιμή που επιστρέφεται από τη μεταβλητή του πίνακα .μήκος ιδιοκτησία, η Java δημιουργεί και ρίχνει ένα ArrayIndexOutOfBoundsException αντικείμενο.
Πολλαπλασιασμός δισδιάστατων συστοιχιών
Ο πολλαπλασιασμός ενός πίνακα με έναν άλλο πίνακα είναι μια κοινή λειτουργία σε τομείς που κυμαίνονται από γραφικά υπολογιστών, οικονομικά, έως τη βιομηχανία μεταφορών. Οι προγραμματιστές συνήθως χρησιμοποιούν τον αλγόριθμο Matrix Multiplication για αυτήν τη λειτουργία.
Πώς λειτουργεί ο πολλαπλασιασμός του matrix; Αφήστε το A να αντιπροσωπεύει έναν πίνακα με Μ σειρές και Π στήλες. Ομοίως, αφήστε το B να αντιπροσωπεύει έναν πίνακα με Π σειρές και ν στήλες. Πολλαπλασιάστε το Α με το Β για να δημιουργήσετε έναν πίνακα C, με Μ σειρές και ν στήλες. Καθε cij η καταχώριση στο C λαμβάνεται πολλαπλασιάζοντας όλες τις καταχωρίσεις στα Α με σειρά με αντίστοιχες καταχωρήσεις στα B's jth στήλη και, στη συνέχεια, προσθέτοντας τα αποτελέσματα. Το σχήμα 3 απεικονίζει αυτές τις λειτουργίες.
Οι στήλες αριστερού πίνακα πρέπει να είναι ίσες με τις σειρές δεξιού πίνακα
Ο πολλαπλασιασμός μήτρας απαιτεί ο αριθμός των στηλών (p) στον αριστερό πίνακα (A) ίσος με τον αριθμό των γραμμών (p) στη δεξιά μήτρα (B). Διαφορετικά, αυτός ο αλγόριθμος δεν θα λειτουργήσει.
Ο ακόλουθος ψευδοκώδικας εκφράζει τον πολλαπλασιασμό Matrix σε ένα πλαίσιο πίνακα 2-σειρά-προς-2-στήλη και 2-σειρά-προς-1-στήλη. (Θυμηθείτε ότι εισήγαγα τον ψευδοκώδικα στο Μέρος 1.)
// == == == == == == // | 10 30 | | 5 | | 10 x 5 + 30 x 7 (260) | // | | Χ | | = | | // | 20 40 | | 7 | | 20 x 5 + 40 * 7 (380) | // == == == == == == ΔΗΛΩΣΗ ΕΝΣΩΜΑΤΩΝ α [] [] = [10, 30] [20, 40] ΔΗΛΩΣΗ ΕΙΣΑΓΩΓΗΣ b [] [] = [5, 7] ΔΗΛΩΣΗ ΕΝΤΑΞΗΣ m = 2 // Αριθμός σειρών στον αριστερό πίνακα (a) DECLARE INTEGER p = 2 // Αριθμός στηλών στον αριστερό πίνακα (a) // Αριθμός σειρών στη δεξιά μήτρα (b) DECLARE INTEGER n = 1 // Αριθμός στηλών στα δεξιά matrix (b) DECLARE INTEGER c [m] [n] // c κρατά 2 σειρές από 1 στήλες // Όλα τα στοιχεία αρχικοποιούνται σε 0 FOR i = 0 TO m - 1 FOR j = 0 TO n - 1 FOR k = 0 TO p - 1 c [i] [j] = c [i] [j] + a [i] [k] * b [k] [j] NEXT k NEXT j NEXT i ENDΛόγω των τριών ΓΙΑ βρόχους, ο πολλαπλασιασμός Matrix έχει πολυπλοκότητα χρόνου Ο (ν3), που προφέρεται "Big Oh of ν κυβισμένος. "Ο πολλαπλασιασμός Matrix προσφέρει κυβική απόδοση, η οποία αποκτά ακριβή χρονική διάρκεια όταν πολλαπλασιάζονται μεγάλες μήτρες. Προσφέρει πολυπλοκότητα χώρου Ο (νμ), που προφέρεται "Big Oh of ν*Μ, "για την αποθήκευση ενός επιπλέον πίνακα ν σειρές από Μ στήλες. Αυτό γίνεται Ο (ν2) για τετραγωνικές μήτρες.
Έχω δημιουργήσει ένα MatMult Εφαρμογή Java που σας επιτρέπει να πειραματιστείτε με τον πολλαπλασιασμό Matrix. Η λίστα 1 παρουσιάζει τον πηγαίο κώδικα αυτής της εφαρμογής.
Λίστα 1. Μια εφαρμογή Java για πειραματισμό με Matrix Multiplication (MatMult.java)
δημόσια τελική τάξη MatMult {public static void main (String [] args) {int [] [] a = {{10, 30}, {20, 40}}; int [] [] b = {{5}, {7}}; χωματερή (α) · System.out.println (); χωματερή (β) · System.out.println (); int [] [] c = πολλαπλασιασμός (a, b); χωματερή (γ) · } ιδιωτικό στατικό κενό vide (int [] [] x) {if (x == null) {System.err.println ("ο πίνακας είναι null"); ΕΠΙΣΤΡΟΦΗ; } // Πετάξτε τις τιμές του στοιχείου της μήτρας στην τυπική έξοδο με μια σειρά // πίνακα. για (int i = 0; i <x.length; i ++) {για (int j = 0; j <x [0] .length; j ++) System.out.print (x [i] [j] + "" ); System.out.println (); }} ιδιωτικό στατικό int [] [] πολλαπλασιασμό (int [] [] a, int [] [] b) {// ====================== ============================================== // 1. a.length περιέχει μια σειρά αριθμών // // 2. a [0] .length (ή οποιοδήποτε άλλο a [x] .length για έγκυρο x) περιέχει // // στήλη // // 3. b.length περιέχει πλήθος σειρών b // // 4. b [0] .length (ή οποιοδήποτε άλλο b [x] .length για έγκυρο x) περιέχει το b's // στήλη // ============ ================================================== ====== // Εάν μετράται η στήλη του α = = η σειρά της σειράς του b, διαφυλάξτε εάν (a [0] .length! = B.length) {System.err.println ("πλήθος στηλών a! = Πλήθος σειρών b "); επιστροφή μηδέν; } // Κατανομή πινάκων αποτελεσμάτων με μέγεθος ίσο με τον αριθμό αρίθμησης σειρών b's // στήλη μέτρηση int [] [] αποτέλεσμα = νέο int [a.length] []; για (int i = 0; i <result.length; i ++) αποτέλεσμα [i] = νέο int [b [0] .length]; // Εκτελέστε τον πολλαπλασιασμό και την προσθήκη για (int i = 0; i <a.length; i ++) για (int j = 0; j <b [0] .length; j ++) για (int k = 0; k <a [0] .length; k ++) // ή k <b.length αποτέλεσμα [i] [j] + = a [i] [k] * b [k] [j]; // Επιστρέψτε το αποτέλεσμα επιστροφής matrix αποτελέσματος. }}MatMult δηλώνει ένα ζεύγος πινάκων και ρίχνει τις τιμές τους στην τυπική έξοδο. Στη συνέχεια πολλαπλασιάζει και τους δύο πίνακες και απορρίπτει τον πίνακα αποτελεσμάτων στην τυπική έξοδο.
Μεταγλώττιση καταχώρισης 1 ως εξής:
javac MatMult.javaΕκτελέστε την εφαρμογή που προκύπτει ως εξής:
java MatMultΠρέπει να παρατηρήσετε την ακόλουθη έξοδο:
10 30 20 40 5 7 260 380Παράδειγμα πολλαπλασιασμού μήτρας
Ας διερευνήσουμε ένα πρόβλημα που επιλύεται καλύτερα με τον πολλαπλασιασμό του πίνακα. Σε αυτό το σενάριο, ένας καλλιεργητής φρούτων στη Φλόριντα φορτώνει μερικά ημιρυμουλκούμενα με 1.250 κουτιά πορτοκαλιών, 400 κουτιά ροδάκινων και 250 κουτιά γκρέιπφρουτ. Το σχήμα 4 δείχνει ένα γράφημα της τιμής αγοράς ανά κουτί για κάθε είδος φρούτου, σε τέσσερις διαφορετικές πόλεις.
Το πρόβλημά μας είναι να προσδιορίσουμε πού θα πρέπει να αποστέλλονται και να πωλούνται τα φρούτα για μέγιστο ακαθάριστο εισόδημα. Για να λύσουμε αυτό το πρόβλημα, αρχικά ανακατασκευάζουμε το γράφημα από το Σχήμα 4 ως πίνακα τιμών τεσσάρων σειρών με τρεις στήλες. Από αυτό, μπορούμε να κατασκευάσουμε έναν πίνακα μήκους τριών σειρών με μία στήλη, ο οποίος εμφανίζεται παρακάτω:
== == | 1250 | | | | 400 | | | | 250 | == ==Με τους δύο πίνακες στο χέρι, πολλαπλασιάζουμε απλά τον πίνακα τιμών με τον πίνακα ποσότητας για να παράγουμε έναν πίνακα ακαθάριστου εισοδήματος:
== == == == | 10.00 8.00 12.00 | == == | 18700,00 | Νέα Υόρκη | | | 1250 | | | | 11.00 8.50 11.55 | | | | 20037.50 | Λος Άντζελες | | Χ | 400 | = | | | 8,75 6,90 10,00 | | | | 16197.50 | Μαϊάμι | | | 250 | | | | 10.50 8.25 11.75 | == == | 19362.50 | Σικάγο == == == ==Η αποστολή και των δύο ημιρυμουλκούμενων στο Λος Άντζελες θα έχει το υψηλότερο ακαθάριστο εισόδημα. Αλλά όταν λαμβάνονται υπόψη τα έξοδα απόστασης και καυσίμου, ίσως η Νέα Υόρκη είναι ένα καλύτερο στοίχημα για την απόδοση του υψηλότερου εισοδήματος.
Ragged συστοιχίες
Έχοντας μάθει για δισδιάστατες συστοιχίες, ίσως τώρα αναρωτιέστε αν είναι δυνατόν να αντιστοιχίσετε μονοδιάστατες συστοιχίες στηλών με διαφορετικά μήκη σε στοιχεία μιας σειράς σειρών. Η απάντηση είναι ναι. Εξετάστε αυτά τα παραδείγματα:
διπλή [] [] θερμοκρασίες1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3}}; διπλό [] [] θερμοκρασίες2 = νέο διπλό [2] []; διπλό [] [] θερμοκρασίες3 = νέο διπλό [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3}};Το πρώτο και το τρίτο παράδειγμα δημιουργούν έναν δισδιάστατο πίνακα όπου η πρώτη σειρά περιέχει τρεις στήλες και η δεύτερη σειρά περιέχει δύο στήλες. Το δεύτερο παράδειγμα δημιουργεί έναν πίνακα με δύο σειρές και έναν μη καθορισμένο αριθμό στηλών.
Μετά τη δημιουργία θερμοκρασία2Ο πίνακας σειράς, τα στοιχεία του πρέπει να συμπληρωθούν με αναφορές σε νέες συστοιχίες στηλών. Το ακόλουθο παράδειγμα δείχνει, αντιστοιχίζοντας 3 στήλες στην πρώτη σειρά και 2 στήλες στη δεύτερη σειρά:
θερμοκρασίες2 [0] = νέο διπλό [3]; θερμοκρασίες2 [1] = νέο διπλό [2];Η προκύπτουσα δισδιάστατη συστοιχία είναι γνωστή ως ragged πίνακας. Εδώ είναι ένα δεύτερο παράδειγμα:
