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

2
00:00:00,500 --> 00:00:03,340
[Muusika mängimine]

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

4
00:00:11,020 --> 00:00:14,010
>> DAVID Humala: See on CS50.

5
00:00:14,010 --> 00:00:18,090
Ja see on nii algus ja
väljatöötamiseni nagu literally-- peaaegu lõpuni

6
00:00:18,090 --> 00:00:18,825
nädala kuus.

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

8
00:00:20,030 --> 00:00:22,640
>> Ma mõtlesin, et ma jagan
natuke lõbus fakt.

9
00:00:22,640 --> 00:00:25,370
Olen tõmmatakse see üles
Viimase semestri andmekogum.

10
00:00:25,370 --> 00:00:29,710
Sul võib meelde tuletada, et me palume teil iga
p set vormi, kui olete võrgus vaadatud

11
00:00:29,710 --> 00:00:31,580
või kui olete käinud isiklikult.

12
00:00:31,580 --> 00:00:33,020
Ja siin on andmed.

13
00:00:33,020 --> 00:00:34,710
Nii et täna oli väga etteaimatav.

14
00:00:34,710 --> 00:00:37,126
Aga me tahtsime kulutada natuke
aega teiega siiski.

15
00:00:37,126 --> 00:00:40,599
Kas keegi tahaks hüpotees miks see
graafik on nii sakiline, üles alla, üles alla,

16
00:00:40,599 --> 00:00:41,265
nii järjekindlalt?

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

18
00:00:42,980 --> 00:00:45,130
Mida iga piikide
ja rennid esindama?

19
00:00:45,130 --> 00:00:46,005
>> Sihtrühm: [kuuldamatu]

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

21
00:00:47,002 --> 00:00:47,835
DAVID Humala: Tõepoolest.

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

23
00:00:50,900 --> 00:00:55,480
Ja veel Lõbusas, jumal hoidku,
hoiame üks loeng reedel

24
00:00:55,480 --> 00:00:58,960
alguses semester,
see, mida me näeme juhtuda.

25
00:00:58,960 --> 00:01:03,430
Nii et täna me võtame natuke
rohkem andmestruktuurid.

26
00:01:03,430 --> 00:01:06,660
Ja teile rohkem tahke
vaimne mudel probleeme viis,

27
00:01:06,660 --> 00:01:07,450
mis on nüüd välja.

28
00:01:07,450 --> 00:01:10,817
Õigekirjavead, mida iseloomustab, siis me
käe tekstifaili mõned 100.000

29
00:01:10,817 --> 00:01:12,650
pluss inglise sõnad ja
sa lähed on

30
00:01:12,650 --> 00:01:17,770
nuputada, kuidas nutikalt laadida
mällu RAM, kasutades mõned andmed

31
00:01:17,770 --> 00:01:19,330
struktuuri oma valik.

32
00:01:19,330 --> 00:01:22,470
>> Nüüd üks selline andmestruktuur võib
olla, kuid ilmselt ei tohiks olla,

33
00:01:22,470 --> 00:01:25,630
küllaltki lihtsustatud seotud nimekirja,
mis tutvustasime viimast korda.

34
00:01:25,630 --> 00:01:29,220
Ja ahelloend oli vähemalt
üks eelis massiivi.

35
00:01:29,220 --> 00:01:32,096
Mis on üks eelis
ahelloend vaieldamatult?

36
00:01:32,096 --> 00:01:32,950
>> Sihtrühm: täiendus.

37
00:01:32,950 --> 00:01:33,908
>> DAVID Humala: täiendus.

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

39
00:01:34,155 --> 00:01:35,196
Mida sa mõtled?

40
00:01:35,196 --> 00:01:37,872
>> Sihtrühm: kuhu tahes mööda
nimekiri [kuuldamatu].

41
00:01:37,872 --> 00:01:38,770
>> DAVID Humala: Hea.

42
00:01:38,770 --> 00:01:42,090
Nii saate sisestada element kõikjal
soovite keskel nimekiri

43
00:01:42,090 --> 00:01:45,490
ilma shuffle midagi,
mis me järeldada, meie sorteerimine

44
00:01:45,490 --> 00:01:47,630
arutelud, ei ole
tingimata hea asi,

45
00:01:47,630 --> 00:01:51,200
sest see võtab aega, et tegelikult liiguvad
kõik need inimesed vasakule või paremale.

46
00:01:51,200 --> 00:01:55,540
Ja nii koos seotud nimekirja, saate
lihtsalt eraldada koos malloc, uus sõlm,

47
00:01:55,540 --> 00:01:58,385
ja seejärel ajakohastada paar
pointers-- kaks, kolm operatsiooni max--

48
00:01:58,385 --> 00:02:01,480
ja me saame pesa keegi
kuhugi loendisse.

49
00:02:01,480 --> 00:02:03,550
>> Mida muud oli soodne
umbes ahelloend?

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

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

52
00:02:05,659 --> 00:02:06,534
>> Sihtrühm: [kuuldamatu]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID Humala: 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
See on tõesti dünaamiline.

58
00:02:12,070 --> 00:02:15,100
Ja et sa ei ole toime,
ette, et teatud fikseeritud suurus

59
00:02:15,100 --> 00:02:18,750
patakas mälu, nagu sa oleks
et array, tagurpidi, mis

60
00:02:18,750 --> 00:02:22,455
on, et saate eraldada sõlmede ainult
nõudlus kasutades seejuures ainult nii palju ruumi

61
00:02:22,455 --> 00:02:23,330
kui sa tegelikult vajad.

62
00:02:23,330 --> 00:02:26,830
Erinevalt massiivi, siis võib
kogemata eraldada liiga vähe.

63
00:02:26,830 --> 00:02:28,871
Ja siis see lihtsalt läheb
olla valu kaela

64
00:02:28,871 --> 00:02:32,440
ümber paigutama uus suurem massiiv, kopeerida
kõik üle, vaba vana massiiv,

65
00:02:32,440 --> 00:02:33,990
ja siis liikuda oma äri.

66
00:02:33,990 --> 00:02:37,479
Või veel hullem, siis võiks eraldada viis
rohkem mälu kui te tegelikult vaja,

67
00:02:37,479 --> 00:02:40,520
ja et sa lähed on väga
hõreda asustusega massiiv, nii rääkida.

68
00:02:40,520 --> 00:02:44,350
>> Nii ahelloend annab teile need
eelised dünaamilisus ja paindlikkus

69
00:02:44,350 --> 00:02:46,080
koos sisestusi ja parandusi.

70
00:02:46,080 --> 00:02:48,000
Aga kindlasti peab olema hind, mida makstakse.

71
00:02:48,000 --> 00:02:50,000
Tegelikult on üks neist teemadest
Uurimist viktoriin null

72
00:02:50,000 --> 00:02:52,430
oli paar kompromissid
oleme näinud siiani.

73
00:02:52,430 --> 00:02:56,161
Mis on hind, mida makstakse või
Negatiivne seotud nimekirja?

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

75
00:02:56,660 --> 00:02:57,560
>> Sihtrühm: No muutmälu.

76
00:02:57,560 --> 00:02:58,809
>> DAVID Humala: No muutmälu.

77
00:02:58,809 --> 00:02:59,540
Aga keda see huvitab?

78
00:02:59,540 --> 00:03:01,546
Muutmälu ei kõla veenvad.

79
00:03:01,546 --> 00:03:02,421
>> Sihtrühm: [kuuldamatu]

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

81
00:03:04,865 --> 00:03:05,740
DAVID Humala: Täpselt.

82
00:03:05,740 --> 00:03:07,580
Kui sa tahad olla
teatud algorithm--

83
00:03:07,580 --> 00:03:10,170
ja andke mulle tegelikult ettepaneku
Kahendotsingupuu eelkõige mis

84
00:03:10,170 --> 00:03:12,600
on üks me olen kasutanud üsna bit--
Kui sul ei ole juhuslik juurdepääs,

85
00:03:12,600 --> 00:03:15,516
sa ei saa seda teha lihtsa aritmeetilise
leida nagu keskmine element

86
00:03:15,516 --> 00:03:16,530
ja hüppas õigus seda.

87
00:03:16,530 --> 00:03:20,239
Te asemel on alustada esimesel
element ja lineaarselt otsida vasakusse

88
00:03:20,239 --> 00:03:22,780
paremale, kui soovite leida
keskel või mõni muu element.

89
00:03:22,780 --> 00:03:24,410
>> Sihtrühm: Tõenäoliselt võtab rohkem mälu.

90
00:03:24,410 --> 00:03:25,040
>> DAVID Humala: võtab rohkem mälu.

91
00:03:25,040 --> 00:03:27,464
Kus on, et täiendavad
maksab pärit mälu?

92
00:03:27,464 --> 00:03:28,339
>> Sihtrühm: [kuuldamatu]

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

94
00:03:32,566 --> 00:03:33,440
DAVID Humala: Täpselt.

95
00:03:33,440 --> 00:03:35,679
Selles asjas oli meil
seotud nimekirja täisarvud,

96
00:03:35,679 --> 00:03:37,470
ja veel me kahekordistada
mälu

97
00:03:37,470 --> 00:03:39,680
vajame poolt ka ladustamiseks neid viiteid.

98
00:03:39,680 --> 00:03:42,090
Nüüd vähem suur asi, kui
Sinu structs saada suuremat

99
00:03:42,090 --> 00:03:45,320
ja sa ei salvestata mitmeid kuid
võibolla õpilane või mõne muu esemega.

100
00:03:45,320 --> 00:03:46,880
Aga asi kindlasti jääb.

101
00:03:46,880 --> 00:03:49,421
Ja nii mitmeid operatsioone
kohta ahelloendid kutsuti

102
00:03:49,421 --> 00:03:50,570
olid suured O n-- lineaarne.

103
00:03:50,570 --> 00:03:54,730
Asjad sisestamine ja otsing
või kustutamise korral element

104
00:03:54,730 --> 00:03:57,720
juhtus olema päris lõpus
nimekiri kas see sorteeritud või mitte.

105
00:03:57,720 --> 00:04:01,167
>> Mõnikord võite saada õnnelik ja
nii alam- need toimingud

106
00:04:01,167 --> 00:04:04,250
Võib ka olla pidev aeg, kui sa oled
Jälgides esimene element,

107
00:04:04,250 --> 00:04:05,070
näiteks.

108
00:04:05,070 --> 00:04:09,360
Aga lõpuks me lubasime
saavutada Püha Graal

109
00:04:09,360 --> 00:04:12,630
andmestruktuuride või
teatud ühtlustamist, ning

110
00:04:12,630 --> 00:04:14,290
teel konstantse ajaga.

111
00:04:14,290 --> 00:04:17,579
Kas me leiame elemendid või lisada elemente
või eemaldada elemente nimekirja?

112
00:04:17,579 --> 00:04:19,059
Me näeme üsna varsti.

113
00:04:19,059 --> 00:04:21,100
Ja selgub, et üks
mehhanismide me oleme

114
00:04:21,100 --> 00:04:23,464
kavatse hakata kasutama täna
aastane kasutamiseks p määrata viis,

115
00:04:23,464 --> 00:04:24,630
on tegelikult päris tuttav.

116
00:04:24,630 --> 00:04:27,430
Näiteks, kui see on kamp
eksami raamatuid, millest igaüks

117
00:04:27,430 --> 00:04:29,660
on õpilase esimene
nimi ja perekonnanimi seda,

118
00:04:29,660 --> 00:04:31,820
ja ma valida neid üles
lõpus eksam,

