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

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: V redu, tako da je to
CS50 To je konec petih teden.

3
00:00:15,860 --> 00:00:19,220
In opozarjajo, da zadnji čas smo
začeli iskati na Ljubitelj podatkov

4
00:00:19,220 --> 00:00:22,310
strukture, ki so se začeli reševati
Težave, ki so se začeli, da uvede

5
00:00:22,310 --> 00:00:25,640
novi problemi, vendar je ključnega pomena, da je to
je vrsta navojev, da smo

6
00:00:25,640 --> 00:00:27,940
začel delati od vozlišča do vozlišča.

7
00:00:27,940 --> 00:00:30,085
Torej, to je seveda
za enkrat povezani seznam.

8
00:00:30,085 --> 00:00:31,960
In posamezno povezana,
Mislim, da je samo ena

9
00:00:31,960 --> 00:00:33,380
nit med vsemi temi vozlišč.

10
00:00:33,380 --> 00:00:35,890
Izkazalo se je, lahko storite Ljubitelj
stvari, kot so dvojno povezanih seznamov

11
00:00:35,890 --> 00:00:38,470
s katerim imate puščico
gre v obeh smereh, ki

12
00:00:38,470 --> 00:00:40,320
lahko pomaga z določenimi učinkovitosti.

13
00:00:40,320 --> 00:00:42,000
Toda to rešiti problem?

14
00:00:42,000 --> 00:00:43,500
Kaj je problem je to rešiti?

15
00:00:43,500 --> 00:00:46,620
Zakaj smo mar v ponedeljek?

16
00:00:46,620 --> 00:00:49,820
Zakaj, v teoriji, ni mi mar v ponedeljek?

17
00:00:49,820 --> 00:00:50,630
Kaj počne?

18
00:00:50,630 --> 00:00:51,950
>> OBČINSTVO: Mi lahko dinamično velikost.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, tako da bomo lahko
dinamično velikost.

20
00:00:53,740 --> 00:00:54,710
Dobro opravljeno oba.

21
00:00:54,710 --> 00:00:57,560
Tako da lahko dinamično spreminjanje velikosti to
podatkovna struktura, medtem ko je niz,

22
00:00:57,560 --> 00:01:00,760
odpoklic, moraš vedeti
priori, koliko prostora želite

23
00:01:00,760 --> 00:01:03,870
in če boste potrebovali malo več
prostor, da ste nekako od sreče.

24
00:01:03,870 --> 00:01:05,560
Boste morali ustvariti povsem novo paleto.

25
00:01:05,560 --> 00:01:07,893
Moraš se premakniti vse vaše
podatki iz ene v drugo,

26
00:01:07,893 --> 00:01:10,600
sčasoma sprostiti staro paleto
če lahko, in nato nadaljujte.

27
00:01:10,600 --> 00:01:13,891
Ki le počuti zelo drago in zelo
neučinkovito, in dejansko je mogoče.

28
00:01:13,891 --> 00:01:14,890
Toda to še ni vse dobro.

29
00:01:14,890 --> 00:01:18,180
Smo plačali ceno, kar je bil eden
bolj očitne cen smo

30
00:01:18,180 --> 00:01:20,550
plačilo z uporabo povezani seznam?

31
00:01:20,550 --> 00:01:22,825
>> OBČINSTVO: moramo uporabiti
dvojni prostor za vsakega od njih.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Ja, zato moramo
vsaj dvakrat toliko prostora.

33
00:01:25,200 --> 00:01:27,700
V bistvu, sem spoznal, ta slika je
celo malo zavajajoče,

34
00:01:27,700 --> 00:01:32,200
ker na CS50 IDE v veliko moderno
računalniki, kazalec ali naslov

35
00:01:32,200 --> 00:01:33,700
dejansko ni štirimi zlogi.

36
00:01:33,700 --> 00:01:36,090
To je zelo pogosto ti
dni osem bajtov, ki

37
00:01:36,090 --> 00:01:38,530
pomeni dno najbolj
pravokotniki tam v resnici

38
00:01:38,530 --> 00:01:40,900
so vrste dvakrat
velik kot tisto, kar sem sestavljen,

39
00:01:40,900 --> 00:01:44,409
kar pomeni, da ste z uporabo trikrat
toliko prostora, kot bi imeli drugače.

40
00:01:44,409 --> 00:01:46,700
Sedaj istočasno, da smo
Še vedno govorimo bajte, kajne?

41
00:01:46,700 --> 00:01:49,140
Mi ni nujno, da govorimo
megabajtov ali gigabajtov,

42
00:01:49,140 --> 00:01:51,000
če teh podatkov strukture dobil velik.

43
00:01:51,000 --> 00:01:54,510
>> In tako smo danes začeli obravnavati
kako bi lahko razišče podatke

44
00:01:54,510 --> 00:01:57,310
bolj učinkovito, če pri
Dejstvo podatki gets večji.

45
00:01:57,310 --> 00:02:00,360
Ampak poskusimo kanoniziran
operacije prvih

46
00:02:00,360 --> 00:02:02,460
ki jih lahko naredite na teh
vrste podatkovnih struktur.

47
00:02:02,460 --> 00:02:04,790
Torej nekaj podobnega, povezane
seznam splošno podpira

48
00:02:04,790 --> 00:02:07,514
Operacije želeli izbrisati,
vstaviti, in iskati.

49
00:02:07,514 --> 00:02:08,639
In kaj mislim s tem?

50
00:02:08,639 --> 00:02:11,222
To samo pomeni, da je običajno,
če ljudje uporabljajo povezani seznam,

51
00:02:11,222 --> 00:02:14,287
sami ali nekdo drug je izvajala
Funkcije, kot so brisanje, vstavljanje,

52
00:02:14,287 --> 00:02:16,120
in iskanja, tako da boste lahko
dejansko nekaj storiti

53
00:02:16,120 --> 00:02:18,030
koristno s strukturo podatkov.

54
00:02:18,030 --> 00:02:20,760
Torej, kaj je na hitro pogledamo
kako lahko izvajamo

55
00:02:20,760 --> 00:02:24,530
nekatere kodirajo za povezani seznam, kot sledi.

56
00:02:24,530 --> 00:02:27,885
>> Torej, to je le nekaj C kodo,
ni niti celoten program

57
00:02:27,885 --> 00:02:29,260
da sem res hitro podžigal.

58
00:02:29,260 --> 00:02:32,300
To ni na spletu v distribuciji
Koda, saj ne bo dejansko vozijo.

59
00:02:32,300 --> 00:02:33,790
Ampak opazila sem pravkar
s komentar dejal,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, da je nekaj
tam, dot dot dot, nekaj tam.

61
00:02:36,130 --> 00:02:38,410
In kaj je samo pogled na
kaj sočno deli.

62
00:02:38,410 --> 00:02:40,790
Torej, on-line tri,
opozarjajo, da je to zdaj

63
00:02:40,790 --> 00:02:45,960
Predlagali smo razglasitvi vozlišče zadnji
Čas, eden izmed teh pravokotnih predmetov.

64
00:02:45,960 --> 00:02:48,790
Ima int da bomo klic N,
vendar bi lahko rekli, da je vse,

65
00:02:48,790 --> 00:02:51,920
in takrat imenovana struct vozlišče zvezda naslednjič.

66
00:02:51,920 --> 00:02:55,520
In samo zato, da bo jasno, da drugi
linija, na vrstnim šestvaljnikom, kaj je to?

67
00:02:55,520 --> 00:02:57,930
Kaj je delal za nas?

68
00:02:57,930 --> 00:03:01,044
Ker je zagotovo izgleda bolj
Grobni od naših običajnih spremenljivk.

69
00:03:01,044 --> 00:03:02,740
>> OBČINSTVO: To omogoča, da se premaknete v enem.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: To omogoča, da se premaknete v enem.

71
00:03:04,650 --> 00:03:08,580
In če smo natančnejši,
bo shranite naslov

72
00:03:08,580 --> 00:03:11,582
vozlišča, ki je pomenilo, da je
semantično zraven njega, kajne?

73
00:03:11,582 --> 00:03:13,540
Tako da je ne bo
nujno premakniti ničesar.

74
00:03:13,540 --> 00:03:15,290
To je le, da bo
shraniti vrednost, ki je

75
00:03:15,290 --> 00:03:17,170
bo naslov
neke druge vozlišča,

76
00:03:17,170 --> 00:03:20,810
in da je, zakaj smo dejal struct
vozlišče zvezda, zvezda označuje

77
00:03:20,810 --> 00:03:22,370
kazalec ali naslov.

78
00:03:22,370 --> 00:03:26,390
OK, tako da zdaj, če predpostavimo, da imamo
To N nam na voljo, in ne dovolimo,

79
00:03:26,390 --> 00:03:29,490
predpostavimo, da ima nekdo drug
vstavi cel kup števil

80
00:03:29,490 --> 00:03:30,400
v povezani seznam.

81
00:03:30,400 --> 00:03:35,640
In to povezano seznam
je poudaril, da ga neki točki

82
00:03:35,640 --> 00:03:39,040
spremenljivka imenovan Seznam A, ki je
opravil sem kot parameter,

83
00:03:39,040 --> 00:03:43,120
Kako naj grem o skladu
14 izvedbenih iskanju?

84
00:03:43,120 --> 00:03:45,990
Z drugimi besedami, če sem izvedbenih
funkcija, katere namen v življenju

85
00:03:45,990 --> 00:03:48,889
je, da int in nato
začetek povezanega seznama,

86
00:03:48,889 --> 00:03:50,430
da je kazalec na povezani seznam.

87
00:03:50,430 --> 00:03:52,992
Tako kot prva, ki mislim, da Davida
je bila naša prostovoljka v ponedeljek,

88
00:03:52,992 --> 00:03:54,700
je bil obrnjen na
celoten povezani seznam,

89
00:03:54,700 --> 00:03:57,820
to je, kot da smo mimo
David v kot naš argument tukaj.

90
00:03:57,820 --> 00:03:59,990
Kako bomo šli o prečkajo ta seznam?

91
00:03:59,990 --> 00:04:04,640
No, izkaže se, da čeprav
kazalci so relativno nova sedaj za nas,

92
00:04:04,640 --> 00:04:07,010
bomo lahko to storili relativno
naravnost.

93
00:04:07,010 --> 00:04:09,500
>> Grem, da gredo naprej in
prijavijo začasno spremenljivko, ki

94
00:04:09,500 --> 00:04:12,364
po dogovoru se le, da bo
da se imenuje kazalec, ali PTR,

95
00:04:12,364 --> 00:04:14,030
ampak jo lahko imenujemo kar hočeš.

96
00:04:14,030 --> 00:04:16,470
In bom za inicializacijo
je na začetku seznama.

97
00:04:16,470 --> 00:04:20,050
Torej si lahko nekako misli o tem
Kot mi je učitelj drugi dan,

98
00:04:20,050 --> 00:04:23,580
nekako kaže na nekoga
med našimi ljudmi kot prostovoljci.

99
00:04:23,580 --> 00:04:26,470
Tako da sem začasno spremenljivko, ki je
samo kaže na isto stvar

100
00:04:26,470 --> 00:04:31,390
da je naš naključno imenovan
prostovoljec David je tudi poudaril.

101
00:04:31,390 --> 00:04:35,440
Zdaj, ko kazalec
ni nič, ker odpoklic

102
00:04:35,440 --> 00:04:40,350
da null je nekaj posebnega sentinel vrednost
razmejuje konec seznama,

103
00:04:40,350 --> 00:04:44,280
Torej, medtem ko jaz ne pokaže na
tla kot naš zadnji prostovoljec

104
00:04:44,280 --> 00:04:47,190
je, pojdimo naprej
in storite naslednje.

105
00:04:47,190 --> 00:04:51,820
Če pointer-- in zdaj sem nekako želim
da to, kar smo naredili z učencem

106
00:04:51,820 --> 00:04:57,410
če structure-- kazalec dot Naslednja
equals-- raje, če kazalec dot N enaka

107
00:04:57,410 --> 00:05:02,290
enak spremenljivka N, pri
Argument, ki je bila sprejeta leta,

108
00:05:02,290 --> 00:05:05,370
potem hočem iti naprej
in pravijo, vrne true.

109
00:05:05,370 --> 00:05:11,020
Ugotovil sem, da številko N notranjost
eden od vozlišča moj povezani seznam.

110
00:05:11,020 --> 00:05:13,500
Toda pika ni več
dela v zvezi s tem,

111
00:05:13,500 --> 00:05:17,260
ker je kazalec, PTR, je
res kazalec, naslov,

112
00:05:17,260 --> 00:05:20,632
smo dejansko lahko čudovito
uporabite končno kos sintakse

113
00:05:20,632 --> 00:05:22,590
da vrsta znamk
intuitiven občutek in dejansko

114
00:05:22,590 --> 00:05:27,870
uporabite puščico tukaj, kar pomeni, da gredo od
da je naslov za celo tam leta.

115
00:05:27,870 --> 00:05:30,160
Torej, to je zelo podobna
duh upravljavcu dot,

116
00:05:30,160 --> 00:05:33,860
ampak zato, ker kazalec ni kazalec
in ne sam po sebi dejansko struct,

117
00:05:33,860 --> 00:05:35,380
smo samo uporabo puščico.

118
00:05:35,380 --> 00:05:40,620
>> Torej, če je trenutno vozlišče, da sem se
začasna spremenljivka, sem gledala

119
00:05:40,620 --> 00:05:43,060
ni N, kaj hočem narediti?

120
00:05:43,060 --> 00:05:45,910
No, z mojo prostovoljcih
da smo imeli tukaj, drugi dan,

121
00:05:45,910 --> 00:05:49,710
če je moj prvi človek ni tisti, ki sem
želijo, in morda drugi človek ni

122
00:05:49,710 --> 00:05:52,660
tista želim, in tretje, sem
potreba, da se fizično premikajo.

123
00:05:52,660 --> 00:05:54,690
Like kako stopim skozi seznamu?

124
00:05:54,690 --> 00:05:57,470
Ko smo imeli paleto vas,
pravkar storil, kot sem plus plus.

125
00:05:57,470 --> 00:06:03,660
Toda v tem primeru zadostuje, da
storiti kazalec, dobi, kazalec, naslednji.

126
00:06:03,660 --> 00:06:07,580
Z drugimi besedami, naslednji polje
je, kot vse leve roke

127
00:06:07,580 --> 00:06:10,880
da naše človeške prostovoljci v ponedeljek
so bili z uporabo opozoriti na neko drugo vozlišče.

128
00:06:10,880 --> 00:06:12,890
Tisti, ki so bili njihovi naslednji sosedje.

129
00:06:12,890 --> 00:06:17,060
>> Torej, če želim stopiti skozi ta seznam,
Ne morem storiti jaz plus plus več,

130
00:06:17,060 --> 00:06:20,120
Jaz namesto reči
I, kazalec, se dogaja

131
00:06:20,120 --> 00:06:24,650
da enako ne glede na naslednjo polje,
Naslednji polje, naslednji polje,

132
00:06:24,650 --> 00:06:28,350
po vseh teh leve roke
da smo imeli na odru kazala

133
00:06:28,350 --> 00:06:30,000
z nekaterimi poznejšimi vrednosti.

134
00:06:30,000 --> 00:06:32,590
In če sem priti skozi
da celotna ponovitev,

135
00:06:32,590 --> 00:06:39,330
in končno, sem udaril null nimajo
Najdenih N še, pravkar sem return false.

136
00:06:39,330 --> 00:06:44,100
Torej še enkrat, vse, kar delamo tukaj,
kot na sliki pred nekaj trenutki,

137
00:06:44,100 --> 00:06:47,840
se začenja z opozorilom Na
začetek seznama verjetno.

138
00:06:47,840 --> 00:06:50,970
In potem sem preveriti, je vrednost
Iščem enaka devet?

139
00:06:50,970 --> 00:06:52,650
Če je tako, se vrnem true in sem naredil.

140
00:06:52,650 --> 00:06:56,450
Če ne, bom posodobiti svojo roko,
AKA kazalec na točko

141
00:06:56,450 --> 00:06:59,540
na lokaciji naslednji puščica je, in
nato lokacija naslednjega puščica je,

