Αλγόριθμοι σε Javascript - Επεξήγηση δυαδικής αναζήτησης

Αν θέλετε να αποκτήσετε νέες δεξιότητες επίλυσης προβλημάτων και να βελτιώσετε τις γνώσεις σας στην Επιστήμη των Υπολογιστών, μην ψάχνετε πέρα ​​από το δωρεάν πρόγραμμα διάρκειας μίας ώρας της Scrimba, τον Οδηγό για Αλγόριθμους του Εργαζόμενου Προγραμματιστή. Σχεδιάστηκε για όσους δεν έχουν υπόβαθρο στην Επιστήμη των Υπολογιστών και πιστεύουν ότι θα ωφεληθούν από την εκμάθηση της σκέψης αλγοριθμικά.

Τι κάνει το μάθημα;

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

Θα μάθετε:

  • Δυαδική αναζήτηση
  • Μεγάλη σημειογραφία
  • Εντυπωσιακός κωδικός
  • Αναδρομή
  • Επανάληψη ουράς
  • Διαχωρισμός συστοιχιών
  • Προβολή σειράς
  • Χώρισμα

Κάθε αλγόριθμος διδάσκεται σε τρία στάδια:

  • Walkthrough: Ο Jonathan παρουσιάζει τον αλγόριθμο εννοιολογικά.
  • Εφαρμογή: Βρώμουμε τα χέρια μας δημιουργώντας τις δικές μας εκδόσεις του αλγορίθμου.
  • Λύση: Ο Jonathan μας δείχνει την εφαρμογή του για σύγκριση.

Προαπαιτούμενα

Θα αξιοποιήσετε στο έπακρο αυτό το μάθημα εάν έχετε καλή κατανόηση του Javascript και ιδανικά εργάζεστε ήδη ως προγραμματιστής ή είστε απόφοιτοι του Bootcamp.

Εάν δεν είστε ακόμα εκεί, δείτε τα υπέροχα δωρεάν εκπαιδευτικά προγράμματα του Scrimba Εισαγωγή στη JavaScript και Εισαγωγή στο ES6 +.

Εισαγωγή στον εκπαιδευτή

Ο Jonathan Lee Martin είναι προγραμματιστής λογισμικού, εκπαιδευτικός ιστού, ομιλητής και συγγραφέας. Βοηθά άλλους προγραμματιστές να επιτύχουν τους επαγγελματικούς και προσωπικούς τους στόχους μέσω γραφής, ομιλίας, συναρπαστικών Bootcamps, εργαστηρίων και διαδικτυακών σεμιναρίων.

Με πελάτες, συμπεριλαμβανομένων εταιρειών όπως η NASA και η HP, είναι ακριβώς το άτομο που θα σας οδηγήσει στο ταξίδι μάθησης Ας ξεκινήσουμε λοιπόν!

Δυαδική αναζήτηση

Γράφημα των αναζητήσεων Sweeper vs Splitter.

Κάντε κλικ στην εικόνα για πρόσβαση στο μάθημα.

Στο πρώτο cast, ο Jonathan εισάγει τις έννοιες της σημειογραφίας Big-O και της δυαδικής αναζήτησης , τον αλγόριθμο με τον οποίο θα εργαζόμαστε.

Η σημειογραφία Big-O είναι ένα μέσο για την περιγραφή της χειρότερης απόδοσης ενός αλγορίθμου. Το Big O του O (n) λέει ότι εάν ένας πίνακας έχει μήκος n στοιχείων, ο χρόνος εκτέλεσης θα είναι ανάλογος με το n. Με άλλα λόγια, μια σειρά από επτά καταχωρήσεις θα απαιτήσει 7 αναζητήσεις στη χειρότερη περίπτωση, όπως και μια σειρά 7 εκατομμυρίων εγγραφών θα λάβει 7 εκατομμύρια εγγραφές στη χειρότερη περίπτωση. Μπορούμε επίσης να πούμε ότι ο χρόνος εκτέλεσης αυτού του αλγορίθμου είναι γραμμικός, όπως φαίνεται στο παραπάνω γράφημα.

Η δυαδική αναζήτηση είναι μία από τις πολλές στρατηγικές για την απάντηση στην ερώτηση "Πού εμφανίζεται αυτό το στοιχείο σε μια λίστα;"

Κατά την απάντηση στην ερώτηση, υπάρχουν δύο βασικές προσεγγίσεις:

  • Sweeper : Έλεγχος σε κάθε στοιχείο της λίστας μέχρι να βρεθεί το σωστό στοιχείο.
  • Splitter / Binary Search : Διαχωρισμός της λίστας στη μέση, έλεγχος αν έχετε πάει πάρα πολύ μακριά ή όχι αρκετά για να εντοπίσετε το αντικείμενο, ψάχνοντας είτε στη δεξιά είτε στην αριστερή πλευρά αντίστοιχα και επαναλαμβάνοντας έως ότου εντοπιστεί το στοιχείο.

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

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

Ενώ η προσέγγιση σάρωσης έχει γραμμικό χρόνο εκτέλεσης (βλέπε γράφημα παραπάνω) και Big O of O (n), η προσέγγιση splitter έχει υπο γραμμικό χρόνο εκτέλεσης και Big O of O (log n).

Επιτακτικός

Στο πρώτο cast της πρόκλησης, ο Jonathan μας ενθαρρύνει να βρώσουμε τα χέρια μας με την εφαρμογή δυαδικής αναζήτησης σε παραδοσιακό στιλ, δηλαδή με ένα Big O of (n), χρησιμοποιώντας μια σταθερή ποσότητα μνήμης και βρόχους.