119
00:04:31,820 --> 00:04:33,746
ja nad kõik on päris
palju juhuslikus järjekorras,

120
00:04:33,746 --> 00:04:36,370
ja me tahame minna sorteerimine
need eksamid nii, et kui sorteeritud

121
00:04:36,370 --> 00:04:38,661
see on lihtsalt palju lihtsam ja
kiiremini kätte neid tagasi viia

122
00:04:38,661 --> 00:04:40,030
õpilastele tähestikulises järjekorras.

123
00:04:40,030 --> 00:04:42,770
Mida oma instinkte olla
vaiade eksamid nagu see on?

124
00:04:42,770 --> 00:04:45,019
>> Noh, kui sa oled nagu mina, siis
võib näha, et see on m,

125
00:04:45,019 --> 00:04:48,505
nii et ma lähen omamoodi panna see,
kui see on mu laua või minu korrusel, kus

126
00:04:48,505 --> 00:04:50,650
Ma levib asjad
out-- või minu massiivi really--

127
00:04:50,650 --> 00:04:52,210
Ma võin panna kõik Ms seal.

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

129
00:04:52,710 --> 00:04:55,020
Siin on A. Nii et ma võiks
pane Nagu siin.

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

131
00:04:55,520 --> 00:04:57,980
Siin on veel üks A. Ma lähen
panna, et siin.

132
00:04:57,980 --> 00:05:02,490
Siin on Z. Siin on veel üks M. Ja nii
Ma võin hakata vaiad niimoodi.

133
00:05:02,490 --> 00:05:06,620
Ja siis äkki ma tahaks minna hiljem
ja omamoodi väga nitpicky-Ly sorteeri

134
00:05:06,620 --> 00:05:07,710
üksikute vaiad.

135
00:05:07,710 --> 00:05:11,300
Aga küsimus on, ma näeks
sisendis, et ma olen käega

136
00:05:11,300 --> 00:05:14,016
ja ma teeks mõned arvutatud
otsus põhineb, et sisend.

137
00:05:14,016 --> 00:05:15,640
Kui see algab, pane see sinna.

138
00:05:15,640 --> 00:05:18,980
Kui see algab Z, pane see üle
seal, ja kõik sellises vahel.

139
00:05:18,980 --> 00:05:22,730
>> Nii et see on tehnika, mis on
üldiselt tuntud hashing-- H--S-H-

140
00:05:22,730 --> 00:05:26,550
mis tähendab üldiselt võttes
sisend ja kasutades sisendina arvutada

141
00:05:26,550 --> 00:05:30,940
väärtus, tavaliselt mitu, ja et
number on indeks ladustamine

142
00:05:30,940 --> 00:05:32,260
konteiner, nagu massiivi.

143
00:05:32,260 --> 00:05:35,490
Nii teisisõnu I võivad olla
hash funktsiooni, kui ma oma peas,

144
00:05:35,490 --> 00:05:37,940
et kui ma näen kedagi on
nime, kes algab,

145
00:05:37,940 --> 00:05:40,190
Ma lähen kaarti, et
null peas.

146
00:05:40,190 --> 00:05:44,160
Ja kui ma näen kedagi, kellel Z, ma olen
läheb kaarti, et 25 minu peas

147
00:05:44,160 --> 00:05:46,220
ja seejärel panna, et arvesse
viimane kõige pakk.

148
00:05:46,220 --> 00:05:50,990
>> Nüüd, kui sa arvad, ei ole minu aju
kuid C programm, mis numbrid võiks

149
00:05:50,990 --> 00:05:53,170
sa tugineda, et saavutada sama tulemus?

150
00:05:53,170 --> 00:05:55,594
Teisisõnu, kui te
oli ASCII,

151
00:05:55,594 --> 00:05:57,510
kuidas sa kindlaks
mida kopp panna see?

152
00:05:57,510 --> 00:05:59,801
Sa ilmselt ei taha
pane see ämber 65, mis

153
00:05:59,801 --> 00:06:01,840
oleks nagu seal
mingit põhjust.

154
00:06:01,840 --> 00:06:04,320
Kui sa tahad panna
poolest ASCII väärtus?

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

156
00:06:05,600 --> 00:06:08,920
Kui sa tahad teha oma ASCII
väärtus tulla targemaks ämber

157
00:06:08,920 --> 00:06:09,480
pane see?

158
00:06:09,480 --> 00:06:10,206
>> Sihtrühm: Minus A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID Humala: Jah.

160
00:06:10,956 --> 00:06:13,190
Seega miinus miinus
just 65, kui see on

161
00:06:13,190 --> 00:06:18,240
kapitali A. Või 98, kui
see on väiketähed.

162
00:06:18,240 --> 00:06:21,300
Ja nii, et võimaldaks meil väga
lihtsalt ja väga aritmeetiliselt,

163
00:06:21,300 --> 00:06:23,260
panna midagi ämbrisse niimoodi.

164
00:06:23,260 --> 00:06:26,010
Nii selgub me tegelikult teha
see ka isegi viktoriine.

165
00:06:26,010 --> 00:06:29,051
>> Nii võite meenutada teile ringiga oma
õpetamise mehe nimi kaanel.

166
00:06:29,051 --> 00:06:32,270
Ja TF nimed korraldati
viiakse need sambad tähestikuliselt,

167
00:06:32,270 --> 00:06:34,400
noh, uskuge või mitte,
kui kõik 80 pluss meist

168
00:06:34,400 --> 00:06:37,800
said kokku ühel õhtul astmeni,
viimane samm meie hindamisprotsessi

169
00:06:37,800 --> 00:06:41,830
on hash viktoriinid suurde
ruumi põrandale [kuuldamatu]

170
00:06:41,830 --> 00:06:45,110
ning määrata igaühe viktoriinid välja
täpselt järjekorras TF

171
00:06:45,110 --> 00:06:47,700
nimed kaanel, sest
siis see on palju lihtsam meile

172
00:06:47,700 --> 00:06:51,290
otsida, et lineaarse
otsida või mingi nutikust

173
00:06:51,290 --> 00:06:54,050
jaoks TF leida oma või
Tema õpilaste viktoriine.

174
00:06:54,050 --> 00:06:56,060
>> Nii et see idee hashing
et näete, on

175
00:06:56,060 --> 00:07:00,520
üsna võimas on tegelikult päris
tavaline ja väga intuitiivne,

176
00:07:00,520 --> 00:07:03,000
meelega ehk jagada ja
vallutada oli nädal null.

177
00:07:03,000 --> 00:07:05,250
Ma kiiresti edasi hackathon
paar aastat tagasi.

178
00:07:05,250 --> 00:07:08,040
See oli Zamyla ja paar
teiste töötajate tervitus üliõpilastele

179
00:07:08,040 --> 00:07:09,030
kui nad tulid.

180
00:07:09,030 --> 00:07:12,680
Ja meil oli terve hunnik kokkuklapitavad
tabelid seal nimesiltide.

181
00:07:12,680 --> 00:07:15,380
Ja meil oli nimesiltide korraldatud
sarnaselt Kuna seal

182
00:07:15,380 --> 00:07:16,690
ja Zs seal.

183
00:07:16,690 --> 00:07:20,350
Ja nii üks TF väga nutikalt
kirjutas selle kui kasutusjuhendid

184
00:07:20,350 --> 00:07:21,030
eest päevas.

185
00:07:21,030 --> 00:07:24,480
Ja 12. nädalal semestri see
kõik tegi väga mõistlik ja igaüks

186
00:07:24,480 --> 00:07:25,310
teadis, mida teha.

187
00:07:25,310 --> 00:07:27,900
Aga millal olete
Järjekorras samamoodi,

188
00:07:27,900 --> 00:07:30,272
sa rakendamisel
Sama mõiste hash.

189
00:07:30,272 --> 00:07:31,730
Nii et olgem vormistada natuke.

190
00:07:31,730 --> 00:07:32,890
Siin on massiiv.

191
00:07:32,890 --> 00:07:36,820
See on koostatud olema veidi
lai lihtsalt kujutada visuaalselt,

192
00:07:36,820 --> 00:07:38,920
et me võiksime panna stringid
midagi sellist.

193
00:07:38,920 --> 00:07:41,970
Ja see massiiv on
selgelt suurus 26 kokku.

194
00:07:41,970 --> 00:07:43,935
Ja asi on nn
Tabelis meelevaldselt.

195
00:07:43,935 --> 00:07:48,930
Aga see on lihtsalt kunstniku üleviimise
mida hash tabel võiks olla.

196
00:07:48,930 --> 00:07:52,799
>> Nii hash tabelit nüüd läheb
olla kõrgem andmestruktuur.

197
00:07:52,799 --> 00:07:54,840
Lõpus päeval
me parasjagu näha, et sa

198
00:07:54,840 --> 00:07:58,700
saab rakendada hash tabelit, mis
on palju nagu check-in line

199
00:07:58,700 --> 00:08:02,059
kell hackathon palju nagu see
Tabelis sorteerimisaedikutest eksam raamatuid.

200
00:08:02,059 --> 00:08:03,850
Kuid hash tabelit
omamoodi kõrge taseme

201
00:08:03,850 --> 00:08:08,250
mõiste, mida võiks kasutada massiivi
all kapuuts seda rakendada,

202
00:08:08,250 --> 00:08:11,890
või siis võiks kasutada pikkuse nimekirja, või isegi
võibolla mõned muud andmed struktuure.

203
00:08:11,890 --> 00:08:15,590
Ja nüüd see on theme-- võtmist
mõned neist põhiline koostisosa

204
00:08:15,590 --> 00:08:18,310
nagu massiivi ja selle hoone
blokeerida nüüd pikkusega nimekiri

205
00:08:18,310 --> 00:08:21,740
ja näha, mida muidu saame ehitada
lisaks neile, nagu koostisosade

206
00:08:21,740 --> 00:08:26,550
arvesse retsept, üha enam
huvitav ja kasulik lõpptulemused.

207
00:08:26,550 --> 00:08:28,680
>> Nii et hash tabelit
me võime seda rakendada

208
00:08:28,680 --> 00:08:32,540
mälu piltlikult meeldib see, kuid
kuidas võib see tegelikult olla kodeeritud up?

209
00:08:32,540 --> 00:08:33,789
Noh, võibolla kui lihtsalt on selline.

210
00:08:33,789 --> 00:08:38,270
Kui suutlikkust kõigis mütsid, on lihtsalt
mõned constant-- näiteks 26,

211
00:08:38,270 --> 00:08:42,030
26 tähte alphabet--
Võib ju olla, minu muutuja tabel,

212
00:08:42,030 --> 00:08:45,630
ja ma võin väita, et ma lähen
pane char tähed seal, või string.

213
00:08:45,630 --> 00:08:49,880
Nii et see on nii lihtne kui see, kui sa
soovivad rakendada hash tabelis.

214
00:08:49,880 --> 00:08:51,490
Ja veel, see on tõesti ainult massiivi.

215
00:08:51,490 --> 00:08:53,198
Aga jälle, hash
Tabelis on nüüd, mida jagame

216
00:08:53,198 --> 00:08:57,470
helistada abstraktsete andmete tüüp, mis on lihtsalt
omamoodi kontseptuaalne kihilisus peal

217
00:08:57,470 --> 00:09:00,780
midagi rohkem Ilmalik
nüüd meeldib massiivi.

218
00:09:00,780 --> 00:09:02,960
>> Nüüd, kuidas me minna
umbes probleemide lahendamisel?