142
00:06:59,540 --> 00:07:00,480
in dostavo.

143
00:07:00,480 --> 00:07:03,770
Jaz sem preprosto hojo skozi ta niz.

144
00:07:03,770 --> 00:07:06,010
>> Torej še enkrat, koga briga?

145
00:07:06,010 --> 00:07:07,861
Všeč, kaj je to sestavina za?

146
00:07:07,861 --> 00:07:10,360
No, opozarjajo, da smo uvedli
pojem dimnika, ki

147
00:07:10,360 --> 00:07:15,400
je abstrakten podatkovni tip, kolikor je to
ni C stvar, to ni CS50 stvar,

148
00:07:15,400 --> 00:07:19,430
to je abstraktna ideja, ta ideja
zlaganje stvari na vrhu med seboj

149
00:07:19,430 --> 00:07:21,820
ki jih je mogoče izvajati
grozde različne načine.

150
00:07:21,820 --> 00:07:25,600
In en način, smo predlagali, je bila z
niz, ali povezanega seznama.

151
00:07:25,600 --> 00:07:29,570
In se izkaže, da je kanonično, A
Snop podpira vsaj dve operaciji.

152
00:07:29,570 --> 00:07:32,320
In buzz besede potisni, da
potisnite nekaj na kupu,

153
00:07:32,320 --> 00:07:34,770
kot nov pladenj v
jedilnica, ali pop,

154
00:07:34,770 --> 00:07:39,000
kar pomeni, da se odstranijo vrhunskih
pladenj iz dimnika v jedilnico

155
00:07:39,000 --> 00:07:41,500
dvorana, nato pa morda nekaj
drugi postopki, kot dobro.

156
00:07:41,500 --> 00:07:45,770
Torej, kako lahko definiramo strukturo
da smo zdaj kliče kup?

157
00:07:45,770 --> 00:07:50,020
>> No, imamo vse zahtevano
skladnja so nam na voljo v C. rečem,

158
00:07:50,020 --> 00:07:53,830
dajte mi definicijo tipskega
struct notranjosti dimnika,

159
00:07:53,830 --> 00:07:58,030
Jaz bom rekel, je matrika odsvojila
cel kup številk in nato velikosti.

160
00:07:58,030 --> 00:08:00,930
Torej, z drugimi besedami, če želim
izvajati to v kodi,

161
00:08:00,930 --> 00:08:03,830
Naj gredo in šele nekako
pripraviti, kaj je to rekel.

162
00:08:03,830 --> 00:08:06,317
Torej, to je rekel, daj mi
struktura, ki je dobil niz,

163
00:08:06,317 --> 00:08:09,400
in ne vem, kaj zmogljivost,
to je očitno nekaj konstanta, ki sem jih

164
00:08:09,400 --> 00:08:10,858
opredeljena drugje, in da je v redu.

165
00:08:10,858 --> 00:08:15,260
Ampak predvidevam, da je samo ena,
dva, tri, štiri, pet.

166
00:08:15,260 --> 00:08:16,700
Torej zmogljivost je 5.

167
00:08:16,700 --> 00:08:21,730
Ta element znotraj my
struktura se bo imenoval številke.

168
00:08:21,730 --> 00:08:24,020
In potem moram eno
druga spremenljivka očitno

169
00:08:24,020 --> 00:08:27,814
imenuje velikost, da najprej grem
določiti, se ponastavi na nič.

170
00:08:27,814 --> 00:08:29,730
Če ni nič v
Sveženj, znaša nič,

171
00:08:29,730 --> 00:08:31,420
in to je smeti vrednosti v številkah.

172
00:08:31,420 --> 00:08:33,450
Nimam pojma, kaj je tam samo še.

173
00:08:33,450 --> 00:08:36,059
>> Torej, če želim push
nekaj na kupu,

174
00:08:36,059 --> 00:08:40,780
Domnevam kličem funkcijo Pritisni in
Pravim potiskanje 50, kot številko 50,

175
00:08:40,780 --> 00:08:44,090
kjer bi predlagali
Sem ga pripravi na tem polju?

176
00:08:44,090 --> 00:08:47,124
Obstaja pet različnih možnih odgovorov.

177
00:08:47,124 --> 00:08:48,790
Kam želite push številko 50?

178
00:08:48,790 --> 00:08:51,899
Če je cilj tukaj, ponovno, pokličite
funkcija Push, prenese v argument

179
00:08:51,899 --> 00:08:52,940
50, kje sem ga dal?

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

181
00:08:55,680 --> 00:08:59,052
Pet possible-- 20% možnosti,
ugibanja pravilno.

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

183
00:08:59,896 --> 00:09:00,740
>> OBČINSTVO: Far desno.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Far desno.

185
00:09:01,990 --> 00:09:08,359
Zdaj je 25% možnosti,
ugibanja pravilno.

186
00:09:08,359 --> 00:09:09,650
Tako da bi dejansko bilo v redu.

187
00:09:09,650 --> 00:09:12,770
Po dogovoru, bom rekel, s paleto,
mi bi običajno začnejo na levi strani,

188
00:09:12,770 --> 00:09:14,519
vendar smo lahko zagotovo
začeti na desno.

189
00:09:14,519 --> 00:09:17,478
Tako da bi spojler tukaj lahko sem
verjetno bo, da ga pripravi na levi strani,

190
00:09:17,478 --> 00:09:20,060
Tako kot v normalnem matrika, kjer
Začnem na levo proti desni.

191
00:09:20,060 --> 00:09:21,780
Ampak, če ste lahko flip
aritmetična, v redu.

192
00:09:21,780 --> 00:09:23,060
To preprosto ni običajna.

193
00:09:23,060 --> 00:09:24,880
OK, moram narediti eno
več sprememb, čeprav.

194
00:09:24,880 --> 00:09:27,710
Zdaj, ko sem potisnil nekaj
na kupu, kaj je naslednje?

195
00:09:27,710 --> 00:09:29,400
>> V redu, moram prirastek velikost.

196
00:09:29,400 --> 00:09:32,600
Zato mi dovolite, pojdi naprej in le
posodablja, ki je enak nič.

197
00:09:32,600 --> 00:09:35,950
In namesto da bi zdaj, bom
dati v vrednosti enega.

198
00:09:35,950 --> 00:09:39,460
In zdaj, da sem potiskanje drugega
Številka na kupu, kot 51.

199
00:09:39,460 --> 00:09:42,680
No, moram narediti eno bolj
Sprememba, ki je do velikosti dveh.

200
00:09:42,680 --> 00:09:46,100
In potem, da sem potisnite enega več
Številka na kupu, kot 61,

201
00:09:46,100 --> 00:09:52,530
Zdaj moram posodobiti velikosti ena
čas, in dobili vrednost 3, kot velikosti.

202
00:09:52,530 --> 00:09:54,690
In zdaj, da sem poklical pop.

203
00:09:54,690 --> 00:09:57,250
Zdaj pop, po dogovoru,
ne bo argument.

204
00:09:57,250 --> 00:10:00,430
Žetonov, celotno
točka pladnja metafore

205
00:10:00,430 --> 00:10:03,450
je, da ne boste imeli diskrecijsko pravico
iti dobili ta pladenj, vse, kar lahko storite

206
00:10:03,450 --> 00:10:06,330
je pop vrhunsko enega iz
Sveženj, samo zato, ker.

207
00:10:06,330 --> 00:10:08,010
To je tisto, kar ta struktura podatkov počne.

208
00:10:08,010 --> 00:10:12,250
>> Torej s to logiko, če sem
pravijo, pop, kaj prihaja off?

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

210
00:10:13,080 --> 00:10:15,402
Torej, kaj je res računalnik
storili v spomin?

211
00:10:15,402 --> 00:10:16,610
Kaj moja koda morate storiti?

212
00:10:16,610 --> 00:10:20,330
Kaj bi predlagali
spremenimo na zaslonu?

213
00:10:20,330 --> 00:10:23,410
Kaj bi spremenili?

214
00:10:23,410 --> 00:10:24,960
Žal?

215
00:10:24,960 --> 00:10:26,334
Torej bomo znebili 61.

216
00:10:26,334 --> 00:10:27,500
Tako sem lahko zagotovo to.

217
00:10:27,500 --> 00:10:28,640
In se ne morem znebiti 61.

218
00:10:28,640 --> 00:10:30,980
In potem kaj drugega
Sprememba se mora zgoditi?

219
00:10:30,980 --> 00:10:33,160
Velikost je, da se vrnete na dva verjetno.

220
00:10:33,160 --> 00:10:34,210
In tako, da je v redu.

221
00:10:34,210 --> 00:10:36,690
Toda počakaj minuto, velikost
pred nekaj trenutki je bil tri.

222
00:10:36,690 --> 00:10:38,240
Kaj je samo naredil preverjanje hitro prištevnosti.

223
00:10:38,240 --> 00:10:41,810
Kako pa vemo, da
želel, da se znebite 61?

224
00:10:41,810 --> 00:10:42,760
Ker smo živahen.

225
00:10:42,760 --> 00:10:46,450
In zato imam to drugo velikost lastnine.

226
00:10:46,450 --> 00:10:48,470
>> Čakaj malo, jaz sem
razmišljal nazaj na dva tedna

227
00:10:48,470 --> 00:10:51,660
ko smo začeli govoriti o
polja, kjer je bila ta lokacija nič,

228
00:10:51,660 --> 00:10:55,920
to je bila lokacija ena, je bila ta lokacija
dva, to je lokacija tri, štiri,

229
00:10:55,920 --> 00:10:58,460
Izgleda, da je
razmerje med velikostjo

230
00:10:58,460 --> 00:11:02,780
in element, da želim, da se odstranijo
Iz matrike zdi, da samo se kaj?

231
00:11:02,780 --> 00:11:05,120
Velikost minus ena.

232
00:11:05,120 --> 00:11:07,786
In da je, kako kot ljudje
vemo, 61 na prvem mestu.

233
00:11:07,786 --> 00:11:09,160
Kako je računalnik bo vedel?

234
00:11:09,160 --> 00:11:11,701
Ko kodo, kjer vas verjetno
želite narediti velikost minus ena,

235
00:11:11,701 --> 00:11:14,950
tako tri minus ena je dva, in da
pomeni, da smo želeli, da se znebite 61.

236
00:11:14,950 --> 00:11:18,000
In potem bomo lahko dejansko posodobiti
velikost, tako da je velikost zdaj

237
00:11:18,000 --> 00:11:20,300
gre iz treh na samo dva.

238
00:11:20,300 --> 00:11:24,520
In samo, da je občutljiv, bom
predlagati, da sem naredil, kajne?

239
00:11:24,520 --> 00:11:27,660
Ste predlagali intuitivno
pravilno sem se moral znebiti 61.

240
00:11:27,660 --> 00:11:30,700
Ampak še nisem nekako
nekako gotten znebite 61?

241
00:11:30,700 --> 00:11:33,790
Sem dejansko pozabljena
da je dejansko tam.

242
00:11:33,790 --> 00:11:37,680
In pomislite na PSET4, če ste prebrali
članek o forenziki, PDF

243
00:11:37,680 --> 00:11:40,780
da smo imeli vi prebrali, ali ste
bo prebral ta teden PSET4.

244
00:11:40,780 --> 00:11:44,300
Spomnimo se, da je to pravzaprav germane za
celotna ideja računalniške forenzike.

245
00:11:44,300 --> 00:11:47,820
Kakšen računalnik splošno pa je
to samo pozabi, kje je kaj,

246
00:11:47,820 --> 00:11:51,300
vendar ne gredo v in podobno
poskusite praska ven ali prekrmiljenje

247
00:11:51,300 --> 00:11:54,560
ti bitov z ničel in enic
ali kakšno drugo naključno vzorec

248
00:11:54,560 --> 00:11:56,690
če ste sami storijo namenoma.

249
00:11:56,690 --> 00:11:58,930
Torej, vaša intuicija je bila
Dobro, dajmo znebiti 61.

250
00:11:58,930 --> 00:12:00,650
Toda v resnici, mi ne bo treba ukvarjati.

251
00:12:00,650 --> 00:12:04,040
Vedeti pa je treba, da pozabimo, da
da je tam s spremembo velikosti.

252
00:12:04,040 --> 00:12:05,662
>> Zdaj pa je problem s tem kupu.

253
00:12:05,662 --> 00:12:07,620
Če Držim potiska stvari
na kupu, kar je

254
00:12:07,620 --> 00:12:11,167
Očitno se bo zgodilo
v samo nekaj trenutkov časa?

255
00:12:11,167 --> 00:12:12,500
Bomo zmanjkalo prostora.

256
00:12:12,500 --> 00:12:13,580
In kaj naj naredimo?

257
00:12:13,580 --> 00:12:14,680
Mi smo nekako zajebali.

258
00:12:14,680 --> 00:12:19,000
To izvajanje ne pusti
nam spremenite velikost array, saj s pomočjo

259
00:12:19,000 --> 00:12:21,240
to sintakso, če vas
pomislite na dva tedna,

260
00:12:21,240 --> 00:12:23,520
ko ste razglašen
velikost matrike,

261
00:12:23,520 --> 00:12:26,780
nismo videli mehanizem še kje
lahko spremenite velikost polja.

262
00:12:26,780 --> 00:12:29,020
In res C nima te funkcije.

263
00:12:29,020 --> 00:12:32,524
Če rečeš mi daš pet
Nths, pravijo številke,

264
00:12:32,524 --> 00:12:33,940
da je vse, kar boš dobil.

265
00:12:33,940 --> 00:12:38,790
Tako smo zdaj od ponedeljka, imajo
sposobnost izražanja rešitev

266
00:12:38,790 --> 00:12:42,480
čeprav smo morali poteg
opredelitev našega dimnika

267
00:12:42,480 --> 00:12:46,840
da ne bodo nekateri težko kodirane-matrika,
ampak samo za shranjevanje naslov.

268
00:12:46,840 --> 00:12:47,890
>> Zdaj zakaj je to?

269
00:12:47,890 --> 00:12:51,690
Zdaj bomo morali biti zadovoljni s
dejstvo, da se, ko je moj program teče,

270
00:12:51,690 --> 00:12:53,730
Jaz sem verjetno bo
morali vprašati človeka,

271
00:12:53,730 --> 00:12:55,110
koliko številk ne želite shraniti?

272
00:12:55,110 --> 00:12:56,776
Tako da je vhod mora priti od nekje.

273
00:12:56,776 --> 00:12:59,140
Toda, ko sem vedel, da
številko, potem sem lahko samo

274
00:12:59,140 --> 00:13:02,470
uporabite tisto, kar deluje, da bi
mi kos pomnilnika?

275
00:13:02,470 --> 00:13:03,580
Lahko uporabite malloc.

276
00:13:03,580 --> 00:13:06,710
In lahko rečem, poljubno število
bajtov hočem nazaj za te Nths.

277
00:13:06,710 --> 00:13:10,910
In vse, kar imam za shranjevanje v številkah
spremenljivka tu notri te struct

278
00:13:10,910 --> 00:13:13,480
bi moralo biti, kaj?

279
00:13:13,480 --> 00:13:18,440
Kaj pravzaprav gre v
Številke v tem scenariju?

280
00:13:18,440 --> 00:13:21,300
Ja, kazalec na prvi
bajt ta kos pomnilnika,

281
00:13:21,300 --> 00:13:24,940
ali natančneje, naslov
prve od teh bajtov.

282
00:13:24,940 --> 00:13:27,300
Ni važno, če je to eno
Byte ali milijarda bajtov,

283
00:13:27,300 --> 00:13:28,890
Moram skrbeti za prvega.

284
00:13:28,890 --> 00:13:31,530
Ker kaj malloc jamstva in
moje operacijskega sistema jamstva,

285
00:13:31,530 --> 00:13:34,170
je, da je kos pomnilniški I
razumem, da se dogaja, da se stikata.

286
00:13:34,170 --> 00:13:35,378
Tam je ne bo vrzeli.

287
00:13:35,378 --> 00:13:38,576
Torej, če sem prosil za 50
bajtov ali 1000 bajtov,

288
00:13:38,576 --> 00:13:40,450
oni vse bo
back to back to back.

