1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[Muziek]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID MALAN: Dit is CS50.

5
00:00:14,010 --> 00:00:18,090
Dit is zowel het begin en het
end-- zoals literally-- bijna het einde

6
00:00:18,090 --> 00:00:18,825
van week zes.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> Ik dacht dat ik zou delen een
beetje een leuk feitje.

9
00:00:22,640 --> 00:00:25,370
Ik trok dit uit een
data afgelopen semester in te stellen.

10
00:00:25,370 --> 00:00:29,710
U herinnert zich misschien dat we u vragen op elke
p set formulier als je hebt online bekeken

11
00:00:29,710 --> 00:00:31,580
of als je hebt bijgewoond in persoon.

12
00:00:31,580 --> 00:00:33,020
En hier is de data.

13
00:00:33,020 --> 00:00:34,710
Dus vandaag was heel erg voorspelbaar.

14
00:00:34,710 --> 00:00:37,126
Maar we wilden een beetje door te brengen
van tijd met jou toch.

15
00:00:37,126 --> 00:00:40,599
Zou iemand graag waarom dit vermoeden
grafiek is zo jaggy, up down, up down,

16
00:00:40,599 --> 00:00:41,265
zo consequent?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
Wat doen elk van de pieken
en dalen vertegenwoordigen?

19
00:00:45,130 --> 00:00:46,005
>> Publiek: [onverstaanbaar]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID MALAN: Inderdaad.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
En meer vermakelijk, god verhoede,
we houden een lezing op een vrijdag

24
00:00:55,480 --> 00:00:58,960
aan het begin van het semester,
dat is wat we zien gebeuren.

25
00:00:58,960 --> 00:01:03,430
Dus vandaag, we deelnemen aan een beetje
meer over datastructuren.

26
00:01:03,430 --> 00:01:06,660
En meer van een vaste stof
mentaal model voor problemen op vijf,

27
00:01:06,660 --> 00:01:07,450
die is nu uit.

28
00:01:07,450 --> 00:01:10,817
Spelfouten, waarin, zullen we
overhandigen u een tekstbestand zo'n 100.000

29
00:01:10,817 --> 00:01:12,650
plus woorden Engels, en
je gaat te hebben

30
00:01:12,650 --> 00:01:17,770
om erachter te komen hoe ze slim te laden
in het geheugen, in het RAM, met behulp van een aantal gegevens

31
00:01:17,770 --> 00:01:19,330
structuur van uw keuze.

32
00:01:19,330 --> 00:01:22,470
>> Nu is een dergelijke datastructuur kan
, maar waarschijnlijk niet zijn,

33
00:01:22,470 --> 00:01:25,630
de vrij simplistische gelinkte lijst,
die we vorige keer geïntroduceerd.

34
00:01:25,630 --> 00:01:29,220
En een gelinkte lijst had tenminste
een voordeel over een array.

35
00:01:29,220 --> 00:01:32,096
Wat is een voordeel van
een gekoppelde lijst misschien wel?

36
00:01:32,096 --> 00:01:32,950
>> Publiek: Insertion.

37
00:01:32,950 --> 00:01:33,908
>> DAVID MALAN: Insertion.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
Wat bedoel je daarmee?

40
00:01:35,196 --> 00:01:37,872
>> Publiek: Overal langs
de lijst [onverstaanbaar].

41
00:01:37,872 --> 00:01:38,770
>> DAVID MALAN: Goed.

42
00:01:38,770 --> 00:01:42,090
Dus je kunt een element waar te voegen
je wilt in het midden van de lijst

43
00:01:42,090 --> 00:01:45,490
zonder iets te schuifelen,
die we tot de conclusie, in onze sorteercentra

44
00:01:45,490 --> 00:01:47,630
discussies, is niet
noodzakelijk een goede zaak,

45
00:01:47,630 --> 00:01:51,200
omdat het tijd kost om daadwerkelijk verplaatsen
al deze mensen links of rechts.

46
00:01:51,200 --> 00:01:55,540
En dus met een gelinkte lijst, kunt u
alleen toe te wijzen met malloc, een nieuw knooppunt,

47
00:01:55,540 --> 00:01:58,385
en dan update een paar
pointers-- twee, drie operaties max--

48
00:01:58,385 --> 00:02:01,480
en we zijn in staat om iemand sleuf
in ergens in een lijst.

49
00:02:01,480 --> 00:02:03,550
>> Wat anders was voordelig
over een gekoppelde lijst?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
Yeah?

52
00:02:05,659 --> 00:02:06,534
>> Publiek: [onverstaanbaar]

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
Het is echt dynamisch.

58
00:02:12,070 --> 00:02:15,100
En dat je niet plegen,
vooraf enkele vaste grootte

59
00:02:15,100 --> 00:02:18,750
stuk van het geheugen, zoals je zou hebben
om met een array, de kop van die

60
00:02:18,750 --> 00:02:22,455
is dat je alleen op knooppunten kan toewijzen
vraag daarbij met alleen zoveel ruimte

61
00:02:22,455 --> 00:02:23,330
als je eigenlijk nodig hebt.

62
00:02:23,330 --> 00:02:26,830
In tegenstelling tot een array, zou je
per ongeluk te weinig toe te wijzen.

63
00:02:26,830 --> 00:02:28,871
En dan is het gewoon
om een ​​pijn in de nek

64
00:02:28,871 --> 00:02:32,440
naar een nieuw groter scala herverdelen, kopiëren
alles over, gratis de oude array,

65
00:02:32,440 --> 00:02:33,990
en ga dan verder over uw bedrijf.

66
00:02:33,990 --> 00:02:37,479
Of erger nog, zou je weg te wijzen
meer geheugen dan je eigenlijk nodig hebt,

67
00:02:37,479 --> 00:02:40,520
en dus je gaat om een ​​zeer hebben
dunbevolkte array, om zo te zeggen.

68
00:02:40,520 --> 00:02:44,350
>> Dus een gelinkte lijst geeft u deze
voordelen van dynamiek en flexibiliteit

69
00:02:44,350 --> 00:02:46,080
met inserties en deleties.

70
00:02:46,080 --> 00:02:48,000
Maar zeker moet er een prijs betaald worden.

71
00:02:48,000 --> 00:02:50,000
In feite is één van de thema
verkend quiz nul

72
00:02:50,000 --> 00:02:52,430
was een paar van de trade-offs
we hebben tot nu toe gezien.

73
00:02:52,430 --> 00:02:56,161
Dus wat is een prijs die betaald of een
nadeel van een gelinkte lijst?

74
00:02:56,161 --> 00:02:56,660
Yeah.

75
00:02:56,660 --> 00:02:57,560
>> Publiek: Geen random access.

76
00:02:57,560 --> 00:02:58,809
>> DAVID MALAN: Geen random access.

77
00:02:58,809 --> 00:02:59,540
Maar who cares?

78
00:02:59,540 --> 00:03:01,546
Random access klinkt niet overtuigend.

79
00:03:01,546 --> 00:03:02,421
>> Publiek: [onverstaanbaar]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID MALAN: Precies.

82
00:03:05,740 --> 00:03:07,580
Als je wilt hebben
een zekere algorithm--

83
00:03:07,580 --> 00:03:10,170
en laat me eigenlijk voorstellen
binary search name die

84
00:03:10,170 --> 00:03:12,600
is degene die we hebben nogal een bit-- gebruikt
als je geen random access hebben,

85
00:03:12,600 --> 00:03:15,516
kun je dat eenvoudige rekenkundige niet doen
vinden als het middelste element

86
00:03:15,516 --> 00:03:16,530
en springen recht op.

87
00:03:16,530 --> 00:03:20,239
U moet in plaats daarvan om te beginnen bij het eerste
element en lineair zoeken van links

88
00:03:20,239 --> 00:03:22,780
naar rechts als u wilt weten
het midden of een ander element.

89
00:03:22,780 --> 00:03:24,410
>> Publiek: Het duurt waarschijnlijk meer geheugen.

90
00:03:24,410 --> 00:03:25,040
>> DAVID MALAN: neemt meer geheugen.

91
00:03:25,040 --> 00:03:27,464
Waar is dat extra
kosten komen van de in het geheugen?

92
00:03:27,464 --> 00:03:28,339
>> Publiek: [onverstaanbaar]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID MALAN: Precies.

95
00:03:33,440 --> 00:03:35,679
In dit geval hier, hadden we
een gelinkte lijst van gehele getallen,

96
00:03:35,679 --> 00:03:37,470
en toch zijn we het verdubbelen
de hoeveelheid geheugen

97
00:03:37,470 --> 00:03:39,680
we nodig hebben door ook opslaan van deze pointers.

98
00:03:39,680 --> 00:03:42,090
Nu minder van een big deal als
uw structs groter worden

99
00:03:42,090 --> 00:03:45,320
en je bent het opslaan geen nummer maar
misschien een student of een ander object.

100
00:03:45,320 --> 00:03:46,880
Maar het punt blijft zeker.

101
00:03:46,880 --> 00:03:49,421
Dus een aantal bewerkingen
geweest op de lijsten werden genoemd

102
00:03:49,421 --> 00:03:50,570
waren grote O van N-- lineair.

103
00:03:50,570 --> 00:03:54,730
Dingen zoals het inbrengen of zoekopdracht
of deletie bij een element

104
00:03:54,730 --> 00:03:57,720
toevallig op het einde van
de lijst of het nu al dan niet gesorteerd.

105
00:03:57,720 --> 00:04:01,167
>> Soms heb je zou je geluk en in
dus ondergrenzen op deze operaties

106
00:04:01,167 --> 00:04:04,250
Ook constante tijd zijn als je
altijd naar het eerste element,

107
00:04:04,250 --> 00:04:05,070
bijvoorbeeld.

108
00:04:05,070 --> 00:04:09,360
Maar uiteindelijk hebben we beloofd
naar de heilige graal te bereiken

109
00:04:09,360 --> 00:04:12,630
gegevensstructuren, of
sommige benadering daarvan,

110
00:04:12,630 --> 00:04:14,290
door middel van een constante tijd.

111
00:04:14,290 --> 00:04:17,579
Kunnen we elementen vinden of elementen toe te voegen
of elementen uit een lijst verwijderen?

112
00:04:17,579 --> 00:04:19,059
We zullen heel snel zien.

113
00:04:19,059 --> 00:04:21,100
En het blijkt dat één
van de mechanismen die we

114
00:04:21,100 --> 00:04:23,464
zal gaan gebruiken vandaag,
jaarlijkse gebruik in p vijf,

115
00:04:23,464 --> 00:04:24,630
is eigenlijk redelijk bekend.

116
00:04:24,630 --> 00:04:27,430
Bijvoorbeeld, als het een groep
examen boeken, die elk

117
00:04:27,430 --> 00:04:29,660
heeft een student de eerste
voornaam en achternaam op,

118
00:04:29,660 --> 00:04:31,820
en ik pak ze op uit
aan het einde van een examen,

119
00:04:31,820 --> 00:04:33,746
en ze zijn allemaal vrij
veel in een willekeurige volgorde,

120
00:04:33,746 --> 00:04:36,370
en we willen gaan over het sorteren
deze examens zodat zodra graded

121
00:04:36,370 --> 00:04:38,661
het is gewoon een stuk makkelijker en
sneller om ze uit te delen terug

122
00:04:38,661 --> 00:04:40,030
aan studenten alfabetisch.