219
00:09:02,960 --> 00:09:06,980
Noh, varem oli mul luksus
võttes piisavalt laud ruumi siin

220
00:09:06,980 --> 00:09:09,460
nii et ma võiksin panna
viktoriinid kuskil ma tahtsin.

221
00:09:09,460 --> 00:09:10,620
Nii võiks minna siin.

222
00:09:10,620 --> 00:09:12,100
Zs võiks minna siin.

223
00:09:12,100 --> 00:09:13,230
Ms võiks minna siin.

224
00:09:13,230 --> 00:09:14,740
Ja siis ma pidin mõned ekstra ruumi.

225
00:09:14,740 --> 00:09:18,740
Aga see on natuke petta õigus
nüüd, sest see tabel, kui ma tõesti

226
00:09:18,740 --> 00:09:22,720
mõtles ta massiiv, on lihtsalt
kavatse olla mõned fikseeritud suurus.

227
00:09:22,720 --> 00:09:25,380
>> Nii tehniliselt kui tõmban
järjekordse õpilase viktoriin

228
00:09:25,380 --> 00:09:28,490
ja vaata, oh, kuidas see inimene
nimi algab ka

229
00:09:28,490 --> 00:09:30,980
Ma nagu tahan panna sinna.

230
00:09:30,980 --> 00:09:34,740
Aga niipea, kui ma panin selle sinna, kui
Selle tabeli esindab tõepoolest massiiv,

231
00:09:34,740 --> 00:09:37,840
Ma lähen esmatähtsad või clobbering
kes iganes see õpilase viktoriin on.

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

233
00:09:38,340 --> 00:09:41,972
Kui see on massiiv, ainult üks asi ei saa
minna iga kõnealuste rakkude või elemente.

234
00:09:41,972 --> 00:09:43,680
Ja nii ma selline on
hoolikalt valima.

235
00:09:43,680 --> 00:09:45,735
>> Nüüd varem I tüüpi
pettis ja tegi seda või I

236
00:09:45,735 --> 00:09:47,526
lihtsalt selline laotud
neid teineteise kohal.

237
00:09:47,526 --> 00:09:49,170
Aga see ei kavatse lennata koodi.

238
00:09:49,170 --> 00:09:52,260
Nii et kui ma saaksin panna
teine ​​õpilane, kelle nimi

239
00:09:52,260 --> 00:09:54,964
on siis, kui kõik oli mul see
saadaval tabeli ruumi?

240
00:09:54,964 --> 00:09:57,880
Ja olen kasutanud kolm pesa ja see
Tundub, seal on lihtsalt mõned teised.

241
00:09:57,880 --> 00:09:58,959
Mida saaksid teha?

242
00:09:58,959 --> 00:09:59,834
Sihtrühm: [kuuldamatu]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID Humala: Jah.

245
00:10:01,315 --> 00:10:02,370
Äkki lähme lihtsalt hoida lihtsa.

246
00:10:02,370 --> 00:10:02,660
Õigus?

247
00:10:02,660 --> 00:10:04,243
See ei sobi, kui ma tahan panna.

248
00:10:04,243 --> 00:10:07,450
Nii et ma panen ta
tehniliselt kui B läheks.

249
00:10:07,450 --> 00:10:09,932
Nüüd, muidugi, ma olen hakanud
maalida ennast nurka.

250
00:10:09,932 --> 00:10:11,890
Kui ma saan üliõpilane
kelle nimi on tegelikult B

251
00:10:11,890 --> 00:10:14,840
nüüd B läheb liigutada veidi
edasi, kuna võib juhtuda, jah,

252
00:10:14,840 --> 00:10:17,530
kui see on B, nüüd peab minema siit.

253
00:10:17,530 --> 00:10:20,180
>> Ja nii see väga kiiresti
võib muutuda problemaatiliseks,

254
00:10:20,180 --> 00:10:23,850
aga see on tehnika, mis tegelikult
nimetatakse lineaarse sondeerimine,

255
00:10:23,850 --> 00:10:26,650
mille sa lihtsalt kaaluma oma
massiiv olla liinil.

256
00:10:26,650 --> 00:10:29,680
Ja sa lihtsalt omamoodi sondi või
kontrollima iga saadaval element

257
00:10:29,680 --> 00:10:31,360
otsin saadaval kohapeal.

258
00:10:31,360 --> 00:10:34,010
Ja kui sa leiad
üks, siis langeb ta sinna.

259
00:10:34,010 --> 00:10:38,390
>> Nüüd on hind, mida makstakse praegu
Selle lahenduse on mis?

260
00:10:38,390 --> 00:10:41,300
Meil on fikseeritud suurus massiiv,
ja kui ma sisestada nimed

261
00:10:41,300 --> 00:10:44,059
sinna, vähemalt esialgu, mis on
sõiduaega sisestamise

262
00:10:44,059 --> 00:10:46,350
laskmise õpilaste
viktoriinid õiges ämbrid?

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

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

265
00:10:50,002 --> 00:10:51,147
>> Sihtrühm: n.

266
00:10:51,147 --> 00:10:52,480
DAVID Humala: Kuulsin suur O n.

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

268
00:10:53,530 --> 00:10:54,300
Ei ole tõsi.

269
00:10:54,300 --> 00:10:56,490
Aga me tease peale
miks just praegu.

270
00:10:56,490 --> 00:10:57,702
Mis veel võiks olla?

271
00:10:57,702 --> 00:10:58,755
>> Sihtrühm: [kuuldamatu]

272
00:10:58,755 --> 00:11:00,380
DAVID Humala: Ja las ma teen selle visuaalselt.

273
00:11:00,380 --> 00:11:04,720
Nii et arvan, et see on täht S.

274
00:11:04,720 --> 00:11:05,604
>> Sihtrühm: See on üks.

275
00:11:05,604 --> 00:11:06,520
DAVID Humala: See on üks.

276
00:11:06,520 --> 00:11:06,710
Õigus?

277
00:11:06,710 --> 00:11:08,950
See on massiiv, mille
tähendab, et meil on ligi pääsema.

278
00:11:08,950 --> 00:11:11,790
Ja kui me mõtleme selle
null ja seda 25,

279
00:11:11,790 --> 00:11:13,800
ja me saame aru, et
oh, siin on minu sisend S,

280
00:11:13,800 --> 00:11:16,350
Võin kindlasti teisendada
S, ASCII,

281
00:11:16,350 --> 00:11:18,540
kuni vastav arv
nulli ja 25

282
00:11:18,540 --> 00:11:20,910
ja siis kohe
pane see, kuhu see kuulub.

283
00:11:20,910 --> 00:11:26,120
>> Aga muidugi, niipea kui saan
Teine isik, kelle nime on A või B või C

284
00:11:26,120 --> 00:11:29,300
lõpuks, kui olen kasutanud
lineaarne katsetamine minu lahendus,

285
00:11:29,300 --> 00:11:31,360
töötamise aeg
sisestamise halvimal juhul

286
00:11:31,360 --> 00:11:33,120
tegelikult läheb vaimule mida?

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

288
00:11:34,270 --> 00:11:36,045
Ja ma ei kuule seda siin
õigesti varakult.

289
00:11:36,045 --> 00:11:36,920
Sihtrühm: [kuuldamatu]

290
00:11:36,920 --> 00:11:41,620
DAVID Humala: Nii et see on n tõesti kord
sul on piisavalt suur andmekogum.

291
00:11:41,620 --> 00:11:44,410
Niisiis, ühelt poolt, kas
Sinu massiiv on piisavalt suur

292
00:11:44,410 --> 00:11:48,287
ja teie andmed on hõre piisavalt, siis
saada see ilus konstantse ajaga.

293
00:11:48,287 --> 00:11:50,620
Aga niipea, kui hakkate
üha rohkem ja rohkem elemente,

294
00:11:50,620 --> 00:11:53,200
ja lihtsalt statistiliselt saad
rohkem inimesi tähega

295
00:11:53,200 --> 00:11:56,030
Oma nime või täht
B, siis võib see

296
00:11:56,030 --> 00:11:57,900
vaimule midagi lineaarne.

297
00:11:57,900 --> 00:11:59,640
Nii et ei ole päris täiuslik.

298
00:11:59,640 --> 00:12:00,690
Nii saaksime teha paremini?

299
00:12:00,690 --> 00:12:03,210
>> Noh, mis oli meie
lahendus enne, kui me

300
00:12:03,210 --> 00:12:06,820
tahad olla rohkem dünaamikat kui
midagi massiivi lubatud?

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

302
00:12:08,085 --> 00:12:08,960
Sihtrühm: [kuuldamatu]

303
00:12:08,960 --> 00:12:10,030
DAVID Humala: Mida me tutvustada?

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

305
00:12:10,530 --> 00:12:11,430
Nii ahelloend.

306
00:12:11,430 --> 00:12:14,430
Noh, vaatame, mis on seotud
nimekirja võib teha meie jaoks mitte.

307
00:12:14,430 --> 00:12:17,630
Noh, las ma ettepaneku, et me
joonistada pilt järgmine.

308
00:12:17,630 --> 00:12:19,620
Nüüd on see erinev
Pildi näide

309
00:12:19,620 --> 00:12:24,750
erinevast tekst, tegelikult, et
on tegelikult kasutades massiivi suurus 31.

310
00:12:24,750 --> 00:12:28,220
Ja selle autor lihtsalt
otsustas hash stringid

311
00:12:28,220 --> 00:12:32,430
ei põhine isiku nimed,
vaid põhineb nende birthdates.

312
00:12:32,430 --> 00:12:35,680
Sõltumata sellest, kuu, siis arvasin
kui sa oled sündinud esimene kuu

313
00:12:35,680 --> 00:12:39,580
või 31. kuu, autor
ei räsi, mis põhineb selle väärtuse,

314
00:12:39,580 --> 00:12:44,154
et levinud nimesid välja natuke
enamat kui lihtsalt 26 laigud võivad anda.

315
00:12:44,154 --> 00:12:47,320
Ja võib-olla see on natuke ühtlasem
kui lähen tähestiku tähti

316
00:12:47,320 --> 00:12:50,236
sest loomulikult on ilmselt
rohkem inimesi maailmas nimed

317
00:12:50,236 --> 00:12:54,020
et alustada kui kindlasti
mõne teise tähestiku tähti.

318
00:12:54,020 --> 00:12:56,380
Nii et võib-olla see on natuke
ühtsema, eeldades,

319
00:12:56,380 --> 00:12:58,640
ühtlase jaotuse
beebide üle kuu.

320
00:12:58,640 --> 00:12:59,990
>> Aga muidugi, see on veel puudulik.

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

322
00:13:00,370 --> 00:13:01,370
Meil oli kokkupõrkeid.

323
00:13:01,370 --> 00:13:04,680
Mitu inimest selles
andmestruktuur veel

324
00:13:04,680 --> 00:13:08,432
millel on sama sünnikuupäev vähemalt
sa oled olenemata kuus.

325
00:13:08,432 --> 00:13:09,640
Aga milline on autor teinud?

326
00:13:09,640 --> 00:13:13,427
Noh, tundub, et meil on massiiv
vasakul servas joonistatud vertikaalselt,

327
00:13:13,427 --> 00:13:15,010
aga see on lihtsalt kunstniku üleviimise.

328
00:13:15,010 --> 00:13:18,009
Ei ole oluline, millises suunas sa
juhtida massiivi, see on ikka massiivi.

329
00:13:18,009 --> 00:13:20,225
Mis see on massiivi ilmselt?