289
00:13:40,450 --> 00:13:44,500
In tako dolgo, kot se spomnim, kako velik, kako
veliko Prosil sem za, vse, kar morate vedeti

290
00:13:44,500 --> 00:13:46,230
je prvi tak naslov.

291
00:13:46,230 --> 00:13:48,660
>> Torej, zdaj imamo možnost, v kodi.

292
00:13:48,660 --> 00:13:51,280
Čeprav, to se dogaja, da nas bo
več časa za to napisati,

293
00:13:51,280 --> 00:13:55,900
smo zdaj lahko prerazporedi ta pomnilnik, ki ga
Samo shranjevanje drug naslov tam

294
00:13:55,900 --> 00:13:59,060
če želimo večji ali celo
manjši kos pomnilnika.

295
00:13:59,060 --> 00:14:00,170
Torej, tukaj na kompromis.

296
00:14:00,170 --> 00:14:01,360
Zdaj smo dobili dinamiko.

297
00:14:01,360 --> 00:14:03,350
Še vedno imamo
contiguousness sem trdijo.

298
00:14:03,350 --> 00:14:05,881
Saj nam bo malloc dal
stičen kos pomnilnika.

299
00:14:05,881 --> 00:14:08,630
Ampak to se dogaja, da je bolečina v
vrat za nas, programer,

300
00:14:08,630 --> 00:14:09,770
dejansko kodo gor.

301
00:14:09,770 --> 00:14:10,730
To je samo več dela.

302
00:14:10,730 --> 00:14:13,930
Potrebujemo kodo, ki spominja na to, kar sem
poriva ven pred nekaj trenutki.

303
00:14:13,930 --> 00:14:16,120
Zelo izvedljivo, vendar dodaja kompleksnost.

304
00:14:16,120 --> 00:14:19,520
In tako, ko razvijalec, programer
Čas je še en vir

305
00:14:19,520 --> 00:14:22,520
da bomo morda morali porabiti
nekaj časa, da bi dobili nove funkcije.

306
00:14:22,520 --> 00:14:24,020
In potem seveda ni čakalne vrste.

307
00:14:24,020 --> 00:14:26,227
Mi ne bo šel v to
eno v veliko podrobnosti.

308
00:14:26,227 --> 00:14:27,560
Ampak to je zelo podobno v duhu.

309
00:14:27,560 --> 00:14:31,220
Jaz bi izvajati čakalne vrste, in
njeni ustrezni postopki,

310
00:14:31,220 --> 00:14:35,660
enqueue ali dequeue, kot dodajanje ali odstranjevanje,
to je samo Ljubitelj način je rekel,

311
00:14:35,660 --> 00:14:38,100
enqueue ali dequeue, kot sledi.

312
00:14:38,100 --> 00:14:41,170
Jaz lahko samo dam struct
ima ta spet številko na paleto,

313
00:14:41,170 --> 00:14:44,000
je, da ponovno velikost,
ampak zakaj jaz zdaj potrebujem

314
00:14:44,000 --> 00:14:46,940
slediti sprednji čakalne vrste?

315
00:14:46,940 --> 00:14:50,630
Nisem vedeti
sprednji del mojega dimnika.

316
00:14:50,630 --> 00:14:53,570
No, če sem spet za
queue-- kaj je samo težko

317
00:14:53,570 --> 00:14:57,870
to kodo, da ima kot pet
cela v tu potencialno.

318
00:14:57,870 --> 00:15:00,940
Torej to je nič, ena, dva, tri, štiri.

319
00:15:00,940 --> 00:15:03,430
To se bo
imenovane spet številke.

320
00:15:03,430 --> 00:15:06,940
In to se bo imenoval velikost.

321
00:15:06,940 --> 00:15:10,056
>> Zakaj je ne zadostuje
da imajo le velikost?

322
00:15:10,056 --> 00:15:11,680
No, pa potisnite te iste številke naprej.

323
00:15:11,680 --> 00:15:14,220
Tako sem pushed-- sem enqueued, ali potiska.

324
00:15:14,220 --> 00:15:20,150
Zdaj bom enqueue 50, in nato
51, nato 61 in dot dot piko.

325
00:15:20,150 --> 00:15:21,070
Tako da je enqueue.

326
00:15:21,070 --> 00:15:23,176
Enqueued sem 50, nato 51, nato 61.

327
00:15:23,176 --> 00:15:25,050
In da izgleda enako
na kup tako daleč,

328
00:15:25,050 --> 00:15:27,190
razen mi morali narediti eno spremembo.

329
00:15:27,190 --> 00:15:33,680
Moram posodobiti te velikosti, tako da sem šel
od nič do enega do dva do tri sedaj.

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

331
00:15:35,760 --> 00:15:36,890
Kaj se zgodi z dequeue?

332
00:15:36,890 --> 00:15:41,950
Kdo naj sname ta seznam prvič
če je to črta na Apple Store?

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

334
00:15:42,780 --> 00:15:44,700
Torej, to je nekako težje tokrat.

335
00:15:44,700 --> 00:15:47,880
Ker zadnjem času je bilo super
enostavno pač velikost minus ena,

336
00:15:47,880 --> 00:15:51,440
Pridem do konca mojega paleto učinkovito
kjer so številke, odpravlja 61.

337
00:15:51,440 --> 00:15:52,920
Ampak jaz ne želim odstraniti 61.

338
00:15:52,920 --> 00:15:55,030
Želim, da bi 50, ki
je bil tam ob 5:00

339
00:15:55,030 --> 00:15:56,790
line up za
Novi iPhone ali malenkosti.

340
00:15:56,790 --> 00:16:01,200
In tako, da se znebite 50, I
To preprosto ne more storiti, kajne?

341
00:16:01,200 --> 00:16:02,547
Znam prečrtati 50.

342
00:16:02,547 --> 00:16:04,380
Vendar smo pravkar rekel, da smo
Ne biti tako analni

343
00:16:04,380 --> 00:16:06,330
kot praska ven ali skrivanje podatkov.

344
00:16:06,330 --> 00:16:08,090
Mi lahko samo pozabil, kje je.

345
00:16:08,090 --> 00:16:12,330
>> Ampak, če spremenim velikost zdaj
dva, je to dovolj informacij

346
00:16:12,330 --> 00:16:15,711
vedeti, kaj se dogaja v moji vrsti?

347
00:16:15,711 --> 00:16:16,680
Niti ne.

348
00:16:16,680 --> 00:16:19,830
Tako kot moja velikost je dva, ampak
kjer se čakalne vrste začne,

349
00:16:19,830 --> 00:16:22,980
še posebej, če sem še vedno
te iste številke v pomnilniku.

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

351
00:16:24,260 --> 00:16:27,090
Tako da moram zapomniti
Sedaj, ko je spredaj.

352
00:16:27,090 --> 00:16:29,630
In tako kot sem predlagal gor
tam, bomo pravkar poklical

353
00:16:29,630 --> 00:16:33,729
N spredaj, katerega začetna
vrednost bi morala biti, kaj?

354
00:16:33,729 --> 00:16:35,270
Nič, samo začetek seznama.

355
00:16:35,270 --> 00:16:40,876
Toda zdaj poleg pomanjšanja
velikost, smo pravkar prirastek spredaj.

356
00:16:40,876 --> 00:16:42,000
Zdaj tukaj je še en problem.

357
00:16:42,000 --> 00:16:43,030
Torej, ko sem se vedno dogaja.

358
00:16:43,030 --> 00:16:47,520
Recimo, to je število
kot 121, 124 in nato, prekleto,

359
00:16:47,520 --> 00:16:48,610
Sem zmanjkalo prostora.

360
00:16:48,610 --> 00:16:50,390
Toda počakaj malo, nisem.

361
00:16:50,390 --> 00:16:55,630
Tako da na tej točki v zgodbi,
Predpostavimo, da je velikost ena, dva,

362
00:16:55,630 --> 00:17:00,370
tri, štiri, tako predpostavimo, da je
znaša štiri, prednja je on,

363
00:17:00,370 --> 00:17:01,621
tako 51 je na sprednji strani.

364
00:17:01,621 --> 00:17:04,329
Rad bi dal še eno številko tukaj,
ampak, prekleto, da sem ven iz prostora.

365
00:17:04,329 --> 00:17:06,710
Ampak jaz nisem res, kajne?

366
00:17:06,710 --> 00:17:11,192
Kje bi jaz dal nekaj
dodatno vrednost, kot je 171?

367
00:17:11,192 --> 00:17:13,400
Ja, jaz bi samo nekako
pojdi nazaj tja, kajne?

368
00:17:13,400 --> 00:17:18,161
In potem prečrtati 50, ali
samo prepisati s 171.

369
00:17:18,161 --> 00:17:20,410
In če ste se spraševala, zakaj
naše številke dobil tako naključno,

370
00:17:20,410 --> 00:17:24,150
ti so pogosto sprejeti računalnik
znanost tečaji na Harvardu po CS50.

371
00:17:24,150 --> 00:17:27,510
Ampak to je bila dobra optimizacija,
ker zdaj ne bom zapravljam prostor.

372
00:17:27,510 --> 00:17:30,750
Še vedno moram zapomniti
kako velika je ta stvar je skupna.

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

374
00:17:31,500 --> 00:17:33,375
Ker ne želim, da
začetek prepisovanju 51.

375
00:17:33,375 --> 00:17:36,260
Torej, zdaj sem še vedno zmanjkalo prostora,
tako isti problem kot prej.

376
00:17:36,260 --> 00:17:39,140
Vendar pa lahko vidite, kako zdaj
v kodi, boste verjetno

377
00:17:39,140 --> 00:17:41,910
morali napisati malo bolj
kompleksnost, da to uresničimo.

378
00:17:41,910 --> 00:17:44,510
In v resnici, kaj operater
v C verjetno lets

379
00:17:44,510 --> 00:17:48,110
si čudežno to krožnost storiti?

380
00:17:48,110 --> 00:17:50,160
Ja upravljavec modulo,
odstotek znamenje.

381
00:17:50,160 --> 00:17:53,160
Torej, kaj je nekako kul o vrsti,
čeprav smo ostali risanje nize

382
00:17:53,160 --> 00:17:56,520
saj te, kot ravnih črt, če vas
nekako razmišljam o tem, kot krivljenje

383
00:17:56,520 --> 00:18:00,341
okoli kot kroga, potem samo
Intuitivno to nekako deluje duševno

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

385
00:18:01,590 --> 00:18:05,190
Ti bi še vedno morali izvajati
da je duševno model v kodi.

386
00:18:05,190 --> 00:18:07,550
Torej ni tako težko,
na koncu, izvajanje,

387
00:18:07,550 --> 00:18:12,430
vendar smo še vedno izgubili size-- bolje,
Sposobnost, da spremenite velikost, če bomo to storili.

388
00:18:12,430 --> 00:18:15,310
>> Moramo se znebiti matriki smo
ga nadomestiti z enim samim kazalcem,

389
00:18:15,310 --> 00:18:20,010
in potem nekje v moji kodi imam
klic, kaj deluje, da dejansko ustvarjanje

390
00:18:20,010 --> 00:18:23,720
array imenovane številke?

391
00:18:23,720 --> 00:18:26,190
Malloc, ali nekaj podobnega
funkcija, točno.

392
00:18:26,190 --> 00:18:30,481
Vsa vprašanja v zvezi nizov ali čakalne vrste.

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

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

395
00:18:33,657 --> 00:18:34,240
Dobro vprašanje.

396
00:18:34,240 --> 00:18:35,830
Kaj modulo bi uporabili tukaj.

397
00:18:35,830 --> 00:18:38,520
Tako na splošno pri uporabi
mod, bi si to naredil

398
00:18:38,520 --> 00:18:40,620
z velikostjo od
celotno strukturo podatkov.

399
00:18:40,620 --> 00:18:44,120
Torej nekaj podobnega kot pet ali sposobnosti, če
je konstanta, ki je verjetno vpletena.

400
00:18:44,120 --> 00:18:47,100
Ampak samo delaš modulo pet
Verjetno ne zadostuje,

401
00:18:47,100 --> 00:18:51,380
saj moramo vedeti počnemo
ovijte okoli tukaj ali tukaj ali tukaj.

402
00:18:51,380 --> 00:18:54,160
Torej, ste verjetno tudi
želeli vključiti

403
00:18:54,160 --> 00:18:57,220
velikost stvar, ali
sprednja spremenljivka tudi.

404
00:18:57,220 --> 00:19:00,140
Torej, to je samo to razmeroma
preprosta aritmetična izraz,

405
00:19:00,140 --> 00:19:02,000
vendar bi modulo ključna sestavina.

406
00:19:02,000 --> 00:19:03,330
>> Torej, kratki film, če boste.

407
00:19:03,330 --> 00:19:05,780
Animacija, da nekateri
ljudje na drugi univerzi

408
00:19:05,780 --> 00:19:08,060
skupaj, ki smo jih
prilagojen za to razpravo.

409
00:19:08,060 --> 00:19:12,630
Gre Jack učenju
dejstva o čakalnih vrst in statistiko.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Nekoč,
tam je bil fant z imenom Jack.

412
00:19:21,890 --> 00:19:25,330
Ko je prišel, da bi prijatelji,
Jack ni imela smisel.

413
00:19:25,330 --> 00:19:28,220
Torej, Jack šel govoriti na
Najbolj priljubljen fant vedel.

414
00:19:28,220 --> 00:19:30,920
Odšel je Lou in vprašal, kaj naj storim?

415
00:19:30,920 --> 00:19:33,400
Lou videl, da je njegov prijatelj
je bil res v stiski.

416
00:19:33,400 --> 00:19:36,050
No, on je začel, samo
poglej, kako ste oblečeni.

417
00:19:36,050 --> 00:19:38,680
Nimaš nobenih oblačil
z drugačnim videzom?

418
00:19:38,680 --> 00:19:39,660
Ja, je dejal Jack.

419
00:19:39,660 --> 00:19:40,840
Sem prepričan storiti.

420
00:19:40,840 --> 00:19:43,320
Prišel v mojo hišo in
Pokazal jim bom za vas.

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

422
00:19:44,550 --> 00:19:47,520
In Jack pokazala Lou polje
kjer se je ohranil vse njegove srajce,

423
00:19:47,520 --> 00:19:49,260
in njegove hlače, in njegove nogavice.

424
00:19:49,260 --> 00:19:52,290
Lou je rekel, vidim, da imate
vsa vaša oblačila v kupu.

425
00:19:52,290 --> 00:19:54,870
Zakaj ne nosiš nekaj
drugi enkrat v nekaj časa?

426
00:19:54,870 --> 00:19:58,020
>> Jack je rekel, dobro, ko sem
odstraniti oblačila in nogavice,

427
00:19:58,020 --> 00:20:00,780
Sem jih operemo in dal
jim stran v polje.

428
00:20:00,780 --> 00:20:03,210
Potem pride naslednji
zjutraj, in do sem hop.

429
00:20:03,210 --> 00:20:06,380
Grem na polje in dobili
moje obleke off vrhu.

430
00:20:06,380 --> 00:20:09,070
Lou hitro spoznal
problem z Jackom.

431
00:20:09,070 --> 00:20:12,080
Je ohranil oblačila, CD-jev,
in knjige v dimnika.

432
00:20:12,080 --> 00:20:14,420
Ko je prišel za
Nekaj ​​za branje ali za nošenje,

433
00:20:14,420 --> 00:20:17,100
on bi izbrati top knjigo ali spodnje perilo.

434
00:20:17,100 --> 00:20:19,500
Potem ko je bil storil, je
bi ga dal nazaj.

435
00:20:19,500 --> 00:20:21,970
Nazaj bi šlo, na vrhu kupa.

436
00:20:21,970 --> 00:20:24,460
Vem, da je rešitev,
dejal zmagoslavno Loud.

437
00:20:24,460 --> 00:20:27,090
Moraš se naučiti
začeti uporabljati čakalno vrsto.

438
00:20:27,090 --> 00:20:29,870
Lou je oblačila Jack in
jim visijo v omari.

439
00:20:29,870 --> 00:20:32,710
In ko je izpraznil
polje, je pravkar ga vrgel.

