1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Dobro, to je
CS50 Ovo je kraj tjedna pet.

3
00:00:15,860 --> 00:00:19,220
I podsjetiti da je zadnji put smo
počeli gleda na ljubitelj podataka

4
00:00:19,220 --> 00:00:22,310
strukture koji su se počeli rješavati
problemi, koji su se počeli uvoditi

5
00:00:22,310 --> 00:00:25,640
novi problemi, ali ključ za to
Bila je to threading da smo

6
00:00:25,640 --> 00:00:27,940
počeo raditi od čvora do čvora.

7
00:00:27,940 --> 00:00:30,085
Dakle, to je, naravno,
popis pojedinačno povezani.

8
00:00:30,085 --> 00:00:31,960
I pojedinačno povezani,
Mislim da postoji samo jedan

9
00:00:31,960 --> 00:00:33,380
nit između svaki od tih čvorova.

10
00:00:33,380 --> 00:00:35,890
Ispada da možete napraviti ljubitelj
stvari kao dvostruko povezane liste

11
00:00:35,890 --> 00:00:38,470
gdje imate strelicu
ide u oba smjera, što

12
00:00:38,470 --> 00:00:40,320
može pomoći s određenim učinkovitosti.

13
00:00:40,320 --> 00:00:42,000
Ali to riješilo problem?

14
00:00:42,000 --> 00:00:43,500
Koji problem je ovo riješiti?

15
00:00:43,500 --> 00:00:46,620
Zašto nam je stalo u ponedjeljak?

16
00:00:46,620 --> 00:00:49,820
Zašto, u teoriji, nije mi stalo u ponedjeljak?

17
00:00:49,820 --> 00:00:50,630
Što to radi?

18
00:00:50,630 --> 00:00:51,950
>> PUBLIKA: Mi dinamički promijeniti veličinu.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, možemo
dinamički promijeniti veličinu.

20
00:00:53,740 --> 00:00:54,710
Pa učinili oboje.

21
00:00:54,710 --> 00:00:57,560
Tako da može dinamički mijenjati veličinu ovog
struktura podataka, dok je niz,

22
00:00:57,560 --> 00:01:00,760
Podsjetimo, morate znati
priori koliko prostora želite

23
00:01:00,760 --> 00:01:03,870
a ako je potrebno malo više
Prostor, ti si vrsta od sreće.

24
00:01:03,870 --> 00:01:05,560
Morate stvoriti cijeli novi niz.

25
00:01:05,560 --> 00:01:07,893
Morate premjestiti sve svoje
podaci iz jednog u drugi,

26
00:01:07,893 --> 00:01:10,600
na kraju oslobodio stari niz
ako možete, a zatim nastavite.

27
00:01:10,600 --> 00:01:13,891
Koji samo osjeća vrlo skupo i vrlo
neučinkovit, i doista može biti.

28
00:01:13,891 --> 00:01:14,890
Ali to nije sve dobro.

29
00:01:14,890 --> 00:01:18,180
Mi platiti cijenu, što je bio jedan
od više očitih cijena mi

30
00:01:18,180 --> 00:01:20,550
platiti pomoću popisa povezani?

31
00:01:20,550 --> 00:01:22,825
>> PUBLIKA: Moramo iskoristiti
dvostruka prostor za svaku od njih.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Da, pa trebamo
najmanje dva puta toliko prostora.

33
00:01:25,200 --> 00:01:27,700
Zapravo, shvatio sam ovu sliku je
čak i malo zabludu,

34
00:01:27,700 --> 00:01:32,200
jer na CS50 IDE u puno modernog
računala, pokazivač ili adresa

35
00:01:32,200 --> 00:01:33,700
u stvari nije četiri bajta.

36
00:01:33,700 --> 00:01:36,090
Vrlo često ovi
dana osam bajtova, koji

37
00:01:36,090 --> 00:01:38,530
znači dno najviše
pravokutnici tamo u stvarnosti

38
00:01:38,530 --> 00:01:40,900
su vrsta dvostruko
velika kao što sam izvući,

39
00:01:40,900 --> 00:01:44,409
što znači da koristite tri puta
puno prostora kao što smo mogli imati drugačije.

40
00:01:44,409 --> 00:01:46,700
Sada, u isto vrijeme, mi smo
uvijek govori bajtova, zar ne?

41
00:01:46,700 --> 00:01:49,140
Mi ne nužno i govori
megabajta ili gigabajta,

42
00:01:49,140 --> 00:01:51,000
osim tih podataka strukture dobili veliki.

43
00:01:51,000 --> 00:01:54,510
>> I tako danas smo započeli u obzir
kako bismo mogli istražiti podatke

44
00:01:54,510 --> 00:01:57,310
učinkovitije ako u
Činjenica podaci dobiva veći.

45
00:01:57,310 --> 00:02:00,360
No, pokušajmo canonicalize
operacije prvi

46
00:02:00,360 --> 00:02:02,460
koje možete učiniti na njih
vrste podatkovnih struktura.

47
00:02:02,460 --> 00:02:04,790
Dakle, nešto poput povezan
Popis općenito podržava

48
00:02:04,790 --> 00:02:07,514
Poslovanje željeli izbrisati,
umetnite i pretraživanje.

49
00:02:07,514 --> 00:02:08,639
A što mislim pod tim?

50
00:02:08,639 --> 00:02:11,222
To samo znači da je obično,
ako su ljudi povezani pomoću popisa,

51
00:02:11,222 --> 00:02:14,287
oni ili netko drugi provodi
funkcije kao što izbrisati, umetnuti,

52
00:02:14,287 --> 00:02:16,120
i pretraživanje, tako da možete
zapravo učiniti nešto

53
00:02:16,120 --> 00:02:18,030
korisna sa strukturom podataka.

54
00:02:18,030 --> 00:02:20,760
Tako ćemo uzeti brzo pogledati
kako bismo mogli provesti

55
00:02:20,760 --> 00:02:24,530
neki broj za popis povezane kako slijedi.

56
00:02:24,530 --> 00:02:27,885
>> Dakle, ovo je samo neki C kod,
ni kompletan program

57
00:02:27,885 --> 00:02:29,260
da sam jako brzo tučeno gore.

58
00:02:29,260 --> 00:02:32,300
To nije online u distribuciji
broj, jer se neće pokrenuti.

59
00:02:32,300 --> 00:02:33,790
Ali primijetite Upravo sam
sa komentarom rekao,

60
00:02:33,790 --> 00:02:36,130
točka točka točkica, nešto
Postoji, dot dot dot, nešto postoji.

61
00:02:36,130 --> 00:02:38,410
I neka je samo pogledajte
što sočan dijelovi.

62
00:02:38,410 --> 00:02:40,790
Dakle, na liniji tri,
Podsjećamo da je ovo sada

63
00:02:40,790 --> 00:02:45,960
mi predložio proglašenje čvor posljednji
vrijeme, jedan od onih pravokutnih objekata.

64
00:02:45,960 --> 00:02:48,790
To je int kako ćemo nazvati N,
ali smo ga mogli nazvati ništa,

65
00:02:48,790 --> 00:02:51,920
a zatim struct čvor zvijezda zove sljedeći.

66
00:02:51,920 --> 00:02:55,520
I samo da bude jasno, da su drugi
linija, na liniji šest, što je to?

67
00:02:55,520 --> 00:02:57,930
Što se to radi za nas?

68
00:02:57,930 --> 00:03:01,044
Jer to sigurno izgleda više
grobni od naših uobičajenih varijabli.

69
00:03:01,044 --> 00:03:02,740
>> PUBLIKA: To čini premjestiti na jedan.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: To čini premjestiti na jedan.

71
00:03:04,650 --> 00:03:08,580
I da budemo precizniji,
to će pohraniti adresu

72
00:03:08,580 --> 00:03:11,582
čvora koji je značilo da se
semantički pokraj njega, zar ne?

73
00:03:11,582 --> 00:03:13,540
Dakle, to neće
nužno premjestiti ništa.

74
00:03:13,540 --> 00:03:15,290
To samo će
pohraniti vrijednost, što je

75
00:03:15,290 --> 00:03:17,170
će biti adresa
nekog drugog čvora,

76
00:03:17,170 --> 00:03:20,810
i to je razlog zašto smo je rekao struct
čvor zvijezda, zvijezda označava

77
00:03:20,810 --> 00:03:22,370
pokazivač ili adresu.

78
00:03:22,370 --> 00:03:26,390
U redu, tako da sada ako pretpostavimo da imamo
ova N dostupan za nas, i neka je

79
00:03:26,390 --> 00:03:29,490
Pretpostavljam da netko drugi ima
umetnuta cijela hrpa brojeva

80
00:03:29,490 --> 00:03:30,400
u popisu povezane.

81
00:03:30,400 --> 00:03:35,640
I to povezano popis
ukazao na neke točke

82
00:03:35,640 --> 00:03:39,040
varijabla zove popis koji je
donesen ovamo kao parametar,

83
00:03:39,040 --> 00:03:43,120
Kako mogu ići o liniji
14 provedbenih pretraživanje?

84
00:03:43,120 --> 00:03:45,990
Drugim riječima, ako sam provedbi
Funkcija čija je svrha u životu

85
00:03:45,990 --> 00:03:48,889
je uzeti int, pa tek onda
početak popisa povezane,

86
00:03:48,889 --> 00:03:50,430
da je pokazivač na popis povezani.

87
00:03:50,430 --> 00:03:52,992
Kao prvo, tko mislim Davida
bio naš volonter u ponedjeljak,

88
00:03:52,992 --> 00:03:54,700
on pokazujući na
cijeli povezani popis,

89
00:03:54,700 --> 00:03:57,820
to je kao da smo mi prolaze
David je u kao naš argument.

90
00:03:57,820 --> 00:03:59,990
Kako ćemo ići oko poprijeko ovaj popis?

91
00:03:59,990 --> 00:04:04,640
Pa, ispada da iako
pokazivače su relativno novi sad za nas,

92
00:04:04,640 --> 00:04:07,010
možemo to učiniti relativno
straightforwardly.

93
00:04:07,010 --> 00:04:09,500
>> Ja ću ići naprijed i
proglasiti privremenu varijablu koja

94
00:04:09,500 --> 00:04:12,364
po konvenciji samo ide
zvati pokazivač ili PTR,

95
00:04:12,364 --> 00:04:14,030
ali možete ga nazvati sve što želite.

96
00:04:14,030 --> 00:04:16,470
I ja ću inicijalizirati
je na početku liste.

97
00:04:16,470 --> 00:04:20,050
Tako možete vrsta misli o ovome
Kao što je mene učitelja drugi dan,

98
00:04:20,050 --> 00:04:23,580
vrsta pokazujući na nekoga
među našim ljudima kao volonteri.

99
00:04:23,580 --> 00:04:26,470
Tako sam privremenu varijablu koja je
Samo pokazujući na istu stvar

100
00:04:26,470 --> 00:04:31,390
da su naši slučajno zove
volonter David je također istaknuo.

101
00:04:31,390 --> 00:04:35,440
Sada, dok je pokazivač
nije null, jer opoziv

102
00:04:35,440 --> 00:04:40,350
koji null neka posebna Sentinel vrijednost
markira kraj popisa,

103
00:04:40,350 --> 00:04:44,280
pa dok nisam pokazujući na
tlo poput našeg zadnjeg volonter

104
00:04:44,280 --> 00:04:47,190
je, idemo naprijed
i učinite sljedeće.

105
00:04:47,190 --> 00:04:51,820
Ako pointer-- a sada sam vrsta želim
učiniti ono što smo učinili s učenikom

106
00:04:51,820 --> 00:04:57,410
structure-- ako pokazivač točka uz
equals-- a, ako se pokazivač točka N jednak

107
00:04:57,410 --> 00:05:02,290
varijabla jednaka N je
Argument koji je donesen u,

108
00:05:02,290 --> 00:05:05,370
onda želim ići naprijed
i reći povratak istina.

109
00:05:05,370 --> 00:05:11,020
Našao sam broj nje unutar
jedan od čvorova mom popisu povezane.

110
00:05:11,020 --> 00:05:13,500
Ali dot više
radi u ovom kontekstu,

111
00:05:13,500 --> 00:05:17,260
jer pokazivač, PTR, je
doista pokazivač, adresa,

112
00:05:17,260 --> 00:05:20,632
možemo zapravo predivno
koristiti konačno komad sintakse

113
00:05:20,632 --> 00:05:22,590
takav čini
intuitivan osjećaj i zapravo

114
00:05:22,590 --> 00:05:27,870
koristite strelicu ovdje, što znači ići od
da adresa na cijeli broj tamo u.

115
00:05:27,870 --> 00:05:30,160
Dakle, to je vrlo slično u
Duh operatoru dot,

116
00:05:30,160 --> 00:05:33,860
ali zato pokazivač nije pokazivač
a ne stvarna sama struct,

117
00:05:33,860 --> 00:05:35,380
mi samo koristiti strelicu.

118
00:05:35,380 --> 00:05:40,620
>> Dakle, ako je trenutni čvor da sam ja,
privremena varijabla, sam pokazujući na

119
00:05:40,620 --> 00:05:43,060
nije N, ono što želim učiniti?

120
00:05:43,060 --> 00:05:45,910
Pa, sa svojim ljudskim dobrovoljcima
da smo imali tu neki dan,

121
00:05:45,910 --> 00:05:49,710
ako je moj prvi čovjek nije onaj sam
žele, a možda i drugi ljudski nije

122
00:05:49,710 --> 00:05:52,660
onaj želim, a treći, ja
morate držati fizički kreće.

123
00:05:52,660 --> 00:05:54,690
Poput kako sam korak kroz popis?

124
00:05:54,690 --> 00:05:57,470
Kad smo imali niz vas,
upravo učinio kao ja plus plus.

125
00:05:57,470 --> 00:06:03,660
No, u ovom slučaju, dovoljno je
napraviti pokazivač, dobiva, pokazivača, sljedeći.

126
00:06:03,660 --> 00:06:07,580
Drugim riječima, sljedeći polje
je kao i svi napustili rukama

127
00:06:07,580 --> 00:06:10,880
da su naši ljudski dobrovoljci u ponedjeljak
su pomoću ukazati na nekom drugom čvoru.

128
00:06:10,880 --> 00:06:12,890
To su bili njihovi susjedi.

129
00:06:12,890 --> 00:06:17,060
>> Dakle, ako želim korak kroz ovaj popis,
Ne mogu samo ja radim plus plus više,

130
00:06:17,060 --> 00:06:20,120
Ja umjesto toga reći
Ja, pokazivač, ide

131
00:06:20,120 --> 00:06:24,650
jednaka bez obzira na sljedeći polje,
sljedeći polje, sljedeći polje,

132
00:06:24,650 --> 00:06:28,350
Sljedeći sve one koji su ostali rukama
da smo imali na pozornici usmjerenim

133
00:06:28,350 --> 00:06:30,000
nekim kasnijim vrijednosti.

134
00:06:30,000 --> 00:06:32,590
A ako ja dobiti preko
da cijeli iteracija,

135
00:06:32,590 --> 00:06:39,330
i na kraju, udario sam NULL nemaju
nađeno N ipak, samo sam return false.

136
00:06:39,330 --> 00:06:44,100
Pa opet, sve što radimo ovdje,
po slici trenutak prije,

137
00:06:44,100 --> 00:06:47,840
počinje od pokazujući na
počevši od popisa vjerojatno.

138
00:06:47,840 --> 00:06:50,970
A onda sam provjeriti, je vrijednost
Tražim jednaka devet?

139
00:06:50,970 --> 00:06:52,650
Ako je tako, ja se vratiti istina i ja sam učinio.

140
00:06:52,650 --> 00:06:56,450
Ako ne, ja ažurirati svoju ruku,
AKA pokazivač, ukazati

141
00:06:56,450 --> 00:06:59,540
Na sljedećem strelicama lokaciji, a
Onda sljedeći Arrow je mjesto,

142
00:06:59,540 --> 00:07:00,480
i sljedeći.

143
00:07:00,480 --> 00:07:03,770
Ja sam jednostavno šetnju kroz ovaj niz.