330
00:13:20,225 --> 00:13:21,500
>> Sihtrühm: seotud nimekirja.

331
00:13:21,500 --> 00:13:21,650
>> DAVID Humala: Jah.

332
00:13:21,650 --> 00:13:23,490
Tundub, et see on
massiivi seotud nimekirja.

333
00:13:23,490 --> 00:13:26,490
Nii et jällegi, et see koht omamoodi
kasutades nende andmestruktuuride nüüd

334
00:13:26,490 --> 00:13:28,550
koostisosadena rohkem
huvitavaid lahendusi,

335
00:13:28,550 --> 00:13:30,862
saab absoluutselt võtma
põhiõiguste, nagu massiiv,

336
00:13:30,862 --> 00:13:33,320
ja siis võta midagi rohkem
huvitav nagu ahelloend

337
00:13:33,320 --> 00:13:36,660
ja isegi ühendada need isegi
huvitavam andmestruktuur.

338
00:13:36,660 --> 00:13:39,630
Ja tõepoolest, ka see oleks
nimetada hash tabelit,

339
00:13:39,630 --> 00:13:42,610
mille massiiv on
tõesti hash tabelit,

340
00:13:42,610 --> 00:13:45,600
kuid hash tabelis on
ketid, niiöelda

341
00:13:45,600 --> 00:13:50,220
mis võib kasvada või kahaneb põhineb
mitmeid elemente, mida soovite lisada.

342
00:13:50,220 --> 00:13:52,990
>> Nüüd, seega, mis on
sõiduaega nüüd?

343
00:13:52,990 --> 00:13:58,030
Kui ma tahan, et sisestada keegi
kelle sünnipäev on 31. oktoober,

344
00:13:58,030 --> 00:13:59,040
kui ei, ta läks?

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

346
00:14:00,530 --> 00:14:01,030
Hea küll.

347
00:14:01,030 --> 00:14:02,819
Kõige all, kus ta ütleb 31.

348
00:14:02,819 --> 00:14:03,610
Ja see on täiuslik.

349
00:14:03,610 --> 00:14:05,060
See oli pidev aega.

350
00:14:05,060 --> 00:14:08,760
Aga mis siis, kui me leiame kellegi teise
kelle sünnipäev on, vaatame,

351
00:14:08,760 --> 00:14:10,950
Oktoober, november, detsember 31?

352
00:14:10,950 --> 00:14:12,790
Kus on ta lähe?

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

354
00:14:13,290 --> 00:14:13,970
Kaks sammu küll.

355
00:14:13,970 --> 00:14:15,303
See on püsiv, kuigi kas pole?

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

357
00:14:16,360 --> 00:14:16,860
Hea küll.

358
00:14:16,860 --> 00:14:17,840
Praegusel hetkel on.

359
00:14:17,840 --> 00:14:20,570
Kuid üldiselt juhul,
rohkem inimesi lisame,

360
00:14:20,570 --> 00:14:23,790
tõenäosuslikult me ​​läheme
et saada rohkem ja rohkem kokkupõrkeid.

361
00:14:23,790 --> 00:14:26,820
>> Nüüd on see väike
parem, sest tehniliselt

362
00:14:26,820 --> 00:14:34,580
nüüd on mu ahelaid võiks olla
Halvimal juhul, kui kaua?

363
00:14:34,580 --> 00:14:38,890
Kui ma sisestan n inimesed sellesse rohkem
keerukamaid andmestruktuur, n inimesi,

364
00:14:38,890 --> 00:14:41,080
halvimal juhul, et see saab olema n.

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

366
00:14:41,815 --> 00:14:43,332
>> Sihtrühm: Sest kui kõik
on sama sünnipäev,

367
00:14:43,332 --> 00:14:44,545
nad ei kavatse olla üks rida.

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

369
00:14:45,420 --> 00:14:47,480
See võib olla natuke kunstlik,
kuid tõeliselt halvimal juhul

370
00:14:47,480 --> 00:14:50,117
kui kõigil on sama sünnipäev,
antud sisendite olete,

371
00:14:50,117 --> 00:14:51,950
sa lähed on
tohutult pikk kett.

372
00:14:51,950 --> 00:14:54,241
Ja nii, siis võiks seda nimetada
hash tabel, kuid tegelikult on see

373
00:14:54,241 --> 00:14:56,810
lihtsalt massiivne seotud nimekirja
Kogu palju raisatud ruumi.

374
00:14:56,810 --> 00:15:00,460
Aga üldiselt, kui me eeldame, et
vähemalt sünnipäevad on uniform--

375
00:15:00,460 --> 00:15:01,750
ja siis ilmselt ei ole.

376
00:15:01,750 --> 00:15:02,587
Ma teen selle ära.

377
00:15:02,587 --> 00:15:04,420
Aga kui me eeldame, et
Huvides arutelu

378
00:15:04,420 --> 00:15:07,717
et nad on, siis teoreetiliselt kui
see on vertikaalse esindatuse

379
00:15:07,717 --> 00:15:11,050
massiiv, hästi siis loodetavasti oled
hakka ketid, tead,

380
00:15:11,050 --> 00:15:15,880
umbes sama pikk, kui iga
need on päev kuus.

381
00:15:15,880 --> 00:15:19,930
>> Nüüd, kui seal on 31 päeva kuus,
see tähendab, et minu sõiduaega tõesti

382
00:15:19,930 --> 00:15:25,230
on suur O n üle 31, mis
tundub parem kui lineaarne.

383
00:15:25,230 --> 00:15:27,950
Aga mis oli üks meie
kohustuste paar nädalat

384
00:15:27,950 --> 00:15:31,145
tagasi, kui ta tuli väljendades
töötamise aeg algoritm?

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

386
00:15:33,450 --> 00:15:35,190
Lihtsalt vaadata ainult kõrge, et perspektiivis.

387
00:15:35,190 --> 00:15:35,690
Õigus?

388
00:15:35,690 --> 00:15:37,400
31 on kindlasti kasulik.

389
00:15:37,400 --> 00:15:39,610
Aga see on ikka suur O n.

390
00:15:39,610 --> 00:15:41,730
Aga üks teemasid
Probleemi seatud viis

391
00:15:41,730 --> 00:15:43,950
läheb üles
tunnistama, et absoluutselt,

392
00:15:43,950 --> 00:15:47,320
asümptootiliselt teoreetiliselt
see andmestruktuur

393
00:15:47,320 --> 00:15:50,470
ei ole parem kui lihtsalt
üks massiivne seotud nimekirja.

394
00:15:50,470 --> 00:15:53,550
Ja tõepoolest, halvimal juhul on see
hash tabelit võiks vaimule et.

395
00:15:53,550 --> 00:15:57,620
>> Aga reaalses maailmas, meie inimestele
et oma Mac või PC-või mis iganes

396
00:15:57,620 --> 00:16:01,240
ja töötab reaalses maailmas
tarkvara reaalses maailmas andmed,

397
00:16:01,240 --> 00:16:03,260
mis algoritmi sa lähed eelistate?

398
00:16:03,260 --> 00:16:09,180
Üks, mis leiab lõpuks samme või
üks, mis võtab n jagatud 31 sammu

399
00:16:09,180 --> 00:16:12,900
leida mingi tükk andmed või
otsida mõned andmed?

400
00:16:12,900 --> 00:16:16,580
Ma mõtlen, et absoluutselt 31 marki
Erinevus reaalses maailmas.

401
00:16:16,580 --> 00:16:18,540
See on 31 korda kiirem.

402
00:16:18,540 --> 00:16:20,880
Ja meie, inimesed, oleme kindlasti
läheb hindan seda.

403
00:16:20,880 --> 00:16:23,004
>> Nii et realiseerida dihhotoomia
seal vahel tegelikult

404
00:16:23,004 --> 00:16:25,920
räägime asjad teoreetiliselt
ja asymptotically mis kindlasti

405
00:16:25,920 --> 00:16:28,760
on väärtus, nagu me oleme näinud,
kuid reaalses maailmas,

406
00:16:28,760 --> 00:16:32,930
kui sa hoolid lihtsalt tegemise
inimese õnnelikuks üldine sisendite

407
00:16:32,930 --> 00:16:36,010
sa võiksid väga hästi taha nõustuda
asjaolu, et jah, see on lineaarne,

408
00:16:36,010 --> 00:16:38,360
aga see on 31 korda kiirem
kui lineaarne olla.

409
00:16:38,360 --> 00:16:41,610
Ja veel parem, me lihtsalt ei pea
midagi meelevaldset nagu sünnikuupäev,

410
00:16:41,610 --> 00:16:44,030
võiksime kulutada veidi
rohkem aega ja nutikust

411
00:16:44,030 --> 00:16:47,140
ja mõtle, mida me võiksime teha,
antud isiku nime ja võib-olla

412
00:16:47,140 --> 00:16:50,130
oma sünnikuupäev ühendada need
koostisosad välja nuputada midagi

413
00:16:50,130 --> 00:16:52,720
see on tõesti rohkem
ühtne ja vähem sakiline,

414
00:16:52,720 --> 00:16:56,250
nii rääkida kui seda pilti
Praegu näitab see võiks olla.

415
00:16:56,250 --> 00:16:57,750
Kuidas me saame rakendada seda koodi?

416
00:16:57,750 --> 00:17:00,280
Noh, las ma ettepaneku, et me
lihtsalt laenata süntaks me oleme

417
00:17:00,280 --> 00:17:01,799
kasutatud paar korda siiani.

418
00:17:01,799 --> 00:17:03,590
Ja ma lähen, et määratleda
sõlm, mis jällegi

419
00:17:03,590 --> 00:17:06,812
on üldnimetus vaid mõned
konteiner mõne andmestruktuuri.

420
00:17:06,812 --> 00:17:09,020
Ma lähen ettepaneku
string läheb sinna.

421
00:17:09,020 --> 00:17:11,369
Aga me ei kavatse hakata võtma
need abirattad ära nüüd.

422
00:17:11,369 --> 00:17:13,230
>> Enam CS50 raamatukogu
tõesti, kui soovite

423
00:17:13,230 --> 00:17:15,230
kasutada seda teie lõplik
Projekt, mis on hea,

424
00:17:15,230 --> 00:17:18,569
kuid nüüd me ei kavatse tõmmake
kardinapuud ja öelda, et see on lihtsalt char täht.

425
00:17:18,569 --> 00:17:22,069
Nii sõna seal saab olema
isiku nimele.

426
00:17:22,069 --> 00:17:25,079
Ja nüüd on mul link
siin järgmise sõlme

427
00:17:25,079 --> 00:17:28,170
nii, et need esindavad
Iga sõlmed

428
00:17:28,170 --> 00:17:30,950
ahelas, potentsiaalselt
on seotud nimekirja.

429
00:17:30,950 --> 00:17:34,090
>> Ja nüüd, kui ma kuulutada
hash tabelit ise?

430
00:17:34,090 --> 00:17:36,660
Kuidas kuulutada kogu see struktuur?

431
00:17:36,660 --> 00:17:40,960
Noh, tegelikult, palju nagu ma harjunud pointer
lihtsalt esimene element nimekirja

432
00:17:40,960 --> 00:17:44,510
enne sarnaselt ma saan ainult öelda,
Ma lihtsalt pean hunnik viiteid

433
00:17:44,510 --> 00:17:46,270
rakendada seda kogu hash tabelis.

434
00:17:46,270 --> 00:17:49,484
Ma lähen on massiivi
nimetatakse tabelit hash tabelis.

435
00:17:49,484 --> 00:17:50,900
See saab olema suurust võimsust.

