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

2
00:00:00,500 --> 00:00:03,340
[MUZIKO Ludante]

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

4
00:00:11,020 --> 00:00:14,010
>> DAVID Malan: Jen CS50.

5
00:00:14,010 --> 00:00:18,090
Kaj ĉi tiu estas la komenco kaj la
end-- kiel literally-- preskaŭ la fino

6
00:00:18,090 --> 00:00:18,825
de semajno ses.

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

8
00:00:20,030 --> 00:00:22,640
>> Mi pensis, ke mi volonte dividas
iom de amuza fakto.

9
00:00:22,640 --> 00:00:25,370
Mi tiris ĉi supre de
pasinta semestro la datuma aro.

10
00:00:25,370 --> 00:00:29,710
Vi eble memoras, ke ni demandos al vi pri ĉiu
p aro formo se vi spektis linio

11
00:00:29,710 --> 00:00:31,580
aŭ se vi jam ĉeestis en persono.

12
00:00:31,580 --> 00:00:33,020
Kaj jen la datumoj.

13
00:00:33,020 --> 00:00:34,710
Do hodiaŭ estis tre antaŭvideblaj.

14
00:00:34,710 --> 00:00:37,126
Sed ni volis elspezi iom
el tempo kun vi malgraŭ tio.

15
00:00:37,126 --> 00:00:40,599
Ĉu iu ŝatus konjekti kial ĉi
grafeo estas tiel jaggy, supren malsupren, supren malsupren,

16
00:00:40,599 --> 00:00:41,265
tiel konsekvence?

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

18
00:00:42,980 --> 00:00:45,130
Kion do ĉiu el la bekoj
kaj trogojn reprezentas?

19
00:00:45,130 --> 00:00:46,005
>> Publiko: [inaudible]

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

21
00:00:47,002 --> 00:00:47,835
DAVID Malan: Efektive.

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

23
00:00:50,900 --> 00:00:55,480
Kaj pli amuze, dio malpermesu,
ni tenu unu prelego en vendredo

24
00:00:55,480 --> 00:00:58,960
komence de la semestro,
ke estas kion ni vidas okazi.

25
00:00:58,960 --> 00:01:03,430
Do hodiaŭ ni partoprenas en iom
pli pri datumstrukturoj.

26
00:01:03,430 --> 00:01:06,660
Kaj doni al vi pli solida
mensa modelo por problemoj en kvin,

27
00:01:06,660 --> 00:01:07,450
kio estas nun ekster.

28
00:01:07,450 --> 00:01:10,817
Fuŝo, kiun, ni
protektu vin tekstdosiero iuj 100.000

29
00:01:10,817 --> 00:01:12,650
plus anglaj vortoj, kaj
vi tuj havos

30
00:01:12,650 --> 00:01:17,770
elkompreni kiel lerte ŝarĝi ilin
en memoro, en RAM, uzante iuj datumoj

31
00:01:17,770 --> 00:01:19,330
strukturo de via elekto.

32
00:01:19,330 --> 00:01:22,470
>> Nun unu tia datumstrukturo povis
esti, sed probable ne devus esti,

33
00:01:22,470 --> 00:01:25,630
la sufiĉe simplista ligillisto,
kiun ni enkondukis lastan fojon.

34
00:01:25,630 --> 00:01:29,220
Kaj ligillisto havis almenaŭ
unu avantaĝon super tabelo.

35
00:01:29,220 --> 00:01:32,096
Kio estas unu avantaĝon
lerta kunligita defendeble?

36
00:01:32,096 --> 00:01:32,950
>> Publiko: 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
Kion vi volas diri per tio?

40
00:01:35,196 --> 00:01:37,872
>> Publiko: Anywhere kune
la listo [inaudible].

41
00:01:37,872 --> 00:01:38,770
>> DAVID Malan: Bone.

42
00:01:38,770 --> 00:01:42,090
Do vi povas enigi ero kien
vi deziras en la mezo de la listo

43
00:01:42,090 --> 00:01:45,490
sen devi barajar ion,
kiun ni konkludis, en nia ordigado

44
00:01:45,490 --> 00:01:47,630
diskutoj, estas ne
nepre estas bona afero,

45
00:01:47,630 --> 00:01:51,200
ĉar ĝi prenas tempon por fakte movas
ĉiuj tiuj homoj maldekstra aŭ dekstra.

46
00:01:51,200 --> 00:01:55,540
Kaj tial kun ligillisto, vi povas
simple malŝparas kun malloc, nova nodo,

47
00:01:55,540 --> 00:01:58,385
kaj tiam ĝisdatigi kelkaj
pointers-- du, tri operacioj max--

48
00:01:58,385 --> 00:02:01,480
kaj ni povis slot iu
en ie en listo.

49
00:02:01,480 --> 00:02:03,550
>> Kion plu estis avantaĝa
pri ligillisto?

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
>> Publiko: [inaudible]

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

54
00:02:07,538 --> 00:02:08,413
DAVID Malan: Perfekta.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
Perfekta.

57
00:02:11,090 --> 00:02:12,070
Estas vere dinamika.

58
00:02:12,070 --> 00:02:15,100
Kaj ke vi ne faras,
anticipe al iu fiksa grandeco

59
00:02:15,100 --> 00:02:18,750
eron de memoro, kiel vi devus
al kun tabelo, la inversa de kio

60
00:02:18,750 --> 00:02:22,455
estas ke vi povas atribui nodoj nur sur
peto tiel uzante nur tiom da spaco

61
00:02:22,455 --> 00:02:23,330
kiel vi vere bezonas.

62
00:02:23,330 --> 00:02:26,830
Kontraste kun tabelo, eble vi
hazarde atribui tro malmulte.

63
00:02:26,830 --> 00:02:28,871
Kaj tiam ĝi estas ĝuste iri
esti doloro en la kolo

64
00:02:28,871 --> 00:02:32,440
al reallocate nova pli granda tabelo, kopiu
ĉio finiĝis, liberigi la malnovan tabelon,

65
00:02:32,440 --> 00:02:33,990
kaj tiam movi pri via negoco.

66
00:02:33,990 --> 00:02:37,479
Aŭ pli malbone, vi povus atribui vojo
pli memoro ol vi fakte bezonas,

67
00:02:37,479 --> 00:02:40,520
kaj tial vi estas iranta havi tre
maldense loĝatajn tabelo, por tiel diri.

68
00:02:40,520 --> 00:02:44,350
>> Do ligillisto donas tiujn
avantagxoj de dinamismo kaj fleksebleco

69
00:02:44,350 --> 00:02:46,080
kun inserciones kaj forigoj.

70
00:02:46,080 --> 00:02:48,000
Sed certe devas esti prezo pagita.

71
00:02:48,000 --> 00:02:50,000
Fakte, unu el la temoj
esploris en kvizo nulo

72
00:02:50,000 --> 00:02:52,430
Estis paro de la komerco-offs
ni vidis ĝis nun.

73
00:02:52,430 --> 00:02:56,161
Do kio estas prezo pagita aŭ
Downside de ligillisto?

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

75
00:02:56,660 --> 00:02:57,560
>> Publiko: Neniu hazarda aliro.

76
00:02:57,560 --> 00:02:58,809
>> DAVID Malan: Neniu hazarda aliro.

77
00:02:58,809 --> 00:02:59,540
Sed kiu zorgas?

78
00:02:59,540 --> 00:03:01,546
Hazarda aliro ne sonas konvinka.

79
00:03:01,546 --> 00:03:02,421
>> Publiko: [inaudible]

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

81
00:03:04,865 --> 00:03:05,740
DAVID Malan: Ĝuste.

82
00:03:05,740 --> 00:03:07,580
Se vi volas havi
iu algorithm--

83
00:03:07,580 --> 00:03:10,170
kaj mi efektive proponas
duuma serĉo en aparta, kiu

84
00:03:10,170 --> 00:03:12,600
Estas unu ni uzas tute bit--
Se vi ne havas aliro aleatorio,

85
00:03:12,600 --> 00:03:15,516
vi ne povas fari tion simpla aritmetiko
trovi kiel la meza ero

86
00:03:15,516 --> 00:03:16,530
kaj saltante rajton gxin.

87
00:03:16,530 --> 00:03:20,239
Vi anstataŭe devas starti je la unua
elemento kaj lineare serĉo de maldekstra

88
00:03:20,239 --> 00:03:22,780
dekstren, se vi volas trovi
meze aŭ ajna alia elemento.

89
00:03:22,780 --> 00:03:24,410
>> Publikon: ĝi probable bezonas pli memoro.

90
00:03:24,410 --> 00:03:25,040
>> DAVID Malan: Takes pli memoro.

91
00:03:25,040 --> 00:03:27,464
Kie estas tiu aldona
kostas devenante en memoro?

92
00:03:27,464 --> 00:03:28,339
>> Publiko: [inaudible]

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

94
00:03:32,566 --> 00:03:33,440
DAVID Malan: Ĝuste.

95
00:03:33,440 --> 00:03:35,679
En tiu kazo tie, ni devis
kunligita listo por entjeroj,

96
00:03:35,679 --> 00:03:37,470
kaj tamen ni estas duobliganta
la kvanto de memoro

97
00:03:37,470 --> 00:03:39,680
ni bezonas por la ankaŭ stoki tiuj punteros.

98
00:03:39,680 --> 00:03:42,090
Nun malpli granda negoco kiel
via structs akiri pli grandaj

99
00:03:42,090 --> 00:03:45,320
kaj vi stoki ne nombro sed
eble studento aŭ alian objekton.

100
00:03:45,320 --> 00:03:46,880
Sed la punkto certe restas.

101
00:03:46,880 --> 00:03:49,421
Kaj tiel multaj el la operacioj
en ligitaj lertaj vokitaj

102
00:03:49,421 --> 00:03:50,570
estis granda a de n-- lineara.

103
00:03:50,570 --> 00:03:54,730
Aĵoj kiel inserción aŭ serĉo
aŭ viŝita en kazo ero

104
00:03:54,730 --> 00:03:57,720
pasis al esti ĉe la fino de
la listo ĉu ĝi estas ordo aŭ ne.

105
00:03:57,720 --> 00:04:01,167
>> Foje vi povus akiri bonŝanca kaj en
tiel malaltaj baroj sur tiuj operacioj

106
00:04:01,167 --> 00:04:04,250
povus ankaŭ esti konstanta tempo se vi estas
ĉiam rigardante la unua elemento,

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

108
00:04:05,070 --> 00:04:09,360
Sed fine, ni promesis
atingi la Holy Grail

109
00:04:09,360 --> 00:04:12,630
de datumstrukturoj, aŭ
iuj alproksimiĝo gxiajn

110
00:04:12,630 --> 00:04:14,290
pere de konstanta tempo.

111
00:04:14,290 --> 00:04:17,579
Povas trovi elementojn aŭ aldoni elementojn
aŭ forigi elementojn el listo?

112
00:04:17,579 --> 00:04:19,059
Ni vidos tute frue.

113
00:04:19,059 --> 00:04:21,100
Kaj ĝi rezultas ke unu
de la mekanismojn ni

114
00:04:21,100 --> 00:04:23,464
tuj ekuzas hodiaŭ,
jara uzo en p starigis kvin,

115
00:04:23,464 --> 00:04:24,630
Estas vere bela familiara.

116
00:04:24,630 --> 00:04:27,430
Ekzemple, se tiu estas faskon
de ekzameno libroj, ĉiu el kiuj

117
00:04:27,430 --> 00:04:29,660
havas studentan unua
Nomo kaj familinomo en ĝi,

118
00:04:29,660 --> 00:04:31,820
kaj mi kaptas ilin el
ĉe la fino de iu ekzameno,

