Μια επισκόπηση του τρόπου λειτουργίας των συστοιχιών

Στην επιστήμη των υπολογιστών, υπάρχει η έννοια μιας γραμμικής δομής δεδομένων , που σημαίνει ότι τα δεδομένα είναι δομημένα με γραμμικό τρόπο με τον οποίο έχει σημασία η σειρά . Υπάρχουν πίνακες και συνδεδεμένες λίστες , αλλά σήμερα θα μιλάω κυρίως για πίνακες και λίγα για συνδεδεμένες λίστες.

Οι περισσότεροι αντικείμενο με προσανατολισμό γλώσσες έρχονται με πίνακες , ενώ τα περισσότερα στ unctional γλώσσες έρχονται με συνδεδεμένες λίστες (δείτε γιατί σε άλλο ένα από τα άρθρα μου, αναφέρεται στο κάτω μέρος αυτού του άρθρου).

Υπάρχει ένας καλός λόγος για αυτήν τη διαφοροποίηση που θα βρούμε αργότερα. Προς το παρόν ας ρίξουμε μια γρήγορη ματιά στις διαφορές μεταξύ των δύο δομών δεδομένων. Για να το κάνουμε αυτό, θα πρέπει να κάνουμε ένα ταξίδι κάτω από τη λωρίδα μνήμης.

Ώρα επαναφοράς

Τα αντικείμενα και οι λειτουργίες και όλα όσα γνωρίζουμε για τους υπολογιστές, αποθηκεύονται ουσιαστικά σε bits και byte στον υπολογιστή.

Σε γλώσσες όπως η Java και η C, πρέπει να δηλώσετε ρητά το μέγεθος ενός πίνακα εκ των προτέρων.

Κράτα, αλλά η Ruby δεν το κάνει αυτό;

Στο Ruby, χρησιμοποιούμε Arrayγια τις γραμμικές δομές δεδομένων μας. Μπορούμε να προσθέσουμε φαινομενικά άπειρα πράγματα σε μια συστοιχία Ruby και δεν θα είχε σημασία για εμάς.

Είναι υπέροχο, έτσι δεν είναι ;! Αυτό σημαίνει ότι οι συστοιχίες είναι απείρως μεγάλες, σωστά; Και ότι η Ruby είναι η ανώτερη γλώσσα; Τυχεροί μας!

Αλλά όχι τόσο γρήγορα. * σκάει τη φούσκα σας *

Δεν υπάρχουν πίνακες απεριόριστου μεγέθους. αυτό που βλέπετε στο Ruby είναι αυτό που ονομάζουμε Dynamic Array και συνοδεύεται από κόστος.

Για να κατανοήσουμε τι είναι οι δυναμικές συστοιχίες, ας ρίξουμε μια πρώτη ματιά στον τρόπο με τον οποίο οι πίνακες αντιπροσωπεύονται στη μνήμη. Δεδομένου ότι το MRI Ruby (Matz 'Ruby Interpreter) μεταγλωττίζεται στον κώδικα C, θα δούμε πώς παρουσιάζονται οι πίνακες στο C.

Το C-ing πιστεύει

Θα βυθίσουμε λίγο κώδικα C για να μας βοηθήσουμε λίγο καλύτερα… :)

Σε γλώσσες χαμηλότερου επιπέδου όπως το C, πρέπει να ασχοληθείτε μόνοι σας με δείκτες και κατανομή μνήμης. Ακόμα κι αν δεν έχετε αντιμετωπίσει το C στο παρελθόν (d isclaimer - ούτε το I ), μπορεί να έχετε το C-een ένα από τα πιο γνωστά παραδείγματα παρακάτω:

Ας αναλύσουμε αυτό το κομμάτι κώδικα:

  • malloc δεν έχει κανένα μαγικό νόημα πίσω του, σημαίνει κυριολεκτικά memory allocation
  • malloc επιστρέφει ένα δείκτη
  • malloc παίρνει ένα όρισμα, ποιο είναι το μέγεθος της μνήμης που θέλετε να εκχωρήσει το πρόγραμμα για εσάς.
  • 100 * sizeof(int) λέει στο πρόγραμμα ότι θέλουμε να αποθηκεύσουμε 100 ακέραιους αριθμούς, οπότε διαθέστε μας 100 * το μέγεθος αυτού που θα καταλαμβάνει κάθε ακέραιος.
  • ptrΤο / pointer αποθηκεύει αναφορά στη διεύθυνση μνήμης.