440
00:20:32,710 --> 00:20:36,500
>> Potem je rekel, zdaj Jack, na koncu
dan, dal svojo obleko na levi strani

441
00:20:36,500 --> 00:20:37,990
ko jih dal proč.

442
00:20:37,990 --> 00:20:41,300
Potem jutri zjutraj, ko vas
glej sonce, dobili vaših oblačil

443
00:20:41,300 --> 00:20:43,440
na desni, od konca vrstice.

444
00:20:43,440 --> 00:20:44,880
Ali ne vidiš? je rekel Lou.

445
00:20:44,880 --> 00:20:46,370
To bo tako lepo.

446
00:20:46,370 --> 00:20:49,770
Boste nositi vse, enkrat
preden kaj nositi dvakrat.

447
00:20:49,770 --> 00:20:52,670
In z vsem v čakalnih vrst
v svoji omari in police

448
00:20:52,670 --> 00:20:55,160
Jack začel počutiti
povsem prepričani o sebi.

449
00:20:55,160 --> 00:20:59,720
Vse zahvaljujoč Lou in
Njegov čudovit čakalne vrste.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: V redu, to je čudovit.

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

452
00:21:05,920 --> 00:21:10,080
Torej, kaj je bilo v resnici dogaja
na pod pokrovom zdaj?

453
00:21:10,080 --> 00:21:12,370
Da imamo kazalce,
da imamo malloc,

454
00:21:12,370 --> 00:21:15,680
da imamo možnost, da ustvarijo
kose pomnilnika za nas

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

456
00:21:16,344 --> 00:21:18,510
Torej je to slika smo
zagledali šele drugi dan.

457
00:21:18,510 --> 00:21:21,180
Mi ni res živijo
na njej, vendar pa je ta slika

458
00:21:21,180 --> 00:21:24,180
bil je dogajalo pod
napa tednov zdaj.

459
00:21:24,180 --> 00:21:27,050
In tako to pomeni, samo
pravokotnik, ki smo pripravljeni,

460
00:21:27,050 --> 00:21:28,180
pomnilnik vašega računalnika.

461
00:21:28,180 --> 00:21:31,850
In morda vaš računalnik ali CS50
ID, ima gigabajt pomnilnika ali RAM

462
00:21:31,850 --> 00:21:33,050
ali dva gigabajta ali štiri.

463
00:21:33,050 --> 00:21:34,450
To sploh ni pomembno.

464
00:21:34,450 --> 00:21:37,240
Vaš operacijski sistem
Windows ali Mac OS ali Linux,

465
00:21:37,240 --> 00:21:41,120
v bistvu omogoča vaš program
misliti, da ima dostop

466
00:21:41,120 --> 00:21:42,982
za celoto
računalnika spomin,

467
00:21:42,982 --> 00:21:45,440
čeprav vas bo morda teče
več programov naenkrat.

468
00:21:45,440 --> 00:21:46,990
Torej, v resnici, da v resnici ne deluje.

469
00:21:46,990 --> 00:21:49,448
Ampak to je neke vrste iluzija
dati vse svoje programe.

470
00:21:49,448 --> 00:21:53,110
Torej, če ste imeli dve nastopov RAM-a, to
je, kako lahko računalnik si o njej mislijo.

471
00:21:53,110 --> 00:21:57,110
>> Zdaj pa po naključju, je eden od teh
stvari, eden izmed teh segmentov pomnilnika,

472
00:21:57,110 --> 00:21:58,350
se imenuje kup.

473
00:21:58,350 --> 00:22:01,680
In res kadarkoli
doslej v pisanje kode

474
00:22:01,680 --> 00:22:05,900
ki ste jih imenuje
funkcija, na primer vod.

475
00:22:05,900 --> 00:22:08,410
Spomnimo se, da vsak čas sem imel
Drawn računalnika spomin,

476
00:22:08,410 --> 00:22:10,640
Vedno rišem nekako
polovica pravokotnika tukaj

477
00:22:10,640 --> 00:22:12,520
in ne trudim govoriti
o tem, kaj je zgoraj.

478
00:22:12,520 --> 00:22:15,980
Ker, ko je glavna imenuje, Trdim
da dobiš to žarek spomina

479
00:22:15,980 --> 00:22:16,970
da gre tukaj dol.

480
00:22:16,970 --> 00:22:20,650
In če glavna imenuje funkcija
kot so zamenjave, ter swap gre tukaj.

481
00:22:20,650 --> 00:22:23,720
In se je izkazalo, da je
kam to konča.

482
00:22:23,720 --> 00:22:26,277
Na nekaj imenujemo kup
znotraj pomnilnika računalnika.

483
00:22:26,277 --> 00:22:28,360
Sedaj na koncu dneva,
to je samo obravnava.

484
00:22:28,360 --> 00:22:30,680
To je kot bajt ničlo,
bajt ena, bajt 2 milijardi.

485
00:22:30,680 --> 00:22:33,130
Ampak, če mislite, da o tem
kot to pravokotnega predmeta,

486
00:22:33,130 --> 00:22:35,130
Vse počneva vsak
Čas pravimo funkcija je

487
00:22:35,130 --> 00:22:37,180
plastenjem nov rezino pomnilnika.

488
00:22:37,180 --> 00:22:41,700
Mi daje to funkcijo rezina
lastnega pomnilnika delati.

489
00:22:41,700 --> 00:22:44,490
>> In spomni se zdaj, da je to pomembno.

490
00:22:44,490 --> 00:22:46,400
Ker če ne bomo imeli
nekaj podobnega zamenjave

491
00:22:46,400 --> 00:22:51,610
in dva lokalne spremenljivke, kot so A in B,
bomo spremenili te vrednote iz ene in dva

492
00:22:51,610 --> 00:22:55,130
za dva in enega, odpoklica
da ko swap vrne,

493
00:22:55,130 --> 00:22:58,330
to je, kot da ta rezina
spomina je pravkar šla.

494
00:22:58,330 --> 00:23:00,080
V resnici pa je še vedno
tam forensically.

495
00:23:00,080 --> 00:23:01,940
In kar je še vedno tam dejansko.

496
00:23:01,940 --> 00:23:05,410
Vendar konceptualno, to je kot
čeprav je to popolnoma izginila.

497
00:23:05,410 --> 00:23:10,910
In tako glavni ne pozna nobenega dela,
ki je bilo storjeno v tej funkciji swap,

498
00:23:10,910 --> 00:23:14,890
razen če je to dejansko prenesejo na tiste,
Argumenti, ki jih kazalcem ali s sklicevanjem.

499
00:23:14,890 --> 00:23:17,790
Zdaj, temeljna rešitev
na ta problem z zamenjavo

500
00:23:17,790 --> 00:23:19,970
je mimo stvari po naslovu.

501
00:23:19,970 --> 00:23:23,250
Ampak se je izkazalo tudi, kaj je
se dogaja na zgoraj navedenem delu

502
00:23:23,250 --> 00:23:26,330
pravokotnika je ves ta čas
še tam je več pomnilnika tam gor.

503
00:23:26,330 --> 00:23:28,790
In ko boste dinamično
dodeliti pomnilnika,

504
00:23:28,790 --> 00:23:32,020
ali je to znotraj GetString, ki
smo počeli za vas v CS50

505
00:23:32,020 --> 00:23:34,710
knjižnica, ali če se vidva
klic malloc in vprašati

506
00:23:34,710 --> 00:23:37,950
operacijski sistem za kos
spomin, da ne prihaja iz dimnika.

507
00:23:37,950 --> 00:23:40,960
To izhaja iz drugega kraja
v pomnilniku računalnika

508
00:23:40,960 --> 00:23:42,220
da se imenuje kup.

509
00:23:42,220 --> 00:23:43,430
In to ni nič drugače.

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 spomin.

512
00:23:45,160 --> 00:23:49,080
To je samo RAM, ki je do
tam namesto dol.

513
00:23:49,080 --> 00:23:50,750
>> In tako, kaj to pomeni?

514
00:23:50,750 --> 00:23:53,650
No, če ima vaš računalnik
končna količina pomnilnika

515
00:23:53,650 --> 00:23:57,450
in kup odrašča, zato
govoriti, in kup, po

516
00:23:57,450 --> 00:23:59,349
te puščice, raste dol.

517
00:23:59,349 --> 00:24:01,140
Z drugimi besedami, vsak
Čas pokličete malloc,

518
00:24:01,140 --> 00:24:03,430
Bili ste dali rezino
pomnilnika od zgoraj,

519
00:24:03,430 --> 00:24:06,630
potem pa malo nižje, nato pa malo
nižje, vsakič, ko klic malloc,

520
00:24:06,630 --> 00:24:10,100
kup, da je navada,
je vrsta raste,

521
00:24:10,100 --> 00:24:11,950
raste bližje in bližje, kaj?

522
00:24:11,950 --> 00:24:13,382
Sveženj.

523
00:24:13,382 --> 00:24:14,840
Torej se to zdi dobra ideja?

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

525
00:24:18,420 --> 00:24:22,140
Mislim, če je to v resnici ni jasno,
kaj še lahko storite, če ste le

526
00:24:22,140 --> 00:24:23,910
imajo končno količino pomnilnika.

527
00:24:23,910 --> 00:24:25,200
Ampak to je zagotovo slabo.

528
00:24:25,200 --> 00:24:27,920
Ti dve puščici določijo na
Crash Course drug za drugega.

529
00:24:27,920 --> 00:24:31,930
>> In se je izkazalo, da je slab fant, ljudje, ki
so še posebej dobro s programiranjem,

530
00:24:31,930 --> 00:24:36,140
in poskuša vdreti v računalnike,
lahko izkoriščajo to realnost.

531
00:24:36,140 --> 00:24:38,290
V resnici pa menijo
malo odrezek.

532
00:24:38,290 --> 00:24:41,350
Torej, to je primer, si lahko preberete
podrobneje na Wikipediji o v.

533
00:24:41,350 --> 00:24:43,100
Vam bomo kazali na
članek, če radoveden.

534
00:24:43,100 --> 00:24:45,650
Ampak tam je napad na splošno
znan kot varovalni preliva da

535
00:24:45,650 --> 00:24:49,570
obstaja že tako dolgo kot ljudje
so imeli možnost, da manipulirajo

536
00:24:49,570 --> 00:24:53,120
računalnika spomin, še posebej v C.
Torej je to zelo poljubna program

537
00:24:53,120 --> 00:24:55,130
ampak dajmo brati od spodaj navzgor.

538
00:24:55,130 --> 00:24:57,650
Main v argc char zvezdic argv.

539
00:24:57,650 --> 00:24:59,830
Torej, to je program, ki traja
argumenti v ukazni vrstici.

540
00:24:59,830 --> 00:25:03,620
In vsi glavni pa očitno je klic
funkcijo, jo pokličite F za preprostost.

541
00:25:03,620 --> 00:25:04,610
In prehaja v kaj?

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

543
00:25:05,490 --> 00:25:09,320
Tako da prehaja v F karkoli
Beseda je, da Vtipkali

544
00:25:09,320 --> 00:25:11,500
na poziv po vrstnem
Ime programa sploh.

545
00:25:11,500 --> 00:25:15,730
Toliko kot Cezarja ali Vigenere, ki
boste morda odpoklic delaš z argv.

546
00:25:15,730 --> 00:25:16,680
>> Torej, kaj je F?

547
00:25:16,680 --> 00:25:19,760
F je v nizu
kot edini argument,

548
00:25:19,760 --> 00:25:22,100
AKA char zvezda, enako
stvar, kot niz.

549
00:25:22,100 --> 00:25:24,920
In se imenuje samovoljno
bar v tem primeru.

550
00:25:24,920 --> 00:25:27,710
In potem char c 12,
samo v smislu navadnega je,

551
00:25:27,710 --> 00:25:31,750
kaj je char c nosilec 12 delaš za nas?

552
00:25:31,750 --> 00:25:33,440
Kaj pa je naredil?

553
00:25:33,440 --> 00:25:36,490
Dodeljevanje pomnilnika, še posebej
12 bajte za 12 znakov.

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

555
00:25:36,990 --> 00:25:40,000
In potem je zadnja vrstica, premešamo in
Kopija, ki ste jih verjetno ni videl.

556
00:25:40,000 --> 00:25:43,360
To je niz kopija
funkcija, katere namen v življenju

557
00:25:43,360 --> 00:25:48,160
je, da kopirate svojo drugo trditev
v svoji prvi argument,

558
00:25:48,160 --> 00:25:51,190
vendar le do
Določeno število bajtov.

559
00:25:51,190 --> 00:25:53,860
Torej tretji argument pravi,
koliko bajtov morate kopirati?

560
00:25:53,860 --> 00:25:56,720
Dolžina vrat,
kar uporabnik vtipka.

561
00:25:56,720 --> 00:25:59,320
In vsebina
bar, ta niz, so

562
00:25:59,320 --> 00:26:02,330
kopirati v pomnilnik opozoril na na C.

563
00:26:02,330 --> 00:26:04,060
>> Torej, to se zdi nekako neumno, in je.

564
00:26:04,060 --> 00:26:06,300
To je izmišljeno primer,
ampak to je reprezentativen

565
00:26:06,300 --> 00:26:10,100
iz razreda napadom vektorjev,
način napadajo program.

566
00:26:10,100 --> 00:26:15,050
Vse je lepo in prav, če uporabnik
vrste v eno besedo, ki je 11 znakov

567
00:26:15,050 --> 00:26:18,040
ali manj, plus poševnica nazaj nič.

568
00:26:18,040 --> 00:26:22,830
Kaj pa, če uporabnik vnese v več kot
11 ali 12 ali 20 ali 50 znakov?

569
00:26:22,830 --> 00:26:25,090
Kaj je to program, boš naredil?

570
00:26:25,090 --> 00:26:29,360
Potencialno seg krivda. To se dogaja
slepo kopirati vse v baru navzgor

571
00:26:29,360 --> 00:26:31,750
njegovi dolžini, ki je
dobesedno vse, kar je v barih,

572
00:26:31,750 --> 00:26:36,307
v naslovu opozoril na C. But C
je le preemptively podana kot 12 bajtov.

573
00:26:36,307 --> 00:26:37,640
Vendar ni dodatno preverjanje.

574
00:26:37,640 --> 00:26:38,700
Če pogojev ni.

575
00:26:38,700 --> 00:26:40,580
Ni preverjanje tu napake.

576
00:26:40,580 --> 00:26:43,270
>> In kaj je ta program
tekoč storiti, je le slepo

577
00:26:43,270 --> 00:26:45,750
kopirate eno stvar za drugo.

578
00:26:45,750 --> 00:26:47,880
In tako, če potegnemo to
kot sliko, tukaj je

579
00:26:47,880 --> 00:26:49,860
samo žarek pomnilniški prostor.

580
00:26:49,860 --> 00:26:53,470
Tako obvestilo na dnu, smo
imajo lokalne variabilne bar.

581
00:26:53,470 --> 00:26:57,330
Tako da je kazalec, da se dogaja, da store--
namesto te lokalne trditev, da je

582
00:26:57,330 --> 00:26:58,672
dogaja, da shranite niz bar.

583
00:26:58,672 --> 00:27:00,380
In potem opazili samo
nad njo v kup,

584
00:27:00,380 --> 00:27:02,505
ker vsakič, ko si vprašal
Za spomin na kupu,

585
00:27:02,505 --> 00:27:04,310
gre malo
nad njo slikovno,

586
00:27:04,310 --> 00:27:06,270
Obvestilo, da imamo 12 bajtov tja.

587
00:27:06,270 --> 00:27:10,690
Zgoraj levo je ena C nosilec nič in
V spodnjem desnem kotu je ena C nosilec 11.

588
00:27:10,690 --> 00:27:12,870
To je samo, kako so računalniki
dogaja, da ga položite ven.

589
00:27:12,870 --> 00:27:18,300
Torej samo intuitivno, če ima bar več
kot 12 znakov v celoti, vključno z

590
00:27:18,300 --> 00:27:25,790
Nagibnica nič, kjer je
12 ali C nosilec 12 šli?

591
00:27:25,790 --> 00:27:28,440
Oziroma, če je 12.
značaj ali 13. značaj,

