Σε προηγούμενα μέρη (, ) μιλήσαμε για τα παγκόσμια ως δέντρα, σε αυτό θα δούμε τα παγκόσμια ως αραιούς πίνακες.
είναι ένας τύπος πίνακα στον οποίο οι περισσότερες από τις τιμές παίρνουν την ίδια τιμή.
Στην πράξη, οι αραιοί πίνακες είναι συχνά τόσο τεράστιοι που δεν έχει νόημα να καταλαμβάνουμε τη μνήμη με πανομοιότυπα στοιχεία. Επομένως, είναι λογικό να εφαρμόζουμε αραιούς πίνακες με τέτοιο τρόπο ώστε η μνήμη να μην σπαταλάται για την αποθήκευση πανομοιότυπων τιμών.
Σε ορισμένες γλώσσες προγραμματισμού, αραιοί πίνακες περιλαμβάνονται στην ίδια τη γλώσσα, , . Άλλες γλώσσες προγραμματισμού έχουν ειδικές βιβλιοθήκες που σας επιτρέπουν να τις εφαρμόσετε. Για C++ - κλπ.
Τα καθολικά είναι καλοί υποψήφιοι για την εφαρμογή αραιών πινάκων επειδή:
- Αποθηκεύουν τις τιμές μόνο ορισμένων κόμβων και δεν αποθηκεύουν τις τιμές ακαθόριστων.
- Η διεπαφή για την πρόσβαση στην τιμή ενός κόμβου είναι εξαιρετικά παρόμοια με το πόσες γλώσσες προγραμματισμού υλοποιούν πρόσβαση σε ένα στοιχείο πολυδιάστατου πίνακα.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Το Global είναι μια δομή αρκετά χαμηλού επιπέδου για την αποθήκευση δεδομένων, επομένως έχει εξαιρετικά χαρακτηριστικά ταχύτητας (από εκατοντάδες χιλιάδες έως δεκάδες εκατομμύρια συναλλαγές ανά δευτερόλεπτο, ανάλογα με το υλικό, δείτε παρακάτω). )
Δεδομένου ότι το καθολικό είναι μια επίμονη δομή, είναι λογικό να δημιουργούνται αραιοί πίνακες σε αυτούς όταν είναι γνωστό εκ των προτέρων ότι η ποσότητα της μνήμης RAM δεν θα είναι αρκετή.
Μία από τις ιδιότητες των υλοποιήσεων αραιού πίνακα είναι να επιστρέφουν κάποια προεπιλεγμένη τιμή εάν γίνει πρόσβαση σε ένα απροσδιόριστο κελί.
Αυτό μπορεί να υλοποιηθεί χρησιμοποιώντας τη συνάρτηση στην COS. Αυτό το παράδειγμα εξετάζει έναν τρισδιάστατο πίνακα.
SET a = $GET(^a(x,y,z), defValue)Ποιες εργασίες απαιτούν αραιούς πίνακες και πώς μπορούν να βοηθήσουν τα παγκόσμια;
Πίνακας γειτνίασης (συνδεσιμότητας).
χρησιμοποιείται για την αναπαράσταση γραφημάτων:
Προφανώς, όσο μεγαλύτερο είναι το γράφημα, τόσο περισσότερα μηδενικά θα υπάρχουν στον πίνακα. Εάν, για παράδειγμα, πάρουμε ένα γράφημα κοινωνικού δικτύου και το παρουσιάσουμε με τη μορφή ενός παρόμοιου πίνακα, τότε θα αποτελείται σχεδόν εξ ολοκλήρου από μηδενικά, δηλ. θα είναι ένας αραιός πίνακας.
Set ^m(id1, id2) = 1
Set ^m(id1, id3) = 1
Set ^m(id1, id4) = 1
Set ^m(id1) = 3
Set ^m(id2, id4) = 1
Set ^m(id2, id5) = 1
Set ^m(id2) = 2
....
Σε αυτό το παράδειγμα, κάνουμε εξοικονόμηση σε παγκόσμιο επίπεδο ^m μήτρα συνδεσιμότητας, καθώς και τον αριθμό των ακμών σε κάθε κόμβο (ποιος είναι φίλος με ποιον και ο αριθμός των φίλων).
Εάν ο αριθμός των στοιχείων στο γράφημα δεν είναι μεγαλύτερος από 29 εκατομμύρια (αυτός ο αριθμός λαμβάνεται ως το γινόμενο του 8 * ), δηλαδή ένας ακόμη πιο οικονομικός τρόπος αποθήκευσης τέτοιων πινάκων είναι οι συμβολοσειρές bit, αφού η εφαρμογή τους βελτιστοποιεί τα μεγάλα κενά με έναν ειδικό τρόπο.
Οι χειρισμοί με συμβολοσειρές bit εκτελούνται από τη συνάρτηση .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Πίνακας μετάβασης μηχανής κατάστασης
Εφόσον το γράφημα μετάβασης ενός πεπερασμένου αυτόματου είναι ένα συνηθισμένο γράφημα, τότε ο πίνακας μετάβασης του πεπερασμένου αυτόματου είναι ο ίδιος πίνακας γειτνίασης που συζητήθηκε παραπάνω.
Κυψελωτά αυτόματα
Το πιο διάσημο κυψελοειδές αυτόματο είναι , το οποίο, λόγω των κανόνων του (όταν ένα κελί έχει πολλούς γείτονες, πεθαίνει) είναι ένας αραιός πίνακας.
Ο Stephen Wolfram πιστεύει ότι τα κυψελωτά αυτόματα είναι . Το 2002, δημοσίευσε ένα βιβλίο 1280 σελίδων, A New Kind of Science, στο οποίο υποστηρίζει ευρέως ότι οι εξελίξεις στα κυψελωτά αυτόματα δεν είναι μεμονωμένες, αλλά είναι διαρκείς και έχουν μεγάλες επιπτώσεις σε όλους τους τομείς της επιστήμης.
Έχει αποδειχθεί ότι οποιοσδήποτε αλγόριθμος εκτελέσιμος σε έναν υπολογιστή μπορεί να υλοποιηθεί χρησιμοποιώντας ένα κυψελοειδές αυτόματο. Τα κυψελωτά αυτόματα χρησιμοποιούνται για τη μοντελοποίηση δυναμικών περιβαλλόντων και συστημάτων, για την επίλυση αλγοριθμικών προβλημάτων και για άλλους σκοπούς.
Εάν έχουμε ένα τεράστιο πεδίο και πρέπει να καταγράψουμε όλες τις ενδιάμεσες καταστάσεις ενός κυψελοειδούς αυτόματου, τότε είναι λογικό να χρησιμοποιούμε σφαιρικά.
Χαρτογραφία
Το πρώτο πράγμα που μου έρχεται στο μυαλό όταν πρόκειται να χρησιμοποιήσω αραιούς πίνακες είναι οι εργασίες χαρτογράφησης.
Κατά κανόνα, υπάρχει πολύς κενός χώρος στους χάρτες. Εάν ο χάρτης απεικονίζεται ως μεγάλα εικονοστοιχεία, τότε το 71% των εικονοστοιχείων της Γης θα καταλαμβάνεται από τον ωκεανό. Αραιή διάταξη. Και αν εφαρμόσετε μόνο έργα ανθρώπινων χεριών, τότε ο κενός χώρος θα είναι περισσότερο από 95%.
Φυσικά, κανείς δεν αποθηκεύει χάρτες με τη μορφή συστοιχιών ράστερ· χρησιμοποιείται διανυσματική αναπαράσταση.
Τι είναι όμως οι διανυσματικοί χάρτες; Αυτό είναι ένα είδος πλαισίου και πολυγραμμών και πολυγώνων που αποτελούνται από σημεία.
Ουσιαστικά μια βάση δεδομένων σημείων και συνδέσεων μεταξύ τους.
Μία από τις πιο φιλόδοξες αποστολές χαρτογράφησης είναι η αποστολή του τηλεσκοπίου Gaia για τη χαρτογράφηση του γαλαξία μας. Μεταφορικά, ο γαλαξίας μας, όπως και ολόκληρο το σύμπαν, είναι μια συνεχής αραιή διάταξη: τεράστιοι χώροι κενού στους οποίους υπάρχουν σπάνια μικρά σημεία - αστέρια. Ο κενός χώρος είναι 99,999999…….%. Για την αποθήκευση του χάρτη του γαλαξία μας, επιλέχθηκε μια παγκόσμια βάση δεδομένων - η Cache.
Δεν γνωρίζω την ακριβή δομή των παγκόσμιων σε αυτό το έργο, μπορώ να υποθέσω ότι είναι κάτι παρόμοιο με:
Set ^galaxy(b, l, d) = 1; Номер звезды по каталогу, если есть
Set ^galaxy(b, l, d, "name") = "Sun"
Set ^galaxy(b, l, d, "type") = "normal" ; варианты blackhole, quazar, red_dwarf и т.д.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercury"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Όπου είναι τα b, l, d και απόσταση από τον Ήλιο.
Η ευέλικτη δομή των παγκόσμιων σάς επιτρέπει να αποθηκεύσετε όλα τα απαραίτητα χαρακτηριστικά των αστεριών και των πλανητών, καθώς οι βάσεις σε παγκόσμιους δεν είναι σχεδιασμένες.
Για την αποθήκευση του χάρτη του σύμπαντός μας, το Cache επιλέχθηκε όχι μόνο για την ευελιξία του, αλλά και για την ικανότητά του να αποθηκεύει μια ροή δεδομένων πολύ γρήγορα, ενώ ταυτόχρονα δημιουργεί παγκόσμια ευρετήρια για γρήγορες αναζητήσεις.
Αν επιστρέψουμε στη Γη, τότε δημιουργήθηκαν χαρτογραφικά έργα σε παγκόσμιους και μια διχάλα του OpenStreetMap - .
Πρόσφατα στις εφαρμόστηκαν γεωχωρικοί δείκτες . Περιμένουμε άρθρο από τους συγγραφείς με λεπτομέρειες υλοποίησης.
Υλοποίηση χωρικών ευρετηρίων σε ένα παγκόσμιο στο OpenStreetMap XAPI
Φωτογραφίες τραβηγμένες από .
Ολόκληρη η υδρόγειος χωρίζεται σε τετράγωνα, μετά σε υποτετράγωνα, και σε υποτετράγωνα σε υποτετράγωνα κ.ο.κ. Γενικά, έχουμε μια ιεραρχική δομή για την αποθήκευση των σφαιρικών που δημιουργούνται.
Ανά πάσα στιγμή, μπορούμε σχεδόν αμέσως να ζητήσουμε το επιθυμητό τετράγωνο ή να το διαγράψουμε και όλα τα υποτετράγωνα θα επιστραφούν ή θα διαγραφούν επίσης.
Ένα παρόμοιο σχήμα στα παγκόσμια μπορεί να εφαρμοστεί με διάφορους τρόπους.
Επιλογή 1:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idПервойТочки
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idВторойТочки
...Επιλογή 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Και στις δύο περιπτώσεις, δεν είναι δύσκολο να χρησιμοποιήσετε το COS/M για να ζητήσετε σημεία που βρίσκονται σε τετράγωνο οποιουδήποτε επιπέδου. Θα είναι κάπως πιο εύκολο να καθαρίσετε τετράγωνα κομμάτια χώρου σε οποιοδήποτε επίπεδο στην πρώτη επιλογή, αλλά αυτό είναι σπάνια απαραίτητο.
Ένα παράδειγμα ενός από τα τετράγωνα χαμηλότερου επιπέδου:
Και εδώ είναι πολλά παγκόσμια από το έργο XAPI: αναπαράσταση ενός ευρετηρίου στα παγκόσμια:
παγκόσμια ^ τρόπος χρησιμοποιείται για την αποθήκευση σημείων (δρόμοι, ποταμάκια κ.λπ.) και πολύγωνα (κλειστές περιοχές: κτίρια, δάση κ.λπ.).
Πρόχειρη ταξινόμηση της χρήσης αραιών πινάκων σε καθολικά.
- Αποθηκεύουμε τις συντεταγμένες ορισμένων αντικειμένων και τις καταστάσεις τους (χαρτογράφηση, κυψελωτά αυτόματα)
- Αποθηκεύουμε αραιούς πίνακες.
Για την περίπτωση 2) όταν ζητάμε μια συγκεκριμένη συντεταγμένη όπου στο στοιχείο δεν έχει εκχωρηθεί μια τιμή, πρέπει να λάβουμε την τιμή του προεπιλεγμένου αραιού στοιχείου πίνακα.
Μπόνους που λαμβάνουμε κατά την αποθήκευση πολυδιάστατων πινάκων σε καθολικά
Αφαιρέστε γρήγορα και/ή επιλέξτε κομμάτια χώρου που είναι πολλαπλάσια σειρών, επιπέδων, κύβων κ.λπ. Για περιπτώσεις όπου χρησιμοποιούνται ευρετήρια ακεραίων, η δυνατότητα γρήγορης αφαίρεσης και/ή ανάκτησης τμημάτων χώρου που είναι πολλαπλάσια σειρών, επιπέδων, κύβων κ.λπ. μπορεί να είναι χρήσιμη.
Ομάδα μπορούμε να διαγράψουμε είτε ένα μεμονωμένο στοιχείο ή μια σειρά ή ακόμα και ένα ολόκληρο επίπεδο. Χάρη στις ιδιότητες των παγκόσμιων, αυτό συμβαίνει πολύ γρήγορα - χιλιάδες φορές πιο γρήγορα από την αφαίρεση στοιχείο προς στοιχείο.
Το σχήμα δείχνει έναν τρισδιάστατο πίνακα σε ένα παγκόσμιο ^a και διαφορετικούς τύπους διαγραφών.
Για να επιλέξετε κομμάτια χώρου χρησιμοποιώντας γνωστά ευρετήρια, μπορείτε να χρησιμοποιήσετε την εντολή .
Επιλογή στήλης μήτρας στη μεταβλητή Στήλη:
; Зададим трёхмерный разреженный массив 3x3x3
Set ^a(0,0,0)=1,^a(2,2,0)=1,^a(2,0,1)=1,^a(0,2,1)=1,^a(2,2,2)=1,^a(2,1,2)=1
Merge Column = ^a(2,2)
; Выведем переменную Column
Zwrite Column
Συμπέρασμα:
Column(0)=1
Column(2)=1
Αυτό που είναι ενδιαφέρον για τη μεταβλητή Column είναι ότι έχουμε επίσης έναν αραιό πίνακα, στον οποίο πρέπει επίσης να προσπελαστεί μέσω , αφού οι προεπιλεγμένες τιμές δεν αποθηκεύονται σε αυτό.
Η επιλογή κομματιών χώρου μπορεί επίσης να γίνει μέσω ενός μικρού προγράμματος χρησιμοποιώντας τη λειτουργία . Αυτό είναι ιδιαίτερα βολικό σε χώρους των οποίων οι δείκτες δεν είναι κβαντισμένοι (χαρτογραφία).
Συμπέρασμα
Οι σημερινοί καιροί θέτουν νέα φιλόδοξα καθήκοντα. Τα γραφήματα μπορούν να αποτελούνται από δισεκατομμύρια κορυφές, οι χάρτες από δισεκατομμύρια σημεία και μερικοί μπορεί ακόμη και να θέλουν να τρέξουν το δικό τους σύμπαν σε κυψελωτά αυτόματα (, ).
Όταν ο όγκος των δεδομένων από αραιούς πίνακες δεν χωράει πλέον στη μνήμη RAM, αλλά πρέπει να εργαστείτε μαζί τους, τότε αξίζει να εξεταστεί η δυνατότητα υλοποίησης παρόμοιων έργων σε παγκόσμιους και COS.
Σας ευχαριστώ για την προσοχή σας! Περιμένουμε τις ερωτήσεις και τις ευχές σας στα σχόλια.
Αποποίηση ευθυνών: Αυτό το άρθρο και τα σχόλιά μου σε αυτό είναι η γνώμη μου και δεν έχουν καμία σχέση με την επίσημη θέση της InterSystems Corporation.
Πηγή: www.habr.com