Ο Timmy αποθηκεύει αποσκευές!

Εάν το παραπάνω παράδειγμα δεν είχε νόημα, δοκιμάστε αυτήν την αναλογία. Σκεφτείτε την κατανομή μνήμης ως θυρωρείο αποσκευών. Δουλεύει κάπως έτσι:

  • Ο Timmy πηγαίνει στον πάγκο, λέει στον θυρωρείο ότι έχει 2 αποσκευές, σχετικά με αυτό το μεγάλο, και ότι θα ήθελε να τα αποθηκεύσει στην αποθήκη.
  • Ο θυρωρός ρίχνει μια ματιά στην αποθήκη και πηγαίνει «Ναι, έχουμε λίγο χώρο στην καθορισμένη B4περιοχή και θα διαθέσουμε αυτόν τον χώρο για να αποθηκεύσουμε τις αποσκευές σας».
  • Δίνουν στον Timmy μια κάρτα παραλαβής με την καθορισμένη περιοχή, B4στην περίπτωσή μας.
  • Ο Timmy είναι χαρούμενος, γυρίζει κάνοντας οτιδήποτε και όταν θέλει να πάρει τις αποσκευές του, επιστρέφει στον πάγκο και τους δείχνει την κάρτα παραλαβής του . « Έχεις τις αποσκευές μου; "

Στο παράδειγμά μας, οι αποσκευές του Timmy είναι τα δεδομένα , η κάρτα παραλαβής είναι ο δείκτης (δηλώνει πού αποθηκεύεται η τσάντα του Timmy). Το μέρος στο οποίο αποθηκεύει ο θυρωρός το Timmy είναι το μπλοκ μνήμης και ο μετρητής είναι το πρόγραμμα .

Εμφανίζοντας τον μετρητή ( το πρόγραμμα ) την κάρτα του Timmy ( διεύθυνση δείκτη / μνήμης ), ο Timmy μπορεί να ανακτήσει τις αποσκευές του ( δεδομένα ). Δώρο? Επειδή γνωρίζουν ακριβώς πού αποθηκεύεται η τσάντα του Timmy - B4αυτό σημαίνει ότι μπορούν να ανακτήσουν όλες τις αποσκευές του Timmy σχετικά γρήγορα!

Επίσης, αναρωτηθήκατε ποτέ γιατί έχετε πρόσβαση σε στοιχεία σε συστοιχία με ευρετήριο , όπως έτσι;

Αυτό συμβαίνει επειδή ο πίνακας διατηρεί τις αναφορές στο μπλοκ μνήμης και το ευρετήριο το λέει ότι το όφσετ .

Μια αναλογία για αυτό είναι εάν σας ζητήσω να αναζητήσετε τον Timmy σε μια ουρά 20 ατόμων, λογικά θα πρέπει να ρωτήσετε καθένα από αυτά αν ήταν Timmy. Αλλά, αν σας έλεγα ότι ο Timmy είναι ο 6ος ( ευρετήριο ) από το πρώτο άτομο ( ο αρχικός δείκτης σας ), ξέρετε ακριβώς πού να κοιτάξετε.

Η ανάκτηση στοιχείων σε πίνακες είναι γρήγορη ακριβώς εξαιτίας αυτού - το πρόγραμμα δεν χρειάζεται να κοιτάξει και τα 100 στοιχεία για να βρει αυτό που ψάχνετε. Εάν έχετε το ευρετήριο, πρέπει απλώς να προσθέσετε το όφσετ στην αρχική διεύθυνση μνήμης και το droid που ψάχνατε θα είναι εκεί!

Τι είναι οι δυναμικές συστοιχίες τότε;

Έτσι σας έχω πει λίγα πράγματα για το πώς οι συστοιχίες αντιπροσωπεύονται στη μνήμη, αλλά τώρα ήρθε η ώρα να μιλήσετε για ορισμένα μειονεκτήματα.