144
00:07:03,770 --> 00:07:06,010
>> Pa opet, koga briga?

145
00:07:06,010 --> 00:07:07,861
Kao što je to sastojak za?

146
00:07:07,861 --> 00:07:10,360
Pa, sjećam da smo uveli
pojam stog, koji

147
00:07:10,360 --> 00:07:15,400
je tip sažetak podataka u mjeri u kojoj je to
Nije C stvar, to nije stvar CS50,

148
00:07:15,400 --> 00:07:19,430
to je apstraktna ideja, ova ideja
slaganje stvari jedan povrh drugog

149
00:07:19,430 --> 00:07:21,820
koji se može provesti u
nakupine različitih načina.

150
00:07:21,820 --> 00:07:25,600
A jedan od načina da predloženo je s
niz ili s popisa povezane.

151
00:07:25,600 --> 00:07:29,570
I ispada da kanonski, A
stog podržava najmanje dvije operacije.

152
00:07:29,570 --> 00:07:32,320
I krilaticama su guranje, na
gurati nešto na stog,

153
00:07:32,320 --> 00:07:34,770
kao novi ladicu u
blagovaonica, ili pop,

154
00:07:34,770 --> 00:07:39,000
što znači ukloniti najviši
ladicu iz dimnjaka u blagovaonicu

155
00:07:39,000 --> 00:07:41,500
hodnik, a onda možda neki
druge poslove, kao dobro.

156
00:07:41,500 --> 00:07:45,770
Pa kako bismo mogli definirati strukturu
da smo sada zovete stog?

157
00:07:45,770 --> 00:07:50,020
>> Pa, imamo sve traženim
Sintaksa na raspolaganju u C. kažem,

158
00:07:50,020 --> 00:07:53,830
dajte mi definiciju vrsta
struct unutar stog,

159
00:07:53,830 --> 00:07:58,030
Idem reći je niz, od a
cijela hrpa brojeva, a zatim veličina.

160
00:07:58,030 --> 00:08:00,930
Dakle, drugim riječima, ako želim
implementirati ovaj u kodu,

161
00:08:00,930 --> 00:08:03,830
neka mi ići i samo vrsta
privući što to govori.

162
00:08:03,830 --> 00:08:06,317
Dakle, ovo je rekao, dajte mi
struktura koja ima niz,

163
00:08:06,317 --> 00:08:09,400
a ja ne znam što je kapacitet,
to je očito neka konstanta koja imam

164
00:08:09,400 --> 00:08:10,858
definirani drugdje, i to je u redu.

165
00:08:10,858 --> 00:08:15,260
No, pretpostavljam da je to samo jedan,
dva, tri, četiri, pet.

166
00:08:15,260 --> 00:08:16,700
Dakle, kapacitet je 5.

167
00:08:16,700 --> 00:08:21,730
Ovaj element unutar moje
struktura će se zvati brojeve.

168
00:08:21,730 --> 00:08:24,020
A onda mi je potreban
druga varijabla očito

169
00:08:24,020 --> 00:08:27,814
zove veličina da najprije idem
propisati inicijalizira na nulu.

170
00:08:27,814 --> 00:08:29,730
Ako postoji ništa u
snop, veličina nula,

171
00:08:29,730 --> 00:08:31,420
i to je vrijednosti smeće u brojkama.

172
00:08:31,420 --> 00:08:33,450
Nemam pojma što je tamo samo još.

173
00:08:33,450 --> 00:08:36,059
>> Dakle, ako želim gurati
nešto na stog,

174
00:08:36,059 --> 00:08:40,780
Pretpostavljam da zovem funkciju guranje i
Kažem gurnuti 50, kao broj 50,

175
00:08:40,780 --> 00:08:44,090
gdje bi predložiti
Ja ga nacrtati u ovom nizu?

176
00:08:44,090 --> 00:08:47,124
Postoji pet različitih mogućih odgovora.

177
00:08:47,124 --> 00:08:48,790
Kamo želite gurnuti broj 50?

178
00:08:48,790 --> 00:08:51,899
Ako je cilj ovdje, opet, nazovite
Funkcija gurati, prolaze u svađi

179
00:08:51,899 --> 00:08:52,940
50, gdje sam ga stavio?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Pet possible-- 20% šanse
nagađanje ispravno.

182
00:08:59,052 --> 00:08:59,896
Da?

183
00:08:59,896 --> 00:09:00,740
>> PUBLIKA: Daleko pravo.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Daleko pravo.

185
00:09:01,990 --> 00:09:08,359
Tu je sada 25% šanse
nagađanje ispravno.

186
00:09:08,359 --> 00:09:09,650
Tako da bi zapravo biti u redu.

187
00:09:09,650 --> 00:09:12,770
Po konvenciji, reći ću s nizom,
mi općenito bi početi na lijevo,

188
00:09:12,770 --> 00:09:14,519
ali smo mogli sigurno
početi na desnoj strani.

189
00:09:14,519 --> 00:09:17,478
Dakle, spojler ovdje bi se sam
Vjerojatno će ga izvući na lijevo,

190
00:09:17,478 --> 00:09:20,060
baš kao u normalnom polje gdje
Sam početak ide s lijeva na desno.

191
00:09:20,060 --> 00:09:21,780
Ali ako možete okrenuti
aritmetički, u redu.

192
00:09:21,780 --> 00:09:23,060
To jednostavno nije konvencionalno.

193
00:09:23,060 --> 00:09:24,880
OK, moram napraviti jedan
više promjena ipak.

194
00:09:24,880 --> 00:09:27,710
Sad kad sam gurnula nešto
na stog, što je sljedeće?

195
00:09:27,710 --> 00:09:29,400
>> U redu, moram povećajte veličinu.

196
00:09:29,400 --> 00:09:32,600
Pa neka mi ići naprijed i samo
ažurirati to, što je nula.

197
00:09:32,600 --> 00:09:35,950
I umjesto da sad idem
staviti u vrijednosti jedne.

198
00:09:35,950 --> 00:09:39,460
A sada pretpostavimo da gurnuti još
broj na stog, kao što je 51.

199
00:09:39,460 --> 00:09:42,680
Pa, moram napraviti još jedan
promjene, što je do veličine dva.

200
00:09:42,680 --> 00:09:46,100
A onda pretpostavljam da gurnuti još jedan
broj na stog poput 61,

201
00:09:46,100 --> 00:09:52,530
Sada moram ažurirati veličinu još jedan
vrijeme, i dobiti vrijednost 3 kao veličini.

202
00:09:52,530 --> 00:09:54,690
A sada pretpostavimo zovem pop.

203
00:09:54,690 --> 00:09:57,250
Sada pop, po konvenciji,
ne uzeti argument.

204
00:09:57,250 --> 00:10:00,430
Uz stog, cijela
točka ladice metafore

205
00:10:00,430 --> 00:10:03,450
je da nemate slobodu
ići dobiti taj pladanj, sve što možete učiniti

206
00:10:03,450 --> 00:10:06,330
je pop najviši jedan od
snop, samo zato.

207
00:10:06,330 --> 00:10:08,010
To je ono što ova struktura podataka radi.

208
00:10:08,010 --> 00:10:12,250
>> Dakle, po toj logici, ako ja
reći pop, što dolazi s?

209
00:10:12,250 --> 00:10:13,080
Dakle, 61.

210
00:10:13,080 --> 00:10:15,402
Dakle, ono što je stvarno računalo
učiniti u memoriji?

211
00:10:15,402 --> 00:10:16,610
Što je moj broj ima veze?

212
00:10:16,610 --> 00:10:20,330
Što biste predložiti
mijenjamo na zaslonu?

213
00:10:20,330 --> 00:10:23,410
Što treba promijeniti?

214
00:10:23,410 --> 00:10:24,960
Žao nam je?

215
00:10:24,960 --> 00:10:26,334
Tako smo dobili osloboditi od 61.

216
00:10:26,334 --> 00:10:27,500
Tako sam definitivno može učiniti.

217
00:10:27,500 --> 00:10:28,640
A ja mogu dobiti osloboditi od 61.

218
00:10:28,640 --> 00:10:30,980
I onda ono što drugima
Promjena treba dogoditi?

219
00:10:30,980 --> 00:10:33,160
Veličina vjerojatno ima vratiti na dva.

220
00:10:33,160 --> 00:10:34,210
I tako to je u redu.

221
00:10:34,210 --> 00:10:36,690
Ali čekaj malo, veličina
trenutak prije bile tri.

222
00:10:36,690 --> 00:10:38,240
Ajmo učiniti brzo provjeriti razum.

223
00:10:38,240 --> 00:10:41,810
Kako znamo da
htio riješiti od 61?

224
00:10:41,810 --> 00:10:42,760
Zato smo iskakanje.

225
00:10:42,760 --> 00:10:46,450
I tako sam ovu drugu veličinu imovine.

226
00:10:46,450 --> 00:10:48,470
>> Čekaj malo, ja sam
misleći natrag na tjedan-dva

227
00:10:48,470 --> 00:10:51,660
kad smo počeli govoriti o
polja, gdje je ovo položaj nula,

228
00:10:51,660 --> 00:10:55,920
ovo je položaj jedan, ovo je položaj
dva, to je lokacija tri, četiri,

229
00:10:55,920 --> 00:10:58,460
izgleda da je
odnos između veličine

230
00:10:58,460 --> 00:11:02,780
i element koji želim ukloniti
iz polja Čini se da samo biti što?

231
00:11:02,780 --> 00:11:05,120
Veličina minus jedan.

232
00:11:05,120 --> 00:11:07,786
I tako to je kako kao ljudi
znamo 61 na prvom mjestu.

233
00:11:07,786 --> 00:11:09,160
Kako je računalo će znati?

234
00:11:09,160 --> 00:11:11,701
Kada vaš broj, gdje vas vjerojatno
želite učiniti veličine minus jedan,

235
00:11:11,701 --> 00:11:14,950
pa tri minus jedan je dva, a to
znači želimo riješiti 61.

236
00:11:14,950 --> 00:11:18,000
A onda smo doista može ažurirati
veličina, tako da veličina sada

237
00:11:18,000 --> 00:11:20,300
ide od tri do samo dva.

238
00:11:20,300 --> 00:11:24,520
I samo da se pedantan, idem
predložiti da sam učinio, zar ne?

239
00:11:24,520 --> 00:11:27,660
Vi predložio intuitivno
točno sam trebao riješiti 61.

240
00:11:27,660 --> 00:11:30,700
Ali se nisam vrsta
vrsta stečen osloboditi od 61?

241
00:11:30,700 --> 00:11:33,790
Ja sam uspješno zaboravila
da je to zapravo bilo.

242
00:11:33,790 --> 00:11:37,680
I sjetim PSET4, ako ste pročitali
članak o forenzici, PDF

243
00:11:37,680 --> 00:11:40,780
da smo imali vi pročitali, ili
će pročitati ovaj tjedan za PSET4.

244
00:11:40,780 --> 00:11:44,300
Sjetite se da je to zapravo tijesnoj se
cijela ideja računalne forenzike.

245
00:11:44,300 --> 00:11:47,820
Što je računalo obično se je
to samo zaboravlja gdje se nešto nalazi,

246
00:11:47,820 --> 00:11:51,300
ali to ne ide i slično
pokušati ga precrtati ili dotjerivanje

247
00:11:51,300 --> 00:11:54,560
ti bitovi s nula i jedinica
ili neki drugi slučajni uzorak

248
00:11:54,560 --> 00:11:56,690
osim ako ste sami učinili namjerno.

249
00:11:56,690 --> 00:11:58,930
Dakle, vaša intuicija je
Dobro, neka je riješiti 61.

250
00:11:58,930 --> 00:12:00,650
No, u stvarnosti, ne moramo gnjaviti.

251
00:12:00,650 --> 00:12:04,040
Mi samo trebate zaboraviti da je
da je tamo mijenjajući naše veličine.

252
00:12:04,040 --> 00:12:05,662
>> Sada postoji problem s ovom stog.

253
00:12:05,662 --> 00:12:07,620
Ako sam gurati stvari
na stog, što je

254
00:12:07,620 --> 00:12:11,167
Očito će se dogoditi
u samo nekoliko trenutaka vremena?

255
00:12:11,167 --> 00:12:12,500
Ćemo ponestane prostora.

256
00:12:12,500 --> 00:12:13,580
I što nam je činiti?

257
00:12:13,580 --> 00:12:14,680
Mi smo vrsta pijan.

258
00:12:14,680 --> 00:12:19,000
Ovaj provedba ne dopustite
nas veličinu polja, jer pomoću

259
00:12:19,000 --> 00:12:21,240
ova sintaksa, ako vas
mislim natrag na tjedan-dva,

260
00:12:21,240 --> 00:12:23,520
nakon što ste proglasili
veličina niza,

261
00:12:23,520 --> 00:12:26,780
nismo vidjeli mehanizam još gdje
možete promijeniti veličinu polja.

262
00:12:26,780 --> 00:12:29,020
I doista C nema tu značajku.

263
00:12:29,020 --> 00:12:32,524
Ako kažeš daj mi pet
Nths, nazivaju ih brojevi,

264
00:12:32,524 --> 00:12:33,940
to je sve što ćeš dobiti.

265
00:12:33,940 --> 00:12:38,790
Tako smo sada od ponedjeljka, ima
sposobnost izražavanja rješenje

266
00:12:38,790 --> 00:12:42,480
ipak, samo trebamo ugađanje
definicija našeg dimnjaka

267
00:12:42,480 --> 00:12:46,840
ne biti neki hard-kodirane niz,
ali samo za pohranu adresu.

268
00:12:46,840 --> 00:12:47,890
>> Sad zašto je to?

269
00:12:47,890 --> 00:12:51,690
Sada samo moramo biti zadovoljni
činjenica da kad je moj program radi,

270
00:12:51,690 --> 00:12:53,730
Ja sam vjerojatno idući u
moraju pitati čovjeka,

271
00:12:53,730 --> 00:12:55,110
koliko brojeva želite spremiti?

272
00:12:55,110 --> 00:12:56,776
Tako je ulaz mora doći odnekud.

273
00:12:56,776 --> 00:12:59,140
Ali jednom znam da
broj, onda ja mogu samo

274
00:12:59,140 --> 00:13:02,470
koristiti ono što funkcionira dati
mi komad memorije?

275
00:13:02,470 --> 00:13:03,580
Mogu koristiti malloc.

276
00:13:03,580 --> 00:13:06,710
I ja mogu reći bilo koji broj
bajtova Želim natrag za ove Nths.

277
00:13:06,710 --> 00:13:10,910
I sve što imam za pohranu u brojkama
varijabla ovdje unutar ove STRUCT

278
00:13:10,910 --> 00:13:13,480
treba biti što?

279
00:13:13,480 --> 00:13:18,440
Što se zapravo ide u
brojevi u ovom slučaju?

280
00:13:18,440 --> 00:13:21,300
Da, pointer na prvi
bajt taj komad memorije,

281
00:13:21,300 --> 00:13:24,940
točnije, adresa
od prvih tih bajtova.

282
00:13:24,940 --> 00:13:27,300
Nije bitno je li to jedan
byte ili milijardu bajtova,

283
00:13:27,300 --> 00:13:28,890
Samo moram brinuti o prvom mjestu.

284
00:13:28,890 --> 00:13:31,530
Jer ono malloc jamstva i
moji operativnog sustava jamstva,

285
00:13:31,530 --> 00:13:34,170
da je komad memorije I.
dobiti, to će biti u dodiru.

286
00:13:34,170 --> 00:13:35,378
Tu neće biti praznina.

287
00:13:35,378 --> 00:13:38,576
Dakle, ako sam pitao za 50
bajtova ili 1.000 bajtova,

288
00:13:38,576 --> 00:13:40,450
svi oni će biti
natrag na leđa na leđa.

289
00:13:40,450 --> 00:13:44,500
I tako dok se sjećam kako je velika, kako
koliko sam tražio, sve što trebate znati

290
00:13:44,500 --> 00:13:46,230
je prvi takav adresa.

291
00:13:46,230 --> 00:13:48,660
>> Tako sada imamo mogućnost u kodu.

