Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Γραμμική Αναζήτηση]
[Patrick Schmid, Πανεπιστήμιο Χάρβαρντ]
[This Is CS50.] [CS50.TV]
Αναζήτηση είναι κάτι που ίσως κάνει πιο συχνά από ό, τι νομίζετε.
Προφανώς, κάθε φορά που ανοίγετε ένα πρόγραμμα περιήγησης στο Web
και την αναζήτηση για μια ιστοσελίδα -
ή αναζήτηση για τους φίλους σας στις αγαπημένες σας τοποθεσίες κοινωνικής δικτύωσης -
ψάχνετε.
Αλλά αυτό είναι μόνο ένα μικρό μέρος του αναζήτηση που κάνετε σε καθημερινή βάση.
Όταν θέλετε να διαπιστώσετε ότι ένα μπλε πουκάμισο στην ντουλάπα,
ή ότι τέλεια κόκκινη μπλούζα για την περίσταση,
ψάχνετε.
Όταν πηγαίνετε σε ένα κατάστημα που έχετε ποτέ δεν ήταν στο παρελθόν,
και ψάχνετε για το μπρόκολο στο διάδρομο προϊόντα
ψάχνετε.
Τι μπορεί να έχετε αρχίσει να παρατηρήσετε
είναι ότι ανάλογα με το τι ψάχνετε
ή πώς οργανώνονται τα στοιχεία, όταν ψάχνετε για τους
έχει επιπτώσεις για το πώς να κάνετε αναζήτηση.
Για παράδειγμα, αν σας πουκάμισα κρέμονται στην ντουλάπα,
μπορείτε πιθανώς να πάρει ακριβώς έξω χωρίς πολύ ψάξιμο.
Αν είστε υποθέτοντας έχετε να περπατήσετε κάτω από το διάδρομο
για να πάρει το μπρόκολο, ίσως πρέπει να εξετάσουμε όλα τα άλλα λαχανικά
προτού να βρείτε το μπρόκολο.
Γραμμική αναζήτησης είναι ένα παράδειγμα μίας τέτοιας μεθόδου αναζήτηση - ή αλγόριθμο.
Όπως υποδηλώνει το όνομα,
η μέθοδος αυτή αναζητά για ένα στοιχείο με ένα γραμμικό τρόπο, το ένα μετά το άλλο.
Έτσι, όταν ψάχνετε τα αποτελέσματα από την αγαπημένη σας μηχανή αναζήτησης
και μπορείτε να διαβάσετε τον κατάλογο των αποτελεσμάτων,
χρησιμοποιείτε γραμμική αναζήτηση.
Εντάξει. Ας δούμε ένα παράδειγμα.
Πούμε ότι έχουμε μια λίστα αριθμών - 2, 4, 0, 5, 3, 7, 8, και 1 -
και ψάχνουμε για το 0 Αριθμός.
Προφανώς, μπορείτε απλά να δείτε ότι το 0 είναι στην τρίτη θέση.
Όμως, ένα πρόγραμμα ηλεκτρονικού υπολογιστή δεν είναι τόσο τυχεροί.
Μπορεί μόνο «βλέπει» έναν αριθμό κάθε φορά.
Έτσι, ξεκινώντας από την αρχή της λίστας,
το μόνο "βλέπει" η 2.
Το πρόγραμμα ελέγχει στη συνέχεια - είναι 2 ίση με 0;
Προφανώς όχι. Έτσι πηγαίνει στο επόμενο αριθμό, 4.
Μήπως 4 ίσες 0; Όχι.
Το επόμενο, 0. Αχ! Μηδέν είναι ίση με 0.
Εκεί το έχετε! Είναι στην τρίτη θέση.
Εντάξει. Ας ρίξουμε μια ματιά σε κάποια ψευδοκώδικα.
Είναι μόνο μια-δυο γραμμές καιρό, αλλά ας ρίξουμε μια ματιά σε αυτό μία γραμμή κάθε φορά.
Κατ 'αρχάς, ας ορίσουμε τη λειτουργία - και θα πάμε να το ονομάσουμε γραμμική αναζήτηση -
και παίρνει δύο ορίσματα - κλειδί και πίνακα.
Το κλειδί είναι ότι η τιμή που ψάχνουμε,
έτσι στο προηγούμενο παράδειγμα, αυτό ήταν το μηδέν.
Ένας πίνακας είναι μια λίστα αριθμών
η οποία έχει όλες τις αξίες που θα πάμε για την αναζήτηση.
Έτσι, αυτό που θέλουμε να κάνουμε είναι να θέλουμε να δούμε -
από όλες τις θέσεις, έτσι ώστε ξεκινώντας από την αρχή κιόλας της συστοιχίας
til το τέλος της συστοιχίας - έτσι ώστε το μήκος της συστοιχίας -
εξετάσουμε κάθε θέση και να ελέγχει κάθε μία.
Έτσι, αυτό είναι ότι "για" βρόχο κάνει.
Και σε κάθε θέση, θα πάμε να πούμε
"Είναι η αξία εκείνη τρέχουσα θέση ίση με το κλειδί που ψάχνουμε;"
Έτσι - στο προηγούμενο παράδειγμα και πάλι, βασικά ήταν 0 -
έτσι λέμε "Είναι η σειρά στη θέση i ισούται με μηδέν;"
Αν είναι, θα πάμε να επιστρέψει το «i», διότι αυτή είναι η τρέχουσα θέση είμαστε σε.
Έτσι, στο προηγούμενο παράδειγμα,
αυτή ήταν η τρίτη θέση.
Αν έχουμε περάσει από ολόκληρο το φάσμα
και δεν έχουμε βρει τίποτα -
οπότε ας πούμε ότι έψαχναν για τον αριθμό 500
τα οποία σαφώς δεν ήταν σε αυτό το παράδειγμα -
πρέπει να επιστρέψει κάτι,
και θα πάμε να επιστρέψει -1.
Και είμαστε μόλις επιστρέφουν -1, επειδή αυτό είναι μια θέση
που δεν υπάρχει στη συστοιχία.
Και έτσι αυτό σημαίνει ότι, όταν το πάρει πίσω από μια συνάρτηση
λέει "Χμμ, εντάξει. Υποθέτω ότι δεν βρήκα τίποτα.
Έτσι ώστε ποτέ 500 ήταν εκεί. "
Το θετικό σχετικά με γραμμική αναζήτηση είναι ότι
αυτό θα λειτουργήσει σε οποιοδήποτε κατάλογο των στοιχείων,
ανεξάρτητα από τον τρόπο διέταξε τα στοιχεία.
Δεν έχει σημασία πού το μπρόκολο είναι στο διάδρομο προϊόντων.
Όσο περπατάτε κάτω από το διάδρομο από την αρχή μέχρι το τέλος,
είστε αναγκασμένοι να το βρείτε,
υποθέτοντας ότι το κατάστημα δεν έχει τρέξει από το μπρόκολο, φυσικά.
Αλλά μεγαλύτερη δύναμη του είναι επίσης η μεγαλύτερη αδυναμία της.
Ας πούμε ότι έχετε μια λίστα από διακόσιες αριθμούς
που είναι ταξινομημένο 1 έως 200.
Αν ψάχνετε για τον αριθμό 198,
θα πρέπει να αναζητήσετε σχεδόν ολόκληρη τη λίστα των αριθμών
πριν να βρείτε αυτό που ψάχνετε.
Πρέπει να υπάρχει ένας καλύτερος τρόπος!
Να είστε βέβαιοι ότι υπάρχει.
Αλλά, αυτό είναι ένα άλλο θέμα για το βίντεο.
Επίσης, μην φθείρετε!
Ακριβώς επειδή γραμμική αναζήτηση δεν είναι η καλύτερη λύση σε όλες τις περιπτώσεις,
αυτό δεν σημαίνει ότι δεν έρχεται σε πρακτικό.
Διαφορετικά, πώς θα βρείτε το μπρόκολο στο διάδρομο προϊόντα;
Το όνομά μου είναι ο Patrick Schmid, και αυτό είναι CS50.
[CS50.TV]