1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Musik zu spielen] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID MALAN: Dies ist CS50. 5 00:00:14,010 --> 00:00:18,090 Und dies ist sowohl der Beginn und das end-- wie literally-- fast zum Ende 6 00:00:18,090 --> 00:00:18,825 der Woche sechs. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Ich dachte, ich würde eine Aktie bisschen ein Spaß Tatsache. 9 00:00:22,640 --> 00:00:25,370 Ich habe dies aus einer hochgezogen Daten vergangenen Semester gesetzt. 10 00:00:25,370 --> 00:00:29,710 Sie erinnern sich vielleicht, dass wir Sie bitten, auf jeden p soll Formular, wenn Sie online gesehen haben 11 00:00:29,710 --> 00:00:31,580 oder wenn Sie persönlich besucht habe. 12 00:00:31,580 --> 00:00:33,020 Und hier sind die Daten. 13 00:00:33,020 --> 00:00:34,710 So war heute sehr vorhersehbar. 14 00:00:34,710 --> 00:00:37,126 Aber wir wollten ein wenig zu verbringen der Zeit mit Ihnen dennoch. 15 00:00:37,126 --> 00:00:40,599 Möchte jemand, warum diese Vermutung Graphen ist so Jaggy, up down, up down, 16 00:00:40,599 --> 00:00:41,265 so konsequent? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Was jeder von den Gipfeln und Mulden stellen? 19 00:00:45,130 --> 00:00:46,005 >> PUBLIKUM: [unverständlich] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID MALAN: In der Tat. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Und mehr amüsant, Gott bewahre, wir halten eine Vorlesung an einem Freitag 24 00:00:55,480 --> 00:00:58,960 zu Beginn des Semesters, das ist, was wir sehen passieren. 25 00:00:58,960 --> 00:01:03,430 So heute, teilhaben wir in ein wenig mehr über Datenstrukturen. 26 00:01:03,430 --> 00:01:06,660 Und um Ihnen mehr von einem Feststoff zu ergeben mentales Modell für Probleme auf fünf, 27 00:01:06,660 --> 00:01:07,450 Das ist jetzt aus. 28 00:01:07,450 --> 00:01:10,817 Rechtschreibfehler, bei dem wir Hand Sie eine Textdatei einige 100.000 29 00:01:10,817 --> 00:01:12,650 zzgl englische Wörter, und Sie gehen zu müssen sind 30 00:01:12,650 --> 00:01:17,770 um herauszufinden, wie man geschickt laden in den Speicher, in den Arbeitsspeicher, mit ein paar Daten 31 00:01:17,770 --> 00:01:19,330 Struktur Ihrer Wahl. 32 00:01:19,330 --> 00:01:22,470 >> Jetzt eine solche Datenstruktur könnte sein, aber wahrscheinlich nicht sein sollte, 33 00:01:22,470 --> 00:01:25,630 die ziemlich simpel verketteten Liste, was wir letztes Mal eingeführt. 34 00:01:25,630 --> 00:01:29,220 Und eine verbundene Liste hatte zumindest Ein Vorteil gegenüber einem Array. 35 00:01:29,220 --> 00:01:32,096 Was ist ein Vorteil eine verbundene Liste wohl? 36 00:01:32,096 --> 00:01:32,950 >> PUBLIKUM: Einfügen. 37 00:01:32,950 --> 00:01:33,908 >> DAVID MALAN: Einfügen. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Was meinen Sie damit? 40 00:01:35,196 --> 00:01:37,872 >> PUBLIKUM: Überall entlang die Liste [unverständlich]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID MALAN: Gut. 42 00:01:38,770 --> 00:01:42,090 So können Sie ein Element, wo einfügen Sie in der Mitte der Liste möchten 43 00:01:42,090 --> 00:01:45,490 ohne etwas zu mischen, welche wir zu dem Schluss, in unserem Sortier 44 00:01:45,490 --> 00:01:47,630 Diskussionen, ist nicht unbedingt eine gute Sache, 45 00:01:47,630 --> 00:01:51,200 weil es Zeit braucht, um tatsächlich zu bewegen alle diese Menschen links oder rechts. 46 00:01:51,200 --> 00:01:55,540 Und so mit einer verketteten Liste, können Sie gerade mit malloc, ein neuer Knoten, 47 00:01:55,540 --> 00:01:58,385 und aktualisieren Sie dann ein paar pointers-- zwei, drei Operationen max-- 48 00:01:58,385 --> 00:02:01,480 und wir sind in der Lage, jemanden Steckplatz in jedem Ort in eine Liste. 49 00:02:01,480 --> 00:02:03,550 >> Was war von Vorteil zu einer verketteten Liste? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Ja? 52 00:02:05,659 --> 00:02:06,534 >> PUBLIKUM: [unverständlich] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID MALAN: Perfect. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Perfect. 57 00:02:11,090 --> 00:02:12,070 Es ist wirklich dynamisch. 58 00:02:12,070 --> 00:02:15,100 Und dass Sie nicht zu begehen, im Voraus, bis zu einem gewissen festen Größe 59 00:02:15,100 --> 00:02:18,750 Teil des Speichers, wie Sie müssten mit einer Anordnung, die auf den Kopf davon 60 00:02:18,750 --> 00:02:22,455 ist, dass man Knoten nur zuteilen Nachfrage dadurch mit nur so viel Platz 61 00:02:22,455 --> 00:02:23,330 wie Sie tatsächlich benötigen. 62 00:02:23,330 --> 00:02:26,830 Im Gegensatz zu einem Array, könnte man versehentlich zu wenig zuordnen. 63 00:02:26,830 --> 00:02:28,871 Und dann ist es nur geht ein Schmerz im Nacken 64 00:02:28,871 --> 00:02:32,440 , um eine neue größere Array umzuschichten, kopieren alles vorbei ist, befreit das alte Array, 65 00:02:32,440 --> 00:02:33,990 und verschieben Sie dann über Ihr Unternehmen. 66 00:02:33,990 --> 00:02:37,479 Oder noch schlimmer, könnte man so zuteilen mehr Speicher, als Sie tatsächlich benötigen, 67 00:02:37,479 --> 00:02:40,520 und so wirst du einen sehr haben sind dünn besiedelten Array, so zu sprechen. 68 00:02:40,520 --> 00:02:44,350 >> So eine verbundene Liste gibt Ihnen diese Vorteile der Dynamik und Flexibilität 69 00:02:44,350 --> 00:02:46,080 mit Insertionen und Deletionen. 70 00:02:46,080 --> 00:02:48,000 Aber sicherlich muss es einen bezahlten Preis. 71 00:02:48,000 --> 00:02:50,000 In der Tat, eines der Themen auf Quiz Null erkundet 72 00:02:50,000 --> 00:02:52,430 war ein paar der Kompromisse wir bisher gesehen. 73 00:02:52,430 --> 00:02:56,161 Also, was ist ein Preis zu zahlen oder eine Nachteil einer verketteten Liste? 74 00:02:56,161 --> 00:02:56,660 Ja. 75 00:02:56,660 --> 00:02:57,560 >> PUBLIKUM: Kein Direktzugriff. 76 00:02:57,560 --> 00:02:58,809 >> DAVID MALAN: Kein Direktzugriff. 77 00:02:58,809 --> 00:02:59,540 Aber wen interessiert das? 78 00:02:59,540 --> 00:03:01,546 Random access klingt nicht überzeugend. 79 00:03:01,546 --> 00:03:02,421 >> PUBLIKUM: [unverständlich] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID MALAN: Genau. 82 00:03:05,740 --> 00:03:07,580 Wenn Sie haben wollen eine gewisse algorithm-- 83 00:03:07,580 --> 00:03:10,170 und lassen Sie mich eigentlich vorschlagen binäre Such insbesondere die 84 00:03:10,170 --> 00:03:12,600 ist einer wir ziemlich bit-- verwendet haben wenn Sie nicht mit wahlfreiem Zugriff, 85 00:03:12,600 --> 00:03:15,516 Sie können nicht so einfach rechnen kann zu finden wie das mittlere Element 86 00:03:15,516 --> 00:03:16,530 und Springen Recht darauf. 87 00:03:16,530 --> 00:03:20,239 Sie haben statt dessen beim ersten Start Element und linear von links suchen 88 00:03:20,239 --> 00:03:22,780 nach rechts, wenn Sie suchen möchten die mittlere oder ein anderes Element. 89 00:03:22,780 --> 00:03:24,410 >> PUBLIKUM: Es dauert wohl mehr Speicher. 90 00:03:24,410 --> 00:03:25,040 >> DAVID MALAN: mehr Speicherplatz. 91 00:03:25,040 --> 00:03:27,464 Wo ist, dass zusätzliche kosten, die aus in Erinnerung? 92 00:03:27,464 --> 00:03:28,339 >> PUBLIKUM: [unverständlich] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID MALAN: Genau. 95 00:03:33,440 --> 00:03:35,679 In diesem Fall hier, wir hatten eine verkettete Liste für ganze Zahlen, 96 00:03:35,679 --> 00:03:37,470 und doch sind wir verdoppeln die Speichermenge, 97 00:03:37,470 --> 00:03:39,680 wir brauchen, indem auch die Speicherung dieser Zeiger. 98 00:03:39,680 --> 00:03:42,090 Jetzt weniger eine große Sache wie Ihre Strukturen werden größer 99 00:03:42,090 --> 00:03:45,320 und Sie die Speicherung nicht eine Zahl, sondern vielleicht ein Student oder ein anderes Objekt. 100 00:03:45,320 --> 00:03:46,880 Aber der Punkt sicherlich bleibt. 101 00:03:46,880 --> 00:03:49,421 Und so eine Reihe von Operationen auf verkettete Listen genannt wurden 102 00:03:49,421 --> 00:03:50,570 waren groß O von N- linear. 103 00:03:50,570 --> 00:03:54,730 Dinge wie Insertion oder Suche oder Löschen, falls ein Element 104 00:03:54,730 --> 00:03:57,720 passiert ganz am Ende sein, die Liste, ob es sortiert oder nicht. 105 00:03:57,720 --> 00:04:01,167 >> Manchmal werden Sie vielleicht Glück haben und in so untere Schranken für diese Operationen 106 00:04:01,167 --> 00:04:04,250 Vielleicht haben Sie auch konstante Zeit sein, wenn Sie immer auf der Suche beim ersten Element, 107 00:04:04,250 --> 00:04:05,070 beispielsweise. 108 00:04:05,070 --> 00:04:09,360 Aber letztlich, wir versprochen um den heiligen Gral zu erreichen 109 00:04:09,360 --> 00:04:12,630 Datenstrukturen oder einige Annäherung davon, 110 00:04:12,630 --> 00:04:14,290 haft konstante Zeit. 111 00:04:14,290 --> 00:04:17,579 Finden wir Elemente oder Elemente hinzufügen oder entfernen Sie Elemente aus einer Liste? 112 00:04:17,579 --> 00:04:19,059 Wir werden schon bald sehen. 113 00:04:19,059 --> 00:04:21,100 Und es stellt sich heraus, dass einer der Mechanismen sind wir 114 00:04:21,100 --> 00:04:23,464 werde heute beginnen zu bedienen, Jahresnutzung in S. fünf, 115 00:04:23,464 --> 00:04:24,630 ist eigentlich ziemlich vertraut. 116 00:04:24,630 --> 00:04:27,430 Zum Beispiel, wenn dies ein Bündel Prüfungs Bücher, von denen jede 117 00:04:27,430 --> 00:04:29,660 hat ein Student das erste Name und Vorname darauf 118 00:04:29,660 --> 00:04:31,820 und ich sie abholen von am Ende einer Prüfung, 119 00:04:31,820 --> 00:04:33,746 und sie sind alle ziemlich viel in einer zufälligen Reihenfolge, 120 00:04:33,746 --> 00:04:36,370 und wir wollen über das Sortieren gehen wollen Diese Prüfungen, so dass einmal benotet 121 00:04:36,370 --> 00:04:38,661 es ist nur viel einfacher und schneller, um sie aus zurückgeben 122 00:04:38,661 --> 00:04:40,030 um Studenten alphabetisch. 123 00:04:40,030 --> 00:04:42,770 Was würden Sie Ihrem Instinkt sein für einen Haufen von Prüfungen wie diese? 124 00:04:42,770 --> 00:04:45,019 >> Nun, wenn Sie wie ich sind, Sie vielleicht sehen, dass dies m, 125 00:04:45,019 --> 00:04:48,505 so werde ich eine Art setzen Sie dieses in, wenn dies meinem Tisch oder meiner Etage, wo 126 00:04:48,505 --> 00:04:50,650 Verbreite ich Dinge out-- oder meine Array really-- 127 00:04:50,650 --> 00:04:52,210 Ich könnte die ganze Frau in es gesetzt. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Hier ist ein A. Also ich könnte Nehmen Sie den AS hier. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Hier ist eine andere Antwort: Ich werde , die der über hier setzen. 132 00:04:57,980 --> 00:05:02,490 Hier ist eine Z. Hier ist ein weiteres M. Und so Ich könnte anfangen, Pfähle wie diese. 133 00:05:02,490 --> 00:05:06,620 Und dann würde ich vielleicht später gehen in und irgendwie sehr pingelig-ly sortieren 134 00:05:06,620 --> 00:05:07,710 die einzelnen Pfähle. 135 00:05:07,710 --> 00:05:11,300 Aber der Punkt ist, ich würde aussehen am Eingang, dass ich handed 136 00:05:11,300 --> 00:05:14,016 und ich würde einige berechnet Entscheidung auf der Grundlage dieser Eingabe. 137 00:05:14,016 --> 00:05:15,640 Wenn Sie es mit A beginnt, legte es dort drüben. 138 00:05:15,640 --> 00:05:18,980 Wenn Sie es mit Z beginnt, legte es über dort, und alles dazwischen. 139 00:05:18,980 --> 00:05:22,730 >> Das ist also eine Technik, die es allgemein als hashing-- H-A-S-H- bekannt 140 00:05:22,730 --> 00:05:26,550 die in der Regel bedeutet, die als Eingang und mit diesem Eingang zu berechnen, 141 00:05:26,550 --> 00:05:30,940 ein Wert, in der Regel eine Zahl ist, und daß Zahl ist der Index in eine Speicher 142 00:05:30,940 --> 00:05:32,260 Behälter, wie ein Array. 143 00:05:32,260 --> 00:05:35,490 Also mit anderen Worten, könnte ich eine haben Hash-Funktion, wie ich in meinem Kopf zu tun, 144 00:05:35,490 --> 00:05:37,940 dass, wenn ich jemanden sehe, ist Namen, die mit A beginnt, 145 00:05:37,940 --> 00:05:40,190 Ich gehe zur Karte, dass in meinem Kopf Null. 146 00:05:40,190 --> 00:05:44,160 Und wenn ich mit Z jemanden sehen, ich bin werde, dass zu 25 Karte in meinem Kopf 147 00:05:44,160 --> 00:05:46,220 und setzen Sie dann, dass in der letzte meisten Haufen. 148 00:05:46,220 --> 00:05:50,990 >> Nun, wenn Sie über keine mein Gehirn denken aber ein C-Programm, welche Zahlen könnten 149 00:05:50,990 --> 00:05:53,170 Sie verlassen sich auf, um das gleiche Ergebnis zu erzielen? 150 00:05:53,170 --> 00:05:55,594 In anderen Worten, wenn man hatte das ASCII-Zeichen A, 151 00:05:55,594 --> 00:05:57,510 wie Sie bestimmen, was Eimer, um es in zu setzen? 152 00:05:57,510 --> 00:05:59,801 Sie wollen wahrscheinlich nicht zu steckte es in Eimer 65, die 153 00:05:59,801 --> 00:06:01,840 wäre wie drüben ohne guten Grund. 154 00:06:01,840 --> 00:06:04,320 Wo sehen Sie nach A setzen wollen im Hinblick auf seine ASCII-Wert? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Wo möchten Sie in die entsprechende ASCII tun wollen Wert zu kommen mit einer intelligenteren Eimer 157 00:06:08,920 --> 00:06:09,480 um es in zu setzen? 158 00:06:09,480 --> 00:06:10,206 >> PUBLIKUM: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID MALAN: Yeah. 160 00:06:10,956 --> 00:06:13,190 Also minus A oder minus Insbesondere wenn es 65 161 00:06:13,190 --> 00:06:18,240 eine Kapital A. Oder 98, wenn es ist eine kleine a. 162 00:06:18,240 --> 00:06:21,300 Und damit würde uns erlauben, sehr einfach und sehr arithmetisch, 163 00:06:21,300 --> 00:06:23,260 geben Sie etwas in einen Eimer so. 164 00:06:23,260 --> 00:06:26,010 So stellt sich heraus, dass wir tatsächlich tun dies auch noch mit den Quizfragen. 165 00:06:26,010 --> 00:06:29,051 >> So könnten Sie sich erinnern Sie kreisten Ihre Name Lehre Kerl auf dem Cover. 166 00:06:29,051 --> 00:06:32,270 Und benennt die TF wurden organisiert in diesen Spalten alphabetisch, 167 00:06:32,270 --> 00:06:34,400 Nun, es glauben oder nicht, wenn alle 80 Plus von uns 168 00:06:34,400 --> 00:06:37,800 trafen sich die andere Nacht in der Besoldungsgruppe, der letzte Schritt in unserem Sortierprozess 169 00:06:37,800 --> 00:06:41,830 ist es, die Quizfragen in ein großes hash Raum der Etage an der [unverständlich] 170 00:06:41,830 --> 00:06:45,110 und jedermanns Quiz zu legen, in genau der Reihenfolge ihrer TF 171 00:06:45,110 --> 00:06:47,700 Namen auf dem Cover, weil dann ist es viel einfacher für uns 172 00:06:47,700 --> 00:06:51,290 durch Verwendung dieser linearen Such Suche oder irgendeine Art von Klugheit 173 00:06:51,290 --> 00:06:54,050 für ein TF zu finden sein oder ihrer Schüler Quiz. 174 00:06:54,050 --> 00:06:56,060 >> Also diese Idee von Hashing dass Sie sehen, ist, 175 00:06:56,060 --> 00:07:00,520 sehr mächtig ist eigentlich ziemlich alltäglich und sehr intuitiv, 176 00:07:00,520 --> 00:07:03,000 ähnlich wie vielleicht teilen und Eroberung war in Woche Null. 177 00:07:03,000 --> 00:07:05,250 Ich faste mich auf den Hackathon ein paar Jahre her. 178 00:07:05,250 --> 00:07:08,040 Dies war Zamyla und ein paar andere Mitarbeiter Gruß Studenten 179 00:07:08,040 --> 00:07:09,030 wie sie hereinkam. 180 00:07:09,030 --> 00:07:12,680 Und wir hatten eine ganze Reihe von Falten Tischen mit Namensschild. 181 00:07:12,680 --> 00:07:15,380 Und wir hatten die Namensschilder organisiert mit wie die Da drüben 182 00:07:15,380 --> 00:07:16,690 und die Zs drüben. 183 00:07:16,690 --> 00:07:20,350 Und so einer der TFs sehr geschickt schrieb dies als den Anweisungen 184 00:07:20,350 --> 00:07:21,030 für den Tag. 185 00:07:21,030 --> 00:07:24,480 Und in der 12. Woche des Semesters dieses alle absolut Sinn, und jeder machte 186 00:07:24,480 --> 00:07:25,310 wusste, was zu tun ist. 187 00:07:25,310 --> 00:07:27,900 Aber, wenn Sie haben in gleicher Weise in der Warteschlange, 188 00:07:27,900 --> 00:07:30,272 Sie Implementierung sind die gleiche Vorstellung von einem Hash. 189 00:07:30,272 --> 00:07:31,730 Lassen Sie uns also zu formalisieren es ein wenig. 190 00:07:31,730 --> 00:07:32,890 Hier ist ein Array. 191 00:07:32,890 --> 00:07:36,820 Es ist gezeichnet, ein wenig breit, nur um darzustellen, visuell, 192 00:07:36,820 --> 00:07:38,920 dass wir vielleicht Saiten setzen in so etwas wie dieses. 193 00:07:38,920 --> 00:07:41,970 Und das Array deutlich von der Größe 26 gesamt. 194 00:07:41,970 --> 00:07:43,935 Und das Ding heißt Tabelle willkürlich. 195 00:07:43,935 --> 00:07:48,930 Doch dies ist nur Wiedergabe eines Künstlers von dem, was eine Hash-Tabelle könnte. 196 00:07:48,930 --> 00:07:52,799 >> So eine Hash-Tabelle nun auf geht sein eine höhere Datenstruktur. 197 00:07:52,799 --> 00:07:54,840 Am Ende des Tages wir sind dabei, um zu sehen, dass Sie 198 00:07:54,840 --> 00:07:58,700 eine Hash-Tabelle, implementieren die ist ähnlich wie die Check-in-Line 199 00:07:58,700 --> 00:08:02,059 bei einem Hackathon ähnlich wie dies Tabelle verwendet zum Sortieren Prüfung Bücher. 200 00:08:02,059 --> 00:08:03,850 Aber eine Hash-Tabelle ist Art von diesem hohen Niveau 201 00:08:03,850 --> 00:08:08,250 Konzept, das ein Array verwenden unter der Haube, sie umzusetzen, 202 00:08:08,250 --> 00:08:11,890 oder es könnte eine Länge Liste verwenden, oder sogar vielleicht einige andere Datenstrukturen. 203 00:08:11,890 --> 00:08:15,590 Und jetzt, da ist der theme-- Mitnahmen einige dieser Grundbestandteile 204 00:08:15,590 --> 00:08:18,310 wie ein Array und diesem Gebäude blockieren jetzt mit einer Länge Liste 205 00:08:18,310 --> 00:08:21,740 und zu sehen, was wir sonst noch bauen können zusätzlich zu jenen, wie Zutaten 206 00:08:21,740 --> 00:08:26,550 in ein Rezept, so dass mehr und mehr interessante und nützliche Endergebnisse. 207 00:08:26,550 --> 00:08:28,680 >> Also mit der Hash-Tabelle könnten wir sie umsetzen 208 00:08:28,680 --> 00:08:32,540 im Speicher bildhaft wie diese, aber wie könnte es tatsächlich kodiert werden? 209 00:08:32,540 --> 00:08:33,789 Nun, so einfach ist vielleicht. 210 00:08:33,789 --> 00:08:38,270 Wenn die Kapazität in Großbuchstaben, ist nur einige constant-- zum Beispiel 26, 211 00:08:38,270 --> 00:08:42,030 für 26 Buchstaben des alphabet-- Ich könnte meine Variablentabelle aufrufen, 212 00:08:42,030 --> 00:08:45,630 und ich könnte behaupten, dass ich zu gehen setzen char Sternen drin, oder ein String. 213 00:08:45,630 --> 00:08:49,880 Also ist es so einfach, wie dies, wenn Sie wollen eine Hash-Tabelle zu implementieren. 214 00:08:49,880 --> 00:08:51,490 Und doch, das ist wirklich nur ein Array. 215 00:08:51,490 --> 00:08:53,198 Aber noch einmal, ein Hash Tabelle ist jetzt, was wir 216 00:08:53,198 --> 00:08:57,470 rufen Sie einen abstrakten Datentyp, der gerade ist Art eines konzeptionellen Schichtung oben 217 00:08:57,470 --> 00:09:00,780 von etwas eher banalen Jetzt wie ein Array. 218 00:09:00,780 --> 00:09:02,960 >> Nun, wie gehen wir über die Lösung von Problemen? 219 00:09:02,960 --> 00:09:06,980 Nun, früher hatte ich den Luxus , genug Tabellenbereich hier 220 00:09:06,980 --> 00:09:09,460 so dass ich die genommen Quiz überall wollte ich. 221 00:09:09,460 --> 00:09:10,620 So könnte hier zu gehen. 222 00:09:10,620 --> 00:09:12,100 Zs vielleicht hier. 223 00:09:12,100 --> 00:09:13,230 Frau könnte hier zu gehen. 224 00:09:13,230 --> 00:09:14,740 Und dann hatte ich etwas mehr Platz. 225 00:09:14,740 --> 00:09:18,740 Aber das ist ein bisschen wie ein Cheat rechts jetzt, weil dieser Tabelle, wenn ich wirklich 226 00:09:18,740 --> 00:09:22,720 dachte an sie als ein Array, ist nur werde von einigen festen Größe sein. 227 00:09:22,720 --> 00:09:25,380 >> So technisch, wenn ich meinen up eines anderen Studenten Quiz 228 00:09:25,380 --> 00:09:28,490 und sehen, oh, diese Person Name beginnt mit einem A zu, 229 00:09:28,490 --> 00:09:30,980 Ich Art wollen sie dort einführen. 230 00:09:30,980 --> 00:09:34,740 Aber sobald ich es da, wenn Diese Tabelle Tat stellt ein Array, 231 00:09:34,740 --> 00:09:37,840 Ich werde dann überwiegend sein kann oder clobbering Wer auch immer dieser Schüler-Quiz ist. 232 00:09:37,840 --> 00:09:38,340 Richtig? 233 00:09:38,340 --> 00:09:41,972 Wenn dies ein Array ist, kann nur eins gehen in jeder dieser Zellen oder Elemente. 234 00:09:41,972 --> 00:09:43,680 Und so habe ich Art haben zu wählen, und wählen. 235 00:09:43,680 --> 00:09:45,735 >> Jetzt früheren Ich Art betrogen und tat dies oder ich 236 00:09:45,735 --> 00:09:47,526 nur irgendwie gestapelt sie übereinander liegen. 237 00:09:47,526 --> 00:09:49,170 Aber das wird nicht im Code zu fliegen. 238 00:09:49,170 --> 00:09:52,260 Also, wo könnte ich das zweite Student, dessen Namen 239 00:09:52,260 --> 00:09:54,964 ist ein, wenn alles, was ich hatte, ist dies verfügbar Tabellenbereich? 240 00:09:54,964 --> 00:09:57,880 Und ich habe drei Steckplätze, und es verwendet sieht aus wie es ist nur ein paar andere. 241 00:09:57,880 --> 00:09:58,959 Was könnten Sie tun? 242 00:09:58,959 --> 00:09:59,834 PUBLIKUM: [unverständlich] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID MALAN: Yeah. 245 00:10:01,315 --> 00:10:02,370 Vielleicht lassen Sie halten es gerade einfach. 246 00:10:02,370 --> 00:10:02,660 Richtig? 247 00:10:02,660 --> 00:10:04,243 Es passt nicht, wo ich will, es zu setzen. 248 00:10:04,243 --> 00:10:07,450 Also werde ich um es technisch, wo ein B gehen würde. 249 00:10:07,450 --> 00:10:09,932 Nun, natürlich, ich fange um mich in eine Ecke zu malen. 250 00:10:09,932 --> 00:10:11,890 Wenn ich an einen Studenten bekommen dessen Name ist eigentlich B, 251 00:10:11,890 --> 00:10:14,840 Jetzt B wird sich ein wenig verschoben werden nach vorn, wie es passieren, yep, 252 00:10:14,840 --> 00:10:17,530 ob dies ein B, jetzt muss es hier gehen. 253 00:10:17,530 --> 00:10:20,180 >> Und so ist dies sehr schnell könnte problematisch werden, 254 00:10:20,180 --> 00:10:23,850 aber es ist eine Technik, die eigentlich wird als lineare Abtastung bezeichnet, 255 00:10:23,850 --> 00:10:26,650 wodurch Sie gerade betrachten Sie Ihre Array entlang der Linie sein. 256 00:10:26,650 --> 00:10:29,680 Und du nur irgendwie Sonde oder Überprüfen Sie jedes verfügbare Element 257 00:10:29,680 --> 00:10:31,360 auf der Suche nach einem freien Fleck. 258 00:10:31,360 --> 00:10:34,010 Und sobald Sie feststellen, ein, es bringt Sie dort. 259 00:10:34,010 --> 00:10:38,390 >> Nun ist der Preis jetzt bezahlt Für diese Lösung ist was? 260 00:10:38,390 --> 00:10:41,300 Wir haben eine feste Größe Anordnung, und wenn ich einfügen Namen 261 00:10:41,300 --> 00:10:44,059 hinein, zumindest anfänglich, was die Laufzeit des Einsetzens 262 00:10:44,059 --> 00:10:46,350 für die Umsetzung der Schülerinnen und Schüler Quiz in den richtigen Eimer? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O von was? 265 00:10:50,002 --> 00:10:51,147 >> PUBLIKUM: n. 266 00:10:51,147 --> 00:10:52,480 DAVID MALAN: Ich habe gehört, Big O n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Das stimmt nicht. 269 00:10:54,300 --> 00:10:56,490 Aber wir werden auseinander zu necken warum in nur einem Augenblick. 270 00:10:56,490 --> 00:10:57,702 Was sonst könnte es sein? 271 00:10:57,702 --> 00:10:58,755 >> PUBLIKUM: [unverständlich] 272 00:10:58,755 --> 00:11:00,380 DAVID MALAN: Und lassen Sie mich es tun visuell. 273 00:11:00,380 --> 00:11:04,720 Also vermute, dies ist der Buchstabe S. 274 00:11:04,720 --> 00:11:05,604 >> PUBLIKUM: Es ist einer. 275 00:11:05,604 --> 00:11:06,520 DAVID MALAN: Es ist einer. 276 00:11:06,520 --> 00:11:06,710 Richtig? 277 00:11:06,710 --> 00:11:08,950 Dies ist ein Array, das bedeutet, dass wir mit wahlfreiem Zugriff. 278 00:11:08,950 --> 00:11:11,790 Und wenn wir davon halten als Null und dies als 25, 279 00:11:11,790 --> 00:11:13,800 und wir erkennen, dass, oh, hier ist mein Eingang S, 280 00:11:13,800 --> 00:11:16,350 Ich kann sicherlich konvertieren S, ein ASCII-Zeichen, 281 00:11:16,350 --> 00:11:18,540 mit einer entsprechenden Anzahl zwischen null und 25 282 00:11:18,540 --> 00:11:20,910 und dann sofort setzte es, wo es hingehört. 283 00:11:20,910 --> 00:11:26,120 >> Aber natürlich, sobald ich auf das zu bekommen zweite Person, der Name ist A oder B oder C 284 00:11:26,120 --> 00:11:29,300 schließlich, wenn ich verwendet habe, die lineare Sondieren als meine Lösung, 285 00:11:29,300 --> 00:11:31,360 die Laufzeit Einführen im ungünstigsten Fall 286 00:11:31,360 --> 00:11:33,120 ist eigentlich los, um in das, was übergehen? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Und ich habe hier hören richtig früh. 289 00:11:36,045 --> 00:11:36,920 PUBLIKUM: [unverständlich] 290 00:11:36,920 --> 00:11:41,620 DAVID MALAN: So ist es in der Tat einmal ist n Sie haben einen ausreichend großen Datensatz. 291 00:11:41,620 --> 00:11:44,410 So, auf der einen Seite, wenn Ihr Array ist groß genug, 292 00:11:44,410 --> 00:11:48,287 und Ihre Daten sind spärlich genug, können Sie bekommen diese schöne konstante Zeit. 293 00:11:48,287 --> 00:11:50,620 Aber sobald Sie anfangen immer mehr Elemente, 294 00:11:50,620 --> 00:11:53,200 und nur statistisch erhalten mehr Menschen mit dem Buchstaben 295 00:11:53,200 --> 00:11:56,030 A wie ihr Name oder der Buchstabe B, könnte es möglicherweise 296 00:11:56,030 --> 00:11:57,900 übertragen in etwas mehr linear. 297 00:11:57,900 --> 00:11:59,640 Also nicht ganz perfekt. 298 00:11:59,640 --> 00:12:00,690 So könnten wir besser machen? 299 00:12:00,690 --> 00:12:03,210 >> Nun, was war unser Lösung vor, wenn wir 300 00:12:03,210 --> 00:12:06,820 wollen mehr Dynamik als haben etwas wie ein Array erlaubt? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 PUBLIKUM: [unverständlich] 303 00:12:08,960 --> 00:12:10,030 DAVID MALAN: Was haben wir vor? 304 00:12:10,030 --> 00:12:10,530 Ja. 305 00:12:10,530 --> 00:12:11,430 So eine verkettete Liste. 306 00:12:11,430 --> 00:12:14,430 Nun, mal sehen, was ein verknüpftes Liste könnte für uns stattdessen tun. 307 00:12:14,430 --> 00:12:17,630 Nun, lassen Sie mich vor, dass wir zeichnen das Bild wie folgt. 308 00:12:17,630 --> 00:12:19,620 Nun ist dies eine andere Bild von einem Beispiel 309 00:12:19,620 --> 00:12:24,750 aus einem anderen Text, tatsächlich, daß tatsächlich unter Verwendung eines Array der Größe 31. 310 00:12:24,750 --> 00:12:28,220 Und dieser Autor einfach beschlossen, Strings hash 311 00:12:28,220 --> 00:12:32,430 nicht auf Namen der Person basiert, sondern auf der Grundlage ihrer Geburtsdaten. 312 00:12:32,430 --> 00:12:35,680 Unabhängig von der Monat, dachte sie wenn Sie am ersten eines Monats geboren sind 313 00:12:35,680 --> 00:12:39,580 oder 31. eines Monats, der Autor wird auf der Grundlage dieser Wert hash, 314 00:12:39,580 --> 00:12:44,154 um so die Namen ein bisschen zu verbreiten mehr als nur 26 Spots könnte ermöglichen. 315 00:12:44,154 --> 00:12:47,320 Und vielleicht ist es ein wenig mehr einheitliche als sich mit alphanumerischen Zeichen 316 00:12:47,320 --> 00:12:50,236 denn natürlich gibt es wahrscheinlich mehr Menschen auf der Welt mit Namen 317 00:12:50,236 --> 00:12:54,020 dass beginnen mit einem als sicher einige andere Buchstaben des Alphabets. 318 00:12:54,020 --> 00:12:56,380 Also vielleicht ist das ein wenig gleichmäßiger, unter der Annahme, 319 00:12:56,380 --> 00:12:58,640 eine gleichmäßige Verteilung von Babys in einem Monat. 320 00:12:58,640 --> 00:12:59,990 >> Aber natürlich ist dies immer noch unvollkommen. 321 00:12:59,990 --> 00:13:00,370 Richtig? 322 00:13:00,370 --> 00:13:01,370 Wir mit Kollisionen. 323 00:13:01,370 --> 00:13:04,680 Mehrere Menschen in diese Datenstruktur noch 324 00:13:04,680 --> 00:13:08,432 mit dem gleichen Geburtsdatum mindestens du bist unabhängig von Monat. 325 00:13:08,432 --> 00:13:09,640 Aber was hat der Autor getan? 326 00:13:09,640 --> 00:13:13,427 Nun, es sieht aus wie wir haben eine Reihe auf der linken Seite vertikal gezogen, 327 00:13:13,427 --> 00:13:15,010 aber das ist nur ein Künstlerwiedergabe. 328 00:13:15,010 --> 00:13:18,009 Es ist egal, welche Richtung man zeichnen ein Array, ist es noch ein Array. 329 00:13:18,009 --> 00:13:20,225 Was ist das ein Array von scheinbar? 330 00:13:20,225 --> 00:13:21,500 >> PUBLIKUM: verketteten Liste. 331 00:13:21,500 --> 00:13:21,650 >> DAVID MALAN: Yeah. 332 00:13:21,650 --> 00:13:23,490 Es sieht aus wie es ist ein Array von verketteten Liste. 333 00:13:23,490 --> 00:13:26,490 Also noch einmal, zu diesem Punkt der Art der Verwendung dieser Datenstrukturen jetzt 334 00:13:26,490 --> 00:13:28,550 als Zutaten mehr interessante Lösungen, 335 00:13:28,550 --> 00:13:30,862 Sie absolut nehmen ein fundamental, wie ein Array, 336 00:13:30,862 --> 00:13:33,320 und dann etwas mehr interessant wie eine verkettete Liste 337 00:13:33,320 --> 00:13:36,660 und sogar kombinieren sie zu einem noch interessanter Datenstruktur. 338 00:13:36,660 --> 00:13:39,630 Und in der Tat, auch dies würde eine Hash-Tabelle aufgerufen werden, 339 00:13:39,630 --> 00:13:42,610 wobei das Array wirklich die Hash-Tabelle, 340 00:13:42,610 --> 00:13:45,600 aber das Hash-Tabelle hat Ketten, sozusagen 341 00:13:45,600 --> 00:13:50,220 dass wachsen oder schrumpfen auf die anhand Anzahl der Elemente, die Sie einfügen möchten. 342 00:13:50,220 --> 00:13:52,990 >> Jetzt dementsprechend, was die Laufzeit ist jetzt? 343 00:13:52,990 --> 00:13:58,030 Wenn ich jemandem einfügen deren Geburtstag ist der 31. Oktober, 344 00:13:58,030 --> 00:13:59,040 wo kommt er oder sie gehen? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 In Ordnung. 347 00:14:01,030 --> 00:14:02,819 Ganz unten, wo es heißt 31. 348 00:14:02,819 --> 00:14:03,610 Und das ist perfekt. 349 00:14:03,610 --> 00:14:05,060 Das war konstante Zeit. 350 00:14:05,060 --> 00:14:08,760 Aber was, wenn wir jemand anderen finden deren Geburtstag wird, mal sehen, 351 00:14:08,760 --> 00:14:10,950 Oktober, November, 31. Dezember? 352 00:14:10,950 --> 00:14:12,790 Wo ist er oder sie hingehen? 353 00:14:12,790 --> 00:14:13,290 Elbe. 354 00:14:13,290 --> 00:14:13,970 Zwei Schritt though. 355 00:14:13,970 --> 00:14:15,303 Das ist konstant aber nicht wahr? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 In Ordnung. 358 00:14:16,860 --> 00:14:17,840 Im Moment ist es. 359 00:14:17,840 --> 00:14:20,570 Aber im allgemeinen Fall, Je mehr Menschen wir hinzufügen, 360 00:14:20,570 --> 00:14:23,790 probabilistisch, wir gehen mehr und mehr Kollisionen zu erhalten. 361 00:14:23,790 --> 00:14:26,820 >> Nun ist dies ein wenig besser, weil technisch 362 00:14:26,820 --> 00:14:34,580 nun meine Ketten könnte sein im schlimmsten Fall, wie lange? 363 00:14:34,580 --> 00:14:38,890 Wenn ich n Personen in diese mehr einfügen komplexe Datenstruktur, n Menschen, 364 00:14:38,890 --> 00:14:41,080 im schlimmsten Fall, es wird n sein. 365 00:14:41,080 --> 00:14:41,815 Warum? 366 00:14:41,815 --> 00:14:43,332 >> PUBLIKUM: Denn wenn alle hat am gleichen Tag Geburtstag, 367 00:14:43,332 --> 00:14:44,545 sie gehen, um eine Zeile sein. 368 00:14:44,545 --> 00:14:45,420 DAVID MALAN: Perfect. 369 00:14:45,420 --> 00:14:47,480 Es könnte ein wenig gekünstelt sein, aber wirklich im schlimmsten Fall, 370 00:14:47,480 --> 00:14:50,117 wenn jeder hat den gleichen Geburtstag, angesichts der Eingänge Sie haben, 371 00:14:50,117 --> 00:14:51,950 Sie ein Baby haben sind massiv langkettigen. 372 00:14:51,950 --> 00:14:54,241 Und so können Sie es einen nennen Hash-Tabelle, aber eigentlich ist es 373 00:14:54,241 --> 00:14:56,810 nur eine massive verketteten Liste mit eine ganze Menge Platz verschwendet. 374 00:14:56,810 --> 00:15:00,460 Aber in der Regel, wenn wir annehmen, daß mindestens Geburtstage sind uniform-- 375 00:15:00,460 --> 00:15:01,750 und es ist wahrscheinlich nicht. 376 00:15:01,750 --> 00:15:02,587 Ich mache, dass bis. 377 00:15:02,587 --> 00:15:04,420 Wenn wir aber annehmen, beispiels um der Diskussion willen 378 00:15:04,420 --> 00:15:07,717 daß sie dann in der Theorie, wenn Dies ist die vertikale Darstellung 379 00:15:07,717 --> 00:15:11,050 des Arrays, na dann hoffentlich bist du werde Ketten, die sind, wissen Sie, 380 00:15:11,050 --> 00:15:15,880 ungefähr die gleiche Länge haben, wo jeder diese stellt einen Tag des Monats. 381 00:15:15,880 --> 00:15:19,930 >> Nun, wenn es 31 Tage im Monat, das bedeutet, dass meine Laufzeit wirklich 382 00:15:19,930 --> 00:15:25,230 ist groß O von n über 31, die fühlt sich besser als linear. 383 00:15:25,230 --> 00:15:27,950 Aber was war eines unserer Verpflichtungen ein paar Wochen 384 00:15:27,950 --> 00:15:31,145 vor, wenn es um auszudrücken kam die Laufzeit eines Algorithmus? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Gerade erst am hohen Auftragstigen aussehen. 387 00:15:35,190 --> 00:15:35,690 Richtig? 388 00:15:35,690 --> 00:15:37,400 31 ist auf jeden Fall hilfreich. 389 00:15:37,400 --> 00:15:39,610 Aber das ist immer noch ein großes O n. 390 00:15:39,610 --> 00:15:41,730 Aber eines der Themen von Problem stellte fünf 391 00:15:41,730 --> 00:15:43,950 wird zu sein, erkennen an, dass absolut, 392 00:15:43,950 --> 00:15:47,320 asymptotisch theoretisch Diese Datenstruktur 393 00:15:47,320 --> 00:15:50,470 ist nicht besser als einfach einem massiven verketteten Liste. 394 00:15:50,470 --> 00:15:53,550 Und zwar im ungünstigsten Fall Hash-Tabelle könnte in diese übergehen. 395 00:15:53,550 --> 00:15:57,620 >> Aber in der realen Welt, mit uns Menschen dass die eigenen Macs oder PCs oder was auch immer 396 00:15:57,620 --> 00:16:01,240 und laufen realen Welt Software auf realen Daten, 397 00:16:01,240 --> 00:16:03,260 welcher Algorithmus wollen Sie lieber? 398 00:16:03,260 --> 00:16:09,180 Die eine, die Ende Schritte oder das dauert eine, n um 31 Schritte unterteilt Takes 399 00:16:09,180 --> 00:16:12,900 einige Stück von Daten zu finden oder nachschlagen einige Informationen? 400 00:16:12,900 --> 00:16:16,580 Ich meine, absolut die 31 Marken ein Unterschied in der realen Welt. 401 00:16:16,580 --> 00:16:18,540 Es ist 31 mal schneller. 402 00:16:18,540 --> 00:16:20,880 Und wir Menschen sind sicherlich werde das zu schätzen wissen. 403 00:16:20,880 --> 00:16:23,004 >> So realisieren die Dichotomie es zwischen tatsächlich 404 00:16:23,004 --> 00:16:25,920 reden über die Dinge theoretisch und asymptotisch die definitiv 405 00:16:25,920 --> 00:16:28,760 Wert hat, wie wir gesehen haben, aber in der realen Welt, 406 00:16:28,760 --> 00:16:32,930 wenn man darüber nur machen die Pflege Menschen glücklich für allgemeine Eingänge, 407 00:16:32,930 --> 00:16:36,010 Sie könnte sehr gut zu akzeptieren möchten die Tatsache, dass ja, ist diese lineare, 408 00:16:36,010 --> 00:16:38,360 aber es ist 31 mal schneller als linear sein könnte. 409 00:16:38,360 --> 00:16:41,610 Und noch besser, wir haben nicht nur zu tun Sie etwas willkürlich wie ein Geburtsdatum, 410 00:16:41,610 --> 00:16:44,030 wir ein wenig verbringen mehr Zeit und Klugheit 411 00:16:44,030 --> 00:16:47,140 und darüber nachdenken, was wir tun könnten, gegebenen Namen einer Person und vielleicht 412 00:16:47,140 --> 00:16:50,130 ihren Geburtstag mit denen kombinieren Zutaten, um herauszufinden, was 413 00:16:50,130 --> 00:16:52,720 das ist wirklich mehr einheitliche und weniger Jaggy, 414 00:16:52,720 --> 00:16:56,250 so als dieses Bild sprechen Derzeit schlägt es sein könnte. 415 00:16:56,250 --> 00:16:57,750 Wie könnten wir implementieren diese im Code? 416 00:16:57,750 --> 00:17:00,280 Nun, lassen Sie mich vor, dass wir nur einige Syntax wir haben zu leihen 417 00:17:00,280 --> 00:17:01,799 ein paar Mal verwendet so weit. 418 00:17:01,799 --> 00:17:03,590 Und ich werde zu definieren ein Knoten, wieder was 419 00:17:03,590 --> 00:17:06,812 ist ein Oberbegriff für nur einige Behälter für einige Datenstruktur. 420 00:17:06,812 --> 00:17:09,020 Ich werde mich vorzuschlagen ein String wird in dort. 421 00:17:09,020 --> 00:17:11,369 Aber wir werden zu Beginn der Einnahme diejenigen, die Ausbildung Räder vom jetzt. 422 00:17:11,369 --> 00:17:13,230 >> No more CS50-Bibliothek wirklich, es sei denn, Sie wollen 423 00:17:13,230 --> 00:17:15,230 um es für Ihre endgültige verwenden Projekt, was in Ordnung ist, 424 00:17:15,230 --> 00:17:18,569 aber jetzt werden wir nach hinten zu ziehen die Vorhang und sagen, es ist nur ein char Stern. 425 00:17:18,569 --> 00:17:22,069 Also das Wort es sein wird den Namen der Person in Frage. 426 00:17:22,069 --> 00:17:25,079 Und jetzt habe ich einen Link hier an den nächsten Knoten 427 00:17:25,079 --> 00:17:28,170 so daß diese stellen jeder der Knoten 428 00:17:28,170 --> 00:17:30,950 in der Kette, möglicherweise, einer verknüpften Liste. 429 00:17:30,950 --> 00:17:34,090 >> Und jetzt, wie kann ich erklären, die Hash-Tabelle selbst? 430 00:17:34,090 --> 00:17:36,660 Wie kann ich erklären, dass diese ganze Struktur? 431 00:17:36,660 --> 00:17:40,960 Also wirklich, so wie ich früher einen Zeiger nur das erste Element der Liste 432 00:17:40,960 --> 00:17:44,510 vor, ähnlich wie kann ich nur sagen, Ich brauche nur ein Bündel von Zeigern 433 00:17:44,510 --> 00:17:46,270 diese ganze Hash-Tabelle zu implementieren. 434 00:17:46,270 --> 00:17:49,484 Ich werde ein Array haben genannt Tisch für Hash-Tabelle. 435 00:17:49,484 --> 00:17:50,900 Es wird von der Größe Kapazität. 436 00:17:50,900 --> 00:17:52,525 Das ist, wie viele Elemente in ihm passen. 437 00:17:52,525 --> 00:17:56,180 Und jedes dieser Elemente in diesem Array wird ein Knoten Star. 438 00:17:56,180 --> 00:17:56,810 Warum? 439 00:17:56,810 --> 00:18:00,160 Nun, das, was ich bin pro Bild Umsetzung der Hash-Tabelle als 440 00:18:00,160 --> 00:18:04,330 effektiv in der Anfang ist nur Dieses Array, das wir haben vertikal gezogen, 441 00:18:04,330 --> 00:18:06,820 deren jeweilige Quadrate repräsentiert einen Zeiger. 442 00:18:06,820 --> 00:18:09,170 Dass diejenigen, die Schrägstriche haben durch sie sind nur null. 443 00:18:09,170 --> 00:18:11,410 Und diejenigen, die haben Pfeilen geht nach rechts 444 00:18:11,410 --> 00:18:16,140 sind tatsächliche Hinweise auf tatsächliche Knoten, ergo den Beginn einer verketteten Liste. 445 00:18:16,140 --> 00:18:19,050 >> So, hier ist also, wie wir Implementierung einer Hash-Tabelle, 446 00:18:19,050 --> 00:18:21,580 implementiert separaten Verkettung. 447 00:18:21,580 --> 00:18:22,840 Jetzt können wir besser machen? 448 00:18:22,840 --> 00:18:25,632 Alles klar ich letztes Mal versprochen, dass konnten wir konstante Zeit zu erreichen. 449 00:18:25,632 --> 00:18:27,381 Und ich Art gab dir konstante Zeit hier, 450 00:18:27,381 --> 00:18:29,850 aber dann sagte nicht wirklich konstante Zeit, denn es ist immer noch 451 00:18:29,850 --> 00:18:31,890 abhängig von der Gesamt Anzahl der Elemente 452 00:18:31,890 --> 00:18:34,500 Sie in der Eingabe sind die Datenstruktur. 453 00:18:34,500 --> 00:18:35,980 Aber nehmen wir dies taten. 454 00:18:35,980 --> 00:18:39,550 Lassen Sie mich zurück auf den Bildschirm hier. 455 00:18:39,550 --> 00:18:44,520 Lassen Sie mich auch projizieren dies hier oben, klar der Bildschirm, und nehme ich dies tat. 456 00:18:44,520 --> 00:18:49,300 Angenommen, ich wollte den Namen einfügen Daven in in meine Datenstruktur. 457 00:18:49,300 --> 00:18:52,100 >> Deshalb möchte ich einen String einfügen Daven in die Datenstruktur. 458 00:18:52,100 --> 00:18:54,370 Was, wenn ich nicht verwenden ein Hash-Tabelle, aber ich benutze 459 00:18:54,370 --> 00:18:56,980 etwas, das mehr ist baumartig wie ein Stammbaum, wo 460 00:18:56,980 --> 00:18:59,670 Sie einige root an die haben oben und dann Knoten und Blätter 461 00:18:59,670 --> 00:19:01,440 dass nach unten und außen zu gehen. 462 00:19:01,440 --> 00:19:04,450 Nehmen wir also an, dass ich wollen einfügen Daven 463 00:19:04,450 --> 00:19:06,430 in das, was ist derzeit eine leere Liste. 464 00:19:06,430 --> 00:19:09,780 Ich werde folgendes tun: Ich bin gehen, um einen Knoten in dieser Familie zu schaffen 465 00:19:09,780 --> 00:19:15,170 baumartige Datenstruktur, die aussieht ein wenig wie diese, von denen jede 466 00:19:15,170 --> 00:19:19,640 Rechtecke hat, sagen wir, für jetzt 26 Elemente. 467 00:19:19,640 --> 00:19:21,650 Und jede der Zellen, in diesem Array wird 468 00:19:21,650 --> 00:19:23,470 um den Buchstaben eines Alphabets repräsentieren. 469 00:19:23,470 --> 00:19:28,190 >> Insbesondere werde ich behandeln dies ist A, dann B, dann C, dann D, 470 00:19:28,190 --> 00:19:29,310 dieser hier. 471 00:19:29,310 --> 00:19:32,940 Also das wird wirksam stellen den Buchstaben D. 472 00:19:32,940 --> 00:19:36,040 Aber um alle Daven einfügen Namen ich, ein bisschen mehr tun müssen. 473 00:19:36,040 --> 00:19:37,840 Also bin ich zuerst zu Hash, so zu sprechen. 474 00:19:37,840 --> 00:19:41,049 Ich werde in dem ersten Buchstaben aussehen in Daven was offensichtlich ist ein D, 475 00:19:41,049 --> 00:19:42,840 und ich werde zuordnen ein Knoten, der aussieht 476 00:19:42,840 --> 00:19:45,570 wie this-- ein großes Rechteck groß genug, um das ganze Alphabet passen. 477 00:19:45,570 --> 00:19:47,140 >> Jetzt D durchgeführt wird. 478 00:19:47,140 --> 00:19:49,720 Jetzt A. D-A-V-E-N ist das Ziel. 479 00:19:49,720 --> 00:19:51,220 So jetzt, was ich tun werde, ist dies. 480 00:19:51,220 --> 00:19:54,027 Sobald ich begann D Ankündigung es gibt keine Zeiger gibt. 481 00:19:54,027 --> 00:19:56,860 Es ist Müll Werte in dem Moment, oder ich könnte es zu initialisieren auf null. 482 00:19:56,860 --> 00:19:59,630 Aber lassen Sie mich weitermachen mit diese Idee zum Bau eines Baumes. 483 00:19:59,630 --> 00:20:04,260 Lassen Sie mich zuordnen einem anderen dieser Knoten, die 26 Elemente in sich hat. 484 00:20:04,260 --> 00:20:05,150 >> Und wissen Sie was? 485 00:20:05,150 --> 00:20:09,130 Ist dies nur ein Knoten im Speicher, Ich mit malloc erstellt, unter Verwendung einer struct 486 00:20:09,130 --> 00:20:11,240 wie wir bald sehen werden, Ich werde this-- tun 487 00:20:11,240 --> 00:20:14,450 Ich werde einen Pfeil aus ziehen die Sache, die D unten dargestellt 488 00:20:14,450 --> 00:20:15,860 zu diesem neuen Knoten. 489 00:20:15,860 --> 00:20:19,240 Und nun zunächst der nächste Brief in Daven Namen, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- Ich werde weitermachen und zeichnen Sie einen weiteren Knoten wie diese, 491 00:20:24,150 --> 00:20:30,150 wobei die V-Elemente hier, die wir werden für instance-- hoppla ziehen. 492 00:20:30,150 --> 00:20:31,020 Wir werden dort nicht zeichnen. 493 00:20:31,020 --> 00:20:31,936 Es wird hier zu gehen. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Dann sind wir zu gehen halten dies für V. sein 496 00:20:35,712 --> 00:20:44,920 Und dann hier unten sind wir zum Index gehen unten von V in das, was wir E. betrachten 497 00:20:44,920 --> 00:20:50,100 Und dann von hier aus sind wir zu gehen gehen einen dieser Knoten hier. 498 00:20:50,100 --> 00:20:52,930 Und jetzt haben wir eine Frage zu beantworten. 499 00:20:52,930 --> 00:20:57,840 Ich muss irgendwie zeigen, dass Wir sind am Ende der Zeichenfolge Daven. 500 00:20:57,840 --> 00:20:59,490 So konnte ich lass es einfach null. 501 00:20:59,490 --> 00:21:02,670 >> Aber was, wenn wir Daven auch den vollständigen Namen, die 502 00:21:02,670 --> 00:21:04,280 ist, wie wir gesagt haben, Davenport? 503 00:21:04,280 --> 00:21:06,970 So was, wenn Daven ist eigentlich ein Teilstring, 504 00:21:06,970 --> 00:21:08,960 ein Präfix eines viel längeren Schnur? 505 00:21:08,960 --> 00:21:11,450 Wir können nicht nur dauerhaft sagen nichts los ist 506 00:21:11,450 --> 00:21:14,410 dorthin zu gehen, weil wir nie ein Wort wie Davenport einfügen 507 00:21:14,410 --> 00:21:15,840 in dieser Datenstruktur 508 00:21:15,840 --> 00:21:19,560 >> Also, was wir tun könnten, ist stattdessen behandeln jedes dieser Elemente 509 00:21:19,560 --> 00:21:22,170 als vielleicht mit zwei Elemente innerhalb von ihnen. 510 00:21:22,170 --> 00:21:24,810 Einer ist ein Zeiger tatsächlich wie ich getan habe. 511 00:21:24,810 --> 00:21:27,100 So wird jede dieser Boxen ist nicht nur eine Zelle. 512 00:21:27,100 --> 00:21:29,855 Aber was, wenn die Besten one-- der Boden irgendjemandes 513 00:21:29,855 --> 00:21:32,230 gehen null zu sein, denn es gibt keine Davenport nur noch. 514 00:21:32,230 --> 00:21:34,197 Was ist, wenn das oberste ist einige spezielle Wert? 515 00:21:34,197 --> 00:21:36,530 Und es geht, ein wenig schwer, es zu dieser Größe zu zeichnen. 516 00:21:36,530 --> 00:21:38,130 Aber angenommen, es ist nur ein Häkchen. 517 00:21:38,130 --> 00:21:38,920 Überprüfen. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N ist ein String in dieser Datenstruktur. 519 00:21:44,230 --> 00:21:48,350 >> Inzwischen, wenn ich mehr Platz hatte hier, ich P-O-R-T tun konnte, 520 00:21:48,350 --> 00:21:52,650 und ich konnte Prüfung im Knoten setzen daß den Buchstaben T am Ende. 521 00:21:52,650 --> 00:21:55,460 Das ist also ein massiv komplexe gerichtete Datenstruktur. 522 00:21:55,460 --> 00:21:57,210 Und meine Handschrift sicherlich nicht helfen. 523 00:21:57,210 --> 00:22:00,043 Aber wenn ich wollte etwas einfügen anderes, überlegen, was wir tun würden. 524 00:22:00,043 --> 00:22:03,370 Wenn wir David in stellen wollte, wir würden die gleiche Logik, D-A-V folgen, 525 00:22:03,370 --> 00:22:08,802 aber jetzt möchte ich in den nächsten Punkt Element nicht aus E, sondern von I bis D. 526 00:22:08,802 --> 00:22:10,760 Also es geht um sein mehrere Knoten in diesem Baum. 527 00:22:10,760 --> 00:22:12,325 Wir werden Call malloc mehr. 528 00:22:12,325 --> 00:22:14,700 Aber ich möchte nicht eine zu machen komplettes Chaos dieses Bildes. 529 00:22:14,700 --> 00:22:17,710 Also lassen Sie uns stattdessen auf einen Blick das ist vorformuliert worden 530 00:22:17,710 --> 00:22:21,810 wie diese mit nicht Punkt, Punkt, Punkte, sondern nur abgekürzt Arrays. 531 00:22:21,810 --> 00:22:23,950 Aber jeder der Knoten In diesem Stammbaum hier 532 00:22:23,950 --> 00:22:26,700 stellt das gleiche thing-- ein Array Ray von Größe 26. 533 00:22:26,700 --> 00:22:28,860 >> Oder wenn wir sein wollen wirklich richtige jetzt, was 534 00:22:28,860 --> 00:22:30,790 wenn jemand den Namen als ein Apostroph, lassen Sie uns 535 00:22:30,790 --> 00:22:35,560 davon ausgehen, dass jeder Knoten tatsächlich wie 27 Indizes in ihm, nicht nur 26. 536 00:22:35,560 --> 00:22:42,020 Also das jetzt wird ein Daten sein Struktur genannt trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 Ein Trie, die angeblich historisch ein cleverer Name für einen Baum 538 00:22:46,120 --> 00:22:49,040 das ist für eine optimierte Abrufen, welche natürlich 539 00:22:49,040 --> 00:22:50,870 mit einem I-E geschrieben, so ist es Trie. 540 00:22:50,870 --> 00:22:52,710 Aber das ist die Geschichte des Trie. 541 00:22:52,710 --> 00:22:55,860 >> Also ein Trie ist diese baumartige Daten Struktur wie ein Familienstammbaum 542 00:22:55,860 --> 00:22:57,510 dass letztlich verhält sich wie das. 543 00:22:57,510 --> 00:23:00,890 Und hier ist ein weiteres Beispiel für ein ganze Reihe von Namen anderer Leute. 544 00:23:00,890 --> 00:23:03,540 Aber die Frage ist jetzt bei der Hand ist, was haben 545 00:23:03,540 --> 00:23:08,070 gewannen wir durch die Einführung wohl eine komplizierte Datenstruktur, und eine, 546 00:23:08,070 --> 00:23:09,870 ehrlich gesagt, verwendet, dass eine Menge Speicher. 547 00:23:09,870 --> 00:23:11,703 >> Denn auch wenn, im Moment bin ich nur 548 00:23:11,703 --> 00:23:15,050 mit D's Zeiger und A und V und E und Ns, 549 00:23:15,050 --> 00:23:16,700 Ich vergeude ein Heck viel Speicher. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Aber wo ich verbringe eine Ressource, Ich neige dazu, nicht zurück ein anderes zu gewinnen. 552 00:23:22,660 --> 00:23:26,020 Also, wenn ich mehr Platz zu verbringen, was ist wohl die Hoffnung? 553 00:23:26,020 --> 00:23:27,407 Dass ich weniger ausgeben, was? 554 00:23:27,407 --> 00:23:28,240 PUBLIKUM: Weniger Zeit. 555 00:23:28,240 --> 00:23:28,990 DAVID MALAN: Zeit. 556 00:23:28,990 --> 00:23:30,320 Nun, warum könnte das sein? 557 00:23:30,320 --> 00:23:33,880 Nun, was ist das Einfügen Zeit, in nun Bezug auf große O, 558 00:23:33,880 --> 00:23:37,660 von einem Namen wie Daven oder Davenport oder David? 559 00:23:37,660 --> 00:23:39,340 Nun, das war Daven fünf Schritten. 560 00:23:39,340 --> 00:23:42,350 Davenport würde neun Stufen sein, so wäre es ein paar Schritte weiter sein. 561 00:23:42,350 --> 00:23:44,250 David würde fünf Schritte als gut. 562 00:23:44,250 --> 00:23:47,230 Also diejenigen Beton Zahlen, aber sicherlich gibt es 563 00:23:47,230 --> 00:23:49,550 auf dem eine obere Schranke Länge des Namens jemand. 564 00:23:49,550 --> 00:23:52,240 Und in der Tat, in der Problem Sätze von fünf Spezifikation 565 00:23:52,240 --> 00:23:54,050 wir werden vorschlagen dass es etwas 566 00:23:54,050 --> 00:23:55,470 das ist 40-some-ungeraden Zeichen. 567 00:23:55,470 --> 00:23:58,180 >> Realistisch gesehen, niemand hat ein unendlich langer Name, 568 00:23:58,180 --> 00:24:01,542 das heißt, daß die Länge a benennen oder die Länge eines Strings könnten wir 569 00:24:01,542 --> 00:24:03,750 haben bestimmte der Staat Struktur ist wohl was? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Es ist konstant. 572 00:24:06,250 --> 00:24:06,430 Richtig? 573 00:24:06,430 --> 00:24:09,310 Es könnte eine große Konstante wie sein 40 etwas, aber sie ist konstant. 574 00:24:09,310 --> 00:24:13,752 Und es keine Abhängigkeit davon, wie viele hat anderen Namen sind in dieser Datenstruktur. 575 00:24:13,752 --> 00:24:15,460 In anderen Worten, wenn I wollte jetzt einfügen 576 00:24:15,460 --> 00:24:20,540 Colton oder Gabriel oder Rob oder Zamyla oder Alison oder Belinda oder irgendwelche anderen Namen 577 00:24:20,540 --> 00:24:23,940 von den Mitarbeitern in diesen Daten Struktur, ist die Laufzeit 578 00:24:23,940 --> 00:24:26,750 Einfügen von anderen Namen in Zukunft an allen betroffen sein 579 00:24:26,750 --> 00:24:30,220 durch, wie viele andere Elemente in der Datenstruktur schon? 580 00:24:30,220 --> 00:24:31,040 Es ist nicht. 581 00:24:31,040 --> 00:24:31,540 Richtig? 582 00:24:31,540 --> 00:24:36,150 Weil wir effektiv mit Diese Mehrschicht-Hash-Tabelle. 583 00:24:36,150 --> 00:24:38,280 Und die Laufzeit jede dieser Operationen 584 00:24:38,280 --> 00:24:41,510 hängt nicht von der Anzahl der Elemente, die in der Datenstruktur sind, 585 00:24:41,510 --> 00:24:43,090 oder dass irgendwann gehen die in der Datenstruktur, 586 00:24:43,090 --> 00:24:44,714 sondern auf die Länge, was speziell? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Der String wobei eingesetzt, die machen tut 589 00:24:49,200 --> 00:24:52,580 diese asymptotisch konstant Zeit-- Big O von einem. 590 00:24:52,580 --> 00:24:54,720 Und ehrlich gesagt, nur in die reale Welt, diese 591 00:24:54,720 --> 00:24:58,380 bedeutet Einsetzen Daven Namen hat wie fünf Stufen oder Davenport neun 592 00:24:58,380 --> 00:25:00,100 Stufen oder David fünf Schritten. 593 00:25:00,100 --> 00:25:03,071 Das ist verdammt kleine Laufzeiten. 594 00:25:03,071 --> 00:25:05,320 Und in der Tat, das ist eine sehr gute Sache, vor allem, wenn 595 00:25:05,320 --> 00:25:08,126 es ist nicht abhängig von der Gesamt Anzahl der Elemente gibt. 596 00:25:08,126 --> 00:25:10,500 Also, wie können wir die einschlägigen Vorschriften des Art der Struktur im Code? 597 00:25:10,500 --> 00:25:12,900 Es ist ein wenig mehr komplex, aber es ist immer noch 598 00:25:12,900 --> 00:25:15,050 nur eine Anwendung des Grundbausteine. 599 00:25:15,050 --> 00:25:17,830 Ich werde neu definieren US-Knoten wie folgt: 600 00:25:17,830 --> 00:25:21,100 bool genannt word-- und dies könnte alles heißen. 601 00:25:21,100 --> 00:25:23,970 Aber die bool repräsentiert was ich zog als Häkchen. 602 00:25:23,970 --> 00:25:24,490 Ja. 603 00:25:24,490 --> 00:25:26,720 Dies ist das Ende einer Zeichenfolge in dieser Datenstruktur. 604 00:25:26,720 --> 00:25:30,702 >> Und natürlich der Knoten star es ist, Kinder zu beziehen. 605 00:25:30,702 --> 00:25:32,410 Und zwar genauso wie ein Stammbaum, Sie 606 00:25:32,410 --> 00:25:34,370 würden die Knoten betrachten dass hängen off 607 00:25:34,370 --> 00:25:36,920 der Boden etwas Mutter Element, Kinder zu sein. 608 00:25:36,920 --> 00:25:40,510 Und damit die Kinder an gehen sein eine Reihe von 27, der 27. ein 609 00:25:40,510 --> 00:25:41,680 einfach nur für Apostroph. 610 00:25:41,680 --> 00:25:43,390 Wir werden sortieren der Sonderfall, dass. 611 00:25:43,390 --> 00:25:45,400 So können Sie bestimmte haben können Namen mit Apostroph. 612 00:25:45,400 --> 00:25:47,399 Vielleicht sogar Bindestrich sind gehen dort, aber du wirst 613 00:25:47,399 --> 00:25:50,330 sehen in p-Set 5 wir nur Pflege etwa Briefe und Apostrophe. 614 00:25:50,330 --> 00:25:52,990 >> Und dann, wie vertreten Sie Die Datenstruktur selbst? 615 00:25:52,990 --> 00:25:56,454 Wie vertreten Sie die Wurzel dieser Trie sozusagen? 616 00:25:56,454 --> 00:25:59,620 Nun, genau wie bei einer verketteten Liste, die Sie benötigen einen Zeiger auf das erste Element. 617 00:25:59,620 --> 00:26:04,270 Mit einem Trie Sie brauchen nur eine Zeiger auf die Wurzel dieser Trie. 618 00:26:04,270 --> 00:26:07,290 Und von dort aus hash kann Ihren Weg nach unten tiefer und tiefer 619 00:26:07,290 --> 00:26:10,460 zu jedem anderen Knoten in der Struktur. 620 00:26:10,460 --> 00:26:13,440 Also einfach mit diesem Dosen wir vertreten, dass struct. 621 00:26:13,440 --> 00:26:15,877 >> Jetzt Meanwhile-- Oh, Frage. 622 00:26:15,877 --> 00:26:17,220 >> PUBLIKUM: Was ist bool Wort? 623 00:26:17,220 --> 00:26:20,490 >> DAVID MALAN: Bool Wort ist gerade diese C Inkarnation 624 00:26:20,490 --> 00:26:22,920 von dem, was ich beschrieben in diesem Feld hier, wenn 625 00:26:22,920 --> 00:26:26,000 Ich begann die Aufteilung jeder der Elemente Arrays in zwei Stücke. 626 00:26:26,000 --> 00:26:27,600 Einer ist ein Zeiger zu dem nächsten Knoten. 627 00:26:27,600 --> 00:26:30,280 Das andere zu sein so etwas wie ein Kontrollkästchen 628 00:26:30,280 --> 00:26:33,770 ja zu sagen, es gibt eine Wort Daven, die hier endet, 629 00:26:33,770 --> 00:26:35,610 weil wir nicht wollen, in dem Moment, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Obwohl Dave wird eine sein legitime Wort, er ist nicht in der Trie 631 00:26:39,320 --> 00:26:39,830 noch. 632 00:26:39,830 --> 00:26:40,950 Und D ist nicht ein Wort. 633 00:26:40,950 --> 00:26:42,770 Und D-A ist nicht ein Wort oder einen Namen. 634 00:26:42,770 --> 00:26:45,020 Also das Häkchen zeigt nur, wenn Sie 635 00:26:45,020 --> 00:26:48,190 traf dieser Knoten der früheren Weg der Zeichen 636 00:26:48,190 --> 00:26:50,700 eigentlich eine Zeichenfolge, die Sie eingefügt haben. 637 00:26:50,700 --> 00:26:53,660 Also das ist alles, die bool es für uns tut. 638 00:26:53,660 --> 00:26:55,500 >> Alle anderen Fragen auf versucht? 639 00:26:55,500 --> 00:26:56,215 Ja. 640 00:26:56,215 --> 00:26:58,035 >> PUBLIKUM: Was ist die Überlappung? 641 00:26:58,035 --> 00:26:59,945 Was, wenn Sie ein Dave und Daven haben? 642 00:26:59,945 --> 00:27:00,820 DAVID MALAN: Perfect. 643 00:27:00,820 --> 00:27:02,580 Was, wenn Sie ein Dave und Daven haben? 644 00:27:02,580 --> 00:27:06,240 Also, wenn wir stecken, sagen, ein Spitzname, für David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Das ist eigentlich super einfach. 647 00:27:08,700 --> 00:27:10,325 Also werden wir nur gehen, um vier Schritte zu unternehmen. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. Und was muss ich tun, wenn ich auf diesen vierten Knoten? 650 00:27:15,847 --> 00:27:16,680 Gerade dabei, zu überprüfen. 651 00:27:16,680 --> 00:27:18,000 Wir sind schon gut zu gehen. 652 00:27:18,000 --> 00:27:18,840 Fertig. 653 00:27:18,840 --> 00:27:19,750 Vier Schritte. 654 00:27:19,750 --> 00:27:21,590 Konstante Zeit asymptotisch. 655 00:27:21,590 --> 00:27:26,300 Und jetzt haben wir, dass sowohl Dave angegeben und Daven sind Strings in der Struktur. 656 00:27:26,300 --> 00:27:27,710 So kein Problem. 657 00:27:27,710 --> 00:27:30,200 Und merken, wie das Vorhandensein von Daven hat es nicht geschafft 658 00:27:30,200 --> 00:27:34,750 keine Zeit mehr oder weniger nehmen Zeit für Dave und umgekehrt. 659 00:27:34,750 --> 00:27:36,000 >> Also, was können wir sonst noch tun? 660 00:27:36,000 --> 00:27:40,680 Wir haben diese Metapher vor verwendet von Schalen, die etwas darstellt. 661 00:27:40,680 --> 00:27:43,380 Aber es stellt sich heraus, dass ein Stapel von Ablagen ist eigentlich 662 00:27:43,380 --> 00:27:47,187 demonstrative eines anderen abstrakten Daten Typ-- eine höhere Datenstruktur 663 00:27:47,187 --> 00:27:49,770 dass am Ende des Tages ist nur wie ein Array oder eine verkettete Liste 664 00:27:49,770 --> 00:27:50,970 oder etwas banal. 665 00:27:50,970 --> 00:27:53,270 Aber es ist ein interessanter konzeptionellen Konzept. 666 00:27:53,270 --> 00:27:56,440 Ein Stapel, wie diese Rinnen hier in Mather, 667 00:27:56,440 --> 00:27:58,750 werden allgemein als nur dass-- einen Stapel. 668 00:27:58,750 --> 00:28:02,540 >> Und bei dieser Art von Datenstruktur, Sie zwei operations-- haben 669 00:28:02,540 --> 00:28:05,880 Sie nannte man Push für haben Hinzufügen etwas auf den Stapel, 670 00:28:05,880 --> 00:28:08,320 wie wenn man ein anderes Fach wieder auf die Spitze des Stapels. 671 00:28:08,320 --> 00:28:11,350 Und dann Pop, der Sie bedeutet nehmen Sie die oberste Schale ab. 672 00:28:11,350 --> 00:28:16,210 Aber was ist Schlüssel zu einem Stapel ist, dass es hat diese merkwürdige Charakteristik. 673 00:28:16,210 --> 00:28:19,560 Als Speisesaal Personal Neuanordnung der Schalen für die nächste Mahlzeit, 674 00:28:19,560 --> 00:28:21,380 was los zu sein wahr, wie Studenten 675 00:28:21,380 --> 00:28:22,856 interagieren mit dieser Datenstruktur? 676 00:28:22,856 --> 00:28:24,480 PUBLIKUM: Sie werden einmalige Pop. 677 00:28:24,480 --> 00:28:26,550 DAVID MALAN: Sie sind zu gehen Pop einmalige, hoffentlich die Spitze. 678 00:28:26,550 --> 00:28:28,910 Sonst ist es nur irgendwie dumm den ganzen Weg auf den Grund gehen. 679 00:28:28,910 --> 00:28:29,070 Richtig? 680 00:28:29,070 --> 00:28:31,620 Die Datenstruktur nicht wirklich erlauben Sie die Bodenwanne mindestens greifen 681 00:28:31,620 --> 00:28:32,520 leicht. 682 00:28:32,520 --> 00:28:35,040 Also gibt es diese merkwürdige Eigenschaft auf einem Stapel 683 00:28:35,040 --> 00:28:39,730 dass das letzte Element in ist werde das erste aus sein. 684 00:28:39,730 --> 00:28:43,400 Und Informatiker nennen dies LIFO-- in erster dauern, heraus. 685 00:28:43,400 --> 00:28:45,540 Und es tatsächlich funktioniert haben interessante Anwendungen. 686 00:28:45,540 --> 00:28:50,090 Es ist nicht unbedingt so offensichtlich wie einige anderen, aber es kann in der Tat nützlich sein, 687 00:28:50,090 --> 00:28:54,040 und es kann in der Tat umgesetzt werden in einer Reihe von verschiedenen Möglichkeiten. 688 00:28:54,040 --> 00:28:58,550 >> So ein, und tatsächlich lassen mich nicht in diesen Tauchgang. 689 00:28:58,550 --> 00:28:59,860 Lassen Sie uns dies tun, statt. 690 00:28:59,860 --> 00:29:03,700 Schauen wir uns ein, die fast das ist gleiche Idee, aber es ist ein wenig gerechter. 691 00:29:03,700 --> 00:29:04,200 Richtig? 692 00:29:04,200 --> 00:29:07,560 Wenn Sie eines dieser Fan Jungen sind oder Mädchen, die wirklich mag Apple-Produkte 693 00:29:07,560 --> 00:29:10,130 und Sie um 3:00 Uhr aufgewacht irgend store antreten 694 00:29:10,130 --> 00:29:14,150 um die neuesten iPhone zu bekommen, können Sie könnte sich wie diese eingereiht haben. 695 00:29:14,150 --> 00:29:15,800 >> Jetzt eine Warteschlange ganz bewusst benannt. 696 00:29:15,800 --> 00:29:18,190 Es ist eine Linie, weil es einige Fairness zu. 697 00:29:18,190 --> 00:29:18,690 Richtig? 698 00:29:18,690 --> 00:29:21,690 Es wäre irgendwie angesaugt, wenn Sie noch war zuerst da im Apple Store 699 00:29:21,690 --> 00:29:25,700 aber man effektiv die unterste sind Fach, da die Apple-Mitarbeiter dann 700 00:29:25,700 --> 00:29:28,189 Pop die letzte Person, die tatsächlich im Einklang stand. 701 00:29:28,189 --> 00:29:31,230 So Stacks und Warteschlangen, obwohl funktional sind sie Art des same-- 702 00:29:31,230 --> 00:29:33,105 es ist nur diese Sammlung von Ressourcen, das ist 703 00:29:33,105 --> 00:29:36,210 werde wachsen und shrink-- es gibt diese Fairness Aspekt, um es, 704 00:29:36,210 --> 00:29:39,634 zumindest in der realen Welt, wo die Operationen, die Sie ausüben 705 00:29:39,634 --> 00:29:40,800 unterscheiden sich grundlegend. 706 00:29:40,800 --> 00:29:43,360 Ein stack-- eine Warteschlange rather-- soll gesagt haben 707 00:29:43,360 --> 00:29:45,320 zwei Operationen: n Warteschlange und d Warteschlange. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Oder Sie können sie anrufen jede Anzahl von Dingen. 710 00:29:48,090 --> 00:29:50,770 Aber Sie wollen einfach nur zu erfassen die Vorstellung, dass man die Zugabe 711 00:29:50,770 --> 00:29:53,230 und man schließlich Subtraktion. 712 00:29:53,230 --> 00:29:58,840 >> Jetzt unter der Haube, die beide der Stapel und eine Warteschlange könnte umgesetzt werden, wie? 713 00:29:58,840 --> 00:30:01,390 Wir werden nicht in die Box zu gehen weil die höhere 714 00:30:01,390 --> 00:30:03,387 Idee ist eine Art offensichtlicher. 715 00:30:03,387 --> 00:30:04,470 Ich meine, was die Menschen tun? 716 00:30:04,470 --> 00:30:07,030 Wenn ich die erste Person auf der Apple Bewahren und das ist die Haustür, 717 00:30:07,030 --> 00:30:08,130 Sie wissen, ich werde hier stehen. 718 00:30:08,130 --> 00:30:09,750 Und die nächste Person hier stehen. 719 00:30:09,750 --> 00:30:11,500 Und die nächste Person hier stehen. 720 00:30:11,500 --> 00:30:13,792 Also, was Datenstruktur eignet sich für eine Warteschlange? 721 00:30:13,792 --> 00:30:14,542 >> PUBLIKUM: Eine Warteschlange. 722 00:30:14,542 --> 00:30:15,667 DAVID MALAN: Nun, eine Warteschlange. 723 00:30:15,667 --> 00:30:16,390 Sicher. 724 00:30:16,390 --> 00:30:16,920 Was sonst? 725 00:30:16,920 --> 00:30:17,600 >> PUBLIKUM: Eine verkettete Liste. 726 00:30:17,600 --> 00:30:18,990 >> DAVID MALAN: Ein verknüpftes Liste Sie implementieren könnte. 727 00:30:18,990 --> 00:30:22,500 Und eine verkettete Liste ist nett, weil dann es beliebig lang werden kann, im Gegensatz 728 00:30:22,500 --> 00:30:24,880 um mit einigen festen Anzahl der Menschen in den Laden. 729 00:30:24,880 --> 00:30:27,030 Aber vielleicht eine feste Anzahl der Plätze ist legitim. 730 00:30:27,030 --> 00:30:30,350 Denn wenn sie nur wie 20 iPhones am ersten Tag, vielleicht 731 00:30:30,350 --> 00:30:33,930 sie müssen nur ein Array der Größe 20, dass die Warteschlange stellen die 732 00:30:33,930 --> 00:30:37,070 erst jetzt zu sagen, sobald wir anfangen zu sprechen zu diesen höheren Probleme Ebene 733 00:30:37,070 --> 00:30:38,890 Sie können es umsetzen in einer beliebigen Anzahl von Möglichkeiten. 734 00:30:38,890 --> 00:30:42,030 Und es ist wahrscheinlich gerade dabei, sein einen Kompromiss in Raum und Zeit 735 00:30:42,030 --> 00:30:43,950 oder einfach nur in Ihrem eigenen Code Komplexität. 736 00:30:43,950 --> 00:30:45,380 >> Was ist mit einem Stapel? 737 00:30:45,380 --> 00:30:48,190 Nun, ein Stapel, auch wir gesehen haben könnte gerade diese Fächer sein. 738 00:30:48,190 --> 00:30:50,007 Und man könnte dies ein Array implementieren. 739 00:30:50,007 --> 00:30:53,090 Aber irgendwann, wenn Sie ein Array verwenden, was los ist, um zu den Tabletts passieren 740 00:30:53,090 --> 00:30:54,173 Sie versuchen, zu legen? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 In Ordnung. 743 00:30:55,670 --> 00:30:57,490 Sie sind nur gehen, um in der Lage, so hoch zu gehen. 744 00:30:57,490 --> 00:31:00,156 Und ich denke, in Mather sie tatsächlich in dieser Öffnung ausgespart ist. 745 00:31:00,156 --> 00:31:01,950 Also ja, es ist fast wie Mather wird mit 746 00:31:01,950 --> 00:31:03,783 ein Array mit fester Größe, Da Sie nur 747 00:31:03,783 --> 00:31:08,302 passen so viele Schalen in dieser Öffnung in die Wand unten Knie der Menschen. 748 00:31:08,302 --> 00:31:10,010 Und damit auch sein mag sagte ein Array sein, 749 00:31:10,010 --> 00:31:14,300 aber wir könnten sicherlich umsetzen, dass allgemein mit einer verknüpften Liste. 750 00:31:14,300 --> 00:31:16,390 >> Nun, was ist mit anderen Datenstruktur? 751 00:31:16,390 --> 00:31:18,760 Lassen Sie mich nach oben ziehen ein anderer visueller hier. 752 00:31:18,760 --> 00:31:24,710 So etwas wie diesen hier? 753 00:31:24,710 --> 00:31:28,920 Warum könnte es sinnvoll sein, nicht etwas so schick wie ein Trie, die 754 00:31:28,920 --> 00:31:32,370 sahen wir hatten diese sehr breiten Knoten, von denen jede in einem Array? 755 00:31:32,370 --> 00:31:35,740 Aber was, wenn wir etwas tun, mehr einfach, wie ein alter Schulstammbaum, 756 00:31:35,740 --> 00:31:38,110 jeder, dessen Knoten hier gerade Speichern einer Nummer. 757 00:31:38,110 --> 00:31:42,180 Statt einem Namen oder einem Abkömmling gerade Speichern einer Nummer wie diese. 758 00:31:42,180 --> 00:31:45,250 >> Nun, der Jargon, die wir in Datenstrukturen ist beide Versuche 759 00:31:45,250 --> 00:31:49,510 und Bäumen, wo ein Trie ist wieder nur einer, dessen Knoten-Arrays, 760 00:31:49,510 --> 00:31:51,680 ist immer noch, was Sie vielleicht Verwenden von der Grundschule 761 00:31:51,680 --> 00:31:53,860 wenn Sie eine Familie haben tree-- Blätter und die Wurzel 762 00:31:53,860 --> 00:31:57,250 des Baumes und die Kinder des Eltern und Geschwister davon. 763 00:31:57,250 --> 00:32:03,670 Und wir könnten einen Baum zu implementieren, zum Beispiel so einfach wie diese. 764 00:32:03,670 --> 00:32:07,420 Ein Baum, wenn er als ein Knoten, eines diese Kreise, die eine Reihe hat, 765 00:32:07,420 --> 00:32:09,947 es ist nicht zu haben, einen Zeiger, sondern zwei. 766 00:32:09,947 --> 00:32:11,780 Und sobald Sie hinzufügen ein zweiter Zeiger, Sie 767 00:32:11,780 --> 00:32:13,905 tatsächlich jetzt machen sort der zweidimensionalen Daten 768 00:32:13,905 --> 00:32:14,780 Strukturen im Speicher. 769 00:32:14,780 --> 00:32:16,660 Ähnlich wie eine zweidimensionale Array, können Sie 770 00:32:16,660 --> 00:32:18,904 haben Art von zweidimensionalen verkettete Listen, sondern diejenigen, 771 00:32:18,904 --> 00:32:20,820 dass ein Muster folgen wo es keine Zyklen. 772 00:32:20,820 --> 00:32:24,487 Es ist wirklich ein Baum mit einem Großeltern Weg bis hier und dann 773 00:32:24,487 --> 00:32:27,320 einige Eltern und Kinder und Enkel und Urenkel. 774 00:32:27,320 --> 00:32:28,370 und so weiter. 775 00:32:28,370 --> 00:32:32,390 >> Aber was ist wirklich ordentlich darüber zu, nur, um Ihnen mit ein bisschen Code zu necken, 776 00:32:32,390 --> 00:32:35,370 Rückruf Rekursion aus eine Weile zurück, wobei 777 00:32:35,370 --> 00:32:38,220 Sie eine Funktion, die sich selbst aufruft. 778 00:32:38,220 --> 00:32:41,140 Dies ist eine schöne Gelegenheit, um etwas umzusetzen 779 00:32:41,140 --> 00:32:42,920 wie Rekursion, denn darüber nachzudenken. 780 00:32:42,920 --> 00:32:43,860 >> Dies ist ein Baum. 781 00:32:43,860 --> 00:32:48,040 Und ich habe schon ein wenig anal mit, wie Ich habe die ganzen Zahlen auf die Straße. 782 00:32:48,040 --> 00:32:51,020 So sehr, dass es eine spezielle hat name-- einen binären Suchbaum. 783 00:32:51,020 --> 00:32:53,460 Jetzt haben wir von binären gehört suchen, aber können Sie 784 00:32:53,460 --> 00:32:55,180 Arbeit nach hinten vom Namen dieses Ding? 785 00:32:55,180 --> 00:32:59,280 Was ist das Muster, wie I eingefügt die ganzen Zahlen in diesem Baum? 786 00:32:59,280 --> 00:33:00,696 Es ist nicht willkürlich. 787 00:33:00,696 --> 00:33:01,570 Es gibt einige Muster. 788 00:33:01,570 --> 00:33:02,090 Ja. 789 00:33:02,090 --> 00:33:03,370 >> PUBLIKUM: Kleinere auf der linken Seite. 790 00:33:03,370 --> 00:33:03,690 >> DAVID MALAN: Yeah. 791 00:33:03,690 --> 00:33:05,062 Kleineren sind auf der linken Seite. 792 00:33:05,062 --> 00:33:06,270 Größeren sind auf der rechten Seite. 793 00:33:06,270 --> 00:33:12,940 So dass eine wahre Aussage ist eine Mutter größer ist als seine linke Kind, 794 00:33:12,940 --> 00:33:14,850 aber weniger als seine rechte Kind. 795 00:33:14,850 --> 00:33:17,750 Und das allein ist selbst ein rekursive verbale Definition 796 00:33:17,750 --> 00:33:20,500 weil Sie, dass gelten elbe Logik jedem Knoten 797 00:33:20,500 --> 00:33:23,080 und es ist nur Sumpf heraus, eine Basis Fall, wenn Sie 798 00:33:23,080 --> 00:33:25,740 wird, wenn Sie eine der Hit die Blätter, sozusagen 799 00:33:25,740 --> 00:33:28,580 wo ein Abschied hat keine Kinder weiter. 800 00:33:28,580 --> 00:33:30,614 >> Nun, wie könnte man die Zahl 44 zu finden? 801 00:33:30,614 --> 00:33:32,280 Sie würden an der Wurzel beginnen und sagen, hm. 802 00:33:32,280 --> 00:33:35,690 55 ist nicht 44 Also will ich gehen rechts oder will ich nach links gehen? 803 00:33:35,690 --> 00:33:37,190 Nun, offensichtlich möchten Sie links. 804 00:33:37,190 --> 00:33:40,060 Und so ist es nur wie das Telefon Buchbeispiel in binäre Suche 805 00:33:40,060 --> 00:33:41,099 allgemeiner. 806 00:33:41,099 --> 00:33:43,390 Aber wir Umsetzung jetzt ein wenig mehr dynamisch 807 00:33:43,390 --> 00:33:45,339 als ein Array könnte ermöglichen. 808 00:33:45,339 --> 00:33:48,130 Und in der Tat, wenn Sie wollen aussehen auf den Code, auf den ersten Blick klar. 809 00:33:48,130 --> 00:33:49,671 Es sieht aus wie eine ganze Reihe von Linien. 810 00:33:49,671 --> 00:33:51,220 Aber es ist schön einfach. 811 00:33:51,220 --> 00:33:54,490 Wenn Sie eine Funktion implementieren möchten genannt Suche, deren Zweck im Leben 812 00:33:54,490 --> 00:33:57,290 ist es, nach einem Wert suchen wie n eine ganze Zahl ist, 813 00:33:57,290 --> 00:34:01,756 und Sie in einer Eins pointer-- vergangen sind ein Zeiger zu dem Knoten der Wurzeln, 814 00:34:01,756 --> 00:34:04,380 vielmehr jenes Baumes, aus dem Sie alles andere zugreifen können, 815 00:34:04,380 --> 00:34:08,850 merken, wie unkompliziert Sie können die Logik zu implementieren. 816 00:34:08,850 --> 00:34:10,880 Wenn Baum ist null, offensichtlich ist es nicht da. 817 00:34:10,880 --> 00:34:11,880 Lass uns einfach return false. 818 00:34:11,880 --> 00:34:12,000 Richtig? 819 00:34:12,000 --> 00:34:14,040 Wenn Sie geben es nichts, dort nichts zu finden. 820 00:34:14,040 --> 00:34:17,900 >> Sonst, wenn n kleiner ist Baum Pfeil N- jetzt arrow n, 821 00:34:17,900 --> 00:34:20,670 erinnern wir uns vorgestellt Super kurz den anderen Tag, 822 00:34:20,670 --> 00:34:25,100 und das bedeutet, nur de-Referenz die Zeiger und Blick auf die Feld namens n. 823 00:34:25,100 --> 00:34:27,690 So bedeutet es gehen dort und Blick auf das Feld genannt n. 824 00:34:27,690 --> 00:34:33,810 Also, wenn n der Wert euch gegeben sind, ist weniger als der Wert in der Baum integer, 825 00:34:33,810 --> 00:34:35,449 Wohin möchten Sie reisen? 826 00:34:35,449 --> 00:34:36,389 Nach links. 827 00:34:36,389 --> 00:34:37,780 >> So bemerken die Rekursion. 828 00:34:37,780 --> 00:34:39,860 Ich returning-- nicht wahr. 829 00:34:39,860 --> 00:34:40,989 Nicht falsch. 830 00:34:40,989 --> 00:34:45,670 Ich bin zurück was die Antwort ist von einem Aufruf mich, vorbei 831 00:34:45,670 --> 00:34:50,100 eine n wieder, die redundante ist, aber was ist jetzt etwas anders? 832 00:34:50,100 --> 00:34:51,989 Wie mache ich das Problem kleiner? 833 00:34:51,989 --> 00:34:54,920 Ich bin vorbei, die als zweiter Argument, nicht die Wurzel des Baumes, 834 00:34:54,920 --> 00:34:59,616 aber das linke Kind in diesem Fall. 835 00:34:59,616 --> 00:35:00,990 Also ich bin vorbei im linken Kind. 836 00:35:00,990 --> 00:35:04,720 >> Inzwischen, wenn n größer ist als der Knoten Ich bin derzeit auf der Suche bei, 837 00:35:04,720 --> 00:35:06,690 Ich suche die rechte Seite. 838 00:35:06,690 --> 00:35:10,880 Andernfalls, wenn der Baum nicht null ist, und wenn das Element ist nicht auf die linke 839 00:35:10,880 --> 00:35:13,240 und es ist nicht nach rechts, was ist wunderbar der Fall? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Wir haben tatsächlich festgestellt, die Knoten in Frage, und so kehren wir wahr. 842 00:35:18,440 --> 00:35:21,490 >> Also haben wir nur an der Oberfläche gekratzt jetzt einige dieser Datenstrukturen. 843 00:35:21,490 --> 00:35:24,370 In Problem stellte fünf du wirst erkunden diese noch weiter, 844 00:35:24,370 --> 00:35:27,250 und Sie werden Ihr Design gegeben werden Wahl, wie um dies zu realisieren. 845 00:35:27,250 --> 00:35:30,250 Was möchte ich zu dem Schluss, auf ist nur ein 30 Sekunden Teaser 846 00:35:30,250 --> 00:35:32,080 von dem, was erwartet nächste Woche und darüber hinaus. 847 00:35:32,080 --> 00:35:35,390 >> Wie wir begin-- Glück Dir evtl. think-- langsam unseren Übergang 848 00:35:35,390 --> 00:35:38,680 aus der Welt von C und Unter Implementierungsebene Einzelheiten 849 00:35:38,680 --> 00:35:42,090 zu einer Welt, in der wir für selbst selbstverständlich, dass jemand anderes hat endlich 850 00:35:42,090 --> 00:35:44,010 diese Daten umgesetzt Strukturen für uns, 851 00:35:44,010 --> 00:35:47,570 und wir beginnen, das zu verstehen, realen Welt mittels Durchführungs 852 00:35:47,570 --> 00:35:50,560 Web-basierte Programme und Webseiten allgemeiner 853 00:35:50,560 --> 00:35:52,910 und auch die sehr sicherheits Auswirkungen, die wir nur haben 854 00:35:52,910 --> 00:35:54,850 begonnen, um die Oberfläche zu zerkratzen. 855 00:35:54,850 --> 00:35:57,320 Hier ist, was uns erwartet in den kommenden Tagen. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO PLAYBACK] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Er Kam mit einer Botschaft, mit einem Protokoll alle seine eigenen. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Er kam in eine Welt der grausamen Firewalls, gefühllos Router, 861 00:36:30,894 --> 00:36:33,368 und Gefahren weit schlimmer als der Tod. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Er ist schnell. 864 00:36:36,236 --> 00:36:37,980 Er ist stark. 865 00:36:37,980 --> 00:36:42,830 Er ist TCP / IP, und er ist Ihre Adresse bekam. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Warriors of the Net". 868 00:36:48,074 --> 00:36:49,660 [END VIDEO PLAYBACK] 869 00:36:49,660 --> 00:36:50,910 DAVID MALAN: Nächste Woche. 870 00:36:50,910 --> 00:36:51,880 Wir werden Sie dann sehen. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VIDEO PLAYBACK] 873 00:36:56,060 --> 00:36:59,240 -Und Jetzt, "Deep Thoughts" durch Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Beginnt immer Vorlesungen mit: "In Ordnung." 876 00:37:05,820 --> 00:37:08,750 Warum nicht: "Hier ist die Lösung in dieser Woche das Problem set " 877 00:37:08,750 --> 00:37:12,180 oder "Wir geben euch alle ein A?" 878 00:37:12,180 --> 00:37:13,380 [Lacht] 879 00:37:13,380 --> 00:37:15,530 [END VIDEO PLAYBACK]