123
00:04:40,030 --> 00:04:42,770
Wat zou je instincten zijn
voor een stapel van examens als deze?

124
00:04:42,770 --> 00:04:45,019
>> Nou, als je net als ik, je
zou kunnen zien dat dit m,

125
00:04:45,019 --> 00:04:48,505
dus ik ga dit soort zetten in,
als dit is mijn tafel of mijn verdieping waar

126
00:04:48,505 --> 00:04:50,650
Ik ben het verspreiden van dingen
out-- of mijn reeks really--

127
00:04:50,650 --> 00:04:52,210
Ik zou al de mevrouw in daar te zetten.

128
00:04:52,210 --> 00:04:52,710
Oh.

129
00:04:52,710 --> 00:04:55,020
Hier is een A. Dus ik zou
zet de Zoals hier.

130
00:04:55,020 --> 00:04:55,520
Oh.

131
00:04:55,520 --> 00:04:57,980
Hier is nog een A. Ik ga
te zetten dat meer dan hier.

132
00:04:57,980 --> 00:05:02,490
Hier is een Z. Hier is een andere M. En zo
Ik zou kunnen beginnen met het maken van palen als deze.

133
00:05:02,490 --> 00:05:06,620
En dan misschien zou ik in later gaan
en een soort van zeer nitpicky-ly sorteren

134
00:05:06,620 --> 00:05:07,710
de individuele palen.

135
00:05:07,710 --> 00:05:11,300
Maar het punt is dat ik zou kijken
aan de ingang dat ik handed

136
00:05:11,300 --> 00:05:14,016
en ik zou een aantal berekende maken
besluit op basis van die input.

137
00:05:14,016 --> 00:05:15,640
Als het begint met A, zet het daar.

138
00:05:15,640 --> 00:05:18,980
Als het begint met Z, zet het dan
daar, en alles daar tussenin.

139
00:05:18,980 --> 00:05:22,730
>> Dus dit is een techniek die
algemeen bekend als hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
Dit betekent gewoonlijk met als
invoeren en gebruiken die ingang te berekenen

141
00:05:26,550 --> 00:05:30,940
een waarde, meestal een aantal, en dat
nummer is de index in een opslagbuffer

142
00:05:30,940 --> 00:05:32,260
container, zoals een array.

143
00:05:32,260 --> 00:05:35,490
Dus met andere woorden, zou ik een heb
hash-functie, als ik in mijn hoofd,

144
00:05:35,490 --> 00:05:37,940
dat als ik iemand zie is
naam die begint met A,

145
00:05:37,940 --> 00:05:40,190
Ik ga naar de kaart die
tot nul in mijn hoofd.

146
00:05:40,190 --> 00:05:44,160
En als ik iemand zie met Z, ik ben
ga naar de kaart die op 25 in mijn hoofd

147
00:05:44,160 --> 00:05:46,220
en zet dan die in
de laatste meest stapel.

148
00:05:46,220 --> 00:05:50,990
>> Nu, als je denkt over het niet mijn hersenen
maar een C-programma, welke nummers kan

149
00:05:50,990 --> 00:05:53,170
u vertrouwen op om dat hetzelfde resultaat te bereiken?

150
00:05:53,170 --> 00:05:55,594
Met andere woorden, als je
had het ASCII-teken A,

151
00:05:55,594 --> 00:05:57,510
hoe bepaal
wat emmer om het aan te brengen?

152
00:05:57,510 --> 00:05:59,801
U heeft waarschijnlijk niet wilt
zet het in emmer 65, dat

153
00:05:59,801 --> 00:06:01,840
zou zijn als daar
zonder goede reden.

154
00:06:01,840 --> 00:06:04,320
Waar wil je A zetten
in termen van de ASCII-waarde?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
Waar wilt u doen om zijn ASCII
waarde om te komen met een slimmere emmer

157
00:06:08,920 --> 00:06:09,480
om het aan te brengen?

158
00:06:09,480 --> 00:06:10,206
>> Publiek: Minus A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID MALAN: Yeah.

160
00:06:10,956 --> 00:06:13,190
Zo min A of min
bijzonder 65 als het

161
00:06:13,190 --> 00:06:18,240
een hoofdletter A. Of 98 als
het is een kleine letter a.

162
00:06:18,240 --> 00:06:21,300
En dus dat zou ons in staat stellen, zeer
eenvoudig en zeer rekenkundig,

163
00:06:21,300 --> 00:06:23,260
zet iets in een emmer als dat.

164
00:06:23,260 --> 00:06:26,010
Dus het blijkt dat we eigenlijk doen
dit zo goed zelfs met de quizzen.

165
00:06:26,010 --> 00:06:29,051
>> Dus je zou herinneren u omcirkeld uw
naam lesgeven collega's op de cover.

166
00:06:29,051 --> 00:06:32,270
En de namen van de TF's werden georganiseerd
in deze kolommen alfabetisch,

167
00:06:32,270 --> 00:06:34,400
Nou, geloof het of niet,
wanneer alle 80 plus van ons

168
00:06:34,400 --> 00:06:37,800
kwamen bij elkaar de andere nacht naar rang,
de laatste stap in onze sorteerproces

169
00:06:37,800 --> 00:06:41,830
is om de quizzen hash in een grote
ruimte van grond aan de [onverstaanbaar]

170
00:06:41,830 --> 00:06:45,110
en tot ieders quizzen lay out
precies de volgorde van TF

171
00:06:45,110 --> 00:06:47,700
namen op de omslag, omdat
dan is het een stuk makkelijker voor ons

172
00:06:47,700 --> 00:06:51,290
om door middel van dat met lineaire
zoeken of een soort van slimheid

173
00:06:51,290 --> 00:06:54,050
een TF te vinden zijn
quizzen van haar leerlingen.

174
00:06:54,050 --> 00:06:56,060
>> Dus dit idee van hashing
dat je zult zien is

175
00:06:56,060 --> 00:07:00,520
vrij krachtig is eigenlijk best
alledaags en zeer intuïtief,

176
00:07:00,520 --> 00:07:03,000
net als misschien verdelen en
heers was in week nul.

177
00:07:03,000 --> 00:07:05,250
Ik snel vooruit naar de hackathon
een paar jaar geleden.

178
00:07:05,250 --> 00:07:08,040
Dit was Zamyla en een paar
ander personeel groet studenten

179
00:07:08,040 --> 00:07:09,030
als ze kwam.

180
00:07:09,030 --> 00:07:12,680
En we hadden een hele hoop van het vouwen
tafels daar met naamplaatjes.

181
00:07:12,680 --> 00:07:15,380
En we hadden de naamplaatjes georganiseerd
met als de As daar

182
00:07:15,380 --> 00:07:16,690
en de Zs daar.

183
00:07:16,690 --> 00:07:20,350
En dus een van de TF's heel slim
schreef dit als de instructies

184
00:07:20,350 --> 00:07:21,030
voor de dag.

185
00:07:21,030 --> 00:07:24,480
En in week 12 van het semester deze
alles was volkomen logisch en iedereen

186
00:07:24,480 --> 00:07:25,310
wist wat te doen.

187
00:07:25,310 --> 00:07:27,900
Maar wanneer je hebt
wachtrij op dezelfde wijze

188
00:07:27,900 --> 00:07:30,272
je bent de uitvoering van de
Hetzelfde idee van een hash.

189
00:07:30,272 --> 00:07:31,730
Dus laten we formaliseren het een beetje.

190
00:07:31,730 --> 00:07:32,890
Hier is een array.

191
00:07:32,890 --> 00:07:36,820
Het is getrokken om een ​​beetje
breed net uit te beelden, visueel,

192
00:07:36,820 --> 00:07:38,920
dat we strings zou kunnen brengen
in iets als dit.

193
00:07:38,920 --> 00:07:41,970
En dit array
duidelijk van de grootte 26 in totaal.

194
00:07:41,970 --> 00:07:43,935
En het ding heet
tafel willekeurig.

195
00:07:43,935 --> 00:07:48,930
Maar dit is slechts vertolking van een kunstenaar
van wat een hash table zou kunnen zijn.

196
00:07:48,930 --> 00:07:52,799
>> Dus een hash table nu gaat
zijn een hoger niveau datastructuur.

197
00:07:52,799 --> 00:07:54,840
Aan het eind van de dag
we staan ​​op het punt om te zien dat u

198
00:07:54,840 --> 00:07:58,700
kan een hash table, implementeren die
is net als de check-in lijn

199
00:07:58,700 --> 00:08:02,059
bij een hackathon dit veel op
tabel gebruikt voor het sorteren examen boeken.

200
00:08:02,059 --> 00:08:03,850
Maar een hash table is
soort van dit hoge niveau

201
00:08:03,850 --> 00:08:08,250
concept dat een array kunnen gebruiken
onder de motorkap om het te implementeren,

202
00:08:08,250 --> 00:08:11,890
of het kan een lengte lijst gebruiken of zelfs
misschien enkele andere datastructuren.

203
00:08:11,890 --> 00:08:15,590
En nu is dat de theme-- nemen
sommige van deze fundamentele ingrediënten

204
00:08:15,590 --> 00:08:18,310
zoals een array en dit gebouw
blokkeren nu met een lengte lijst

205
00:08:18,310 --> 00:08:21,740
en het zien van wat we kunnen bouwen
naast die welke, zoals ingrediënten

206
00:08:21,740 --> 00:08:26,550
in een recept, waardoor meer en meer
interessant en nuttig eindresultaten.

207
00:08:26,550 --> 00:08:28,680
>> Dus met de hash table
we zouden het uit te voeren

208
00:08:28,680 --> 00:08:32,540
in het geheugen van dit picturaal als, maar
hoe zou het eigenlijk zijn gecodeerd up?

209
00:08:32,540 --> 00:08:33,789
Nou, misschien zo eenvoudig is dit.

210
00:08:33,789 --> 00:08:38,270
Als de capaciteit in alle caps, is gewoon
sommige constant-- bijvoorbeeld 26,

211
00:08:38,270 --> 00:08:42,030
voor de 26 letters van het alphabet--
Ik zou mijn variabele tafel roepen,

212
00:08:42,030 --> 00:08:45,630
en ik zou beweren dat ik ga
zet char sterren daar, of string.

213
00:08:45,630 --> 00:08:49,880
Dus het is zo simpel als dit als je
willen een hash table implementeren.

214
00:08:49,880 --> 00:08:51,490
En toch, dit is echt gewoon een array.

215
00:08:51,490 --> 00:08:53,198
Maar nogmaals, een hash
tafel is nu wat we zullen

216
00:08:53,198 --> 00:08:57,470
noem een ​​abstract datatype dat is gewoon
soort van een conceptuele gelaagdheid op de top

217
00:08:57,470 --> 00:09:00,780
van iets meer alledaagse
nu graag een array.

218
00:09:00,780 --> 00:09:02,960
>> Nu, hoe gaan we heen
over het oplossen van problemen?

219
00:09:02,960 --> 00:09:06,980
Nou, vroeger had ik de luxe
van het hebben hier genoeg ruimte in

220
00:09:06,980 --> 00:09:09,460
zodat ik kon het zetten
quizzen ergens wilde ik.

221
00:09:09,460 --> 00:09:10,620
Dus als zou hier gaan.

222
00:09:10,620 --> 00:09:12,100
Zs zou hier gaan.

