Μάθετε τις βασικές αρχές κωδικοποίησης: τις κύριες διαφορές μεταξύ συνόλων και συστοιχιών

Μια ερώτηση που έχω πολλά από τους μαθητές μου CS στο The Forge είναι γιατί χρησιμοποιώ συχνά σετ αντί για απλούς παλιούς πίνακες σε προβλήματα συνέντευξης.

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

Εάν είστε οπτικός μαθητής και προτιμάτε μια εξήγηση βίντεο, ακολουθεί ένα βίντεο 3 λεπτών που εξηγεί την απάντηση (αν και σε λιγότερο βάθος).

Οι πίνακες ήταν μια από τις πρώτες δομές δεδομένων που έμαθα πώς να χρησιμοποιώ.

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

Μόλις αργότερα στην καριέρα μου στο λογισμικό πήγα με τον περίεργο, αλλά μαγικό, ξάδελφο του πίνακα:

Το σετ.

Τα σετ είναι σαν συστοιχίες… εκτός αν δεν είναι.

Ας θυμηθούμε γρήγορα πώς λειτουργεί ένας πίνακας

Πίνακες:

  • Παραγγέλλονται
  • Έχετε δείκτες από το 0
  • Μπορεί να περιέχει διπλά στοιχεία
  • Έχετε χρόνο αναζήτησης O (n) όταν αναζητάτε ένα στοιχείο

Ωστόσο, τα σετ συμπεριφέρονται λίγο διαφορετικά

Σκηνικά:

  • Είναι χωρίς ταξινόμηση (σε όλες σχεδόν τις γλώσσες)
  • Έχετε κατακερματισμένους δείκτες
  • ΔΕΝ μπορεί να περιέχει διπλά στοιχεία
  • Έχετε έναν χρόνο αναζήτησης O (1) κατά την αναζήτηση ενός στοιχείου

Ας ρίξουμε μια πιο εμπεριστατωμένη ματιά.

1. Σετ Εισαγωγή με κατακερματισμό

Τα στοιχεία σε ένα σύνολο αποθηκεύονται αρκετά διαφορετικά από αυτά ενός πίνακα.

Ο τρόπος με τον οποίο ένα σύνολο αποθηκεύει τα στοιχεία του είναι με το Hashing.

Ας υποθέσουμε ότι θέλετε να αποθηκεύσετε τον χαρακτήρα "A" σε ένα σύνολο και έναν πίνακα.

Ο πίνακας θα βρει απλώς το επόμενο διαθέσιμο ευρετήριο, εκτός αν ορίζεται διαφορετικά, και θα τοποθετεί το στοιχείο σε αυτό το ευρετήριο.

Ωστόσο, με κατακερματισμό, τα πράγματα φαίνονται λίγο διαφορετικά.

Πώς λειτουργεί το Hashing

Το κατακερματισμό είναι η πράξη λήψης εισόδου (x), παραμόρφωσης με συγκεκριμένη συνάρτηση κατακερματισμού (h) και λήψης τελικής εξόδου (y).

Βασικά h (x) = (y)

Φαίνεται λίγο συγκεχυμένο, έτσι;

Μην ανησυχείς! Αυτό πρέπει να ξεκαθαρίσει τα πράγματα.

Ένα εύκολο παράδειγμα μιας λειτουργίας κατακερματισμού (h) θα μπορούσε να είναι η προσθήκη του "asdf" στο τέλος της εισόδου σας (x).

Εάν το (x) είναι "A" και το προσάρτημα "asdf" είναι (h), η έξοδος (y) θα ήταν απλώς ως εξής:

"A" + "asdf" → "Aasdf"

Έτσι, το "Aasdf" θα ήταν το (y) μας.

Λοιπόν, πώς ένα σετ χρησιμοποιεί Hashing;

Ένα σύνολο χρησιμοποιεί κατακερματισμό για να αποφασίσει πού θα αποθηκεύσει την εισαγωγή σας (x).