292
00:13:48,660 --> 00:13:51,280
Iako, to će nas odvesti
više vremena za pisanje ovaj gore,

293
00:13:51,280 --> 00:13:55,900
mi sada mogli preraspodijeliti tu memoriju
Samo spremanje drugu adresu tamo

294
00:13:55,900 --> 00:13:59,060
ako želimo veći ili čak
manji komad memorije.

295
00:13:59,060 --> 00:14:00,170
Dakle, ovdje se trgovina off.

296
00:14:00,170 --> 00:14:01,360
Sada smo dobili dinamiku.

297
00:14:01,360 --> 00:14:03,350
Imamo još
contiguousness sam tvrdi.

298
00:14:03,350 --> 00:14:05,881
Budući da će nam dati malloc
neprekinut komad memorije.

299
00:14:05,881 --> 00:14:08,630
No, to će biti bol u
vrat za nas, programer,

300
00:14:08,630 --> 00:14:09,770
zapravo kodirati gore.

301
00:14:09,770 --> 00:14:10,730
To je samo više posla.

302
00:14:10,730 --> 00:14:13,930
Trebamo kôd srodan što sam bio
lupanje iz samo trenutak prije.

303
00:14:13,930 --> 00:14:16,120
Vrlo izvodljiv, ali dodaje kompleksnost.

304
00:14:16,120 --> 00:14:19,520
I tako vrijeme programer, programer
Vrijeme je još jedan izvor

305
00:14:19,520 --> 00:14:22,520
da bismo je potrebno provesti
neko vrijeme da biste dobili nove značajke.

306
00:14:22,520 --> 00:14:24,020
I onda naravno postoji red.

307
00:14:24,020 --> 00:14:26,227
Nećemo ulaziti u to
jedan u više detalja.

308
00:14:26,227 --> 00:14:27,560
Ali to je vrlo sličan u duhu.

309
00:14:27,560 --> 00:14:31,220
Mogao bih provesti red, i
njegove odgovarajuće radnje,

310
00:14:31,220 --> 00:14:35,660
Postavi u red ili dequeue, kao što dodati ili ukloniti,
to je samo ljubitelj način ga govoreći:

311
00:14:35,660 --> 00:14:38,100
ili u red dequeue, kao što slijedi.

312
00:14:38,100 --> 00:14:41,170
Ja samo mogu dati ja osobno struct
opet ima niz je niz,

313
00:14:41,170 --> 00:14:44,000
opet ima veličinu,
ali zašto mi sada treba

314
00:14:44,000 --> 00:14:46,940
pratiti prednje redu?

315
00:14:46,940 --> 00:14:50,630
Nisam morate znati
ispred moje stog.

316
00:14:50,630 --> 00:14:53,570
Pa, ako sam opet za
queue-- neka je samo teško

317
00:14:53,570 --> 00:14:57,870
kodirati ga kao vlasništvo kao pet
cijeli brojevi u tu potencijalno.

318
00:14:57,870 --> 00:15:00,940
Dakle, ovo je nula, jedan, dva, tri, četiri.

319
00:15:00,940 --> 00:15:03,430
To će biti
ponovno pozvao brojevi.

320
00:15:03,430 --> 00:15:06,940
I to će se zvati veličina.

321
00:15:06,940 --> 00:15:10,056
>> Zašto je nije dovoljna
da imaju samo veličinu?

322
00:15:10,056 --> 00:15:11,680
Pa, neka je gurati one iste brojeve na.

323
00:15:11,680 --> 00:15:14,220
Tako sam pushed-- enqueued sam, ili guraju.

324
00:15:14,220 --> 00:15:20,150
Sad ću u red 50, a zatim
51, a zatim 61, a dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Dakle, to je u red.

326
00:15:21,070 --> 00:15:23,176
Enqueued sam 50, zatim 51, pa 61.

327
00:15:23,176 --> 00:15:25,050
I to izgleda identično
na hrpi do sada,

328
00:15:25,050 --> 00:15:27,190
osim što trebate napraviti jednu promjenu.

329
00:15:27,190 --> 00:15:33,680
Trebam ažurirati ove veličine, pa sam ići
od nula do jedan do dva na tri sada.

330
00:15:33,680 --> 00:15:35,760
Kako dequeue?

331
00:15:35,760 --> 00:15:36,890
Što se događa s dequeue?

332
00:15:36,890 --> 00:15:41,950
Tko bi trebao ispasti ovaj popis prvi
ako je linija na Apple Store?

333
00:15:41,950 --> 00:15:42,780
Dakle, 50.

334
00:15:42,780 --> 00:15:44,700
Dakle, to je vrsta trickier ovaj put.

335
00:15:44,700 --> 00:15:47,880
Dok zadnji put je bilo super
lako samo napraviti veličina minus jedan,

336
00:15:47,880 --> 00:15:51,440
Ja bi se na kraju mog niz učinkovito
gdje su brojevi, uklanja 61.

337
00:15:51,440 --> 00:15:52,920
Ali ja ne želim ukloniti 61.

338
00:15:52,920 --> 00:15:55,030
Želim da se 50, koji je
bio tamo u 5:00

339
00:15:55,030 --> 00:15:56,790
da se postroje za
Novi iPhone i sitnica.

340
00:15:56,790 --> 00:16:01,200
I tako riješiti 50, ja
ne mogu samo to učiniti, zar ne?

341
00:16:01,200 --> 00:16:02,547
Mogu precrtati 50.

342
00:16:02,547 --> 00:16:04,380
Ali samo mi smo rekli
ne moraju biti tako analni

343
00:16:04,380 --> 00:16:06,330
da precrtati ili sakriti podatke.

344
00:16:06,330 --> 00:16:08,090
Mi samo možemo zaboraviti gdje je.

345
00:16:08,090 --> 00:16:12,330
>> Ali ako promijenim veličinu sada
dva, to dovoljno informacija

346
00:16:12,330 --> 00:16:15,711
znati što se događa u mom redu?

347
00:16:15,711 --> 00:16:16,680
Ne baš.

348
00:16:16,680 --> 00:16:19,830
Kao moja veličina je dva, ali
gdje se red početak,

349
00:16:19,830 --> 00:16:22,980
pogotovo ako još uvijek imam
te iste brojeve u memoriji.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Dakle, moram se sjetiti
Sada, gdje je prednji je.

352
00:16:27,090 --> 00:16:29,630
I tako kao što sam predložio gore
tamo ćemo upravo nazvao

353
00:16:29,630 --> 00:16:33,729
NTH sprijeda, čija je početna
vrijednost treba biti što?

354
00:16:33,729 --> 00:16:35,270
Nula, tek početak popisa.

355
00:16:35,270 --> 00:16:40,876
Ali sada uz decrementing
veličina, samo smo povećajte frontu.

356
00:16:40,876 --> 00:16:42,000
Sada ovdje je još jedan problem.

357
00:16:42,000 --> 00:16:43,030
Dakle, nakon što sam se stalno događa.

358
00:16:43,030 --> 00:16:47,520
Smatram to je broj
poput 121, 124, a onda, dovraga,

359
00:16:47,520 --> 00:16:48,610
Ja sam iz prostora.

360
00:16:48,610 --> 00:16:50,390
Ali čekaj malo, ja nisam.

361
00:16:50,390 --> 00:16:55,630
Dakle, u ovom trenutku u priči,
Pretpostavimo da je veličina je jedan, dva,

362
00:16:55,630 --> 00:17:00,370
tri, četiri, pa pretpostavljam da je
veličina je četiri, prednji je jedan,

363
00:17:00,370 --> 00:17:01,621
pa 51 je na prednjoj strani.

364
00:17:01,621 --> 00:17:04,329
Želim staviti ovdje drugi broj,
ali, k vragu, ja sam iz prostora.

365
00:17:04,329 --> 00:17:06,710
Ali nisam stvarno, zar ne?

366
00:17:06,710 --> 00:17:11,192
Gdje bih mogao staviti neke
dodatna vrijednost, kao i 171?

367
00:17:11,192 --> 00:17:13,400
Da, mogao sam samo vrsta
vratite tamo, zar ne?

368
00:17:13,400 --> 00:17:18,161
A onda prelaze iz 50, ili
samo ga prebrisati sa 171.

369
00:17:18,161 --> 00:17:20,410
A ako se pitate zašto
naši brojevi dobio tako slučajni,

370
00:17:20,410 --> 00:17:24,150
oni se obično uzimaju računalo
Znanost tečajevi na Harvardu nakon CS50.

371
00:17:24,150 --> 00:17:27,510
Ali to je dobra optimizacija,
jer sada nisam gubit prostor.

372
00:17:27,510 --> 00:17:30,750
Još uvijek imati na umu
koliko je velika ova stvar je ukupno.

373
00:17:30,750 --> 00:17:31,500
To je pet ukupno.

374
00:17:31,500 --> 00:17:33,375
Jer ja ne želim
početak prepisati 51.

375
00:17:33,375 --> 00:17:36,260
Dakle, sada sam još uvijek izvan prostora,
tako da je isti problem kao i prije.

376
00:17:36,260 --> 00:17:39,140
Ali možete vidjeti kako sada
u kodu, vjerojatno

377
00:17:39,140 --> 00:17:41,910
napisati malo više
Složenost da bi se to dogodilo.

378
00:17:41,910 --> 00:17:44,510
A u stvari, ono što operater
u C vjerojatno omogućuje

379
00:17:44,510 --> 00:17:48,110
što magično to kružnost učiniti?

380
00:17:48,110 --> 00:17:50,160
Da operator modulo,
postotak znak.

381
00:17:50,160 --> 00:17:53,160
Dakle, što je vrsta cool o redu,
iako smo zadržati crtanje polja

382
00:17:53,160 --> 00:17:56,520
kao što su ovi poput ravne linije, ako vas
vrsta misli o tome što zakrivljeni

383
00:17:56,520 --> 00:18:00,341
okolo kao krug, onda samo
Intuitivno je vrsta radova psihički

384
00:18:00,341 --> 00:18:01,590
Mislim da je malo više čisto.

385
00:18:01,590 --> 00:18:05,190
Ti bi i dalje morati provesti
koji mentalni model u kodu.

386
00:18:05,190 --> 00:18:07,550
Dakle, ne da je teško,
u konačnici, za provedbu,

387
00:18:07,550 --> 00:18:12,430
ali još uvijek izgubiti size-- radije,
sposobnost za promjenu veličine, osim ako smo to učinili.

388
00:18:12,430 --> 00:18:15,310
>> Moramo se riješiti niz, mi
zamijenite ga s jednim pokazivačem,

389
00:18:15,310 --> 00:18:20,010
a onda negdje u mom kodu imam
poziv što funkcionira zapravo stvoriti

390
00:18:20,010 --> 00:18:23,720
Niz nazivaju brojeve?

391
00:18:23,720 --> 00:18:26,190
Malloc, ili neki sličan
funkcija, točno.

392
00:18:26,190 --> 00:18:30,481
Bilo kakva pitanja o hrpama ili redova.

393
00:18:30,481 --> 00:18:30,980
Da?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Dobro pitanje.

396
00:18:34,240 --> 00:18:35,830
Što modulo biste koristili ovdje.

397
00:18:35,830 --> 00:18:38,520
Dakle općenito, kada koristite
mod, što bi to

398
00:18:38,520 --> 00:18:40,620
sa veličinom od
Cijela struktura podataka.

399
00:18:40,620 --> 00:18:44,120
Dakle, nešto poput pet ili sposobnosti, ako
to je konstanta, vjerojatno je uključen.

400
00:18:44,120 --> 00:18:47,100
Ali samo radi modulo pet
Vjerojatno nije dovoljno,

401
00:18:47,100 --> 00:18:51,380
jer moramo znati da smo učinili
zamotajte ovdje ili ovdje ili ovdje oko.

402
00:18:51,380 --> 00:18:54,160
Dakle, vjerojatno ste također
će htjeti uključiti

403
00:18:54,160 --> 00:18:57,220
veličina stvar, ili
prednji varijabla, kao dobro.

404
00:18:57,220 --> 00:19:00,140
Dakle, to je samo to relativno
Jednostavna matematika izraz,

405
00:19:00,140 --> 00:19:02,000
ali modulo će biti ključni sastojak.

406
00:19:02,000 --> 00:19:03,330
>> Dakle, kratki film, ako hoćete.

407
00:19:03,330 --> 00:19:05,780
Animacija da su neki
ljudi na drugom sveučilištu

408
00:19:05,780 --> 00:19:08,060
staviti zajedno da smo
prilagođena za ovu raspravu.

409
00:19:08,060 --> 00:19:12,630
To uključuje Jack učenju
činjenice o redovima i statistike.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: Jednom davno,
bio je čovjek po imenu Jack.

412
00:19:21,890 --> 00:19:25,330
Kada je došlo do izrade prijatelje,
Jack nije imao smisao.

413
00:19:25,330 --> 00:19:28,220
Tako je Jack otišao razgovarati s
najpopularniji dečko znao.

414
00:19:28,220 --> 00:19:30,920
Otišao je Lou i pitao, što da radim?

415
00:19:30,920 --> 00:19:33,400
Lou je vidio da je njegov prijatelj
je stvarno nevolji.

416
00:19:33,400 --> 00:19:36,050
Pa, on je počeo, samo
pogledajte kako ste odjeveni.

417
00:19:36,050 --> 00:19:38,680
Zar ne imati bilo odjeću
s različitim izgled?

418
00:19:38,680 --> 00:19:39,660
Da, rekao je Jack.

419
00:19:39,660 --> 00:19:40,840
Ja sigurno učiniti.

420
00:19:40,840 --> 00:19:43,320
Dođite u moju kuću i
Ja ću im pokazati.

421
00:19:43,320 --> 00:19:44,550
Tako su otišli Jack.

422
00:19:44,550 --> 00:19:47,520
A Jack je pokazao Lou kutiju
gdje je zadržao sve svoje košulje,

423
00:19:47,520 --> 00:19:49,260
a njegove hlače i čarapama.

424
00:19:49,260 --> 00:19:52,290
Lou je rekao, vidim da imate
sve svoje odjeće u gomili.

425
00:19:52,290 --> 00:19:54,870
Zašto ne nosiš neke
drugi jednom u neko vrijeme?

426
00:19:54,870 --> 00:19:58,020
>> Jack je rekao, dobro, kada sam
izvadite odjeću i čarape,

427
00:19:58,020 --> 00:20:00,780
Ja ih oprati i staviti
ih daleko u kutiji.

428
00:20:00,780 --> 00:20:03,210
Tada dolazi sljedeći
jutro, i gore sam hop.

429
00:20:03,210 --> 00:20:06,380
Idem kutije i dobiti
moja odjeća off vrhu.

430
00:20:06,380 --> 00:20:09,070
Lou brzo shvatio
problem s Jackom.

431
00:20:09,070 --> 00:20:12,080
Držao odjeću, CD-a,
a knjige u dimnjaku.

432
00:20:12,080 --> 00:20:14,420
Kad je posegnuo za
nešto čitati ili nositi,

433
00:20:14,420 --> 00:20:17,100
on bi odabrati gornji knjigu ili donje rublje.

434
00:20:17,100 --> 00:20:19,500
Onda kada je učinio, on je
bi ga stavio natrag.

435
00:20:19,500 --> 00:20:21,970
Natrag to će ići, na vrhu dimnjaka.

436
00:20:21,970 --> 00:20:24,460
Znam rješenje,
rekao pobjednički Loud.

437
00:20:24,460 --> 00:20:27,090
Morate naučiti
početi koristiti red.

438
00:20:27,090 --> 00:20:29,870
Lou je Jackove odjeću i
objesio ih u ormaru.

439
00:20:29,870 --> 00:20:32,710
I kad je ispraznio
okvir, on je samo bacio.

440
00:20:32,710 --> 00:20:36,500
>> Tada je rekao, sada je Jack, na kraju
dan, stavite odjeću na lijevoj

441
00:20:36,500 --> 00:20:37,990
kada ih otpustiti.

442
00:20:37,990 --> 00:20:41,300
Sutra ujutro kad vas
vidjeti sunce, dobiti svoju odjeću