223
00:09:12,100 --> 00:09:13,230
Ms zou gaan hier.

224
00:09:13,230 --> 00:09:14,740
En toen had ik wat extra ruimte.

225
00:09:14,740 --> 00:09:18,740
Maar dit is een beetje een cheat recht
nu, omdat deze tabel, als ik echt

226
00:09:18,740 --> 00:09:22,720
dacht aan het als een array, is gewoon
gaan van bepaalde vaste omvang hebben.

227
00:09:22,720 --> 00:09:25,380
>> Dus technisch gezien, als ik trek
up van een andere student quiz

228
00:09:25,380 --> 00:09:28,490
en zie, oh, deze persoon
naam met een A begint ook,

229
00:09:28,490 --> 00:09:30,980
Ik wil dat soort om het daar te zetten.

230
00:09:30,980 --> 00:09:34,740
Maar zodra ik het daar, als
Deze tabel vormt inderdaad een matrix,

231
00:09:34,740 --> 00:09:37,840
Ik ga worden dwingende of beuken
wie deze student quiz is.

232
00:09:37,840 --> 00:09:38,340
Right?

233
00:09:38,340 --> 00:09:41,972
Als dit een array slechts één ding kan
gaan in elk van deze cellen of elementen.

234
00:09:41,972 --> 00:09:43,680
En dus heb ik soort
om te kiezen.

235
00:09:43,680 --> 00:09:45,735
>> Nu eerder het soort van I
bedrogen en deed dit of ik

236
00:09:45,735 --> 00:09:47,526
gewoon een soort van gestapelde
ze boven elkaar.

237
00:09:47,526 --> 00:09:49,170
Maar dat gaat niet in code om te vliegen.

238
00:09:49,170 --> 00:09:52,260
Dus waar kan ik de
tweede student wiens naam

239
00:09:52,260 --> 00:09:54,964
is A als alles wat ik had is dit
beschikbare ruimte in?

240
00:09:54,964 --> 00:09:57,880
En ik heb drie slots en het gebruikt
ziet eruit alsof er net een paar anderen.

241
00:09:57,880 --> 00:09:58,959
Wat zou u doen?

242
00:09:58,959 --> 00:09:59,834
Publiek: [onverstaanbaar]

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
Misschien laten we het gewoon simpel houden.

246
00:10:02,370 --> 00:10:02,660
Right?

247
00:10:02,660 --> 00:10:04,243
Het past niet waar ik wil om het te zetten.

248
00:10:04,243 --> 00:10:07,450
Dus ik ga om het te zetten
technisch gezien waar een B zou gaan.

249
00:10:07,450 --> 00:10:09,932
Nu, natuurlijk, ik begin
om mezelf te schilderen in een hoek.

250
00:10:09,932 --> 00:10:11,890
Als ik aan een student
wiens naam is eigenlijk B,

251
00:10:11,890 --> 00:10:14,840
B zal nu een beetje te verplaatsen
naar voren, zoals zou kunnen gebeuren, yep,

252
00:10:14,840 --> 00:10:17,530
indien een B is nu het moet hier gaan.

253
00:10:17,530 --> 00:10:20,180
>> En dus is deze zeer snel
kan problematisch worden,

254
00:10:20,180 --> 00:10:23,850
maar het is een techniek die eigenlijk
wordt aangeduid als lineaire sonderen,

255
00:10:23,850 --> 00:10:26,650
waarbij je gewoon rekening houden met uw
array worden langs de lijn.

256
00:10:26,650 --> 00:10:29,680
En je gewoon een soort sonde of
inspecteren elke beschikbare element

257
00:10:29,680 --> 00:10:31,360
op zoek naar een beschikbare plek.

258
00:10:31,360 --> 00:10:34,010
En zodra je merkt
één, je het laat vallen daar.

259
00:10:34,010 --> 00:10:38,390
>> Nu, wordt de prijs die nu betaald
deze oplossing is wat?

260
00:10:38,390 --> 00:10:41,300
We hebben een vaste grootte array,
en toen ik de namen in te voegen

261
00:10:41,300 --> 00:10:44,059
in het, althans in het begin, wat is
de looptijd van het inbrengen

262
00:10:44,059 --> 00:10:46,350
voor het aanbrengen van de studenten '
quizzen in de juiste bakken?

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
Big O van wat?

265
00:10:50,002 --> 00:10:51,147
>> Publiek: n.

266
00:10:51,147 --> 00:10:52,480
DAVID MALAN: Ik hoorde big O van n.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
Niet waar.

269
00:10:54,300 --> 00:10:56,490
Maar we zullen elkaar plagen
waarom in slechts een moment.

270
00:10:56,490 --> 00:10:57,702
Wat zou het zijn?

271
00:10:57,702 --> 00:10:58,755
>> Publiek: [onverstaanbaar]

272
00:10:58,755 --> 00:11:00,380
DAVID MALAN: En laat me visueel doen.

273
00:11:00,380 --> 00:11:04,720
Dus stel dat dit de letter S.

274
00:11:04,720 --> 00:11:05,604
>> Publiek: Het is één.

275
00:11:05,604 --> 00:11:06,520
DAVID MALAN: Het is één.

276
00:11:06,520 --> 00:11:06,710
Right?

277
00:11:06,710 --> 00:11:08,950
Dit is een array, die
betekent dat we random access.

278
00:11:08,950 --> 00:11:11,790
En als we denken van deze
als nul en dit als 25,

279
00:11:11,790 --> 00:11:13,800
en we beseffen dat,
oh, hier is mijn ingang S,

280
00:11:13,800 --> 00:11:16,350
Ik kan zeker omzetten
S, een ASCII-karakter,

281
00:11:16,350 --> 00:11:18,540
een overeenkomstig aantal
tussen nul en 25

282
00:11:18,540 --> 00:11:20,910
en dan meteen
het zetten waar het behoort.

283
00:11:20,910 --> 00:11:26,120
>> Maar natuurlijk, zodra ik bij de
tweede persoon wiens naam is A of B of C

284
00:11:26,120 --> 00:11:29,300
uiteindelijk, als ik heb gebruikt de
lineaire indringende als mijn oplossing,

285
00:11:29,300 --> 00:11:31,360
de looptijd van
insertie in het ergste geval

286
00:11:31,360 --> 00:11:33,120
er werkelijk gaande is om te delegeren naar wat?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
En ik heb hier horen
kunnen vroeg.

289
00:11:36,045 --> 00:11:36,920
Publiek: [onverstaanbaar]

290
00:11:36,920 --> 00:11:41,620
DAVID MALAN: Dus het is n inderdaad een keer
heb je een voldoende grote dataset.

291
00:11:41,620 --> 00:11:44,410
Dus, enerzijds, indien
array is groot genoeg

292
00:11:44,410 --> 00:11:48,287
en uw gegevens is schaars genoeg, je
krijg deze mooie constante tijd.

293
00:11:48,287 --> 00:11:50,620
Maar zodra je begint
steeds meer en meer elementen,

294
00:11:50,620 --> 00:11:53,200
en gewoon statistisch je krijgt
meer mensen met de letter

295
00:11:53,200 --> 00:11:56,030
Een als hun naam of de letter
B, het kon in potentie

296
00:11:56,030 --> 00:11:57,900
overgaan in iets meer lineair.

297
00:11:57,900 --> 00:11:59,640
Dus niet helemaal perfect.

298
00:11:59,640 --> 00:12:00,690
Dus konden we beter doen?

299
00:12:00,690 --> 00:12:03,210
>> Nou, wat was onze
oplossing voor wanneer we

300
00:12:03,210 --> 00:12:06,820
willen meer dynamiek dan hebben
iets als een array toegestaan?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
Publiek: [onverstaanbaar]

303
00:12:08,960 --> 00:12:10,030
DAVID MALAN: Wat hebben we introduceren?

304
00:12:10,030 --> 00:12:10,530
Yeah.

305
00:12:10,530 --> 00:12:11,430
Dus een gelinkte lijst.

306
00:12:11,430 --> 00:12:14,430
Nou, laten we eens kijken wat een gekoppelde
lijst zou in plaats daarvan voor ons doen.

307
00:12:14,430 --> 00:12:17,630
Nou, laat ik stel voor dat we
de foto te trekken als volgt.

308
00:12:17,630 --> 00:12:19,620
Nu is dit een ander
afbeelding van een voorbeeld

309
00:12:19,620 --> 00:12:24,750
een andere tekst, eigenlijk, dat
eigenlijk met een array van grootte 31.

310
00:12:24,750 --> 00:12:28,220
En deze auteur gewoon
besloten om strings hash

311
00:12:28,220 --> 00:12:32,430
niet op naam van de persoon,
maar op basis van hun geboortedata.

312
00:12:32,430 --> 00:12:35,680
Onafhankelijk van de maand, ze dacht
als je geboren bent op de eerste van de maand

313
00:12:35,680 --> 00:12:39,580
of de 31e van een maand, de auteur
zal hash op basis van die waarde,

314
00:12:39,580 --> 00:12:44,154
zodat de namen een beetje spreiden
meer dan alleen maar 26 plekken zou kunnen stellen.

315
00:12:44,154 --> 00:12:47,320
En misschien is het een beetje meer uniforme
dan ga met alfabetische letters,

316
00:12:47,320 --> 00:12:50,236
want natuurlijk is er waarschijnlijk
meer mensen in de wereld met namen

317
00:12:50,236 --> 00:12:54,020
die beginnen met A dan zeker
andere letters van het alfabet.

318
00:12:54,020 --> 00:12:56,380
Dus misschien is dit een beetje
uniformer, uitgaande

319
00:12:56,380 --> 00:12:58,640
een uniforme verdeling
van baby's over een maand.

320
00:12:58,640 --> 00:12:59,990
>> Maar natuurlijk is dit nog steeds niet perfect.

321
00:12:59,990 --> 00:13:00,370
Right?

322
00:13:00,370 --> 00:13:01,370
We hebben van botsingen.

323
00:13:01,370 --> 00:13:04,680
Meerdere mensen in dit
datastructuur nog

324
00:13:04,680 --> 00:13:08,432
met dezelfde geboortedatum minstens
je bent ongeacht maand.

325
00:13:08,432 --> 00:13:09,640
Maar wat heeft de auteur gedaan?

326
00:13:09,640 --> 00:13:13,427
Nou, het lijkt erop dat we hebben een scala
aan de linkerkant verticaal getrokken,

327
00:13:13,427 --> 00:13:15,010
maar dat is slechts vertolking van een kunstenaar.

328
00:13:15,010 --> 00:13:18,009
Het maakt niet uit welke richting je
trekken een array, het is nog steeds een array.

329
00:13:18,009 --> 00:13:20,225
Wat is dit voor een reeks van schijnbaar?

330
00:13:20,225 --> 00:13:21,500
>> Publiek: Linked lijst.

331
00:13:21,500 --> 00:13:21,650
>> DAVID MALAN: Yeah.

332
00:13:21,650 --> 00:13:23,490
Het lijkt erop dat het een
reeks van gekoppelde lijst.

333
00:13:23,490 --> 00:13:26,490
Dus nogmaals, op dit punt van de soort
het gebruik van deze gegevensstructuren nu

334
00:13:26,490 --> 00:13:28,550
als ingrediënten meer
interessante oplossingen,

335
00:13:28,550 --> 00:13:30,862
je absoluut eens
fundamenteel, als een array,