436
00:17:50,900 --> 00:17:52,525
See, kui palju elemente mahub ta.

437
00:17:52,525 --> 00:17:56,180
Ja kõik need elemendid selles
massiivi läheb sõlme star.

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

439
00:17:56,810 --> 00:18:00,160
Noh, kohta see pilt, mida ma olen
rakendamisel hash tabelit

440
00:18:00,160 --> 00:18:04,330
tõhusalt algusest on lihtsalt
Selle massiivi et oleme tõmmatud vertikaalselt,

441
00:18:04,330 --> 00:18:06,820
Iga kelle väljakud
esindab pointer.

442
00:18:06,820 --> 00:18:09,170
See need, mis on kaldkriipsuga
nende kaudu on lihtsalt null.

443
00:18:09,170 --> 00:18:11,410
Ja need, mis on
nooled läheb paremale

444
00:18:11,410 --> 00:18:16,140
on tegelik vihjeid tegelik sõlmede
Ergo algust seotud nimekirja.

445
00:18:16,140 --> 00:18:19,050
>> Nii et siin on siis kuidas me võiksime
rakendada hash tabelit, et

446
00:18:19,050 --> 00:18:21,580
rakendab eraldi ühendamine.

447
00:18:21,580 --> 00:18:22,840
Nüüd me saame teha paremini?

448
00:18:22,840 --> 00:18:25,632
Olgu Lubasin viimane kord,
võiksime saavutada konstantset aega.

449
00:18:25,632 --> 00:18:27,381
Ja ma omamoodi andis sulle
konstantset aega siin,

450
00:18:27,381 --> 00:18:29,850
kuid siis ütles, ei ole tõesti
pidev aeg, sest see on ikka

451
00:18:29,850 --> 00:18:31,890
sõltub kokku
elementide arv

452
00:18:31,890 --> 00:18:34,500
sa oled sisestamist
andmestruktuur.

453
00:18:34,500 --> 00:18:35,980
Aga oletame me seda tegime.

454
00:18:35,980 --> 00:18:39,550
Lubage mul minna tagasi ekraanil siin.

455
00:18:39,550 --> 00:18:44,520
Lubage mul ka projitseerida see siin, selge
ekraanile ja arvan, et ma tegin seda.

456
00:18:44,520 --> 00:18:49,300
Oletame, et ma tahtsin lisada nimi
Daven aastal minu andmete struktuuri.

457
00:18:49,300 --> 00:18:52,100
>> Ma tahan lisada string
Daven arvesse andmete struktuuri.

458
00:18:52,100 --> 00:18:54,370
Mida teha, kui ma ei kasuta
hash tabel, kuid ma kasutan

459
00:18:54,370 --> 00:18:56,980
midagi, mis on rohkem puu-like
nagu sugupuu, kus

460
00:18:56,980 --> 00:18:59,670
teil on root
top ja siis sõlmede ja lehed

461
00:18:59,670 --> 00:19:01,440
mis lähevad alla ja väljapoole.

462
00:19:01,440 --> 00:19:04,450
Oletame siis, et ma
soovite lisada Daven poolt

463
00:19:04,450 --> 00:19:06,430
arvesse, milline on hetkel tühi nimekiri.

464
00:19:06,430 --> 00:19:09,780
Ma lähen tegema järgmist: Ma olen
kavatse luua sõlme selles perekonnas

465
00:19:09,780 --> 00:19:15,170
puu-like andmete struktuur, mis näeb välja
natuke niimoodi, millest igaüks

466
00:19:15,170 --> 00:19:19,640
ristkülikud on, ütleme,
nüüd 26 elemente.

467
00:19:19,640 --> 00:19:21,650
Ja iga rakkudes
selles array läheb

468
00:19:21,650 --> 00:19:23,470
esindada kirja tähestik.

469
00:19:23,470 --> 00:19:28,190
>> Täpsemalt, ma lähen raviks
see on, siis B, siis C, siis D

470
00:19:28,190 --> 00:19:29,310
see siin.

471
00:19:29,310 --> 00:19:32,940
Nii et see saab tõhusalt
esindavad kirja D.

472
00:19:32,940 --> 00:19:36,040
Aga sisestada kõik Daven on
nimi mida ma pean tegema natuke rohkem.

473
00:19:36,040 --> 00:19:37,840
Nii et ma olen esimene läheb räsi, nii rääkida.

474
00:19:37,840 --> 00:19:41,049
Ma lähen vaatama algustäht
aastal Daven on mis on ilmselgelt D

475
00:19:41,049 --> 00:19:42,840
ja ma lähen eraldada
sõlm, mis näeb välja

476
00:19:42,840 --> 00:19:45,570
nagu see-- suur ristkülik suur
piisavalt, et see sobiks kogu tähestikku.

477
00:19:45,570 --> 00:19:47,140
>> Nüüd D on tehtud.

478
00:19:47,140 --> 00:19:49,720
Nüüd A. D--V-E-N on eesmärk.

479
00:19:49,720 --> 00:19:51,220
Nii et nüüd ma lähen tegema, on see.

480
00:19:51,220 --> 00:19:54,027
Niipea kui hakkasin D teade
pole pointer seal.

481
00:19:54,027 --> 00:19:56,860
See on prügi väärtused hetkel,
või ma võin selle vormindamiseks tühjaks.

482
00:19:56,860 --> 00:19:59,630
Aga las ma käiks koos
Selle ehitamise idee puu.

483
00:19:59,630 --> 00:20:04,260
Lubage mul eraldada veel üks neist
sõlmed, mis on 26 elemente.

484
00:20:04,260 --> 00:20:05,150
>> Ja tead mis?

485
00:20:05,150 --> 00:20:09,130
Kui see on lihtsalt sõlme mälu
Ma loodud malloc, kasutades struct

486
00:20:09,130 --> 00:20:11,240
nagu me varsti näeme,
Ma lähen tegema see--

487
00:20:11,240 --> 00:20:14,450
Ma lähen juhtida nool
asi, mis esindab D alla

488
00:20:14,450 --> 00:20:15,860
Selle uue sõlme.

489
00:20:15,860 --> 00:20:19,240
Ja nüüd, esimene järgmise
kirja Daven nimi,

490
00:20:19,240 --> 00:20:24,150
V- D--V- ma lähen edasi minna
ja juhtida teise sõlme meeldib see,

491
00:20:24,150 --> 00:20:30,150
kusjuures, V elementide siit, mida
me joonistada instance-- whoops.

492
00:20:30,150 --> 00:20:31,020
Me ei tõmba sinna.

493
00:20:31,020 --> 00:20:31,936
See saab minna siin.

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

495
00:20:32,890 --> 00:20:35,712
>> Siis me ei kavatse
peavad seda V.

496
00:20:35,712 --> 00:20:44,920
Ja siis siin me ei kavatse indeks
maha V, mida me kaaluda E.

497
00:20:44,920 --> 00:20:50,100
Ja siis siit me läheme
minge üks neist sõlmede siin.

498
00:20:50,100 --> 00:20:52,930
Ja nüüd on küsimus vastata.

499
00:20:52,930 --> 00:20:57,840
Mul on vaja kuidagi näidata, et
me lõpus stringi Daven.

500
00:20:57,840 --> 00:20:59,490
Nii et ma võiks lihtsalt jätta see null.

501
00:20:59,490 --> 00:21:02,670
>> Aga kui meil on Daven poolt
täisnimi ka, mis

502
00:21:02,670 --> 00:21:04,280
on, nagu me oleme öelnud, Davenport?

503
00:21:04,280 --> 00:21:06,970
Mis siis, kui Daven on
tegelikult alamstring,

504
00:21:06,970 --> 00:21:08,960
eesliide palju pikem string?

505
00:21:08,960 --> 00:21:11,450
Me ei saa lihtsalt püsivalt
Rääkimata läheb

506
00:21:11,450 --> 00:21:14,410
sinna minna, sest me võiksime
kunagi sisestada sõna nagu Davenport

507
00:21:14,410 --> 00:21:15,840
sellesse andmestruktuur

508
00:21:15,840 --> 00:21:19,560
>> Niisiis, mida me võiksime teha, selle asemel on
Raviks iga nende elementide

509
00:21:19,560 --> 00:21:22,170
nagu võibolla millel on kaks
elementide sees neist.

510
00:21:22,170 --> 00:21:24,810
Üks on osuti tõepoolest
nagu ma olen teinud.

511
00:21:24,810 --> 00:21:27,100
Nii et kõik need karbid
ei ole vaid ühe lahtri.

512
00:21:27,100 --> 00:21:29,855
Aga kui top
one-- alt üks

513
00:21:29,855 --> 00:21:32,230
saab olema null, sest
puudub Davenport veel.

514
00:21:32,230 --> 00:21:34,197
Mis siis, kui ülemine
on mingi eriline väärtus?

515
00:21:34,197 --> 00:21:36,530
Ja see saab olema veidi
raske tõmmata ta selle suurus.

516
00:21:36,530 --> 00:21:38,130
Aga arvan, et see on lihtsalt linnuke.

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

518
00:21:38,920 --> 00:21:44,230
D--V-E-N on string
selles andmestruktuur.

519
00:21:44,230 --> 00:21:48,350
>> Vahepeal, kui mul oleks rohkem ruumi
siin, ma võiks teha P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
ja ma võiks panna check sõlme
mis on kirjas T päris lõpus.

521
00:21:52,650 --> 00:21:55,460
Nii et see on tohutult
keeruline välimusega andmestruktuur.

522
00:21:55,460 --> 00:21:57,210
Ja minu käekiri
Kindlasti ei aita.

523
00:21:57,210 --> 00:22:00,043
Aga kui ma tahan lisada midagi
muud, kaaluma, mida me teeme.

524
00:22:00,043 --> 00:22:03,370
Kui me tahtsime panna Taavet,
me tahaks järgida sama loogikat, D--V

525
00:22:03,370 --> 00:22:08,802
aga nüüd märgin järgmise
element mitte E, vaid I D.

526
00:22:08,802 --> 00:22:10,760
Nii et saab olema
rohkem tippe seda puud.

527
00:22:10,760 --> 00:22:12,325
Me läheme on kõne malloc rohkem.

528
00:22:12,325 --> 00:22:14,700
Aga ma ei taha teha
täielik jama see pilt.

529
00:22:14,700 --> 00:22:17,710
Nii et olgem selle asemel vaadata ühe
mis on olnud eelnevalt koostatud

530
00:22:17,710 --> 00:22:21,810
niimoodi ei dot, dot,
täpid, aga lihtsalt lühendatult massiivid.

531
00:22:21,810 --> 00:22:23,950
Kuid iga sõlmed
Selles puu siin

532
00:22:23,950 --> 00:22:26,700
on sama asi--
massiivi Ray suurus 26.

533
00:22:26,700 --> 00:22:28,860
>> Või kui me tahame olla
tõesti õige nüüd, mida

534
00:22:28,860 --> 00:22:30,790
kui kellegi nime
ülakomaga, olgem

535
00:22:30,790 --> 00:22:35,560
eeldada, et iga sõlm on tegelikult
nagu 27 indeksid seda, mitte ainult 26.

536
00:22:35,560 --> 00:22:42,020
Nii et see nüüd läheb andmed
struktuuri nimetatakse trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
Prefiksipuu, mis on väidetavalt
ajalooliselt nutikas nimi puu

538
00:22:46,120 --> 00:22:49,040
mis on optimeeritud
otsing, mis muidugi