119
00:04:31,820 --> 00:04:33,746
kaj ili ĉiuj estas belaj
multe en hazarda ordo,

120
00:04:33,746 --> 00:04:36,370
kaj ni volas iri de ordiga
tiujn ekzamenojn por ke fojo gradita

121
00:04:36,370 --> 00:04:38,661
estas nur multe pli facila kaj
rapida transdoni ilin el

122
00:04:38,661 --> 00:04:40,030
por lernantoj alfabete.

123
00:04:40,030 --> 00:04:42,770
Kia estus via instinktoj esti
por amaso de ekzamenoj tiel?

124
00:04:42,770 --> 00:04:45,019
>> Nu, se vi estas kiel mi, vi
povus vidi ke tiu estas m,

125
00:04:45,019 --> 00:04:48,505
tial Mi iras al ia meti tiu enen,
Se ĉi tiu estas mia tablo aŭ mia garbejo kie

126
00:04:48,505 --> 00:04:50,650
Mi etendis tion
out-- aŭ mia tabelo really--

127
00:04:50,650 --> 00:04:52,210
Mi povus meti ĉiuj m tien.

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

129
00:04:52,710 --> 00:04:55,020
Jen A. Do mi povus
metis la mezuro super tie.

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

131
00:04:55,520 --> 00:04:57,980
Jen alia A. Mi iras
meti tiun ĉi tien.

132
00:04:57,980 --> 00:05:02,490
Jen Z. Jen alia M. Kaj tiel
Mi povus komenci farante aretojn kiel ĉi.

133
00:05:02,490 --> 00:05:06,620
Kaj tiam eble mi irus en postaj
kaj ia tre nitpicky-tas speco

134
00:05:06,620 --> 00:05:07,710
la individuo aretoj.

135
00:05:07,710 --> 00:05:11,300
Sed la punkto estas mi aspektus
ĉe la eniro ke mi manoj

136
00:05:11,300 --> 00:05:14,016
kaj mi farus kelkajn kalkulinta
decido bazita sur tiu eniro.

137
00:05:14,016 --> 00:05:15,640
Se ĝi komenciĝas per A, metis ĝin tien.

138
00:05:15,640 --> 00:05:18,980
Se ĝi komencas kun Z, metu ĝin sur
tie kaj ĉio en inter.

139
00:05:18,980 --> 00:05:22,730
>> Do tiu estas teknika kiu estas
ĝenerale konata kiel hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
kiu ĝenerale signifas prenanta
enigo kaj uzas input komputi

141
00:05:26,550 --> 00:05:30,940
valoro, ĝenerale numero, kaj ke
nombro estas la indico en stokado

142
00:05:30,940 --> 00:05:32,260
ujo, kiel tabelo.

143
00:05:32,260 --> 00:05:35,490
Do alivorte, mi povus havi
hash funkcio, kiel mi faras en mia kapo,

144
00:05:35,490 --> 00:05:37,940
ke se mi vidas ke iu estas
nomo kiu komenciĝas per A,

145
00:05:37,940 --> 00:05:40,190
Mi tuj mapaj ke
al nulo en mia kapo.

146
00:05:40,190 --> 00:05:44,160
Kaj se mi vidas iun kun Z, mi estas
tuj mapaj ke al 25 en mia kapo

147
00:05:44,160 --> 00:05:46,220
kaj tiam enkalkulu en
la lasta plej amaso.

148
00:05:46,220 --> 00:05:50,990
>> Nun, se vi pensas pri ne mia cerbo
sed C programo, kio nombroj povis

149
00:05:50,990 --> 00:05:53,170
fidi atingi tiun saman rezulton?

150
00:05:53,170 --> 00:05:55,594
En aliaj vortoj, se vi
havis la ASCII A

151
00:05:55,594 --> 00:05:57,510
kiel vi determini
kio sitelo meti ĝin?

152
00:05:57,510 --> 00:05:59,801
Vi probable ne volas
jxetos en rubujon 65, kiu

153
00:05:59,801 --> 00:06:01,840
estus kiel tie
sen bona kialo.

154
00:06:01,840 --> 00:06:04,320
Kie vi deziras meti
en terminoj de lia ASCII valoro?

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

156
00:06:05,600 --> 00:06:08,920
Kie vi deziras fari al liaj ASCII
valoro veni supren kun inteligenta sitelo

157
00:06:08,920 --> 00:06:09,480
meti ĝin?

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

159
00:06:10,206 --> 00:06:10,956
>> DAVID Malan: Jes.

160
00:06:10,956 --> 00:06:13,190
Do minus A aŭ minus
specife 65 se ĝi estas

161
00:06:13,190 --> 00:06:18,240
majuskla A. Aŭ 98 se
ĝi estas minuskla a.

162
00:06:18,240 --> 00:06:21,300
Kaj por ke ili permesus al ni, tre
simple kaj tre aritmetike,

163
00:06:21,300 --> 00:06:23,260
meti ion en sitelo tiel.

164
00:06:23,260 --> 00:06:26,010
Do rezultas ni efektive fari
ĉi tiel eĉ kun la kvizojn.

165
00:06:26,010 --> 00:06:29,051
>> Do vi eble memoras vin kaj cxirkaux via
instruado ulo nomo sur la ferdekon.

166
00:06:29,051 --> 00:06:32,270
Kaj la TF nomoj estis organizitaj
en tiuj kolumnoj alfabete,

167
00:06:32,270 --> 00:06:34,400
nu, kredu ĝin aŭ ne,
Kiam ĉiuj 80 plus nin

168
00:06:34,400 --> 00:06:37,800
kunvenigis la alian nokton al grado,
la lasta paŝo en nia grading procezo

169
00:06:37,800 --> 00:06:41,830
estas hash la kvizojn en grandan
spaco de etaĝo ĉe la [inaudible]

170
00:06:41,830 --> 00:06:45,110
kaj meti ĉies kvizojn el
en ĝuste la ordo de ilia TF La

171
00:06:45,110 --> 00:06:47,700
nomoj sur la kovrilo, ĉar
tiam ĝi estas multe pli facile por ni

172
00:06:47,700 --> 00:06:51,290
serĉi tra tiu uzanta linearaj
serĉu aŭ ian lertecon

173
00:06:51,290 --> 00:06:54,050
por TF trovi sian aŭ
ŝi studentoj kvizojn.

174
00:06:54,050 --> 00:06:56,060
>> Do tiu ideo de hashing
ke vi vidos estas

175
00:06:56,060 --> 00:07:00,520
sufiĉe potenca estas vere bela
banala kaj tre intuicia,

176
00:07:00,520 --> 00:07:03,000
multe kiel eble dividu kaj
konkero estis en semajno nulo.

177
00:07:03,000 --> 00:07:05,250
Mi firme antaŭen al la hackathon
paro de jaroj.

178
00:07:05,250 --> 00:07:08,040
Tio estis Zamyla kaj paro da
alia personaro saluton studentoj

179
00:07:08,040 --> 00:07:09,030
kiam ili eniris.

180
00:07:09,030 --> 00:07:12,680
Kaj ni havis tutan faskon da kunmeto
tabloj tie kun nomo etikedoj.

181
00:07:12,680 --> 00:07:15,380
Kaj ni estis la nomo tags organizita
kun kiel la mezuro tien

182
00:07:15,380 --> 00:07:16,690
kaj Zs tie.

183
00:07:16,690 --> 00:07:20,350
Kaj venis unu el la TFS tre lerte
verkis tion kiel la instrukcioj

184
00:07:20,350 --> 00:07:21,030
cxar la tago.

185
00:07:21,030 --> 00:07:24,480
Kaj en la semajno 12 de la semestro ĉi
ĉiuj perfektiĝas senco kaj ĉiuj

186
00:07:24,480 --> 00:07:25,310
sciis, kion fari.

187
00:07:25,310 --> 00:07:27,900
Sed anytime vi havas
vosto en la sama maniero,

188
00:07:27,900 --> 00:07:30,272
vi realiganta la
sama nocio de hash.

189
00:07:30,272 --> 00:07:31,730
Do ni formaligi gxin iomete.

190
00:07:31,730 --> 00:07:32,890
Jen tabelo.

191
00:07:32,890 --> 00:07:36,820
Ĝi estas desegnita por esti iom
larĝa ĝuste priskribi, vide,

192
00:07:36,820 --> 00:07:38,920
ke ni povu kordoj
en iu kiel ĉi tio.

193
00:07:38,920 --> 00:07:41,970
Kaj ĉi tabelo estas
klare de grandeco 26 entute.

194
00:07:41,970 --> 00:07:43,935
Kaj la afero estas nomita
tablo arbitre.

195
00:07:43,935 --> 00:07:48,930
Sed tio estas nur artisto lego
de kia hash tablo povus esti.

196
00:07:48,930 --> 00:07:52,799
>> Do hash tablo nun tuj
esti supera nivelo datumstrukturo.

197
00:07:52,799 --> 00:07:54,840
Je la fino de la tago
ni estas proksimume vidi ke vi

198
00:07:54,840 --> 00:07:58,700
povas implementar hash tablo, kiu
estas tre simila al la check-in linio

199
00:07:58,700 --> 00:08:02,059
ĉe hackathon multe ŝatas ĉi
tablo uzita por ordiga ekzameno libroj.

200
00:08:02,059 --> 00:08:03,850
Sed hash tablo
ia tiu alta nivelo

201
00:08:03,850 --> 00:08:08,250
koncepto kiu povus uzi tabelo
sub la kapuĉo funkciigi ĝin,

202
00:08:08,250 --> 00:08:11,890
aŭ ĝi povus uzi longitudon listo, aŭ eĉ
eble iuj aliaj datumstrukturoj.

203
00:08:11,890 --> 00:08:15,590
Kaj nun jen la theme-- preno
kelkaj el tiuj fundamentaj ingrediencoj

204
00:08:15,590 --> 00:08:18,310
kiel tabelo kaj tiu konstruaĵo
bloki nun de longa lerta

205
00:08:18,310 --> 00:08:21,740
kaj vidante kion alian ni povas konstrui
sur supro de tiuj, kiel ingrediencoj

206
00:08:21,740 --> 00:08:26,550
en recepto, farante pli kaj pli
interesa kaj utila finaj rezultoj.

207
00:08:26,550 --> 00:08:28,680
>> Do kun la hash tablo
ni povus apliki ŝin

208
00:08:28,680 --> 00:08:32,540
memore pictóricamente ŝatas tion, sed
kiom eble ĝi reale esti koditaj supren?

209
00:08:32,540 --> 00:08:33,789
Nu, eble simple estas tiu.

210
00:08:33,789 --> 00:08:38,270
Se kapablo en ĉiuj kaskedoj, estas nur
iuj constant-- ekzemple 26

211
00:08:38,270 --> 00:08:42,030
por 26 literoj de la alphabet--
Mi povus nomi mian variablo tablo

212
00:08:42,030 --> 00:08:45,630
kaj mi povus aserti, ke mi tuj
metis char steloj en tie, aŭ ŝnuro.

213
00:08:45,630 --> 00:08:49,880
Do ĝi estas tiel simpla kiel ĉi se vi
volas implementar hash tablo.

214
00:08:49,880 --> 00:08:51,490
Kaj tamen, tio estas vere nur tabelo.

215
00:08:51,490 --> 00:08:53,198
Sed denove, hash
tablo estas nun kion ni

216
00:08:53,198 --> 00:08:57,470
alvoki abstrakta datumtipo estas nur
ia conceptual layering supre

217
00:08:57,470 --> 00:09:00,780
de iu pli sekulara
nun kiel tabelo.