Ο Jonathan μας παρέχει μια δοκιμαστική σουίτα που μπορούμε να χρησιμοποιήσουμε για να διασφαλίσουμε ότι η λύση μας είναι επιτυχής και μας ενθαρρύνει να δοκιμάσουμε οι ίδιοι την πρόκληση πριν ελέγξουμε την εφαρμογή του. Δεν υπάρχουν spoilers εδώ, οπότε κατευθυνθείτε στο cast για να το δοκιμάσετε.

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

Αναδρομή

Σε αυτό το cast, εξετάζουμε τη βελτίωση της δυαδικής αναζήτησης με την εφαρμογή μιας νέας έκδοσης με μερικούς περιορισμούς. Ενώ η λύση μας πρέπει να έχει ακόμα ένα μεγάλο O (n), δεν θα πρέπει να χρησιμοποιεί βρόχους και πρέπει να χρησιμοποιεί αναδρομή. Όλες οι μεταβλητές πρέπει να αρχικοποιηθούν με τον constτελεστή, ώστε να μην μπορούν να μεταλλαχθούν.

Ο Jonanthan μας ξεκινά με μια σκελετική έκδοση της λύσης και στη συνέχεια μας ενθαρρύνει να δοκιμάσουμε τη δική μας πρόκληση:

let binarySearchWithRecursion = (array, element, compare = defaultCompare) => { return -1; }; export default binarySearchWithRecursion; 

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

Επανάληψη ουράς

Η πρόκληση για το επόμενο cast είναι να βελτιώσουμε την προηγούμενη εφαρμογή μας μειώνοντας την επικάλυψη.

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

Διαχωρισμός συστοιχιών

If you completed the previous challenge, you may have felt that we're still passing a lot of extra information into our binary search via recursion. This cast looks at a way of cleaning that up called array splitting.

We can think of array splitting in terms of our phone book example from earlier - whenever we decide that half the phone book is irrelevant, we just tear it off and throw it away. Similarly, our next solution should disregard any parts of the array which don't include our desired entry.

To help us achieve this, Jonathan starts us off with some skeleton code:

let binarySearchWithArraySplitting = ( array, element, compare = defaultCompare ) => { return -1; }; 

Then, as usual, he gives us free rein to try to the solution for ourselves before walking us through his own implementation.

Although this is an elegant method of binary search, because it involves making a copy of part of the array, it no longer has a Big O of O(n) and has a higher memory usage and slower run time. Continue with the course to find out whether there is a way to regain a higher performance with a similar code solution...

Array View

In this cast, we look for ways of merging the higher performance of our previous solutions with the elegance of array splitting. To do this, we create an array-like object that responds to the same methods as an array. We'll then inject this object in place of the original array.

Jonathan gets us started by initializing a function ArrayView which returns an object that expects three arguments: array, start and end. When invoked, ArrayView should return an object with four methods, length, toArray, slice and get.

export let ArrayView = ( array, start = 0, end = array.length, ) => ({ length: end - start, toArray: () => array.slice(start, end), slice: () => , get: () => , }); let binarySearchWithArrayView = (array, ...args) => binarySearchWithArraySplitting(ArrayView(array), ...args) 

Our challenge is to implement the slice and get methods of ArrayView without making a copy of the original array. Click through to try it out and then view Jonathan's walkthrough.

Although this solution produces better, more readable code, it is longer than some of our previous solutions. Continue with the course to find out if we can retain the benefits of ArrayView while lifting even more of the logic out of binary search code...

Array Partition

In the final challenge cast of the course, Jonathan gives us a goal of extracting some of the cryptic bounce logic in our previous version into a data structure.

For this, we need a simple data structure which returns the middle, left or right part of an array. To start us off, Jonathan sets up a function ArrayPartition:

export let ArrayPartition = (array, pivot) => ({ left: () => array.slice(0, pivot), middle: () => array.get(pivot), right: () => array.slice(pivot + 1, array.length), }); 

Next, Jonathan sets up a new version of binary search called binarySearchWithPartition, which has a starting signature the same as binarySearchWithArraySplitting:

let binarySearchWithPartition = (array, element, compare = defaultCompare) => { if (array.length === 0) { return -1; } const middle = Math.floor(array.length / 2); const comparison = compare(element, array.get(middle)); if (comparison === 0) { return middle; } //bounce logic const [left, right] = comparison === -1 ? [0, middle - 1] : [middle + 1, array.length]; //end of bounce logic const subIndex = binarySearchWithArraySplitting( array.slice(left, right), element, compare ); return subIndex === -1 ? -1 : left + subIndex; }; let binarySearchWithPartitionAndView = (array, ...args) => binarySearchWithPartition(ArrayView(array), ...args); 

Our challenge now is to rewrite binarySearchWithPartition with none of the bounce logic highlighted above, instead of creating an array partition and making calls to its left, middle and right methods.

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

Τύλιξε

Το έχετε φτάσει στο τέλος του μαθήματος - καταπληκτική δουλειά! Έχουμε καλύψει αρκετές προσεγγίσεις στη δυαδική αναζήτηση, όλες με τα δικά τους πλεονεκτήματα και μειονεκτήματα, και έχουμε δημιουργήσει κάποια μεγάλη μυϊκή μνήμη για αποτελεσματική εργασία με αλγόριθμους.

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

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

Καλή κωδικοποίηση :)