443
00:20:41,300 --> 00:20:43,440
na desnoj strani, od kraja linije.

444
00:20:43,440 --> 00:20:44,880
Zar ne vidite? reče Lou.

445
00:20:44,880 --> 00:20:46,370
To će biti tako lijepo.

446
00:20:46,370 --> 00:20:49,770
Vi ćete nositi sve odjednom
Prije nego što nosite nešto dvaput.

447
00:20:49,770 --> 00:20:52,670
I sa svime u redovima
u svom ormaru i polica,

448
00:20:52,670 --> 00:20:55,160
Jack je počeo osjećati
sasvim sigurni u sebe.

449
00:20:55,160 --> 00:20:59,720
Sve zahvaljujući Lou i
njegova prekrasna red.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Dobro, to je divan.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Dakle, ono što je stvarno događa
na ispod haube sada?

453
00:21:10,080 --> 00:21:12,370
Da imamo upućuje,
da imamo malloc,

454
00:21:12,370 --> 00:21:15,680
da imamo mogućnost stvaranja
komadi memorije za sebe

455
00:21:15,680 --> 00:21:16,344
dinamički.

456
00:21:16,344 --> 00:21:18,510
Dakle, ovo je slika nas
nazire baš neki dan.

457
00:21:18,510 --> 00:21:21,180
Mi stvarno ne prebiva
na njemu, ali ova slika

458
00:21:21,180 --> 00:21:24,180
ima se događa ispod
napa već tjednima.

459
00:21:24,180 --> 00:21:27,050
I tako to predstavlja, samo
pravokutnik koji smo izvući,

460
00:21:27,050 --> 00:21:28,180
memorije računala.

461
00:21:28,180 --> 00:21:31,850
A možda je računalo, ili CS50
ID, ima gigabajt memorije ili RAM

462
00:21:31,850 --> 00:21:33,050
ili dva gigabajta ili četiri.

463
00:21:33,050 --> 00:21:34,450
To zapravo ne smeta.

464
00:21:34,450 --> 00:21:37,240
Vaš operativni sustav
Windows ili Mac OS ili Linux,

465
00:21:37,240 --> 00:21:41,120
suštini omogućuje svoj program
da mislim da ima pristup

466
00:21:41,120 --> 00:21:42,982
na cjelinu
memorije računala,

467
00:21:42,982 --> 00:21:45,440
iako možda biti pokrenut
više programa odjednom.

468
00:21:45,440 --> 00:21:46,990
Tako je u stvarnosti, to zapravo ne rade.

469
00:21:46,990 --> 00:21:49,448
No, to je vrsta iluzije
s obzirom na sve svoje programe.

470
00:21:49,448 --> 00:21:53,110
Dakle, ako ste imali dva nastupa RAM, ovaj
je kako se računalo može misliti o tome.

471
00:21:53,110 --> 00:21:57,110
>> Sada je slučajno, jedan od tih
stvari, jedna od tih segmenata memorije,

472
00:21:57,110 --> 00:21:58,350
naziva stog.

473
00:21:58,350 --> 00:22:01,680
I doista bilo koje vrijeme
Do sada je u pisanje koda

474
00:22:01,680 --> 00:22:05,900
da ste naziva
funkcija, primjerice Main.

475
00:22:05,900 --> 00:22:08,410
Sjetite se da je bilo vrijeme imam
memorije nacrtana računala,

476
00:22:08,410 --> 00:22:10,640
Uvijek sam crtati vrsta
polovica pravokutnika ovdje

477
00:22:10,640 --> 00:22:12,520
i ne smetaju govori
o tome što je ranije.

478
00:22:12,520 --> 00:22:15,980
Jer kada glavni zove, tvrdim
da ste dobili ovu luč memorije

479
00:22:15,980 --> 00:22:16,970
da ide ovdje dolje.

480
00:22:16,970 --> 00:22:20,650
I ako glavna naziva funkcija
kao zamjene, te zamjena ide ovdje.

481
00:22:20,650 --> 00:22:23,720
I ispada da je
gdje je završio.

482
00:22:23,720 --> 00:22:26,277
Na nešto što se zove snop
unutar memorije računala.

483
00:22:26,277 --> 00:22:28,360
Sada je na kraju dan,
ovo je samo bavi.

484
00:22:28,360 --> 00:22:30,680
To je kao byte nula,
bajt jedan, bajt 2 milijarde.

485
00:22:30,680 --> 00:22:33,130
Ali ako mislite o tome
što je ovaj pravokutni objekt,

486
00:22:33,130 --> 00:22:35,130
svi mi radimo svaki
Vrijeme mi zovemo funkcija

487
00:22:35,130 --> 00:22:37,180
raslojavanje novi komad memorije.

488
00:22:37,180 --> 00:22:41,700
Mi smo davanje tu funkciju kriška
vlastite memorije raditi.

489
00:22:41,700 --> 00:22:44,490
>> A sjećam se sada da je to važno.

490
00:22:44,490 --> 00:22:46,400
Jer ako mi nemamo
nešto poput zamjene

491
00:22:46,400 --> 00:22:51,610
i dvije lokalne varijable kao što su A i B i
možemo promijeniti te vrijednosti od jednog i dva

492
00:22:51,610 --> 00:22:55,130
za dva i jedan, opoziv
da kad zamjena vraća,

493
00:22:55,130 --> 00:22:58,330
to je kao da je ovaj kriška
memorije je samo otišao.

494
00:22:58,330 --> 00:23:00,080
U stvarnosti, to je još uvijek
Postoji forenzički.

495
00:23:00,080 --> 00:23:01,940
I nešto još zapravo tamo.

496
00:23:01,940 --> 00:23:05,410
No konceptualno, to je kao
iako je potpuno nestala.

497
00:23:05,410 --> 00:23:10,910
I tako glavna ne zna bilo koji dio posla
koje je učinjeno u tom swapu funkciji,

498
00:23:10,910 --> 00:23:14,890
osim ako to je zapravo prošlo u onima
Argumenti po karti ili referenca.

499
00:23:14,890 --> 00:23:17,790
Sada, temeljno rješenje
za taj problem s swapa

500
00:23:17,790 --> 00:23:19,970
prolazi stvari u koju adresu.

501
00:23:19,970 --> 00:23:23,250
No, ispostavilo se, također, ono što je
događa iznad tog dijela

502
00:23:23,250 --> 00:23:26,330
pravokutnika sve ovo vrijeme
Još ima više memorije tamo.

503
00:23:26,330 --> 00:23:28,790
A kada dinamički
alocirati memoriju,

504
00:23:28,790 --> 00:23:32,020
da li je unutar GetString, koji
smo radili za vas u CS50

505
00:23:32,020 --> 00:23:34,710
knjižnica, ili ako vi
nazvati i pitati malloc

506
00:23:34,710 --> 00:23:37,950
operativni sustav za komad
memorije, to ne dolazi iz dimnjaka.

507
00:23:37,950 --> 00:23:40,960
Ona dolazi s drugog mjesta
u memoriju računala

508
00:23:40,960 --> 00:23:42,220
kako se zove gomila.

509
00:23:42,220 --> 00:23:43,430
I to nije bilo drugačije.

510
00:23:43,430 --> 00:23:44,285
To je isti RAM.

511
00:23:44,285 --> 00:23:45,160
To je isti memorije.

512
00:23:45,160 --> 00:23:49,080
To je samo RAM-to je gore
tamo umjesto ovamo.

513
00:23:49,080 --> 00:23:50,750
>> I tako, što to znači?

514
00:23:50,750 --> 00:23:53,650
Pa, ako vaše računalo ima
konačan iznos memorije

515
00:23:53,650 --> 00:23:57,450
i stog raste, tako
govoriti, a gomila, prema

516
00:23:57,450 --> 00:23:59,349
ovom strijelom, raste prema dolje.

517
00:23:59,349 --> 00:24:01,140
Drugim riječima, svaki
Vrijeme nazovete malloc,

518
00:24:01,140 --> 00:24:03,430
ti si se dao krišku
memorije odozgo,

519
00:24:03,430 --> 00:24:06,630
onda možda malo niža, a zatim malo
niže, svaki put kad poziv malloc,

520
00:24:06,630 --> 00:24:10,100
hrpu, to je običaj,
je vrsta raste,

521
00:24:10,100 --> 00:24:11,950
raste bliže i bliže što?

522
00:24:11,950 --> 00:24:13,382
Stog.

523
00:24:13,382 --> 00:24:14,840
Dakle, to se čini kao dobra ideja?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Mislim, gdje je zapravo nije jasno
Što još možete učiniti ako samo

526
00:24:22,140 --> 00:24:23,910
imaju ograničen količinu memorije.

527
00:24:23,910 --> 00:24:25,200
No, to je sigurno loše.

528
00:24:25,200 --> 00:24:27,920
Te dvije strelice ste na
sudar naravno jedni za druge.

529
00:24:27,920 --> 00:24:31,930
>> I ispada da negativca, ljudi koji
posebno su dobri s programiranjem,

530
00:24:31,930 --> 00:24:36,140
i pokušava provaliti u računala,
mogu iskoristiti ovu stvarnost.

531
00:24:36,140 --> 00:24:38,290
U stvari, neka je uzeti u obzir
malo isječak.

532
00:24:38,290 --> 00:24:41,350
Dakle, ovo je primjer možete pročitati
O detaljnije na Wikipediji.

533
00:24:41,350 --> 00:24:43,100
Mi ćemo Vam ukazati na
Članak ako znatiželjni.

534
00:24:43,100 --> 00:24:45,650
No, tu je napad općenito
poznat kao buffer overflow koji

535
00:24:45,650 --> 00:24:49,570
postoji koliko god ljudi
imali sposobnost da manipulira

536
00:24:49,570 --> 00:24:53,120
memorije računala, a posebno u C.
Dakle, ovo je vrlo proizvoljna programa,

537
00:24:53,120 --> 00:24:55,130
ali neka je čitati od dna prema gore.

538
00:24:55,130 --> 00:24:57,650
Glavni u argC char zvjezdica argv.

539
00:24:57,650 --> 00:24:59,830
Dakle, to je program koji traje
argumente naredbenog retka.

540
00:24:59,830 --> 00:25:03,620
I svi glavni očito nema je poziv
funkcija, nazivaju ga F za jednostavnošću.

541
00:25:03,620 --> 00:25:04,610
I to prolazi u što?

542
00:25:04,610 --> 00:25:05,490
Argv jednog.

543
00:25:05,490 --> 00:25:09,320
Dakle, to prelazi u F god
Riječ je da korisnik upisali

544
00:25:09,320 --> 00:25:11,500
u retku nakon što je
Ime programa je na sve.

545
00:25:11,500 --> 00:25:15,730
Toliko poput Cezara ili Vigenere koji
možda sjetiti radiš sa argv.

546
00:25:15,730 --> 00:25:16,680
>> Dakle, što je F?

547
00:25:16,680 --> 00:25:19,760
F uzima u nizu
kao jedini argument,

548
00:25:19,760 --> 00:25:22,100
AKA ugljen zvijezda, isto
stvar, kao string.

549
00:25:22,100 --> 00:25:24,920
I to se zove proizvoljno
bar u ovom primjeru.

550
00:25:24,920 --> 00:25:27,710
A onda char c 12,
Samo u laik uvjete,

551
00:25:27,710 --> 00:25:31,750
Što je char c nosač 12 radi za nas?

552
00:25:31,750 --> 00:25:33,440
Što je to?

553
00:25:33,440 --> 00:25:36,490
Dodjela memorije, posebno
12 bajta za 12 znakova.

554
00:25:36,490 --> 00:25:36,990
Točno.

555
00:25:36,990 --> 00:25:40,000
I onda posljednja linija, promiješati i
kopija, vjerojatno ste ne vidi.

556
00:25:40,000 --> 00:25:43,360
To je niz kopija
Funkcija čija je svrha u životu

557
00:25:43,360 --> 00:25:48,160
je da kopirate svoju drugu tvrdnju
u svom prvom argumentu,

558
00:25:48,160 --> 00:25:51,190
ali samo do
određeni broj bajtova.

559
00:25:51,190 --> 00:25:53,860
Dakle, treći argument kaže,
koliko bajtova trebate kopirati?

560
00:25:53,860 --> 00:25:56,720
Duljina trake,
sve što korisnik upisali u.

561
00:25:56,720 --> 00:25:59,320
A sadržaj
bar, taj string, su

562
00:25:59,320 --> 00:26:02,330
kopirati u memoriju ukazao na na C

563
00:26:02,330 --> 00:26:04,060
>> Tako to izgleda nekako glupo, i to je to.

564
00:26:04,060 --> 00:26:06,300
To je neprirodan primjer,
ali to je predstavnik

565
00:26:06,300 --> 00:26:10,100
klase napada vektora,
način napadaju program.

566
00:26:10,100 --> 00:26:15,050
Sve je u redu i dobro ako korisnik
vrste u riječ koja je 11 znakova

567
00:26:15,050 --> 00:26:18,040
ili manje, plus backslash nula.

568
00:26:18,040 --> 00:26:22,830
Što ako korisnik upiše u više od
11 ili 12 ili 20 ili 50 znakova?

569
00:26:22,830 --> 00:26:25,090
Što je ovaj program će učiniti?

570
00:26:25,090 --> 00:26:29,360
Potencijalno SEG kriv. Ide
slijepo kopirati sve što je u baru do

571
00:26:29,360 --> 00:26:31,750
svoje dužine, koji je
doslovno sve u baru,

572
00:26:31,750 --> 00:26:36,307
u adresi ukazao na C. No C
je samo preventivno dati kao 12 bajtova.

573
00:26:36,307 --> 00:26:37,640
Ali nema dodatnih provjera.

574
00:26:37,640 --> 00:26:38,700
Nema li uvjete.

575
00:26:38,700 --> 00:26:40,580
Nema provjere ovdje pogreške.

576
00:26:40,580 --> 00:26:43,270
>> I tako ono što ovaj program
učiniti je samo slijepo

577
00:26:43,270 --> 00:26:45,750
kopirati jednu stvar na drugu.

578
00:26:45,750 --> 00:26:47,880
I tako, ako ćemo izvući ovu
kao slika, evo

579
00:26:47,880 --> 00:26:49,860
samo komadić od memorijskog prostora.

580
00:26:49,860 --> 00:26:53,470
Tako obavijest na dnu smo
imaju lokalnu varijablu bar.

581
00:26:53,470 --> 00:26:57,330
Tako da pokazivač da će store--
umjesto da lokalne argument koji je

582
00:26:57,330 --> 00:26:58,672
će pohraniti string bar.

583
00:26:58,672 --> 00:27:00,380
A onda primijetiti samo
iznad njega u snopu,

584
00:27:00,380 --> 00:27:02,505
jer svaki put kad pitam
za sjećanje na dimnjaku,

585
00:27:02,505 --> 00:27:04,310
to ide malo
iznad njega slikovito,

586
00:27:04,310 --> 00:27:06,270
Obavijest da imamo 12 bajtova tamo.

587
00:27:06,270 --> 00:27:10,690
Gornja lijeva jedna je C nosač nula i
donji desni je C nosač 11.

588
00:27:10,690 --> 00:27:12,870
To je samo način na koji računala
će ga nokautirati.

589
00:27:12,870 --> 00:27:18,300
Dakle, samo intuitivno, ako bar ima više
od 12 znakova ukupno, uključujući

590
00:27:18,300 --> 00:27:25,790
obrnute kose crte nula, gdje je
12 ili C nosač 12 ići?

591
00:27:25,790 --> 00:27:28,440
Ili, bolje rečeno, gdje je 12.
lik ili 13. znak,

592
00:27:28,440 --> 00:27:30,900
stoti lik ide
završiti na slici?

593
00:27:30,900 --> 00:27:33,400
Iznad ili ispod?

594
00:27:33,400 --> 00:27:36,300
>> Točno, jer iako
sama stog raste prema gore,

595
00:27:36,300 --> 00:27:39,590
nakon što ste stavili stvari u
da, to za dizajn razloga,

596
00:27:39,590 --> 00:27:41,294
stavlja memoriju od vrha do dna.