218
00:09:00,780 --> 00:09:02,960
>> Nun, kiel do ni iru
pri solvi problemojn?

219
00:09:02,960 --> 00:09:06,980
Nu, antaŭe mi havis la lukson
havi sufiĉe tablo spacon tie

220
00:09:06,980 --> 00:09:09,460
tiel ke mi povus meti la
kvizojn ie mi volis.

221
00:09:09,460 --> 00:09:10,620
Do Kiel povas iri tien.

222
00:09:10,620 --> 00:09:12,100
Zs venu ĉi tie.

223
00:09:12,100 --> 00:09:13,230
M povus iri tien.

224
00:09:13,230 --> 00:09:14,740
Kaj tiam mi havis iun ekstran spacon.

225
00:09:14,740 --> 00:09:18,740
Sed tio estas iom de Cheat dekstra
nun ĉar ĉi tabelo, se mi vere

226
00:09:18,740 --> 00:09:22,720
pensis pri ĝi kiel tabelo, estas nur
tuj estos de iu fiksa grandeco.

227
00:09:22,720 --> 00:09:25,380
>> Do teknike, se mi tiri
ĝis alia studenta kvizo

228
00:09:25,380 --> 00:09:28,490
kaj vidu, ho, tiu persono
nomo komenciĝas per A tro,

229
00:09:28,490 --> 00:09:30,980
Mi ia volas meti ĝin tie.

230
00:09:30,980 --> 00:09:34,740
Sed tuj kiam mi metis ĝin tie, se
tiu tabelo efektive reprezentas tabelo,

231
00:09:34,740 --> 00:09:37,840
Mi iras al esti supera aŭ clobbering
Kiu ĉi studenta kvizo estas.

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

233
00:09:38,340 --> 00:09:41,972
Se ĉi tiu estas tabelo, nur unu afero povas
iru en ĉiu el tiuj ĉeloj aŭ elementoj.

234
00:09:41,972 --> 00:09:43,680
Kaj tial mi specon de havi
elekti kaj elekti.

235
00:09:43,680 --> 00:09:45,735
>> Nun antaŭe mi specon de
trompis kaj faris tion aŭ mi

236
00:09:45,735 --> 00:09:47,526
nur speco de plata
ili supre la alia.

237
00:09:47,526 --> 00:09:49,170
Sed tio ne tuj flugas en kodo.

238
00:09:49,170 --> 00:09:52,260
Do kie mi povus meti la
dua studento kies nomo

239
00:09:52,260 --> 00:09:54,964
estas A se ĉiuj mi havis estas ĉi
disponebla tablo spaco?

240
00:09:54,964 --> 00:09:57,880
Kaj mi uzis tri fendojn kaj
Ŝajnas ke estas nur kelkaj aliaj.

241
00:09:57,880 --> 00:09:58,959
Kion vi povus fari?

242
00:09:58,959 --> 00:09:59,834
Publiko: [inaudible]

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

244
00:10:00,565 --> 00:10:01,315
DAVID Malan: Jes.

245
00:10:01,315 --> 00:10:02,370
Eble ni simple teni ĝin simpla.

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

247
00:10:02,660 --> 00:10:04,243
Ĝi ne taŭgas, kie mi volas meti ĝin.

248
00:10:04,243 --> 00:10:07,450
Do mi tuj metis ĝin
teknike kie B devus iri.

249
00:10:07,450 --> 00:10:09,932
Nun, kompreneble, mi ekde
pentri min en angulon.

250
00:10:09,932 --> 00:10:11,890
Se mi alvenas al lernanto
kies nomo estas fakte B

251
00:10:11,890 --> 00:10:14,840
Nun B tuj movi iom
antaŭen, kiel povus okazi, Yep,

252
00:10:14,840 --> 00:10:17,530
se tio estas B, nun devas iri tien.

253
00:10:17,530 --> 00:10:20,180
>> Kaj tiel ĉi tre rapide
povus iĝi problema,

254
00:10:20,180 --> 00:10:23,850
sed estas teknika kiu reale
estas referita al kiel lineara sondado,

255
00:10:23,850 --> 00:10:26,650
per vi nur rigardu vian
tabelo por esti laŭ la linio.

256
00:10:26,650 --> 00:10:29,680
Kaj vi ĝuste speco de sondilo aux
inspekti ĉiu disponebla elemento

257
00:10:29,680 --> 00:10:31,360
serĉas havebla makulo.

258
00:10:31,360 --> 00:10:34,010
Kaj kiam vi trovas
unu, vi faligis ĝin tie.

259
00:10:34,010 --> 00:10:38,390
>> Nun, la prezo pagita nun
por ĉi tiu solvo estas kio?

260
00:10:38,390 --> 00:10:41,300
Ni havas fiksan grandecon tabelo,
kaj kiam mi enŝovu nomoj

261
00:10:41,300 --> 00:10:44,059
en ĝin, almenaŭ komence, kio estas
la rula tempo de inserción

262
00:10:44,059 --> 00:10:46,350
por meti la studentoj '
kvizojn en la dekstra siteloj?

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

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

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

266
00:10:51,147 --> 00:10:52,480
DAVID Malan: Mi aŭdis granda O de n.

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

268
00:10:53,530 --> 00:10:54,300
Tio ne veras.

269
00:10:54,300 --> 00:10:56,490
Sed ni turmentus aparte
kial en nur momento.

270
00:10:56,490 --> 00:10:57,702
Kion alian povus esti?

271
00:10:57,702 --> 00:10:58,755
>> Publiko: [inaudible]

272
00:10:58,755 --> 00:11:00,380
DAVID Malan: Kaj lasu min fari ĝin vide.

273
00:11:00,380 --> 00:11:04,720
Do hipotezu tiu estas la letero S.

274
00:11:04,720 --> 00:11:05,604
>> Publiko: Estas unu.

275
00:11:05,604 --> 00:11:06,520
DAVID Malan: Estas unu.

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

277
00:11:06,710 --> 00:11:08,950
Tiu estas tabelo, kiu
signifas ke ni havos hazarda aliro.

278
00:11:08,950 --> 00:11:11,790
Kaj se ni pensas pri tio
kiel nulo kaj ĉi tiu 25

279
00:11:11,790 --> 00:11:13,800
kaj ni rimarkas ke,
Ho, ĉi tie estas mia enigo S,

280
00:11:13,800 --> 00:11:16,350
Mi certe povas konverti
S, estas ASCII,

281
00:11:16,350 --> 00:11:18,540
al responda nombro
inter nulo kaj 25

282
00:11:18,540 --> 00:11:20,910
kaj tiam tuj
meti ĝin kie ĝi apartenas.

283
00:11:20,910 --> 00:11:26,120
>> Sed kompreneble, kiam mi alvenas al la
dua persono kiu estas nomo estas A aŭ B aŭ C

284
00:11:26,120 --> 00:11:29,300
eventuale, se mi uzis la
lineara sondado kiel mia solvo,

285
00:11:29,300 --> 00:11:31,360
la rula tempo de
inserción en la plej malbona kazo

286
00:11:31,360 --> 00:11:33,120
Efektive tuj devolve en kio?

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

288
00:11:34,270 --> 00:11:36,045
Kaj mi ne aŭdas ĝin tie
korekte frue.

289
00:11:36,045 --> 00:11:36,920
Publiko: [inaudible]

290
00:11:36,920 --> 00:11:41,620
DAVID Malan: Do ĝi estas n ja unufoje
vi havas sufiĉe granda datumaro.

291
00:11:41,620 --> 00:11:44,410
Do, unuflanke, se
via tabelo estas sufiĉe granda

292
00:11:44,410 --> 00:11:48,287
kaj viajn datumojn estas maldensa sufiĉas, vi
ricevas tiun belegan konstanta tempo.

293
00:11:48,287 --> 00:11:50,620
Sed tuj kiam vi komencas
atingi pli kaj pli da eroj,

294
00:11:50,620 --> 00:11:53,200
kaj ĝuste statistike vi ricevas
pli da homoj kun la letero

295
00:11:53,200 --> 00:11:56,030
A kiel ilia nomo aŭ la letero
B, ĝi povus potenciale

296
00:11:56,030 --> 00:11:57,900
devolve en ion pli lineara.

297
00:11:57,900 --> 00:11:59,640
Do ne plene perfekta.

298
00:11:59,640 --> 00:12:00,690
Do ni povus fari pli bone?

299
00:12:00,690 --> 00:12:03,210
>> Nu, kion fari estis nia
solvon antaŭ kiam ni

300
00:12:03,210 --> 00:12:06,820
volas havi pli dinamismo ol
iu kiel tabelo permesita?

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

302
00:12:08,085 --> 00:12:08,960
Publiko: [inaudible]

303
00:12:08,960 --> 00:12:10,030
DAVID Malan: Kion ni enkonduki?

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

305
00:12:10,530 --> 00:12:11,430
Tiel lerta kunligita.

306
00:12:11,430 --> 00:12:14,430
Nu, ni vidu kion kunligita
lerta povus fari por ni anstataŭe.

307
00:12:14,430 --> 00:12:17,630
Nu, lasu min proponi ke ni
desegni la bildon kiel sekvas.

308
00:12:17,630 --> 00:12:19,620
Nun ĉi tiu estas malsama
bildo de ekzemplo

309
00:12:19,620 --> 00:12:24,750
el alia teksto, efektive, ke
fakte uzante tabelo de amplekso 31.

310
00:12:24,750 --> 00:12:28,220
Kaj tiu aŭtoro simple
decidis hash kordoj

311
00:12:28,220 --> 00:12:32,430
ne bazita sur la persona nomoj
sed bazita sur ilia birthdates.

312
00:12:32,430 --> 00:12:35,680
Sendepende de la monato, oni kalkulis
se vi naskiĝis en la unua de monato

313
00:12:35,680 --> 00:12:39,580
aŭ la 31a de la monato, la aŭtoro
Mi hash bazita sur tiu valoro,

314
00:12:39,580 --> 00:12:44,154
tiel kiel disvastigi la nomojn el iom
pli ol 26 makuloj povus permesi.

315
00:12:44,154 --> 00:12:47,320
Kaj eble ĝi estas iom pli unuforma
ol iri kun alfabeta leteroj

316
00:12:47,320 --> 00:12:50,236
ĉar kompreneble ekzistas probable
pli da homoj en la mondo kun nomoj

317
00:12:50,236 --> 00:12:54,020
ke komenciĝu per ol certe
kelkaj aliaj literoj de la alfabeto.

318
00:12:54,020 --> 00:12:56,380
Do eble tio iom
pli unuforma, supozante

319
00:12:56,380 --> 00:12:58,640
uniforma distribuo
de beboj transa monato.

320
00:12:58,640 --> 00:12:59,990
>> Sed, kompreneble, tiu estas ankoraŭ neperfekta.

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

322
00:13:00,370 --> 00:13:01,370
Ni devi kolizioj.

323
00:13:01,370 --> 00:13:04,680
Pluraj personoj en tiu
datumstrukturo restas

324
00:13:04,680 --> 00:13:08,432
havantaj la saman naskiĝo almenaŭ
vi senkonsidere monato.

325
00:13:08,432 --> 00:13:09,640
Sed kion la aŭtoro faris?

326
00:13:09,640 --> 00:13:13,427
Nu, ĝi aspektas kiel ni havas tabelo
sur la maldekstra flanko desegnita vertikale,

327
00:13:13,427 --> 00:13:15,010
sed tio estas nura artisto transdonado.

328
00:13:15,010 --> 00:13:18,009
Negrave kiudirekte vi
cxerpi tabelo, estas ankoraŭ tabelo.

329
00:13:18,009 --> 00:13:20,225
Kio estas ĉi tiu tabelo de ŝajne?