592
00:27:28,440 --> 00:27:30,900
stoti znak dogaja
končajo na sliki?

593
00:27:30,900 --> 00:27:33,400
Zgoraj ali spodaj?

594
00:27:33,400 --> 00:27:36,300
>> Prav, ker čeprav
Sveženj sama raste navzgor,

595
00:27:36,300 --> 00:27:39,590
ko ste dal stvari v
to je za oblikovalskih razlogov,

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

597
00:27:41,294 --> 00:27:44,460
Torej, če imaš več kot 12 bajtov,
boš začeti prepisati bar.

598
00:27:44,460 --> 00:27:47,280
Zdaj, ko je napako, vendar je
ni res big deal.

599
00:27:47,280 --> 00:27:51,130
Ampak to je velik posel, saj je
več stvari dogaja v pomnilniku.

600
00:27:51,130 --> 00:27:53,074
Torej, tukaj je, kako bi lahko
dal zdravo, da bo jasno.

601
00:27:53,074 --> 00:27:54,490
Če sem tipkal v pozdrav na poziv.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O Nagibnica nič, konča znotraj
ti 12 bajtov, in smo super varna.

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

604
00:28:00,330 --> 00:28:03,020
Ampak, če sem kaj natipkali
več, morda je

605
00:28:03,020 --> 00:28:05,860
dogaja, da lezenje v bar prostor.

606
00:28:05,860 --> 00:28:08,405
Ampak še huje, se izkaže
ven vsem tem času,

607
00:28:08,405 --> 00:28:11,530
čeprav se nikoli nismo pogovarjali o
to je kup uporablja za druge stvari.

608
00:28:11,530 --> 00:28:13,560
To ni le lokalne spremenljivke.

609
00:28:13,560 --> 00:28:15,100
>> C je jezik zelo nizko raven.

610
00:28:15,100 --> 00:28:17,810
In to je nekako na skrivaj
uporablja stack tudi

611
00:28:17,810 --> 00:28:21,260
da se spomniš, ko
Funkcija se imenuje, kaj

612
00:28:21,260 --> 00:28:26,040
naslov je prejšnji funkciji
tako da lahko skoči nazaj na to funkcijo.

613
00:28:26,040 --> 00:28:29,980
Torej, ko glavni klici zamenjali, med
stvari potisniti na kupu

614
00:28:29,980 --> 00:28:34,380
niso samo zamenjav lokalnih spremenljivk,
ali njeni argumenti, tudi na skrivaj porinil

615
00:28:34,380 --> 00:28:37,510
na kupu, kot je predstavljena
z rdečim rezine tod

616
00:28:37,510 --> 00:28:40,520
je naslov glavne fizično
v spominu računalnika,

617
00:28:40,520 --> 00:28:44,180
tako da, ko je zamenjava opravljeno, računalnik
ve, da moram iti nazaj na glavno

618
00:28:44,180 --> 00:28:46,760
in konča izvedbo glavno funkcijo.

619
00:28:46,760 --> 00:28:51,960
Torej je to nevarno sedaj, ker če
uporabnik vnese v dobro več kot zdravo,

620
00:28:51,960 --> 00:28:57,030
tako da vhod uporabnikova clobbers
ali prepiše ta rdeči del,

621
00:28:57,030 --> 00:28:59,820
logično, če računalnika
le, da bo slepo prevzame

622
00:28:59,820 --> 00:29:03,830
da so bajtov tem rdeče rezine
naslov, na katerega bi se moral vrniti,

623
00:29:03,830 --> 00:29:09,020
Kaj pa, če nasprotnik je dovolj pameten, ali
dovolj srečni, da bi dal zaporedje bajtov

624
00:29:09,020 --> 00:29:13,450
tam, da izgleda kot naslov,
ampak to je naslov kode

625
00:29:13,450 --> 00:29:18,730
da je on ali ona želi računalnik
izvršiti namesto glavnega?

626
00:29:18,730 --> 00:29:21,670
>> Z drugimi besedami, če je kaj na
Uporabnik je tipkanje na poziv,

627
00:29:21,670 --> 00:29:23,850
ni samo nekaj,
neškodljive kot zdravo,

628
00:29:23,850 --> 00:29:28,210
ampak to je dejansko kodo, ki je enakovreden
izbrisati vse datoteke Ta uporabnik je?

629
00:29:28,210 --> 00:29:30,060
Ali email svoje geslo z mano?

630
00:29:30,060 --> 00:29:31,940
Ali začeti prijavite svoje
tipkanja, kajne?

631
00:29:31,940 --> 00:29:34,920
Obstaja način, dajmo določajo danes,
da bi jih tip v ne samo zdravo

632
00:29:34,920 --> 00:29:36,711
svet ali njihovo ime,
so lahko v bistvu

633
00:29:36,711 --> 00:29:39,570
prenese v kodo, ničle in
tisti, ki računalnik

634
00:29:39,570 --> 00:29:43,450
napake tako za kodo in naslov.

635
00:29:43,450 --> 00:29:48,950
Torej, čeprav je nekoliko abstraktno, če
uporabnik vnese v dovolj kontradiktornosti kodo

636
00:29:48,950 --> 00:29:52,330
da bomo posplošiti tukaj
A. A je napad ali nasprotniki.

637
00:29:52,330 --> 00:29:53,140
Tako da samo slabe stvari.

638
00:29:53,140 --> 00:29:55,306
Mi ne skrbi
številke ali ničle ali tisti,

639
00:29:55,306 --> 00:29:59,470
danes, tako da boste na koncu
prepisovanju ta rdeči del,

640
00:29:59,470 --> 00:30:01,580
opazili, da je zaporedje bajtov.

641
00:30:01,580 --> 00:30:05,020
O 835 Cnič osem nič.

642
00:30:05,020 --> 00:30:08,960
In zdaj, ko Wikipedije članek tukaj
je predlagal, če boste zdaj dejansko začeli

643
00:30:08,960 --> 00:30:12,460
označevanje bajtov v vašem računalniku
spomin, kaj je članek Wikipedija

644
00:30:12,460 --> 00:30:19,060
predlagateljica je to, kaj pa če je naslov
navedene zgornjem levem bajt 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Z drugimi besedami, če je slab fant je
dovolj pameten s svojo kodo

646
00:30:22,200 --> 00:30:26,650
dejansko dal številko tukaj, da
ustreza naslovu oznake

647
00:30:26,650 --> 00:30:29,180
on ali ona vbrizga
v računalniku,

648
00:30:29,180 --> 00:30:31,050
lahko trik računalnik
v delaš karkoli.

649
00:30:31,050 --> 00:30:34,140
Odstranjevanje datotek, pošiljanje e-pošte
Stvari, nahod svojega prometa,

650
00:30:34,140 --> 00:30:36,710
dobesedno vse, kar bi lahko
vbrizga v računalniku.

651
00:30:36,710 --> 00:30:39,220
In tako buffer overflow
napad v svojem jedru

652
00:30:39,220 --> 00:30:43,530
je samo neumna, neumna
prevlada od matrike, ki

653
00:30:43,530 --> 00:30:45,840
niso imeli preveriti njene meje.

654
00:30:45,840 --> 00:30:48,850
In to je tisto, kar je super nevarno
in hkrati super močan

655
00:30:48,850 --> 00:30:52,560
v C je, da smo zares imeli
dostop do kjerkoli v pomnilniku.

656
00:30:52,560 --> 00:30:55,320
To je odvisno od nas, programerji,
ki pišejo izvirno kodo

657
00:30:55,320 --> 00:30:59,330
preveriti dolžino darn kateregakoli
nizi, da smo manipuliranja.

658
00:30:59,330 --> 00:31:00,750
Torej, da bo jasno, kaj je fix?

659
00:31:00,750 --> 00:31:03,190
Če smo roll nazaj na to
koda, jaz ne bi samo

660
00:31:03,190 --> 00:31:08,000
spremeniti dolžino vrat, kar
sicer bi moral biti preverjanje?

661
00:31:08,000 --> 00:31:10,620
Kaj drugega naj se delaš, da
popolnoma preprečiti ta napad?

662
00:31:10,620 --> 00:31:14,110
Nočem, da bi le slepo reči
da bi morali kopirati toliko bajtov

663
00:31:14,110 --> 00:31:16,140
kot je dolžina vrat.

664
00:31:16,140 --> 00:31:18,910
Hočem reči, kopirate
veliko bajti, kot so v barih

665
00:31:18,910 --> 00:31:24,090
do dodeljena
spomin, ali 12 maksimalno.

666
00:31:24,090 --> 00:31:27,450
Torej rabim nekakšen če pogoj
da ne preveri dolžino vrat,

667
00:31:27,450 --> 00:31:32,800
če pa preseže 12, samo trdo kodo
12, kot je v največji možni razdalji.

668
00:31:32,800 --> 00:31:35,910
V nasprotnem primeru se ti buffer
overflow napad lahko zgodi.

669
00:31:35,910 --> 00:31:38,451
Na dnu teh stekelc,
Če ste radovedni, da preberete več

670
00:31:38,451 --> 00:31:41,200
je dejanska izvirni članek
če želite, da pogled.

671
00:31:41,200 --> 00:31:44,550
>> Toda zdaj, med cenami
plačan tukaj je neučinkovitosti.

672
00:31:44,550 --> 00:31:46,680
Tako da je to lahko hitro
nizka pogled raven, na kaj

673
00:31:46,680 --> 00:31:49,709
Težave se lahko pojavijo zdaj, da smo
imajo dostop do pomnilnika računalnika.

674
00:31:49,709 --> 00:31:51,750
Ampak en problem smo
že naletel na ponedeljek

675
00:31:51,750 --> 00:31:53,800
je samo neučinkovitost
iz povezani seznam.

676
00:31:53,800 --> 00:31:56,019
Mi smo nazaj v linearnem času.

677
00:31:56,019 --> 00:31:57,560
Nimamo več sosednji paleto.

678
00:31:57,560 --> 00:31:58,980
Nimamo naključni dostop.

679
00:31:58,980 --> 00:32:00,710
Ne moremo uporabiti oglati oklepaj zapis.

680
00:32:00,710 --> 00:32:04,590
Mi dobesedno morali uporabiti while zanko
kot tisti, ki sem napisal pred nekaj trenutki.

681
00:32:04,590 --> 00:32:09,740
Ampak v ponedeljek, smo trdili, da smo lahko
lezenje nazaj v sfero učinkovitosti

682
00:32:09,740 --> 00:32:13,040
doseči nekaj, kar je
logaritemsko morda, ali še najbolje,

683
00:32:13,040 --> 00:32:16,120
morda celo nekaj, kar je
ti konstantna čas.

684
00:32:16,120 --> 00:32:19,840
Torej, kako lahko naredimo, da z uporabo teh novih
orodja, ti naslovi, ti kazalci,

685
00:32:19,840 --> 00:32:22,210
in navojev stvari sami?

686
00:32:22,210 --> 00:32:23,960
No, recimo, da je
tukaj, to so kup

687
00:32:23,960 --> 00:32:27,170
številk, ki jih želimo shranite v
Struktura podatkov in iskanje učinkovito.

688
00:32:27,170 --> 00:32:30,960
Mi lahko povsem nazaj do tedna
dva, vrgel ti v array,

689
00:32:30,960 --> 00:32:33,150
in jih iskati v dvojiškem iskanje.

690
00:32:33,150 --> 00:32:34,040
Deli in vladaj.

691
00:32:34,040 --> 00:32:37,720
In v resnici si napisal
binarno iskanje v PSET3,

692
00:32:37,720 --> 00:32:40,100
kjer se izvaja program najde.

693
00:32:40,100 --> 00:32:40,890
Ampak veš kaj.

694
00:32:40,890 --> 00:32:45,060
Tam je nekako bolj
pameten način za to.

695
00:32:45,060 --> 00:32:47,390
To je malo bolj
prefinjen in ga morda

696
00:32:47,390 --> 00:32:50,830
nam omogoča, da vidite, zakaj binarni
Iskanje je toliko hitrejši.

697
00:32:50,830 --> 00:32:52,980
Najprej, kaj je uvesti
pojem drevesa.

698
00:32:52,980 --> 00:32:54,730
Ki je, čeprav v
realnost drevesa vrste

699
00:32:54,730 --> 00:32:57,730
rastejo, kot je ta, v svetu računalniku
znanost so vrsta raste navzdol

700
00:32:57,730 --> 00:33:00,830
kot družinsko drevo, kjer imate
vaši stari starši ali stari starši veliko

701
00:33:00,830 --> 00:33:04,580
ali malenkosti na vrhu, patriarha in
Matriarchs družine, le eno

702
00:33:04,580 --> 00:33:07,930
ti koren, vozlišče, spodaj
ki so njegovi otroci,

703
00:33:07,930 --> 00:33:11,442
pod katero so njeni otroci, ali
njegovi potomci bolj na splošno.

704
00:33:11,442 --> 00:33:13,400
In kdo visi off
dno družine

705
00:33:13,400 --> 00:33:16,070
drevo, poleg tega pri čemer je
najmlajši v družini,

706
00:33:16,070 --> 00:33:19,520
Lahko tudi samo biti splošno
imenovani listi drevesa.

707
00:33:19,520 --> 00:33:21,800
>> Torej je to samo kup
besed in definicij

708
00:33:21,800 --> 00:33:25,790
za nekaj, kar se imenuje drevo v računalniku
znanost, podobno kot družinsko drevo.

709
00:33:25,790 --> 00:33:28,770
Ampak tam je Ljubitelj inkarnacije
dreves, od katerih je eden

710
00:33:28,770 --> 00:33:30,780
imenujemo binarno iskalno drevo.

711
00:33:30,780 --> 00:33:34,380
In lahko nekako tease
narazen, kaj ta stvar počne.

712
00:33:34,380 --> 00:33:37,180
No, to je binarni, v kakšnem smislu?

713
00:33:37,180 --> 00:33:41,455
Kje binarni prihaja od tukaj?

714
00:33:41,455 --> 00:33:41,955
Žal?

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

716
00:33:45,961 --> 00:33:47,210
To ni toliko bodisi ali.

717
00:33:47,210 --> 00:33:52,000
To je več, da ima vsaka izmed vozlišč ne
več kot dva otroka, kot smo videli tukaj.

718
00:33:52,000 --> 00:33:54,990
Na splošno je tree-- in
vaši starši in stari starši

719
00:33:54,990 --> 00:33:57,640
imajo lahko toliko otrok ali
vnuki, kot so dejansko želijo,

720
00:33:57,640 --> 00:34:00,820
in tako na primer tam imamo tri
otroci izven te desnem vozlišču,

721
00:34:00,820 --> 00:34:05,480
temveč v binarnem drevesu vozlišče ima
nič, ena ali dva otroka najvišja.

722
00:34:05,480 --> 00:34:08,496
In to je lepa lastnost,
ker če je to omejena z dvema,

723
00:34:08,496 --> 00:34:10,620
bomo mogli
dobili malo dnevnika baze dva

724
00:34:10,620 --> 00:34:11,975
dejanje dogaja na koncu.

725
00:34:11,975 --> 00:34:13,350
Torej, imamo nekaj logaritemsko.

726
00:34:13,350 --> 00:34:14,558
Ampak več o tem v tem trenutku.

727
00:34:14,558 --> 00:34:19,810
Iskanje drevo pomeni, da so številke
razporejena tako, da je leva otroka

728
00:34:19,810 --> 00:34:22,429
je vrednost večja od korena.

729
00:34:22,429 --> 00:34:26,010
In njegova pravica otrok
večja od korena.

730
00:34:26,010 --> 00:34:29,290
Z drugimi besedami, če jemljete katero koli izmed
vozlišča, krogi v tej sliki,

731
00:34:29,290 --> 00:34:31,840
in gleda na levi
Otrok in njegova pravica otrok,

732
00:34:31,840 --> 00:34:34,739
prva mora biti manjša
Drugi mora biti večja od.

733
00:34:34,739 --> 00:34:36,159
Torej sanity check 55.

734
00:34:36,159 --> 00:34:37,780
To je zapustila otroka, je 33.

735
00:34:37,780 --> 00:34:38,620
To je manj kot.