Με λίγα λόγια, ένα σύνολο παίρνει την είσοδό σας, το κατακερματιστεί και το αποθηκεύει στο ευρετήριο που ταιριάζει με την κατακερματισμένη είσοδο, AKA την έξοδο (y).

Αυτός είναι ο λόγος για τον οποίο τα σύνολα δεν ταξινομούνται στις περισσότερες γλώσσες.

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

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

2. Τα σύνολα δεν μπορούν να περιέχουν διπλότυπα

Σωστά!

Ένα σύνολο μπορεί να περιέχει μόνο μοναδικά στοιχεία.

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

Γιατί το κάνει αυτό, ρωτάτε;

Λοιπόν, λόγω κατακερματισμού!

Εφόσον η λειτουργία κατακερματισμού μου (h) θα παραμείνει συνεπής καθώς εκτελείται το πρόγραμμά μου, η εισαγωγή του ίδιου (x) θα σας δίνει πάντα το ίδιο (y).

Αυτό σημαίνει ότι αν προσπαθούσα να εισαγάγω ένα δεύτερο "A", η λειτουργία κατακερματισμού μου θα έδινε την ίδια διεύθυνση με το πρώτο "A", και θα το αντικατέστησε απλώς!

Με έναν πίνακα, θα προσθέσει απλώς το δεύτερο "A" στον επόμενο διαθέσιμο ευρετήριο.

3. Τα σετ έχουν χρόνο αναζήτησης O (1)

Ας υποθέσουμε ότι έχετε έναν πίνακα στοιχείων n , όπου το n είναι ένας μεγάλος αριθμός και θέλετε να δείτε εάν υπήρχε το "A" σε αυτόν τον πίνακα.

Λοιπόν, το χειρότερο σενάριο, το "Α" δεν υπάρχει.

Και για να το καταλάβετε, θα πρέπει να επαναλαμβάνεται σε όλα τα n των στοιχείων αυτών!

Αυτό δίνει στον Array μια πολυπλοκότητα χρόνου του O (n) όταν πρόκειται για αναζήτηση ενός στοιχείου.

Μπορούμε να εξοικονομήσουμε πολύ χρόνο με ένα σετ

Αν θέλαμε να βρούμε εάν υπάρχει ένα στοιχείο στο σύνολο μας, το μόνο που πρέπει να κάνουμε είναι να κατακερματιστεί αυτό το στοιχείο και να ελέγξει το ευρετήριο!

Θυμηθείτε: Το ευρετήριο στο οποίο είναι αποθηκευμένο ένα στοιχείο συνδέεται με το ίδιο το στοιχείο.

Επομένως, εάν θέλαμε να δούμε αν υπήρχε ή όχι το "A" στο σετ μας, θα πρέπει απλώς να το κατακερματιστεί (+ "asdf") και να ελέγξουμε αυτό το ευρετήριο!

Δεδομένου ότι αυτή η διαδικασία θα έχει πάντα μια σταθερή λειτουργία, ανεξάρτητα από το πόσο μεγάλο είναι το σετ, έχει μια σταθερή χρονική πολυπλοκότητα.

Αυτό σημαίνει ότι ένα σετ έχει χρονική πολυπλοκότητα του O (1) όταν πρόκειται για αναζήτηση ενός στοιχείου… Ποια είναι μια τεράστια βελτίωση!

Μπορείτε να σκεφτείτε καταστάσεις όπου αυτό είναι χρήσιμο;

Εάν δεν μπορείτε, ρίξτε μια ματιά σε αυτήν την ερώτηση συνέντευξης Google όπου ένα σετ κάνει όλη τη διαφορά!

Ευχαριστώ για την ανάγνωση!

.ένα

PS - Για περισσότερες δομές δεδομένων και αλγορίθμους σεμινάρια και προετοιμασία συνεντεύξεων, ανατρέξτε στο www.TheForge.ca!

Βοηθάμε τους μαθητές και τους νέους απόφοιτους να προσέλθουν τη δουλειά των ονείρων τους στο λογισμικό!