330
00:13:20,225 --> 00:13:21,500
>> Publiko: Ligita listo.

331
00:13:21,500 --> 00:13:21,650
>> DAVID Malan: Jes.

332
00:13:21,650 --> 00:13:23,490
Ĝi aspektas kiel ĝi estas
tabelo de ligitaj listo.

333
00:13:23,490 --> 00:13:26,490
Do denove, por tiu punkto de la varo
uzi tiujn datumstrukturoj nun

334
00:13:26,490 --> 00:13:28,550
kiel ingrediencojn por pli
interesajn solvojn,

335
00:13:28,550 --> 00:13:30,862
vi povas absolute preni
fundamenta, kiel tabelo,

336
00:13:30,862 --> 00:13:33,320
kaj poste prenu ion pli
interesa kiel ligillisto

337
00:13:33,320 --> 00:13:36,660
kaj eĉ kombini ilin en eĉ
pli interesa datumstrukturo.

338
00:13:36,660 --> 00:13:39,630
Kaj efektive, tiu tro farus
nomiĝi hash tablo

339
00:13:39,630 --> 00:13:42,610
per la tabelo estas
vere la hash tablo

340
00:13:42,610 --> 00:13:45,600
sed tiu hash tablo havas
ĉenoj, por tiel diri,

341
00:13:45,600 --> 00:13:50,220
kiu povas kreski aŭ ŝrumpi bazita sur la
nombro de elementoj vi volas enigi.

342
00:13:50,220 --> 00:13:52,990
>> Nun, laŭe, kio estas
la rula tempo nun?

343
00:13:52,990 --> 00:13:58,030
Se mi volas enigi iu
kies naskiĝtago estas oktobro 31

344
00:13:58,030 --> 00:13:59,040
Kie li aŭ ŝi iros?

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

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

347
00:14:01,030 --> 00:14:02,819
Ĉe la fundo kie diras 31.

348
00:14:02,819 --> 00:14:03,610
Kaj tio estas perfekta.

349
00:14:03,610 --> 00:14:05,060
Tio estis konstanta tempo.

350
00:14:05,060 --> 00:14:08,760
Sed kio se ni trovos iun alian
kies naskiĝtago estas, vidu,

351
00:14:08,760 --> 00:14:10,950
Oktobro, Novembro, Decembro 31?

352
00:14:10,950 --> 00:14:12,790
Kie estas li aŭ ŝi tuj iros?

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

354
00:14:13,290 --> 00:14:13,970
Du paŝo tamen.

355
00:14:13,970 --> 00:14:15,303
Tio estas konstanto se ĉu ne?

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

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

358
00:14:16,860 --> 00:14:17,840
Nuntempe ĝi estas.

359
00:14:17,840 --> 00:14:20,570
Sed en la ĝenerala kazo,
ju pli da homoj ni aldonu,

360
00:14:20,570 --> 00:14:23,790
_probabilistically_, ni iras
akiri pli kaj pli kolizioj.

361
00:14:23,790 --> 00:14:26,820
>> Nun tiu estas iom
bona ĉar teknike

362
00:14:26,820 --> 00:14:34,580
nun mia ĉenoj eblus en
la plej malbona kazo, kiel longe?

363
00:14:34,580 --> 00:14:38,890
Se mi enŝovu n popolon en tiu pli
malnaiva datumstrukturo, n popolon

364
00:14:38,890 --> 00:14:41,080
en la plej malbona kazo tuj estos n.

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

366
00:14:41,815 --> 00:14:43,332
>> Publiko: Ĉar se ĉiuj
havas la saman naskiĝtagon,

367
00:14:43,332 --> 00:14:44,545
ili tuj estos unu linio.

368
00:14:44,545 --> 00:14:45,420
DAVID Malan: Perfekta.

369
00:14:45,420 --> 00:14:47,480
Ĝi povus esti iom artefaritaj,
sed nur en la plej malbona kazo,

370
00:14:47,480 --> 00:14:50,117
se ĉiuj havas la saman naskiĝtagon,
donita la enigoj vi,

371
00:14:50,117 --> 00:14:51,950
vi tuj havos
amase longa ĉeno.

372
00:14:51,950 --> 00:14:54,241
Kaj tiel, vi povus nomi tion
hash tablo, sed vere ĝi estas

373
00:14:54,241 --> 00:14:56,810
nur amasan ligillisto kun
tutan multan malŝparis spaco.

374
00:14:56,810 --> 00:15:00,460
Sed ĝenerale, se ni supozas, ke
almenaŭ naskiĝtago estas uniform--

375
00:15:00,460 --> 00:15:01,750
kaj tio probable ne estas.

376
00:15:01,750 --> 00:15:02,587
Mi faras ke supren.

377
00:15:02,587 --> 00:15:04,420
Sed se ni supozas, por
pro diskuto

378
00:15:04,420 --> 00:15:07,717
ke ili, tiam teorie se
tio estas la vertikala reprezento

379
00:15:07,717 --> 00:15:11,050
de la tabelo, bone do espereble vi
tuj akiri ĉenoj kiuj estas, vi scias,

380
00:15:11,050 --> 00:15:15,880
proksimume la sama longo, kie ĉiu de
tiuj reprezentas tago de la monato.

381
00:15:15,880 --> 00:15:19,930
>> Nun, se estas 31 tagoj en la monato
kiu volas diri mian rultempo vere

382
00:15:19,930 --> 00:15:25,230
estas granda O de n super 31, kiu
sentas pli bona ol lineara.

383
00:15:25,230 --> 00:15:27,950
Sed kio estis unu el niaj
devontigoj paron de semajnoj

384
00:15:27,950 --> 00:15:31,145
antaŭ kiam ĝi venis al esprimo
la rula tempo de algoritmo?

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

386
00:15:33,450 --> 00:15:35,190
Simple nur rigardi la alta ordo terminon.

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

388
00:15:35,690 --> 00:15:37,400
31 estas definitive helpema.

389
00:15:37,400 --> 00:15:39,610
Sed tio estas ankoraŭ granda O de n.

390
00:15:39,610 --> 00:15:41,730
Sed unu el la temoj
de problemo starigis kvin

391
00:15:41,730 --> 00:15:43,950
tuj estos al
agnoski ke absolute,

392
00:15:43,950 --> 00:15:47,320
asimptote, teorie
tiu datumstrukturo

393
00:15:47,320 --> 00:15:50,470
Estas ne pli bona ol nur
unu masiva ligillisto.

394
00:15:50,470 --> 00:15:53,550
Kaj efektive, en la plej malbona kazo, ĉi
hash tablo povus devolve en tiun.

395
00:15:53,550 --> 00:15:57,620
>> Sed en la reala mondo, kun ni homoj
ke propraj Macs aŭ PC aŭ kio ajn

396
00:15:57,620 --> 00:16:01,240
kaj kuras reala mondo
programaro sur reala mondo datumoj

397
00:16:01,240 --> 00:16:03,260
kiun algoritmon vi iras preferi?

398
00:16:03,260 --> 00:16:09,180
Kiu portas fino paŝoj aŭ
Kiu prenas n dividita per 31 paŝoj

399
00:16:09,180 --> 00:16:12,900
trovi iun pecon de datumoj aŭ
serĉi informojn?

400
00:16:12,900 --> 00:16:16,580
Mi volas diri, absolute la 31 fabrikas
diferenco en la reala mondo.

401
00:16:16,580 --> 00:16:18,540
Ĝi estas 31 fojoj pli rapida.

402
00:16:18,540 --> 00:16:20,880
Kaj ni homoj estas sendube
tuj estimos tio.

403
00:16:20,880 --> 00:16:23,004
>> Do realigi la dicotomía
ekzistas inter reale

404
00:16:23,004 --> 00:16:25,920
parolante pri aferoj teorie
kaj asimptote kiu definitive

405
00:16:25,920 --> 00:16:28,760
havas valoron kiel ni vidis,
sed en la reala mondo,

406
00:16:28,760 --> 00:16:32,930
se vi interesas nur farante la
homa feliĉa por ĝenerala enigoj,

407
00:16:32,930 --> 00:16:36,010
vi eble tre bone volas akcepti
la fakto, ke, jes, tio estas lineara,

408
00:16:36,010 --> 00:16:38,360
sed estas 31 fojoj pli rapida
ol lineara povus esti.

409
00:16:38,360 --> 00:16:41,610
Kaj eĉ pli bone, ni ne nur devas
faru ion arbitra kiel naskiĝo,

410
00:16:41,610 --> 00:16:44,030
ni povis elspezi iom
pli tempo kaj lerteco

411
00:16:44,030 --> 00:16:47,140
kaj pensi pri kio ni povus fari,
donis la nomon de persono kaj eble

412
00:16:47,140 --> 00:16:50,130
ilia naskiĝo kombini tiujn
ingrediencoj elkompreni ion

413
00:16:50,130 --> 00:16:52,720
kiu estas vere pli
unuforma kaj malpli jaggy,

414
00:16:52,720 --> 00:16:56,250
tiel diri, ol tiu bildo
aktuale sugestas estu.

415
00:16:56,250 --> 00:16:57,750
Kiel ni povus apliki tion en la kodo?

416
00:16:57,750 --> 00:17:00,280
Nu, lasu min proponi ke ni
nur prunteprenis kelkajn sintakso ni

417
00:17:00,280 --> 00:17:01,799
uzis paron tempoj tiom.

418
00:17:01,799 --> 00:17:03,590
Kaj mi tuj difinos
nodon, kiu denove

419
00:17:03,590 --> 00:17:06,812
estas ĝenerala termino por nur kelkaj
kontenero por iu datumstrukturo.

420
00:17:06,812 --> 00:17:09,020
Mi tuj proponas ke
ŝnureto tuj tien.

421
00:17:09,020 --> 00:17:11,369
Sed ni tuj komencos preni
tiuj trejnado radoj for nun.

422
00:17:11,369 --> 00:17:13,230
>> Plu CS50 biblioteko
vere, krom se vi volas

423
00:17:13,230 --> 00:17:15,230
uzi ĝin por via fina
projekto, kiu estas pura,

424
00:17:15,230 --> 00:17:18,569
sed nun ni iras por tiri reen la
kurteno kaj diri estas nur char stelo.

425
00:17:18,569 --> 00:17:22,069
Do la vorto tie tuj estos
la persono nomo en demando.

426
00:17:22,069 --> 00:17:25,079
Kaj nun mi havas ligilon
tie al la sekva nodo

427
00:17:25,079 --> 00:17:28,170
tiel ke ĉi tiuj reprezentas
ĉiu el la nodoj

428
00:17:28,170 --> 00:17:30,950
en la ĉeno, potenciale,
de ligillisto.

429
00:17:30,950 --> 00:17:34,090
>> Kaj nun kio do mi rakontu
la hash tablo mem?

430
00:17:34,090 --> 00:17:36,660
Kjel mi rakontos cxi tiun tutan strukturon?

431
00:17:36,660 --> 00:17:40,960
Nu, vere, multe kiel mi uzis montrilon
al nur la unua elemento de listo

432
00:17:40,960 --> 00:17:44,510
antaŭe, simile mi povas simple diri
Mi nur bezonas faskon de punteros

433
00:17:44,510 --> 00:17:46,270
implementar ĉi tiu tuta hash tablo.

434
00:17:46,270 --> 00:17:49,484
Mi iras havi tabelo
nomata tablo por hash tablo.

435
00:17:49,484 --> 00:17:50,900
Ĝi tuj estos de grandeco kapablo.

436
00:17:50,900 --> 00:17:52,525
Tiel estas kiel multaj elementoj povas havi en ĝi.