736
00:34:38,620 --> 00:34:40,929
55, njena pravica otrok je 77.

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

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

739
00:34:43,199 --> 00:34:46,480
Mi lahko preveri vsak eno izmed tistih,
vozlišča in isti vzorec bi imel.

740
00:34:46,480 --> 00:34:49,389
>> Torej, kaj je lepo v
binarno iskalno drevo, je

741
00:34:49,389 --> 00:34:52,204
da je eden, ga lahko izvajajo
s struct, tako kot to.

742
00:34:52,204 --> 00:34:54,620
In čeprav smo metali
veliko objektov na vaši,

743
00:34:54,620 --> 00:34:56,560
oni nekoliko
intuitivno zdaj upajmo.

744
00:34:56,560 --> 00:35:00,570
Sintaksa je še vedno Skrivnosten za prepričani,
vendar pa je vsebina vozlišča v tem

745
00:35:00,570 --> 00:35:02,786
context-- in hranimo
z besedo vozlišče,

746
00:35:02,786 --> 00:35:04,910
ali je pravokotnik
na zaslonu ali kroga,

747
00:35:04,910 --> 00:35:08,970
to je samo nekaj generično posoda,
V tem primeru drevesa, podobnega tistemu

748
00:35:08,970 --> 00:35:11,780
smo videli, moramo celo
v vsakem od vozlišč

749
00:35:11,780 --> 00:35:15,460
in potem moram dva kazalca, ki kaže
na levo otroka in desni otroka,

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

751
00:35:16,590 --> 00:35:20,730
Torej, to je, kako bomo morda
sredstva, ki je v struct.

752
00:35:20,730 --> 00:35:22,315
In kako bi jaz to izvesti v kodo?

753
00:35:22,315 --> 00:35:26,730
No, vzemimo hitro
poglej ta majhen primer.

754
00:35:26,730 --> 00:35:29,820
To ne deluje, vendar sem
kopirali in prilepili to strukturo.

755
00:35:29,820 --> 00:35:33,510
In če je moja funkcija za binarne
Iskanje drevo se imenuje iskanje,

756
00:35:33,510 --> 00:35:36,980
in to traja dva argumenta,
celo število N in kazalec

757
00:35:36,980 --> 00:35:41,400
na vozlišča, tako da kazalec na drevesu
ali kazalec do korena drevesa,

758
00:35:41,400 --> 00:35:43,482
kako iti o iskanju za N?

759
00:35:43,482 --> 00:35:45,440
No, najprej, ker sem
ki se ukvarjajo s kazalci,

760
00:35:45,440 --> 00:35:46,750
Bom naredil pregled prištevnosti.

761
00:35:46,750 --> 00:35:54,279
Če drevo Ene enak null, je N
v tem drevo ali ni v tem drevesu?

762
00:35:54,279 --> 00:35:55,070
To ne more biti, kajne?

763
00:35:55,070 --> 00:35:56,870
Če sem mimo null,
tam ni ničesar.

764
00:35:56,870 --> 00:35:59,230
Jaz lahko tudi samo
slepo pravijo vrne false.

765
00:35:59,230 --> 00:36:04,050
Če mi daš nič, jaz zagotovo ne morem
najti številko N. Torej kaj bi jaz

766
00:36:04,050 --> 00:36:04,750
preveriti zdaj?

767
00:36:04,750 --> 00:36:12,830
Jaz bom rekel, tudi drugje, če je N
manj kot vse, kar je na drevo vozlišče

768
00:36:12,830 --> 00:36:16,300
da sem bil izročil N vrednost.

769
00:36:16,300 --> 00:36:20,270
Z drugimi besedami, če je število sem
išče, N, je manjša od vozlišča

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

771
00:36:21,340 --> 00:36:23,190
In vozlišče Iščem
pri imenujemo drevo,

772
00:36:23,190 --> 00:36:26,370
in odpoklic iz prejšnjega primera
da se pri vrednosti v kazalca

773
00:36:26,370 --> 00:36:28,310
I uporabite puščico zapis.

774
00:36:28,310 --> 00:36:35,960
Torej, če je N manj kot drevo puščico
N, želim konceptualno iti levo.

775
00:36:35,960 --> 00:36:38,590
Kako ekspres iskanje po levi?

776
00:36:38,590 --> 00:36:41,560
Da bo jasno, če je to
slika v vprašanju,

777
00:36:41,560 --> 00:36:44,612
in sem bil sprejet, da je vrhunska
arrow ki je obrnjena navzdol.

778
00:36:44,612 --> 00:36:45,570
To je moje drevo kazalec.

779
00:36:45,570 --> 00:36:48,060
Jaz sem gledala v korenu drevesa.

780
00:36:48,060 --> 00:36:52,100
In iščem recimo, za
številka 44, poljubno.

781
00:36:52,100 --> 00:36:55,300
Je 44 manj kot ali
večja od 55 očitno?

782
00:36:55,300 --> 00:36:56,360
Torej, to je manj kot.

783
00:36:56,360 --> 00:36:58,760
In tako je to, če velja pogoj.

784
00:36:58,760 --> 00:37:03,981
Torej konceptualno, kaj hočem
iskanje zraven, če iščem 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Točno, želim
iskanje po levi otroka,

788
00:37:11,100 --> 00:37:12,789
ali levo sub-tree te slike.

789
00:37:12,789 --> 00:37:14,830
In v resnici, pustite me skozi
slika tukaj

790
00:37:14,830 --> 00:37:17,770
za trenutek, saj
Tega ne morem opraskati ven.

791
00:37:17,770 --> 00:37:21,150
Če začnem tukaj na 55, in
Vem, da je vrednost 44

792
00:37:21,150 --> 00:37:23,180
Iščem je
levo, to je neke vrste

793
00:37:23,180 --> 00:37:26,010
podobnega solzenje imenika v
polovico ali solzenje drevo na pol.

794
00:37:26,010 --> 00:37:29,660
Nimam več skrbeti
ta cela polovica drevesa.

795
00:37:29,660 --> 00:37:33,270
In vendar, radovedno v odnosu na
struktura, ta stvar tukaj, ki

796
00:37:33,270 --> 00:37:36,682
se začne z 33, ki sama po sebi
je dvojiško iskalno drevo.

797
00:37:36,682 --> 00:37:39,890
Rekel sem, beseda rekurzivna prej, ker
dejansko je to podatkovna struktura, ki

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

799
00:37:41,707 --> 00:37:44,540
Morda imate drevo, ki je to
velik, vendar vsak od njenih otrok

800
00:37:44,540 --> 00:37:46,870
predstavlja drevo le malo manjši.

801
00:37:46,870 --> 00:37:50,910
Namesto njega pa dedek
ali babica, zdaj pa je samo mama

802
00:37:50,910 --> 00:37:54,300
or-- ne morem say-- ni mama
ali oče, da bi bilo čudno.

803
00:37:54,300 --> 00:37:59,000
Namesto tega dva otroka tam
bi bilo, kot brat in brat.

804
00:37:59,000 --> 00:38:01,120
Nova generacija družinskega drevesa.

805
00:38:01,120 --> 00:38:02,900
Ampak strukturno, to je ista ideja.

806
00:38:02,900 --> 00:38:06,790
In se je izkazalo, da imam funkcijo
s katero sem lahko poiščete binarno iskanje

807
00:38:06,790 --> 00:38:07,290
drevo.

808
00:38:07,290 --> 00:38:08,680
To se imenuje iskanje.

809
00:38:08,680 --> 00:38:17,870
Iščem za N v drevo puščico levo
drugega, če je n večji od vrednosti

810
00:38:17,870 --> 00:38:18,870
da sem trenutno.

811
00:38:18,870 --> 00:38:20,800
55 v zgodbi trenutek nazaj.

812
00:38:20,800 --> 00:38:23,780
Imam funkcijo imenovano
iskanje, da sem lahko samo

813
00:38:23,780 --> 00:38:29,660
mimo N to in rekurzivno iskanje
sub-tree in samo donos

814
00:38:29,660 --> 00:38:30,620
karkoli že to odgovor.

815
00:38:30,620 --> 00:38:33,530
Else Imam nekaj končno bazo primera tukaj.

816
00:38:33,530 --> 00:38:35,310
>> Kaj je končna primer?

817
00:38:35,310 --> 00:38:36,570
Drevo je bodisi nična.

818
00:38:36,570 --> 00:38:39,980
Vrednost bom niti iskal je
manjši od njega ali višja kot tista

819
00:38:39,980 --> 00:38:42,610
ali enako njej.

820
00:38:42,610 --> 00:38:44,750
In lahko rečem enako
enaka, vendar pa je logično, da je

821
00:38:44,750 --> 00:38:46,500
enakovredna samo rekel še tukaj.

822
00:38:46,500 --> 00:38:49,150
Torej, res je, kako sem našel nekaj.

823
00:38:49,150 --> 00:38:51,710
Zato upajmo, da je to
Še bolj prepričljiv primer

824
00:38:51,710 --> 00:38:54,900
kot neumnega funkcijo sigma
smo naredili nekaj predavanj nazaj,

825
00:38:54,900 --> 00:38:58,360
kjer je bilo prav tako enostaven za uporabo zanko
za štetje gor vse številke iz enega

826
00:38:58,360 --> 00:39:02,390
v N. tukaj s podatkovno strukturo
da sama rekurzivno

827
00:39:02,390 --> 00:39:07,050
opredeljena in rekurzivno pripravljeni, zdaj smo
imeti možnost, da sami izrazijo

828
00:39:07,050 --> 00:39:09,780
V kodeksu je rekurzivni, da je sama.

829
00:39:09,780 --> 00:39:12,580
Torej, to je točno isto kodo tukaj.

830
00:39:12,580 --> 00:39:14,400
>> Torej, kaj druge težave lahko rešimo?

831
00:39:14,400 --> 00:39:18,160
Torej, hiter korak stran od
drevesa za trenutek.

832
00:39:18,160 --> 00:39:20,130
Tukaj je, pravijo, nemško zastavo.

833
00:39:20,130 --> 00:39:22,020
In tam je jasno
Vzorec te zastave.

834
00:39:22,020 --> 00:39:23,811
In tam je veliko
Zastave na svetu, ki

835
00:39:23,811 --> 00:39:27,560
so tako enostavno, kot je to v smislu
njihovih barv in vzorcev.

836
00:39:27,560 --> 00:39:31,930
Recimo, da je ta shranjena kot
GIF ali JPEG, ali bitmap ali ping,

837
00:39:31,930 --> 00:39:34,240
katerikoli grafični format datotek
s katerim ste seznanjeni,

838
00:39:34,240 --> 00:39:36,460
nekateri, ki smo
igranje z v PSET4.

839
00:39:36,460 --> 00:39:41,550
To se ne zdi vredno, da shranite
črna pixel, črna pixel, črna pixel,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, cel kup
črnih pik za prvi scanline,

841
00:39:44,790 --> 00:39:47,430
ali vrstica, nato pa cel kup
enaka, potem cel kup

842
00:39:47,430 --> 00:39:49,530
iste, nato pa
cel kup rdečih pik,

843
00:39:49,530 --> 00:39:53,020
rdečih pik, rdeče pik, potem celota
šopek rumenih pik, rumena, kajne?

844
00:39:53,020 --> 00:39:55,050
>> Tam je kot neučinkovitost tukaj.

845
00:39:55,050 --> 00:39:59,040
Kako bi si intuitivno
stisniti nemško zastavo

846
00:39:59,040 --> 00:40:01,320
če ga izvajajo kot datoteko?

847
00:40:01,320 --> 00:40:04,940
Všeč, kaj informacij ne moremo
trudim shranjevanje na disku, da bi

848
00:40:04,940 --> 00:40:08,040
zmanjšati našo velikost datoteke iz podobnih
megabajt do kilobyte, nekaj

849
00:40:08,040 --> 00:40:09,430
manjši?

850
00:40:09,430 --> 00:40:13,130
V čem je redundanca
Tukaj mora biti jasno?

851
00:40:13,130 --> 00:40:13,880
Kaj lahko naredim?

852
00:40:13,880 --> 00:40:14,380
Ja?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Točno tako.

855
00:40:21,970 --> 00:40:24,550
Zakaj ne bi namesto spomnim
barva vsake darn piksla

856
00:40:24,550 --> 00:40:28,200
tako kot počnete v PSET4
z obliko bitmap datoteke,

857
00:40:28,200 --> 00:40:32,060
zakaj ne samo predstavljajo
Skrajno levi stolpec slikovnih pik, na primer

858
00:40:32,060 --> 00:40:35,370
kup črnih pik, kup
rdeče, in kup rumena,

859
00:40:35,370 --> 00:40:39,210
in potem nekako kodiranje
Zamisel o ponovite ta 100-krat

860
00:40:39,210 --> 00:40:41,020
ali ponovite 1000-krat?

861
00:40:41,020 --> 00:40:43,430
Kjer je 100 ali 1000 je
samo celo število, zato vas

862
00:40:43,430 --> 00:40:47,290
lahko izmaže samo eno številko
namesto da bi več sto ali tisoč

863
00:40:47,290 --> 00:40:48,270
dodatnih pik.

864
00:40:48,270 --> 00:40:50,990
In res, to je, kako smo
lahko stisne nemško zastavo.

865
00:40:50,990 --> 00:40:51,490
In

866
00:40:51,490 --> 00:40:53,470
Zdaj kaj francosko zastavo?

867
00:40:53,470 --> 00:40:58,930
In malo nekakšna
mentalna vaja, ki zastava

868
00:40:58,930 --> 00:41:01,040
je mogoče stisniti več na disku?

869
00:41:01,040 --> 00:41:05,720
Nemška zastava ali francoščina
zastava, če vzamemo, da je pristop?

870
00:41:05,720 --> 00:41:08,490
Nemška zastava, ker tam je
bolj horizontalno odveč.

871
00:41:08,490 --> 00:41:12,190
In z zasnovo, mnogi grafična datoteka
Oblike zares delujejo kot skeniranja linije

872
00:41:12,190 --> 00:41:12,830
vodoravno.

873
00:41:12,830 --> 00:41:14,674
Da bi lahko delali
navpično, samo človeštvo

874
00:41:14,674 --> 00:41:17,090
Pred odločili let, da bomo
običajno razmišljati o stvari zapored

875
00:41:17,090 --> 00:41:18,880
z vrstico namesto kolono s kolone.

876
00:41:18,880 --> 00:41:20,820
Torej res, če ste bili
pogledati datoteko

877
00:41:20,820 --> 00:41:24,670
Velikost nemško zastavo in francoščini
zastave, tako dolgo, kot je ločljivost

878
00:41:24,670 --> 00:41:27,530
enako, enako širino
ter višine, tale

879
00:41:27,530 --> 00:41:31,580
tukaj se bo večji, ker vas
morali sami ponovite trikrat.

880
00:41:31,580 --> 00:41:35,570
Morate navesti modro, ponovitev
sami, bela, ponovite sami, rdeča,

881
00:41:35,570 --> 00:41:36,740
ponovite sami.

882
00:41:36,740 --> 00:41:39,000
Ne moreš kar iti vse
pot v desno.

883
00:41:39,000 --> 00:41:41,200
In kot prahi, da bi
počistite stiskanje

884
00:41:41,200 --> 00:41:43,910
je povsod, če so ti
štirje okvirji iz video-- vas

885
00:41:43,910 --> 00:41:45,890
Morda se spomni, da je film
ali video je na splošno

886
00:41:45,890 --> 00:41:47,286
kot 29 ali 30 sličic na sekundo.

887
00:41:47,286 --> 00:41:50,410
To je kot malo flip knjigo, kjer vas
le glej slike, slike, slike, slike,

888
00:41:50,410 --> 00:41:54,410
slika samo super hitro, tako da izgleda kot
akterji na zaslonu se gibljejo.

889
00:41:54,410 --> 00:41:57,130
Tukaj je čmrljev na
vrh kup cvetja.

890
00:41:57,130 --> 00:41:59,790
In čeprav bi bilo nekako
težko videti na prvi pogled,

891
00:41:59,790 --> 00:42:04,020
edina stvar gibljejo
Ta film je čebela.