539
00:22:49,040 --> 00:22:50,870
kirjutatakse I-E, nii see on Prefiksipuu.

540
00:22:50,870 --> 00:22:52,710
Aga see on ajalugu Prefiksipuu.

541
00:22:52,710 --> 00:22:55,860
>> Nii Prefiksipuu on see puu-like andmete
struktuur nagu sugupuu

542
00:22:55,860 --> 00:22:57,510
et lõpuks käitub niimoodi.

543
00:22:57,510 --> 00:23:00,890
Ja siin on lihtsalt üks järjekordne näide
terve hunnik teiste inimeste nimed.

544
00:23:00,890 --> 00:23:03,540
Aga küsimus nüüd
käepärast on see, mis on

545
00:23:03,540 --> 00:23:08,070
Me saime kehtestades vaieldamatult rohkem
keeruline andmestruktuur, ja üks,

546
00:23:08,070 --> 00:23:09,870
ausalt, mis kasutab palju mälu.

547
00:23:09,870 --> 00:23:11,703
>> Sest kuigi
hetkel, ma olen ainult

548
00:23:11,703 --> 00:23:15,050
kasutades D's osuti ja
Ja V Es ja Ns,

549
00:23:15,050 --> 00:23:16,700
Ma raisata Heck palju mälu.

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

551
00:23:18,030 --> 00:23:22,660
Aga kus ma veedan ühe ressursi,
Ma pigem ei saada tagasi teise.

552
00:23:22,660 --> 00:23:26,020
Nii et kui ma kulutada rohkem ruumi
mis on ilmselt lootust?

553
00:23:26,020 --> 00:23:27,407
Et ma olen vähem kulutama mida?

554
00:23:27,407 --> 00:23:28,240
Sihtrühm: Vähem aega.

555
00:23:28,240 --> 00:23:28,990
DAVID Humala: Aeg.

556
00:23:28,990 --> 00:23:30,320
Nüüd, miks see võiks olla?

557
00:23:30,320 --> 00:23:33,880
Noh, mis on sisestamise
ajal nii suur O nüüd,

558
00:23:33,880 --> 00:23:37,660
nime nagu Daven
või Davenport või David?

559
00:23:37,660 --> 00:23:39,340
Noh, Daven oli viis sammu.

560
00:23:39,340 --> 00:23:42,350
Davenport oleks üheksa astet,
nii et see oleks veel paar sammu.

561
00:23:42,350 --> 00:23:44,250
David oleks viis sammu samuti.

562
00:23:44,250 --> 00:23:47,230
Nii et need on betooni
numbreid, kuid kindlasti pole

563
00:23:47,230 --> 00:23:49,550
ülemise kohta
pikkus kellegi nime.

564
00:23:49,550 --> 00:23:52,240
Ja tõepoolest, on probleem
komplekti viis kirjeldusele

565
00:23:52,240 --> 00:23:54,050
me ei kavatse teha ettepanekuid
et see on midagi,

566
00:23:54,050 --> 00:23:55,470
see on 40-mõned-paaritu tähemärki.

567
00:23:55,470 --> 00:23:58,180
>> Reaalselt ei ole keegi
lõpmatult pikk nimi,

568
00:23:58,180 --> 00:24:01,542
mis tähendab, et pikkus
Nimi või pikkus string me võiksime

569
00:24:01,542 --> 00:24:03,750
on teatud seisund
struktuur on vaieldamatult mida?

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

571
00:24:05,550 --> 00:24:06,250
See on pidev.

572
00:24:06,250 --> 00:24:06,430
Õigus?

573
00:24:06,430 --> 00:24:09,310
See võib olla suur konstantne nagu
40-midagi, kuid see on konstantne.

574
00:24:09,310 --> 00:24:13,752
Ja see ei ole sõltuvus, kui palju
teised nimed on selles andmestruktuur.

575
00:24:13,752 --> 00:24:15,460
Teisisõnu, kui ma
tahtsin nüüd sisestada

576
00:24:15,460 --> 00:24:20,540
Colton või Gabriel või Rob või Zamyla või
Alison või Belinda või muud nimed

577
00:24:20,540 --> 00:24:23,940
alates personal sellesse andmed
struktuuri, on sõiduaega

578
00:24:23,940 --> 00:24:26,750
sisestades muud nimed
saab olema kõik mõjutanud

579
00:24:26,750 --> 00:24:30,220
kui palju muid elemente
andmestruktuuris juba?

580
00:24:30,220 --> 00:24:31,040
See ei ole.

581
00:24:31,040 --> 00:24:31,540
Õigus?

582
00:24:31,540 --> 00:24:36,150
Kuna me tegelikult kasutab
see mitmekihiline hash tabelis.

583
00:24:36,150 --> 00:24:38,280
Ja sõiduaega
kõik need toimingud

584
00:24:38,280 --> 00:24:41,510
ei sõltu arvu kohta
elemendid, mis on andmestruktuur

585
00:24:41,510 --> 00:24:43,090
või mis lõpuks läheb
olema andmestruktuur,

586
00:24:43,090 --> 00:24:44,714
kuid pikkus, mida konkreetselt?

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

588
00:24:46,500 --> 00:24:49,200
>> String on
sisestatud, mis ei tee

589
00:24:49,200 --> 00:24:52,580
Selle asymptotically pidev
AEG_ suur O ühe.

590
00:24:52,580 --> 00:24:54,720
Ja ausalt öeldes, igaks
reaalses maailmas, see

591
00:24:54,720 --> 00:24:58,380
tähendab sisestamist Daven nime võtab
nagu viis sammu või Davenport üheksa

592
00:24:58,380 --> 00:25:00,100
samme või David viis sammu.

593
00:25:00,100 --> 00:25:03,071
See on päris darn väike jooksmine korda.

594
00:25:03,071 --> 00:25:05,320
Ja tõesti, see on väga
hea asi, eriti kui

595
00:25:05,320 --> 00:25:08,126
see ei sõltu kokku
elementide arv seal.

596
00:25:08,126 --> 00:25:10,500
Niisiis, kuidas võiks me rakendada seda
selline struktuur koodi?

597
00:25:10,500 --> 00:25:12,900
See on veidi rohkem
keeruline, kuid siiski on see

598
00:25:12,900 --> 00:25:15,050
lihtsalt kohaldamist
põhiplokke.

599
00:25:15,050 --> 00:25:17,830
Ma lähen uuesti
meile sõlme järgmiselt:

600
00:25:17,830 --> 00:25:21,100
bool nimetatakse word-- ja see
võiks nimetada midagi.

601
00:25:21,100 --> 00:25:23,970
Aga bool esindab
mida ma joonistasin nagu linnuke.

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

603
00:25:24,490 --> 00:25:26,720
See on lõpuks string
selles andmestruktuur.

604
00:25:26,720 --> 00:25:30,702
>> Ja muidugi sõlme tärni
seal viitab lastele.

605
00:25:30,702 --> 00:25:32,410
Ja tõesti, just nagu
sugupuu, siis

606
00:25:32,410 --> 00:25:34,370
kaaluks sõlmed
mis ripuvad välja

607
00:25:34,370 --> 00:25:36,920
põhja mõned vanema
element olema lapsed.

608
00:25:36,920 --> 00:25:40,510
Ja nii lastel läheb
olema massiiv 27, 27. üks

609
00:25:40,510 --> 00:25:41,680
olemisele eest ülakoma.

610
00:25:41,680 --> 00:25:43,390
Me läheme sorteeri
erijuhtum seda.

611
00:25:43,390 --> 00:25:45,400
Nii et teil on teatud
nimed ülakomad.

612
00:25:45,400 --> 00:25:47,399
Võib-olla isegi sidekriipsuga peaks
sinna minna, aga sa pead

613
00:25:47,399 --> 00:25:50,330
vt lk komplekt 5 me vaid ravi
umbes tähed ja ülakomad.

614
00:25:50,330 --> 00:25:52,990
>> Ja siis kuidas te esindate
andmestruktuur ise?

615
00:25:52,990 --> 00:25:56,454
Kuidas esindavad juur
Selle Prefiksipuu niiöelda?

616
00:25:56,454 --> 00:25:59,620
Noh, lihtsalt meeldib koos seotud nimekirja, siis
vaja viit esimese osaga.

617
00:25:59,620 --> 00:26:04,270
Mis Prefiksipuu sa lihtsalt vaja üks
kursor root selle Prefiksipuu.

618
00:26:04,270 --> 00:26:07,290
Ja sealt saab hash
teed alla sügavamale ja sügavamale

619
00:26:07,290 --> 00:26:10,460
iga teise sõlme struktuuri.

620
00:26:10,460 --> 00:26:13,440
Nii lihtsalt selle saab
me esindame, et struktuure.

621
00:26:13,440 --> 00:26:15,877
>> Nüüd Meanwhile-- Oh küsimus.

622
00:26:15,877 --> 00:26:17,220
>> Sihtrühm: Mis bool sõna?

623
00:26:17,220 --> 00:26:20,490
>> DAVID Humala: Bool sõna
just see C kehastus

624
00:26:20,490 --> 00:26:22,920
mida ma kirjeldasin
Selles lahtris siin, kui

625
00:26:22,920 --> 00:26:26,000
Hakkasin jagades iga
massiivi elemente kaks tükki.

626
00:26:26,000 --> 00:26:27,600
Üks on viit järgmise sõlme.

627
00:26:27,600 --> 00:26:30,280
Muud peab olema
midagi ruut

628
00:26:30,280 --> 00:26:33,770
öelda jah, seal on
Sõna Daven mis lõpeb siin,

629
00:26:33,770 --> 00:26:35,610
sest me ei taha,
hetkel, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Kuigi Dave saab olema
õigustatud sõna, ta ei Prefiksipuu

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

632
00:26:39,830 --> 00:26:40,950
Ja D ei ole sõna.

633
00:26:40,950 --> 00:26:42,770
Ja D-ei ole sõna või nimi.

634
00:26:42,770 --> 00:26:45,020
Nii linnuke
näitab alles siis, kui

635
00:26:45,020 --> 00:26:48,190
tabanud see sõlm on
Eelmise tee tähemärki

636
00:26:48,190 --> 00:26:50,700
tegelikult string et olete sisestanud.

637
00:26:50,700 --> 00:26:53,660
Nii et kõik bool
seal teeb meile.

638
00:26:53,660 --> 00:26:55,500
>> Muid küsimustele proovib?

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

640
00:26:56,215 --> 00:26:58,035
>> Sihtrühm: Mis on kattuvad?

641
00:26:58,035 --> 00:26:59,945
Mida teha, kui teil on Dave ja Daven?

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

643
00:27:00,820 --> 00:27:02,580
Mida teha, kui teil on Dave ja Daven?

644
00:27:02,580 --> 00:27:06,240
Nii et kui me lisada, ütleme hüüdnimi
jaoks David-- Dave-- D--V-E?

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

646
00:27:07,370 --> 00:27:08,700
See on tegelikult super lihtne.

647
00:27:08,700 --> 00:27:10,325
Nii et me ainult kavatse võtta neljast etapist.

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

649
00:27:11,042 --> 00:27:15,847
D--V-E. Ja mida ma pean
teha, kui ma tabanud, et neljanda sõlme?

650
00:27:15,847 --> 00:27:16,680
Just kavatse vaadata.

651
00:27:16,680 --> 00:27:18,000
Oleme juba hea minna.

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

653
00:27:18,840 --> 00:27:19,750
Neli sammu.

654
00:27:19,750 --> 00:27:21,590
Pidev aja asymptotically.