437
00:17:52,525 --> 00:17:56,180
Kaj ĉiu el tiuj elementoj en ĉi
tabelo tuj estos nodo stelo.

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

439
00:17:56,810 --> 00:18:00,160
Nu, por ĉi tiu bildo, kio mi estas
realiganta la hash tablo

440
00:18:00,160 --> 00:18:04,330
efike en la komenco estas nur
tiu tabelo ke ni eltiris vertikale,

441
00:18:04,330 --> 00:18:06,820
ĉiu el kies kvadratoj
reprezentas montrilo.

442
00:18:06,820 --> 00:18:09,170
Ke tiuj, kiuj havas slashes
tra ili estas simple nula.

443
00:18:09,170 --> 00:18:11,410
Kaj tiuj, kiuj havas
sagoj tuj dekstre

444
00:18:11,410 --> 00:18:16,140
Estas reala punteros al efektiva nodoj,
Ergo la komenco de ligillisto.

445
00:18:16,140 --> 00:18:19,050
>> Do jen, do, estas kiel ni povus
implementar hash tablo ke

446
00:18:19,050 --> 00:18:21,580
implementa apartan sinsekvon.

447
00:18:21,580 --> 00:18:22,840
Nun ni povas fari pli bone?

448
00:18:22,840 --> 00:18:25,632
Bone mi promesis lastan fojon ke
ni povis atingi konstantan tempon.

449
00:18:25,632 --> 00:18:27,381
Kaj mi ia donis vin
konstanta tempo tie,

450
00:18:27,381 --> 00:18:29,850
sed tiam ne diris vere
konstantan tempo ĉar ĝi estas ankoraŭ

451
00:18:29,850 --> 00:18:31,890
dependa de la tuta
nombro de elementoj

452
00:18:31,890 --> 00:18:34,500
vi inputting en
la datumstrukturo.

453
00:18:34,500 --> 00:18:35,980
Sed supozu ni faris.

454
00:18:35,980 --> 00:18:39,550
Lasu min reiri al la ekrano super tie.

455
00:18:39,550 --> 00:18:44,520
Permesu al mi ankaŭ projekti ĉi tien, klaraj
la ekrano, kaj supozas ke mi tion faris.

456
00:18:44,520 --> 00:18:49,300
Supozi volis enmeti la nomon
Daven en en mian datumstrukturo.

457
00:18:49,300 --> 00:18:52,100
>> Do mi volas enigi kordo
Daven en la datumstrukturo.

458
00:18:52,100 --> 00:18:54,370
Kio se mi ne uzas
hash tablo, sed mi uzas

459
00:18:54,370 --> 00:18:56,980
iu kiu estas pli arbo-simila
kiel familio arbo, kie

460
00:18:56,980 --> 00:18:59,670
vi havas iun radikon en la
supro kaj tiam nodoj kaj folioj

461
00:18:59,670 --> 00:19:01,440
kiuj iras malsupren kaj eksteren.

462
00:19:01,440 --> 00:19:04,450
Supozu, ke mi
volas enigi Daven La

463
00:19:04,450 --> 00:19:06,430
en kio estas nuntempe vaka listo.

464
00:19:06,430 --> 00:19:09,780
Mi tuj faros la sekvan: Mi
tuj kreos nodon en tiu familio

465
00:19:09,780 --> 00:19:15,170
arbo-simila datumstrukturo kiuj aspektas
iom kiel tio, ĉiu el kiuj

466
00:19:15,170 --> 00:19:19,640
ortanguloj estas, ni diru,
nun 26 eroj en ĝi.

467
00:19:19,640 --> 00:19:21,650
Kaj ĉiu de la ĉeloj
en tiu tabelo tuj

468
00:19:21,650 --> 00:19:23,470
reprezenti la litero de alfabeto.

469
00:19:23,470 --> 00:19:28,190
>> Specife, Mi iras por trakti
ĉi estas A, do B, tiam C, tiam D,

470
00:19:28,190 --> 00:19:29,310
ĉi tie.

471
00:19:29,310 --> 00:19:32,940
Do tiu tuj efike
reprezenti la literon D.

472
00:19:32,940 --> 00:19:36,040
Sed enigi ĉiuj Daven La
nomon mi bezonas fari iom pli.

473
00:19:36,040 --> 00:19:37,840
Do mi unue iri al hash, por tiel diri.

474
00:19:37,840 --> 00:19:41,049
Mi iras rigardi la unuan literon
en Daven la kiu estas evidente D,

475
00:19:41,049 --> 00:19:42,840
kaj mi tuj rezervu
nodon kiu vidas

476
00:19:42,840 --> 00:19:45,570
kiel this-- grandan rektangulon big
sufiĉis por persvadi la tuta alfabeto.

477
00:19:45,570 --> 00:19:47,140
>> Nun D estas farita.

478
00:19:47,140 --> 00:19:49,720
Nun A. D-A-V-E-N estas la celo.

479
00:19:49,720 --> 00:19:51,220
Do nun kion mi tuj faros estas tiu.

480
00:19:51,220 --> 00:19:54,027
Apenaŭ mi komencis D avizo
ne estas puntero tie.

481
00:19:54,027 --> 00:19:56,860
Estas rubo valoroj en la momento,
aŭ mi pravalorizi ĝin nula.

482
00:19:56,860 --> 00:19:59,630
Sed lasu min plu iri kun
ĉi tiu ideo de konstruado de arbo.

483
00:19:59,630 --> 00:20:04,260
Lasu min atribui alia de tiuj
nodoj kiu havas 26 eroj en ĝi.

484
00:20:04,260 --> 00:20:05,150
>> Kaj vi scias kion?

485
00:20:05,150 --> 00:20:09,130
Se ĉi tio estas nur nodo en memoro ke
Mi kreis kun malloc, uzante struct

486
00:20:09,130 --> 00:20:11,240
kiel ni baldaŭ vidos,
Mi tuj faros this--

487
00:20:11,240 --> 00:20:14,450
Mi iras al desegni sago de
la afero, kiun reprezentis D malsupren

488
00:20:14,450 --> 00:20:15,860
al tiu nova nodo.

489
00:20:15,860 --> 00:20:19,240
Kaj nun, unue la proksima
letero en Daven nomo,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- Mi tuj iros antaŭen
ellogu alia nodo kiel tiu,

491
00:20:24,150 --> 00:20:30,150
per la V elementoj tie, kiuj
ni devos sortear instance-- Whoops.

492
00:20:30,150 --> 00:20:31,020
Ni ne tiros tie.

493
00:20:31,020 --> 00:20:31,936
Ĝi tuj iru tien.

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

495
00:20:32,890 --> 00:20:35,712
>> Tiam ni tuj
opinias tion V.

496
00:20:35,712 --> 00:20:44,920
Kaj poste malsupren tie ni iras al indekso
malsupren de V en kion ni konsideras E.

497
00:20:44,920 --> 00:20:50,100
Kaj tiam el tie ni tuj
iri havi unu el tiuj nodoj tie.

498
00:20:50,100 --> 00:20:52,930
Kaj nun ni havas demandon respondi.

499
00:20:52,930 --> 00:20:57,840
Mi bezonas iel indiki ke
ni estas ĉe la fino de la kordo Daven.

500
00:20:57,840 --> 00:20:59,490
Do mi povis nur lasi ĝin nula.

501
00:20:59,490 --> 00:21:02,670
>> Sed kio se ni havas Daven La
plena nomo ankaŭ, kiu

502
00:21:02,670 --> 00:21:04,280
estas, kiel ni jam diris, Davenport?

503
00:21:04,280 --> 00:21:06,970
Do kio se Daven estas
fakte subĉeno,

504
00:21:06,970 --> 00:21:08,960
prefikso de multe pli longa kordo?

505
00:21:08,960 --> 00:21:11,450
Ni ne povas simple konstante
diru nenion tuj

506
00:21:11,450 --> 00:21:14,410
iri tien, ĉar ni povis
neniam enmeti vorton kiel Davenport

507
00:21:14,410 --> 00:21:15,840
en tiu datumstrukturo

508
00:21:15,840 --> 00:21:19,560
>> Do kion ni povus fari anstataŭ trovas
trakti ĉiu el tiuj elementoj

509
00:21:19,560 --> 00:21:22,170
kiel eble havante du
elementoj ene de ili.

510
00:21:22,170 --> 00:21:24,810
Unu estas puntero ja
kiel Mi estis faranta.

511
00:21:24,810 --> 00:21:27,100
Do ĉiu el tiuj skatoloj
ne estas nur unu ĉelo.

512
00:21:27,100 --> 00:21:29,855
Sed kion se la supro
one-- malsupre ies

513
00:21:29,855 --> 00:21:32,230
tuj estos nula, ĉar
ne ekzistas Davenport nur ankoraŭ.

514
00:21:32,230 --> 00:21:34,197
Kio se la supra
Estas iu speciala valoro?

515
00:21:34,197 --> 00:21:36,530
Kaj tuj estos iom
malfacile treni lin tiu grandeco.

516
00:21:36,530 --> 00:21:38,130
Sed supozu gxuste ĉekon marko.

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

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N estas ĉeno
en tiu datumstrukturo.

519
00:21:44,230 --> 00:21:48,350
>> Dume, se mi havus pli spaco
tie mi povis fari P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
kaj mi povus meti ĉeko en la nodo
kiu havas la literon T en la fino.

521
00:21:52,650 --> 00:21:55,460
Do tio estas amase
kompleksa aspekto datumstrukturo.

522
00:21:55,460 --> 00:21:57,210
Kaj mia manskribo
certe ne helpas.

523
00:21:57,210 --> 00:22:00,043
Sed se mi volas enigi ion
alie, konsideri kion ni faros.

524
00:22:00,043 --> 00:22:03,370
Se ni volis meti Davidon,
Ni volonte sekvus la saman logikon, D-A-V,

525
00:22:03,370 --> 00:22:08,802
sed nun mi notus en la sekvanta
elemento ne de E, sed de Mi al D.

526
00:22:08,802 --> 00:22:10,760
Do tuj estos
pli nodoj en la arbo.

527
00:22:10,760 --> 00:22:12,325
Ni tuj havas alvokon malloc pli.

528
00:22:12,325 --> 00:22:14,700
Sed mi ne volas fari
kompleta salaton de ĉi tiu pentraĵo.

529
00:22:14,700 --> 00:22:17,710
Do ni anstataŭ rigardi unu
kiuj pasis antaŭ-formulita

530
00:22:17,710 --> 00:22:21,810
kiel tiu de ne pentras, punkto,
dots, sed simple mallongigita arrays.

531
00:22:21,810 --> 00:22:23,950
Sed ĉiu el la nodoj
en tiu arbo tien

532
00:22:23,950 --> 00:22:26,700
reprezentas la saman thing--
tabelo Radio de grandeco 26.

533
00:22:26,700 --> 00:22:28,860
>> Aŭ se ni volas esti
vere taŭga nun kion

534
00:22:28,860 --> 00:22:30,790
se ies nomon
apostrofo, ni

535
00:22:30,790 --> 00:22:35,560
supozi ke ĉiu nodo reale havas
kiel 27 indeksoj en ĝi, ne nur 26.

536
00:22:35,560 --> 00:22:42,020
Do tio nun tuj estos datuma
strukturo nomiĝas trie-- T-R-Mi-E.

537
00:22:42,020 --> 00:22:46,120
A trie, kiu estas supozeble
historie saĝa nomo por arbo

538
00:22:46,120 --> 00:22:49,040
ke estas optimumigita por
reakiro, kiu kompreneble,

539
00:22:49,040 --> 00:22:50,870
literumas kun I-E tiel ĝi estas trie.

540
00:22:50,870 --> 00:22:52,710
Sed tio estas la historio de la trie.