597
00:27:41,294 --> 00:27:44,460
Dakle, ako imate više od 12 bajtova,
da ćeš početi prepisati bar.

598
00:27:44,460 --> 00:27:47,280
A da je bug, ali to je
zapravo i nije velika stvar.

599
00:27:47,280 --> 00:27:51,130
Ali, to je velika stvar, jer je
više stvari događa u memoriji.

600
00:27:51,130 --> 00:27:53,074
Pa evo kako smo mogli
stavi Pozdrav, da bude jasno.

601
00:27:53,074 --> 00:27:54,490
Ako sam upisali u Hello na redak.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash nula, završava unutar
ti 12 bajtova, a mi smo super sigurno.

603
00:27:59,330 --> 00:28:00,330
Sve je dobro.

604
00:28:00,330 --> 00:28:03,020
Ali ako upišete nešto
više, potencijalno je

605
00:28:03,020 --> 00:28:05,860
će se uvlače u razmaknice.

606
00:28:05,860 --> 00:28:08,405
Ali još gore, ispada
sve ovo vrijeme,

607
00:28:08,405 --> 00:28:11,530
iako nikad nismo razgovarali o
je, snop se koristi za druge stvari.

608
00:28:11,530 --> 00:28:13,560
To je ne samo lokalne varijable.

609
00:28:13,560 --> 00:28:15,100
>> C je vrlo niska razina jezika.

610
00:28:15,100 --> 00:28:17,810
I to vrsta potajno
koristi snop također

611
00:28:17,810 --> 00:28:21,260
zapamtiti kada
Funkcija se zove, ono

612
00:28:21,260 --> 00:28:26,040
je adresa od prethodne funkcije,
tako da može skočiti natrag na tu funkciju.

613
00:28:26,040 --> 00:28:29,980
Dakle, kada glavni pozivi zamijeniti, među
stvari gurnula na stog

614
00:28:29,980 --> 00:28:34,380
nisu samo swaps lokalne varijable,
ili njegovi argumenti, također potajno gurnula

615
00:28:34,380 --> 00:28:37,510
na stog kao što je prikazano
crveni kriška ovdje

616
00:28:37,510 --> 00:28:40,520
je adresa glavni fizički
u memoriji računala,

617
00:28:40,520 --> 00:28:44,180
tako da kad zamjena je učinio, računalo
zna Moram se vratiti u glavni

618
00:28:44,180 --> 00:28:46,760
i završiti izvršavanju glavnu funkciju.

619
00:28:46,760 --> 00:28:51,960
Dakle, to je opasno i sada, jer ako
korisnik upisuje u i više od hello,

620
00:28:51,960 --> 00:28:57,030
kao da korisnikov unos clobbers
ili prebrisati taj crveni dio,

621
00:28:57,030 --> 00:28:59,820
logično ako je računalo je
Samo će slijepo pretpostaviti

622
00:28:59,820 --> 00:29:03,830
da bajtova u tom crvenom kriška su
adresa na koju se treba vratiti,

623
00:29:03,830 --> 00:29:09,020
što ako protivnik je dovoljno pametan ili
dovoljno sretan da stavi niz bajtova

624
00:29:09,020 --> 00:29:13,450
tamo izgleda kao adresu,
ali to je adresa koda

625
00:29:13,450 --> 00:29:18,730
da on ili ona želi računalo
izvršiti umjesto glavni?

626
00:29:18,730 --> 00:29:21,670
>> Drugim riječima, ako je ono što je
Korisnik piše na upit,

627
00:29:21,670 --> 00:29:23,850
nije samo nešto
bezazleno kao zdravo,

628
00:29:23,850 --> 00:29:28,210
ali to je zapravo kod koji je ekvivalent
izbrisati sve ove korisnikovih datoteka?

629
00:29:28,210 --> 00:29:30,060
Ili e-mail lozinke za mene?

630
00:29:30,060 --> 00:29:31,940
Ili početi prijavom njihova
tipke, zar ne?

631
00:29:31,940 --> 00:29:34,920
Postoji način, neka je propisano i danas,
da bi mogli upisati ne samo pozdravi

632
00:29:34,920 --> 00:29:36,711
Svijet i njihovo ime,
su mogli bitno

633
00:29:36,711 --> 00:29:39,570
proći kod, nula i
one, da računalo

634
00:29:39,570 --> 00:29:43,450
grešaka za oba koda i adrese.

635
00:29:43,450 --> 00:29:48,950
Dakle, iako pomalo apstraktno, ako je
korisnik upiše u dovoljno kontradiktornosti kod

636
00:29:48,950 --> 00:29:52,330
da ćemo generalizirati ovdje
A. je napad ili protivnici.

637
00:29:52,330 --> 00:29:53,140
Dakle, samo loše stvari.

638
00:29:53,140 --> 00:29:55,306
Mi ne briga o
brojeva ili nula ili one

639
00:29:55,306 --> 00:29:59,470
danas, tako da ćete završiti
prepisati taj crveni dio,

640
00:29:59,470 --> 00:30:01,580
primijetiti da je slijed bajtova.

641
00:30:01,580 --> 00:30:05,020
O 835 C nula osam nula.

642
00:30:05,020 --> 00:30:08,960
I sada kao Wikipedia članak je ovdje
predlaže, ako se sada zapravo početi

643
00:30:08,960 --> 00:30:12,460
označavanje bajtova u vašem računalu
memorije, što je Wikipedia članak je

644
00:30:12,460 --> 00:30:19,060
predlaganje je da, što ako je adresa
tog gornjem lijevom bajta je 80 ° C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Drugim riječima, ako je negativac je
dovoljno pametan sa svojim kodom

646
00:30:22,200 --> 00:30:26,650
zapravo staviti ovdje broj koji
odgovara na adresu koda

647
00:30:26,650 --> 00:30:29,180
on ili ona ubrizgava
u računalo,

648
00:30:29,180 --> 00:30:31,050
može izigrati računalo
u radi ništa.

649
00:30:31,050 --> 00:30:34,140
Uklanjanje datoteka, slanje e
stvari, njuškanje prometa,

650
00:30:34,140 --> 00:30:36,710
doslovno ništa mogao biti
ubrizgava u računalo.

651
00:30:36,710 --> 00:30:39,220
I tako buffer overflow
Napad u svojoj srži

652
00:30:39,220 --> 00:30:43,530
samo je glupo, glupo
Najvažniji od niza koji

653
00:30:43,530 --> 00:30:45,840
nisu imali njegove granice provjeriti.

654
00:30:45,840 --> 00:30:48,850
I to je ono što je super opasan
i istovremeno super moćan

655
00:30:48,850 --> 00:30:52,560
u C je da smo doista nemamo
pristup bilo gdje u memoriji.

656
00:30:52,560 --> 00:30:55,320
To je do nas, programeri,
koji pišu izvorni kod

657
00:30:55,320 --> 00:30:59,330
provjeriti duljinu darn bilo
polja koje smo manipulira.

658
00:30:59,330 --> 00:31:00,750
Dakle, da bude jasno, što je popravak?

659
00:31:00,750 --> 00:31:03,190
Ako smo vratiti na ovo
kod, ne samo treba

660
00:31:03,190 --> 00:31:08,000
promijenili duljinu trake, što
inače bih se provjera?

661
00:31:08,000 --> 00:31:10,620
Što još trebam raditi na
spriječilo ovaj napad u potpunosti?

662
00:31:10,620 --> 00:31:14,110
Ne želim da samo slijepo reći
koje bi trebali kopirati što više bajtova

663
00:31:14,110 --> 00:31:16,140
kao što je dužina trake.

664
00:31:16,140 --> 00:31:18,910
Želim reći, kopirati kao
mnogi bajtova što su u baru

665
00:31:18,910 --> 00:31:24,090
do dodijeljeni
memorije, ili 12 maksimalno.

666
00:31:24,090 --> 00:31:27,450
Dakle, trebam nekakav ako stanje
koji radi provjeriti duljinu trake,

667
00:31:27,450 --> 00:31:32,800
ali ako prelazi 12, samo tvrdi kôd
12 što u najvećoj mogućoj udaljenosti.

668
00:31:32,800 --> 00:31:35,910
Inače tzv pufer
overflow napad može dogoditi.

669
00:31:35,910 --> 00:31:38,451
Na dnu tih slajdova,
Ako ste znatiželjan to opširnije

670
00:31:38,451 --> 00:31:41,200
je stvarni izvorni članak
Ako želite pogledati.

671
00:31:41,200 --> 00:31:44,550
>> Ali sada, među cijene
plaćeni ovdje bio neučinkovitosti.

672
00:31:44,550 --> 00:31:46,680
Tako da je brz
niska razina pogled na ono što

673
00:31:46,680 --> 00:31:49,709
problemi mogu nastati sada da smo
imati pristup memoriji računala.

674
00:31:49,709 --> 00:31:51,750
No, još jedan problem smo
Već je posrnuo u ponedjeljak

675
00:31:51,750 --> 00:31:53,800
je samo neučinkovitost
popisa povezane.

676
00:31:53,800 --> 00:31:56,019
Mi smo natrag u linearnom vremenu.

677
00:31:56,019 --> 00:31:57,560
Mi više ne imati granični niz.

678
00:31:57,560 --> 00:31:58,980
Nemamo slučajni pristup.

679
00:31:58,980 --> 00:32:00,710
Ne možemo koristiti uglata zagrada zapis.

680
00:32:00,710 --> 00:32:04,590
Mi smo doslovno morati koristiti while petlja
poput onoga što sam napisao maloprije.

681
00:32:04,590 --> 00:32:09,740
No, u ponedjeljak, tvrdili smo da možemo
puzanje natrag u carstvo učinkovitosti

682
00:32:09,740 --> 00:32:13,040
postizanje nešto što je
logaritamska možda, ili najbolje još,

683
00:32:13,040 --> 00:32:16,120
možda čak i nešto što je
Takozvani konstanta vrijeme.

684
00:32:16,120 --> 00:32:19,840
Pa kako možemo učiniti da pomoću ove nove
alati, ove adrese, ove naputke,

685
00:32:19,840 --> 00:32:22,210
i navoja stvari vlastitih?

686
00:32:22,210 --> 00:32:23,960
Pa, pretpostavimo da
ovdje su hrpa

687
00:32:23,960 --> 00:32:27,170
brojeva koje želite pohraniti u
Struktura i traženje podataka učinkovito.

688
00:32:27,170 --> 00:32:30,960
Mi apsolutno može premotati u tjedan
dva, baciti ih u polje,

689
00:32:30,960 --> 00:32:33,150
te ih pretraživati ​​pomoću binarnog pretraživanja.

690
00:32:33,150 --> 00:32:34,040
Podijeli pa vladaj.

691
00:32:34,040 --> 00:32:37,720
A u stvari si napisao
binarno pretraživanje u PSET3,

692
00:32:37,720 --> 00:32:40,100
gdje se provodi za traženje programa.

693
00:32:40,100 --> 00:32:40,890
Ali znate što.

694
00:32:40,890 --> 00:32:45,060
Postoji vrsta više
pametan način za to.

695
00:32:45,060 --> 00:32:47,390
To je malo više
sofisticiran i to možda

696
00:32:47,390 --> 00:32:50,830
omogućuje nam da vidimo zašto je binarni
traži toliko puno brže.

697
00:32:50,830 --> 00:32:52,980
Prvo, neka je uvesti
pojam stabla.

698
00:32:52,980 --> 00:32:54,730
Koji iako u
stvarnost drveće vrsta

699
00:32:54,730 --> 00:32:57,730
rastu ovako, u svijetu računala
znanost se vrsta raste prema dolje

700
00:32:57,730 --> 00:33:00,830
poput stabla, gdje imate
Vaši djedovi ili bake i djedovi velik

701
00:33:00,830 --> 00:33:04,580
ili sitnica na vrhu, patrijarha i
matriarch obitelji, samo jedan

702
00:33:04,580 --> 00:33:07,930
Takozvani korijen, čvor, ispod
koji su njegovi sinovi,

703
00:33:07,930 --> 00:33:11,442
ispod kojeg su njegovi sinovi, ili
njegovi potomci općenito.

704
00:33:11,442 --> 00:33:13,400
A tko visi
dno obitelji

705
00:33:13,400 --> 00:33:16,070
stabla, osim što je
najmlađi u obitelji,

706
00:33:16,070 --> 00:33:19,520
može biti samo generički
zove lišće stabla.

707
00:33:19,520 --> 00:33:21,800
>> Dakle, ovo je samo hrpa
riječi i definicija

708
00:33:21,800 --> 00:33:25,790
za nešto što se zove stablo u računalu
znanost, baš kao obiteljsko stablo.

709
00:33:25,790 --> 00:33:28,770
No, tu je ljubitelj inkarnacija
stabala, od kojih je jedan

710
00:33:28,770 --> 00:33:30,780
se zove pretraživanje po binarnom stablu.

711
00:33:30,780 --> 00:33:34,380
A možete vrsta zafrkavati
Osim što je ova stvar radi.

712
00:33:34,380 --> 00:33:37,180
Pa, to je binarna u kojem smislu?

713
00:33:37,180 --> 00:33:41,455
Odakle binarni dolazi odavde?

714
00:33:41,455 --> 00:33:41,955
Žao nam je?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
To nije toliko bilo ili.

717
00:33:47,210 --> 00:33:52,000
To je još da svaki od čvorova nema
više od dvoje djece, kao što smo vidjeli ovdje.

718
00:33:52,000 --> 00:33:54,990
Općenito, tree-- i
tvoji roditelji i djedovi

719
00:33:54,990 --> 00:33:57,640
može imati onoliko djece ili
grandkids što oni zapravo žele,

720
00:33:57,640 --> 00:34:00,820
pa primjerice tu imamo tri
djeca gola koja desnoj čvor,

721
00:34:00,820 --> 00:34:05,480
ali u binarnom stablu, čvor ima
nula, jedan ili dvoje djece najvi.

722
00:34:05,480 --> 00:34:08,496
I to je lijepo svojstvo,
jer ako se to poklopi s dva,

723
00:34:08,496 --> 00:34:10,620
ćemo moći
dobiti malo log bazu dva

724
00:34:10,620 --> 00:34:11,975
akcija događa ovdje u konačnici.

725
00:34:11,975 --> 00:34:13,350
Dakle, imamo nešto logaritamske.

726
00:34:13,350 --> 00:34:14,558
No, više o tome u ovom trenutku.

727
00:34:14,558 --> 00:34:19,810
Traži stablo znači da su brojevi
postavljeni tako da lijevi djeteta

728
00:34:19,810 --> 00:34:22,429
vrijednost je veća od korijena.

729
00:34:22,429 --> 00:34:26,010
A svoje pravo dijete
veći od korijena.

730
00:34:26,010 --> 00:34:29,290
Drugim riječima, ako se bilo što od
čvorovi, krugovi u ovoj slici,

731
00:34:29,290 --> 00:34:31,840
i izgleda na svojoj lijevoj
Dijete i njegova pravo djeteta,

732
00:34:31,840 --> 00:34:34,739
prvi bi trebao biti manji od,
drugi bi trebao biti veći od.

733
00:34:34,739 --> 00:34:36,159
Dakle, razum provjeriti 55.

734
00:34:36,159 --> 00:34:37,780
To je napustio dijete je 33.

735
00:34:37,780 --> 00:34:38,620
To je manje od.

736
00:34:38,620 --> 00:34:40,929
55, svoje pravo dijete 77.

737
00:34:40,929 --> 00:34:41,783
To je veći od.

738
00:34:41,783 --> 00:34:43,199
I to je rekurzivna definicija.

739
00:34:43,199 --> 00:34:46,480
Možemo provjeriti svaki od tih
čvorovi i isti uzorak bi držati.

740
00:34:46,480 --> 00:34:49,389
>> Dakle, ono što je lijepo u
pretraživanje po binarnom stablu, je

741
00:34:49,389 --> 00:34:52,204
da jedan, možemo ga provesti
s STRUCT, baš kao i ova.

742
00:34:52,204 --> 00:34:54,620
I iako smo bacanje
puno objekata na svoje,