336
00:13:30,862 --> 00:13:33,320
en neem dan iets meer
interessant als een gelinkte lijst

337
00:13:33,320 --> 00:13:36,660
en zelfs te combineren tot een nog
interessanter gegevensstructuur.

338
00:13:36,660 --> 00:13:39,630
En inderdaad, ook dit zou
een hash tabel worden genoemd,

339
00:13:39,630 --> 00:13:42,610
waarbij de array
echt de hash table,

340
00:13:42,610 --> 00:13:45,600
maar dat hash table heeft
kettingen zogezegd,

341
00:13:45,600 --> 00:13:50,220
die kan groeien of krimpen basis van de
aantal elementen die u wilt invoegen.

342
00:13:50,220 --> 00:13:52,990
>> Nu, dus, wat is er
de lopende tijd nu?

343
00:13:52,990 --> 00:13:58,030
Als ik iemand wil invoegen
wiens verjaardag is 31 oktober,

344
00:13:58,030 --> 00:13:59,040
waar komt hij of zij heen?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
Prima.

347
00:14:01,030 --> 00:14:02,819
Helemaal onderaan waar het zegt 31.

348
00:14:02,819 --> 00:14:03,610
En dat is perfect.

349
00:14:03,610 --> 00:14:05,060
Dat was constante tijd.

350
00:14:05,060 --> 00:14:08,760
Maar wat als we iemand anders vinden
wiens verjaardag is, laten we eens kijken,

351
00:14:08,760 --> 00:14:10,950
Oktober, november, 31 december?

352
00:14:10,950 --> 00:14:12,790
Waar is hij of zij gaan om te gaan?

353
00:14:12,790 --> 00:14:13,290
Hetzelfde.

354
00:14:13,290 --> 00:14:13,970
Twee stap wel.

355
00:14:13,970 --> 00:14:15,303
Dat is constant al is het niet?

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
Prima.

358
00:14:16,860 --> 00:14:17,840
Op dit moment is het.

359
00:14:17,840 --> 00:14:20,570
Maar in het algemene geval,
hoe meer mensen we voegen,

360
00:14:20,570 --> 00:14:23,790
probabilistisch, we gaan
om meer en meer botsingen te krijgen.

361
00:14:23,790 --> 00:14:26,820
>> Nu is dit een beetje
beter omdat technisch

362
00:14:26,820 --> 00:14:34,580
nu mijn ketenen zou kunnen worden in
het ergste geval hoe lang?

363
00:14:34,580 --> 00:14:38,890
Als ik n mensen in te voegen in dit meer
geavanceerde datastructuur, n mensen,

364
00:14:38,890 --> 00:14:41,080
in het ergste geval het gaat om n zijn.

365
00:14:41,080 --> 00:14:41,815
Waarom?

366
00:14:41,815 --> 00:14:43,332
>> Publiek: Want als iedereen
heeft dezelfde verjaardag,

367
00:14:43,332 --> 00:14:44,545
ze gaan om één lijn te zijn.

368
00:14:44,545 --> 00:14:45,420
DAVID MALAN: Perfect.

369
00:14:45,420 --> 00:14:47,480
Het is misschien een beetje gekunsteld,
maar echt in het ergste geval,

370
00:14:47,480 --> 00:14:50,117
als iedereen heeft dezelfde verjaardag,
gezien de ingangen u hebt,

371
00:14:50,117 --> 00:14:51,950
je gaat naar een hebben
massaal lange keten.

372
00:14:51,950 --> 00:14:54,241
En dus, zou je het kunnen noemen een
hash table, maar eigenlijk is het

373
00:14:54,241 --> 00:14:56,810
gewoon een enorme gelinkte lijst met
een hele hoop verspilde ruimte.

374
00:14:56,810 --> 00:15:00,460
Maar in het algemeen, als we aannemen dat
tenminste verjaardagen zijn uniform--

375
00:15:00,460 --> 00:15:01,750
en is het waarschijnlijk niet.

376
00:15:01,750 --> 00:15:02,587
Ik ben het maken van die up.

377
00:15:02,587 --> 00:15:04,420
Als we aannemen voor
Omwille van de bespreking

378
00:15:04,420 --> 00:15:07,717
dat zij dan in theorie, indien
Dit is de verticale voorstelling

379
00:15:07,717 --> 00:15:11,050
van de array, en dan hopelijk ben je
ga ketens die zijn, weet je,

380
00:15:11,050 --> 00:15:15,880
ongeveer dezelfde lengte waarbij elk van
deze staat voor een dag van de maand.

381
00:15:15,880 --> 00:15:19,930
>> Nu, als er 31 dagen in de maand,
dat betekent dat mijn lopende tijd echt

382
00:15:19,930 --> 00:15:25,230
is big O van n meer dan 31, die
voelt beter dan lineair.

383
00:15:25,230 --> 00:15:27,950
Maar wat was een van onze
toezeggingen een paar weken

384
00:15:27,950 --> 00:15:31,145
geleden wanneer het ging om het uiten van
de looptijd van een algoritme?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
Gewoon alleen kijken naar de hoge orde term.

387
00:15:35,190 --> 00:15:35,690
Right?

388
00:15:35,690 --> 00:15:37,400
31 is zeker nuttig.

389
00:15:37,400 --> 00:15:39,610
Maar dit is nog steeds big O van n.

390
00:15:39,610 --> 00:15:41,730
Maar een van de thema's
van het probleem te stellen vijf

391
00:15:41,730 --> 00:15:43,950
zal worden
erkennen dat absoluut,

392
00:15:43,950 --> 00:15:47,320
asymptotisch theorie
Deze gegevensstructuur

393
00:15:47,320 --> 00:15:50,470
is niet beter dan
één massieve gelinkte lijst.

394
00:15:50,470 --> 00:15:53,550
Inderdaad, in het ergste geval, dit
hash table zou kunnen delegeren naar die.

395
00:15:53,550 --> 00:15:57,620
>> Maar in de echte wereld, met ons mensen
dat de eigen Mac's of pc's of wat dan ook

396
00:15:57,620 --> 00:16:01,240
en lopen echte wereld
software op reële datasets,

397
00:16:01,240 --> 00:16:03,260
welk algoritme ga je het liefst?

398
00:16:03,260 --> 00:16:09,180
De ene daartoe stappen of het neemt
die n neemt gedeeld door 31 stappen

399
00:16:09,180 --> 00:16:12,900
om een ​​stukje data te vinden of
opzoeken wat informatie?

400
00:16:12,900 --> 00:16:16,580
Ik bedoel, absoluut de 31 merken
een verschil in de echte wereld.

401
00:16:16,580 --> 00:16:18,540
Het is 31 keer sneller.

402
00:16:18,540 --> 00:16:20,880
En wij mensen zijn zeker
gaan waarderen dat.

403
00:16:20,880 --> 00:16:23,004
>> Zo realiseren de dichotomie
er tussen eigenlijk

404
00:16:23,004 --> 00:16:25,920
praten over dingen theoretisch
en asymptotisch die zeker

405
00:16:25,920 --> 00:16:28,760
heeft waarde zoals we hebben gezien,
maar in de echte wereld,

406
00:16:28,760 --> 00:16:32,930
als je de zorg over alleen het maken van de
mens blij voor algemene ingangen,

407
00:16:32,930 --> 00:16:36,010
je zou heel goed willen accepteren
dat, ja, is lineair,

408
00:16:36,010 --> 00:16:38,360
maar het is 31 keer sneller
dan lineair kan zijn.

409
00:16:38,360 --> 00:16:41,610
En beter nog, we hebben niet alleen te
iets willekeurig doen, zoals een geboortedatum,

410
00:16:41,610 --> 00:16:44,030
konden we een beetje door te brengen
meer tijd en slimheid

411
00:16:44,030 --> 00:16:47,140
en na te denken over wat we zouden kunnen doen,
gegeven naam van een persoon en misschien

412
00:16:47,140 --> 00:16:50,130
hun geboortedatum die combineren
ingrediënten om erachter te komen wat

413
00:16:50,130 --> 00:16:52,720
dat is echt meer
uniforme en minder jaggy,

414
00:16:52,720 --> 00:16:56,250
bij wijze van spreken dan deze foto
momenteel suggereert dat het zou kunnen zijn.

415
00:16:56,250 --> 00:16:57,750
Hoe kunnen we dit implementeren in de code?

416
00:16:57,750 --> 00:17:00,280
Nou, laat ik stel voor dat we
gewoon lenen sommige syntax we hebben

417
00:17:00,280 --> 00:17:01,799
gebruikt een paar keer tot nu toe.

418
00:17:01,799 --> 00:17:03,590
En ik ga om te definiëren
een knooppunt opnieuw dat

419
00:17:03,590 --> 00:17:06,812
is een generieke term voor slechts enkele
container enige datastructuur.

420
00:17:06,812 --> 00:17:09,020
Ik ga om te stellen dat
een string gaat daar.

421
00:17:09,020 --> 00:17:11,369
Maar we gaan beginnen met het nemen
opleiders van wielen van nu.

422
00:17:11,369 --> 00:17:13,230
>> Niet meer CS50 bibliotheek
echt, tenzij je wilt

423
00:17:13,230 --> 00:17:15,230
om het te gebruiken voor uw uiteindelijke
project, dat is prima,

424
00:17:15,230 --> 00:17:18,569
maar nu gaan we terug te trekken het
gordijn en zeggen: het is gewoon een char ster.

425
00:17:18,569 --> 00:17:22,069
Dus het woord er gaat worden
naam van de persoon in kwestie.

426
00:17:22,069 --> 00:17:25,079
En nu heb ik een link
hier de volgende knoop

427
00:17:25,079 --> 00:17:28,170
zodat deze vertegenwoordigen
elk van de knooppunten

428
00:17:28,170 --> 00:17:30,950
in de keten, eventueel,
van een gelinkte lijst.

429
00:17:30,950 --> 00:17:34,090
>> En nu hoe doe ik verklaar
de hash tabel zelf?

430
00:17:34,090 --> 00:17:36,660
Hoe kan ik verklaar deze hele structuur?

431
00:17:36,660 --> 00:17:40,960
Nou ja, echt, net als ik vroeger een pointer
om alleen het eerste element van een lijst

432
00:17:40,960 --> 00:17:44,510
vóór, evenzo kan ik alleen maar zeggen
Ik gewoon een stelletje pointers nodig

433
00:17:44,510 --> 00:17:46,270
ter uitvoering van deze hele hash table.

434
00:17:46,270 --> 00:17:49,484
Ik ga naar een array
riep tafel voor hash table.

435
00:17:49,484 --> 00:17:50,900
Het zal van de omvang van de capaciteit te zijn.

436
00:17:50,900 --> 00:17:52,525
Dat is hoe veel elementen kunnen passen in het.

437
00:17:52,525 --> 00:17:56,180
En elk van deze elementen in deze
serie gaat een knooppunt ster te zijn.

438
00:17:56,180 --> 00:17:56,810
Waarom?

439
00:17:56,810 --> 00:18:00,160
Nou, per deze foto, wat ik ben
de uitvoering van de hash table als

440
00:18:00,160 --> 00:18:04,330
effectief in het begin is gewoon
deze array dat we verticaal hebt getekend,

441
00:18:04,330 --> 00:18:06,820
elk van wie de pleinen
is een pointer.