541
00:22:52,710 --> 00:22:55,860
>> Do trie estas tiu arbo-similaj datumoj
strukturo kiel familio arbo

542
00:22:55,860 --> 00:22:57,510
kiuj fine kondutas tiel.

543
00:22:57,510 --> 00:23:00,890
Kaj tie ĉi estas ĝuste alia ekzemplo de
amaso de fremdaj nomoj.

544
00:23:00,890 --> 00:23:03,540
Sed la demando nun
ĉe mano estas kio havas

545
00:23:03,540 --> 00:23:08,070
ni gajnis enkondukante defendeble pli
komplika datumstrukturo, kaj unu,

546
00:23:08,070 --> 00:23:09,870
sincere, kiu uzas multe da memoro.

547
00:23:09,870 --> 00:23:11,703
>> Ĉar kvankam,
Nuntempe, mi estas nur

548
00:23:11,703 --> 00:23:15,050
uzante D's puntero kaj
A kaj V kaj S kaj Ns,

549
00:23:15,050 --> 00:23:16,700
Mi malŝparante heck de multe da memoro.

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

551
00:23:18,030 --> 00:23:22,660
Sed kie mi pasigas unu rimedo,
Mi emas ne gajni reen alia.

552
00:23:22,660 --> 00:23:26,020
Do se mi elspezi pli spaco,
kio estas verŝajne la esperon?

553
00:23:26,020 --> 00:23:27,407
Ke mi elspezante malpli kio?

554
00:23:27,407 --> 00:23:28,240
Publiko: Malpli tempo.

555
00:23:28,240 --> 00:23:28,990
DAVID Malan: Epoko.

556
00:23:28,990 --> 00:23:30,320
Nun kial povus esti?

557
00:23:30,320 --> 00:23:33,880
Nu, kio estas la inserción
tempo, en terminoj de granda a nun,

558
00:23:33,880 --> 00:23:37,660
de nomo kiel Daven
aŭ Davenport aŭ David?

559
00:23:37,660 --> 00:23:39,340
Nu, Daven kvin paŝojn.

560
00:23:39,340 --> 00:23:42,350
Davenport estus naŭ ŝtupoj,
tiel estus kelkaj paŝoj.

561
00:23:42,350 --> 00:23:44,250
David estus kvin paŝoj tiel.

562
00:23:44,250 --> 00:23:47,230
Do tiuj estas konkretaj
nombroj, sed verŝajne ekzistas

563
00:23:47,230 --> 00:23:49,550
supera baro sur la
longo de ies nomon.

564
00:23:49,550 --> 00:23:52,240
Kaj efektive, la problemo
aroj de kvin specifo,

565
00:23:52,240 --> 00:23:54,050
Ni tuj proponos
ke io

566
00:23:54,050 --> 00:23:55,470
tio estas 40-iom-neparaj signoj.

567
00:23:55,470 --> 00:23:58,180
>> Realisme, neniu havas
senfine longa nomo

568
00:23:58,180 --> 00:24:01,542
tio estas, ke la longo de
nomo aŭ la longeco de kordo ni povus

569
00:24:01,542 --> 00:24:03,750
havi iun la stato de
strukturo estas defendeble kio?

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

571
00:24:05,550 --> 00:24:06,250
Ĝi estas konstanta.

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

573
00:24:06,430 --> 00:24:09,310
Ĝi povus esti granda konstanta ŝatas
40-ion, sed estas konstanta.

574
00:24:09,310 --> 00:24:13,752
Kaj ĝi havas nenian dependecon kiom
aliaj nomoj estas en tiu datumstrukturo.

575
00:24:13,752 --> 00:24:15,460
En aliaj vortoj, se mi
volis nun enmeti

576
00:24:15,460 --> 00:24:20,540
Colton aŭ Gabriel aŭ Rob aŭ Zamyla aŭ
Alison aŭ Belinda aŭ ajna aliaj nomoj

577
00:24:20,540 --> 00:24:23,940
de la dungitaro en ĉi datumoj
strukturon, estas la rultempo

578
00:24:23,940 --> 00:24:26,750
havigo aliaj nomoj
tuj estos tute impactado

579
00:24:26,750 --> 00:24:30,220
por kiel multaj aliaj elementoj estas
en la datumstrukturo jam?

580
00:24:30,220 --> 00:24:31,040
Ĝi estas ne.

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

582
00:24:31,540 --> 00:24:36,150
Ĉar ni efike uzi
tiu multi-tavolaj hash tablo.

583
00:24:36,150 --> 00:24:38,280
Kaj la rula tempo de
iu el tiuj operacioj

584
00:24:38,280 --> 00:24:41,510
dependas ne de la nombro de
elementoj, kiuj estas en la datumstrukturo

585
00:24:41,510 --> 00:24:43,090
aŭ kiu eventuale iri
esti en la datumstrukturo,

586
00:24:43,090 --> 00:24:44,714
sed sur la longeco de kion specife?

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

588
00:24:46,500 --> 00:24:49,200
>> La kordoj estas
insertan, kio faras ke

589
00:24:49,200 --> 00:24:52,580
ĉi asimptote konstanto
time-- granda O de unu.

590
00:24:52,580 --> 00:24:54,720
Kaj sincere, nur en
la reala mondo, tiu

591
00:24:54,720 --> 00:24:58,380
signifas enmeto Daven nomo prenas
kiel kvin paŝoj, aŭ Davenport naŭ

592
00:24:58,380 --> 00:25:00,100
paŝoj, aŭ Davido kvin paŝojn.

593
00:25:00,100 --> 00:25:03,071
Tio estas bela Darn malgrandaj kurado fojojn.

594
00:25:03,071 --> 00:25:05,320
Kaj ja, tio estas tre
bona afero, precipe kiam

595
00:25:05,320 --> 00:25:08,126
tio ne dependas de la tuta
nombro de elementoj en tie.

596
00:25:08,126 --> 00:25:10,500
Do kiel povas ni implementar ĉi
speco de strukturo en kodo?

597
00:25:10,500 --> 00:25:12,900
Ĝi estas iom pli
kompleksa, sed ankoraŭ estas

598
00:25:12,900 --> 00:25:15,050
nur apliko de
bazaj konstruelementoj.

599
00:25:15,050 --> 00:25:17,830
Mi iras redifini
ni nodo kiel sekvas:

600
00:25:17,830 --> 00:25:21,100
bool nomita word-- kaj ĉi
povus nomi ion.

601
00:25:21,100 --> 00:25:23,970
Sed la bool reprezentas
kion mi desegnis kiel ĉekon marko.

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

603
00:25:24,490 --> 00:25:26,720
Jen la fino de ĉeno
en tiu datumstrukturo.

604
00:25:26,720 --> 00:25:30,702
>> Kaj, kompreneble, la nodo stelo
tie estas referenco al infanoj.

605
00:25:30,702 --> 00:25:32,410
Kaj efektive, nur ŝatas
familio arbo, vi

606
00:25:32,410 --> 00:25:34,370
konsiderus la nodoj
kiuj pendis ekstere

607
00:25:34,370 --> 00:25:36,920
de la fundo de iu patro
elemento esti infanoj.

608
00:25:36,920 --> 00:25:40,510
Kaj tial la infanoj tuj
esti tabelo de 27, la 27-unu

609
00:25:40,510 --> 00:25:41,680
simple restante por apostrofo.

610
00:25:41,680 --> 00:25:43,390
Ni tuj ordigi
de speciala kazo tio.

611
00:25:43,390 --> 00:25:45,400
Do vi povas havi iun
nomoj kun apostrofoj.

612
00:25:45,400 --> 00:25:47,399
Eble eĉ streketo devus
iri tien, sed vi

613
00:25:47,399 --> 00:25:50,330
vidi en p aro 5 ni nur zorgo
pri literoj kaj apostrofoj.

614
00:25:50,330 --> 00:25:52,990
>> Kaj do kiel vi reprezentas
la datumstrukturo mem?

615
00:25:52,990 --> 00:25:56,454
Kiel vi reprezentus la radiko
de tiu trie, por tiel diri?

616
00:25:56,454 --> 00:25:59,620
Nu, simile kun ligillisto, vi
bezonas puntero al la unua ero.

617
00:25:59,620 --> 00:26:04,270
Kun trie vi nur bezonas unu
montrilon al la radiko de tiu trie.

618
00:26:04,270 --> 00:26:07,290
Kaj de tie povas hash
vian vojon malsupren pli kaj pli profunden

619
00:26:07,290 --> 00:26:10,460
al ĉiu alia nodo en la strukturo.

620
00:26:10,460 --> 00:26:13,440
Do simple per ĉi tedaĵo
Ni reprezentas ke struct.

621
00:26:13,440 --> 00:26:15,877
>> Nun Meanwhile-- Ho, demando.

622
00:26:15,877 --> 00:26:17,220
>> Publiko: Kio bool vorto?

623
00:26:17,220 --> 00:26:20,490
>> DAVID Malan: bool vorto
nur tiun C enkarniĝo

624
00:26:20,490 --> 00:26:22,920
kion mi priskribis
en tiu skatolo tie, kiam

625
00:26:22,920 --> 00:26:26,000
Mi komencis dividi ĉiu de la
tabelo de elementoj en du pecojn.

626
00:26:26,000 --> 00:26:27,600
Unu estas puntero al la venonta vertico.

627
00:26:27,600 --> 00:26:30,280
La aliaj devas esti
iu kiel ĉeko skatolo

628
00:26:30,280 --> 00:26:33,770
diri jes, ekzistas
vorto Daven kiu finiĝas ĉi tie,

629
00:26:33,770 --> 00:26:35,610
ĉar ni ne volas,
Nuntempe, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Kvankam Dave tuj estos
legitima vorton, li ne estas en la trie

631
00:26:39,320 --> 00:26:39,830
ankoraŭ.

632
00:26:39,830 --> 00:26:40,950
Kaj D estas ne unu vorton.

633
00:26:40,950 --> 00:26:42,770
Kaj D-A ne estas vorto aŭ nomo.

634
00:26:42,770 --> 00:26:45,020
Do la ĉekon markon
indikas nur unufoje vi

635
00:26:45,020 --> 00:26:48,190
batita tiu nodo estas
antaŭa vojo de karakteroj

636
00:26:48,190 --> 00:26:50,700
fakte ĉeno kiu vi enmetita.

637
00:26:50,700 --> 00:26:53,660
Do jen ĉio la bool
tie faras por ni.

638
00:26:53,660 --> 00:26:55,500
>> Ajna alia demandojn tries?

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

640
00:26:56,215 --> 00:26:58,035
>> Publiko: Kio estas la koincido?

641
00:26:58,035 --> 00:26:59,945
Kio, se vi havas Dave kaj Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID Malan: Perfekta.

643
00:27:00,820 --> 00:27:02,580
Kio, se vi havas Dave kaj Daven?

644
00:27:02,580 --> 00:27:06,240
Do se ni enŝovu diru alnomo,
por David-- Dave-- D-A-V-E?

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

646
00:27:07,370 --> 00:27:08,700
Tiu estas vere súper simpla.

647
00:27:08,700 --> 00:27:10,325
Do ni nur tuj prenos kvar paŝoj.

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

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. Kaj kion mi havas por
fari unufoje mi trafis ke kvara vertico?

650
00:27:15,847 --> 00:27:16,680
Nur tuj kontrolu.

651
00:27:16,680 --> 00:27:18,000
Ni estas jam bone iri.

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

653
00:27:18,840 --> 00:27:19,750
Kvar ŝtupoj.

654
00:27:19,750 --> 00:27:21,590
Konstanta tempo asimptote.