743
00:34:54,620 --> 00:34:56,560
oni su nešto
Sada intuitivno nadamo.

744
00:34:56,560 --> 00:35:00,570
Sintaksa je uvijek Arcane sigurno,
ali sadržaj čvor u ovoj

745
00:35:00,570 --> 00:35:02,786
context-- i držimo
koristim riječ čvor,

746
00:35:02,786 --> 00:35:04,910
da li je pravokutnik
na zaslonu ili krug,

747
00:35:04,910 --> 00:35:08,970
to je samo neki generički kontejner,
u ovom slučaju drvo, kao što je onaj

748
00:35:08,970 --> 00:35:11,780
Vidjeli smo, moramo cijeli broj
u svakoj od čvorova

749
00:35:11,780 --> 00:35:15,460
a onda moram dva ptičara koji upućuju
na lijevoj djeteta i pravo djeteta,

750
00:35:15,460 --> 00:35:16,590
respektivno.

751
00:35:16,590 --> 00:35:20,730
Dakle, to je kako bismo mogli
provesti kako u Struct.

752
00:35:20,730 --> 00:35:22,315
A kako bi moglo da ga provede u kodu?

753
00:35:22,315 --> 00:35:26,730
Pa, neka je uzme brz
pogledajte ovaj mali primjer.

754
00:35:26,730 --> 00:35:29,820
To nije funkcionalna, ali sam
kopirati i zalijepiti tu strukturu.

755
00:35:29,820 --> 00:35:33,510
I ako moj funkcija za binarnom
traži stablo zove pretraživanje,

756
00:35:33,510 --> 00:35:36,980
i to traje dva argumenta,
cijeli broj N i pokazivač

757
00:35:36,980 --> 00:35:41,400
u čvor, pa pokazivač na stablu
ili pokazivač na korijen stabla,

758
00:35:41,400 --> 00:35:43,482
Kako mogu ići o potrazi za N?

759
00:35:43,482 --> 00:35:45,440
Pa, prvo, zato što sam
bave pokazivače,

760
00:35:45,440 --> 00:35:46,750
Ja ću učiniti ček razum.

761
00:35:46,750 --> 00:35:54,279
Ako stabla jednaka jednaka null, N
u ovom stablu ili ne u ovom stablu?

762
00:35:54,279 --> 00:35:55,070
To ne može biti, zar ne?

763
00:35:55,070 --> 00:35:56,870
Ako sam pokraj null,
nema ničega.

764
00:35:56,870 --> 00:35:59,230
Ja možda i samo
slijepo reći return false.

765
00:35:59,230 --> 00:36:04,050
Ako mi ne daju ništa, ja sigurno ne mogu
pronaći bilo koji broj N. Pa što drugi možda sam

766
00:36:04,050 --> 00:36:04,750
provjeri sada?

767
00:36:04,750 --> 00:36:12,830
Ja ću reći i drugo, ako je N
manje nego ono što je na stablu čvor

768
00:36:12,830 --> 00:36:16,300
da sam bio predao N vrijednosti.

769
00:36:16,300 --> 00:36:20,270
Drugim riječima, ako je broj sam
tražite, N, manji od čvora

770
00:36:20,270 --> 00:36:21,340
da gledam.

771
00:36:21,340 --> 00:36:23,190
A čvor tražim
na se zove stablo,

772
00:36:23,190 --> 00:36:26,370
i sjećam iz prethodnog primjera
dobiti na vrijednosti u pokazivač,

773
00:36:26,370 --> 00:36:28,310
Koristim strelicom zapis.

774
00:36:28,310 --> 00:36:35,960
Dakle, ako je N manji od stabla strelice
N, želim konceptualno ide lijevo.

775
00:36:35,960 --> 00:36:38,590
Kako izražavam potrazi otišao?

776
00:36:38,590 --> 00:36:41,560
Da bude jasno, ako je to
slika u pitanju,

777
00:36:41,560 --> 00:36:44,612
i ja sam prošao taj najviši
strelica koja se pokazuje prema dolje.

778
00:36:44,612 --> 00:36:45,570
To je moje drvo pokazivač.

779
00:36:45,570 --> 00:36:48,060
Ja sam pokazujući na korijen stabla.

780
00:36:48,060 --> 00:36:52,100
I tražim recimo, za
broj 44, proizvoljno.

781
00:36:52,100 --> 00:36:55,300
Je li 44 ili manje od
veći od 55 očito?

782
00:36:55,300 --> 00:36:56,360
Tako da je manje od.

783
00:36:56,360 --> 00:36:58,760
I tako to, ako uvjet vrijedi.

784
00:36:58,760 --> 00:37:03,981
Pa koncepcijski, ono što želim
Pretražite Sljedeći ako tražim 44?

785
00:37:03,981 --> 00:37:04,480
Da?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Točno, želim
Pretražite lijevu dijete,

788
00:37:11,100 --> 00:37:12,789
ili ulijevo pod-stablo ovu sliku.

789
00:37:12,789 --> 00:37:14,830
A u stvari, pustite me da prođem
slika ovdje

790
00:37:14,830 --> 00:37:17,770
samo na trenutak, jer
Ne mogu ispočetka ovo.

791
00:37:17,770 --> 00:37:21,150
Ako počnem ovdje u 55, i
Znam da je vrijednost 44

792
00:37:21,150 --> 00:37:23,180
Tražim je da
lijeva, to je vrsta

793
00:37:23,180 --> 00:37:26,010
poput suzenje telefonski imenik u
pola ili suzenje stabla na pola.

794
00:37:26,010 --> 00:37:29,660
Ja više ne moraju brinuti o
Cijeli ovaj pola stabla.

795
00:37:29,660 --> 00:37:33,270
A ipak, začudo u smislu
Struktura, ova stvar ovdje da

796
00:37:33,270 --> 00:37:36,682
počinje s 33, koji sebi
je pretraživanje po binarnom stablu.

797
00:37:36,682 --> 00:37:39,890
Rekao sam da je riječ rekurzivna prije, jer
Doista to je struktura podataka koji

798
00:37:39,890 --> 00:37:41,707
po definiciji je rekurzivna.

799
00:37:41,707 --> 00:37:44,540
Možda ste stablo koje je ovo
velika, ali svaki od njegovih djece

800
00:37:44,540 --> 00:37:46,870
predstavlja stablo samo malo manji.

801
00:37:46,870 --> 00:37:50,910
Umjesto toga se djeda
ili baka, sada je samo mama

802
00:37:50,910 --> 00:37:54,300
or-- Ne mogu ne say-- mama
ili tata, koji će biti čudno.

803
00:37:54,300 --> 00:37:59,000
Umjesto dvoje djece tamo
bi bilo kao brata i sestru.

804
00:37:59,000 --> 00:38:01,120
Nova generacija obiteljskog stabla.

805
00:38:01,120 --> 00:38:02,900
Ali strukturno, to je ista ideja.

806
00:38:02,900 --> 00:38:06,790
I ispada da imam funkciju
s kojima mogu potražiti binarnu pretragu

807
00:38:06,790 --> 00:38:07,290
stablo.

808
00:38:07,290 --> 00:38:08,680
To se zove pretraživanja.

809
00:38:08,680 --> 00:38:17,870
Tražim N u stablo strelice lijevo
inače ako je n veći od vrijednosti

810
00:38:17,870 --> 00:38:18,870
da sam trenutno.

811
00:38:18,870 --> 00:38:20,800
55 u priči trenutak prije.

812
00:38:20,800 --> 00:38:23,780
Imam funkciju pod nazivom
traži da ja mogu jednostavno

813
00:38:23,780 --> 00:38:29,660
prođe N ovo i rekurzivno pretragu
pod-stablo i samo povratak

814
00:38:29,660 --> 00:38:30,620
što god da je odgovor.

815
00:38:30,620 --> 00:38:33,530
Inače imam neku konačnu bazu slučaj ovdje.

816
00:38:33,530 --> 00:38:35,310
>> Što je konačni slučaj?

817
00:38:35,310 --> 00:38:36,570
Stablo je bilo nula.

818
00:38:36,570 --> 00:38:39,980
Vrijednost sam bilo tražite
manji od njega, ili veći od onog

819
00:38:39,980 --> 00:38:42,610
ili jednak tome.

820
00:38:42,610 --> 00:38:44,750
I moglo bi se reći jednaka
jednaka, ali logično je

821
00:38:44,750 --> 00:38:46,500
ekvivalent za samo govoreći ostalo ovdje.

822
00:38:46,500 --> 00:38:49,150
Dakle, istina je kako sam naći nešto.

823
00:38:49,150 --> 00:38:51,710
Dakle, nadam se da je to
još uvjerljiv primjer

824
00:38:51,710 --> 00:38:54,900
nego glupog funkciji sigma
smo nekoliko predavanja natrag,

825
00:38:54,900 --> 00:38:58,360
gdje je jednako lako koristiti petlju
brojati sve brojeve iz jednog

826
00:38:58,360 --> 00:39:02,390
N. ovdje sa strukturom podataka
koja je sama po sebi rekurzivno

827
00:39:02,390 --> 00:39:07,050
definirati i rekurzivno nacrtana, sada smo
imaju sposobnost da se izrazim

828
00:39:07,050 --> 00:39:09,780
u kodu koji je sam po sebi rekurzivna.

829
00:39:09,780 --> 00:39:12,580
Dakle, to je isti broj ovdje.

830
00:39:12,580 --> 00:39:14,400
>> Dakle, ono što drugi problemi mogu se riješiti?

831
00:39:14,400 --> 00:39:18,160
Tako brz korak od
Stabla za samo trenutak.

832
00:39:18,160 --> 00:39:20,130
Evo, recimo, njemački zastavu.

833
00:39:20,130 --> 00:39:22,020
I tu je jasno
Uzorak ovom zastavom.

834
00:39:22,020 --> 00:39:23,811
A tu je puno
zastave u svijetu koji

835
00:39:23,811 --> 00:39:27,560
kao jednostavan kao ovaj u smislu
njihovih boja i uzoraka.

836
00:39:27,560 --> 00:39:31,930
Ali pretpostavljam da je to čuvati kao
.GIF Ili JPEG ili Bitmap ili ping,

837
00:39:31,930 --> 00:39:34,240
bilo grafički format datoteke
s kojima ste upoznati,

838
00:39:34,240 --> 00:39:36,460
od kojih smo
igranje s u PSET4.

839
00:39:36,460 --> 00:39:41,550
To se ne čini vrijedno pohraniti
crna piksela, crne piksela, crne piksela,

840
00:39:41,550 --> 00:39:44,790
točka, točka, točka, cijela hrpa
crni pikseli za prvi scanline,

841
00:39:44,790 --> 00:39:47,430
ili red, onda cijela hrpa
isti, onda cijela hrpa

842
00:39:47,430 --> 00:39:49,530
istog, a zatim
cijela hrpa crvenih piksela,

843
00:39:49,530 --> 00:39:53,020
crvena piksela, crvene piksela, onda cijeli
gomila žutih piksela, žuta, zar ne?

844
00:39:53,020 --> 00:39:55,050
>> Postoji takva neučinkovitost ovdje.

845
00:39:55,050 --> 00:39:59,040
Kako biste intuitivno
stisnuti njemačku zastavu

846
00:39:59,040 --> 00:40:01,320
ako ga provodi kao datoteku?

847
00:40:01,320 --> 00:40:04,940
Kao što informacije ne možemo
gnjaviti spremanje na disk kako

848
00:40:04,940 --> 00:40:08,040
smanjiti našu veličinu iz poput
megabajt u kilobajt, nešto

849
00:40:08,040 --> 00:40:09,430
manja?

850
00:40:09,430 --> 00:40:13,130
U kojoj leži zalihost
Ovdje se jasno?

851
00:40:13,130 --> 00:40:13,880
Što možete učiniti?

852
00:40:13,880 --> 00:40:14,380
Da?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Točno.

855
00:40:21,970 --> 00:40:24,550
Zašto se ne sjećam, a ne
boja svakog piksela prokleto

856
00:40:24,550 --> 00:40:28,200
baš kao što radite u PSET4
s formatom bitmap datoteke,

857
00:40:28,200 --> 00:40:32,060
zašto jednostavno ne predstavljaju
krajnjem lijevom stupcu piksela, primjerice

858
00:40:32,060 --> 00:40:35,370
hrpa crnih piksela, gomila
crvene i hrpa žute,

859
00:40:35,370 --> 00:40:39,210
i onda samo nekako kodiraju
Ideja Ponovite ovaj 100 puta

860
00:40:39,210 --> 00:40:41,020
ili ponovite 1000 puta?

861
00:40:41,020 --> 00:40:43,430
Gdje 100 ili 1000 je
samo cijeli broj, pa vas

862
00:40:43,430 --> 00:40:47,290
može dobiti daleko sa samo jednim brojem
umjesto stotina ili tisuća

863
00:40:47,290 --> 00:40:48,270
dodatnih piksela.

864
00:40:48,270 --> 00:40:50,990
I doista, to je kako smo
mogao stisnuti njemačku zastavu.

865
00:40:50,990 --> 00:40:51,490
I

866
00:40:51,490 --> 00:40:53,470
A što je s francuskom zastavom?

867
00:40:53,470 --> 00:40:58,930
I malo neka vrsta
mentalne vježbe, koja zastava

868
00:40:58,930 --> 00:41:01,040
može se sažeti više na disku?

869
00:41:01,040 --> 00:41:05,720
Njemačka zastava ili francuski
zastava, ako uzmemo da je pristup?

870
00:41:05,720 --> 00:41:08,490
Njemačka zastava, jer je
više horizontalna zalihost.

871
00:41:08,490 --> 00:41:12,190
I po dizajnu, mnogi grafički datotečni
formati doista rade linije kao skeniranje

872
00:41:12,190 --> 00:41:12,830
vodoravno.

873
00:41:12,830 --> 00:41:14,674
Mogli su raditi
vertikalno, samo čovječanstvo

874
00:41:14,674 --> 00:41:17,090
Prije odlučili godina da ćemo
općenito mislim da stvari zaredom

875
00:41:17,090 --> 00:41:18,880
po red umjesto stupca strane stupca.

876
00:41:18,880 --> 00:41:20,820
Dakle, doista, ako ste bili
pogledati datoteke

877
00:41:20,820 --> 00:41:24,670
Veličina njemačkom zastavom i francuski
zastava, tako dugo dok je razlučivost

878
00:41:24,670 --> 00:41:27,530
isti, iste širine
i visina, to je jedan

879
00:41:27,530 --> 00:41:31,580
Ovdje će biti veći, jer vas
moraju sami ponoviti tri puta.

880
00:41:31,580 --> 00:41:35,570
Morate navesti plave, ponavljanje
sebe, bijela, ponavljam se, crvena,

881
00:41:35,570 --> 00:41:36,740
Ponavljam se.

882
00:41:36,740 --> 00:41:39,000
Vi ne možete samo ići sve
put u desno.

883
00:41:39,000 --> 00:41:41,200
I usput, da bi
jasno kompresije

884
00:41:41,200 --> 00:41:43,910
je svugdje, ako su
Četiri okviri iz video-- ste

885
00:41:43,910 --> 00:41:45,890
možda podsjetiti da je film
ili video općenito

886
00:41:45,890 --> 00:41:47,286
kao i 29 ili 30 sličica u sekundi.

887
00:41:47,286 --> 00:41:50,410
To je kao malo flip knjigu u kojoj vas
samo vidjeti slike, slike, slike, slike,

888
00:41:50,410 --> 00:41:54,410
Slika samo super brzo, tako da izgleda kao
glumci na zaslonu se kreće.

889
00:41:54,410 --> 00:41:57,130
Evo bumbar na
vrh hrpa cvijeća.

890
00:41:57,130 --> 00:41:59,790
I iako bi to moglo biti vrsta
teško je vidjeti na prvi pogled,

891
00:41:59,790 --> 00:42:04,020
jedino što se kreće u
ovaj film je pčela.

892
00:42:04,020 --> 00:42:06,880
>> Što je nijem o spremanju
Video komprimirana?