442
00:18:06,820 --> 00:18:09,170
Dat degenen die slashes hebben
door hen zijn gewoon null.

443
00:18:09,170 --> 00:18:11,410
En degenen die moeten
pijlen naar rechts

444
00:18:11,410 --> 00:18:16,140
daadwerkelijke verwijzingen naar daadwerkelijke knooppunten
ergo het begin van een gelinkte lijst.

445
00:18:16,140 --> 00:18:19,050
>> Dus hier is dan ook hoe we zouden kunnen
implementeren van een hash table die

446
00:18:19,050 --> 00:18:21,580
implementeert aparte chaining.

447
00:18:21,580 --> 00:18:22,840
Nu kunnen we beter doen?

448
00:18:22,840 --> 00:18:25,632
Oké Ik beloofde vorige keer dat
we konden constante tijd te bereiken.

449
00:18:25,632 --> 00:18:27,381
En ik soort gaf je
constante tijd hier,

450
00:18:27,381 --> 00:18:29,850
maar zei toen niet echt
constante tijd, want het is nog steeds

451
00:18:29,850 --> 00:18:31,890
afhankelijk van de totale
aantal elementen

452
00:18:31,890 --> 00:18:34,500
je invoeren in
de gegevensstructuur.

453
00:18:34,500 --> 00:18:35,980
Maar stel dat we dit deden.

454
00:18:35,980 --> 00:18:39,550
Laat me teruggaan naar het scherm over hier.

455
00:18:39,550 --> 00:18:44,520
Laat me dit ook projecteren hier, duidelijk
het scherm, en stel dat ik dit deed.

456
00:18:44,520 --> 00:18:49,300
Neem nu dat je de naam in te voegen
Daven in in mijn datastructuur.

457
00:18:49,300 --> 00:18:52,100
>> Dus ik wil een string te voegen
Daven in de datastructuur.

458
00:18:52,100 --> 00:18:54,370
Wat als ik geen gebruik maken van een
hash table, maar ik gebruik

459
00:18:54,370 --> 00:18:56,980
iets dat meer boomachtige
als een stamboom, waar

460
00:18:56,980 --> 00:18:59,670
heb je een aantal wortels in de
top en dan knopen en bladeren

461
00:18:59,670 --> 00:19:01,440
dat gaat naar beneden en naar buiten.

462
00:19:01,440 --> 00:19:04,450
Veronderstel dan, dat ik
wilt Daven's invoegen

463
00:19:04,450 --> 00:19:06,430
in wat er is momenteel een lege lijst.

464
00:19:06,430 --> 00:19:09,780
Ik ga het volgende doen: ik ben
naar een knooppunt maken in dit gezin

465
00:19:09,780 --> 00:19:15,170
boomachtige datastructuur die eruit ziet
wat dit houdt, die elk

466
00:19:15,170 --> 00:19:19,640
rechthoeken is, laten we zeggen,
nu 26 elementen daarin.

467
00:19:19,640 --> 00:19:21,650
En elk van de cellen
in deze array gaat

468
00:19:21,650 --> 00:19:23,470
naar de letter van een alfabet vertegenwoordigen.

469
00:19:23,470 --> 00:19:28,190
>> Concreet, ik ga behandelen
dit is A, dan B, dan C, dan D,

470
00:19:28,190 --> 00:19:29,310
deze hier.

471
00:19:29,310 --> 00:19:32,940
Dus dit gaat om effectief
vertegenwoordigen de letter D.

472
00:19:32,940 --> 00:19:36,040
Maar om alle Daven's invoegen
noem ik nodig om een ​​beetje meer te doen.

473
00:19:36,040 --> 00:19:37,840
Dus ik ga eerst naar hash, zo te zeggen.

474
00:19:37,840 --> 00:19:41,049
Ik ga kijken naar de eerste letter
in Daven's die uiteraard een D,

475
00:19:41,049 --> 00:19:42,840
en ik ga om te wijzen
een knooppunt dat eruit ziet

476
00:19:42,840 --> 00:19:45,570
als dit-- een grote rechthoek groot
voldoende om het gehele alfabet passen.

477
00:19:45,570 --> 00:19:47,140
>> Nu D gebeurt.

478
00:19:47,140 --> 00:19:49,720
Nu A. D-A-V-E-N is het doel.

479
00:19:49,720 --> 00:19:51,220
Dus nu wat ik ga doen is het volgende.

480
00:19:51,220 --> 00:19:54,027
Zodra ik begon D kennisgeving
er is geen wijzer daar.

481
00:19:54,027 --> 00:19:56,860
Het is vuilnis waarden op het moment,
of ik kan het initialiseren op null.

482
00:19:56,860 --> 00:19:59,630
Maar laat me blijven gaan met
Dit idee van het bouwen van een boom.

483
00:19:59,630 --> 00:20:04,260
Laat me nog een van deze toe te wijzen
knooppunten die 26 elementen in zich heeft.

484
00:20:04,260 --> 00:20:05,150
>> En weet je wat?

485
00:20:05,150 --> 00:20:09,130
Als dit is gewoon een knoop in het geheugen dat
Ik heb met malloc, met behulp van een structuur

486
00:20:09,130 --> 00:20:11,240
als we straks zullen zien,
Ik ga dit-- doen

487
00:20:11,240 --> 00:20:14,450
Ik ga om een ​​pijl te trekken uit
het ding dat D beneden vertegenwoordigd

488
00:20:14,450 --> 00:20:15,860
deze nieuwe knooppunt.

489
00:20:15,860 --> 00:20:19,240
En nu, voor het eerst de volgende
brief in naam Daven's,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- ik ga om verder te gaan
en teken een ander knooppunt als dit,

491
00:20:24,150 --> 00:20:30,150
waarbij de V elementen hier, dat
we trekken voor instance-- whoops.

492
00:20:30,150 --> 00:20:31,020
We zullen niet tekenen daar.

493
00:20:31,020 --> 00:20:31,936
Het zal hier gaan.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> Dan gaan we naar
beschouw dit als V. zijn

496
00:20:35,712 --> 00:20:44,920
En dan naar beneden hier gaan we naar index
neer van V in wat we zullen overwegen E.

497
00:20:44,920 --> 00:20:50,100
En dan van hier gaan we
ga een van deze knooppunten hier.

498
00:20:50,100 --> 00:20:52,930
En nu hebben we een vraag om te beantwoorden.

499
00:20:52,930 --> 00:20:57,840
Ik moet een of andere manier aan te geven dat
we zijn aan het einde van de string Daven.

500
00:20:57,840 --> 00:20:59,490
Dus kon ik gewoon laten null.

501
00:20:59,490 --> 00:21:02,670
>> Maar wat als we hebben Daven's
volledige naam ook, die

502
00:21:02,670 --> 00:21:04,280
is, zoals we hebben gezegd, Davenport?

503
00:21:04,280 --> 00:21:06,970
Dus wat als Daven is
eigenlijk een substring,

504
00:21:06,970 --> 00:21:08,960
een prefix van een veel langere reeks?

505
00:21:08,960 --> 00:21:11,450
We kunnen niet zomaar permanent
zeggen dat er niets gebeurt

506
00:21:11,450 --> 00:21:14,410
om daar heen te gaan, want we konden
steek nooit een woord als Davenport

507
00:21:14,410 --> 00:21:15,840
in deze data Structuur

508
00:21:15,840 --> 00:21:19,560
>> Dus wat we konden doen in plaats daarvan is
behandelen elk van deze elementen

509
00:21:19,560 --> 00:21:22,170
zoals je misschien met twee
elementen binnen hen.

510
00:21:22,170 --> 00:21:24,810
Eén is een pointer inderdaad
zoals ik heb gedaan.

511
00:21:24,810 --> 00:21:27,100
Zodat elk van deze dozen
niet één cel.

512
00:21:27,100 --> 00:21:29,855
Maar wat als de top
een-- de onderste's

513
00:21:29,855 --> 00:21:32,230
gaan null zijn, omdat
er is geen Davenport gewoon nog niet.

514
00:21:32,230 --> 00:21:34,197
Wat als de bovenste
is een aantal speciale waarde?

515
00:21:34,197 --> 00:21:36,530
En het gaat een beetje te zijn
moeilijk om het deze grootte te tekenen.

516
00:21:36,530 --> 00:21:38,130
Maar stel dat het is gewoon een vinkje.

517
00:21:38,130 --> 00:21:38,920
Controleren.

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N is een string
in deze datastructuur.

519
00:21:44,230 --> 00:21:48,350
>> Ondertussen, als ik meer ruimte
hier, kon ik doen P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
en ik kon check in de knoop leggen
dat heeft de letter T op het einde.

521
00:21:52,650 --> 00:21:55,460
Dus dit is een massively
complex kijkt datastructuur.

522
00:21:55,460 --> 00:21:57,210
En mijn handschrift
zeker niet helpen.

523
00:21:57,210 --> 00:22:00,043
Maar als ik iets wilde voegen
anders, nadenken over wat we zouden doen.

524
00:22:00,043 --> 00:22:03,370
Als we wilden David in te zetten,
we dezelfde logica, D-A-V zou volgen,

525
00:22:03,370 --> 00:22:08,802
maar nu ik zou wijzen in de komende
element niet uit E, maar van I tot D.

526
00:22:08,802 --> 00:22:10,760
Dus er gaat worden
meer knooppunten in deze boom.

527
00:22:10,760 --> 00:22:12,325
We gaan bellen malloc meer hebben.

528
00:22:12,325 --> 00:22:14,700
Maar ik wil niet een te maken
grote puinhoop van deze foto.

529
00:22:14,700 --> 00:22:17,710
Dus laten we in plaats daarvan kijken naar een
dat is al-pre geformuleerd

530
00:22:17,710 --> 00:22:21,810
als dit met niet dot, dot,
stippen, maar gewoon afgekort arrays.

531
00:22:21,810 --> 00:22:23,950
Maar elk van de knooppunten
in deze boom hier

532
00:22:23,950 --> 00:22:26,700
vertegenwoordigt dezelfde thing--
een array Ray van grootte 26.

533
00:22:26,700 --> 00:22:28,860
>> Of als we willen zijn
nu echt een goede, wat

534
00:22:28,860 --> 00:22:30,790
Als iemands naam als
een apostrof, laten we

535
00:22:30,790 --> 00:22:35,560
aannemen dat ieder knooppunt eigenlijk
zoals 27 indexen in het, niet alleen 26.

536
00:22:35,560 --> 00:22:42,020
Dus dit nu gaat om een ​​data zijn
genaamd een trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
Een trie, die zogenaamd
historisch gezien een slimme naam voor een boom

538
00:22:46,120 --> 00:22:49,040
die is geoptimaliseerd voor
ophalen, die natuurlijk

539
00:22:49,040 --> 00:22:50,870
wordt gespeld met een I-E dus het is trie.

540
00:22:50,870 --> 00:22:52,710
Maar dat is de geschiedenis van de trie.

541
00:22:52,710 --> 00:22:55,860
>> Dus een trie is deze boom-achtige data
structuur als een stamboom

542
00:22:55,860 --> 00:22:57,510
die uiteindelijk gedraagt ​​als dat.

543
00:22:57,510 --> 00:23:00,890
En hier is weer een voorbeeld van een
hele hoop namen van andere mensen.

544
00:23:00,890 --> 00:23:03,540
Maar de vraag is nu
bij de hand is wat hebben