655
00:27:21,590 --> 00:27:26,300
Ja nüüd me oleme näidanud, et nii Dave
ja Daven on stringid struktuuris.

656
00:27:26,300 --> 00:27:27,710
Niisiis ei ole probleem.

657
00:27:27,710 --> 00:27:30,200
Ja pange tähele, kuidas kohalolek
kohta Daven ei pääsenud

658
00:27:30,200 --> 00:27:34,750
võtab rohkem aega või vähem
aeg Dave ja vastupidi.

659
00:27:34,750 --> 00:27:36,000
>> Niisiis, mida me saame nüüd teha?

660
00:27:36,000 --> 00:27:40,680
Oleme kasutanud seda metafoori enne
plaate esindavad midagi.

661
00:27:40,680 --> 00:27:43,380
Aga selgub, et
virna on tegelikult

662
00:27:43,380 --> 00:27:47,187
demonstratiivne teise abstraktsete andmete
liik-- kõrgem andmestruktuur

663
00:27:47,187 --> 00:27:49,770
et lõpus päeval on lihtsalt
nagu massiivi või seotud nimekirja

664
00:27:49,770 --> 00:27:50,970
või midagi rohkem Ilmalik.

665
00:27:50,970 --> 00:27:53,270
Aga see on huvitav
kontseptuaalne mõiste.

666
00:27:53,270 --> 00:27:56,440
Stack, nagu need
salved siin Mather,

667
00:27:56,440 --> 00:27:58,750
nimetatakse üldiselt
lihtsalt selle-- virna.

668
00:27:58,750 --> 00:28:02,540
>> Ja seda tüüpi andmestruktuuri
Teil on kaks operations--

669
00:28:02,540 --> 00:28:05,880
teil on üks nn push
lisades midagi virna,

670
00:28:05,880 --> 00:28:08,320
justkui teise salve
tagasi magasini tippu.

671
00:28:08,320 --> 00:28:11,350
Ja siis pop, mis tähendab, et sa
võtta tähtsaim salve välja.

672
00:28:11,350 --> 00:28:16,210
Aga mis peamine kohta virna, et
see ju see kummaline omadus.

673
00:28:16,210 --> 00:28:19,560
Kuna söögisaal töötajad
ümberkorraldamine salved järgmise toidukorra,

674
00:28:19,560 --> 00:28:21,380
mis saab olema
tõsi, kuidas õpilased

675
00:28:21,380 --> 00:28:22,856
suhelda andmete struktuur?

676
00:28:22,856 --> 00:28:24,480
Sihtrühm: Nad lähevad pop ühekordne.

677
00:28:24,480 --> 00:28:26,550
DAVID Humala: Nad lähed
pop ühekordne loodetavasti tippu.

678
00:28:26,550 --> 00:28:28,910
Muidu on see lihtsalt tobe
minna kõik viis põhja.

679
00:28:28,910 --> 00:28:29,070
Õigus?

680
00:28:29,070 --> 00:28:31,620
Andmete struktuur ei võimalda hästi
teil haarata põhja salve vähemalt

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

682
00:28:32,520 --> 00:28:35,040
Nii et see on uudishimulik
vara korstnat

683
00:28:35,040 --> 00:28:39,730
et viimane element on
saab olema esimene välja.

684
00:28:39,730 --> 00:28:43,400
Ja arvuti teadlased nimetavad
Selle LIFO-- kesta sisse, esimesena välja.

685
00:28:43,400 --> 00:28:45,540
Ja tegelikult ei ole
huvitavaid rakendusi.

686
00:28:45,540 --> 00:28:50,090
See ei ole tingimata nii ilmne, nagu mõned
teised, kuid see võib tõepoolest olla kasulik,

687
00:28:50,090 --> 00:28:54,040
ja see võib tõepoolest ellu
paari erinevalt.

688
00:28:54,040 --> 00:28:58,550
>> Nii et üks, ja tegelikult, las
mulle ei sukelduda seda.

689
00:28:58,550 --> 00:28:59,860
Teeme selle asemel.

690
00:28:59,860 --> 00:29:03,700
Vaatame üks, mis on peaaegu
Sama mõte, aga see on natuke õiglasem.

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

692
00:29:04,200 --> 00:29:07,560
Kui sa oled üks neist fänn poisid või
tüdrukud, mis tõesti meeldib Apple tooted

693
00:29:07,560 --> 00:29:10,130
ja sa ärkasin kell 03:00
rivistama teatud kauplus

694
00:29:10,130 --> 00:29:14,150
saada uusimaid iPhone, siis
oleks sabas kuni niimoodi.

695
00:29:14,150 --> 00:29:15,800
>> Nüüd järjekord on väga teadlikult nimega.

696
00:29:15,800 --> 00:29:18,190
See on joon, sest seal on
mõned õiglus ta.

697
00:29:18,190 --> 00:29:18,690
Õigus?

698
00:29:18,690 --> 00:29:21,690
Oleks selline imeda kui olete
sain seal esmalt Apple Store

699
00:29:21,690 --> 00:29:25,700
aga sa oled tegelikult kõige alumine
salve, sest Apple töötajad siis

700
00:29:25,700 --> 00:29:28,189
pop viimane inimene, kes
tegelikult sain kooskõlas.

701
00:29:28,189 --> 00:29:31,230
Nii korstnad ja järjekorrad, kuigi
funktsionaalselt nad omamoodi same--

702
00:29:31,230 --> 00:29:33,105
see on lihtsalt selle kollektsiooni
ressursse, mis on

703
00:29:33,105 --> 00:29:36,210
läheb kasvama ja shrink-- seal
see õigluse aspekt see,

704
00:29:36,210 --> 00:29:39,634
vähemalt reaalses maailmas,
kus tegevuse treenite

705
00:29:39,634 --> 00:29:40,800
on täiesti erinevad.

706
00:29:40,800 --> 00:29:43,360
Stack-- järjekorda
rather-- ütles, et on

707
00:29:43,360 --> 00:29:45,320
kaks operatsiooni: n järjekorda ja d järjekorda.

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

709
00:29:46,341 --> 00:29:48,090
Või võite helistada neile
mis tahes mitmeid asju.

710
00:29:48,090 --> 00:29:50,770
Aga sa lihtsalt tahad lüüa
arusaam, et üks on lisades

711
00:29:50,770 --> 00:29:53,230
ja üks on lõpuks lahutada.

712
00:29:53,230 --> 00:29:58,840
>> Nüüd all kapuuts, nii korstnat
ja järjekord võiks rakendada siis kuidas?

713
00:29:58,840 --> 00:30:01,390
Me ei hakka koodi
sest kõrgema

714
00:30:01,390 --> 00:30:03,387
Idee on omamoodi ilmsem.

715
00:30:03,387 --> 00:30:04,470
Ma mõtlen, mida inimesed teevad?

716
00:30:04,470 --> 00:30:07,030
Kui ma olen esimene inimene, kes on Apple
Hoidke ja see on välisuks,

717
00:30:07,030 --> 00:30:08,130
tead, ma lähen siin seista.

718
00:30:08,130 --> 00:30:09,750
Ja järgmine isiku
läheb siin seista.

719
00:30:09,750 --> 00:30:11,500
Ja järgmine isiku
läheb siin seista.

720
00:30:11,500 --> 00:30:13,792
Mida andmestruktuur
sobiv järjekord?

721
00:30:13,792 --> 00:30:14,542
>> Sihtrühm: järjekorda.

722
00:30:14,542 --> 00:30:15,667
DAVID Humala: Noh, järjekorda.

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

724
00:30:16,390 --> 00:30:16,920
Mida veel?

725
00:30:16,920 --> 00:30:17,600
>> Sihtrühm: seotud nimekirja.

726
00:30:17,600 --> 00:30:18,990
>> DAVID Humala: seotud
nimekiri, mida võiks rakendada.

727
00:30:18,990 --> 00:30:22,500
Ja ahelloend on tore, sest siis
see võib kasvada meelevaldselt pika erinevalt

728
00:30:22,500 --> 00:30:24,880
võttes teatud fikseeritud number
inimesed poest.

729
00:30:24,880 --> 00:30:27,030
Aga võib-olla fikseeritud arv
kohti on õigustatud.

730
00:30:27,030 --> 00:30:30,350
Sest kui nad ainult nagu 20
iPhone'i esimesel päeval, võibolla

731
00:30:30,350 --> 00:30:33,930
nad on vaja ainult massiivi suurus
20 esindamiseks et järjekorda, mis

732
00:30:33,930 --> 00:30:37,070
ainult öelda nüüd, kui hakkame rääkima
nendest kõrgema taseme probleemid,

733
00:30:37,070 --> 00:30:38,890
saab seda rakendada
igal mitmel viisil.

734
00:30:38,890 --> 00:30:42,030
Ja seal on ilmselt lihtsalt läheb
olema kompromiss ajas ja ruumis

735
00:30:42,030 --> 00:30:43,950
või ainult oma koodi keerukust.

736
00:30:43,950 --> 00:30:45,380
>> Aga pakk?

737
00:30:45,380 --> 00:30:48,190
Noh, korstna, oleme näinud liiga
võib olla lihtsalt nende plaate.

738
00:30:48,190 --> 00:30:50,007
Ja siis võiks rakendada seda massiivi.

739
00:30:50,007 --> 00:30:53,090
Aga mingil hetkel, kui kasutad massiiv,
mis juhtub, et salved

740
00:30:53,090 --> 00:30:54,173
üritate panema?

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

742
00:30:55,170 --> 00:30:55,670
Hea küll.

743
00:30:55,670 --> 00:30:57,490
Sa oled ainult kavatse
oleks võimalik minna nii kõrge.

744
00:30:57,490 --> 00:31:00,156
Ja ma arvan, et Mather nad
tegelikult süvistatakse et avamist.

745
00:31:00,156 --> 00:31:01,950
Nii et tõesti, see on peaaegu
nagu Ema kasutab

746
00:31:01,950 --> 00:31:03,783
massiivi fikseeritud suurus,
sest saab ainult

747
00:31:03,783 --> 00:31:08,302
mahub nii palju plaate, et avamine
seina allapoole inimeste põlvi.

748
00:31:08,302 --> 00:31:10,010
Ja nii, et oleks
Öeldakse, massiiv,

749
00:31:10,010 --> 00:31:14,300
aga me võiksime kindlasti rakendada, et
üldisemalt seotud nimekirja.

750
00:31:14,300 --> 00:31:16,390
>> Noh, mida veel umbes andmestruktuur?

751
00:31:16,390 --> 00:31:18,760
Lubage mul tõmba üks muu visuaalse siin.

752
00:31:18,760 --> 00:31:24,710
Midagi kuidas see siin?

753
00:31:24,710 --> 00:31:28,920
Miks võib see olla kasulik pole
midagi nii väljamõeldud kui Prefiksipuu, mis

754
00:31:28,920 --> 00:31:32,370
me nägime oli neid väga palju tippe,
millest igaüks on massiivi?

755
00:31:32,370 --> 00:31:35,740
Aga mis siis, kui me teeme midagi
lihtsalt, nagu vana kooli sugupuu

756
00:31:35,740 --> 00:31:38,110
Iga mille sõlmed siin
lihtsalt ladustamiseks number.

757
00:31:38,110 --> 00:31:42,180
Selle asemel, et nime või järeltulija
lihtsalt ladustamiseks number niimoodi.

758
00:31:42,180 --> 00:31:45,250
>> Noh, kõnepruuki me kasutame
andmestruktuurid on nii üritab