Θυμάστε πώς πρέπει να δηλώσετε ρητά το μέγεθος της μνήμης που χρειάζεστε; Αυτό σημαίνει ότι ο πίνακας θα βρει ένα σημείο που θα ταιριάζει ακριβώς στο μέγεθός σας. Δεν υπάρχει καμία εγγύηση ότι θα μπορεί να χωρέσει περισσότερο από αυτό που έχετε (επειδή το μπλοκ μνήμης ακριβώς πίσω από αυτό μπορεί να καταληφθεί).

Επιστροφή στην αναλογία αποσκευών μας: σκεφτείτε το σαν ο Timmy να αποθηκεύσει 2 τεμάχια αποσκευών και B4να αποθηκεύσει ακριβώς 2 κομμάτια αποσκευών, οπότε το κατανέμει στον Timmy. Τώρα για κάποιο λόγο ο Timmy θέλει να αποθηκεύσει ένα άλλο κομμάτι αποσκευών, αλλά B4δεν μπορεί να αποθηκεύσει 3 κομμάτια, μόνο 2, οπότε τι κάνουν;

Παίρνουν όλες τις υπάρχουσες αποσκευές του, μετακινούνται σε ένα νέο σημείο που μπορεί να χωρέσει περισσότερα από 3 τεμάχια και στη συνέχεια αποθηκεύουν όλα μαζί.

Αυτή είναι μια δαπανηρή λειτουργία αλλά είναι ακριβώς πώς λειτουργεί και η μνήμη!

Στο Ruby, δεν χρειάζεται να δηλώσετε ένα συγκεκριμένο μέγεθος πριν από το χέρι , αλλά αυτό συμβαίνει επειδή το Ruby το χειρίζεται για εσάς αυτόματα μέσω δυναμικών συστοιχιών.

Αυτό που κάνει μια δυναμική συστοιχία είναι ότι εάν ο πίνακας πλησιάζει την πλήρη χωρητικότητά του, θα δηλώσει αυτόματα έναν νέο, μεγαλύτερο πίνακα και θα μετακινήσει όλα τα υπάρχοντα στοιχεία σε αυτόν και στη συνέχεια ο παλιός πίνακας συλλέγεται σκουπίδια. Πόσο μεγαλύτερο; Ο αυξητικός παράγοντας είναι συνήθως 2. διπλασιάστε το μέγεθος του τρέχοντος πίνακα.

Στην πραγματικότητα, μην πάρετε τα λόγια μου για αυτό .

Το Ruby διαθέτει μια μονάδα ObjectSpace που μας επιτρέπει να αλληλεπιδρούμε με τα τρέχοντα αντικείμενα που ζουν στη μνήμη. Μπορούμε να χρησιμοποιήσουμε αυτήν την ενότητα για να ρίξουμε μια ματιά στη χρήση μνήμης του δυναμικού μας πίνακα - ακούγεται ακριβώς όπως θέλουμε!

Έχω γράψει ένα μικρό σενάριο Ruby που υπολογίζει τον παράγοντα ανάπτυξης του δυναμικού πίνακα. Μη διστάσετε να ρίξετε μια ματιά εδώ, και αν το κάνετε, μπορείτε να δείτε ότι οι συστοιχίες Ruby έχουν αυξητικό παράγοντα 1,5x (δηλαδή, δημιουργούν έναν πίνακα που είναι 50% μεγαλύτερος σε κάθε αντίγραφο).

Ξέρω τι είναι οι πίνακες, τι είναι οι συνδεδεμένες λίστες;

Λάβετε υπόψη ότι αν και οι πίνακες και οι συνδεδεμένες λίστες θεωρούνται και οι δύο γραμμικές δομές δεδομένων, έχουν μια μεγάλη διαφορά μεταξύ τους.