545
00:23:03,540 --> 00:23:08,070
we hebben opgedaan door de invoering van misschien wel een meer
complexe datastructuur, en één,

546
00:23:08,070 --> 00:23:09,870
eerlijk gezegd, dat gebruikt veel geheugen.

547
00:23:09,870 --> 00:23:11,703
>> Want ook al,
op het moment, ik ben alleen

548
00:23:11,703 --> 00:23:15,050
met behulp van D's pointer en
A en V en Es en Ns,

549
00:23:15,050 --> 00:23:16,700
Ik verspil een deurklink van veel geheugen.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
Maar waar ik doorbrengen één bron,
Ik heb de neiging om te doen terug te krijgen een ander.

552
00:23:22,660 --> 00:23:26,020
Dus als ik de uitgaven meer ruimte,
wat is waarschijnlijk de hoop?

553
00:23:26,020 --> 00:23:27,407
Dat ik minder uitgeven wat?

554
00:23:27,407 --> 00:23:28,240
Publiek: Minder tijd.

555
00:23:28,240 --> 00:23:28,990
DAVID MALAN: Tijd.

556
00:23:28,990 --> 00:23:30,320
Waarom zou dat zijn?

557
00:23:30,320 --> 00:23:33,880
Nou, wat is het inbrengen
tijd qua grote O nu,

558
00:23:33,880 --> 00:23:37,660
van een naam als Daven
of Davenport of David?

559
00:23:37,660 --> 00:23:39,340
Nou, Daven was vijf stappen.

560
00:23:39,340 --> 00:23:42,350
Davenport zou zijn negen stappen,
dus het zou een paar stappen.

561
00:23:42,350 --> 00:23:44,250
David zou vijf stappen ook.

562
00:23:44,250 --> 00:23:47,230
Dus dat zijn betonnen
aantallen, maar zeker is er

563
00:23:47,230 --> 00:23:49,550
een bovengrens voor de
lengte van iemands naam.

564
00:23:49,550 --> 00:23:52,240
En inderdaad, in het probleem
sets van vijf specificatie

565
00:23:52,240 --> 00:23:54,050
we gaan voorstellen
dat het iets

566
00:23:54,050 --> 00:23:55,470
dat is 40-sommige-oneven tekens.

567
00:23:55,470 --> 00:23:58,180
>> Realistisch, niemand heeft
een oneindig lange naam,

568
00:23:58,180 --> 00:24:01,542
dat wil zeggen dat de lengte van een
de naam of de lengte van een string kunnen we

569
00:24:01,542 --> 00:24:03,750
bepaalde de stand van
structuur is misschien wel wat?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
Het is constant.

572
00:24:06,250 --> 00:24:06,430
Right?

573
00:24:06,430 --> 00:24:09,310
Het is misschien een grote constante zoals zijn
40 iets, maar is constant.

574
00:24:09,310 --> 00:24:13,752
En het heeft geen afhankelijkheid hoeveel
andere namen zijn in deze datastructuur.

575
00:24:13,752 --> 00:24:15,460
Met andere woorden, als I
wilde nu voegen

576
00:24:15,460 --> 00:24:20,540
Colton of Gabriel of Rob of Zamyla of
Alison of Belinda of enige andere namen

577
00:24:20,540 --> 00:24:23,940
van het personeel op deze data
structuur, is de looptijd

578
00:24:23,940 --> 00:24:26,750
van het invoegen van andere namen
zal zijn op alle beïnvloed

579
00:24:26,750 --> 00:24:30,220
door hoeveel andere elementen
in de datastructuur al?

580
00:24:30,220 --> 00:24:31,040
Het is niet.

581
00:24:31,040 --> 00:24:31,540
Right?

582
00:24:31,540 --> 00:24:36,150
Omdat we effectief gebruik
Deze meerlagige hash tabel.

583
00:24:36,150 --> 00:24:38,280
En de looptijd van
een van deze bewerkingen

584
00:24:38,280 --> 00:24:41,510
is niet afhankelijk van het aantal
elementen die in de datastructuur

585
00:24:41,510 --> 00:24:43,090
of die uiteindelijk gaan
om in de gegevensstructuur,

586
00:24:43,090 --> 00:24:44,714
maar de lengte van wat specifiek?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> De snaar
ingevoegd, die maakt

589
00:24:49,200 --> 00:24:52,580
deze asymptotisch constante
tijd-- big O van één.

590
00:24:52,580 --> 00:24:54,720
En eerlijk gezegd, gewoon in
de echte wereld, dit

591
00:24:54,720 --> 00:24:58,380
betekent het invoegen naam Daven's neemt
als vijf stappen, of Davenport negen

592
00:24:58,380 --> 00:25:00,100
stappen, of David vijf stappen.

593
00:25:00,100 --> 00:25:03,071
Dat is pretty darn kleine looptijden.

594
00:25:03,071 --> 00:25:05,320
En, inderdaad, dat is een zeer
goede zaak, vooral wanneer

595
00:25:05,320 --> 00:25:08,126
Het is niet afhankelijk van de totale
aantal elementen in daar.

596
00:25:08,126 --> 00:25:10,500
Dus hoe kunnen we dit implementeren
soort structuur in de code?

597
00:25:10,500 --> 00:25:12,900
Het is een beetje meer
complex, maar toch is het

598
00:25:12,900 --> 00:25:15,050
gewoon een toepassing van
elementaire bouwstenen.

599
00:25:15,050 --> 00:25:17,830
Ik ga om te herdefiniëren
Knoop van de VS als volgt:

600
00:25:17,830 --> 00:25:21,100
bool genaamd word-- en dit
alles onder de noemer.

601
00:25:21,100 --> 00:25:23,970
Maar de bool vertegenwoordigt
wat ik tekende als een vinkje.

602
00:25:23,970 --> 00:25:24,490
Ja.

603
00:25:24,490 --> 00:25:26,720
Dit is het einde van een string
in deze datastructuur.

604
00:25:26,720 --> 00:25:30,702
>> En, natuurlijk, het knooppunt ster
Er wordt verwezen naar kinderen.

605
00:25:30,702 --> 00:25:32,410
En, inderdaad, net als
een stamboom, je

606
00:25:32,410 --> 00:25:34,370
zou overwegen de knooppunten
die zijn opknoping uit

607
00:25:34,370 --> 00:25:36,920
van onder sommige ouder
element zijn kinderen.

608
00:25:36,920 --> 00:25:40,510
En zodat de kinderen gaat
zijn een reeks van 27, 27 één

609
00:25:40,510 --> 00:25:41,680
gewoon voor de apostrof.

610
00:25:41,680 --> 00:25:43,390
We gaan om te sorteren
Een bijzonder geval van dat.

611
00:25:43,390 --> 00:25:45,400
Dus u kunt er zeker van zijn
namen met apostrof.

612
00:25:45,400 --> 00:25:47,399
Misschien zelfs koppelteken moet
naar binnen gaan, maar je zult

613
00:25:47,399 --> 00:25:50,330
zien in p set 5 we alleen zorg
over brieven en apostrof.

614
00:25:50,330 --> 00:25:52,990
>> En hoe doe je vertegenwoordigen
de datastructuur zelf?

615
00:25:52,990 --> 00:25:56,454
Hoe maak je de wortel vertegenwoordigen
van deze trie, om zo te zeggen?

616
00:25:56,454 --> 00:25:59,620
Nou, net als met een gelinkte lijst, u
moet een pointer naar het eerste element.

617
00:25:59,620 --> 00:26:04,270
Met een trie je hoeft alleen maar een
Pointer naar de wortel van deze trie.

618
00:26:04,270 --> 00:26:07,290
En vanaf daar kun je hash
je weg naar beneden dieper en dieper

619
00:26:07,290 --> 00:26:10,460
met elk ander knooppunt in de structuur.

620
00:26:10,460 --> 00:26:13,440
Dus gewoon met dit blikje
wij vertegenwoordigen dat struct.

621
00:26:13,440 --> 00:26:15,877
>> Meanwhile-- nu Oh, vraag.

622
00:26:15,877 --> 00:26:17,220
>> Publiek: Wat is bool woord?

623
00:26:17,220 --> 00:26:20,490
>> DAVID MALAN: Bool woord is
alleen deze C incarnatie

624
00:26:20,490 --> 00:26:22,920
van wat ik beschreef
in deze doos hier, wanneer

625
00:26:22,920 --> 00:26:26,000
Ik begon het splitsen van elk van de
elementen array in twee stukken.

626
00:26:26,000 --> 00:26:27,600
Eén is een pointer naar de volgende knoop.

627
00:26:27,600 --> 00:26:30,280
De andere moet worden
iets als een selectievakje

628
00:26:30,280 --> 00:26:33,770
om ja te zeggen, er is een
woord Daven dat hier eindigt,

629
00:26:33,770 --> 00:26:35,610
omdat we niet willen,
op het moment, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Hoewel Dave gaat om een ​​te zijn
legitiem woord, hij is niet in de trie

631
00:26:39,320 --> 00:26:39,830
Nog.

632
00:26:39,830 --> 00:26:40,950
En D is niet een woord.

633
00:26:40,950 --> 00:26:42,770
En D-A is niet een woord of een naam.

634
00:26:42,770 --> 00:26:45,020
Dus het vinkje
geeft alleen aan als je eenmaal

635
00:26:45,020 --> 00:26:48,190
raakte dit knooppunt is het
vorige pad karakters

636
00:26:48,190 --> 00:26:50,700
eigenlijk een string die je hebt ingevoegd.

637
00:26:50,700 --> 00:26:53,660
Dus dat is al de bool
er voor ons doet.

638
00:26:53,660 --> 00:26:55,500
>> Alle andere vragen over pogingen?

639
00:26:55,500 --> 00:26:56,215
Yeah.

640
00:26:56,215 --> 00:26:58,035
>> Publiek: Wat is de overlap?

641
00:26:58,035 --> 00:26:59,945
Wat als je een Dave en een Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID MALAN: Perfect.

643
00:27:00,820 --> 00:27:02,580
Wat als je een Dave en een Daven?

644
00:27:02,580 --> 00:27:06,240
Dus als we in te voegen, bijvoorbeeld een bijnaam,
voor David-- Dave-- D-A-V-E?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
Dit is eigenlijk super simpel.

647
00:27:08,700 --> 00:27:10,325
Dus we alleen gaan om vier stappen te ondernemen.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. En wat moet ik
doen zodra ik raakte dat vierde knooppunt?

650
00:27:15,847 --> 00:27:16,680
Gewoon gaan controleren.

651
00:27:16,680 --> 00:27:18,000
We zijn al goed om te gaan.

652
00:27:18,000 --> 00:27:18,840
Gedaan.

653
00:27:18,840 --> 00:27:19,750
Vier stappen.

654
00:27:19,750 --> 00:27:21,590
Constante tijd asymptotisch.

655
00:27:21,590 --> 00:27:26,300
En nu hebben we aangegeven dat zowel Dave
en Daven zijn strings in de structuur.

656
00:27:26,300 --> 00:27:27,710
Dus geen probleem.

657
00:27:27,710 --> 00:27:30,200
En merk op hoe de aanwezigheid
van Daven heeft het niet gehaald

658
00:27:30,200 --> 00:27:34,750
neem geen tijd meer of minder
tijd voor Dave en vice versa.

659
00:27:34,750 --> 00:27:36,000
>> Dus wat kunnen we nu doen?