892
00:42:04,020 --> 00:42:06,880
>> Kaj je neumna o shranjevanju
video nestisnjena?

893
00:42:06,880 --> 00:42:11,420
To je neke vrste odpadkov, za shranjevanje videa
kot štiri skoraj enakih podob, ki

894
00:42:11,420 --> 00:42:13,670
razlikujejo le toliko, kolikor kje je čebela.

895
00:42:13,670 --> 00:42:16,280
Lahko mečejo najbolj
te informacije

896
00:42:16,280 --> 00:42:20,190
in zapomni samo, na primer,
prvi okvir in zadnji okvir,

897
00:42:20,190 --> 00:42:22,180
Ključne okvirji Če ste
kdaj slišal besedo,

898
00:42:22,180 --> 00:42:24,337
in samo shranite v
sredina, kjer je čebela.

899
00:42:24,337 --> 00:42:26,170
In ti ne bi bilo treba
shranjevanje vseh roza,

900
00:42:26,170 --> 00:42:28,330
in modro, ter
zelene vrednosti, kot dobro.

901
00:42:28,330 --> 00:42:31,200
Torej, to se pravi, da le
Stiskanje je povsod.

902
00:42:31,200 --> 00:42:34,900
To je tehnika, smo pogosto uporabljajo
ali jemljemo za samoumevno v teh dneh.

903
00:42:34,900 --> 00:42:38,750
>> Ampak kako si stisniti besedilo?

904
00:42:38,750 --> 00:42:40,450
Kako greste o stiskanjem besedilo?

905
00:42:40,450 --> 00:42:45,410
No, vsaka od znakov
ASCII je en bajt, ali osem bitov.

906
00:42:45,410 --> 00:42:47,360
In to je nekako neumno, kajne?

907
00:42:47,360 --> 00:42:51,160
Ker ste verjetno tip A
in E in I in O in U veliko

908
00:42:51,160 --> 00:42:55,270
največkrat kot W ali Q ali Z,
odvisno od jezika, v katerem

909
00:42:55,270 --> 00:42:56,610
pišete zagotovo.

910
00:42:56,610 --> 00:42:59,600
In zakaj smo se s pomočjo
osem bitov za vsako pismu,

911
00:42:59,600 --> 00:43:02,040
vključno z najmanj
zanimiva pisma, kajne?

912
00:43:02,040 --> 00:43:05,300
Zakaj ne bi uporabili manj bitov za
super priljubljena pisma,

913
00:43:05,300 --> 00:43:07,760
kot E, stvari, ki jih ugibati
najprej v Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
in uporabite več bitov za
manj zanimiva pisma?

915
00:43:10,450 --> 00:43:10,950
Zakaj?

916
00:43:10,950 --> 00:43:13,130
Ker smo le, da bo
jih uporabljajo manj pogosto.

917
00:43:13,130 --> 00:43:15,838
>> No, izkaže se, da je imela
bil napore, da to storijo.

918
00:43:15,838 --> 00:43:18,630
In če se spomnite iz razreda
šoli ali srednji šoli, Morse code.

919
00:43:18,630 --> 00:43:20,400
Morse code ima pike
in črtice, ki se lahko

920
00:43:20,400 --> 00:43:24,270
prenaša vzdolž žice kot
sliši ali signali neke vrste.

921
00:43:24,270 --> 00:43:25,930
Ampak Morse code je super čist.

922
00:43:25,930 --> 00:43:29,010
To je nekako binarnega sistema
da imate pike ali črtice.

923
00:43:29,010 --> 00:43:30,977
Ampak, če ste videli, na primer, dve piki.

924
00:43:30,977 --> 00:43:33,810
Ali pa, če mislite, da nazaj na izvajalca
ki gre takole pisk, pisk, pisk

925
00:43:33,810 --> 00:43:36,760
pisk, hitting malo sprožilec
ki oddaja signal,

926
00:43:36,760 --> 00:43:40,360
če vas, prejemnik prejme dva
pike, kakšno sporočilo ste prejeli?

927
00:43:40,360 --> 00:43:43,490
Popolnoma samovoljno.

928
00:43:43,490 --> 00:43:44,450
>> JAZ?

929
00:43:44,450 --> 00:43:45,060
JAZ?

930
00:43:45,060 --> 00:43:47,500
Ali kaj about-- ali jaz?

931
00:43:47,500 --> 00:43:49,570
Mogoče je bilo samo dva prava E je?

932
00:43:49,570 --> 00:43:52,480
Tako da je ta problem
od decodability z Morse

933
00:43:52,480 --> 00:43:54,890
kode, pri čemer razen če
Oseba, ki vam pošilja sporočilo

934
00:43:54,890 --> 00:43:59,510
dejansko premori, tako da lahko nekako
videli ali slišali vrzeli med črkami,

935
00:43:59,510 --> 00:44:02,990
to ni dovolj, samo, da
pošljete tok ničel in enic,

936
00:44:02,990 --> 00:44:05,610
ali pike in črtice,
zato, ker je dvoumnost.

937
00:44:05,610 --> 00:44:08,640
E je ena pika, tako da, če vas
glej dve piki ali slišali dve piki,

938
00:44:08,640 --> 00:44:11,254
morda je dva E ali morda je ena I.

939
00:44:11,254 --> 00:44:13,670
Zato moramo sistem, ki je
malo bolj pameten kot to.

940
00:44:13,670 --> 00:44:16,851
Torej človek, imenovan Huffman let
Pred prišel s točno to.

941
00:44:16,851 --> 00:44:18,600
Tako da smo šele tekoč
vzeti hiter pogled

942
00:44:18,600 --> 00:44:20,114
kako so drevesa germane za to.

943
00:44:20,114 --> 00:44:22,530
Recimo, da je to nekaj
neumen sporočilo, ki ga želite poslati,

944
00:44:22,530 --> 00:44:26,342
sestavljajo samo A, B, C v D-jev, in E je,
ampak tam je veliko redundance tukaj.

945
00:44:26,342 --> 00:44:27,550
To ni mišljeno, da bo angleščina.

946
00:44:27,550 --> 00:44:28,341
To ni šifrirana.

947
00:44:28,341 --> 00:44:30,540
To je samo neumno sporočilo
z veliko ponavljanja.

948
00:44:30,540 --> 00:44:34,010
Torej, če ste dejansko izločiš vse
Je A, B je, C-ih, D's, in E je, tu je

949
00:44:34,010 --> 00:44:34,890
frekvenca.

950
00:44:34,890 --> 00:44:37,800
20% črk
Je, 45% črk

951
00:44:37,800 --> 00:44:39,660
so E-jev, in tri druge frekvence.

952
00:44:39,660 --> 00:44:41,960
Smo prešteti tam ročno
in samo naredil matematike.

953
00:44:41,960 --> 00:44:44,579
>> Tako se izkaže, da
Huffman, nekaj časa nazaj,

954
00:44:44,579 --> 00:44:46,620
spoznal, da veste
kaj, če začnem stavbo

955
00:44:46,620 --> 00:44:51,172
drevo ali gozd dreves, če hočete,
takole, jaz lahko storite naslednje.

956
00:44:51,172 --> 00:44:53,880
Bom dal vozlišče za vsako
pisem, ki mi je mar

957
00:44:53,880 --> 00:44:55,530
in bom za shranjevanje
Notranjost vozlišča

958
00:44:55,530 --> 00:44:58,610
frekvence kot plavajočo vejico
vrednost, ali pa bi ga uporabili N, preveč,

959
00:44:58,610 --> 00:45:00,210
vendar bomo šele raba plovec tukaj.

960
00:45:00,210 --> 00:45:03,100
In algoritem, ki
je predlagal je, da si

961
00:45:03,100 --> 00:45:07,210
to gozd samega vozlišča
drevesa, tako super kratke drevesa,

962
00:45:07,210 --> 00:45:11,920
in začnete jih povezujejo s
nove skupine, nove starše, če hočete.

963
00:45:11,920 --> 00:45:16,150
In to storite z izbiro
dve najmanjši frekvenci hkrati.

964
00:45:16,150 --> 00:45:18,110
Zato sem vzel 10% in 10%.

965
00:45:18,110 --> 00:45:19,090
Sem ustvariti novo vozlišče.

966
00:45:19,090 --> 00:45:20,910
In kličem novo vozlišče 20%.

967
00:45:20,910 --> 00:45:22,750
>> Kateri dve vozlišči kombiniram zraven?

968
00:45:22,750 --> 00:45:23,810
To je malo dvoumno.

969
00:45:23,810 --> 00:45:26,643
Torej je nekaj kotiček primerov na
menijo, ampak da se stvari precej,

970
00:45:26,643 --> 00:45:29,300
Grem, da izberejo 20% -
Zdaj prezreti otroke.

971
00:45:29,300 --> 00:45:33,640
Grem, da izberejo 20% in
15% in sestaviti dva nova robove.

972
00:45:33,640 --> 00:45:35,624
In sedaj katera dva vozlišča
jaz logično združiti?

973
00:45:35,624 --> 00:45:38,540
Ignoriraj vse otroke, vsa
vnuki, samo poglej na koreninah

974
00:45:38,540 --> 00:45:39,070
zdaj.

975
00:45:39,070 --> 00:45:42,220
Kateri dve vozlišči moram kravato skupaj?

976
00:45:42,220 --> 00:45:44,530
Točka dva in 0,35.

977
00:45:44,530 --> 00:45:45,890
Torej mi pripravi dva nova robove.

978
00:45:45,890 --> 00:45:47,570
In potem imam samo eno levo.

979
00:45:47,570 --> 00:45:48,650
Torej, tukaj je drevo.

980
00:45:48,650 --> 00:45:51,160
In to je bil sestavljen namerno
pogledati nekako lepo,

981
00:45:51,160 --> 00:45:55,870
vendar opazili, da imajo robovi
Prav tako je bilo označeno nič in ena.

982
00:45:55,870 --> 00:45:59,510
Torej vse levimi robovi so nič
samovoljno, ampak dosledno.

983
00:45:59,510 --> 00:46:01,170
Vse desni robovi so tisti.

984
00:46:01,170 --> 00:46:05,070
>> In kaj Hoffman je predlagana,
če želite, da predstavljajo B,

985
00:46:05,070 --> 00:46:10,080
namesto predstavljajo število 66 kot
ASCII, ki je osem celotno bitov,

986
00:46:10,080 --> 00:46:13,360
Veš kaj, samo trgovina
vzorec nič, nič, nič,

987
00:46:13,360 --> 00:46:17,030
nič, ker je to pot
iz mojega drevesa, gospoda Huffman je drevo,

988
00:46:17,030 --> 00:46:18,600
na krilo od korena.

989
00:46:18,600 --> 00:46:20,970
Če želite shraniti
E, nasprotno, ne

990
00:46:20,970 --> 00:46:26,290
poslati osem bitov, ki predstavljajo E.
Namesto, pošljete kakšen vzorec bitov?

991
00:46:26,290 --> 00:46:26,890
Ena.

992
00:46:26,890 --> 00:46:30,410
In tisto, kar je lepo, o tem je
da E je najbolj priljubljena pismo,

993
00:46:30,410 --> 00:46:32,340
in ste z uporabo
Najkrajša koda za njo.

994
00:46:32,340 --> 00:46:34,090
Naslednja najbolj priljubljen
Pismo je videti, kot da

995
00:46:34,090 --> 00:46:37,380
je A. In tako, koliko bitov
pa je predlagala uporabo za to?

996
00:46:37,380 --> 00:46:38,270
Nič, ena.

997
00:46:38,270 --> 00:46:41,060
>> In zato, ker je izvajala
kot je to drevo, za zdaj

998
00:46:41,060 --> 00:46:43,350
Naj določi, da je
nejasnosti kot v Morse

999
00:46:43,350 --> 00:46:46,090
Koda, ker vse
črke, ki jih skrbijo

1000
00:46:46,090 --> 00:46:48,780
so na koncu teh robov.

1001
00:46:48,780 --> 00:46:50,580
Torej, to je samo ena
Uporaba drevesa.

1002
00:46:50,580 --> 00:46:52,538
To is-- in bom val
moja roka na to, kako vas

1003
00:46:52,538 --> 00:46:55,570
to lahko izvede kot struktura C.

1004
00:46:55,570 --> 00:46:58,260
Vedeti pa je treba združiti
simbol, kot char,

1005
00:46:58,260 --> 00:46:59,910
in frekvenca v levo in desno.

1006
00:46:59,910 --> 00:47:02,510
Toda poglejmo na dveh
Končni primeri, da boste

1007
00:47:02,510 --> 00:47:06,070
dobili precej seznanjeni s po
kviz nič na problem nastaviti pet.

1008
00:47:06,070 --> 00:47:09,210
>> Tako da je struktura podatkov
znan kot hash tabele.

1009
00:47:09,210 --> 00:47:12,247
In hash tabela je nekako
ohladi s tem, da ima žlice.

1010
00:47:12,247 --> 00:47:14,830
In Recimo, da je štiri žlice
tu, le štiri presledke.

1011
00:47:14,830 --> 00:47:20,830
Tukaj je kart, in tu se
klub, lopato, klub, diamanti, klub,

1012
00:47:20,830 --> 00:47:25,960
diamanti, klub, diamanti,
clubs-- tako da je to naključno.

1013
00:47:25,960 --> 00:47:30,330
Hearts, hearts-- tako da sem
bucketizing vse vhode tukaj.

1014
00:47:30,330 --> 00:47:32,430
In hash table potrebe
pogled na vaš prispevek,

1015
00:47:32,430 --> 00:47:34,850
in ga nato dal v neka
postavite na osnovi tega, kar vidite.

1016
00:47:34,850 --> 00:47:35,600
To je algoritem.

1017
00:47:35,600 --> 00:47:37,980
In sem bil z uporabo super
enostavna vizualna algoritem.

1018
00:47:37,980 --> 00:47:40,030
Najtežji del je bil
spomnimo, kaj so bile slike.

1019
00:47:40,030 --> 00:47:41,590
In potem je tu še štiri skupne stvari.

1020
00:47:41,590 --> 00:47:45,440
>> Zdaj nizov so bile narašča, kar
je premišljena zasnova stvar tukaj.

1021
00:47:45,440 --> 00:47:46,540
Ampak, kaj še lahko storim?

1022
00:47:46,540 --> 00:47:49,080
Torej, dejansko tukaj imamo
kup starih šola izpit knjig.

1023
00:47:49,080 --> 00:47:51,240
Denimo, da je kup
Imena študentov so tukaj.

1024
00:47:51,240 --> 00:47:52,570
Tukaj je večji hash tabele.

1025
00:47:52,570 --> 00:47:54,867
Namesto štiri segmente,
Sem, recimo, 26.

1026
00:47:54,867 --> 00:47:57,950
In nismo želeli iti izposoditi 26
Stvari od zunaj [? Annenberg?], Zato

1027
00:47:57,950 --> 00:48:00,289
tukaj je pet, ki predstavljajo
A do Z. In če sem

1028
00:48:00,289 --> 00:48:03,580
glej študenta, čigar ime se začne z A,
Jaz grem k svoji kviz dal tja.

1029
00:48:03,580 --> 00:48:08,850
Če nekdo začne s C, tam,
A-- dejansko, ni želel, da to storim.

1030
00:48:08,850 --> 00:48:10,060
B gre tukaj.

1031
00:48:10,060 --> 00:48:13,390
Torej imam A in B in C. In
tukaj je še en študent.

1032
00:48:13,390 --> 00:48:16,212
Ampak, če je to hash tabela
izvaja z vrsto,

1033
00:48:16,212 --> 00:48:17,920
Jaz sem nekako zajebali
na tej točki, kajne?

1034
00:48:17,920 --> 00:48:19,510
Sem nekako morali dati to nekje.

1035
00:48:19,510 --> 00:48:24,380
>> Torej en način sem lahko reši to je vse
desno, A je zaseden, B je zaposlen, C je zaseden.

1036
00:48:24,380 --> 00:48:28,880
Bom ga dal v D. Torej na
Najprej sem imela naključno takojšen dostop

1037
00:48:28,880 --> 00:48:31,064
za vsakega od vedra za študente.