893
00:42:06,880 --> 00:42:11,420
To je vrsta otpada za pohranu videa
kao četiri gotovo identične slike koje

894
00:42:11,420 --> 00:42:13,670
razlikuju samo utoliko što, gdje pčela je.

895
00:42:13,670 --> 00:42:16,280
Možete baciti većinu
tih informacija

896
00:42:16,280 --> 00:42:20,190
i zapamtiti samo na primjer,
prvi okvir i posljednji kadar,

897
00:42:20,190 --> 00:42:22,180
Ključni okviri, ako ste
ikada čuli tu riječ,

898
00:42:22,180 --> 00:42:24,337
i samo pohraniti u
Srednji gdje pčela je.

899
00:42:24,337 --> 00:42:26,170
A vi ne morate
pohraniti sve ružičastoj,

900
00:42:26,170 --> 00:42:28,330
i plava, a
zelene vrijednosti kao dobro.

901
00:42:28,330 --> 00:42:31,200
Dakle, ovo je samo reći da
Kompresija je posvuda.

902
00:42:31,200 --> 00:42:34,900
To je tehnika često se koriste
ili uzeti zdravo za gotovo ovih dana.

903
00:42:34,900 --> 00:42:38,750
>> Ali kako stisnuti tekst?

904
00:42:38,750 --> 00:42:40,450
Kako idete o sažimanje teksta?

905
00:42:40,450 --> 00:42:45,410
Pa, svaki od likova u
Ascii je jedan bajt ili osam bitova.

906
00:42:45,410 --> 00:42:47,360
I to je vrsta glupo, zar ne?

907
00:42:47,360 --> 00:42:51,160
Jer vjerojatno tip A
i E i ja i O i U mnogo

908
00:42:51,160 --> 00:42:55,270
češće nego poput W ili P ili Z,
ovisno o jeziku na kojem

909
00:42:55,270 --> 00:42:56,610
pišete sigurno.

910
00:42:56,610 --> 00:42:59,600
I zašto smo koristeći
osam bitova za svaku riječ,

911
00:42:59,600 --> 00:43:02,040
uključujući najmanje
Popularni slova, zar ne?

912
00:43:02,040 --> 00:43:05,300
Zašto ne koristiti manje bitova za
super popularne slova,

913
00:43:05,300 --> 00:43:07,760
kao i E, ono što pretpostavljam
prvi u Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
i koristiti više bitova za
manje popularne slova?

915
00:43:10,450 --> 00:43:10,950
Zašto?

916
00:43:10,950 --> 00:43:13,130
Jer samo ćemo se
koristiti ih rjeđe.

917
00:43:13,130 --> 00:43:15,838
>> Pa, ispada da tamo ima
bili pokušaji napravljeni da to učinite.

918
00:43:15,838 --> 00:43:18,630
A ako se sjećate iz razreda
školu ili srednju školu, Morseov kod.

919
00:43:18,630 --> 00:43:20,400
Morseov kod ima točkice
i crtice koje mogu biti

920
00:43:20,400 --> 00:43:24,270
prenosi duž žice kao
zvukova ili signali neke vrste.

921
00:43:24,270 --> 00:43:25,930
No, Morseov kod je super čist.

922
00:43:25,930 --> 00:43:29,010
To je vrsta binarnog sustava
da imate točkice ili crtice.

923
00:43:29,010 --> 00:43:30,977
Ali ako vidite, na primjer, dvije točkice.

924
00:43:30,977 --> 00:43:33,810
Ili ako mislite natrag operatera
koji ide ovako bip bip, bip,,

925
00:43:33,810 --> 00:43:36,760
zvučni signal, udaranje malo okidač
koji prenosi signal,

926
00:43:36,760 --> 00:43:40,360
Ako vi kao primatelj prima dvije
točkice, koju poruku ste dobili?

927
00:43:40,360 --> 00:43:43,490
Potpuno proizvoljna.

928
00:43:43,490 --> 00:43:44,450
>> Ja?

929
00:43:44,450 --> 00:43:45,060
Ja?

930
00:43:45,060 --> 00:43:47,500
Ili što about-- ili ne?

931
00:43:47,500 --> 00:43:49,570
Možda je to samo dvije e je u pravu?

932
00:43:49,570 --> 00:43:52,480
Tako je ovaj problem
od decodability s Morse

933
00:43:52,480 --> 00:43:54,890
kod, pri čemu osim ako
Osoba slanja poruke

934
00:43:54,890 --> 00:43:59,510
zapravo zaustavlja tako da možete sortirati od
vidjeti ili čuti razlike između pojedinih slova,

935
00:43:59,510 --> 00:44:02,990
to nije dovoljno samo
pošalji strujom nula i jedinica,

936
00:44:02,990 --> 00:44:05,610
ili točkice i crtice,
jer ima nejasnoća.

937
00:44:05,610 --> 00:44:08,640
E je jedna točka, pa ako vas
vidjeti dvije točkice ili čuti dvije točkice,

938
00:44:08,640 --> 00:44:11,254
možda je dva E-a ili je to možda jedan I.

939
00:44:11,254 --> 00:44:13,670
Dakle, trebamo sustav koji je
malo pametniji od toga.

940
00:44:13,670 --> 00:44:16,851
Dakle, čovjek po imenu Huffman godina
Prije smislio upravo to.

941
00:44:16,851 --> 00:44:18,600
Dakle, samo ćemo
uzeti brz pogled

942
00:44:18,600 --> 00:44:20,114
kako su stabla tijesnoj na to.

943
00:44:20,114 --> 00:44:22,530
Smatram da je to neki
glupo poruku koju želite poslati,

944
00:44:22,530 --> 00:44:26,342
sastavljen od samo A, B, C je D's i E-a,
ali ima puno redundancije ovdje.

945
00:44:26,342 --> 00:44:27,550
To nije značilo da se engleski.

946
00:44:27,550 --> 00:44:28,341
To nije šifrirana.

947
00:44:28,341 --> 00:44:30,540
To je samo glupa poruka
s mnogo ponavljanja.

948
00:44:30,540 --> 00:44:34,010
Dakle, ako ste zapravo računati iz svih
A-a, B-a, C-a, D's, i E je, ovdje je

949
00:44:34,010 --> 00:44:34,890
frekvencija.

950
00:44:34,890 --> 00:44:37,800
20% od slova
A je, 45% od slova

951
00:44:37,800 --> 00:44:39,660
su E, a tri druge frekvencije.

952
00:44:39,660 --> 00:44:41,960
Računali smo tamo ručno
i upravo učinio math.

953
00:44:41,960 --> 00:44:44,579
>> Tako ispada da je
Huffman, prije nekog vremena,

954
00:44:44,579 --> 00:44:46,620
shvatio da, znate
ono, ako sam početi graditi

955
00:44:46,620 --> 00:44:51,172
drvo ili šumu stabala, ako hoćete,
kao što slijedi, ja mogu učiniti sljedeće.

956
00:44:51,172 --> 00:44:53,880
Idem dati čvor na svakoj
od pisama koje mi je stalo

957
00:44:53,880 --> 00:44:55,530
i ja ću za pohranu
unutar tog čvora

958
00:44:55,530 --> 00:44:58,610
frekvencije kao pomičnim zarezom
vrijednost, ili možete koristiti N, također,

959
00:44:58,610 --> 00:45:00,210
ali ćemo samo koristiti plovak ovdje.

960
00:45:00,210 --> 00:45:03,100
A algoritam koji
predložio je da se

961
00:45:03,100 --> 00:45:07,210
iskoristiti ovu šumu jednog čvora
stabla, tako super kratke stabala,

962
00:45:07,210 --> 00:45:11,920
i početi ih povezuje s
nove skupine, novi roditelji, ako će.

963
00:45:11,920 --> 00:45:16,150
A vi to učiniti odabirom
Dva najmanja frekvencija u isto vrijeme.

964
00:45:16,150 --> 00:45:18,110
Zato sam uzeo 10% i 10%.

965
00:45:18,110 --> 00:45:19,090
Ja stvoriti novi čvor.

966
00:45:19,090 --> 00:45:20,910
I ja nazivam novi čvor 20%.

967
00:45:20,910 --> 00:45:22,750
>> Koje dvije čvorovi sam kombinirati sljedeće?

968
00:45:22,750 --> 00:45:23,810
To je malo nejasan.

969
00:45:23,810 --> 00:45:26,643
Dakle, postoji neki kutak slučajeve
uzeti u obzir, ali da bi stvari lijepe,

970
00:45:26,643 --> 00:45:29,300
Idem odabrati 20% -
Sada ignorirati djecu.

971
00:45:29,300 --> 00:45:33,640
Idem izabrati 20% i
15% i nacrtati dvije nove rubove.

972
00:45:33,640 --> 00:45:35,624
I sad su dva čvora
ja logično kombinirati?

973
00:45:35,624 --> 00:45:38,540
Zanemari sve djece, sve
unuci, samo pogledajte korijenima

974
00:45:38,540 --> 00:45:39,070
Sada.

975
00:45:39,070 --> 00:45:42,220
Koje dvije čvorovi mogu povezati?

976
00:45:42,220 --> 00:45:44,530
Točka dva i 0,35.

977
00:45:44,530 --> 00:45:45,890
Pa neka mi nacrtati dvije nove rubove.

978
00:45:45,890 --> 00:45:47,570
A onda sam dobio samo jedan lijevo.

979
00:45:47,570 --> 00:45:48,650
Dakle, ovdje je drvo.

980
00:45:48,650 --> 00:45:51,160
I to je bio nacrtan namjerno
gledati vrsta lijepa,

981
00:45:51,160 --> 00:45:55,870
ali primijetiti da rubovi moraju
Također su označeni nula i jedan.

982
00:45:55,870 --> 00:45:59,510
Dakle, svi su napustili rubova su nula
proizvoljno, ali dosljedno.

983
00:45:59,510 --> 00:46:01,170
Sve desni rub su one.

984
00:46:01,170 --> 00:46:05,070
>> I tako ono što Hoffman predložio je,
Ako želite predstavlja B,

985
00:46:05,070 --> 00:46:10,080
umjesto predstavlja broj 66 kao
ascii što je osam cijeli bita,

986
00:46:10,080 --> 00:46:13,360
Znaš što, samo dućan
uzorak nula, nula, nula,

987
00:46:13,360 --> 00:46:17,030
nula, jer to je put
iz mog stabla, gospodina Huffman je stablo,

988
00:46:17,030 --> 00:46:18,600
na list iz korijena.

989
00:46:18,600 --> 00:46:20,970
Ako želite pohraniti
E, s druge strane, ne

990
00:46:20,970 --> 00:46:26,290
pošalji osam bitova koji predstavljaju E.
Umjesto toga, pošaljite što uzorak bitova?

991
00:46:26,290 --> 00:46:26,890
Jedna.

992
00:46:26,890 --> 00:46:30,410
A što je lijepo o tome
da e je najpopularniji pismo,

993
00:46:30,410 --> 00:46:32,340
i da ste korištenjem
Najkraći kod za to.

994
00:46:32,340 --> 00:46:34,090
Sljedeći najpopularniji
Pismo izgleda kao da

995
00:46:34,090 --> 00:46:37,380
je A. I tako koliko bitova
je on predlaže pomoću za to?

996
00:46:37,380 --> 00:46:38,270
Nula, jedan.

997
00:46:38,270 --> 00:46:41,060
>> I zato što je proveden
kao ovog drveta, za sada

998
00:46:41,060 --> 00:46:43,350
neka mi propisuje postoji
nema dvosmislenosti kao u Morse

999
00:46:43,350 --> 00:46:46,090
broj, jer je sve od
slova stalo

1000
00:46:46,090 --> 00:46:48,780
su na kraju tih rubova.

1001
00:46:48,780 --> 00:46:50,580
Dakle, to je samo jedan
Primjena stabla.

1002
00:46:50,580 --> 00:46:52,538
Ovaj is-- a ja ću mahati
moja ruka na to kako vas

1003
00:46:52,538 --> 00:46:55,570
Možda provesti ovo kao C strukture.

1004
00:46:55,570 --> 00:46:58,260
Mi samo trebate kombinirati
simbol, poput char,

1005
00:46:58,260 --> 00:46:59,910
a učestalost u lijevo i desno.

1006
00:46:59,910 --> 00:47:02,510
Ali pogledajmo dva
Konačni primjeri koje ćete

1007
00:47:02,510 --> 00:47:06,070
dobiti prilično upoznat s poslije
Kviz nula u problemu postaviti pet.

1008
00:47:06,070 --> 00:47:09,210
>> Tako da je struktura podataka
poznat kao hash tablicu.

1009
00:47:09,210 --> 00:47:12,247
I hash tablica je vrsta
hladiti da se posude.

1010
00:47:12,247 --> 00:47:14,830
I pretpostavimo da postoji četiri kante
Ovdje, samo četiri razmaci.

1011
00:47:14,830 --> 00:47:20,830
Evo špilom karata, a ovdje se
klub, Spade, klub, dijamanti, klub,

1012
00:47:20,830 --> 00:47:25,960
dijamanti, klub, dijamanti,
clubs-- pa to je slučajan.

1013
00:47:25,960 --> 00:47:30,330
Srca, hearts-- pa sam
bucketizing sve ulaza ovdje.

1014
00:47:30,330 --> 00:47:32,430
I šifriran tablice potrebe
gledati na svoj ulaz,

1015
00:47:32,430 --> 00:47:34,850
a zatim ga staviti u neki
staviti na temelju onoga što vidite.

1016
00:47:34,850 --> 00:47:35,600
To je algoritam.

1017
00:47:35,600 --> 00:47:37,980
I ja sam bio koristeći super
Jednostavan vizualni algoritam.

1018
00:47:37,980 --> 00:47:40,030
Najteži dio koji je bio
prisjećajući se što su slike bile.

1019
00:47:40,030 --> 00:47:41,590
A tu je i četiri ukupno stvari.

1020
00:47:41,590 --> 00:47:45,440
>> Sada hrpe su rasle, što
je namjerno dizajn stvar ovdje.

1021
00:47:45,440 --> 00:47:46,540
Ali, što drugo bi moglo da radim?

1022
00:47:46,540 --> 00:47:49,080
Tako zapravo ovdje imamo
hrpa starih škola ispita knjigama.

1023
00:47:49,080 --> 00:47:51,240
Pretpostavimo da je hrpa
studenti su imena ovdje.

1024
00:47:51,240 --> 00:47:52,570
Evo veći hash tablicu.

1025
00:47:52,570 --> 00:47:54,867
Umjesto četiri kante,
Ja sam, recimo 26.

1026
00:47:54,867 --> 00:47:57,950
I nismo htjeli ići posuditi 26
stvari iz vanjskog [? Annenberg?], Tako da

1027
00:47:57,950 --> 00:48:00,289
evo pet koje predstavljaju
A do Z. I ako ja

1028
00:48:00,289 --> 00:48:03,580
vidi student čije ime počinje sa A,
Idem s njegovim kviz stavio tamo.

1029
00:48:03,580 --> 00:48:08,850
Ako netko počne s C, tamo,
A- zapravo, nije htio učiniti.

1030
00:48:08,850 --> 00:48:10,060
B ide ovamo.

1031
00:48:10,060 --> 00:48:13,390
Tako sam dobio A i B i C. A
Sada ovdje je još jedan student.

1032
00:48:13,390 --> 00:48:16,212
No, ako je to hash tablica
provode s nizom,

1033
00:48:16,212 --> 00:48:17,920
Ja sam vrsta pijan
u ovom trenutku, zar ne?

1034
00:48:17,920 --> 00:48:19,510
Ja vrsta morati staviti ovaj negdje.

1035
00:48:19,510 --> 00:48:24,380
>> Tako je jedan od načina da se riješi ovo je sve
pravo, zauzet, B je zauzet, C je zauzet.

1036
00:48:24,380 --> 00:48:28,880
Ja ću ga staviti u D. Dakle, na
Prvo, imam slučajnim brz pristup

1037
00:48:28,880 --> 00:48:31,064
da svaki od kante za studente.

1038
00:48:31,064 --> 00:48:33,230
Ali sada je to vrsta devolved
u nešto linearno,