660
00:27:36,000 --> 00:27:40,680
We hebben deze metafoor gebruikt voor
trays vertegenwoordigen iets.

661
00:27:40,680 --> 00:27:43,380
Maar het blijkt dat een
stapel trays eigenlijk

662
00:27:43,380 --> 00:27:47,187
demonstratieve van een andere abstracte gegevens
type-- een hoger niveau datastructuur

663
00:27:47,187 --> 00:27:49,770
dat aan het eind van de dag is gewoon
als een array of een gelinkte lijst

664
00:27:49,770 --> 00:27:50,970
of iets meer alledaagse.

665
00:27:50,970 --> 00:27:53,270
Maar het is een interessantere
conceptuele concept.

666
00:27:53,270 --> 00:27:56,440
Een stapel, zoals deze
trays hier in Mather,

667
00:27:56,440 --> 00:27:58,750
algemeen genoemd
gewoon dat-- een stapel.

668
00:27:58,750 --> 00:28:02,540
>> En dergelijke datastructuur
je hebt twee operations--

669
00:28:02,540 --> 00:28:05,880
heb je een zogenaamde push voor
iets toe te voegen aan de stapel,

670
00:28:05,880 --> 00:28:08,320
als het zetten van een andere lade
rug op de top van de stack.

671
00:28:08,320 --> 00:28:11,350
En dan pop, wat betekent dat u
neem de bovenste lade uit.

672
00:28:11,350 --> 00:28:16,210
Maar wat is belangrijk over een stack is dat
het heeft deze merkwaardige eigenschap.

673
00:28:16,210 --> 00:28:19,560
Zoals de eetzaal personeel zijn
herschikken van de laden voor de volgende maaltijd,

674
00:28:19,560 --> 00:28:21,380
wat gaat worden
waar over hoe studenten

675
00:28:21,380 --> 00:28:22,856
interageren met deze datastructuur?

676
00:28:22,856 --> 00:28:24,480
Publiek: Ze gaan eenmalige pop.

677
00:28:24,480 --> 00:28:26,550
DAVID MALAN: Ze gaan
pop one off, hopelijk de top.

678
00:28:26,550 --> 00:28:28,910
Anders is het gewoon een soort van domme
om helemaal naar de bodem.

679
00:28:28,910 --> 00:28:29,070
Right?

680
00:28:29,070 --> 00:28:31,620
De datastructuur niet echt toe
u naar de onderste lade tenminste grijpen

681
00:28:31,620 --> 00:28:32,520
gemakkelijk.

682
00:28:32,520 --> 00:28:35,040
Dus er is deze merkwaardige
woning naar een stack

683
00:28:35,040 --> 00:28:39,730
dat het laatste item in is
naar de eerste uit zijn.

684
00:28:39,730 --> 00:28:43,400
En computer wetenschappers noemen
Dit LIFO-- last in, first out.

685
00:28:43,400 --> 00:28:45,540
En het eigenlijk heeft
interessante toepassingen.

686
00:28:45,540 --> 00:28:50,090
Het is niet per se zo vanzelfsprekend als een aantal
anderen, maar het kan inderdaad nuttig,

687
00:28:50,090 --> 00:28:54,040
en kan inderdaad worden toegepast
in een paar verschillende manieren.

688
00:28:54,040 --> 00:28:58,550
>> Zo één, en eigenlijk, laat
me niet om te duiken in die.

689
00:28:58,550 --> 00:28:59,860
Laten we dit doen in plaats daarvan.

690
00:28:59,860 --> 00:29:03,700
Laten we eens kijken naar een die is bijna de
Hetzelfde idee, maar het is een beetje eerlijker.

691
00:29:03,700 --> 00:29:04,200
Right?

692
00:29:04,200 --> 00:29:07,560
Als je een van deze fan jongens of
meisjes die echt leuk vindt Apple producten

693
00:29:07,560 --> 00:29:10,130
en je werd wakker om 3:00
aan line-up op een bepaald winkel

694
00:29:10,130 --> 00:29:14,150
aan de allernieuwste iPhone te krijgen, je
zou kunnen hebben in de wachtrij als deze.

695
00:29:14,150 --> 00:29:15,800
>> Nu een wachtrij is heel bewust vernoemd.

696
00:29:15,800 --> 00:29:18,190
Het is een lijn, want er is
sommige eerlijkheid aan.

697
00:29:18,190 --> 00:29:18,690
Right?

698
00:29:18,690 --> 00:29:21,690
Het zou soort gezogen als je hebt
eerst daar aankwam bij de Apple Store

699
00:29:21,690 --> 00:29:25,700
maar je bent in feite de onderste
lade omdat de Apple-medewerkers dan

700
00:29:25,700 --> 00:29:28,189
pop de laatste persoon die
eigenlijk kreeg in de rij.

701
00:29:28,189 --> 00:29:31,230
Dus stapels en rijen, hoewel
functioneel ze zijn soort van de same--

702
00:29:31,230 --> 00:29:33,105
het is gewoon deze collectie
van de middelen die

703
00:29:33,105 --> 00:29:36,210
gaan groeien en shrink-- er is
Deze eerlijkheid aspect aan,

704
00:29:36,210 --> 00:29:39,634
althans in de echte wereld,
waar de handelingen die u uit te oefenen

705
00:29:39,634 --> 00:29:40,800
zijn fundamenteel verschillend.

706
00:29:40,800 --> 00:29:43,360
Een stack-- een wachtrij
rather-- wordt gezegd dat

707
00:29:43,360 --> 00:29:45,320
twee operaties: n rij en d wachtrij.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
Of je kunt ze bellen
een aantal dingen.

710
00:29:48,090 --> 00:29:50,770
Maar je wilt vastleggen
het idee dat men toevoegt

711
00:29:50,770 --> 00:29:53,230
en een uiteindelijk trekken.

712
00:29:53,230 --> 00:29:58,840
>> Nu onder de kap zowel de stack
en een wachtrij kunnen worden uitgevoerd hoe?

713
00:29:58,840 --> 00:30:01,390
We zullen niet in de code van gaan
omdat de hogere

714
00:30:01,390 --> 00:30:03,387
idee is een soort van meer voor de hand.

715
00:30:03,387 --> 00:30:04,470
Ik bedoel, wat doen mensen dat doen?

716
00:30:04,470 --> 00:30:07,030
Als ik de eerste persoon op de Apple
Slaan en dit is de voordeur,

717
00:30:07,030 --> 00:30:08,130
weet je, ik ga hier staan.

718
00:30:08,130 --> 00:30:09,750
En de volgende persoon
gaan om hier te staan.

719
00:30:09,750 --> 00:30:11,500
En de volgende persoon
gaan om hier te staan.

720
00:30:11,500 --> 00:30:13,792
Wat datastructuur
leent zich voor een wachtrij?

721
00:30:13,792 --> 00:30:14,542
>> Publiek: Een wachtrij.

722
00:30:14,542 --> 00:30:15,667
DAVID MALAN: Nou, een wachtrij.

723
00:30:15,667 --> 00:30:16,390
Tuurlijk.

724
00:30:16,390 --> 00:30:16,920
Wat anders?

725
00:30:16,920 --> 00:30:17,600
>> Publiek: Een gelinkte lijst.

726
00:30:17,600 --> 00:30:18,990
>> DAVID MALAN: Een gekoppeld
lijst kon implementeren.

727
00:30:18,990 --> 00:30:22,500
En een gelinkte lijst is leuk want dan
kan willekeurig lang worden tegenstelling

728
00:30:22,500 --> 00:30:24,880
om met een aantal vast aantal
van de mensen in de winkel.

729
00:30:24,880 --> 00:30:27,030
Maar misschien een vast aantal
plaatsen is legitiem.

730
00:30:27,030 --> 00:30:30,350
Want als ze alleen als 20
iPhones op de eerste dag, misschien

731
00:30:30,350 --> 00:30:33,930
ze alleen een array van grootte nodig hebt
20 die wachtrij vertegenwoordigen die

732
00:30:33,930 --> 00:30:37,070
is alleen nu te zeggen als we eenmaal beginnen te praten
over deze hogere problemen niveau,

733
00:30:37,070 --> 00:30:38,890
je kunt het implementeren
in een aantal manieren.

734
00:30:38,890 --> 00:30:42,030
En er is waarschijnlijk gewoon gaan
zijn een afweging in ruimte en tijd

735
00:30:42,030 --> 00:30:43,950
of gewoon in uw eigen code complexiteit.

736
00:30:43,950 --> 00:30:45,380
>> Hoe zit het met een stapel?

737
00:30:45,380 --> 00:30:48,190
Nou, een stapel, we hebben ook gezien
kon gewoon zijn deze trays.

738
00:30:48,190 --> 00:30:50,007
En je kon dit een array uit te voeren.

739
00:30:50,007 --> 00:30:53,090
Maar op een gegeven moment als je een array,
wat er gaat gebeuren met de trays

740
00:30:53,090 --> 00:30:54,173
je probeert neer te zetten?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
Prima.

743
00:30:55,670 --> 00:30:57,490
Je bent alleen gaat
zijn om zo hoog te gaan.

744
00:30:57,490 --> 00:31:00,156
En ik denk dat in Mather ze
eigenlijk verzonken in die opening.

745
00:31:00,156 --> 00:31:01,950
Dus inderdaad, het is bijna
zoals Mather wordt met behulp van

746
00:31:01,950 --> 00:31:03,783
een array van vaste grootte,
want je kunt alleen

747
00:31:03,783 --> 00:31:08,302
past zo veel laden in die opening in
de muur beneden de knieën van de mensen.

748
00:31:08,302 --> 00:31:10,010
En dus dat zou kunnen zijn
gezegd dat een array,

749
00:31:10,010 --> 00:31:14,300
maar we konden zeker implementeren dat
meer in het algemeen met een gekoppelde lijst.

750
00:31:14,300 --> 00:31:16,390
>> Nou, wat te denken van een andere datastructuur?

751
00:31:16,390 --> 00:31:18,760
Laat me omhoog te trekken een andere visuele hier.

752
00:31:18,760 --> 00:31:24,710
Zoiets als hoe dacht je van deze hier?

753
00:31:24,710 --> 00:31:28,920
Waarom zou het nuttig zijn om niet over
iets zo luxe als een trie, die

754
00:31:28,920 --> 00:31:32,370
we zagen hadden deze zeer breed knooppunten,
die elk in een array?

755
00:31:32,370 --> 00:31:35,740
Maar wat als we iets meer te doen
gewoon, net als een oude school stamboom,

756
00:31:35,740 --> 00:31:38,110
elk van wie de knooppunten hier
wordt gewoon het opslaan van een nummer.

757
00:31:38,110 --> 00:31:42,180
In plaats van een naam of een afstammeling
wordt gewoon het opslaan van een nummer als dit.

758
00:31:42,180 --> 00:31:45,250
>> Nou, het jargon gebruiken we in
datastructuren is zowel pogingen

759
00:31:45,250 --> 00:31:49,510
en bomen, waarbij een trie, opnieuw, is
slechts één waarvan de knopen zijn arrays,

760
00:31:49,510 --> 00:31:51,680
is nog steeds wat je misschien
Gebruik van de lagere school

761
00:31:51,680 --> 00:31:53,860
wanneer je een gezin gemaakt
tree-- bladeren en de wortel