Τα στοιχεία σε έναν πίνακα αποθηκεύονται κυριολεκτικά το ένα δίπλα στο άλλο στη μνήμη (έτσι μπορούμε να έχουμε ευρετήριο για γρήγορες αναζητήσεις). Όμως, οι κόμβοι σε συνδεδεμένες λίστες δεν έχουν τέτοιο περιορισμό (γι 'αυτό δεν υπάρχει αναζήτηση ευρετηρίου για συνδεδεμένες λίστες) - κάθε στοιχείο μπορεί να αποθηκευτεί οπουδήποτε στο μπλοκ μνήμης.

Είναι σχεδόν σαν ο Timmy να προσπαθεί να αποθηκεύσει 5 αποσκευές και ο θυρωρός δεν έχει χώρο και αποφασίζει να τα αφήσει παντού. Ακούγεται οργανωμένη;

Επίσης, εάν αποθηκεύονται σε διαφορετικά μέρη, πώς ξέρετε ποιες τσάντες είναι οι Timmy; Συμβουλή: Απλώς παρακολουθήστε τον επόμενο κόμβο / τσάντα! Στην περίπτωσή μας, ο θυρωρός τους κρατά ξεχωριστά, αλλά με μια ετικέτα σε καθένα από αυτά που δείχνει στην επόμενη τσάντα.

Ένας κόμβος σε μια συνδεδεμένη λίστα αποτελείται από δύο μέρη - το τμήμα δεδομένων και έναν δείκτη στον επόμενο κόμβο. Με αυτόν τον τρόπο είναι σε θέση να διατηρήσουν το linearκομμάτι του - εξακολουθούν να έχουν την έννοια της τάξης, απλά δεν χρειάζεται να αποθηκευτούν στη σειρά κυριολεκτικά!

node = [ data | pointer ]

Για παράδειγμα, με το ακόλουθο παράδειγμα αποθηκευμένο στη μνήμη:

[C | D] [A | B] [B | C] [D | nil]

Αυτά τα κομμάτια μοιάζουν ότι είναι εκτός λειτουργίας - αλλά αν σας είπα ότι το πρώτο στοιχείο είναι A, θα μπορούσατε να μου πείτε την ακριβή σειρά της λίστας:

list = [A -> B -> C ->Δ -> μηδέν]

Υπάρχουν πολλά ενδιαφέροντα πράγματα που μπορείτε να κάνετε με συνδεδεμένες λίστες για τις οποίες δεν πρόκειται να βυθίσω εδώ (επίσης πολλά στο Big O για τα οποία δεν μίλησα). Αλλά υπάρχουν ήδη πολλά καλά άρθρα εκεί έξω σχετικά με τις δομές δεδομένων. Εάν το καταφέρατε εδώ, σας προτείνω να διαβάσετε από το blogpost του Ali εδώ.

ευχαριστώ, επόμενη: μια εισαγωγή στις συνδεδεμένες λίστες

Σε αυτήν την ανάρτηση, πρόκειται να μιλήσουμε για τη δομή δεδομένων της συνδεδεμένης λίστας στη γλώσσα "ευχαριστώ, επόμενη" από ... dev.to

Μπορείτε επίσης να διαβάσετε περισσότερα για τη Λίστα / Μειονεκτήματα στο Wiki εδώ.

Κλείσιμο σημείωσης

Αρχικά έγραψα αυτό το άρθρο για ένα ελαφρώς διαφορετικό θέμα - [Elixir | Γιατί οι συνδεδεμένες λίστες;], αλλά βρήκαν ότι χρειάστηκε πολύς χρόνος για να εξηγήσουν πώς λειτουργούν οι συστοιχίες προτού μπορέσω να εξηγήσω την εξερεύνηση γιατί το Elixir χρησιμοποιεί συνδεδεμένες λίστες. Γι 'αυτό τα χωρίζω σε δύο άρθρα.

Σε αυτό το άρθρο, μιλάω γιατί οι λειτουργικές γλώσσες χρησιμοποιούν συνδεδεμένες λίστες ως γραμμική δομή δεδομένων. Ελέγξτε το!

[Ελιξίριο | Γιατί οι συνδεδεμένες λίστες; ]

Πάντα πίστευα ότι οι δομές δεδομένων είναι δροσερές, αλλά ξέρετε τι είναι πιο δροσερό; Βλέποντάς τα στη φύση! Καθώς περνάτε… dev.to

Πηγές

  1. //medium.com/@rebo_dood/ruby-has-a-memory-problem-part-1-7887bbacc579 - Εδώ έμαθα για πρόσθετες ObjectSpaceμεθόδους, απαιτώντας το

Αρχικά δημοσιεύτηκε στο dev.to