1038
00:48:31,064 --> 00:48:33,230
Ampak zdaj je vrsta preneseno
v nekaj linearnega,

1039
00:48:33,230 --> 00:48:36,750
ker če želim iskati nekoga
katerih ime se začne z A, I preverite tukaj.

1040
00:48:36,750 --> 00:48:38,854
Toda, če to ni A
študent Iščem,

1041
00:48:38,854 --> 00:48:41,520
Nekako sem moral začeti preverjanje
Vedra, ker tisto, kar sem storil

1042
00:48:41,520 --> 00:48:44,530
je nekako linearno
sonda podatkovne strukture.

1043
00:48:44,530 --> 00:48:47,710
Neumen način rekel samo poglej
za prvo razpoložljivo odprtino,

1044
00:48:47,710 --> 00:48:51,850
in dal kot Plan B, tako rekoč,
ali plan D, v tem primeru vrednost

1045
00:48:51,850 --> 00:48:53,340
na tem mestu namesto.

1046
00:48:53,340 --> 00:48:56,470
To je samo zato, da, če ste
dobil 26 lokacij in študenti

1047
00:48:56,470 --> 00:49:00,600
z imenom Q ali Z, ali kaj podobnega
da, vsaj boste uporabljali prostor.

1048
00:49:00,600 --> 00:49:03,140
>> Ampak smo že videli več
pametne rešitve tukaj, kajne?

1049
00:49:03,140 --> 00:49:04,870
Kaj bi ti naredil namesto
če imate trčenje?

1050
00:49:04,870 --> 00:49:06,670
Če imata dve osebi
ime A, kaj bi

1051
00:49:06,670 --> 00:49:09,160
so bili pametnejši ali bolj
intuitivno rešitev, kot le

1052
00:49:09,160 --> 00:49:12,840
Prenos kjer je D naj bi bila?

1053
00:49:12,840 --> 00:49:14,810
Zakaj ne samo pojdi
izven [? Annenberg?]

1054
00:49:14,810 --> 00:49:19,960
kot knjižnične funkcije malloc, drugo vozlišče, ga
tukaj, in potem dal, da študent tukaj.

1055
00:49:19,960 --> 00:49:22,120
Tako, da sem v bistvu še
nekakšen array,

1056
00:49:22,120 --> 00:49:25,590
ali morda še bolj elegantno, kot smo
začenja videti povezani seznam.

1057
00:49:25,590 --> 00:49:29,520
>> In zato je hash tabela je struktura
da bi lahko videti kot to,

1058
00:49:29,520 --> 00:49:33,900
ampak bolj spretno, si nekaj, kar se imenuje
ločen veriženje, s katerim hash tabela

1059
00:49:33,900 --> 00:49:38,340
preprosto je matrika, vsaka
katere elementi ni številka,

1060
00:49:38,340 --> 00:49:40,470
je sama povezani seznam.

1061
00:49:40,470 --> 00:49:45,080
Torej, da dobiš super hitri dostop
odločanju, kje izbrskali svojo vrednost.

1062
00:49:45,080 --> 00:49:48,059
Podobno kot s primerom kartice,
Naredil sem super hitre odločitve.

1063
00:49:48,059 --> 00:49:49,600
Hearts gre tukaj, diamanti gre tukaj.

1064
00:49:49,600 --> 00:49:52,180
Enako tukaj, A gre tu,
D gre tukaj, B gre tukaj.

1065
00:49:52,180 --> 00:49:55,740
Torej super hitro look-ups, in če
se zgodi, da delujejo v primeru

1066
00:49:55,740 --> 00:49:59,429
kjer imaš trkov, dve
ljudje z istim imenom, in nato

1067
00:49:59,429 --> 00:50:00,970
ste šele začeli ju povezuje.

1068
00:50:00,970 --> 00:50:03,900
In morda boste obdržali jih razporejene
po abecednem redu, morda ne.

1069
00:50:03,900 --> 00:50:05,900
Ampak zdaj vsaj imamo dinamičnost.

1070
00:50:05,900 --> 00:50:10,250
Torej na eni strani imamo zelo hitro
stalen čas in vrsta linearnem času

1071
00:50:10,250 --> 00:50:14,110
vključeni, če teh povezanih seznamov
začetek, da bi dobili malo dolgo.

1072
00:50:14,110 --> 00:50:16,880
>> Tako da je ta vrsta neumno,
pred geeky potegavščine let.

1073
00:50:16,880 --> 00:50:19,590
Na CS50 hack-a-thon,
ko so študenti prijavijo,

1074
00:50:19,590 --> 00:50:22,040
nekateri TF ali CA vsako leto
misli, da je smešno, da dajo

1075
00:50:22,040 --> 00:50:27,772
znak, kot je ta, če je le
pomeni, da če vaše ime se začne z A,

1076
00:50:27,772 --> 00:50:28,870
gredo v to smer.

1077
00:50:28,870 --> 00:50:31,110
Če je vaše ime se začne
z B, pojdite this-- OK,

1078
00:50:31,110 --> 00:50:33,290
to je smešno, morda kasneje v semestru.

1079
00:50:33,290 --> 00:50:36,420
Toda obstaja še ena
načinov za to, preveč.

1080
00:50:36,420 --> 00:50:37,410
Vrnite se k temu.

1081
00:50:37,410 --> 00:50:38,600
>> Torej je ta struktura.

1082
00:50:38,600 --> 00:50:40,420
In to je naša zadnja
struktura za danes,

1083
00:50:40,420 --> 00:50:42,400
ki je nekaj, kar se imenuje trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, ki je iz neznanega razloga je kratka
za iskanje, vendar je pozval trie.

1085
00:50:47,140 --> 00:50:51,389
Torej trie je še ena zanimiva
amalgam veliko teh idej.

1086
00:50:51,389 --> 00:50:52,930
To je drevo, ki smo ga videli prej.

1087
00:50:52,930 --> 00:50:54,180
To ni binarno iskalno drevo.

1088
00:50:54,180 --> 00:50:58,410
To je drevo s poljubnim številom otrok,
ampak vsak otrok v Trie

1089
00:50:58,410 --> 00:51:00,090
je niz.

1090
00:51:00,090 --> 00:51:04,790
Niz velikosti, recimo, 26 ali morda 27
Če želite podpreti sklopljenih imena

1091
00:51:04,790 --> 00:51:06,790
ali opuščaj v imenih ljudi.

1092
00:51:06,790 --> 00:51:08,280
>> In tako je to struktura podatkov.

1093
00:51:08,280 --> 00:51:10,290
In če pogledaš od zgoraj
do dna, kot če vas

1094
00:51:10,290 --> 00:51:13,710
poglej zgornjem vozlišču tam, M, je
kaže na skrajni levi stvar tam,

1095
00:51:13,710 --> 00:51:17,665
ki ga nato A, X, W, E, L, L. Gre
le struktura podatkov, ki samovoljno

1096
00:51:17,665 --> 00:51:19,120
je shranjevanje imen ljudi.

1097
00:51:19,120 --> 00:51:25,720
In Maxwell shranijo samo po
pot od polja do polja do polja.

1098
00:51:25,720 --> 00:51:30,050
Toda kaj je neverjetno približno trie je
da, ker je povezana seznama in še

1099
00:51:30,050 --> 00:51:34,520
matrika, najbolje kar smo jih kdaj gotten je
linearni čas ali logaritemsko čas iščejo

1100
00:51:34,520 --> 00:51:35,600
nekdo gor.

1101
00:51:35,600 --> 00:51:40,530
V tej strukturi podatkov za trie, če
moj podatkovna struktura ima eno ime v njej

1102
00:51:40,530 --> 00:51:43,720
in iščem Maxwell, sem
dogaja, da ga precej hitro našli.

1103
00:51:43,720 --> 00:51:47,910
Pravkar sem si za M-A-X-W-E-L-L. Če
ta struktura podatkov, nasprotno,

1104
00:51:47,910 --> 00:51:51,830
če N je milijon, če obstaja
milijon imen v tej strukturi podatkov,

1105
00:51:51,830 --> 00:51:57,100
Maxwell je še vedno dogaja, da se
odkriti po samo M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
koraki.

1107
00:51:58,090 --> 00:52:01,276
In koraki David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
Z drugimi besedami, z oblikovanjem
podatkovna struktura, ki je

1109
00:52:03,400 --> 00:52:07,240
nimajo od katerih so vsi ti nizi, vse
sami podpirajo naključni dostop,

1110
00:52:07,240 --> 00:52:11,090
Lahko začnete iskati up ljudske
ime uporabljate količino časa, ki je

1111
00:52:11,090 --> 00:52:14,340
sorazmerna ne številom
stvari v strukturi podatkov,

1112
00:52:14,340 --> 00:52:16,330
kot milijon obstoječa imena.

1113
00:52:16,330 --> 00:52:20,135
Količina časa, da me popelje najti
M-A-X-W-E-L-L v tej strukturi podatkov je

1114
00:52:20,135 --> 00:52:22,260
sorazmerna ne do
velikost strukture podatkov,

1115
00:52:22,260 --> 00:52:25,930
vendar dolžini imenom.

1116
00:52:25,930 --> 00:52:28,440
In stvarno
Imena iščemo up

1117
00:52:28,440 --> 00:52:29,970
se nikoli ne bo noro dolgo.

1118
00:52:29,970 --> 00:52:32,600
Mogoče kdo ima 10 značaja
ime, 20 ime znakov.

1119
00:52:32,600 --> 00:52:33,900
To je gotovo omejen, kajne?

1120
00:52:33,900 --> 00:52:37,110
Tam je človek na Zemlji, ki
ima najdaljšo možno ime,

1121
00:52:37,110 --> 00:52:39,920
ampak to ime je konstanta
Dolžina vrednost, kajne?

1122
00:52:39,920 --> 00:52:41,980
To ne spreminja v nobenem smislu.

1123
00:52:41,980 --> 00:52:45,090
Torej, na ta način, ki smo jih
doseženi podatkovne strukture

1124
00:52:45,090 --> 00:52:47,800
da je stalen čas look-up.

1125
00:52:47,800 --> 00:52:50,670
To ne bo več korakov
odvisno od dolžine vnosa,

1126
00:52:50,670 --> 00:52:54,250
vendar ne število imenom
v podatkovno strukturo.

1127
00:52:54,250 --> 00:52:58,700
Torej, če bomo podvojili število imen
Naslednje leto od milijarde do dveh milijard evrov,

1128
00:52:58,700 --> 00:53:03,720
Ugotovitev Maxwell se dogaja, da sprejmejo
natančno enako število sedmih korakih

1129
00:53:03,720 --> 00:53:04,650
da bi ga našli.

1130
00:53:04,650 --> 00:53:08,810
In tako se zdi, da smo dosegli
naš sveti gral čas teče.

1131
00:53:08,810 --> 00:53:10,860
>> Torej Nekaj ​​hitrih objav.

1132
00:53:10,860 --> 00:53:11,850
Kviz nič prihaja.

1133
00:53:11,850 --> 00:53:14,600
Več o tem na spletni strani predmeta je
v naslednjih nekaj dneh.

1134
00:53:14,600 --> 00:53:17,120
Ponedeljek je lecture-- To je praznik
tukaj na Harvardu v ponedeljek.

1135
00:53:17,120 --> 00:53:18,850
To ni v New Haven,
tako da smo vzeli razred

1136
00:53:18,850 --> 00:53:20,310
New Haven za predavanje v ponedeljek.

1137
00:53:20,310 --> 00:53:22,550
Vse bo posnet
in predvajale v živo, kot ponavadi,

1138
00:53:22,550 --> 00:53:24,900
ampak kaj je na koncu danes
z drugo sponko 30

1139
00:53:24,900 --> 00:53:26,910
imenovane "Deep Thoughts"
ga Daven Farnham, ki je

1140
00:53:26,910 --> 00:53:30,850
je navdihnila lani do sobote
Night Live je "Deep Thoughts"

1141
00:53:30,850 --> 00:53:35,700
Jack Handy, ki
bi se morali zdaj smisla.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: In zdaj, "Deep
Misli "po Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tabela.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: V redu, to je to za zdaj.

1147
00:53:47,660 --> 00:53:48,805
Se vidimo naslednji teden.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> Doug: Da bi ga videli v akciji.

1150
00:53:56,680 --> 00:53:58,304
Torej, kaj je si oglejte, da je prav zdaj.

1151
00:53:58,304 --> 00:53:59,890
Torej, tukaj imamo neurejen paleto.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, lahko greš naprej in ponovni zagon
to za eno samo sekundo, prosim.

1153
00:54:04,860 --> 00:54:08,562
Vredu, kamere so valjanje, tako
Akcijski ko boste pripravljeni, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
Doug: V redu, tako da tisto, kar smo
imamo tukaj je razvrščen niz.

1155
00:54:11,020 --> 00:54:13,960
In sem obarvani vse elemente
rdeče, kar pomeni, da je v resnici

1156
00:54:13,960 --> 00:54:14,460
razvrščeni.

1157
00:54:14,460 --> 00:54:17,960
Tako opozarjajo, da je prva stvar, ki jo storite
je levi polovici matrike smo razvrstiti.

1158
00:54:17,960 --> 00:54:20,630
Potem smo razvrstiti pravico
polovica matriki.

1159
00:54:20,630 --> 00:54:22,830
In ya-da, ya-da, ya-da,
smo jih združiti skupaj.

1160
00:54:22,830 --> 00:54:24,520
In imamo popolnoma urejen niz.

1161
00:54:24,520 --> 00:54:25,360
Torej, to je, kako združiti nekako deluje.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Vau, vau, vau,
cut, cut, cut, cut.

1163
00:54:27,109 --> 00:54:30,130
Doug, ne moreš samo ya-da, ya-da,
ya-da, svojo pot skozi zlivanjem.

1164
00:54:30,130 --> 00:54:31,970
>> Doug: sem pravkar storil.

1165
00:54:31,970 --> 00:54:32,832
V redu je.

1166
00:54:32,832 --> 00:54:33,540
Mi smo na dobri poti.

1167
00:54:33,540 --> 00:54:34,760
Recimo samo, da valjanje.

1168
00:54:34,760 --> 00:54:35,380
Tako nekako,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Moraš razložiti
bolj polno, kot da.

1170
00:54:37,800 --> 00:54:39,999
To preprosto ni dovolj.

1171
00:54:39,999 --> 00:54:41,790
Doug: Ian, ne bomo
morali iti nazaj v enem.

1172
00:54:41,790 --> 00:54:42,350
V redu je.

1173
00:54:42,350 --> 00:54:45,690
Torej nekako, če bomo nadaljevali s merge--
Ian, smo sredi snemanja.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Vem.

1175
00:54:46,612 --> 00:54:49,320
In ne moremo samo ya-da, ya-da,
ya-da, skozi celoten proces.

1176
00:54:49,320 --> 00:54:52,200
Moraš pojasniti, kako je
Obe strani sta se združili skupaj.

1177
00:54:52,200 --> 00:54:53,570
>> Doug: Ampak smo že
pojasnil, kako sta sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Pravkar ste prikazani
jim omogoča spajanje nizov.

1179
00:54:55,321 --> 00:54:56,486
Doug: Poznajo postopek.

1180
00:54:56,486 --> 00:54:57,172
Oni so v redu.

1181
00:54:57,172 --> 00:54:58,380
Šli smo nad njim desetkrat.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Pravkar si preskočila prav nad njim.

1183
00:55:00,330 --> 00:55:03,360
Gremo nazaj v eno,
Ne morem vam ya-da, ya-da nad njim.

1184
00:55:03,360 --> 00:55:05,480
V redu, nazaj v enem.

1185
00:55:05,480 --> 00:55:07,833
>> Doug: Moram iti nazaj
skozi vse diapozitivov?

1186
00:55:07,833 --> 00:55:08,332
Moj Bog.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
To je, kot že šestič, Ian.

1189
00:55:13,004 --> 00:55:13,940
V redu je.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: V redu.

1191
00:55:15,200 --> 00:55:16,590
Ste pripravljeni?

1192
00:55:16,590 --> 00:55:17,400
Great.

1193
00:55:17,400 --> 00:55:18,950
Ukrepanje.