762
00:31:53,860 --> 00:31:57,250
van de boom en de kinderen van de
ouders en broers en zussen daarvan.

763
00:31:57,250 --> 00:32:03,670
En we zouden een boom te implementeren,
bijvoorbeeld Zo eenvoudig.

764
00:32:03,670 --> 00:32:07,420
Een boom, als het als een knoop, een van
deze cirkels een getal,

765
00:32:07,420 --> 00:32:09,947
het gaat niet om te hebben
één wijzer, maar twee.

766
00:32:09,947 --> 00:32:11,780
En zodra je toevoegen
een tweede wijzer, u

767
00:32:11,780 --> 00:32:13,905
kan eigenlijk nu maken soort
tweedimensionale data

768
00:32:13,905 --> 00:32:14,780
structuren in het geheugen.

769
00:32:14,780 --> 00:32:16,660
Net als een tweedimensionale
array, kunt u

770
00:32:16,660 --> 00:32:18,904
hebben dergelijke tweedimensionale
gelinkte lijsten, maar degenen

771
00:32:18,904 --> 00:32:20,820
die volgen een patroon
waar er geen cycli.

772
00:32:20,820 --> 00:32:24,487
Het is echt een boom met een
grootouder weg hier en dan omhoog

773
00:32:24,487 --> 00:32:27,320
sommige ouders en kinderen en
kleinkinderen en achterkleinkinderen.

774
00:32:27,320 --> 00:32:28,370
enzovoort.

775
00:32:28,370 --> 00:32:32,390
>> Maar wat echt netjes over dit ook,
alleen maar om je te plagen met een stukje code,

776
00:32:32,390 --> 00:32:35,370
recall recursie uit
een tijdje terug, waarbij

777
00:32:35,370 --> 00:32:38,220
u een functie die zichzelf aanroept schrijven.

778
00:32:38,220 --> 00:32:41,140
Dit is een mooie kans
iets implementeren

779
00:32:41,140 --> 00:32:42,920
zoals recursie, omdat dit te overwegen.

780
00:32:42,920 --> 00:32:43,860
>> Dit is een boom.

781
00:32:43,860 --> 00:32:48,040
En ik heb een beetje anale met hoe geweest
Ik zette de gehele getallen in de straat.

782
00:32:48,040 --> 00:32:51,020
Zozeer zelfs dat het een speciale
name-- een binaire zoekboom.

783
00:32:51,020 --> 00:32:53,460
Nu hebben we gehoord van binaire
zoeken, maar kan je

784
00:32:53,460 --> 00:32:55,180
terug te werken uit naam van dit ding?

785
00:32:55,180 --> 00:32:59,280
Wat is het patroon van hoe ik
ingestoken de gehele getallen in deze boom?

786
00:32:59,280 --> 00:33:00,696
Het is niet willekeurig.

787
00:33:00,696 --> 00:33:01,570
Er is een bepaald patroon.

788
00:33:01,570 --> 00:33:02,090
Yeah.

789
00:33:02,090 --> 00:33:03,370
>> Publiek: kleinere aan de linkerkant.

790
00:33:03,370 --> 00:33:03,690
>> DAVID MALAN: Yeah.

791
00:33:03,690 --> 00:33:05,062
Kleinere zijn aan de linkerkant.

792
00:33:05,062 --> 00:33:06,270
Grotere zijn aan de rechterkant.

793
00:33:06,270 --> 00:33:12,940
Zodanig dat een ware uitspraak is een
ouder groter is dan zijn linkerkind,

794
00:33:12,940 --> 00:33:14,850
maar minder dan haar recht kind.

795
00:33:14,850 --> 00:33:17,750
En dat alleen is zelfs een
recursieve verbale definitie

796
00:33:17,750 --> 00:33:20,500
want je kunt toepassen dat
Dezelfde logica elk knooppunt

797
00:33:20,500 --> 00:33:23,080
en alleen bodems
out, een base case als je

798
00:33:23,080 --> 00:33:25,740
zal, wanneer u een van hit
de bladeren, zogezegd,

799
00:33:25,740 --> 00:33:28,580
waar een verlof heeft geen kinderen meer.

800
00:33:28,580 --> 00:33:30,614
>> Nu hoe zou u het nummer 44 vinden?

801
00:33:30,614 --> 00:33:32,280
Je zou beginnen bij de wortel en zeggen, hm.

802
00:33:32,280 --> 00:33:35,690
55 is geen 44 Dus wil ik gaan
rechts of wil ik om links te gaan?

803
00:33:35,690 --> 00:33:37,190
Nou, natuurlijk wilt u links gaan.

804
00:33:37,190 --> 00:33:40,060
En dus is het net als de telefoon
boek bijvoorbeeld in binaire zoekopdracht

805
00:33:40,060 --> 00:33:41,099
meer algemeen.

806
00:33:41,099 --> 00:33:43,390
Maar we zijn de uitvoering ervan
nu een beetje meer dynamisch

807
00:33:43,390 --> 00:33:45,339
dan een serie zou kunnen stellen.

808
00:33:45,339 --> 00:33:48,130
En in feite, als je wilt kijken
bij de code, op het eerste gezicht zeker.

809
00:33:48,130 --> 00:33:49,671
Het ziet eruit als een hele hoop van lijnen.

810
00:33:49,671 --> 00:33:51,220
Maar het is heel eenvoudig.

811
00:33:51,220 --> 00:33:54,490
Als u een functie wilt implementeren
riep zoeken waarvan het doel in het leven

812
00:33:54,490 --> 00:33:57,290
is het zoeken naar een waarde
als n een geheel getal,

813
00:33:57,290 --> 00:34:01,756
en je bent geslaagd in een één pointer--
een pointer naar het knooppunt van de wortels,

814
00:34:01,756 --> 00:34:04,380
veeleer van die boom waarvan
kun je al het andere toegang,

815
00:34:04,380 --> 00:34:08,850
merken hoe onomwonden
kunt u de logica te implementeren.

816
00:34:08,850 --> 00:34:10,880
Als boom is null,
uiteraard is het er niet.

817
00:34:10,880 --> 00:34:11,880
Laten we gewoon return false.

818
00:34:11,880 --> 00:34:12,000
Right?

819
00:34:12,000 --> 00:34:14,040
Als je hand het niets,
er is niets daar.

820
00:34:14,040 --> 00:34:17,900
>> Anders, indien n kleiner dan
boom pijl N-- nu arrow n,

821
00:34:17,900 --> 00:34:20,670
herinneren we super geïntroduceerd
kort op de andere dag,

822
00:34:20,670 --> 00:34:25,100
en dat betekent gewoon de-verwijzing de
pointer en kijk naar het veld met de naam n.

823
00:34:25,100 --> 00:34:27,690
Het betekent dus ga daar en
kijk naar het veld met de naam n.

824
00:34:27,690 --> 00:34:33,810
Dus als n, de waarde die u hebt opgegeven, is minder
dan de waarde in de bomen integer,

825
00:34:33,810 --> 00:34:35,449
waar wil je heen?

826
00:34:35,449 --> 00:34:36,389
Naar links.

827
00:34:36,389 --> 00:34:37,780
>> Dus let op de recursie.

828
00:34:37,780 --> 00:34:39,860
Ik ben returning-- niet waar.

829
00:34:39,860 --> 00:34:40,989
Niet vals.

830
00:34:40,989 --> 00:34:45,670
Ik ben terug, ongeacht het antwoord
is van een oproep bij mezelf, het passeren

831
00:34:45,670 --> 00:34:50,100
weer een n, die overbodig
maar wat is er nu iets anders?

832
00:34:50,100 --> 00:34:51,989
Hoe maak ik het probleem kleiner?

833
00:34:51,989 --> 00:34:54,920
Ik ben het passeren in de tweede
argument, niet de wortel van de boom,

834
00:34:54,920 --> 00:34:59,616
maar de linkerkind in dit geval.

835
00:34:59,616 --> 00:35:00,990
Dus ik ben het passeren in de linker kind.

836
00:35:00,990 --> 00:35:04,720
>> Ondertussen, als n groter is dan
de knoop Ik ben momenteel op zoek naar,

837
00:35:04,720 --> 00:35:06,690
Ik zoek de rechterkant.

838
00:35:06,690 --> 00:35:10,880
Anders, als de structuur niet nul, en
Als het element niet naar links

839
00:35:10,880 --> 00:35:13,240
en het is niet aan de rechter,
wat is er heerlijk het geval?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
We hebben eigenlijk vond het knooppunt in
vraag, en dus hebben we return true.

842
00:35:18,440 --> 00:35:21,490
>> Dus we hebben net gekrast de oppervlakte
nu een aantal van deze datastructuren.

843
00:35:21,490 --> 00:35:24,370
In set probleem vijf u zult
staand deze nog verder,

844
00:35:24,370 --> 00:35:27,250
en u zult gegeven worden uw ontwerp
keuze van hoe om te gaan over dit.

845
00:35:27,250 --> 00:35:30,250
Wat ik zou willen besluiten op
is slechts een 30 seconden teaser

846
00:35:30,250 --> 00:35:32,080
van wat wacht volgende week en verder.

847
00:35:32,080 --> 00:35:35,390
>> Zoals we begin-- gelukkig je misschien
langzaam think-- onze overgang

848
00:35:35,390 --> 00:35:38,680
uit de wereld van C en lager
level implementatie details,

849
00:35:38,680 --> 00:35:42,090
aan een wereld waarin we kunnen nemen voor
vanzelfsprekend dat iemand anders heeft eindelijk

850
00:35:42,090 --> 00:35:44,010
geïmplementeerd deze data
structuren voor ons,

851
00:35:44,010 --> 00:35:47,570
en we beginnen om het te begrijpen
echte wereld betekent de uitvoering

852
00:35:47,570 --> 00:35:50,560
web-based programma's en
websites algemeen

853
00:35:50,560 --> 00:35:52,910
en ook het security
implicaties die we hebben alleen

854
00:35:52,910 --> 00:35:54,850
begonnen om krassen op het oppervlak van.

855
00:35:54,850 --> 00:35:57,320
Hier is wat ons te wachten staat
in de dagen die komen.

856
00:35:57,320 --> 00:36:00,480
>> [VIDEO AFSPELEN]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -Hij Kwam met een boodschap,
met een protocol al zijn eigen.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Hij kwam tot een wereld van wrede
firewalls, onverschillig routers,

861
00:36:30,894 --> 00:36:33,368
en gevaren veel erger dan de dood.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Hij is snel.

864
00:36:36,236 --> 00:36:37,980
Hij is sterk.

865
00:36:37,980 --> 00:36:42,830
Hij is TCP / IP, en hij heeft je adres.

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 AFSPELEN]

869
00:36:49,660 --> 00:36:50,910
DAVID MALAN: Coming volgende week.

870
00:36:50,910 --> 00:36:51,880
Wij zullen u dan zien.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[VIDEO AFSPELEN]

873
00:36:56,060 --> 00:36:59,240
-En Nu, "Deep Thoughts"
door Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Begint altijd
lezingen met: "Goed."

876
00:37:05,820 --> 00:37:08,750
Waarom niet, "Hier is de oplossing
om deze week probleem set "

877
00:37:08,750 --> 00:37:12,180
of "We geven jullie allemaal een A?"

878
00:37:12,180 --> 00:37:13,380
[Lacht]

879
00:37:13,380 --> 00:37:15,530
[END VIDEO AFSPELEN]