759
00:31:45,250 --> 00:31:49,510
ja puud, kus Prefiksipuu on jällegi
vaid üks, mille tipud on massiivid

760
00:31:49,510 --> 00:31:51,680
on ikka see, mida sa võiksid
kasutada alates algkool

761
00:31:51,680 --> 00:31:53,860
kui sa tegid perekond
tree-- lehed ja juur

762
00:31:53,860 --> 00:31:57,250
puu ja lapsed
vanem ja õdede-vendade hulgast.

763
00:31:57,250 --> 00:32:03,670
Ja me võiksime rakendada puu,
Näiteks, kui lihtsalt see.

764
00:32:03,670 --> 00:32:07,420
Puu, kui seda sõlme, üks
need ringid, mis on mitu,

765
00:32:07,420 --> 00:32:09,947
ta ei kavatse olla
üks pointer, vaid kaks.

766
00:32:09,947 --> 00:32:11,780
Ja niipea, kui lisate
teine ​​osuti, siis

767
00:32:11,780 --> 00:32:13,905
võib tegelikult nüüd tegema omamoodi
kahemõõtmeline andmed

768
00:32:13,905 --> 00:32:14,780
struktuuride mälu.

769
00:32:14,780 --> 00:32:16,660
Palju nagu kahemõõtmeline
massiiv, saate

770
00:32:16,660 --> 00:32:18,904
on omamoodi kahemõõtmeline
ahelloendid kuid need

771
00:32:18,904 --> 00:32:20,820
et järgida muster
kus pole tsüklit.

772
00:32:20,820 --> 00:32:24,487
See on tõeliselt puu ühe
vanavanem, kuidas siia üles ja siis

773
00:32:24,487 --> 00:32:27,320
mõned vanemad ja lapsed ja
lapselapsed ja lapse-lapselast.

774
00:32:27,320 --> 00:32:28,370
ja nii edasi.

775
00:32:28,370 --> 00:32:32,390
>> Aga mis on tegelikult puhas sellest ka,
lihtsalt kiusa natuke koodi

776
00:32:32,390 --> 00:32:35,370
tagasikutsumise recursion alates
mõnda aega tagasi, kusjuures

777
00:32:35,370 --> 00:32:38,220
Sa kirjutad funktsioon, mis nimetab ennast.

778
00:32:38,220 --> 00:32:41,140
See on ilus võimalus
rakendada midagi

779
00:32:41,140 --> 00:32:42,920
nagu recursion, sest pean seda.

780
00:32:42,920 --> 00:32:43,860
>> See on puu.

781
00:32:43,860 --> 00:32:48,040
Ja ma olen olnud veidi anal, kuidas
Panin täisarvud tänavale.

782
00:32:48,040 --> 00:32:51,020
Nii palju, et see on eriline
name-- kahendotsingupuu.

783
00:32:51,020 --> 00:32:53,460
Nüüd oleme kuulnud binaarne
otsida, kuid sa saad

784
00:32:53,460 --> 00:32:55,180
tööle tagasi selle asja nimi on?

785
00:32:55,180 --> 00:32:59,280
Mis on muster, kuidas ma
sisestatud täisarvud sellesse puu?

786
00:32:59,280 --> 00:33:00,696
See ei ole meelevaldne.

787
00:33:00,696 --> 00:33:01,570
Seal on mõned muster.

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

789
00:33:02,090 --> 00:33:03,370
>> Sihtrühm: Väiksemad vasakul.

790
00:33:03,370 --> 00:33:03,690
>> DAVID Humala: Jah.

791
00:33:03,690 --> 00:33:05,062
Väiksemad on vasakul.

792
00:33:05,062 --> 00:33:06,270
Suuremad neist on paremal.

793
00:33:06,270 --> 00:33:12,940
Selline, et õige väide on
vanem on suurem kui vasaku laps,

794
00:33:12,940 --> 00:33:14,850
kuid vähem kui selle õige laps.

795
00:33:14,850 --> 00:33:17,750
Ja et üksi on isegi
rekursiivne verbaalne definitsioon

796
00:33:17,750 --> 00:33:20,500
sest võite taotleda, et
Sama loogika, et iga sõlme

797
00:33:20,500 --> 00:33:23,080
ja see ainult põhjad
välja, tugipunkti, kui te

798
00:33:23,080 --> 00:33:25,740
hakkab, kui vajutad üks
lehed, nii et rääkida,

799
00:33:25,740 --> 00:33:28,580
kui puhkust ei ole lapsi veelgi.

800
00:33:28,580 --> 00:33:30,614
>> Nüüd, kuidas võiks leida number 44?

801
00:33:30,614 --> 00:33:32,280
Sa hakkaks keskmes ja öelda, hm.

802
00:33:32,280 --> 00:33:35,690
55 ei ole 44 Nii et ma tahan minna
õige või ma tahan minna vasakule?

803
00:33:35,690 --> 00:33:37,190
Noh, ilmselt sa tahad minna vasakule.

804
00:33:37,190 --> 00:33:40,060
Ja nii see on nagu telefon
raamat näiteks binaarne otsing

805
00:33:40,060 --> 00:33:41,099
üldisemalt.

806
00:33:41,099 --> 00:33:43,390
Aga me selle rakendamiseks
Nüüd veidi dünaamiliselt

807
00:33:43,390 --> 00:33:45,339
kui massiivi võib lubada.

808
00:33:45,339 --> 00:33:48,130
Ja tegelikult, kui soovite otsida
kell kood esmapilgul kindel.

809
00:33:48,130 --> 00:33:49,671
Tundub, et terve hunnik ridu.

810
00:33:49,671 --> 00:33:51,220
Aga see on ilusti lihtne.

811
00:33:51,220 --> 00:33:54,490
Kui soovite rakendada funktsioon
nimetatakse otsingumootori kelle eesmärk elus

812
00:33:54,490 --> 00:33:57,290
on otsida väärtus
nagu n, täisarv

813
00:33:57,290 --> 00:34:01,756
ja sa oled sooritanud ühe pointer--
kursor sõlme juured,

814
00:34:01,756 --> 00:34:04,380
pigem selle puu, millest
pääsete kõik muu,

815
00:34:04,380 --> 00:34:08,850
märgata, kuidas arusaadav
saab rakendada loogikat.

816
00:34:08,850 --> 00:34:10,880
Kui puu on null,
ilmselt see ei ole seal.

817
00:34:10,880 --> 00:34:11,880
Lähme lihtsalt tagasi vale.

818
00:34:11,880 --> 00:34:12,000
Õigus?

819
00:34:12,000 --> 00:34:14,040
Kui sa käe ta midagi,
seal on midagi seal.

820
00:34:14,040 --> 00:34:17,900
>> Muud, kui n on alla
puu nool n-- nüüd nool n,

821
00:34:17,900 --> 00:34:20,670
meenutada tutvustasime super
lühidalt mõni päev tagasi,

822
00:34:20,670 --> 00:34:25,100
ja see tähendab lihtsalt de-viide
pointer ja vaadata Väli n.

823
00:34:25,100 --> 00:34:27,690
Nii et see tähendab, minna ja
vaadata Väli n.

824
00:34:27,690 --> 00:34:33,810
Nii et kui n väärtus olete andnud, on vähem
kui väärtus on puud täisarv,

825
00:34:33,810 --> 00:34:35,449
kus sa tahad minna?

826
00:34:35,449 --> 00:34:36,389
Vasakule.

827
00:34:36,389 --> 00:34:37,780
>> Nii märkate recursion.

828
00:34:37,780 --> 00:34:39,860
Ma returning-- ole tõsi.

829
00:34:39,860 --> 00:34:40,989
Ei ole vale.

830
00:34:40,989 --> 00:34:45,670
Ma naasmist iganes vastus
on kõne ise, mis kulgeb

831
00:34:45,670 --> 00:34:50,100
n uuesti, mis on koondatud,
kuid milline on veidi erinev nüüd?

832
00:34:50,100 --> 00:34:51,989
Kuidas ma muutes probleem väiksem?

833
00:34:51,989 --> 00:34:54,920
Ma möödaminnes kui teine
argument, mitte puu juur,

834
00:34:54,920 --> 00:34:59,616
kuid vasakul lapse käesolevas asjas.

835
00:34:59,616 --> 00:35:00,990
Nii et ma olen kulgeb vasakult laps.

836
00:35:00,990 --> 00:35:04,720
>> Vahepeal, kui n on suurem kui
sõlme Ma olen praegu vaadates,

837
00:35:04,720 --> 00:35:06,690
Ma otsin löögile.

838
00:35:06,690 --> 00:35:10,880
Else, kui puu ei ole null, ja
kui element on mitte vasakul

839
00:35:10,880 --> 00:35:13,240
ja see ei ole õigust,
mis on imeliselt puhul?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Me oleme tegelikult leidnud sõlme
küsimus, ja nii me tagasi tõsi.

842
00:35:18,440 --> 00:35:21,490
>> Nii oleme lihtsalt kriimustatud pinda
nüüd mõned neist andmestruktuuride.

843
00:35:21,490 --> 00:35:24,370
In probleem seatud viie saate
uurida neid veelgi,

844
00:35:24,370 --> 00:35:27,250
ja antakse teile oma disaini
otsustada, kuidas edasi minna.

845
00:35:27,250 --> 00:35:30,250
Mida ma tahaksin teha järeldusi
on vaid 30-sekundiline teaser

846
00:35:30,250 --> 00:35:32,080
mis ootab järgmisel nädalal ja pärast seda.

847
00:35:32,080 --> 00:35:35,390
>> Nagu me begin-- õnneks võite
think-- meie üleminek aeglaselt

848
00:35:35,390 --> 00:35:38,680
maailmast C ja madalam
tasandil rakendamise üksikasju,

849
00:35:38,680 --> 00:35:42,090
et maailmas, kus me saame võtta
anda, et keegi on lõpuks

850
00:35:42,090 --> 00:35:44,010
rakendatakse neid andmeid
struktuuride meile

851
00:35:44,010 --> 00:35:47,570
ja hakkame mõistma
Reaalses maailmas rakendusaktidega

852
00:35:47,570 --> 00:35:50,560
veebipõhiste programmidega ja
veebilehed üldisemalt

853
00:35:50,560 --> 00:35:52,910
ja ka väga julgeolek
mõju, et me oleme ainult

854
00:35:52,910 --> 00:35:54,850
hakanud pinnapealselt.

855
00:35:54,850 --> 00:35:57,320
Siin on, mida ootab meid
päevil tulla.

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
>> -Ta Tuli teade,
koos protokolliga kõik omal.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Ta tuli maailma julm
tulemüürid uncaring ruuterid

861
00:36:30,894 --> 00:36:33,368
ja ohte palju hullem kui surm.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Ta on kiire.

864
00:36:36,236 --> 00:36:37,980
Ta on tugev.

865
00:36:37,980 --> 00:36:42,830
Ta on TCP / IP, ja tal on oma aadress.

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 Humala: Tulevad järgmisel nädalal.

870
00:36:50,910 --> 00:36:51,880
Me näeme siis.

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
-Ja Nüüd, "Deep Mõtted"
poolt Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Algab alati
loengud, "Olgu."

876
00:37:05,820 --> 00:37:08,750
Miks mitte, "Siin on lahendus
selle nädala probleem komplekt "

877
00:37:08,750 --> 00:37:12,180
või "Me anname teile kõigile?"

878
00:37:12,180 --> 00:37:13,380
[Naerab]

879
00:37:13,380 --> 00:37:15,530
[END VIDEO PLAYBACK]