1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Παίζει μουσική] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID Malan: Αυτό είναι CS50. 5 00:00:14,010 --> 00:00:18,090 Και αυτό είναι το ξεκίνημα και το end-- όπως literally-- σχεδόν το τέλος 6 00:00:18,090 --> 00:00:18,825 της εβδομάδας έξι. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Σκέφτηκα να μοιραστώ ένα λίγο ένα διασκεδαστικό γεγονός. 9 00:00:22,640 --> 00:00:25,370 Έχω τραβήξει αυτό επάνω από ένα που τα δεδομένα του παρελθόντος εξαμήνου. 10 00:00:25,370 --> 00:00:29,710 Ίσως να θυμάστε ότι σας ζητάμε για κάθε σύνολο φόρμα p αν έχετε παρακολουθήσει σε απευθείας σύνδεση 11 00:00:29,710 --> 00:00:31,580 ή αν έχετε παρακολουθήσει στο πρόσωπο. 12 00:00:31,580 --> 00:00:33,020 Και εδώ είναι τα δεδομένα. 13 00:00:33,020 --> 00:00:34,710 Μέχρι σήμερα ήταν πολύ προβλέψιμη. 14 00:00:34,710 --> 00:00:37,126 Αλλά θέλαμε να περάσετε λίγο του χρόνου μαζί σας, ωστόσο. 15 00:00:37,126 --> 00:00:40,599 Θα μπορούσε κάποιος ήθελε να εικάσουμε γιατί αυτό γράφημα είναι τόσο αλλοιωμένες, πάνω κάτω, πάνω κάτω, 16 00:00:40,599 --> 00:00:41,265 έτσι με συνέπεια; 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Τι κάνουν κάθε μία από τις κορυφές και γούρνες αντιπροσωπεύουν; 19 00:00:45,130 --> 00:00:46,005 >> ΚΟΙΝΟ: [δεν ακούγεται] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID Malan: Πράγματι. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Και πιο διασκεδαστικά, Θεός φυλάξοι, κρατάμε μια διάλεξη την Παρασκευή 24 00:00:55,480 --> 00:00:58,960 στην αρχή του εξαμήνου, αυτό είναι που βλέπουμε να συμβαίνουν. 25 00:00:58,960 --> 00:01:03,430 Έτσι, σήμερα, συμμετέχουμε σε ένα κομμάτι περισσότερα για τις δομές δεδομένων. 26 00:01:03,430 --> 00:01:06,660 Και για να σας δώσει περισσότερο από ένα στερεό νοητικό μοντέλο για τα προβλήματα σε πέντε, 27 00:01:06,660 --> 00:01:07,450 που είναι τώρα έξω. 28 00:01:07,450 --> 00:01:10,817 Ορθογραφικά λάθη, όπου, θα θα παραδώσει ένα αρχείο κειμένου περίπου 100.000 29 00:01:10,817 --> 00:01:12,650 συν αγγλικές λέξεις, και θα πάμε να έχουν 30 00:01:12,650 --> 00:01:17,770 για να καταλάβω πώς να τους φορτώσει έξυπνα στη μνήμη, στη μνήμη RAM, χρησιμοποιώντας κάποια δεδομένα 31 00:01:17,770 --> 00:01:19,330 δομή της επιλογής σας. 32 00:01:19,330 --> 00:01:22,470 >> Τώρα, μία τέτοια δομή δεδομένων θα μπορούσε να είναι, αλλά κατά πάσα πιθανότητα δεν θα πρέπει να είναι, 33 00:01:22,470 --> 00:01:25,630 η αρκετά απλοϊκή συνδεδεμένη λίστα, που παρουσιάσαμε την προηγούμενη φορά. 34 00:01:25,630 --> 00:01:29,220 Και μια συνδεδεμένη λίστα είχε τουλάχιστον ένα πλεονέκτημα σε σχέση με μία συστοιχία. 35 00:01:29,220 --> 00:01:32,096 Τι είναι ένα πλεονέκτημα μια συνδεδεμένη λίστα αναμφισβήτητα; 36 00:01:32,096 --> 00:01:32,950 >> ΚΟΙΝΟ: Εισαγωγή. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Malan: Εισαγωγή. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Τι εννοείτε με αυτό; 40 00:01:35,196 --> 00:01:37,872 >> ΚΟΙΝΟ: Οπουδήποτε μαζί ο κατάλογος [δεν ακούγεται]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Malan: Καλή. 42 00:01:38,770 --> 00:01:42,090 Έτσι, μπορείτε να εισαγάγετε ένα στοιχείο οπουδήποτε θέλετε στη μέση της λίστας 43 00:01:42,090 --> 00:01:45,490 χωρίς να χρειάζεται να ανακατέψει τίποτα, οποία καταλήξαμε, σε διαλογή μας 44 00:01:45,490 --> 00:01:47,630 συζητήσεις, δεν είναι απαραιτήτως ένα καλό πράγμα, 45 00:01:47,630 --> 00:01:51,200 γιατί χρειάζεται χρόνος για να προχωρήσουμε στην πραγματικότητα όλες εκείνες ανθρώπους αριστερά ή προς τα δεξιά. 46 00:01:51,200 --> 00:01:55,540 Και έτσι με μια συνδεδεμένη λίστα, μπορείτε να απλά διαθέσουν με malloc, ένας νέος κόμβος, 47 00:01:55,540 --> 00:01:58,385 και στη συνέχεια να ενημερώσετε ένα ζευγάρι των pointers-- δύο, τρεις εγχειρήσεις max-- 48 00:01:58,385 --> 00:02:01,480 και είμαστε σε θέση να σχισμή κάποιον σε οποιοδήποτε σημείο σε μια λίστα. 49 00:02:01,480 --> 00:02:03,550 >> Τι άλλο ήταν συμφέρουσα σχετικά με μια συνδεδεμένη λίστα; 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Ναι; 52 00:02:05,659 --> 00:02:06,534 >> ΚΟΙΝΟ: [δεν ακούγεται] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID Malan: Τέλεια. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Τέλεια. 57 00:02:11,090 --> 00:02:12,070 Είναι πραγματικά δυναμική. 58 00:02:12,070 --> 00:02:15,100 Και ότι δεν είστε διαπράττουν, εκ των προτέρων, σε κάποιο σταθερό μέγεθος 59 00:02:15,100 --> 00:02:18,750 κομμάτι της μνήμης, όπως θα έχετε σε με μια σειρά, ανοδικοί των οποίων 60 00:02:18,750 --> 00:02:22,455 είναι ότι μπορείτε να διαθέσετε κόμβους μόνο στις η ζήτηση έτσι χρησιμοποιώντας μόνο όσο χώρο 61 00:02:22,455 --> 00:02:23,330 όπως έχετε πραγματικά ανάγκη. 62 00:02:23,330 --> 00:02:26,830 Σε αντίθεση με μια σειρά, ίσως τυχαία κατανομή πολύ λίγο. 63 00:02:26,830 --> 00:02:28,871 Και τότε ακριβώς πρόκειται να είναι ένας πόνος στο λαιμό 64 00:02:28,871 --> 00:02:32,440 να ανακατανείμει ένα νέο μεγαλύτερο φάσμα, αντιγραφή τα πάντα πάνω, ελευθερώστε την παλιά σειρά, 65 00:02:32,440 --> 00:02:33,990 και στη συνέχεια να προχωρήσουμε για την επιχείρησή σας. 66 00:02:33,990 --> 00:02:37,479 Ή, ακόμη χειρότερα, θα μπορούσε να διαθέσει τρόπο περισσότερη μνήμη από ό, τι πραγματικά χρειάζεται, 67 00:02:37,479 --> 00:02:40,520 και έτσι θα πάμε να έχουν ένα πολύ αραιοκατοικημένες σειρά, να το πω έτσι. 68 00:02:40,520 --> 00:02:44,350 >> Έτσι, μια συνδεδεμένη λίστα σας δίνει αυτά πλεονεκτήματα του δυναμισμού και ευελιξίας 69 00:02:44,350 --> 00:02:46,080 με εισαγωγές και διαγραφές. 70 00:02:46,080 --> 00:02:48,000 Αλλά σίγουρα πρέπει να υπάρχει μια τιμή που καταβάλλεται. 71 00:02:48,000 --> 00:02:50,000 Στην πραγματικότητα, ένα από τα θέματα διερευνηθούν σε ένα κουίζ μηδέν 72 00:02:50,000 --> 00:02:52,430 Ήταν ένα ζευγάρι των εμπορικών-offs έχουμε δει μέχρι στιγμής. 73 00:02:52,430 --> 00:02:56,161 Έτσι τι είναι ένα τίμημα που καταβάλλεται ή μειονέκτημα συνδεδεμένη λίστα; 74 00:02:56,161 --> 00:02:56,660 Ναι. 75 00:02:56,660 --> 00:02:57,560 >> ΚΟΙΝΟ: Όχι τυχαία πρόσβαση. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Malan: Όχι τυχαία πρόσβαση. 77 00:02:58,809 --> 00:02:59,540 Αλλά ποιος νοιάζεται; 78 00:02:59,540 --> 00:03:01,546 Τυχαία πρόσβαση δεν ακούγεται συναρπαστικό. 79 00:03:01,546 --> 00:03:02,421 >> ΚΟΙΝΟ: [δεν ακούγεται] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Malan: Ακριβώς. 82 00:03:05,740 --> 00:03:07,580 Αν θέλετε να έχετε ένα ορισμένο algorithm-- 83 00:03:07,580 --> 00:03:10,170 και επιτρέψτε μου πραγματικά προτείνουν δυαδική αναζήτηση ειδικότερα, η οποία 84 00:03:10,170 --> 00:03:12,600 είναι μία έχουμε χρησιμοποιήσει αρκετά bit-- εάν δεν έχετε τυχαίας προσπέλασης, 85 00:03:12,600 --> 00:03:15,516 δεν μπορείτε να κάνετε αυτή την απλή αριθμητική εύρεσης σαν το μεσαίο στοιχείο 86 00:03:15,516 --> 00:03:16,530 και το άλμα δικαίωμα σε αυτό. 87 00:03:16,530 --> 00:03:20,239 Μπορείτε αντ 'αυτού πρέπει να ξεκινήσει κατά την πρώτη στοιχείου και γραμμικά αναζήτηση από την αριστερά 88 00:03:20,239 --> 00:03:22,780 προς τα δεξιά αν θέλετε να βρείτε η μεσαία ή οποιοδήποτε άλλο στοιχείο. 89 00:03:22,780 --> 00:03:24,410 >> ΚΟΙΝΟ: Χρειάζονται μάλλον περισσότερη μνήμη. 90 00:03:24,410 --> 00:03:25,040 >> DAVID Malan: Παίρνει περισσότερη μνήμη. 91 00:03:25,040 --> 00:03:27,464 Πού είναι ότι οι πρόσθετες το κόστος που προέρχεται από τη μνήμη; 92 00:03:27,464 --> 00:03:28,339 >> ΚΟΙΝΟ: [δεν ακούγεται] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Malan: Ακριβώς. 95 00:03:33,440 --> 00:03:35,679 Σε αυτήν την περίπτωση εδώ, είχαμε μια συνδεδεμένη λίστα για ακέραιους αριθμούς, 96 00:03:35,679 --> 00:03:37,470 και όμως είμαστε διπλασιασμό το ποσό της μνήμης 97 00:03:37,470 --> 00:03:39,680 χρειαζόμαστε επίσης από την αποθήκευση αυτών των δεικτών. 98 00:03:39,680 --> 00:03:42,090 Τώρα, λιγότερο από ένα big deal, όπως structs σας πάρουν τα μεγαλύτερα 99 00:03:42,090 --> 00:03:45,320 και είστε αποθήκευση και όχι στον αριθμό, αλλά ίσως ένας φοιτητής ή κάποιο άλλο αντικείμενο. 100 00:03:45,320 --> 00:03:46,880 Αλλά το σημείο σίγουρα παραμένει. 101 00:03:46,880 --> 00:03:49,421 Και έτσι ένας αριθμός ενεργειών σε συνδεδεμένες λίστες κλήθηκαν 102 00:03:49,421 --> 00:03:50,570 ήταν μεγάλη O της n-- γραμμική. 103 00:03:50,570 --> 00:03:54,730 Τα πράγματα όπως εισαγωγή ή αναζήτηση ή διαγραφή σε περίπτωση που ένα στοιχείο 104 00:03:54,730 --> 00:03:57,720 έτυχε να είναι στο τέλος του ο κατάλογος αν είναι ταξινομημένο ή όχι. 105 00:03:57,720 --> 00:04:01,167 >> Μερικές φορές μπορείτε να πάρετε τυχεροί και σε έτσι ώστε τα κατώτερα όρια για τις πράξεις αυτές 106 00:04:01,167 --> 00:04:04,250 θα μπορούσε επίσης να είναι σταθερό χρόνο αν είστε πάντα ψάχνει στο πρώτο στοιχείο, 107 00:04:04,250 --> 00:04:05,070 για παράδειγμα. 108 00:04:05,070 --> 00:04:09,360 Αλλά τελικά, υποσχεθήκαμε για να επιτευχθεί το άγιο δισκοπότηρο 109 00:04:09,360 --> 00:04:12,630 των δομών δεδομένων, ή κάποια προσέγγιση αυτών, 110 00:04:12,630 --> 00:04:14,290 μέσω της σταθερής του χρόνου. 111 00:04:14,290 --> 00:04:17,579 Μπορούμε να βρούμε στοιχεία ή να προσθέσετε στοιχεία ή να αφαιρέσετε στοιχεία από μια λίστα; 112 00:04:17,579 --> 00:04:19,059 Θα δούμε αρκετά σύντομα. 113 00:04:19,059 --> 00:04:21,100 Και αποδεικνύεται ότι ένα των μηχανισμών είμαστε 114 00:04:21,100 --> 00:04:23,464 πρόκειται να αρχίσετε να χρησιμοποιείτε σήμερα, ετήσια χρήση σε π έθεσε πέντε, 115 00:04:23,464 --> 00:04:24,630 είναι στην πραγματικότητα αρκετά εξοικειωμένοι. 116 00:04:24,630 --> 00:04:27,430 Για παράδειγμα, εάν πρόκειται για μια δέσμη βιβλία εξετάσεων, καθένα από τα οποία 117 00:04:27,430 --> 00:04:29,660 έχει ένας φοιτητής πρώτη το όνομα και το επίθετο σε αυτό, 118 00:04:29,660 --> 00:04:31,820 και εγώ τους πάρει από στο τέλος της εξέτασης, 119 00:04:31,820 --> 00:04:33,746 και είναι όλα όμορφα πολύ σε μια τυχαία σειρά, 120 00:04:33,746 --> 00:04:36,370 και θέλουμε να πάμε για τη διαλογή Αυτές οι εξετάσεις, έτσι ώστε κάποτε στοιβάζονταν 121 00:04:36,370 --> 00:04:38,661 είναι απλά πολύ πιο εύκολο και γρηγορότερα για να τους παραδώσει πίσω έξω 122 00:04:38,661 --> 00:04:40,030 για μαθητές με αλφαβητική σειρά. 123 00:04:40,030 --> 00:04:42,770 Ποιο θα είναι το ένστικτό σας για ένα σωρό εξετάσεις, όπως αυτό; 124 00:04:42,770 --> 00:04:45,019 >> Λοιπόν, αν είστε σαν κι εμένα, σας μπορεί να δει ότι αυτό είναι m, 125 00:04:45,019 --> 00:04:48,505 έτσι Πάω να είδος τεθεί αυτό σε, αν αυτό είναι το τραπέζι μου ή στο πάτωμα μου, όπου 126 00:04:48,505 --> 00:04:50,650 Είμαι εξαπλώνεται πράγματα out-- ή σειρά μου really-- 127 00:04:50,650 --> 00:04:52,210 Θα ήθελα να βάλει όλα της κας εκεί. 128 00:04:52,210 --> 00:04:52,710 Ω. 129 00:04:52,710 --> 00:04:55,020 Εδώ είναι ένα A. Έτσι θα μπορούσα θέσει τα Ως εδώ. 130 00:04:55,020 --> 00:04:55,520 Ω. 131 00:04:55,520 --> 00:04:57,980 Εδώ είναι ένα άλλο Α Πάω να θέσω εδώ. 132 00:04:57,980 --> 00:05:02,490 Εδώ είναι μια Ζ Εδώ είναι ένα άλλο Μ Και έτσι Θα ήθελα να αρχίσουμε να κάνουμε σωρούς σαν αυτό. 133 00:05:02,490 --> 00:05:06,620 Και τότε ίσως θα ήθελα να πάω σε αργότερα και το είδος της πολύ nitpicky-LY είδος 134 00:05:06,620 --> 00:05:07,710 οι επιμέρους σωρούς. 135 00:05:07,710 --> 00:05:11,300 Αλλά το θέμα είναι ότι θα δούμε στην είσοδο που είμαι χέρια 136 00:05:11,300 --> 00:05:14,016 και θα ήθελα να κάνω κάποια υπολογίζεται απόφαση με βάση την είσοδο. 137 00:05:14,016 --> 00:05:15,640 Αν ξεκινά με Α, το έβαλε εκεί πέρα. 138 00:05:15,640 --> 00:05:18,980 Αν ξεκινά με το Ζ, το έβαλε πάνω εκεί, και πάντα στο μεταξύ. 139 00:05:18,980 --> 00:05:22,730 >> Έτσι, αυτό είναι μια τεχνική που είναι γενικά γνωστό ως hashing-- H-A-S-H-- 140 00:05:22,730 --> 00:05:26,550 πράγμα που σημαίνει γενικά λαμβάνοντας ως εισόδου και χρησιμοποιώντας αυτή την είσοδο για τον υπολογισμό 141 00:05:26,550 --> 00:05:30,940 μια τιμή, γενικά ένας αριθμός, και ότι αριθμός είναι ο δείκτης σε μια αποθήκη 142 00:05:30,940 --> 00:05:32,260 δοχείο, όπως μία συστοιχία. 143 00:05:32,260 --> 00:05:35,490 Έτσι με άλλα λόγια, μπορεί να έχω μια hash λειτουργία, όπως και εγώ στο κεφάλι μου, 144 00:05:35,490 --> 00:05:37,940 ότι αν δω κάποιον που είναι όνομα που ξεκινά με Α, 145 00:05:37,940 --> 00:05:40,190 Πάω να χαρτογραφήσει ότι στο μηδέν στο κεφάλι μου. 146 00:05:40,190 --> 00:05:44,160 Και αν δω κάποιον με Ζ, είμαι πρόκειται να χαρτογραφήσει ότι σε 25 στο κεφάλι μου 147 00:05:44,160 --> 00:05:46,220 και στη συνέχεια να θέσει ότι σε η τελευταία πιο σωρό. 148 00:05:46,220 --> 00:05:50,990 >> Τώρα, αν νομίζετε ότι για να μην του εγκεφάλου μου αλλά ένα πρόγραμμα C, τι αριθμούς θα μπορούσε να 149 00:05:50,990 --> 00:05:53,170 θα στηριχθεί για να επιτευχθεί το ίδιο αποτέλεσμα; 150 00:05:53,170 --> 00:05:55,594 Με άλλα λόγια, αν είχε τον ASCII χαρακτήρα Α, 151 00:05:55,594 --> 00:05:57,510 πώς μπορώ να προσδιορίσω τι κουβά για να το θέσω σε; 152 00:05:57,510 --> 00:05:59,801 Πιθανότατα δεν θέλουν να το βάζουμε σε κάδο 65, η οποία 153 00:05:59,801 --> 00:06:01,840 θα είναι σαν εκεί για κανέναν καλό λόγο. 154 00:06:01,840 --> 00:06:04,320 Πού θέλετε να βάλετε ένα όσον αφορά την τιμή ASCII του; 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Πού θέλετε να κάνετε για να ASCII του αξία να καταλήξουμε σε μια πιο έξυπνη κάδο 157 00:06:08,920 --> 00:06:09,480 για να το θέσω σε; 158 00:06:09,480 --> 00:06:10,206 >> ΚΟΙΝΟ: Μείον Α 159 00:06:10,206 --> 00:06:10,956 >> DAVID Malan: Ναι. 160 00:06:10,956 --> 00:06:13,190 Έτσι μείον Α ή μείον συγκεκριμένα 65 αν είναι 161 00:06:13,190 --> 00:06:18,240 ένα κεφάλαιο Α ή 98 εάν είναι ένα πεζό α. 162 00:06:18,240 --> 00:06:21,300 Και έτσι αυτό θα μας επιτρέψει να, πολύ απλά και πολύ αριθμητικά, 163 00:06:21,300 --> 00:06:23,260 βάλει κάτι σε ένα κουβά όπως αυτό. 164 00:06:23,260 --> 00:06:26,010 Έτσι αποδεικνύεται μπορούμε πραγματικά να κάνουμε αυτό, καθώς ακόμη και με τα κουίζ. 165 00:06:26,010 --> 00:06:29,051 >> Έτσι, μπορείτε να ανακαλέσετε σας κύκλο σας Όνομα διδασκαλία τους συναδέλφους του στο εξώφυλλο. 166 00:06:29,051 --> 00:06:32,270 Και τα ονόματα του TF οργανώθηκαν σε αυτές τις στήλες με αλφαβητική σειρά, 167 00:06:32,270 --> 00:06:34,400 Λοιπόν, είτε το πιστεύετε είτε όχι, όταν όλα τα 80 συν μας 168 00:06:34,400 --> 00:06:37,800 πήρε μαζί τις προάλλες στο βαθμό, το τελευταίο βήμα στη διαδικασία βαθμολόγησης μας 169 00:06:37,800 --> 00:06:41,830 είναι να hash τις κουίζ σε μια μεγάλη χώρο του δαπέδου στο [δεν ακούγεται] 170 00:06:41,830 --> 00:06:45,110 και να θέσει κουίζ όλοι έξω ακριβώς τη σειρά του TF τους 171 00:06:45,110 --> 00:06:47,700 ονόματα στο εξώφυλλο, γιατί τότε είναι πολύ πιο εύκολο για εμάς 172 00:06:47,700 --> 00:06:51,290 για να αναζητήσετε μέσα από αυτό χρησιμοποιώντας την γραμμική αναζήτηση ή κάποιο είδος της ευφυΐας 173 00:06:51,290 --> 00:06:54,050 για μια TF για να βρείτε ή του κουίζ των μαθητών της. 174 00:06:54,050 --> 00:06:56,060 >> Έτσι, αυτή η ιδέα του κατακερματισμού ότι θα δείτε είναι 175 00:06:56,060 --> 00:07:00,520 αρκετά ισχυρό είναι στην πραγματικότητα αρκετά συνηθισμένη και πολύ έξυπνο, 176 00:07:00,520 --> 00:07:03,000 σαν ίσως χωρίζουν και Conquer ήταν στην εβδομάδα μηδέν. 177 00:07:03,000 --> 00:07:05,250 Εγώ γρήγορα προς τα εμπρός για την hackathon ένα-δύο χρόνια πριν. 178 00:07:05,250 --> 00:07:08,040 Αυτό ήταν Zamyla και ένα ζευγάρι των άλλους μαθητές χαιρετισμό του προσωπικού 179 00:07:08,040 --> 00:07:09,030 όπως ήρθαν σε. 180 00:07:09,030 --> 00:07:12,680 Και είχαμε ένα σωρό αναδίπλωσης τραπέζια εκεί με ετικέτες ονομάτων. 181 00:07:12,680 --> 00:07:15,380 Και είχαμε τις ετικέτες όνομα του οργανωμένου με, όπως τα Ως εκεί 182 00:07:15,380 --> 00:07:16,690 και η Zs εκεί. 183 00:07:16,690 --> 00:07:20,350 Και έτσι ένα από τα TFs πολύ έξυπνα έγραψε αυτό ως τις οδηγίες 184 00:07:20,350 --> 00:07:21,030 για την ημέρα. 185 00:07:21,030 --> 00:07:24,480 Και στην 12η εβδομάδα του εξαμήνου αυτού του όλα γίνονται τέλεια αίσθηση και ο καθένας 186 00:07:24,480 --> 00:07:25,310 δεν ήξερε τι να κάνει. 187 00:07:25,310 --> 00:07:27,900 Αλλά οποτεδήποτε έχετε ουρά με τον ίδιο τρόπο, 188 00:07:27,900 --> 00:07:30,272 είστε εφαρμογή η ίδια έννοια του κατακερματισμού. 189 00:07:30,272 --> 00:07:31,730 Οπότε ας το λίγο επισημοποιήσει. 190 00:07:31,730 --> 00:07:32,890 Εδώ είναι ένας πίνακας. 191 00:07:32,890 --> 00:07:36,820 Είναι που να είναι λίγο ευρύ μόνο για να απεικονίσει, οπτικά, 192 00:07:36,820 --> 00:07:38,920 ότι θα μπορούσαμε να βάλει χορδές σε κάτι σαν αυτό. 193 00:07:38,920 --> 00:07:41,970 Και αυτή η σειρά είναι σαφώς από το μέγεθος 26 συνολικά. 194 00:07:41,970 --> 00:07:43,935 Και το πράγμα που ονομάζεται τραπέζι αυθαίρετα. 195 00:07:43,935 --> 00:07:48,930 Αλλά αυτό είναι μόνο παράδοση ενός καλλιτέχνη από ό, τι ένας πίνακας κατακερματισμού θα μπορούσε να είναι. 196 00:07:48,930 --> 00:07:52,799 >> Έτσι, ένας πίνακας κατακερματισμού τώρα πρόκειται να είναι ένα υψηλότερο επίπεδο δομής δεδομένων. 197 00:07:52,799 --> 00:07:54,840 Στο τέλος της ημέρας είμαστε για να δείτε ότι σας 198 00:07:54,840 --> 00:07:58,700 μπορεί να εφαρμόσει ένα πίνακα κατακερματισμού, η οποία μοιάζει πολύ με τη γραμμή check-in 199 00:07:58,700 --> 00:08:02,059 σε ένα hackathon πολύ σαν αυτό πίνακας που χρησιμοποιείται για τη διαλογή βιβλία εξετάσεις. 200 00:08:02,059 --> 00:08:03,850 Αλλά ένας πίνακας κατακερματισμού είναι είδος αυτού του υψηλού επιπέδου 201 00:08:03,850 --> 00:08:08,250 έννοια που θα μπορούσε να χρησιμοποιήσει μια σειρά κάτω από το καπό για να την εφαρμόσει, 202 00:08:08,250 --> 00:08:11,890 ή θα μπορούσε να χρησιμοποιήσει μια λίστα μήκος, ή ακόμη και ίσως ορισμένες άλλες δομές δεδομένων. 203 00:08:11,890 --> 00:08:15,590 Και τώρα που είναι η theme-- λήψη ορισμένα από τα βασικά συστατικά 204 00:08:15,590 --> 00:08:18,310 σαν μια σειρά και αυτό το κτίριο μπλοκάρουν τώρα από μια λίστα μήκους 205 00:08:18,310 --> 00:08:21,740 και να δούμε τι άλλο μπορούμε να χτίσουμε πάνω από αυτά, όπως και τα συστατικά 206 00:08:21,740 --> 00:08:26,550 σε μια συνταγή, καθιστώντας όλο και περισσότερο ενδιαφέρουσα και χρήσιμη τελικά αποτελέσματα. 207 00:08:26,550 --> 00:08:28,680 >> Έτσι με τον πίνακα κατακερματισμού θα μπορούσαμε να το εφαρμόσει 208 00:08:28,680 --> 00:08:32,540 στη μνήμη εικονογραφικά σαν αυτό, αλλά πώς θα μπορούσε πραγματικά να κωδικοποιηθεί μέχρι; 209 00:08:32,540 --> 00:08:33,789 Καλά, ίσως, όσο πιο απλά είναι αυτό. 210 00:08:33,789 --> 00:08:38,270 Αν η χωρητικότητα σε όλα τα καλύμματα, είναι απλά κάποια constant-- για παράδειγμα 26, 211 00:08:38,270 --> 00:08:42,030 για 26 επιστολές του alphabet-- Θα ήθελα να καλέσετε μεταβλητή τραπέζι μου, 212 00:08:42,030 --> 00:08:45,630 και εγώ μπορεί να ισχυριστεί ότι θα πάω να θέσει char αστέρια εκεί, ή σπάγκο. 213 00:08:45,630 --> 00:08:49,880 Γι 'αυτό είναι τόσο απλό όσο αυτό αν θέλουν να εφαρμόσουν ένα πίνακα κατακερματισμού. 214 00:08:49,880 --> 00:08:51,490 Και όμως, αυτό είναι πραγματικά ακριβώς μια σειρά. 215 00:08:51,490 --> 00:08:53,198 Αλλά και πάλι, ένα hash πίνακας είναι τώρα τι θα 216 00:08:53,198 --> 00:08:57,470 καλέστε έναν αφηρημένο τύπο δεδομένων που είναι ακριβώς Ταξινόμηση των εννοιολογική διαστρωμάτωση στην κορυφή 217 00:08:57,470 --> 00:09:00,780 κάτι πιο πεζά ήθελα τώρα μια σειρά. 218 00:09:00,780 --> 00:09:02,960 >> Τώρα, πώς πηγαίνουμε για την επίλυση των προβλημάτων; 219 00:09:02,960 --> 00:09:06,980 Λοιπόν, νωρίτερα είχα την πολυτέλεια έχουν αρκετό χώρο τραπέζι εδώ 220 00:09:06,980 --> 00:09:09,460 έτσι ώστε θα μπορούσα να βάλω το κουίζ οπουδήποτε ήθελα. 221 00:09:09,460 --> 00:09:10,620 Έτσι, όπως θα μπορούσε να πάει εδώ. 222 00:09:10,620 --> 00:09:12,100 Zs θα μπορούσε να πάει εδώ. 223 00:09:12,100 --> 00:09:13,230 Κα μπορεί να πάει εδώ. 224 00:09:13,230 --> 00:09:14,740 Και τότε είχα κάποια επιπλέον χώρο. 225 00:09:14,740 --> 00:09:18,740 Αλλά αυτό είναι ένα κομμάτι από ένα εξαπατήσει δικαιώματος τώρα, γιατί αυτόν τον πίνακα, αν πραγματικά 226 00:09:18,740 --> 00:09:22,720 σκεφτόμουν σαν μια σειρά, είναι απλά πρόκειται να είναι από κάποιο σταθερό μέγεθος. 227 00:09:22,720 --> 00:09:25,380 >> Έτσι, τεχνικά, αν μου τραβήξει μέχρι κουίζ κάποιου άλλου φοιτητή 228 00:09:25,380 --> 00:09:28,490 και να δείτε, ω, αυτό το άτομο είναι Όνομα ξεκινάει με ένα Α πάρα πολύ, 229 00:09:28,490 --> 00:09:30,980 Ι το είδος θέλετε να το βάλετε εκεί. 230 00:09:30,980 --> 00:09:34,740 Αλλά μόλις το έβαλα εκεί, αν ο πίνακας αυτός αποτελεί πράγματι μια σειρά, 231 00:09:34,740 --> 00:09:37,840 Πάω να προεξεχόντων ή clobbering όποιος κουίζ αυτού του μαθητή είναι. 232 00:09:37,840 --> 00:09:38,340 Σωστά; 233 00:09:38,340 --> 00:09:41,972 Εάν αυτό είναι ένας πίνακας, ένα μόνο πράγμα μπορεί να πάει σε καθένα από αυτά τα κύτταρα ή στοιχείων. 234 00:09:41,972 --> 00:09:43,680 Και γι 'αυτό το είδος έχει για να επιλέξετε και να επιλέξετε. 235 00:09:43,680 --> 00:09:45,735 >> Τώρα νωρίτερα Ι το είδος του εξαπατημένοι και έκανε αυτό ή εγώ 236 00:09:45,735 --> 00:09:47,526 ακριβώς το είδος των στοιβάζονται τους πάνω από κάθε άλλο. 237 00:09:47,526 --> 00:09:49,170 Αλλά αυτό δεν πρόκειται να πετάξει στον κώδικα. 238 00:09:49,170 --> 00:09:52,260 Έτσι, όταν θα μπορούσε να βάλω το δεύτερος φοιτητής του οποίου το όνομα 239 00:09:52,260 --> 00:09:54,964 είναι ένα, αν το μόνο που είχα είναι αυτό διαθέσιμος χώρος στο τραπέζι; 240 00:09:54,964 --> 00:09:57,880 Και έχω χρησιμοποιήσει τρεις υποδοχές και μοιάζει σαν να υπάρχει μόνο μερικά άλλα. 241 00:09:57,880 --> 00:09:58,959 Τι θα μπορούσατε να κάνετε; 242 00:09:58,959 --> 00:09:59,834 ΚΟΙΝΟ: [δεν ακούγεται] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID Malan: Ναι. 245 00:10:01,315 --> 00:10:02,370 Ίσως απλά ας την κρατήσουμε απλή. 246 00:10:02,370 --> 00:10:02,660 Σωστά; 247 00:10:02,660 --> 00:10:04,243 Δεν χωράει όπου θέλω να το θέσω. 248 00:10:04,243 --> 00:10:07,450 Έτσι, Πάω να το θέσουμε από τεχνική όπου ένας Β θα πάει. 249 00:10:07,450 --> 00:10:09,932 Τώρα, βέβαια, αρχίζω να ζωγραφίσει τον εαυτό μου σε μια γωνία. 250 00:10:09,932 --> 00:10:11,890 Αν φτάσουμε σε ένα μαθητή του οποίου το όνομα είναι πράγματι Β, 251 00:10:11,890 --> 00:10:14,840 τώρα B πρόκειται να μετακινηθεί λίγο προς τα εμπρός, όπως θα μπορούσε να συμβεί, yep, 252 00:10:14,840 --> 00:10:17,530 αν αυτό είναι ένα Β, τώρα πρέπει να πάει εδώ. 253 00:10:17,530 --> 00:10:20,180 >> Και έτσι αυτό πολύ γρήγορα θα μπορούσε να καταστεί προβληματική, 254 00:10:20,180 --> 00:10:23,850 αλλά είναι μια τεχνική που στην πραγματικότητα αναφέρεται ως γραμμική διερεύνηση, 255 00:10:23,850 --> 00:10:26,650 όπου μπορείτε απλά να εξετάσει σας συστοιχία να είναι κατά μήκος της γραμμής. 256 00:10:26,650 --> 00:10:29,680 Και ακριβώς το είδος του καθετήρα ή επιθεωρούν κάθε διαθέσιμο στοιχείο 257 00:10:29,680 --> 00:10:31,360 ψάχνει για ένα διαθέσιμο σημείο. 258 00:10:31,360 --> 00:10:34,010 Και το συντομότερο μπορείτε να βρείτε ένα, μπορείτε να ρίξετε εκεί. 259 00:10:34,010 --> 00:10:38,390 >> Τώρα, η τιμή που καταβάλλεται τώρα για αυτή τη λύση είναι αυτό; 260 00:10:38,390 --> 00:10:41,300 Έχουμε μια σταθερή σειρά μεγέθους, και όταν εισάγω τα ονόματα 261 00:10:41,300 --> 00:10:44,059 σε αυτό, τουλάχιστον αρχικά, τι είναι ο χρόνος εκτέλεσης της εισαγωγής 262 00:10:44,059 --> 00:10:46,350 για την τοποθέτηση των μαθητών κουίζ στη σωστή κάδους; 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O τι; 265 00:10:50,002 --> 00:10:51,147 >> ΚΟΙΝΟ: Ν. 266 00:10:51,147 --> 00:10:52,480 DAVID Malan: Άκουσα μεγάλη O Ν. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Δεν είναι αλήθεια. 269 00:10:54,300 --> 00:10:56,490 Αλλά εμείς θα δώσουμε έμφαση, εκτός γιατί ακριβώς σε μια στιγμή. 270 00:10:56,490 --> 00:10:57,702 Τι άλλο μπορεί να είναι; 271 00:10:57,702 --> 00:10:58,755 >> ΚΟΙΝΟ: [δεν ακούγεται] 272 00:10:58,755 --> 00:11:00,380 DAVID Malan: Και επιτρέψτε μου να το κάνω οπτικά. 273 00:11:00,380 --> 00:11:04,720 Έτσι, υποθέστε ότι αυτό είναι το γράμμα S. 274 00:11:04,720 --> 00:11:05,604 >> ΚΟΙΝΟ: Είναι μία. 275 00:11:05,604 --> 00:11:06,520 DAVID Malan: Είναι μία. 276 00:11:06,520 --> 00:11:06,710 Σωστά; 277 00:11:06,710 --> 00:11:08,950 Αυτό είναι ένας πίνακας, ο οποίος σημαίνει ότι έχουμε τυχαία πρόσβαση. 278 00:11:08,950 --> 00:11:11,790 Και αν σκεφτούμε αυτό ως μηδέν και αυτό ως 25, 279 00:11:11,790 --> 00:11:13,800 και συνειδητοποιούμε ότι, Ω, εδώ είναι είσοδος μου S, 280 00:11:13,800 --> 00:11:16,350 Σίγουρα μπορεί να μετατρέψει S, ένας χαρακτήρας ASCII, 281 00:11:16,350 --> 00:11:18,540 σε έναν αντίστοιχο αριθμό μεταξύ μηδέν και 25 282 00:11:18,540 --> 00:11:20,910 και αμέσως μετά το βάζουμε εκεί που ανήκει. 283 00:11:20,910 --> 00:11:26,120 >> Αλλά φυσικά, το συντομότερο πάρω να το δεύτερο πρόσωπο που το όνομα του είναι Α ή Β ή Γ 284 00:11:26,120 --> 00:11:29,300 τελικά, αν έχω χρησιμοποιήσει το γραμμική σχολαστικά ως λύση μου, 285 00:11:29,300 --> 00:11:31,360 ο χρόνος εκτέλεσης του εισαγωγή στη χειρότερη περίπτωση 286 00:11:31,360 --> 00:11:33,120 είναι πραγματικά πρόκειται να περιέλθει σε τι; 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Και εγώ δεν το ακούω εδώ σωστά από νωρίς. 289 00:11:36,045 --> 00:11:36,920 ΚΟΙΝΟ: [δεν ακούγεται] 290 00:11:36,920 --> 00:11:41,620 DAVID Malan: Έτσι είναι n πράγματι μία φορά έχετε ένα αρκετά μεγάλο σύνολο δεδομένων. 291 00:11:41,620 --> 00:11:44,410 Έτσι, από τη μία πλευρά, αν σειρά σας είναι αρκετά μεγάλη 292 00:11:44,410 --> 00:11:48,287 και τα δεδομένα σας είναι αρκετά αραιή, μπορείτε να πάρει αυτό το όμορφο σταθερό χρόνο. 293 00:11:48,287 --> 00:11:50,620 Αλλά μόλις ξεκινήσετε όλο και περισσότερα στοιχεία, 294 00:11:50,620 --> 00:11:53,200 και απλά στατιστικά μπορείτε να πάρετε περισσότερα άτομα με το γράμμα 295 00:11:53,200 --> 00:11:56,030 Α, όπως το όνομά τους ή το γράμμα Β, θα μπορούσε δυνητικά 296 00:11:56,030 --> 00:11:57,900 περιέλθει σε κάτι πιο γραμμική. 297 00:11:57,900 --> 00:11:59,640 Έτσι, δεν είναι αρκετά τέλειο. 298 00:11:59,640 --> 00:12:00,690 Έτσι, θα μπορούσαμε να κάνουμε καλύτερα; 299 00:12:00,690 --> 00:12:03,210 >> Λοιπόν, τι ήταν μας λύση πριν, όταν εμείς 300 00:12:03,210 --> 00:12:06,820 θέλουν να έχουν μεγαλύτερη δυναμική από ό, τι κάτι σαν μια σειρά επιτρέπονται; 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 ΚΟΙΝΟ: [δεν ακούγεται] 303 00:12:08,960 --> 00:12:10,030 DAVID Malan: Τι εισάγουμε; 304 00:12:10,030 --> 00:12:10,530 Ναι. 305 00:12:10,530 --> 00:12:11,430 Έτσι, μια συνδεδεμένη λίστα. 306 00:12:11,430 --> 00:12:14,430 Λοιπόν, ας δούμε τι συνδέεται κατάλογος θα μπορούσε να κάνει για μας αντ 'αυτού. 307 00:12:14,430 --> 00:12:17,630 Λοιπόν, επιτρέψτε μου να προτείνω να επιστήσει την εικόνα ως εξής. 308 00:12:17,630 --> 00:12:19,620 Τώρα αυτό είναι μια διαφορετική εικόνα από ένα παράδειγμα 309 00:12:19,620 --> 00:12:24,750 από ένα διαφορετικό κείμενο, στην πραγματικότητα, ότι είναι στην πραγματικότητα χρησιμοποιώντας ένα πίνακα μεγέθους 31. 310 00:12:24,750 --> 00:12:28,220 Και ο συγγραφέας απλά αποφάσισε να hash χορδές 311 00:12:28,220 --> 00:12:32,430 όχι με βάση τα ονόματα του ατόμου, αλλά βασίζεται σε ημερομηνιες γέννησης τους. 312 00:12:32,430 --> 00:12:35,680 Ανεξαρτήτως του μήνα, κατάλαβα αν γεννηθεί την πρώτη του μήνα 313 00:12:35,680 --> 00:12:39,580 ή η 31η του μήνα, ο συγγραφέας θα hash βασίζεται στην εν λόγω τιμή, 314 00:12:39,580 --> 00:12:44,154 έτσι ώστε να εξαπλωθεί τα ονόματα από λίγο περισσότερο από ακριβώς 26 σημεία μπορεί να επιτρέψει. 315 00:12:44,154 --> 00:12:47,320 Και ίσως είναι λίγο πιο ομοιόμορφη ό, τι συμβαίνει με τα γράμματα του αλφαβήτου, 316 00:12:47,320 --> 00:12:50,236 γιατί φυσικά υπάρχει πιθανώς περισσότεροι άνθρωποι στον κόσμο με τα ονόματα 317 00:12:50,236 --> 00:12:54,020 ότι ξεκινούν με ένα από τα σίγουρα κάποια άλλα γράμματα της αλφαβήτου. 318 00:12:54,020 --> 00:12:56,380 Έτσι ίσως αυτό είναι λίγο πιο ομοιόμορφη, υποθέτοντας 319 00:12:56,380 --> 00:12:58,640 μια ομοιόμορφη κατανομή των βρεφών σε ένα μήνα. 320 00:12:58,640 --> 00:12:59,990 >> Αλλά, φυσικά, αυτό εξακολουθεί να είναι ατελής. 321 00:12:59,990 --> 00:13:00,370 Σωστά; 322 00:13:00,370 --> 00:13:01,370 Είμαστε έχοντας συγκρούσεις. 323 00:13:01,370 --> 00:13:04,680 Πολλαπλές οι άνθρωποι σε αυτό δομή δεδομένων είναι ακόμα 324 00:13:04,680 --> 00:13:08,432 έχουν την ίδια ημερομηνία γέννησης, τουλάχιστον είστε ανεξάρτητα από το μήνα. 325 00:13:08,432 --> 00:13:09,640 Αλλά αυτό που έχει κάνει ο συγγραφέας; 326 00:13:09,640 --> 00:13:13,427 Λοιπόν, φαίνεται σαν να έχουμε μια σειρά στην αριστερή πλευρά που κάθετα, 327 00:13:13,427 --> 00:13:15,010 αλλά αυτό είναι μόνο παράδοση ενός καλλιτέχνη. 328 00:13:15,010 --> 00:13:18,009 Δεν έχει σημασία ποια κατεύθυνση συντάξει μια σειρά, είναι ακόμα μια σειρά. 329 00:13:18,009 --> 00:13:20,225 Τι είναι αυτό μια σειρά από φαινομενικά; 330 00:13:20,225 --> 00:13:21,500 >> ΚΟΙΝΟ: συνδεδεμένη λίστα. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Malan: Ναι. 332 00:13:21,650 --> 00:13:23,490 Μοιάζει σαν να είναι ένα συστοιχία συνδεδεμένη λίστα. 333 00:13:23,490 --> 00:13:26,490 Έτσι και πάλι, σε αυτό το σημείο του είδους από τη χρήση αυτών των δομών δεδομένων τώρα 334 00:13:26,490 --> 00:13:28,550 ως συστατικά σε περισσότερες ενδιαφέρουσες λύσεις, 335 00:13:28,550 --> 00:13:30,862 μπορείτε να πάρετε απολύτως θεμελιώδη, όπως και μια σειρά, 336 00:13:30,862 --> 00:13:33,320 και στη συνέχεια να λάβει κάτι περισσότερο ενδιαφέρουσα σαν μια συνδεδεμένη λίστα 337 00:13:33,320 --> 00:13:36,660 και ακόμα να τα συνδυάσετε σε ένα ακόμη πιο ενδιαφέρουσα δομή δεδομένων. 338 00:13:36,660 --> 00:13:39,630 Και πράγματι, αυτό επίσης θα να ονομάζεται ένα πίνακα κατακερματισμού, 339 00:13:39,630 --> 00:13:42,610 οπότε η συστοιχία είναι πραγματικά ο πίνακας κατακερματισμού, 340 00:13:42,610 --> 00:13:45,600 αλλά ότι ο πίνακας κατακερματισμού έχει αλυσίδες, να το πω έτσι, 341 00:13:45,600 --> 00:13:50,220 ότι μπορεί να αυξηθεί ή να συρρικνωθεί με βάση το τον αριθμό των στοιχείων που θέλετε να εισαγάγετε. 342 00:13:50,220 --> 00:13:52,990 >> Τώρα, ως εκ τούτου, ό, τι είναι ο χρόνος τρέχει τώρα; 343 00:13:52,990 --> 00:13:58,030 Αν θέλετε να εισάγετε κάποιον του οποίου τα γενέθλια είναι η 31η Οκτωβρίου, 344 00:13:58,030 --> 00:13:59,040 πού αυτός ή αυτή να πάει; 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Εντάξει. 347 00:14:01,030 --> 00:14:02,819 Στο κάτω μέρος όπου λέει 31. 348 00:14:02,819 --> 00:14:03,610 Και αυτό είναι τέλειο. 349 00:14:03,610 --> 00:14:05,060 Αυτό ήταν σταθερό χρόνο. 350 00:14:05,060 --> 00:14:08,760 Αλλά τι θα γίνει αν βρεθεί κάποιος άλλος του οποίου τα γενέθλια είναι, ας δούμε, 351 00:14:08,760 --> 00:14:10,950 Οκτώβριος, Νοέμβριος, Δεκέμβριος 31; 352 00:14:10,950 --> 00:14:12,790 Πού είναι αυτός ή αυτή πρόκειται να πάει; 353 00:14:12,790 --> 00:14:13,290 Το ίδιο πράγμα. 354 00:14:13,290 --> 00:14:13,970 Δύο βήμα όμως. 355 00:14:13,970 --> 00:14:15,303 Αυτό είναι σταθερή και αν δεν είναι; 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Εντάξει. 358 00:14:16,860 --> 00:14:17,840 Αυτή τη στιγμή είναι. 359 00:14:17,840 --> 00:14:20,570 Αλλά στη γενική περίπτωση, οι περισσότεροι άνθρωποι προσθέτουμε, 360 00:14:20,570 --> 00:14:23,790 πιθανολογικά, θα πάμε να πάρει όλο και περισσότερες συγκρούσεις. 361 00:14:23,790 --> 00:14:26,820 >> Τώρα αυτό είναι μια μικρή καλύτερα, διότι είναι τεχνικά 362 00:14:26,820 --> 00:14:34,580 τώρα αλυσίδες μου θα μπορούσε να είναι σε η χειρότερη περίπτωση για πόσο καιρό; 363 00:14:34,580 --> 00:14:38,890 Αν τοποθετήσετε n άνθρωποι σε αυτή την πιο εξελιγμένα δομή δεδομένων, n οι άνθρωποι, 364 00:14:38,890 --> 00:14:41,080 στη χειρότερη περίπτωση, πρόκειται να είναι n. 365 00:14:41,080 --> 00:14:41,815 Γιατί; 366 00:14:41,815 --> 00:14:43,332 >> ΚΟΙΝΟ: Γιατί αν όλοι έχει γενέθλια την ίδια μέρα, 367 00:14:43,332 --> 00:14:44,545 από όπου και αν πρόκειται να είναι μία γραμμή. 368 00:14:44,545 --> 00:14:45,420 DAVID Malan: Τέλεια. 369 00:14:45,420 --> 00:14:47,480 Θα μπορούσε να είναι λίγο σκηνοθετημένη, αλλά πραγματικά στη χειρότερη περίπτωση, 370 00:14:47,480 --> 00:14:50,117 αν ο καθένας έχει γενέθλια την ίδια μέρα, λαμβάνοντας υπόψη τις εισροές που έχετε, 371 00:14:50,117 --> 00:14:51,950 θα πάμε να έχουν ένα μαζικά μακράς αλύσου. 372 00:14:51,950 --> 00:14:54,241 Και έτσι, θα μπορούσε να είναι μια κλήση hash πίνακα, αλλά πραγματικά είναι 373 00:14:54,241 --> 00:14:56,810 απλά μια μαζική συνδεδεμένη λίστα με ένα σωρό σπατάλη χώρου. 374 00:14:56,810 --> 00:15:00,460 Αλλά σε γενικές γραμμές, αν υποθέσουμε ότι τουλάχιστον γενέθλια είναι uniform-- 375 00:15:00,460 --> 00:15:01,750 και κατά πάσα πιθανότητα δεν είναι. 376 00:15:01,750 --> 00:15:02,587 Κάνω ότι μέχρι. 377 00:15:02,587 --> 00:15:04,420 Αλλά αν υποθέσουμε, για η χάρη της συζήτησης 378 00:15:04,420 --> 00:15:07,717 ότι είναι, στη συνέχεια, στη θεωρία, εάν Αυτό είναι η κατακόρυφη αναπαράσταση 379 00:15:07,717 --> 00:15:11,050 του πίνακα, και στη συνέχεια, ελπίζω να είστε πρόκειται να πάρει αλυσίδες που είναι, ξέρετε, 380 00:15:11,050 --> 00:15:15,880 περίπου το ίδιο μήκος, όπου κάθε ένα από αυτά αντιπροσωπεύει μια ημέρα του μήνα. 381 00:15:15,880 --> 00:15:19,930 >> Τώρα, αν υπάρχει 31 ημέρες το μήνα, αυτό σημαίνει ότι χρόνος μου τρέχει πραγματικά 382 00:15:19,930 --> 00:15:25,230 Είναι μεγάλη O Ν πάνω από 31, το οποίο αισθάνεται καλύτερα από ό, τι γραμμική. 383 00:15:25,230 --> 00:15:27,950 Αλλά αυτό ήταν ένα από μας δεσμεύσεις μια-δυο εβδομάδες 384 00:15:27,950 --> 00:15:31,145 Πριν από κάθε φορά που ήρθε στην έκφραση ο χρόνος εκτέλεσης ενός αλγορίθμου; 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Αρκεί να δει κανείς μόνο στο υψηλό όρος τάξης. 387 00:15:35,190 --> 00:15:35,690 Σωστά; 388 00:15:35,690 --> 00:15:37,400 31 είναι σίγουρα χρήσιμη. 389 00:15:37,400 --> 00:15:39,610 Αλλά αυτό είναι ακόμα μεγάλη O Ν. 390 00:15:39,610 --> 00:15:41,730 Αλλά ένα από τα θέματα του προβλήματος που πέντε 391 00:15:41,730 --> 00:15:43,950 πρόκειται να είναι σε Αναγνωρίζετε ότι απολύτως, 392 00:15:43,950 --> 00:15:47,320 ασυμπτωτικά, θεωρητικά Αυτή η δομή δεδομένων 393 00:15:47,320 --> 00:15:50,470 δεν είναι καλύτερη από ό, τι ακριβώς μία μαζική συνδεδεμένη λίστα. 394 00:15:50,470 --> 00:15:53,550 Και πράγματι, στη χειρότερη περίπτωση, αυτό hash πίνακας θα μπορούσε να περιέλθει σε αυτό. 395 00:15:53,550 --> 00:15:57,620 >> Αλλά στον πραγματικό κόσμο, με εμάς τους ανθρώπους ότι η δική τους Mac ή το PC ή ο, τιδήποτε 396 00:15:57,620 --> 00:16:01,240 και τρέχουν πραγματικό κόσμο λογισμικού σε πραγματικό κόσμο των δεδομένων, 397 00:16:01,240 --> 00:16:03,260 η οποία αλγόριθμο θα πας να προτιμάτε; 398 00:16:03,260 --> 00:16:09,180 Το ένα που παίρνει τέλος βήματα ή το μία η οποία παίρνει n διαιρείται με 31 βήματα 399 00:16:09,180 --> 00:16:12,900 να βρείτε κάποιο κομμάτι των δεδομένων ή να αναζητήσετε κάποιες πληροφορίες; 400 00:16:12,900 --> 00:16:16,580 Θέλω να πω, απολύτως τις 31 μάρκες μια διαφορά στον πραγματικό κόσμο. 401 00:16:16,580 --> 00:16:18,540 Είναι 31 φορές πιο γρήγορα. 402 00:16:18,540 --> 00:16:20,880 Και εμείς οι άνθρωποι είναι σίγουρα πρόκειται να το εκτιμήσουν. 403 00:16:20,880 --> 00:16:23,004 >> Έτσι αντιλαμβάνονται τη διχοτόμηση υπάρχει ανάμεσα στην πραγματικότητα 404 00:16:23,004 --> 00:16:25,920 μιλάμε για τα πράγματα θεωρητικά και ασυμπτωτικά που σίγουρα 405 00:16:25,920 --> 00:16:28,760 έχει αξία, όπως έχουμε δει, αλλά στον πραγματικό κόσμο, 406 00:16:28,760 --> 00:16:32,930 αν σας ενδιαφέρει να κάνουμε απλώς το ανθρώπινη χαρούμενος για γενικές εισροές, 407 00:16:32,930 --> 00:16:36,010 θα μπορούσε κάλλιστα να δεχθεί Το γεγονός ότι, ναι, αυτό είναι γραμμική, 408 00:16:36,010 --> 00:16:38,360 αλλά είναι 31 φορές πιο γρήγορα από ό, τι θα μπορούσε να είναι γραμμική. 409 00:16:38,360 --> 00:16:41,610 Και ακόμα καλύτερα, δεν πρέπει απλώς να κάνουμε κάτι αυθαίρετο σαν ημερομηνία γέννησης, 410 00:16:41,610 --> 00:16:44,030 Θα μπορούσαμε να περάσουμε λίγο περισσότερο χρόνο και εξυπνάδα 411 00:16:44,030 --> 00:16:47,140 και να σκεφτούμε τι μπορούμε να κάνουμε, όνομα και ίσως ενός ατόμου 412 00:16:47,140 --> 00:16:50,130 ημερομηνία γέννησής τους να συνδυάζουν εκείνες συστατικά για να καταλάβω κάτι 413 00:16:50,130 --> 00:16:52,720 ότι είναι πραγματικά περισσότερο ομοιόμορφη και λιγότερο αλλοιωμένες, 414 00:16:52,720 --> 00:16:56,250 να το πω έτσι από αυτή την εικόνα σήμερα δείχνει ότι θα μπορούσε να είναι. 415 00:16:56,250 --> 00:16:57,750 Πώς θα μπορούσαμε να εφαρμόσουμε στον κώδικα; 416 00:16:57,750 --> 00:17:00,280 Λοιπόν, επιτρέψτε μου να προτείνω να απλά δανειστεί κάποια σύνταξη έχουμε 417 00:17:00,280 --> 00:17:01,799 χρησιμοποιείται ένα ζευγάρι φορές μέχρι στιγμής. 418 00:17:01,799 --> 00:17:03,590 Και Πάω να καθορίσουν ένας κόμβος, ο οποίος και πάλι 419 00:17:03,590 --> 00:17:06,812 είναι ένας γενικός όρος για μερικά μόνο δοχείο για κάποια δομή δεδομένων. 420 00:17:06,812 --> 00:17:09,020 Πάω να προτείνω ένα string πηγαίνει εκεί. 421 00:17:09,020 --> 00:17:11,369 Αλλά θα πάμε για να αρχίσετε να παίρνετε εκείνους που έτρεχαν τροχούς μακριά τώρα. 422 00:17:11,369 --> 00:17:13,230 >> Δεν υπάρχει πλέον η CS50 βιβλιοθήκη Πραγματικά, αν θέλετε 423 00:17:13,230 --> 00:17:15,230 να το χρησιμοποιήσει για την τελική σας έργου, η οποία είναι λεπτή, 424 00:17:15,230 --> 00:17:18,569 αλλά τώρα θα πάμε για να τραβήξει πίσω το κουρτίνα και να πω ότι είναι απλά ένα αστέρι ΧΑΡ. 425 00:17:18,569 --> 00:17:22,069 Έτσι, η λέξη υπάρχει πρόκειται να είναι το όνομα του ατόμου στο ερώτημα. 426 00:17:22,069 --> 00:17:25,079 Και τώρα έχω ένα σύνδεσμο εδώ στον επόμενο κόμβο 427 00:17:25,079 --> 00:17:28,170 έτσι ώστε αυτές να αντιπροσωπεύουν κάθε ένα από τους κόμβους 428 00:17:28,170 --> 00:17:30,950 στην αλυσίδα, δυνητικά, μιας συνδεδεμένης λίστας. 429 00:17:30,950 --> 00:17:34,090 >> Και τώρα πώς μπορώ να δηλώνω ο ίδιος ο πίνακας κατακερματισμού; 430 00:17:34,090 --> 00:17:36,660 Πώς μπορώ να δηλώσει όλη αυτή τη δομή; 431 00:17:36,660 --> 00:17:40,960 Λοιπόν, πραγματικά, πολύ όπως εγώ χρησιμοποίησα ένα δείκτη απλά το πρώτο στοιχείο μιας λίστας 432 00:17:40,960 --> 00:17:44,510 πριν, ομοίως μπορώ μόνο να πω Απλώς χρειάζεται μια δέσμη των δεικτών 433 00:17:44,510 --> 00:17:46,270 να εφαρμόσει όλη αυτή πίνακα κατακερματισμού. 434 00:17:46,270 --> 00:17:49,484 Πάω να έχουν μια σειρά ονομάζεται πίνακας για πίνακα κατακερματισμού. 435 00:17:49,484 --> 00:17:50,900 Είναι πρόκειται να είναι του μεγέθους χωρητικότητας. 436 00:17:50,900 --> 00:17:52,525 Αυτό είναι το πόσα στοιχεία μπορούν να χωρέσουν σε αυτό. 437 00:17:52,525 --> 00:17:56,180 Και καθένα από αυτά τα στοιχεία σε αυτό σειρά πρόκειται να είναι ένα αστέρι κόμβο. 438 00:17:56,180 --> 00:17:56,810 Γιατί; 439 00:17:56,810 --> 00:18:00,160 Λοιπόν, κατ 'αυτή την εικόνα, τι είμαι την εφαρμογή του πίνακα κατακερματισμού ως 440 00:18:00,160 --> 00:18:04,330 αποτελεσματικά η αρχή είναι ακριβώς Αυτή η σειρά που έχουμε χαραγμένη κάθετα, 441 00:18:04,330 --> 00:18:06,820 καθένας εκ των οποίων πλατείες αντιπροσωπεύει ένα δείκτη. 442 00:18:06,820 --> 00:18:09,170 Ότι αυτοί που έχουν καθέτους μέσω αυτών είναι μόνο άκυρη. 443 00:18:09,170 --> 00:18:11,410 Και εκείνοι που έχουν βέλη πηγαίνει προς τα δεξιά 444 00:18:11,410 --> 00:18:16,140 είναι πραγματική δείκτες για την πραγματική κόμβους, όθεν την έναρξη μιας συνδεδεμένης λίστας. 445 00:18:16,140 --> 00:18:19,050 >> Μέχρι εδώ, λοιπόν, είναι πώς μπορούμε να εφαρμόσει ένα πίνακα κατακερματισμού που 446 00:18:19,050 --> 00:18:21,580 υλοποιεί Ξεχωριστές αλυσίδες. 447 00:18:21,580 --> 00:18:22,840 Τώρα μπορούμε να κάνουμε καλύτερα; 448 00:18:22,840 --> 00:18:25,632 Εντάξει είχα υποσχεθεί τελευταία φορά που θα μπορούσαμε να επιτύχουμε συνεχή χρόνο. 449 00:18:25,632 --> 00:18:27,381 Και εγώ το είδος σας έδωσε σταθερό χρόνο εδώ, 450 00:18:27,381 --> 00:18:29,850 αλλά στη συνέχεια δεν είπε πραγματικά σταθερό χρόνο γιατί είναι ακόμα 451 00:18:29,850 --> 00:18:31,890 εξαρτάται από την συνολική αριθμό στοιχείων 452 00:18:31,890 --> 00:18:34,500 είστε στη χάραξη της η δομή δεδομένων. 453 00:18:34,500 --> 00:18:35,980 Αλλά ας υποθέσουμε ότι το κάναμε αυτό. 454 00:18:35,980 --> 00:18:39,550 Επιτρέψτε μου να πάω πίσω στην οθόνη εδώ. 455 00:18:39,550 --> 00:18:44,520 Επιτρέψτε μου να προεξέχει επίσης αυτό εδώ, σαφή η οθόνη, και ας υποθέσουμε ότι το έκανα αυτό. 456 00:18:44,520 --> 00:18:49,300 Ας υποθέσουμε Ήθελα να εισάγετε το όνομα Daven σε σε δομή δεδομένων μου. 457 00:18:49,300 --> 00:18:52,100 >> Θέλω, λοιπόν, να εισαγάγετε μια συμβολοσειρά Daven μέσα στην δομή δεδομένων. 458 00:18:52,100 --> 00:18:54,370 Τι θα γίνει αν δεν χρησιμοποιείτε ένα hash πίνακα, αλλά μπορώ να χρησιμοποιήσω 459 00:18:54,370 --> 00:18:56,980 κάτι που είναι πιο δέντρο-όπως σαν ένα οικογενειακό δέντρο, όπου 460 00:18:56,980 --> 00:18:59,670 έχετε κάποια ρίζα κατά τη κορυφή και, στη συνέχεια, οι κόμβοι και τα φύλλα 461 00:18:59,670 --> 00:19:01,440 ότι πάει προς τα κάτω και προς τα έξω. 462 00:19:01,440 --> 00:19:04,450 Ας υποθέσουμε λοιπόν, ότι εγώ θέλετε να εισάγετε Daven του 463 00:19:04,450 --> 00:19:06,430 σε ό, τι είναι σήμερα μια κενή λίστα. 464 00:19:06,430 --> 00:19:09,780 Πάω να κάνω το εξής: είμαι πρόκειται να δημιουργήσει έναν κόμβο σε αυτή την οικογένεια 465 00:19:09,780 --> 00:19:15,170 δέντρο-όπως δομή δεδομένων που φαίνεται λίγο σαν αυτό, καθένα από τα οποία 466 00:19:15,170 --> 00:19:19,640 ορθογώνια έχει, ας πούμε, για σήμερα 26 στοιχεία σε αυτό. 467 00:19:19,640 --> 00:19:21,650 Και κάθε ένα από τα κύτταρα σε αυτήν την σειρά θα 468 00:19:21,650 --> 00:19:23,470 να εκπροσωπεί το γράμμα του αλφαβήτου. 469 00:19:23,470 --> 00:19:28,190 >> Συγκεκριμένα, Πάω για τη θεραπεία Αυτό είναι ένα, τότε Β, στη συνέχεια το C, τότε το D, 470 00:19:28,190 --> 00:19:29,310 αυτό εδώ. 471 00:19:29,310 --> 00:19:32,940 Έτσι, αυτό πρόκειται για την αποτελεσματική αντιπροσωπεύουν το γράμμα Δ 472 00:19:32,940 --> 00:19:36,040 Αλλά για να εισαγάγετε όλα τα Daven του το όνομα πρέπει να κάνω λίγο περισσότερο. 473 00:19:36,040 --> 00:19:37,840 Έτσι είμαι πρώτος πρόκειται να hash, να το πω έτσι. 474 00:19:37,840 --> 00:19:41,049 Πάω να δούμε το πρώτο γράμμα σε Daven το οποίο είναι προφανώς ένα D, 475 00:19:41,049 --> 00:19:42,840 και Πάω να διαθέσει ένας κόμβος που μοιάζει 476 00:19:42,840 --> 00:19:45,570 όπως this-- ένα μεγάλο ορθογώνιο μεγάλο αρκετό για να χωρέσει ολόκληρο το αλφάβητο. 477 00:19:45,570 --> 00:19:47,140 >> Τώρα D γίνεται. 478 00:19:47,140 --> 00:19:49,720 Τώρα Α Δ-Α-ν-Ε-Ν είναι ο στόχος. 479 00:19:49,720 --> 00:19:51,220 Και τώρα τι Πάω να κάνουμε είναι αυτό. 480 00:19:51,220 --> 00:19:54,027 Μόλις άρχισα Δ ειδοποίηση δεν υπάρχει δείκτης εκεί. 481 00:19:54,027 --> 00:19:56,860 Είναι αξίες σκουπίδια αυτή τη στιγμή, ή θα μπορούσε να γίνει η προετοιμασία της σε null. 482 00:19:56,860 --> 00:19:59,630 Αλλά επιτρέψτε μου να συνεχίσω με Αυτή η ιδέα της οικοδόμησης ενός δέντρου. 483 00:19:59,630 --> 00:20:04,260 Επιτρέψτε μου να διαθέσει άλλο ένα από αυτά κόμβους που έχει 26 στοιχεία σε αυτό. 484 00:20:04,260 --> 00:20:05,150 >> Και ξέρετε τι; 485 00:20:05,150 --> 00:20:09,130 Αν αυτό είναι μόνο ένας κόμβος σε μνήμη που Δημιούργησα με malloc, χρησιμοποιώντας ένα struct 486 00:20:09,130 --> 00:20:11,240 όπως θα δούμε σύντομα, Πάω να κάνω this-- 487 00:20:11,240 --> 00:20:14,450 Πάω να σχεδιάσετε ένα βέλος από το πράγμα που αντιπροσώπευε D προς τα κάτω 488 00:20:14,450 --> 00:20:15,860 σε αυτό το νέο κόμβο. 489 00:20:15,860 --> 00:20:19,240 Και τώρα, για πρώτη φορά το επόμενο επιστολή στο όνομα Daven του, 490 00:20:19,240 --> 00:20:24,150 V-- D-Α-V-- Πάω να πάει μπροστά και σχεδιάστε ένα άλλο κόμβο, όπως αυτό, 491 00:20:24,150 --> 00:20:30,150 σύμφωνα με την οποία, οι V στοιχεία εδώ, η οποία θα συντάξει για instance-- κραυγών. 492 00:20:30,150 --> 00:20:31,020 Εμείς δεν θα τραβήξει εκεί. 493 00:20:31,020 --> 00:20:31,936 Είναι πρόκειται να πάει εδώ. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Στη συνέχεια θα πάμε να θεωρούν ότι αυτό είναι V. 496 00:20:35,712 --> 00:20:44,920 Και στη συνέχεια κάτω από εδώ θα πάμε στο ευρετήριο κάτω από το V σε αυτό που θα εξετάσει Ε 497 00:20:44,920 --> 00:20:50,100 Και στη συνέχεια, από εδώ θα πάμε να πηγαίνετε έχει ένα από αυτούς τους κόμβους εδώ. 498 00:20:50,100 --> 00:20:52,930 Και τώρα έχουμε μια ερώτηση για να απαντήσει. 499 00:20:52,930 --> 00:20:57,840 Πρέπει με κάποιο τρόπο να δείξει ότι είμαστε στο τέλος του string Daven. 500 00:20:57,840 --> 00:20:59,490 Γι 'αυτό και θα μπορούσε απλά αφήστε το null. 501 00:20:59,490 --> 00:21:02,670 >> Αλλά τι γίνεται αν έχουμε Daven του πλήρες όνομα, επίσης, το οποίο 502 00:21:02,670 --> 00:21:04,280 είναι, όπως έχουμε πει, Ντάβενπορτ; 503 00:21:04,280 --> 00:21:06,970 Έτσι, ό, τι και αν είναι Daven στην πραγματικότητα μια συμβολοσειρά, 504 00:21:06,970 --> 00:21:08,960 ένα πρόθεμα του μια πολύ μεγαλύτερη χορδών; 505 00:21:08,960 --> 00:21:11,450 Δεν μπορούμε απλά να μόνιμα να πω τίποτα δεν πρόκειται 506 00:21:11,450 --> 00:21:14,410 να πάω εκεί, γιατί θα μπορούσαμε να Ποτέ εισάγετε μια λέξη όπως Davenport 507 00:21:14,410 --> 00:21:15,840 σε αυτή τη δομή δεδομένων 508 00:21:15,840 --> 00:21:19,560 >> Λοιπόν, τι θα μπορούσαμε να κάνουμε, αντιθέτως, είναι τη θεραπεία κάθε ένα από αυτά τα στοιχεία 509 00:21:19,560 --> 00:21:22,170 όπως ίσως έχει δύο στοιχείων στο εσωτερικό τους. 510 00:21:22,170 --> 00:21:24,810 Ένα είναι ένας δείκτης, πράγματι, όπως έχω ήδη κάνει. 511 00:21:24,810 --> 00:21:27,100 Έτσι, κάθε ένα από αυτά τα πλαίσια Δεν είναι μόνο ένα κύτταρο. 512 00:21:27,100 --> 00:21:29,855 Αλλά τι θα γινόταν αν η κορυφή ένα-- το κάτω μέρος κάποιου 513 00:21:29,855 --> 00:21:32,230 πρόκειται να είναι μηδενική, γιατί δεν υπάρχει Davenport ακριβώς ακόμα. 514 00:21:32,230 --> 00:21:34,197 Τι θα συμβεί αν η κορυφή ενός είναι κάποια ιδιαίτερη αξία; 515 00:21:34,197 --> 00:21:36,530 Και αυτό πρόκειται να είναι μια μικρή σκληρά για να είναι αυτό το μέγεθος επιστήσει. 516 00:21:36,530 --> 00:21:38,130 Αλλά ας υποθέσουμε ότι είναι απλά ένα σημάδι ελέγχου. 517 00:21:38,130 --> 00:21:38,920 Ελέγξτε. 518 00:21:38,920 --> 00:21:44,230 D-Α-V-Ε-Ν είναι ένα string σε αυτή τη δομή δεδομένων. 519 00:21:44,230 --> 00:21:48,350 >> Εν τω μεταξύ, αν είχα περισσότερο χώρο εδώ, θα μπορούσα να κάνω Ρ-Ο-Ρ-Τ, 520 00:21:48,350 --> 00:21:52,650 και θα μπορούσα να βάλω το check-in κόμβο που έχει το γράμμα Τ στο τέλος. 521 00:21:52,650 --> 00:21:55,460 Έτσι, αυτό είναι ένα μαζικά σύνθετη-αναζητούν δομή δεδομένων. 522 00:21:55,460 --> 00:21:57,210 Και το χειρόγραφό μου σίγουρα δεν βοηθά. 523 00:21:57,210 --> 00:22:00,043 Αλλά αν ήθελα να τοποθετήσετε κάτι αλλιώς, σκεφτείτε τι θα κάνουμε. 524 00:22:00,043 --> 00:22:03,370 Αν θέλαμε να βάλει ο David στο, είχαμε ακολουθήσει την ίδια λογική, D-Α-V, 525 00:22:03,370 --> 00:22:08,802 αλλά τώρα θα ήθελα να επισημάνω στην επόμενη στοιχείο όχι από Ε, αλλά από Ι Δ 526 00:22:08,802 --> 00:22:10,760 Έτσι, εκεί πρόκειται να είναι περισσότερους κόμβους σε αυτό το δέντρο. 527 00:22:10,760 --> 00:22:12,325 Εμείς πάμε για να έχουν malloc κλήση περισσότερο. 528 00:22:12,325 --> 00:22:14,700 Αλλά δεν θέλω να κάνω μια πλήρες χάος αυτής της εικόνας. 529 00:22:14,700 --> 00:22:17,710 Ας δούμε, αντί σε ένα που είναι ήδη προ-διαμορφωθεί 530 00:22:17,710 --> 00:22:21,810 όπως αυτό με όχι τελεία, τελεία, τελείες, αλλά μόνο συντετμημένη συστοιχίες. 531 00:22:21,810 --> 00:22:23,950 Αλλά κάθε ένα από τους κόμβους σε αυτό το δέντρο μέχρι εδώ 532 00:22:23,950 --> 00:22:26,700 αντιπροσωπεύει την ίδια thing-- μια σειρά Ray μεγέθους 26. 533 00:22:26,700 --> 00:22:28,860 >> Ή αν θέλουμε να είμαστε πραγματικά σωστή τώρα, τι 534 00:22:28,860 --> 00:22:30,790 αν το όνομα κάποιου ατόμου ως μια απόστροφο, ας 535 00:22:30,790 --> 00:22:35,560 υποθέσουμε ότι κάθε κόμβος έχει στην πραγματικότητα όπως και 27 ευρετήρια σε αυτό, όχι μόνο 26. 536 00:22:35,560 --> 00:22:42,020 Μέχρι τώρα αυτό πρόκειται να είναι ένας δεδομένα δομή ονομάζεται trie-- Τ-Κ-Ι-Ε. 537 00:22:42,020 --> 00:22:46,120 Ένα trie, η οποία υποτίθεται ότι είναι ιστορικά ένα έξυπνο όνομα για ένα δέντρο 538 00:22:46,120 --> 00:22:49,040 που είναι βελτιστοποιημένη για ανάκτησης, η οποία φυσικά, 539 00:22:49,040 --> 00:22:50,870 γράφεται με Ι-Ε έτσι είναι trie. 540 00:22:50,870 --> 00:22:52,710 Αλλά αυτή είναι η ιστορία του trie. 541 00:22:52,710 --> 00:22:55,860 >> Έτσι, ένα trie είναι αυτό το δέντρο-όπως δεδομένα δομή, όπως ένα οικογενειακό δέντρο 542 00:22:55,860 --> 00:22:57,510 ότι συμπεριφέρεται τελικά σαν αυτό. 543 00:22:57,510 --> 00:23:00,890 Και εδώ είναι απλώς άλλο ένα παράδειγμα ενός σωρό ονόματα άλλων ανθρώπων. 544 00:23:00,890 --> 00:23:03,540 Αλλά το ερώτημα τώρα στο χέρι είναι ό, τι έχουν 545 00:23:03,540 --> 00:23:08,070 έχουμε αποκτήσει με την εισαγωγή αναμφισβήτητα μια πιο πολύπλοκη δομή δεδομένων, και ένα, 546 00:23:08,070 --> 00:23:09,870 ειλικρινά, ότι χρησιμοποιεί πολλή μνήμη. 547 00:23:09,870 --> 00:23:11,703 >> Διότι ακόμη και αν, αυτή τη στιγμή, είμαι μόνο 548 00:23:11,703 --> 00:23:15,050 χρησιμοποιώντας το δείκτη του D's και Α και V και Ες και της NS, 549 00:23:15,050 --> 00:23:16,700 Είμαι σπατάλη ένα καλό των πολύ μνήμη. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Αλλά πού θα περάσουν έναν πόρο, Τείνω να μην κερδίσει πίσω ένα άλλο. 552 00:23:22,660 --> 00:23:26,020 Έτσι, αν ξοδεύω περισσότερο χώρο, τι είναι ίσως η ελπίδα; 553 00:23:26,020 --> 00:23:27,407 Ότι είμαι ξοδεύουν λιγότερο, τι; 554 00:23:27,407 --> 00:23:28,240 ΚΟΙΝΟ: Λιγότερο χρόνο. 555 00:23:28,240 --> 00:23:28,990 DAVID Malan: Ώρα. 556 00:23:28,990 --> 00:23:30,320 Τώρα γιατί θα μπορούσε αυτό να είναι; 557 00:23:30,320 --> 00:23:33,880 Λοιπόν, ποια είναι η εισαγωγή χρόνο, από την άποψη των μεγάλων O τώρα, 558 00:23:33,880 --> 00:23:37,660 από ένα όνομα όπως Daven ή Davenport ή Δαβίδ; 559 00:23:37,660 --> 00:23:39,340 Λοιπόν, Daven ήταν πέντε βήματα. 560 00:23:39,340 --> 00:23:42,350 Davenport θα είναι εννέα βήματα, οπότε θα ήταν μερικά ακόμη βήματα. 561 00:23:42,350 --> 00:23:44,250 Ο David θα είναι πέντε βήματα, καθώς και. 562 00:23:44,250 --> 00:23:47,230 Έτσι, αυτές είναι συγκεκριμένες αριθμούς, αλλά σίγουρα υπάρχει 563 00:23:47,230 --> 00:23:49,550 ένα άνω φράγμα για το μήκος του ονόματος κάποιου. 564 00:23:49,550 --> 00:23:52,240 Και πράγματι, το πρόβλημα σύνολα των πέντε προδιαγραφής, 565 00:23:52,240 --> 00:23:54,050 θα πάμε να προτείνει ότι αυτό είναι κάτι 566 00:23:54,050 --> 00:23:55,470 ότι είναι 40-μερικοί-περίεργο χαρακτήρες. 567 00:23:55,470 --> 00:23:58,180 >> Ρεαλιστικά, κανείς δεν έχει ένα απείρως μεγάλο όνομα, 568 00:23:58,180 --> 00:24:01,542 το οποίο είναι να πούμε ότι το μήκος ενός το όνομα ή το μήκος μιας συμβολοσειράς θα μπορούσαμε 569 00:24:01,542 --> 00:24:03,750 έχουν ορισμένα η κατάσταση της δομής είναι αναμφισβήτητα ό, τι; 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Είναι σταθερή. 572 00:24:06,250 --> 00:24:06,430 Σωστά; 573 00:24:06,430 --> 00:24:09,310 Θα μπορούσε να είναι μια μεγάλη σταθερά, όπως 40-κάτι, αλλά είναι σταθερή. 574 00:24:09,310 --> 00:24:13,752 Και δεν έχει καμία εξάρτηση από το πόσες άλλα ονόματα είναι σε αυτή τη δομή δεδομένων. 575 00:24:13,752 --> 00:24:15,460 Με άλλα λόγια, αν μου ήθελε να εισάγετε τώρα 576 00:24:15,460 --> 00:24:20,540 Colton ή Γαβριήλ ή Rob ή Zamyla ή Alison ή Μπελίντα ή οποιαδήποτε άλλα ονόματα 577 00:24:20,540 --> 00:24:23,940 από το προσωπικό σε αυτά τα δεδομένα δομή, είναι ο χρόνος τρέχει 578 00:24:23,940 --> 00:24:26,750 της εισάγοντας άλλα ονόματα πρόκειται να είναι καθόλου κρούση 579 00:24:26,750 --> 00:24:30,220 από το πόσο πολλά άλλα στοιχεία είναι στη δομή των δεδομένων που έχουν ήδη; 580 00:24:30,220 --> 00:24:31,040 Δεν είναι. 581 00:24:31,040 --> 00:24:31,540 Σωστά; 582 00:24:31,540 --> 00:24:36,150 Επειδή είμαστε η αποτελεσματική χρήση των Αυτό το hash πίνακα πολλαπλών στρωμάτων. 583 00:24:36,150 --> 00:24:38,280 Και ο χρόνος εκτέλεσης του οποιαδήποτε από αυτές τις εργασίες 584 00:24:38,280 --> 00:24:41,510 δεν εξαρτάται από τον αριθμό των στοιχεία που βρίσκονται στη δομή δεδομένων 585 00:24:41,510 --> 00:24:43,090 ή ότι τελικά θα να είναι στη δομή δεδομένων, 586 00:24:43,090 --> 00:24:44,714 αλλά το μήκος του τι ειδικώς; 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Το κορδόνι είναι εισαχθεί, το οποίο κάνει 589 00:24:49,200 --> 00:24:52,580 Αυτό ασυμπτωτικά σταθερό time-- μεγάλη O ενός. 590 00:24:52,580 --> 00:24:54,720 Και ειλικρινά, μόνο σε το πραγματικό κόσμο, αυτό 591 00:24:54,720 --> 00:24:58,380 σημαίνει εισάγοντας το όνομα Daven παίρνει σαν πέντε βήματα, ή εννέα Davenport 592 00:24:58,380 --> 00:25:00,100 βήματα, ή Δαβίδ πέντε βήματα. 593 00:25:00,100 --> 00:25:03,071 Αυτό είναι αρκετά καταριέται μικρούς χρόνους λειτουργίας. 594 00:25:03,071 --> 00:25:05,320 Και, πράγματι, αυτό είναι ένα πολύ καλό πράγμα, ειδικά όταν 595 00:25:05,320 --> 00:25:08,126 δεν είναι εξαρτάται από την συνολική αριθμός των στοιχείων εκεί. 596 00:25:08,126 --> 00:25:10,500 Λοιπόν, πώς θα μπορούσαμε να εφαρμόσουμε το είδος της δομής στον κώδικα; 597 00:25:10,500 --> 00:25:12,900 Είναι λίγο πιο πολύπλοκο, αλλά εξακολουθεί να είναι 598 00:25:12,900 --> 00:25:15,050 απλά μια εφαρμογή βασικά δομικά στοιχεία. 599 00:25:15,050 --> 00:25:17,830 Πάω να επαναπροσδιορίσει κόμβος μας ως εξής: 600 00:25:17,830 --> 00:25:21,100 bool ονομάζεται word-- και αυτό θα μπορούσε να ονομάζεται τίποτα. 601 00:25:21,100 --> 00:25:23,970 Αλλά η bool αντιπροσωπεύει αυτό που μου επέστησε ως ένα σημάδι ελέγχου. 602 00:25:23,970 --> 00:25:24,490 Ναι. 603 00:25:24,490 --> 00:25:26,720 Αυτό είναι το τέλος μιας συμβολοσειράς σε αυτή τη δομή δεδομένων. 604 00:25:26,720 --> 00:25:30,702 >> Και, φυσικά, το αστέρι κόμβος υπάρχει αναφορά για τα παιδιά. 605 00:25:30,702 --> 00:25:32,410 Και, πράγματι, ήθελε απλά ένα οικογενειακό δέντρο, σας 606 00:25:32,410 --> 00:25:34,370 θα εξετάσει τους κόμβους που κρέμονται από 607 00:25:34,370 --> 00:25:36,920 του πυθμένα κάποιου γονέα στοιχείο για να είναι τα παιδιά. 608 00:25:36,920 --> 00:25:40,510 Και έτσι τα παιδιά πρόκειται να είναι ένας πίνακας του 27, το 27ο το ένα 609 00:25:40,510 --> 00:25:41,680 απλά να είναι για την απόστροφο. 610 00:25:41,680 --> 00:25:43,390 Εμείς πάμε για να ταξινομήσετε της ειδικής περίπτωσης αυτής. 611 00:25:43,390 --> 00:25:45,400 Έτσι μπορείτε να έχετε ορισμένους ονόματα με αποστρόφους. 612 00:25:45,400 --> 00:25:47,399 Ίσως ακόμη και παύλα θα πρέπει πάω εκεί, αλλά θα 613 00:25:47,399 --> 00:25:50,330 δείτε το σύνολο P 5 έχουμε μόνο φροντίδα σχετικά με γράμματα και αποστρόφους. 614 00:25:50,330 --> 00:25:52,990 >> Και τότε πώς θα αντιπροσωπεύουν η ίδια η δομή δεδομένων; 615 00:25:52,990 --> 00:25:56,454 Πώς μπορείτε να αντιπροσωπεύουν τη ρίζα αυτής trie, να το πω έτσι; 616 00:25:56,454 --> 00:25:59,620 Λοιπόν, ήθελα απλά με μια συνδεδεμένη λίστα, μπορείτε χρειάζεται ένα δείκτη προς το πρώτο στοιχείο. 617 00:25:59,620 --> 00:26:04,270 Με ένα trie χρειάζεστε μόνο ένα δείκτη στη ρίζα αυτής της trie. 618 00:26:04,270 --> 00:26:07,290 Και από εκεί μπορείτε να hash το δρόμο σας προς τα κάτω όλο και βαθύτερα 619 00:26:07,290 --> 00:26:10,460 σε κάθε άλλο κόμβο στη δομή. 620 00:26:10,460 --> 00:26:13,440 Έτσι, απλά με αυτό μπορεί να εμείς εκπροσωπούμε αυτό το struct. 621 00:26:13,440 --> 00:26:15,877 >> Τώρα Meanwhile-- Ω, ερώτηση. 622 00:26:15,877 --> 00:26:17,220 >> ΚΟΙΝΟ: Τι είναι λέξη bool; 623 00:26:17,220 --> 00:26:20,490 >> DAVID Malan: λέξη Bool είναι ακριβώς αυτή η ενσάρκωση C 624 00:26:20,490 --> 00:26:22,920 από ό, τι περιέγραψα σε αυτό το πλαίσιο εδώ, όταν 625 00:26:22,920 --> 00:26:26,000 Άρχισα χωρίζοντας το καθένα από τα στοιχεία συστοιχίας σε δύο κομμάτια. 626 00:26:26,000 --> 00:26:27,600 Το ένα είναι ένας δείκτης στον επόμενο κόμβο. 627 00:26:27,600 --> 00:26:30,280 Το άλλο πρέπει να είναι κάτι σαν ένα κουτί ελέγχου 628 00:26:30,280 --> 00:26:33,770 να πω ναι, υπάρχει μια Daven λέξη που τελειώνει εδώ, 629 00:26:33,770 --> 00:26:35,610 γιατί δεν θέλουμε, αυτή τη στιγμή, ο Dave. 630 00:26:35,610 --> 00:26:39,320 >> Ακόμα κι αν ο Dave πρόκειται να είναι μια νόμιμη λέξη, αυτός δεν είναι στην trie 631 00:26:39,320 --> 00:26:39,830 ακόμα. 632 00:26:39,830 --> 00:26:40,950 Και D δεν είναι μια λέξη. 633 00:26:40,950 --> 00:26:42,770 Και D-Α δεν είναι μια λέξη ή ένα όνομα. 634 00:26:42,770 --> 00:26:45,020 Έτσι, το σήμα ελέγχου δείχνει μόνο τη στιγμή που θα 635 00:26:45,020 --> 00:26:48,190 χτύπησε ο κόμβος αυτός είναι ο προηγούμενη πορεία των χαρακτήρων 636 00:26:48,190 --> 00:26:50,700 πραγματικά ένα string που έχετε εισάγει. 637 00:26:50,700 --> 00:26:53,660 Έτσι, αυτό είναι όλο το bool είναι εκεί να κάνει για εμάς. 638 00:26:53,660 --> 00:26:55,500 >> Οποιεσδήποτε άλλες ερωτήσεις σχετικά προσπαθεί; 639 00:26:55,500 --> 00:26:56,215 Ναι. 640 00:26:56,215 --> 00:26:58,035 >> ΚΟΙΝΟ: Ποια είναι η επικάλυψη; 641 00:26:58,035 --> 00:26:59,945 Τι γίνεται αν έχετε ένα Ντέιβ και Daven; 642 00:26:59,945 --> 00:27:00,820 DAVID Malan: Τέλεια. 643 00:27:00,820 --> 00:27:02,580 Τι γίνεται αν έχετε ένα Ντέιβ και Daven; 644 00:27:02,580 --> 00:27:06,240 Έτσι αν εισάγουμε, να πω ένα ψευδώνυμο, για David-- Dave-- D-Α-V-Ε; 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Αυτό είναι στην πραγματικότητα εξαιρετικά απλή. 647 00:27:08,700 --> 00:27:10,325 Έτσι είμαστε μόνο πρόκειται να διαρκέσει τέσσερα βήματα. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-Α-V-E. Και τι πρέπει να κάνω κάνουμε μια φορά χτύπησα ότι η τέταρτη κόμβο; 650 00:27:15,847 --> 00:27:16,680 Απλά πρόκειται να ελέγξει. 651 00:27:16,680 --> 00:27:18,000 Είμαστε ήδη καλό να πάει. 652 00:27:18,000 --> 00:27:18,840 Έγινε. 653 00:27:18,840 --> 00:27:19,750 Τέσσερα στάδια. 654 00:27:19,750 --> 00:27:21,590 Σταθερή χρόνο ασυμπτωτικά. 655 00:27:21,590 --> 00:27:26,300 Και τώρα έχουμε δηλώσει ότι τόσο ο Dave και Daven είναι χορδές στη δομή. 656 00:27:26,300 --> 00:27:27,710 Έτσι, δεν αποτελεί πρόβλημα. 657 00:27:27,710 --> 00:27:30,200 Και παρατηρήστε πώς η παρουσία της Daven δεν το κάνει 658 00:27:30,200 --> 00:27:34,750 να λάβει περισσότερο χρόνο ή λιγότερο χρόνο για τον Dave και το αντίστροφο. 659 00:27:34,750 --> 00:27:36,000 >> Λοιπόν, τι άλλο μπορούμε να κάνουμε τώρα; 660 00:27:36,000 --> 00:27:40,680 Έχουμε χρησιμοποιήσει αυτήν την παρομοίωση πριν των δίσκων που αντιπροσωπεύουν κάτι. 661 00:27:40,680 --> 00:27:43,380 Αλλά αποδεικνύεται ότι ένα στοίβα των δίσκων είναι στην πραγματικότητα 662 00:27:43,380 --> 00:27:47,187 εκδηλωτικός άλλου αφηρημένων στοιχείων type-- ένα υψηλότερο επίπεδο δομής δεδομένων 663 00:27:47,187 --> 00:27:49,770 ότι στο τέλος της ημέρας είναι ακριβώς σαν μια σειρά ή μια συνδεδεμένη λίστα 664 00:27:49,770 --> 00:27:50,970 ή κάτι πιο πεζά. 665 00:27:50,970 --> 00:27:53,270 Αλλά είναι μια πιο ενδιαφέρουσα εννοιολογική αντίληψη. 666 00:27:53,270 --> 00:27:56,440 Μια στοίβα, όπως αυτές Θήκες εδώ στο Mather, 667 00:27:56,440 --> 00:27:58,750 γενικά ονομάζονται απλά that-- μια στοίβα. 668 00:27:58,750 --> 00:28:02,540 >> Και σε αυτό το είδος της δομής δεδομένων έχετε δύο operations-- 669 00:28:02,540 --> 00:28:05,880 έχετε ένα ονομάζεται ώθηση για προσθέτοντας κάτι στη στοίβα, 670 00:28:05,880 --> 00:28:08,320 σαν να βάζουμε άλλο δίσκο αντίγραφα στην κορυφή της στοίβας. 671 00:28:08,320 --> 00:28:11,350 Και τότε ποπ, η οποία θα σημαίνει λαμβάνει το ανώτερο δίσκο μακριά. 672 00:28:11,350 --> 00:28:16,210 Αλλά τι είναι κλειδί για μια στοίβα είναι ότι αυτό πήρε αυτό το περίεργο χαρακτηριστικό. 673 00:28:16,210 --> 00:28:19,560 Καθώς το προσωπικό τραπεζαρία είναι αναδιατάσσοντας τους δίσκους για το επόμενο γεύμα, 674 00:28:19,560 --> 00:28:21,380 τι πρόκειται να είναι αλήθεια για το πώς οι μαθητές 675 00:28:21,380 --> 00:28:22,856 αλληλεπιδρούν με αυτή τη δομή δεδομένων; 676 00:28:22,856 --> 00:28:24,480 ΚΟΙΝΟ: Θα πάμε να σκάσει εφάπαξ. 677 00:28:24,480 --> 00:28:26,550 DAVID Malan: Θα πάμε να pop εφάπαξ, ελπίζω, την κορυφή. 678 00:28:26,550 --> 00:28:28,910 Διαφορετικά είναι ακριβώς το είδος της ηλίθια να πάνε όλα το δρόμο προς τα κάτω. 679 00:28:28,910 --> 00:28:29,070 Σωστά; 680 00:28:29,070 --> 00:28:31,620 Η δομή δεδομένων που πραγματικά δεν επιτρέπουν μπορείτε να αρπάξει την κάτω δίσκο τουλάχιστον 681 00:28:31,620 --> 00:28:32,520 εύκολα. 682 00:28:32,520 --> 00:28:35,040 Έτσι, υπάρχει αυτό το περίεργο ιδιοκτησίας σε μια στοίβα 683 00:28:35,040 --> 00:28:39,730 ότι το τελευταίο στοιχείο είναι πρόκειται να είναι η πρώτη έξω. 684 00:28:39,730 --> 00:28:43,400 Και οι επιστήμονες υπολογιστών καλέστε Αυτό LIFO-- διαρκέσει in, first out. 685 00:28:43,400 --> 00:28:45,540 Και αυτό πραγματικά δεν έχει ενδιαφέρουσες εφαρμογές. 686 00:28:45,540 --> 00:28:50,090 Δεν είναι κατ 'ανάγκην τόσο προφανής όσο μερικοί άλλους, αλλά μπορεί, πράγματι, να είναι χρήσιμα, 687 00:28:50,090 --> 00:28:54,040 και μπορεί, πράγματι, να εφαρμοστεί σε μια-δυο διαφορετικούς τρόπους. 688 00:28:54,040 --> 00:28:58,550 >> Έτσι μία, και στην πραγματικότητα, ας μου να μην βουτήξει σε αυτό. 689 00:28:58,550 --> 00:28:59,860 Ας κάνουμε αυτό αντ 'αυτού. 690 00:28:59,860 --> 00:29:03,700 Ας ρίξουμε μια ματιά σε αυτό που είναι σχεδόν το ίδια ιδέα, αλλά είναι λίγο πιο δίκαιη. 691 00:29:03,700 --> 00:29:04,200 Σωστά; 692 00:29:04,200 --> 00:29:07,560 Αν είστε ένας από αυτούς αγόρια ανεμιστήρα ή τα κορίτσια που του αρέσει πραγματικά τα προϊόντα της Apple 693 00:29:07,560 --> 00:29:10,130 και σας ξύπνησε στις 3:00 π.μ. να παρατάξει σε κάποιο κατάστημα 694 00:29:10,130 --> 00:29:14,150 για να πάρετε την πολύ τελευταίες iPhone, μπορείτε θα μπορούσαν να έχουν ουρά σαν αυτό. 695 00:29:14,150 --> 00:29:15,800 >> Τώρα μια ουρά είναι πολύ σκόπιμα το όνομα. 696 00:29:15,800 --> 00:29:18,190 Είναι μια γραμμή επειδή υπάρχει κάποια δικαιοσύνη σ 'αυτό. 697 00:29:18,190 --> 00:29:18,690 Σωστά; 698 00:29:18,690 --> 00:29:21,690 Είναι το είδος του θα αναρροφάται αν έχετε πήρε εκεί πρώτα στο Apple Store 699 00:29:21,690 --> 00:29:25,700 αλλά είστε αποτελεσματικά το κατώτατο δίσκο, επειδή οι εργαζόμενοι της Apple στη συνέχεια, 700 00:29:25,700 --> 00:29:28,189 ποπ το τελευταίο πρόσωπο που πήρε πραγματικά στην γραμμή. 701 00:29:28,189 --> 00:29:31,230 Έτσι, στοίβες και ουρές, ακόμη και αν λειτουργικά από όπου και αν το είδος του same-- 702 00:29:31,230 --> 00:29:33,105 είναι ακριβώς αυτή η συλλογή των πόρων που είναι 703 00:29:33,105 --> 00:29:36,210 πρόκειται να αυξηθεί και shrink-- του εκεί Αυτή η πτυχή της δικαιοσύνης σε αυτό, 704 00:29:36,210 --> 00:29:39,634 τουλάχιστον στον πραγματικό κόσμο, όπου οι εργασίες που ασκούν 705 00:29:39,634 --> 00:29:40,800 είναι ριζικά διαφορετικές. 706 00:29:40,800 --> 00:29:43,360 Μια stack-- μια ουρά rather-- λέγεται για να έχει 707 00:29:43,360 --> 00:29:45,320 δύο λειτουργίες: n ουρά και δ ουρά. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Ή μπορείτε να καλέσετε πολλά πράγματα. 710 00:29:48,090 --> 00:29:50,770 Αλλά απλά θέλετε να συλλάβει η αντίληψη ότι μία είναι η προσθήκη 711 00:29:50,770 --> 00:29:53,230 και ένα τελικά αφαίρεση. 712 00:29:53,230 --> 00:29:58,840 >> Τώρα κάτω από την κουκούλα, τόσο η στοίβα και μια ουρά θα μπορούσε να υλοποιηθεί με ποιον τρόπο; 713 00:29:58,840 --> 00:30:01,390 Εμείς δεν θα πάμε στον κώδικα του επειδή το υψηλότερο επίπεδο 714 00:30:01,390 --> 00:30:03,387 ιδέα είναι είδος πιο προφανής. 715 00:30:03,387 --> 00:30:04,470 Θέλω να πω, τι κάνουν οι άνθρωποι; 716 00:30:04,470 --> 00:30:07,030 Αν είμαι το πρώτο πρόσωπο στην Μήλο Αποθηκεύστε και αυτή είναι η μπροστινή πόρτα, 717 00:30:07,030 --> 00:30:08,130 Ξέρετε, εγώ είμαι πρόκειται να σταθεί εδώ. 718 00:30:08,130 --> 00:30:09,750 Και η επόμενη ατόμου πρόκειται να σταθεί εδώ. 719 00:30:09,750 --> 00:30:11,500 Και η επόμενη ατόμου πρόκειται να σταθεί εδώ. 720 00:30:11,500 --> 00:30:13,792 Λοιπόν, τι δομή δεδομένων προσφέρεται σε μια ουρά; 721 00:30:13,792 --> 00:30:14,542 >> ΚΟΙΝΟ: Μια ουρά. 722 00:30:14,542 --> 00:30:15,667 DAVID Malan: Λοιπόν, μια ουρά. 723 00:30:15,667 --> 00:30:16,390 Σίγουρα. 724 00:30:16,390 --> 00:30:16,920 Τι άλλο; 725 00:30:16,920 --> 00:30:17,600 >> ΚΟΙΝΟ: Μια συνδεδεμένη λίστα. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Malan: Ένα συνδεδεμένο λίστα θα μπορούσε να εφαρμόσει. 727 00:30:18,990 --> 00:30:22,500 Και μια συνδεδεμένη λίστα είναι ωραίο, διότι τότε μπορεί να αυξηθεί αυθαίρετα μεγάλη αντίθεση 728 00:30:22,500 --> 00:30:24,880 να έχουν κάποιο σταθερό αριθμό των ανθρώπων στο κατάστημα. 729 00:30:24,880 --> 00:30:27,030 Αλλά ίσως ένα σταθερό αριθμό των θέσεων είναι νόμιμη. 730 00:30:27,030 --> 00:30:30,350 Διότι, αν έχουν μόνο σαν 20 iphones την πρώτη ημέρα, ίσως 731 00:30:30,350 --> 00:30:33,930 που χρειάζονται μόνο ένα πίνακα μεγέθους 20 να εκπροσωπεί την ουρά, η οποία 732 00:30:33,930 --> 00:30:37,070 μόνο να πω τώρα μόλις αρχίζουμε να μιλάμε σχετικά με αυτές τις υψηλότερες προβλήματα επίπεδο, 733 00:30:37,070 --> 00:30:38,890 μπορείτε να το εφαρμόσει σε οποιοδήποτε αριθμό τρόπων. 734 00:30:38,890 --> 00:30:42,030 Και υπάρχει πιθανώς ακριβώς πρόκειται να είναι ένα εμπόριο μακριά στο χώρο και το χρόνο 735 00:30:42,030 --> 00:30:43,950 ή μόνο στο δικό σας κώδικα πολυπλοκότητα. 736 00:30:43,950 --> 00:30:45,380 >> Τι γίνεται με μια στοίβα; 737 00:30:45,380 --> 00:30:48,190 Λοιπόν, μια στοίβα, έχουμε δει πάρα πολύ θα μπορούσε απλώς να είναι αυτοί οι δίσκοι. 738 00:30:48,190 --> 00:30:50,007 Και θα μπορούσε να εφαρμόσει αυτό μια σειρά. 739 00:30:50,007 --> 00:30:53,090 Αλλά σε κάποιο σημείο, αν χρησιμοποιείτε μια συστοιχία, τι πρόκειται να συμβεί με τους δίσκους 740 00:30:53,090 --> 00:30:54,173 προσπαθείτε να βάλετε κάτω; 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Εντάξει. 743 00:30:55,670 --> 00:30:57,490 Είστε μόνο πρόκειται να να είναι σε θέση να πάει τόσο ψηλά. 744 00:30:57,490 --> 00:31:00,156 Και νομίζω ότι στην Mather ότι είναι πραγματικά εσοχή σε εκείνο το άνοιγμα. 745 00:31:00,156 --> 00:31:01,950 Έτσι, πράγματι, είναι σχεδόν όπως Mather χρησιμοποιεί 746 00:31:01,950 --> 00:31:03,783 μία συστοιχία σταθερού μεγέθους, επειδή μπορείτε μόνο 747 00:31:03,783 --> 00:31:08,302 χωρέσει τόσα πολλά δίσκους σε αυτό το άνοιγμα στην ο τοίχος κάτω από τα γόνατα των ανθρώπων. 748 00:31:08,302 --> 00:31:10,010 Και έτσι ώστε να μπορεί να λέγεται ότι είναι ένας πίνακας, 749 00:31:10,010 --> 00:31:14,300 αλλά θα μπορούσαμε βεβαίως να εφαρμόσουν ότι γενικότερα με μια συνδεδεμένη λίστα. 750 00:31:14,300 --> 00:31:16,390 >> Λοιπόν, τι γίνεται με άλλη δομή δεδομένων; 751 00:31:16,390 --> 00:31:18,760 Επιτρέψτε μου να σηκώσει μια άλλη οπτική εδώ. 752 00:31:18,760 --> 00:31:24,710 Κάτι σαν σχετικά με το πώς αυτό εδώ; 753 00:31:24,710 --> 00:31:28,920 Γιατί μπορεί να είναι χρήσιμο να μην έχουν κάτι σαν φανταχτερό ως trie, η οποία 754 00:31:28,920 --> 00:31:32,370 είδαμε είχε αυτές τις πολύ μεγάλη κόμβους, καθένα από τα οποία βρίσκεται σε μία συστοιχία; 755 00:31:32,370 --> 00:31:35,740 Αλλά ό, τι και αν κάνουμε κάτι περισσότερο απλά, σαν ένα παλιό οικογενειακό δέντρο του σχολείου, 756 00:31:35,740 --> 00:31:38,110 καθένας εκ των οποίων οι κόμβοι εδώ μόλις αποθήκευση ενός αριθμού. 757 00:31:38,110 --> 00:31:42,180 Αντί για ένα όνομα ή έναν απόγονο μόλις την αποθήκευση ενός αριθμού, όπως αυτό. 758 00:31:42,180 --> 00:31:45,250 >> Λοιπόν, η ορολογία που χρησιμοποιούμε σε δομών δεδομένων που είναι και οι δύο προσπάθειες 759 00:31:45,250 --> 00:31:49,510 και δέντρα, όπου ένα trie, και πάλι, είναι μόνο ένα οποίου οι κόμβοι είναι συστοιχίες, 760 00:31:49,510 --> 00:31:51,680 εξακολουθεί να είναι αυτό που θα μπορούσε χρησιμοποιούν από το δημοτικό 761 00:31:51,680 --> 00:31:53,860 όταν κάνατε μια οικογένεια tree-- φύλλα και η ρίζα 762 00:31:53,860 --> 00:31:57,250 του δέντρου και τα παιδιά του γονέα και τα αδέλφια τους. 763 00:31:57,250 --> 00:32:03,670 Και θα μπορούσαμε να εφαρμόσουν ένα δέντρο, για παράδειγμα, ως απλά ως αυτό. 764 00:32:03,670 --> 00:32:07,420 Ένα δέντρο, αν ως κόμβος, ένας από Αυτοί οι κύκλοι που έχει ένα αριθμό, 765 00:32:07,420 --> 00:32:09,947 δεν πρόκειται να έχουν ένα δείκτη, αλλά δύο. 766 00:32:09,947 --> 00:32:11,780 Και το συντομότερο μπορείτε να προσθέσετε ένα δεύτερο δείκτη, 767 00:32:11,780 --> 00:32:13,905 μπορεί πραγματικά να κάνει τώρα το είδος δύο διαστάσεων δεδομένα 768 00:32:13,905 --> 00:32:14,780 δομές στη μνήμη. 769 00:32:14,780 --> 00:32:16,660 Μοιάζει πολύ με ένα δισδιάστατο σειρά, μπορείτε να 770 00:32:16,660 --> 00:32:18,904 έχουν το είδος των δύο διαστάσεων συνδεδεμένες λίστες, αλλά αυτά 771 00:32:18,904 --> 00:32:20,820 ότι ακολουθούν ένα μοτίβο όπου δεν υπάρχει κύκλους. 772 00:32:20,820 --> 00:32:24,487 Είναι πραγματικά ένα δέντρο με ένα παππούς και γιαγιά δρόμο μέχρι εδώ και, στη συνέχεια, 773 00:32:24,487 --> 00:32:27,320 μερικοί γονείς και παιδιά και εγγόνια και δισέγγονα. 774 00:32:27,320 --> 00:32:28,370 και ούτω καθεξής. 775 00:32:28,370 --> 00:32:32,390 >> Αλλά τι είναι πραγματικά τακτοποιημένο για αυτό πάρα πολύ, απλά για να σας πειράζω με ένα κομμάτι του κώδικα, 776 00:32:32,390 --> 00:32:35,370 ανάκληση αναδρομή από λίγο πίσω, σύμφωνα με την οποία 777 00:32:35,370 --> 00:32:38,220 να γράψετε μια συνάρτηση που καλεί τον εαυτό της. 778 00:32:38,220 --> 00:32:41,140 Αυτή είναι μια όμορφη ευκαιρία να εφαρμόσει κάτι 779 00:32:41,140 --> 00:32:42,920 όπως η αναδρομή, επειδή θεωρούν αυτό. 780 00:32:42,920 --> 00:32:43,860 >> Αυτό είναι ένα δέντρο. 781 00:32:43,860 --> 00:32:48,040 Και έχω μια μικρή πρωκτική με το πώς Έβαλα τα ακέραιοι στο δρόμο. 782 00:32:48,040 --> 00:32:51,020 Τόσο μεγάλο μέρος έτσι ώστε να έχει μια ειδική name-- ένα δυαδικό δέντρο αναζήτησης. 783 00:32:51,020 --> 00:32:53,460 Τώρα έχουμε ακούσει δυαδικό αναζήτησης, αλλά μπορεί να σας 784 00:32:53,460 --> 00:32:55,180 εργάζονται πίσω από το όνομα αυτό το πράγμα; 785 00:32:55,180 --> 00:32:59,280 Ποιο είναι το σχέδιο για το πώς θα παρεμβάλλονται οι ακέραιοι σε αυτό το δέντρο; 786 00:32:59,280 --> 00:33:00,696 Δεν είναι αυθαίρετη. 787 00:33:00,696 --> 00:33:01,570 Υπάρχει κάποιο μοτίβο. 788 00:33:01,570 --> 00:33:02,090 Ναι. 789 00:33:02,090 --> 00:33:03,370 >> ΚΟΙΝΟ: μικρότερα στα αριστερά. 790 00:33:03,370 --> 00:33:03,690 >> DAVID Malan: Ναι. 791 00:33:03,690 --> 00:33:05,062 Μικρότερα βρίσκονται στα αριστερά. 792 00:33:05,062 --> 00:33:06,270 Οι μεγαλύτερες από αυτές είναι στα δεξιά. 793 00:33:06,270 --> 00:33:12,940 Τέτοια ότι μια αληθινή δήλωση είναι μια γονέας είναι μεγαλύτερη από ό, τι το αριστερό παιδί του, 794 00:33:12,940 --> 00:33:14,850 αλλά λιγότερο από το δικαίωμα του παιδιού της. 795 00:33:14,850 --> 00:33:17,750 Και αυτό από μόνο του είναι ακόμη ένα αναδρομικές λεκτική ορισμό 796 00:33:17,750 --> 00:33:20,500 επειδή μπορείτε να εφαρμόσετε ότι ίδια λογική σε κάθε κόμβο 797 00:33:20,500 --> 00:33:23,080 και μόνο πυθμένες έξω, μία βασική περίπτωση, αν 798 00:33:23,080 --> 00:33:25,740 θα είναι, όταν χτύπησε ένα από τα τα φύλλα, να το πω έτσι, 799 00:33:25,740 --> 00:33:28,580 όπου μια άδεια έχει επιπλέον κανένα παιδί. 800 00:33:28,580 --> 00:33:30,614 >> Τώρα πώς μπορεί να σας βρει τον αριθμό 44; 801 00:33:30,614 --> 00:33:32,280 Θα ξεκινούν από τη ρίζα και να πω, hm. 802 00:33:32,280 --> 00:33:35,690 55 δεν είναι 44 Κι εγώ θέλω να πάω δεξιά ή θέλω να πάμε αριστερά; 803 00:33:35,690 --> 00:33:37,190 Λοιπόν, προφανώς θέλετε να πάτε αριστερά. 804 00:33:37,190 --> 00:33:40,060 Και έτσι ακριβώς όπως το τηλέφωνο βιβλίο παράδειγμα σε δυαδική αναζήτηση 805 00:33:40,060 --> 00:33:41,099 γενικότερα. 806 00:33:41,099 --> 00:33:43,390 Αλλά είμαστε το εκτελεστικών τώρα λίγο πιο δυναμικά 807 00:33:43,390 --> 00:33:45,339 από μια σειρά μπορεί να επιτρέψει. 808 00:33:45,339 --> 00:33:48,130 Και στην πραγματικότητα, αν θέλετε να δείτε κατά τον κώδικα, με την πρώτη ματιά σίγουρος. 809 00:33:48,130 --> 00:33:49,671 Μοιάζει με ένα σωρό γραμμές. 810 00:33:49,671 --> 00:33:51,220 Αλλά είναι όμορφα απλό. 811 00:33:51,220 --> 00:33:54,490 Αν θέλετε να υλοποιήσετε μια συνάρτηση που ονομάζεται αναζήτηση των οποίων ο σκοπός στη ζωή 812 00:33:54,490 --> 00:33:57,290 είναι να ψάξει για μια αξία όπως n, ένας ακέραιος αριθμός, 813 00:33:57,290 --> 00:34:01,756 και είστε περάσει σε ένα pointer-- ένα δείκτη στον κόμβο των ριζών, 814 00:34:01,756 --> 00:34:04,380 μάλλον, από αυτό το δέντρο από το οποίο μπορείτε να έχετε πρόσβαση σε όλα τα άλλα, 815 00:34:04,380 --> 00:34:08,850 παρατηρήστε πώς ευθέως μπορείτε να εφαρμόσετε τη λογική. 816 00:34:08,850 --> 00:34:10,880 Αν το δέντρο είναι μηδενική, προφανώς δεν είναι εκεί. 817 00:34:10,880 --> 00:34:11,880 Ας επιστρέψει false. 818 00:34:11,880 --> 00:34:12,000 Σωστά; 819 00:34:12,000 --> 00:34:14,040 Αν το χέρι τίποτα, δεν υπάρχει τίποτα εκεί. 820 00:34:14,040 --> 00:34:17,900 >> Αλλιώς, εάν το η είναι μικρότερο από δέντρο βέλος n-- τώρα arrow n, 821 00:34:17,900 --> 00:34:20,670 Υπενθυμίζουμε εισαγάγαμε σούπερ εν συντομία την άλλη μέρα, 822 00:34:20,670 --> 00:34:25,100 και αυτό σημαίνει ότι μόλις de-αναφοράς για την δείκτη και να εξετάσουμε το πεδίο που ονομάζεται n. 823 00:34:25,100 --> 00:34:27,690 Έτσι, αυτό σημαίνει να πάει εκεί και κοιτάξτε στο πεδίο που ονομάζεται n. 824 00:34:27,690 --> 00:34:33,810 Έτσι, αν n, η τιμή που σας δίνεται, είναι λιγότερο από την τιμή στο ακέραιο δέντρα, 825 00:34:33,810 --> 00:34:35,449 Που θέλετε να πάτε; 826 00:34:35,449 --> 00:34:36,389 Στα αριστερά. 827 00:34:36,389 --> 00:34:37,780 >> Έτσι παρατηρήσετε την αναδρομή. 828 00:34:37,780 --> 00:34:39,860 Είμαι returning-- δεν είναι αλήθεια. 829 00:34:39,860 --> 00:34:40,989 Δεν είναι ψευδείς. 830 00:34:40,989 --> 00:34:45,670 Είμαι επιστρέφουν ανεξάρτητα από την απάντηση είναι από μια κλήση στον εαυτό μου, περνώντας 831 00:34:45,670 --> 00:34:50,100 ένα n ξανά, η οποία είναι περιττή, αλλά αυτό που είναι ελαφρώς διαφορετική τώρα; 832 00:34:50,100 --> 00:34:51,989 Πώς είμαι καθιστώντας το πρόβλημα μικρότερο; 833 00:34:51,989 --> 00:34:54,920 Είμαι περνώντας ως δεύτερη επιχείρημα, δεν είναι η ρίζα του δέντρου, 834 00:34:54,920 --> 00:34:59,616 αλλά το αριστερό παιδί σε αυτή την περίπτωση. 835 00:34:59,616 --> 00:35:00,990 Έτσι περνάω στο αριστερό παιδί. 836 00:35:00,990 --> 00:35:04,720 >> Εν τω μεταξύ, εάν η είναι μεγαλύτερο από ο κόμβος είμαι σήμερα κοιτάζοντας, 837 00:35:04,720 --> 00:35:06,690 Γυρεύω την δεξιά πλευρά. 838 00:35:06,690 --> 00:35:10,880 Αλλιώς, αν το δέντρο δεν είναι μηδενική, και εάν το στοιχείο δεν είναι προς τα αριστερά 839 00:35:10,880 --> 00:35:13,240 και δεν είναι προς τα δεξιά, τι είναι θαυμάσια η περίπτωση; 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Έχουμε βρει πραγματικά τον κόμβο στο ερώτηση, και έτσι επιστρέφουμε αλήθεια. 842 00:35:18,440 --> 00:35:21,490 >> Έτσι έχουμε μόλις γδαρμένο από την επιφάνεια τώρα μερικές από αυτές τις δομές δεδομένων. 843 00:35:21,490 --> 00:35:24,370 Στο πρόβλημα που πέντε που θα διερευνήσει αυτά ακόμη περαιτέρω, 844 00:35:24,370 --> 00:35:27,250 και θα σας δοθεί το σχέδιό σας επιλογή του πώς να πάει για αυτό. 845 00:35:27,250 --> 00:35:30,250 Αυτό που θα ήθελα να ολοκληρώσω με είναι μόλις 30 δευτερολέπτων τρέιλερ 846 00:35:30,250 --> 00:35:32,080 του τι περιμένει την επόμενη εβδομάδα και πέρα. 847 00:35:32,080 --> 00:35:35,390 >> Όπως έχουμε begin-- ευτυχώς ίσως think-- μετάβαση μας σιγά-σιγά 848 00:35:35,390 --> 00:35:38,680 από τον κόσμο της C και κάτω λεπτομέρειες εφαρμογής επίπεδο, 849 00:35:38,680 --> 00:35:42,090 σε έναν κόσμο στον οποίο μπορούμε να πάρουμε για δεδομένο ότι κάποιος άλλος έχει τέλος 850 00:35:42,090 --> 00:35:44,010 εφαρμοστούν αυτά τα δεδομένα δομές για εμάς, 851 00:35:44,010 --> 00:35:47,570 και θα αρχίσουν να καταλαβαίνουν το πραγματικό κόσμο μέσα από την εφαρμογή 852 00:35:47,570 --> 00:35:50,560 web-based προγράμματα και ιστοσελίδες γενικότερα 853 00:35:50,560 --> 00:35:52,910 καθώς επίσης και η ίδια η ασφάλεια επιπτώσεις που έχουμε μόνο 854 00:35:52,910 --> 00:35:54,850 αρχίσει να γρατσουνίσει την επιφάνεια της. 855 00:35:54,850 --> 00:35:57,320 Εδώ είναι τι μας περιμένει στις μέρες που έρχονται. 856 00:35:57,320 --> 00:36:00,480 >> [ΑΝΑΠΑΡΑΓΩΓΗ] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Αυτός Ήρθε με ένα μήνυμα, με ένα πρωτόκολλο όλα δικά του. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Ήρθε σε έναν κόσμο της σκληρής firewalls, routers αδιάφορος, 861 00:36:30,894 --> 00:36:33,368 και κινδύνους πολύ χειρότερη από τον θάνατο. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Είναι γρήγορο. 864 00:36:36,236 --> 00:36:37,980 Είναι ισχυρή. 865 00:36:37,980 --> 00:36:42,830 Είναι το πρωτόκολλο TCP / IP, και πήρε τη διεύθυνσή σας. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Πολεμιστές του Net." 868 00:36:48,074 --> 00:36:49,660 [ΤΕΛΟΣ VIDEO Αναπαραγωγή] 869 00:36:49,660 --> 00:36:50,910 DAVID Malan: Ερχόμενοι την επόμενη εβδομάδα. 870 00:36:50,910 --> 00:36:51,880 Θα σας δούμε στη συνέχεια. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [ΑΝΑΠΑΡΑΓΩΓΗ] 873 00:36:56,060 --> 00:36:59,240 -Και Τώρα, «βαθιές σκέψεις" από Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Ξεκινά πάντα διαλέξεις με, "Εντάξει." 876 00:37:05,820 --> 00:37:08,750 Γιατί όχι, "Εδώ είναι η λύση στο σύνολο το πρόβλημα αυτής της εβδομάδας " 877 00:37:08,750 --> 00:37:12,180 ή «Δίνουμε όλοι σας ένα Α;" 878 00:37:12,180 --> 00:37:13,380 [Γέλια] 879 00:37:13,380 --> 00:37:15,530 [ΤΕΛΟΣ VIDEO Αναπαραγωγή]