655
00:27:21,590 --> 00:27:26,300
Kaj nun ni indikis ke ambaŭ Dave
kaj Daven estas kordoj en la strukturo.

656
00:27:26,300 --> 00:27:27,710
Do ne estas problemo.

657
00:27:27,710 --> 00:27:30,200
Kaj rimarki kiom la ĉeesto
de Daven ne fari

658
00:27:30,200 --> 00:27:34,750
preni plu tempo aŭ malpli
tempon por Dave kaj viceversa.

659
00:27:34,750 --> 00:27:36,000
>> Do kion ajn ni povas nun fari?

660
00:27:36,000 --> 00:27:40,680
Ni uzis tiun metaforon antaŭe
de pletoj reprezenti ion.

661
00:27:40,680 --> 00:27:43,380
Sed rezultu ke
stako de pletoj estas reale

662
00:27:43,380 --> 00:27:47,187
demonstrativo de alia abstrakta datumoj
type-- altan nivelon datumstrukturo

663
00:27:47,187 --> 00:27:49,770
ke fine la tago estas nur
kiel tabelo aŭ ligillisto

664
00:27:49,770 --> 00:27:50,970
aŭ ion pli sekulara.

665
00:27:50,970 --> 00:27:53,270
Sed ĝi estas pli interesa
koncepta koncepto.

666
00:27:53,270 --> 00:27:56,440
Stako, kiel tiuj
pletoj tie en Mather,

667
00:27:56,440 --> 00:27:58,750
ĝenerale nomiĝas
nur that-- stako.

668
00:27:58,750 --> 00:28:02,540
>> Kaj en ĉi tiu tipo de datumstrukturo
vi havas du operations--

669
00:28:02,540 --> 00:28:05,880
Vi havas unu nomis puŝo por
aldoni ion al la pilo,

670
00:28:05,880 --> 00:28:08,320
kiel meti alian pleto
denove sur la supro de la stako.

671
00:28:08,320 --> 00:28:11,350
Kaj tiam elvenos, kio signifas ke
preni la plejsupra pleto ekstere.

672
00:28:11,350 --> 00:28:16,210
Sed kio estas klavo sur stako estas ke
ĝi estas atingis tiun scivolan karakterizaĵon.

673
00:28:16,210 --> 00:28:19,560
Kiel la manĝejo ŝablono estas
reordigante la pletoj por la venonta manĝo,

674
00:28:19,560 --> 00:28:21,380
kio okazas al esti
vera pri kiel studentoj

675
00:28:21,380 --> 00:28:22,856
interagi kun tiu datumstrukturo?

676
00:28:22,856 --> 00:28:24,480
Publiko: ili tuj pop unu ekstere.

677
00:28:24,480 --> 00:28:26,550
DAVID Malan: ili tuj
pop unu malproksime, espereble la supro.

678
00:28:26,550 --> 00:28:28,910
Alie ĝi estas nur speco de stulta
iri la tutan vojon al la fundo.

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

680
00:28:29,070 --> 00:28:31,620
La datumstrukturo vere ne permesas
vi ekpreni la malsupro pleto almenaŭ

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

682
00:28:32,520 --> 00:28:35,040
Do tie estas tio scivolema
posedaĵo al pilo

683
00:28:35,040 --> 00:28:39,730
ke la lasta ero en estas
tuj estos la unua unu el.

684
00:28:39,730 --> 00:28:43,400
Kaj komputilaj sciencistoj nomas
ĉi LIFO-- daŭri en, unua el.

685
00:28:43,400 --> 00:28:45,540
Kaj fakte ne havas
interesajn aplikojn.

686
00:28:45,540 --> 00:28:50,090
Tio ne nepre tiel evidenta kiel iuj
aliaj, sed ĝi povas ja esti utila,

687
00:28:50,090 --> 00:28:54,040
kaj ĝi povas efektive esti implementado
en kelkaj malsamaj manieroj.

688
00:28:54,040 --> 00:28:58,550
>> Do, kaj fakte, lasu
mi ne plonĝi en tiun.

689
00:28:58,550 --> 00:28:59,860
Ni faru tion anstataŭe.

690
00:28:59,860 --> 00:29:03,700
Ni rigardu, kiu estas preskaŭ la
sama ideo, sed ĝi estas iom pli justan.

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

692
00:29:04,200 --> 00:29:07,560
Se vi estas unu el tiuj fano boys aŭ
knabinoj kiuj vere ŝatas Apple produktoj

693
00:29:07,560 --> 00:29:10,130
kaj vi vekiĝis je 3:00 AM
vicigi en iu vendejo

694
00:29:10,130 --> 00:29:14,150
akiri la tre lasta iPhone, vi
eble vosto supren kiel ĉi.

695
00:29:14,150 --> 00:29:15,800
>> Nun vosto estas tre intence nomita.

696
00:29:15,800 --> 00:29:18,190
Estas linio ĉar estas
iuj justeco al ĝi.

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

698
00:29:18,690 --> 00:29:21,690
Estus ia sucxis Se vi
alvenis tie unue en la Apple Store

699
00:29:21,690 --> 00:29:25,700
sed vi estas efektive la ĉefundan
pleto ĉar la Apple oficistoj tiam

700
00:29:25,700 --> 00:29:28,189
pop la lasta persono, kiu
efektive havas en la linio.

701
00:29:28,189 --> 00:29:31,230
Do stakoj kaj vostoj, kvankam
funkcie ili estas speco de la same--

702
00:29:31,230 --> 00:29:33,105
estas nur tiu kolekto
de rimedoj kiuj estas

703
00:29:33,105 --> 00:29:36,210
tuj kreski kaj shrink-- ekzistas
tiu justeco aspekton al ĝi,

704
00:29:36,210 --> 00:29:39,634
almenaŭ en la reala mondo,
kie la operacioj vin praktiki

705
00:29:39,634 --> 00:29:40,800
estas fundamente malsama.

706
00:29:40,800 --> 00:29:43,360
A stack-- vosto
rather-- laŭdire havas

707
00:29:43,360 --> 00:29:45,320
du operacioj: n vosto kaj d vosto.

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

709
00:29:46,341 --> 00:29:48,090
Aŭ vi povas nomi ilin
ajna kvanto de aĵoj.

710
00:29:48,090 --> 00:29:50,770
Sed vi simple volas kapti
la nocio ke oni aldonas

711
00:29:50,770 --> 00:29:53,230
kaj estas finfine restante.

712
00:29:53,230 --> 00:29:58,840
>> Nun sub la kapuĉo, ambaŭ la pilo
kaj vosto povus implementados kiel?

713
00:29:58,840 --> 00:30:01,390
Ni ne eniros en la kodo de
ĉar la pli alta nivelo

714
00:30:01,390 --> 00:30:03,387
ideo estas ia pli evidenta.

715
00:30:03,387 --> 00:30:04,470
Mi volas diri, kion homoj faras?

716
00:30:04,470 --> 00:30:07,030
Se mi estas la unua persono en la Apple
Stoki kaj tio estas la granda pordo,

717
00:30:07,030 --> 00:30:08,130
Vi scias, ke mi tuj staru tie.

718
00:30:08,130 --> 00:30:09,750
Kaj en la sekvanta persono
tuj staru tie.

719
00:30:09,750 --> 00:30:11,500
Kaj en la sekvanta persono
tuj staru tie.

720
00:30:11,500 --> 00:30:13,792
Do kio datumstrukturo
pruntas al vosto?

721
00:30:13,792 --> 00:30:14,542
>> Publiko: A vosto.

722
00:30:14,542 --> 00:30:15,667
DAVID Malan: Bone, vosto.

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

724
00:30:16,390 --> 00:30:16,920
Kion alian?

725
00:30:16,920 --> 00:30:17,600
>> Publiko: Ligita listo.

726
00:30:17,600 --> 00:30:18,990
>> DAVID Malan: Ligita
listo vi povus apliki.

727
00:30:18,990 --> 00:30:22,500
Kaj ligillisto estas bela ĉar tiam
Ĝi povas kreski arbitre longajn kontraste

728
00:30:22,500 --> 00:30:24,880
por havi iu fiksita nombro
homoj en la vendejo.

729
00:30:24,880 --> 00:30:27,030
Sed eble fiksa nombro
de lokoj estas leĝa.

730
00:30:27,030 --> 00:30:30,350
Ĉar se ili nur havas kiel 20
iPhones en la unua tago, eble

731
00:30:30,350 --> 00:30:33,930
Ili nur bezonas tabelo de amplekso
20 reprezenti ke vosto, kiu

732
00:30:33,930 --> 00:30:37,070
nur diri nun kiam ni komencos parolante
pri tiuj altaj nivelo problemoj,

733
00:30:37,070 --> 00:30:38,890
vi povas funkciigi ĝin
en ajna nombro de manieroj.

734
00:30:38,890 --> 00:30:42,030
Kaj estas verŝajne nur tuj
esti komerco off en spaco kaj tempo

735
00:30:42,030 --> 00:30:43,950
aŭ nur en via propra kodo komplekseco.

736
00:30:43,950 --> 00:30:45,380
>> Kio pri pilo?

737
00:30:45,380 --> 00:30:48,190
Nu, stako, ni vidis tro
povus esti simple tiuj pletoj.

738
00:30:48,190 --> 00:30:50,007
Kaj vi povus implementar ĉi tabelo.

739
00:30:50,007 --> 00:30:53,090
Sed en iu momento, se vi uzas tabelo,
kio okazos al la pletojn

740
00:30:53,090 --> 00:30:54,173
vi provas sufoki?

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

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

743
00:30:55,670 --> 00:30:57,490
Vi nur tuj
povos iri tiom alte.

744
00:30:57,490 --> 00:31:00,156
Kaj mi kredas en Mather ili estas
efektive recessed en tiu malfermo.

745
00:31:00,156 --> 00:31:01,950
Do ja, estas preskaŭ
kiel Mather estas uzanta

746
00:31:01,950 --> 00:31:03,783
tabelo de fiksa grandeco,
ĉar vi nur povas

747
00:31:03,783 --> 00:31:08,302
ĝustigis tiel multaj pletoj en tiu malfermo en
la muro malsupre popola genuoj.

748
00:31:08,302 --> 00:31:10,010
Kaj tial eble
dirita esti tabelo,

749
00:31:10,010 --> 00:31:14,300
sed ni certe povus implementar ke
pli ĝenerale kun ligitaj listo.

750
00:31:14,300 --> 00:31:16,390
>> Nu, kio pri alia datumstrukturo?

751
00:31:16,390 --> 00:31:18,760
Lasu min eltiri supren unu alia vida tie.

752
00:31:18,760 --> 00:31:24,710
Io kiel kio pri tiu ĉi ankaŭ?

753
00:31:24,710 --> 00:31:28,920
Kial povus gxin utile havi ne
io kiel fantazio kiel trie, kion

754
00:31:28,920 --> 00:31:32,370
ni vidis havis tiujn tre larĝa nodoj,
ĉiu de kiuj estas en tabelo?

755
00:31:32,370 --> 00:31:35,740
Sed kio se ni faros ion pli
simple, kiel malnova lernejo genealogia arbo,

756
00:31:35,740 --> 00:31:38,110
ĉiu el kies verticoj tie
Estas simple stoki numero.

757
00:31:38,110 --> 00:31:42,180
Anstataŭ nomo aŭ posteulo
Estas simple stoki nombro kiel ĉi.

758
00:31:42,180 --> 00:31:45,250
>> Nu, la ĵargonon ni uzas en
datumstrukturoj estas ambaŭ tries

759
00:31:45,250 --> 00:31:49,510
kaj arboj, kie trie, denove, estas
nur unu kies nodoj estas arrays,