1039
00:48:33,230 --> 00:48:36,750
jer ako želim tražiti nekoga
čije ime počinje sa A, sam provjeriti ovdje.

1040
00:48:36,750 --> 00:48:38,854
No, ako to nije A
Student Tražim,

1041
00:48:38,854 --> 00:48:41,520
Ja vrsta početi provjeru
su kante, jer ono što sam učinio

1042
00:48:41,520 --> 00:48:44,530
je vrsta linearno
istražiti strukturu podataka.

1043
00:48:44,530 --> 00:48:47,710
Glupi način govoreći samo pogledajte
prvi dostupnih otvaranja,

1044
00:48:47,710 --> 00:48:51,850
i staviti kao plan B, da se tako izrazim,
ili plan D, u ovom slučaju, vrijednost

1045
00:48:51,850 --> 00:48:53,340
na tom mjestu umjesto.

1046
00:48:53,340 --> 00:48:56,470
To je samo tako da ako ste
dobio 26 mjesta i bez studente

1047
00:48:56,470 --> 00:49:00,600
s imenom Q ili Z, ili nešto slično
da, barem da koristite prostor.

1048
00:49:00,600 --> 00:49:03,140
>> No, već smo vidjeli više
pametan rješenja ovdje, zar ne?

1049
00:49:03,140 --> 00:49:04,870
Što biste učinili umjesto
Ako imate sudar?

1050
00:49:04,870 --> 00:49:06,670
Ako dvije osobe imaju
naziv A, što bi

1051
00:49:06,670 --> 00:49:09,160
bio pametniji ili više
intuitivno rješenje nego samo

1052
00:49:09,160 --> 00:49:12,840
Stavljanje gdje je D trebao biti?

1053
00:49:12,840 --> 00:49:14,810
Zašto ne bih jednostavno otići
izvan [? Annenberg?]

1054
00:49:14,810 --> 00:49:19,960
poput malloc, drugi čvor, stavi ga
ovdje, a zatim staviti da student ovdje.

1055
00:49:19,960 --> 00:49:22,120
Tako da sam u biti ima
neka niza,

1056
00:49:22,120 --> 00:49:25,590
ili možda i više elegantno kao da smo
počinju vidjeti popis povezane.

1057
00:49:25,590 --> 00:49:29,520
>> I tako hash tablicu je struktura
koji bi mogao izgledati upravo ovako,

1058
00:49:29,520 --> 00:49:33,900
ali više pametno, te nešto što se zove
odvojeni ulančavanje, pri čemu hash tablicu

1059
00:49:33,900 --> 00:49:38,340
jednostavno je niz, svaki od
čije elemente nije broj,

1060
00:49:38,340 --> 00:49:40,470
je sam popis povezani.

1061
00:49:40,470 --> 00:49:45,080
Tako da dobijete super brzo pristupa
odlučivanja gdje hash svoju vrijednost na.

1062
00:49:45,080 --> 00:49:48,059
Slično kao s kartice, primjerice,
Napravio sam super brze odluke.

1063
00:49:48,059 --> 00:49:49,600
Hearts ide ovdje, dijamanti ide ovdje.

1064
00:49:49,600 --> 00:49:52,180
Isto ovdje, A ide ovdje,
D ide ovdje, B ide ovdje.

1065
00:49:52,180 --> 00:49:55,740
Dakle, super brzo izgled-up, a ako
vam se dogoditi da se izvoditi u slučaju

1066
00:49:55,740 --> 00:49:59,429
gdje Imaš sudari, dva
ljudi s istim imenom, ali onda

1067
00:49:59,429 --> 00:50:00,970
vi samo početi povezuje ih zajedno.

1068
00:50:00,970 --> 00:50:03,900
A možda bi ih razvrstani
abecednom redu, možda ne.

1069
00:50:03,900 --> 00:50:05,900
Ali barem sada imamo dinamiku.

1070
00:50:05,900 --> 00:50:10,250
Dakle, s jedne strane imamo super brzi
vremenska konstanta, a vrsta linearnog vremena

1071
00:50:10,250 --> 00:50:14,110
uključena, ako ovim povezanim popisima
početi da se malo dugo.

1072
00:50:14,110 --> 00:50:16,880
>> Dakle, ova vrsta glup,
štreberski vic godina.

1073
00:50:16,880 --> 00:50:19,590
Na CS50 hack-a-Thon,
kada učenici check in,

1074
00:50:19,590 --> 00:50:22,040
Neki TF ili CA svake godine
misli da je smiješno da se stavi

1075
00:50:22,040 --> 00:50:27,772
znak kao što je ovaj, gdje je samo
znači ako je vaše ime počinje sa A,

1076
00:50:27,772 --> 00:50:28,870
ići na ovaj način.

1077
00:50:28,870 --> 00:50:31,110
Ako vaše ime počinje
s B, idite this-- redu,

1078
00:50:31,110 --> 00:50:33,290
to je smiješno možda kasnije u semestru.

1079
00:50:33,290 --> 00:50:36,420
No, tu je još jedan
način za to, previše.

1080
00:50:36,420 --> 00:50:37,410
Vratite se na to.

1081
00:50:37,410 --> 00:50:38,600
>> Tako je ova struktura.

1082
00:50:38,600 --> 00:50:40,420
A ovo je naša posljednja
Struktura za danas,

1083
00:50:40,420 --> 00:50:42,400
što je nešto što se zove Trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-e, koji je iz nekog razloga je kratka
za dohvat, ali to se zove Trie.

1085
00:50:47,140 --> 00:50:51,389
Tako Trie je još jedan zanimljiv
amalgam puno tih ideja.

1086
00:50:51,389 --> 00:50:52,930
To je stablo, koje smo vidjeli.

1087
00:50:52,930 --> 00:50:54,180
Nije pretraživanje po binarnom stablu.

1088
00:50:54,180 --> 00:50:58,410
To je stablo s bilo kojim brojem djece,
ali svaki od djece u Trie

1089
00:50:58,410 --> 00:51:00,090
je niz.

1090
00:51:00,090 --> 00:51:04,790
Niz veličine, kažu, 26 ili možda 27
Ako želite podržati crticu imena

1091
00:51:04,790 --> 00:51:06,790
ili apostrofe u ljudi imena.

1092
00:51:06,790 --> 00:51:08,280
>> I tako je to struktura podataka.

1093
00:51:08,280 --> 00:51:10,290
A ako pogledate odozgo
do dna, kao i ako

1094
00:51:10,290 --> 00:51:13,710
pogledajte gornjem čvoru tamo, M, je
ukazujući na krajnjem lijevom stvar postoji,

1095
00:51:13,710 --> 00:51:17,665
koji se zatim su A, X, W, E, L, L. To je
samo struktura podataka koja samovoljno

1096
00:51:17,665 --> 00:51:19,120
je spremanje imena ljudi.

1097
00:51:19,120 --> 00:51:25,720
I Maxwell se pohranjuje samo nakon
put od polja do polja na polje.

1098
00:51:25,720 --> 00:51:30,050
No, ono što je nevjerojatna o Trie je
da, dok je popis povezanih, pa čak i

1099
00:51:30,050 --> 00:51:34,520
niz, najbolji smo ikada stečen je
linearno vrijeme ili logaritamska vremena u potrazi

1100
00:51:34,520 --> 00:51:35,600
netko gore.

1101
00:51:35,600 --> 00:51:40,530
U ovom struktura podataka, ako Trie
moja struktura podataka ima jedno ime u njemu

1102
00:51:40,530 --> 00:51:43,720
i ja sam u potrazi za Maxwell, ja sam
će ga pronaći prilično brzo.

1103
00:51:43,720 --> 00:51:47,910
Upravo sam u potrazi za M-A-X-W-E-L-L. Ukoliko
ova struktura podataka, za razliku od,

1104
00:51:47,910 --> 00:51:51,830
ako je N milijun, ako postoji
Milijun imena u ovoj strukturi podataka,

1105
00:51:51,830 --> 00:51:57,100
Maxwell i dalje će biti
otkriti nakon samo M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
koraka.

1107
00:51:58,090 --> 00:52:01,276
A David-- D-A-V-I-D koraka.

1108
00:52:01,276 --> 00:52:03,400
Drugim riječima, gradeći
struktura podataka koji je

1109
00:52:03,400 --> 00:52:07,240
nema a svi od ovih polja, sve
uzdržavati slučajni pristup,

1110
00:52:07,240 --> 00:52:11,090
Mogu početi gleda gore Narodne
ime koristite količinu vremena koja je

1111
00:52:11,090 --> 00:52:14,340
proporcionalna ne po broju
stvari u strukturi podataka,

1112
00:52:14,340 --> 00:52:16,330
Poput milijuna postojećih imena.

1113
00:52:16,330 --> 00:52:20,135
Iznos od vrijeme koje je potrebno mi je naći
M-A-X-W-E-L-L u ovoj strukturi podataka je

1114
00:52:20,135 --> 00:52:22,260
proporcionalna ne na
Veličina strukture podataka,

1115
00:52:22,260 --> 00:52:25,930
ali na duljinu imena.

1116
00:52:25,930 --> 00:52:28,440
A realno
imena što smo se gleda

1117
00:52:28,440 --> 00:52:29,970
se nikada ne će biti ludi dugo.

1118
00:52:29,970 --> 00:52:32,600
Možda netko ima 10 karaktera
ime, ime 20 znakova.

1119
00:52:32,600 --> 00:52:33,900
To je svakako konačni, zar ne?

1120
00:52:33,900 --> 00:52:37,110
Tu je čovjek na Zemlji, koji
ima najdulji mogući naziv,

1121
00:52:37,110 --> 00:52:39,920
ali to ime je konstanta
Duljina vrijednost, zar ne?

1122
00:52:39,920 --> 00:52:41,980
To ne razlikuju u bilo kojem smislu.

1123
00:52:41,980 --> 00:52:45,090
Dakle, na ovaj način, mi smo
postigla strukturu podataka

1124
00:52:45,090 --> 00:52:47,800
da je vremenska konstanta pregledna.

1125
00:52:47,800 --> 00:52:50,670
To ne uzeti broj koraka
ovisno o dužini unosa,

1126
00:52:50,670 --> 00:52:54,250
ali ne i broj imena
u podatkovnoj strukturi.

1127
00:52:54,250 --> 00:52:58,700
Dakle, ako ćemo udvostručiti broj imena
sljedeće godine od milijardu do dvije milijarde,

1128
00:52:58,700 --> 00:53:03,720
Nalaz Maxwell će potrajati
točno isti broj sedam koraka

1129
00:53:03,720 --> 00:53:04,650
ga naći.

1130
00:53:04,650 --> 00:53:08,810
I tako mi se čini da su postigli
naš sveti gral trčanje vremena.

1131
00:53:08,810 --> 00:53:10,860
>> Dakle, par brzih najave.

1132
00:53:10,860 --> 00:53:11,850
Kviz nula dolazi.

1133
00:53:11,850 --> 00:53:14,600
Više o tome na stranicama tijeku je
u narednih nekoliko dana.

1134
00:53:14,600 --> 00:53:17,120
Ponedjeljak lecture-- to je odmor
ovdje na Harvardu u ponedjeljak.

1135
00:53:17,120 --> 00:53:18,850
To nije u New Havenu,
tako da smo uzimajući klase

1136
00:53:18,850 --> 00:53:20,310
New Haven za predavanje u ponedjeljak.

1137
00:53:20,310 --> 00:53:22,550
Sve će biti sniman
i streamed uživo, kao i obično,

1138
00:53:22,550 --> 00:53:24,900
ali neka je danas završava
s druge isječak 30

1139
00:53:24,900 --> 00:53:26,910
pod nazivom "Deep misli"
po Daven Farnham, koji

1140
00:53:26,910 --> 00:53:30,850
je inspiriran prošle godine u subotu
Night Live-a "Deep misli"

1141
00:53:30,850 --> 00:53:35,700
Jack pri ruci, što
Sada bi trebalo smisla.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: A sada, "Deep
Misli "od Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tablica.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Dobro, to je to za sada.

1147
00:53:47,660 --> 00:53:48,805
Vidimo se sljedeći tjedan.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> Doug: Da biste ga vidjeli u akciji.

1150
00:53:56,680 --> 00:53:58,304
Tako ćemo pogledati kako upravo sada.

1151
00:53:58,304 --> 00:53:59,890
Dakle ovdje imamo nesortiranog niz.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, možete ići naprijed i ponovno pokretanje
to za samo jednu sekundu, molim.

1153
00:54:04,860 --> 00:54:08,562
U redu, kamere su valjanje, pa
akcija kad god ste spremni, Doug, u redu?

1154
00:54:08,562 --> 00:54:11,020
Doug: U redu, tako da ono što smo
imamo ovdje je Nesortirano polje.

1155
00:54:11,020 --> 00:54:13,960
I ja sam boji sve elemente
crveno što znači da je, u stvari,

1156
00:54:13,960 --> 00:54:14,460
nesortiran.

1157
00:54:14,460 --> 00:54:17,960
Tako podsjetiti da je prva stvar koju radimo
je smo sortirali utakmice polovicu polja.

1158
00:54:17,960 --> 00:54:20,630
Onda smo sortirali pravo
polovica polja.

1159
00:54:20,630 --> 00:54:22,830
A ya-da, ya-da, ya-da,
možemo ih spojiti zajedno.

1160
00:54:22,830 --> 00:54:24,520
I imamo potpuno sortirani niz.

1161
00:54:24,520 --> 00:54:25,360
Dakle, to je kako spojiti vrsta radova.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Joj, joj, joj,
cut, cut, cut, cut.

1163
00:54:27,109 --> 00:54:30,130
Doug, ne možeš samo ya-da, ya-da,
ya-da, svoj put kroz spajanje vrste.

1164
00:54:30,130 --> 00:54:31,970
>> Doug: Upravo sam učinio.

1165
00:54:31,970 --> 00:54:32,832
U redu je.

1166
00:54:32,832 --> 00:54:33,540
Mi si dobar to ići.

1167
00:54:33,540 --> 00:54:34,760
Ajmo zadržati valjanje.

1168
00:54:34,760 --> 00:54:35,380
Pa ipak,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Morate objasniti
što potpunije od toga.

1170
00:54:37,800 --> 00:54:39,999
To jednostavno nije dovoljno.

1171
00:54:39,999 --> 00:54:41,790
Doug: Ian, mi ne
morate se vratiti na jedan.

1172
00:54:41,790 --> 00:54:42,350
U redu je.

1173
00:54:42,350 --> 00:54:45,690
Pa ipak, ako nastavimo s merge--
Ian, mi smo usred snimanja.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Znam.

1175
00:54:46,612 --> 00:54:49,320
A mi ne možemo samo ya-da, ya-da,
ya-da, kroz cijeli proces.

1176
00:54:49,320 --> 00:54:52,200
Morate objasniti kako
Dvije strane se spojene zajedno.

1177
00:54:52,200 --> 00:54:53,570
>> Doug: Ali mi smo već
objasnio kako dvije sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Upravo ste prikazano
ih spajanje polje.

1179
00:54:55,321 --> 00:54:56,486
Doug: Znaju proces.

1180
00:54:56,486 --> 00:54:57,172
Oni su u redu.

1181
00:54:57,172 --> 00:54:58,380
Mi smo otišli preko njega deset puta.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Vi samo preskočila pravo nad njom.

1183
00:55:00,330 --> 00:55:03,360
Vraćamo se na jednu, što
Ne možeš ya-da, ya-da preko njega.

1184
00:55:03,360 --> 00:55:05,480
Dobro, natrag u jedan.

1185
00:55:05,480 --> 00:55:07,833
>> Doug: Moram se vratiti
kroz sve slajdove?

1186
00:55:07,833 --> 00:55:08,332
O moj Bože.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
To je kao šesti put, Ian.

1189
00:55:13,004 --> 00:55:13,940
U redu je.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: U redu.

1191
00:55:15,200 --> 00:55:16,590
Spreman?

1192
00:55:16,590 --> 00:55:17,400
Veliki.

1193
00:55:17,400 --> 00:55:18,950
Akcija.