760
00:31:49,510 --> 00:31:51,680
Ankoraŭ kion vi eble
uzi de grado lernejo

761
00:31:51,680 --> 00:31:53,860
kiam vi faris familio
tree-- folioj kaj la radiko

762
00:31:53,860 --> 00:31:57,250
de la arbo kaj infanoj de la
patro kaj gefratoj largxo.

763
00:31:57,250 --> 00:32:03,670
Kaj ni povus apliki al arbo,
ekzemple, kiel simple kiel tiu.

764
00:32:03,670 --> 00:32:07,420
Arbo, se kiel nodo, unu el
tiuj rondoj kiuj havas numeron,

765
00:32:07,420 --> 00:32:09,947
tio ne tuj havos
unu montrilo, sed du.

766
00:32:09,947 --> 00:32:11,780
Kaj kiam vi aldonas
dua montrilo, vi

767
00:32:11,780 --> 00:32:13,905
efektive povas nun fari speco
de dudimensiaj datumoj

768
00:32:13,905 --> 00:32:14,780
strukturoj en memoro.

769
00:32:14,780 --> 00:32:16,660
Multe kiel du-dimensia
tabelo, vi povas

770
00:32:16,660 --> 00:32:18,904
havi specon de du-dimensia
ligitaj lertaj sed aĵoj

771
00:32:18,904 --> 00:32:20,820
kiuj sekvas mastron
kie ne estas cikloj.

772
00:32:20,820 --> 00:32:24,487
Estas vere arbon kun unu
avo vojon tien kaj tiam

773
00:32:24,487 --> 00:32:27,320
kelkaj gepatroj kaj infanoj kaj
nepoj kaj pranepoj.

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

775
00:32:28,370 --> 00:32:32,390
>> Sed kio estas vere neta pri tiu tro,
nur turmentus vin per iom da kodo,

776
00:32:32,390 --> 00:32:35,370
Memoru rikuro de
momenton dorso, per kiu

777
00:32:35,370 --> 00:32:38,220
vi skribas funkcio kiu nomas sin.

778
00:32:38,220 --> 00:32:41,140
Tiu estas bela ŝanco
implementar ion

779
00:32:41,140 --> 00:32:42,920
kiel rikuro, ĉar konsideras ĉi.

780
00:32:42,920 --> 00:32:43,860
>> Tio estas arbo.

781
00:32:43,860 --> 00:32:48,040
Kaj mi estis iom anal kun kiel
Mi metis la entjeroj eksteren.

782
00:32:48,040 --> 00:32:51,020
Tiel ke ĝi havas specialan
name-- duuma serĉarbo.

783
00:32:51,020 --> 00:32:53,460
Nun ni aŭdis pri duumaj
esplori, sed ĉu eblas

784
00:32:53,460 --> 00:32:55,180
labori malantaŭen de tiu afero estas nomata?

785
00:32:55,180 --> 00:32:59,280
Kio estas la mastro de kiel mi
insertado la entjerojn en ĉi arbo?

786
00:32:59,280 --> 00:33:00,696
Ĝi ne estas arbitra.

787
00:33:00,696 --> 00:33:01,570
Ekzistas iuj ŝablono.

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

789
00:33:02,090 --> 00:33:03,370
>> Publiko: plej malgranda sur la maldekstra.

790
00:33:03,370 --> 00:33:03,690
>> DAVID Malan: Jes.

791
00:33:03,690 --> 00:33:05,062
Malgrandaj estas maldekstre.

792
00:33:05,062 --> 00:33:06,270
Pli grandajn estas dekstre.

793
00:33:06,270 --> 00:33:12,940
Tia ke vera aserto estas
patro estas pli granda ol lia maldekstra infano,

794
00:33:12,940 --> 00:33:14,850
sed malpli ol lia dekstra infano.

795
00:33:14,850 --> 00:33:17,750
Kaj tio sola estas eĉ
rekursiaj parola difino

796
00:33:17,750 --> 00:33:20,500
ĉar vi povas peti ke
saman logikon por ĉiu nodo

797
00:33:20,500 --> 00:33:23,080
kaj nur fundoj
ekster, bazo kazo se vi

798
00:33:23,080 --> 00:33:25,740
volas, kiam vi batas unu el
la folioj, tiel diri,

799
00:33:25,740 --> 00:33:28,580
kie permeso ne havas infanojn for.

800
00:33:28,580 --> 00:33:30,614
>> Nun kiel eble vi trovos la numeron 44?

801
00:33:30,614 --> 00:33:32,280
Vi komencu je la radiko kaj diru, hm.

802
00:33:32,280 --> 00:33:35,690
55 ne estas 44 tiel Mi volas iri
dekstra aŭ mi volas iri forlasis?

803
00:33:35,690 --> 00:33:37,190
Nu, evidente vi volas iri maldekstren.

804
00:33:37,190 --> 00:33:40,060
Kaj tiel estas ĝuste kiel la telefono
libro ekzemple en duuma serĉo

805
00:33:40,060 --> 00:33:41,099
pli ĝenerale.

806
00:33:41,099 --> 00:33:43,390
Sed ni implementarla
nun iom pli dinamike

807
00:33:43,390 --> 00:33:45,339
ol tabelo povus permesi.

808
00:33:45,339 --> 00:33:48,130
Kaj fakte, se vi volas rigardi
en la kodo, unuavide certa.

809
00:33:48,130 --> 00:33:49,671
Ĝi aspektas kiel tuta fasko da linioj.

810
00:33:49,671 --> 00:33:51,220
Sed estas bele simpla.

811
00:33:51,220 --> 00:33:54,490
Se vi volas implementar funkcio
nomita serĉo kies celo en la vivo

812
00:33:54,490 --> 00:33:57,290
estas serĉi valoro
kiel n, entjero,

813
00:33:57,290 --> 00:34:01,756
kaj vi pasis en unu pointer--
puntero al la nodo de la radikoj,

814
00:34:01,756 --> 00:34:04,380
pli ĝuste, de tiu arbo de kiu
Vi povas aliri ĉion alian,

815
00:34:04,380 --> 00:34:08,850
rimarki kiom juste
Vi povas apliki la logikon.

816
00:34:08,850 --> 00:34:10,880
Se arbo estas nula,
Evidente ĝi ne estas tie.

817
00:34:10,880 --> 00:34:11,880
Ni simple reveni falsaj.

818
00:34:11,880 --> 00:34:12,000
Rajto?

819
00:34:12,000 --> 00:34:14,040
Se vi transdonos ŝin nenion,
nenio estas tie.

820
00:34:14,040 --> 00:34:17,900
>> Alie, se n estas malpli ol
arbo sagon n-- nun arrow n,

821
00:34:17,900 --> 00:34:20,670
memoras ni enkondukis súper
brevemente la alia tago,

822
00:34:20,670 --> 00:34:25,100
kaj tio nur signifas de-referenco la
puntero kaj rigardi la kampo nomata n.

823
00:34:25,100 --> 00:34:27,690
Do ĝi signifas iri tie kaj
rigardi la kampo nomata n.

824
00:34:27,690 --> 00:34:33,810
Do se n, la valoro vi donis, estas malpli
ol la valoro en la arboj entjero,

825
00:34:33,810 --> 00:34:35,449
Kien vi volas iri?

826
00:34:35,449 --> 00:34:36,389
Maldekstren.

827
00:34:36,389 --> 00:34:37,780
>> Do rimarki la rikuro.

828
00:34:37,780 --> 00:34:39,860
Mi returning-- ne veras.

829
00:34:39,860 --> 00:34:40,989
Ne falsaj.

830
00:34:40,989 --> 00:34:45,670
Mi revenos ajn respondon
Estas de alvoko al mi, pasante

831
00:34:45,670 --> 00:34:50,100
n denove, kio estas redunda,
sed kio estas iomete malsama nun?

832
00:34:50,100 --> 00:34:51,989
Kiel mi fari la problemo malgrandaj?

833
00:34:51,989 --> 00:34:54,920
Mi pasis en la dua
argumenton, ne la radiko de la arbo,

834
00:34:54,920 --> 00:34:59,616
sed la maldekstra infano en tiu kazo.

835
00:34:59,616 --> 00:35:00,990
Do mi pasis en la maldekstra infano.

836
00:35:00,990 --> 00:35:04,720
>> Dume, se n estas pli granda ol
la nodo Mi aktuale rigardis,

837
00:35:04,720 --> 00:35:06,690
Mi serĉas la dekstra flanko.

838
00:35:06,690 --> 00:35:10,880
Alie, se la arbo ne estas nula, kaj
se la elemento ne maldekstren

839
00:35:10,880 --> 00:35:13,240
kaj ne estas por la dekstra,
kio estas mirinde la kazo?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Ni fakte trovis la nodo en
demando, do ni revenos vera.

842
00:35:18,440 --> 00:35:21,490
>> Do ni nur skrapis la surfacon
nun kelkaj el tiuj datumstrukturoj.

843
00:35:21,490 --> 00:35:24,370
En problemo starigis kvin Vi
esplori tiujn ankoraŭ plu,

844
00:35:24,370 --> 00:35:27,250
kaj vi estos donita vian dezajno
elekto de kiel iri pri tio.

845
00:35:27,250 --> 00:35:30,250
Kion mi volas konkludi pri
Estas nur 30 duaj teaser

846
00:35:30,250 --> 00:35:32,080
de kio atendas venontan semajnon kaj pretere.

847
00:35:32,080 --> 00:35:35,390
>> Kiel ni begin-- dankeme vi eble
think-- nian transiron malrapide

848
00:35:35,390 --> 00:35:38,680
el la mondo de C kaj malsupra
nivelo efektivigo detaloj

849
00:35:38,680 --> 00:35:42,090
al mondo en kiu ni povas preni por
koncedas ke iu alia havas finfine

850
00:35:42,090 --> 00:35:44,010
implementado tiuj datumoj
strukturoj por ni,

851
00:35:44,010 --> 00:35:47,570
kaj ni komencas kompreni la
reala mondo signifas efektivigo

852
00:35:47,570 --> 00:35:50,560
TTT-bazita programoj kaj
retejojn pli ĝenerale

853
00:35:50,560 --> 00:35:52,910
kaj ankaŭ la tre sekureco
implicoj kiujn ni nur

854
00:35:52,910 --> 00:35:54,850
komencis skrapi la surfaco de.

855
00:35:54,850 --> 00:35:57,320
Jen kio atendas nin
en la tempo estonta.

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
>> -li Venis kun mesaĝo,
per protokolo tutan sian.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Li venis al mondo de kruela
firewalls, uncaring routers,

861
00:36:30,894 --> 00:36:33,368
kaj danĝeroj multe pli malbona ol la morto.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Li estas rapida.

864
00:36:36,236 --> 00:36:37,980
Li estas forta.

865
00:36:37,980 --> 00:36:42,830
Li estas TCP / IP, kaj li havas vian adreson.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Soldatoj de la Reto".

868
00:36:48,074 --> 00:36:49,660
[END VIDEO Playback]

869
00:36:49,660 --> 00:36:50,910
DAVID Malan: Coming venontan semajnon.

870
00:36:50,910 --> 00:36:51,880
Ni vidos vin poste.

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
-kaj Nun, "Deep Pensoj"
per Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Ĉiam startas
prelegoj kun, "Bone."

876
00:37:05,820 --> 00:37:08,750
Kial ne, "Jen la solvo
al tiu semajno problemo aro "

877
00:37:08,750 --> 00:37:12,180
aŭ "Ni donas al vi ĉiuj A?"

878
00:37:12,180 --> 00:37:13,380
[Ridante]

879
00:37:13,380 --> 00:37:15,530
[END VIDEO Playback]