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

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Olgu, nii et see on
CS50 See on nädala lõpuks viis.

3
00:00:15,860 --> 00:00:19,220
Ja meenutada, et viimane kord
Hakkasin uurima Kasvataja andmeid

4
00:00:19,220 --> 00:00:22,310
struktuurid, mis algas lahendada
probleeme, mis algas tutvustada

5
00:00:22,310 --> 00:00:25,640
uusi probleeme, kuid võti selles
oli omamoodi väliskeermestamiseks, et me

6
00:00:25,640 --> 00:00:27,940
hakkas tegema sõlmest sõlmeni.

7
00:00:27,940 --> 00:00:30,085
Nii see muidugi on
ühekaupa seotud nimekirja.

8
00:00:30,085 --> 00:00:31,960
Ja üksi seotud,
Ma mõtlen seal on vaid üks

9
00:00:31,960 --> 00:00:33,380
niit omavahel nende sõlmede.

10
00:00:33,380 --> 00:00:35,890
Selgub, mida saate teha Kasvataja
asjad kahekordselt ahelloendid

11
00:00:35,890 --> 00:00:38,470
kusjuures sul on nool
läheb mõlemas suunas, mis

12
00:00:38,470 --> 00:00:40,320
aitab teatud kasutegurit.

13
00:00:40,320 --> 00:00:42,000
Aga see lahendas probleemi?

14
00:00:42,000 --> 00:00:43,500
Mis probleem ei seda lahendada?

15
00:00:43,500 --> 00:00:46,620
Miks me hoolime esmaspäeval?

16
00:00:46,620 --> 00:00:49,820
Miks teoreetiliselt ei me hoolime esmaspäeval?

17
00:00:49,820 --> 00:00:50,630
Mida ta teeb?

18
00:00:50,630 --> 00:00:51,950
>> Sihtrühm: Me ei dünaamiliselt suurust muuta.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, et saaksime
dünaamiliselt suurust muuta.

20
00:00:53,740 --> 00:00:54,710
Hästi tehtud teile mõlemale.

21
00:00:54,710 --> 00:00:57,560
Nii saab dünaamiliselt suurust selle
andmestruktuur, kusjuures massiivi,

22
00:00:57,560 --> 00:01:00,760
Meenuta, mida sa pead teada
priori, kui palju ruumi soovite

23
00:01:00,760 --> 00:01:03,870
ja kui teil on vaja natuke rohkem
ruumi, et sa oled selline õnne.

24
00:01:03,870 --> 00:01:05,560
Sul on luua täiesti uue massiivi.

25
00:01:05,560 --> 00:01:07,893
Sa pead liikuma kogu oma
andmeid ühest teise,

26
00:01:07,893 --> 00:01:10,600
lõpuks vabastama vana massiivi
kui saad, ja siis edasi.

27
00:01:10,600 --> 00:01:13,891
Mis lihtsalt tundub väga kulukas ja väga
ebaefektiivne ja isegi see võib olla.

28
00:01:13,891 --> 00:01:14,890
Aga see pole veel kõik hea.

29
00:01:14,890 --> 00:01:18,180
Pöörame hind, mis oli üks
ilmsem hindadega me

30
00:01:18,180 --> 00:01:20,550
maksma abil ahelloend?

31
00:01:20,550 --> 00:01:22,825
>> Sihtrühm: peame kasutama
topelt ruumi igaüks.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Jah, nii et me peame
vähemalt kaks korda sama palju ruumi.

33
00:01:25,200 --> 00:01:27,700
Tegelikult ma mõistsin seda pilti oma
isegi natuke eksitav,

34
00:01:27,700 --> 00:01:32,200
sest kohta CS50 IDE palju kaasaegse
arvutid, osuti või aadress

35
00:01:32,200 --> 00:01:33,700
ei ole tegelikult neli baiti.

36
00:01:33,700 --> 00:01:36,090
See on väga sageli need
päeva kaheksa baiti, mis

37
00:01:36,090 --> 00:01:38,530
tähendab põhja kõige
ristkülikud on tegelikult

38
00:01:38,530 --> 00:01:40,900
on mingi kaks korda
suur kui see, mida ma olen juhtinud,

39
00:01:40,900 --> 00:01:44,409
mis tähendab, te kasutate kolm korda
palju ruumi kui meil oleks teisiti.

40
00:01:44,409 --> 00:01:46,700
Nüüd samal ajal, et me oleme
veel räägi baiti, eks?

41
00:01:46,700 --> 00:01:49,140
Me ei pruugi rääkides
megabaiti või gigabaiti,

42
00:01:49,140 --> 00:01:51,000
kui need andmestruktuurid saada suur.

43
00:01:51,000 --> 00:01:54,510
>> Ja nii täna hakkame kaaluma
kuidas me võiksime uurida andmeid

44
00:01:54,510 --> 00:01:57,310
efektiivsemalt kui ka
Tegelikult andmeid muutub suuremaks.

45
00:01:57,310 --> 00:02:00,360
Aga proovime õgvenda
tegevuse esimene

46
00:02:00,360 --> 00:02:02,460
mida saate teha nende
liiki andmestruktuuride.

47
00:02:02,460 --> 00:02:04,790
Nii midagi seotud
nimekirja toetab üldiselt

48
00:02:04,790 --> 00:02:07,514
operatsioonide meeldi kustutada,
sisestada ning otsida.

49
00:02:07,514 --> 00:02:08,639
Ja mida ma mõtlen, et?

50
00:02:08,639 --> 00:02:11,222
See tähendab lihtsalt, et tavaliselt,
Kui inimesed kasutavad seotud nimekirja,

51
00:02:11,222 --> 00:02:14,287
nemad või keegi teine ​​on rakendanud
funktsioone nagu delete, lisada,

52
00:02:14,287 --> 00:02:16,120
ja otsida, siis võite
tegelikult midagi

53
00:02:16,120 --> 00:02:18,030
kasulikeks andmestruktuur.

54
00:02:18,030 --> 00:02:20,760
Võtame pilgu
kuidas me võiksime rakendada

55
00:02:20,760 --> 00:02:24,530
Mõnes kood ahelloend järgmiselt.

56
00:02:24,530 --> 00:02:27,885
>> Nii et see on vaid mõned C-kood,
isegi mitte täielik programm

57
00:02:27,885 --> 00:02:29,260
et ma tõesti kiiresti vahustatud.

58
00:02:29,260 --> 00:02:32,300
See ei ole internetis levitamise
koodi, sest see ei reaalselt sõita.

59
00:02:32,300 --> 00:02:33,790
Aga teate ma olen lihtsalt
koos Kommentaari ütles,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, et siin on midagi
seal dot dot dot, midagi seal.

61
00:02:36,130 --> 00:02:38,410
Ja olgem lihtsalt vaadata
mida mahlane osad.

62
00:02:38,410 --> 00:02:40,790
Nii on line kolm,
Tuletame meelde, et see on nüüd

63
00:02:40,790 --> 00:02:45,960
Me pakkusime kuulutab sõlme viimase
aega, üks neist ristkülikukujulise objektid.

64
00:02:45,960 --> 00:02:48,790
See on int, et me kutsume N,
kuid me võime seda kutsuda midagi,

65
00:02:48,790 --> 00:02:51,920
ja siis struct node star nimetas tuleva.

66
00:02:51,920 --> 00:02:55,520
Ja just olema selge, et teine
line, line kuus, mis see on?

67
00:02:55,520 --> 00:02:57,930
Mis on see meie heaks teeb?

68
00:02:57,930 --> 00:03:01,044
Sest see kindlasti tundub rohkem
segasena kui meie tavaline muutujaid.

69
00:03:01,044 --> 00:03:02,740
>> Sihtrühm: See muudab liikuda üle.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: See muudab liikuda üle.

71
00:03:04,650 --> 00:03:08,580
Ja täpsemalt,
see salvestab aadress

72
00:03:08,580 --> 00:03:11,582
sõlme, mis on mõeldud
semantiliselt kõrval, eks?

73
00:03:11,582 --> 00:03:13,540
Nii see ei lähe
pruugi liikuda midagi.

74
00:03:13,540 --> 00:03:15,290
See lihtsalt läheb
talletada väärtust, mis on

75
00:03:15,290 --> 00:03:17,170
saab olema aadress
Mõnede muude sõlme,

76
00:03:17,170 --> 00:03:20,810
ja sellepärast oleme öelnud struct
sõlme täht, mis tähistab

77
00:03:20,810 --> 00:03:22,370
osuti või aadress.

78
00:03:22,370 --> 00:03:26,390
OK, nii et nüüd, kui sa arvata, et meil on
Selles N meile kättesaadav, ja olgem

79
00:03:26,390 --> 00:03:29,490
eeldada, et keegi teine ​​on
lisada terve hunnik täisarvud

80
00:03:29,490 --> 00:03:30,400
arvesse ahelloend.

81
00:03:30,400 --> 00:03:35,640
Ja mis on seotud nimekiri on
osutas mõnede punkti

82
00:03:35,640 --> 00:03:39,040
muutuja nimega loend, mis on
möödunud aastal siin parameeter,

83
00:03:39,040 --> 00:03:43,120
kuidas ma minna line
14 rakendamisel otsida?

84
00:03:43,120 --> 00:03:45,990
Teisisõnu, kui ma rakendamisel
funktsiooni, mille eesmärk elus

85
00:03:45,990 --> 00:03:48,889
on võtta int ja seejärel
algus ahelloend,

86
00:03:48,889 --> 00:03:50,430
mis on kursor seotud nimekirja.

87
00:03:50,430 --> 00:03:52,992
Nagu esimene, kes ma arvan, et David
oli meie vabatahtlike esmaspäeval,

88
00:03:52,992 --> 00:03:54,700
ta vastakuti
Kogu seotud nimekirja,

89
00:03:54,700 --> 00:03:57,820
see on nagu oleks me möödaminnes
David on meie argument siin.

90
00:03:57,820 --> 00:03:59,990
Kuidas minna liiklevad see nimekiri?

91
00:03:59,990 --> 00:04:04,640
Noh, tuleb välja, et kuigi
viiteid on suhteliselt uus nüüd meile,

92
00:04:04,640 --> 00:04:07,010
Me saame seda teha suhteliselt
arusaadav.

93
00:04:07,010 --> 00:04:09,500
>> Ma lähen edasi minna ja
kuulutada ajutise muutuja

94
00:04:09,500 --> 00:04:12,364
Tavapäraselt on lihtsalt läheb
mida nimetatakse pointer, ja PTR,

95
00:04:12,364 --> 00:04:14,030
aga sa võiksid seda nimetada kõike, mida sa tahad.

96
00:04:14,030 --> 00:04:16,470
Ja ma initsialiseerida
selle algust nimekirja.

97
00:04:16,470 --> 00:04:20,050
Nii saab mingi mõtle sellele
kui mul õpetaja teisel päeval,

98
00:04:20,050 --> 00:04:23,580
Selline osutades keegi
seas meie inimeste vabatahtlikena.

99
00:04:23,580 --> 00:04:26,470
Nii et ma olen ajutise muutuja, mis on
lihtsalt osutades sama asi

100
00:04:26,470 --> 00:04:31,390
et meie juhuslikult nimega
Vabatahtliku David oli ka meenutanud.

101
00:04:31,390 --> 00:04:35,440
Nüüd, kui kursor on
ei ole null, sest meenutavad

102
00:04:35,440 --> 00:04:40,350
et null on mingi eriline kontroll väärtus
piiritleb nimekirja lõppu,

103
00:04:40,350 --> 00:04:44,280
Niisiis, kui ma ei osutades
maa nagu meie viimane vabatahtlike

104
00:04:44,280 --> 00:04:47,190
oli, lähme edasi
ja teha järgmist.

105
00:04:47,190 --> 00:04:51,820
Kui pointer-- ja nüüd ma mingi tahan
teha seda, mida me tegime koos õpilase

106
00:04:51,820 --> 00:04:57,410
structure-- kui osuti dot järgmine
equals-- pigem kui osuti dot N võrdub

107
00:04:57,410 --> 00:05:02,290
võrdub muutuja N, siis
argument, mis on olnud möödunud aastal,

108
00:05:02,290 --> 00:05:05,370
siis ma tahan minna
ja öelda naasta tõsi.

109
00:05:05,370 --> 00:05:11,020
Ma leidsin numbri N sees
sõlm minu ahelloendid.

110
00:05:11,020 --> 00:05:13,500
Aga dot enam
töötab selles kontekstis

111
00:05:13,500 --> 00:05:17,260
sest pointer, PTR, on
tõepoolest pointer, aadressi,

112
00:05:17,260 --> 00:05:20,632
me tegelikult ei imeliselt
kasuta lõpuks tükk süntaks

113
00:05:20,632 --> 00:05:22,590
et ajab
intuitiivset tunnet ja tegelikult

114
00:05:22,590 --> 00:05:27,870
kasuta noolt siin, mis tähendab minna
et aadressi täisarv seal.

115
00:05:27,870 --> 00:05:30,160
Nii et see on väga sarnane
vaimu dot operaator,

116
00:05:30,160 --> 00:05:33,860
kuid kuna osuti ei viida
mitte tegelik struct ise,

117
00:05:33,860 --> 00:05:35,380
me lihtsalt kasutada nooleklahve.

118
00:05:35,380 --> 00:05:40,620
>> Nii et kui praegune sõlme, et mina,
Ajutise muutuja, olen osutades

119
00:05:40,620 --> 00:05:43,060
ei ole N, mida ma tahan teha?

120
00:05:43,060 --> 00:05:45,910
Noh, minu inimvabatahtlikele
et meil oli siin ükspäev,

121
00:05:45,910 --> 00:05:49,710
kui mu esimene inimene ei ole see, mida ma
tahad, ja võib-olla teisel inimesel ei ole

122
00:05:49,710 --> 00:05:52,660
Ühest ma tahan, ja kolmas, ma
on vaja hoida füüsiliselt liigub.

123
00:05:52,660 --> 00:05:54,690
Nagu kuidas ma sammult läbi nimekirja?

124
00:05:54,690 --> 00:05:57,470
Kui meil oli massiivi, siis
just tegin nagu ma pluss pluss.

125
00:05:57,470 --> 00:06:03,660
Aga sel juhul piisab
teha pointer, saab, pointer, kõrval.

126
00:06:03,660 --> 00:06:07,580
Teisisõnu järgmisele väljale
on nagu kõik kas käsi

127
00:06:07,580 --> 00:06:10,880
et meie vabatahtlikel inimestel esmaspäeval
kasutasid punkti teisigi sõlme.

128
00:06:10,880 --> 00:06:12,890
Need olid nende kõrval naabrid.

129
00:06:12,890 --> 00:06:17,060
>> Nii et kui ma tahan astuda läbi selle nimekirja,
Ma ei saa lihtsalt ma pluss pluss enam,

130
00:06:17,060 --> 00:06:20,120
Ma asemel öelda
I, pointer, läheb

131
00:06:20,120 --> 00:06:24,650
võrdse iganes järgmise valdkonnas on,
Järgmise väli, järgmisel valdkonnas on,

132
00:06:24,650 --> 00:06:28,350
järgmiste kõik need jäänud käed
et meil oli laval juhtides

133
00:06:28,350 --> 00:06:30,000
mõningal järgnevate väärtustega.

134
00:06:30,000 --> 00:06:32,590
Ja kui ma saan läbi
et kogu korduse

135
00:06:32,590 --> 00:06:39,330
ja lõpuks, ma tabanud null, millel ei ole
leitud N veel, ma lihtsalt tagasi vale.

136
00:06:39,330 --> 00:06:44,100
Nii jälle, kõik, mis me teeme siin,
ühe pildi hetk tagasi,

137
00:06:44,100 --> 00:06:47,840
hakkab juhtides juures
loendi alguses arvatavasti.

138
00:06:47,840 --> 00:06:50,970
Ja siis ma kontrollin, on väärtus
Otsin võrdne üheksa?

139
00:06:50,970 --> 00:06:52,650
Kui jah, siis ma tagasi tõsi ja ma olen teinud.

140
00:06:52,650 --> 00:06:56,450
Kui ei, ma uuendada oma käsi,
AKA pointer, juhtida

141
00:06:56,450 --> 00:06:59,540
järgmisel noole asukoht ja
siis järgmisel noole asukoht,

142
00:06:59,540 --> 00:07:00,480
ja järgmine.

143
00:07:00,480 --> 00:07:03,770
Ma lihtsalt jalgsi läbi selle massiivi.

144
00:07:03,770 --> 00:07:06,010
>> Nii jälle, kes hoolib?

145
00:07:06,010 --> 00:07:07,861
Nagu mida see koostisosana?

146
00:07:07,861 --> 00:07:10,360
Noh, meelde tuletada, et oleme kasutusele
mõiste virna, mis

147
00:07:10,360 --> 00:07:15,400
on abstraktne andmetüüp, kuivõrd see on
ei ole C asi, see ei ole CS50 asi,

148
00:07:15,400 --> 00:07:19,430
see on abstraktne idee, idee
virnastamine asju üksteise peale

149
00:07:19,430 --> 00:07:21,820
mida saab rakendada
kobarad erinevalt.

150
00:07:21,820 --> 00:07:25,600
Ja üks viis, kuidas me kavandatud oli
massiivi või koos seotud nimekirja.

151
00:07:25,600 --> 00:07:29,570
Ja selgub, et kanooniliselt, et
stack toetab vähemalt kaks operatsiooni.

152
00:07:29,570 --> 00:07:32,320
Ja buzz sõnad on push, kuni
lükake midagi peale virna,

153
00:07:32,320 --> 00:07:34,770
nagu uus salv
söögisaal, või pop,

154
00:07:34,770 --> 00:07:39,000
mis tähendab, et eemaldada tähtsaim
salve korstna söögituba

155
00:07:39,000 --> 00:07:41,500
hall, ja siis võib-olla mõned
muud toimingud samuti.

156
00:07:41,500 --> 00:07:45,770
Niisiis, kuidas võiks me defineerime struktuur
et me nüüd helistades virna?

157
00:07:45,770 --> 00:07:50,020
>> Noh, meil on kõik vajalikud
süntaks meie käsutuses olevaid C. ütlen,

158
00:07:50,020 --> 00:07:53,830
mulle tüübi määratlus
struct sees korstna

159
00:07:53,830 --> 00:07:58,030
Ma ütlen on massiiv, mille
terve hunnik numbreid ja seejärel suurust.

160
00:07:58,030 --> 00:08:00,930
Nii teisisõnu, kui ma tahan
rakendada seda koodi,

161
00:08:00,930 --> 00:08:03,830
lase mul minna ja lihtsalt selline
joonistada, mida see ütleb.

162
00:08:03,830 --> 00:08:06,317
Nii et see ütleb mulle
struktuur, mis sai hulgaliselt,

163
00:08:06,317 --> 00:08:09,400
ja ma ei tea, millises ulatuses on
see on ilmselt mingi konstant, et ma olen

164
00:08:09,400 --> 00:08:10,858
mis on mujal, ja see on hea.

165
00:08:10,858 --> 00:08:15,260
Aga arvan, et see on lihtsalt üks,
kaks, kolm, neli, viis.

166
00:08:15,260 --> 00:08:16,700
Nii võimsus on 5.

167
00:08:16,700 --> 00:08:21,730
See element sees minu
struktuuri nimetatakse numbrid.

168
00:08:21,730 --> 00:08:24,020
Ja siis ma pean ühe
muud muutuva ilmselt

169
00:08:24,020 --> 00:08:27,814
nimetatakse suurust, mis esialgu ma lähen
sätestada käivitub nulli.

170
00:08:27,814 --> 00:08:29,730
Kui seal on midagi
virna, suurus on null,

171
00:08:29,730 --> 00:08:31,420
ja see on prügi väärtused numbrid.

172
00:08:31,420 --> 00:08:33,450
Ma ei tea, mis on seal veel.

173
00:08:33,450 --> 00:08:36,059
>> Nii et kui ma tahan, et lükata
midagi peale virna,

174
00:08:36,059 --> 00:08:40,780
arvan, et ma kutsun funktsiooni push, ja
Ma ütlen suruda 50, nagu number 50,

175
00:08:40,780 --> 00:08:44,090
kus soovitaksite
Ma joonistan selle selle massiivi?

176
00:08:44,090 --> 00:08:47,124
Seal on viis erinevat vastusevarianti.

177
00:08:47,124 --> 00:08:48,790
Kuhu ma suruda number 50?

178
00:08:48,790 --> 00:08:51,899
Kui eesmärk siin jälle helistada
funktsiooni push, liigu argument

179
00:08:51,899 --> 00:08:52,940
50, kus ma pane see?

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

181
00:08:55,680 --> 00:08:59,052
Viis possible-- 20% võimalus
aim õigesti.

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

183
00:08:59,896 --> 00:09:00,740
>> Sihtrühm: paremas servas.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: paremas servas.

185
00:09:01,990 --> 00:09:08,359
Nüüdseks on 25% võimalus
aim õigesti.

186
00:09:08,359 --> 00:09:09,650
Nii et tegelikult on kõik korras.

187
00:09:09,650 --> 00:09:12,770
Kokkuleppeliselt ma ütlen array,
me tavaliselt algavad vasakul,

188
00:09:12,770 --> 00:09:14,519
aga me võiksime kindlasti
alustama õigelt.

189
00:09:14,519 --> 00:09:17,478
Nii spoiler oleks siin ma olen
ilmselt läheb joonistada vasakul,

190
00:09:17,478 --> 00:09:20,060
justnagu tavaline massiiv, kus
Ma alguses läheb vasakult paremale.

191
00:09:20,060 --> 00:09:21,780
Aga kui sa ei flip
aritmeetiline, fine.

192
00:09:21,780 --> 00:09:23,060
See lihtsalt ei ole tavalised.

193
00:09:23,060 --> 00:09:24,880
OK, mul on vaja teha üks
rohkem muutus küll.

194
00:09:24,880 --> 00:09:27,710
Nüüd, kui ma olen surunud midagi
kuhja, mis järgmiseks?

195
00:09:27,710 --> 00:09:29,400
>> Olgu, ma pean juurdekasvu suurust.

196
00:09:29,400 --> 00:09:32,600
Nii et lubage mul minna ja lihtsalt
uuendada seda, mis oli null.

197
00:09:32,600 --> 00:09:35,950
Ja selle asemel, ma lähen
panna väärtus on üks.

198
00:09:35,950 --> 00:09:39,460
Ja nüüd arvan, et ma suruda teise
number peale virna, nagu 51.

199
00:09:39,460 --> 00:09:42,680
Noh, ma pean tegema veel ühe
muutust, mis on suuruses kuni kaks.

200
00:09:42,680 --> 00:09:46,100
Ja siis arvan, et ma push üks
number kuhja nagu 61,

201
00:09:46,100 --> 00:09:52,530
Nüüd on mul vaja uuendada suurus ühe
aega ja saada väärtus 3 nagu suurus.

202
00:09:52,530 --> 00:09:54,690
Ja nüüd arvan, et ma kutsun pop.

203
00:09:54,690 --> 00:09:57,250
Nüüd pop Tavapäraselt
ei võta argument.

204
00:09:57,250 --> 00:10:00,430
Mis virna, kogu
punkti salve metafoor

205
00:10:00,430 --> 00:10:03,450
on see, et sa ei pea äranägemisel
minna saan, et salve, mida sa teha oskad

206
00:10:03,450 --> 00:10:06,330
on pop tähtsaim üks
virna, lihtsalt sellepärast.

207
00:10:06,330 --> 00:10:08,010
Just see andmestruktuur teeb.

208
00:10:08,010 --> 00:10:12,250
>> Nii selle loogika, kui ma
öelda pop, mis tuleb välja?

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

210
00:10:13,080 --> 00:10:15,402
Mis siis tegelikult on arvutiga
kavatseb teha mälu?

211
00:10:15,402 --> 00:10:16,610
Mida minu kood on teha?

212
00:10:16,610 --> 00:10:20,330
Mida soovitaksite
meil muuta ekraanil?

213
00:10:20,330 --> 00:10:23,410
Mida peaks muutma?

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

215
00:10:24,960 --> 00:10:26,334
Nii me vabaneda 61.

216
00:10:26,334 --> 00:10:27,500
Nii võin kindlasti teha.

217
00:10:27,500 --> 00:10:28,640
Ja ma ei saa vabaneda 61.

218
00:10:28,640 --> 00:10:30,980
Ja mis siis muu
muutus peab toimuma?

219
00:10:30,980 --> 00:10:33,160
Suurus on ilmselt minna tagasi kaks.

220
00:10:33,160 --> 00:10:34,210
Ja nii see on hea.

221
00:10:34,210 --> 00:10:36,690
Aga oota natuke, suurus
Hetk tagasi oli kolm.

222
00:10:36,690 --> 00:10:38,240
Lihtsalt teha kiire meelerahu kontrolli.

223
00:10:38,240 --> 00:10:41,810
Kuidas me teame, et me
tahtis vabaneda 61?

224
00:10:41,810 --> 00:10:42,760
Kuna me popping.

225
00:10:42,760 --> 00:10:46,450
Ja nii on mul selle teise vara suurusest.

226
00:10:46,450 --> 00:10:48,470
>> Oota, ma olen
Mõeldes tagasi nädalal kaks

227
00:10:48,470 --> 00:10:51,660
kui me hakkasime rääkima
massiivid, kus see oli asukohast null,

228
00:10:51,660 --> 00:10:55,920
see oli asukoha ühe, see oli asukoha
kaks, see on asukoha kolme, nelja

229
00:10:55,920 --> 00:10:58,460
see näeb välja nagu
suhet suurus

230
00:10:58,460 --> 00:11:02,780
ja element, mida ma tahan, et eemaldada
massiivi tundub just see, mida?

231
00:11:02,780 --> 00:11:05,120
Suurus miinus üks.

232
00:11:05,120 --> 00:11:07,786
Ja nii see on, kuidas nii inimestele
me teame 61 jõuab.

233
00:11:07,786 --> 00:11:09,160
Kuidas arvuti läheb tea?

234
00:11:09,160 --> 00:11:11,701
Kui koodi, kus sa ilmselt
tahan teha suurust miinus üks,

235
00:11:11,701 --> 00:11:14,950
nii kolme miinus üks on kaks, ja et
tähendab, et me tahame vabaneda 61.

236
00:11:14,950 --> 00:11:18,000
Ja siis me saame tõepoolest uuendada
suurus nii, et suurus praegu

237
00:11:18,000 --> 00:11:20,300
läheb kolm kuni vaid kaks.

238
00:11:20,300 --> 00:11:24,520
Ja lihtsalt olla pedantne, ma lähen
ettepaneku, et ma olen teinud, eks?

239
00:11:24,520 --> 00:11:27,660
Sa kavandatud intuitiivselt
õigesti ma peaks vabaneda 61.

240
00:11:27,660 --> 00:11:30,700
Aga ei ole ma mingi
omamoodi saanud lahti 61?

241
00:11:30,700 --> 00:11:33,790
Olen tegelikult unustatud
et see on tegelikult olemas.

242
00:11:33,790 --> 00:11:37,680
Ja arvan, et tagasi PSET4, kui olete lugenud
artikkel umbes kriminalistika PDF

243
00:11:37,680 --> 00:11:40,780
et meil oli teiega lugeda, või siis
loeb sel nädalal PSET4.

244
00:11:40,780 --> 00:11:44,300
Tuletame meelde, et see on tegelikult Sobiv
Kogu idee arvuti kohtuekspertiisi.

245
00:11:44,300 --> 00:11:47,820
Mis arvuti üldiselt teeb, on
see lihtsalt unustab, kus midagi on,

246
00:11:47,820 --> 00:11:51,300
kuid see ei lähe ja nagu
proovige seda kratsida välja või alistada

247
00:11:51,300 --> 00:11:54,560
need bitti ühtede ja nullide
või mõni muu juhuslikult struktuuris

248
00:11:54,560 --> 00:11:56,690
kui sa ise seda tahtlikult.

249
00:11:56,690 --> 00:11:58,930
Nii oma intuitsiooni oli
õige, olgem vabaneda 61.

250
00:11:58,930 --> 00:12:00,650
Aga tegelikult me ​​ei pea vaeva.

251
00:12:00,650 --> 00:12:04,040
Me lihtsalt vaja unustada, et
see on seal, muutes oma suurust.

252
00:12:04,040 --> 00:12:05,662
>> Nüüd on probleem selles virnas.

253
00:12:05,662 --> 00:12:07,620
Kui ma hoida surudes asju
kuhja, mis on

254
00:12:07,620 --> 00:12:11,167
ilmselt juhtub
vaid mõni hetk aega?

255
00:12:11,167 --> 00:12:12,500
Me läheme ruum otsa.

256
00:12:12,500 --> 00:12:13,580
Ja mida me teeme?

257
00:12:13,580 --> 00:12:14,680
Me liiki kruvitud.

258
00:12:14,680 --> 00:12:19,000
See rakendamist ei lase
Meie suurust massiivi, sest kasutades

259
00:12:19,000 --> 00:12:21,240
Selle süntaks, kui te
arvan, et tagasi nädalal kaks,

260
00:12:21,240 --> 00:12:23,520
kui olete deklareerinud
suurus massiivi,

261
00:12:23,520 --> 00:12:26,780
me ei ole näinud mehhanismi veel, kus
saate muuta suurust massiivi.

262
00:12:26,780 --> 00:12:29,020
Ja tõepoolest C ei ole selle funktsiooni.

263
00:12:29,020 --> 00:12:32,524
Kui te ütlete mulle viis
Nths, kutsume neid numbreid,

264
00:12:32,524 --> 00:12:33,940
see on kõik sa lähed saada.

265
00:12:33,940 --> 00:12:38,790
Nii me nüüd teeme nii esmaspäeval, on
suutlikkus väljendada lahendust

266
00:12:38,790 --> 00:12:42,480
aga me lihtsalt vaja näpistama
määratlus meie stack

267
00:12:42,480 --> 00:12:46,840
mitte olema mingi kõva kodeeritud massiiv,
aga lihtsalt salvestada aadressi.

268
00:12:46,840 --> 00:12:47,890
>> Nüüd, miks see nii on?

269
00:12:47,890 --> 00:12:51,690
Nüüd me lihtsalt peame olema rahul
asjaolu, et kui mu programm töötab,

270
00:12:51,690 --> 00:12:53,730
Ma arvatavasti läheb
küsida inimese,

271
00:12:53,730 --> 00:12:55,110
kui palju numbreid sa tahad hoida?

272
00:12:55,110 --> 00:12:56,776
Nii sisend peab tulema kusagilt.

273
00:12:56,776 --> 00:12:59,140
Aga kui ma tean, et
number, siis saan lihtsalt

274
00:12:59,140 --> 00:13:02,470
kasuta missugust ülesannet anda
mul patakas mälu?

275
00:13:02,470 --> 00:13:03,580
Oskan kasutada malloc.

276
00:13:03,580 --> 00:13:06,710
Ja ma ei saa öelda ühtegi arvu
baiti Ma tahan tagasi neid Nths.

277
00:13:06,710 --> 00:13:10,910
Ja kõik, mis mul salvestada numbrid
muutuva siin sees see struct

278
00:13:10,910 --> 00:13:13,480
peaks olema siis?

279
00:13:13,480 --> 00:13:18,440
Mis tegelikult läheb
numbrid selle stsenaariumi?

280
00:13:18,440 --> 00:13:21,300
Jah, viit esimest
bait, et patakas mälu

281
00:13:21,300 --> 00:13:24,940
või täpsemalt, aadressi
esimese neist baiti.

282
00:13:24,940 --> 00:13:27,300
Ei ole oluline, kas see on üks
baidi või miljard baiti,

283
00:13:27,300 --> 00:13:28,890
Ma lihtsalt pean hooli esimene.

284
00:13:28,890 --> 00:13:31,530
Sest see, mis malloc garantiide ja
minu operatsioonisüsteemi garantiid,

285
00:13:31,530 --> 00:13:34,170
on see, et patakas mälu ma
saada see saab olema piirnevad.

286
00:13:34,170 --> 00:13:35,378
Seal ei kavatse olla puudujääke.

287
00:13:35,378 --> 00:13:38,576
Nii et kui ma olen küsinud 50
baiti või 1000 baiti,

288
00:13:38,576 --> 00:13:40,450
nad kõik saab olema
tagasi seljad.

289
00:13:40,450 --> 00:13:44,500
Ja nii kaua, kui ma mäletan, kuidas suur, kuidas
palju ma küsisin, kõik mul on vaja teada

290
00:13:44,500 --> 00:13:46,230
on esimene selline aadress.

291
00:13:46,230 --> 00:13:48,660
>> Nüüd on meil võimalus koodi.

292
00:13:48,660 --> 00:13:51,280
Kuigi, see läheb meid
rohkem aega kirjutada seda üles,

293
00:13:51,280 --> 00:13:55,900
me võiks nüüd ümber, et mälu
lihtsalt ladustamiseks erinev aadress olemas

294
00:13:55,900 --> 00:13:59,060
kui me tahame suurem või isegi
väiksem patakas mälu.

295
00:13:59,060 --> 00:14:00,170
Nii et siin on kompromiss.

296
00:14:00,170 --> 00:14:01,360
Nüüd saame dünaamikat.

297
00:14:01,360 --> 00:14:03,350
Meil on veel
contiguousness ma väidan.

298
00:14:03,350 --> 00:14:05,881
Kuna malloc annab meile
külgnevas patakas mälu.

299
00:14:05,881 --> 00:14:08,630
Aga see saab olema valu
kaela juures, programmeerija,

300
00:14:08,630 --> 00:14:09,770
tegelikult koodi üles.

301
00:14:09,770 --> 00:14:10,730
See on lihtsalt rohkem tööd.

302
00:14:10,730 --> 00:14:13,930
Me peame kood sarnane sellele, mida olin
peksma välja hetk tagasi.

303
00:14:13,930 --> 00:14:16,120
Väga sooritatav, kuid see lisab keerukust.

304
00:14:16,120 --> 00:14:19,520
Ja nii arendaja aega, programmeerija
aega on veel üks ressurss

305
00:14:19,520 --> 00:14:22,520
mis võiks olla vaja kulutada
aega, et saada uusi funktsioone.

306
00:14:22,520 --> 00:14:24,020
Ja siis muidugi on järjekord.

307
00:14:24,020 --> 00:14:26,227
Me ei hakka seda
üks palju detaile.

308
00:14:26,227 --> 00:14:27,560
Aga see on väga sarnase sisuga.

309
00:14:27,560 --> 00:14:31,220
Ma võiks rakendada järjekorda, ja
sellele vastava tegevuse,

310
00:14:31,220 --> 00:14:35,660
Lisa järjekorda või dequeue, nagu lisada või eemaldada,
see on lihtsalt Kasvataja viis öelda seda,

311
00:14:35,660 --> 00:14:38,100
Lisa järjekorda või dequeue järgmiselt.

312
00:14:38,100 --> 00:14:41,170
Ma ei anna endale struct
et jälle on mitmeid tema massiiv,

313
00:14:41,170 --> 00:14:44,000
seda uuesti tema suurus,
aga miks ma nüüd vaja

314
00:14:44,000 --> 00:14:46,940
jälgida ees järjekorras?

315
00:14:46,940 --> 00:14:50,630
Ma ei pea teadma
ees minu pakk.

316
00:14:50,630 --> 00:14:53,570
Noh, kui ma veel kord
queue-- olgem lihtsalt raske

317
00:14:53,570 --> 00:14:57,870
koodeksi, millel, nagu viis
täisarvud siin potentsiaalselt.

318
00:14:57,870 --> 00:15:00,940
Nii et see on null, üks, kaks, kolm, neli.

319
00:15:00,940 --> 00:15:03,430
See saab olema
numbrite uuesti.

320
00:15:03,430 --> 00:15:06,940
Ja see saab nimeks suurusest.

321
00:15:06,940 --> 00:15:10,056
>> Miks ei ole piisav
on lihtsalt suurus?

322
00:15:10,056 --> 00:15:11,680
Noh, olgem suruda samu numbreid.

323
00:15:11,680 --> 00:15:14,220
Nii et ma pushed-- ma enqueued või lükatakse.

324
00:15:14,220 --> 00:15:20,150
Nüüd ma Lisa järjekorda 50 ja seejärel
51 ja siis 61 ja dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Nii et Lisa järjekorda.

326
00:15:21,070 --> 00:15:23,176
Ma enqueued 50, siis 51, siis 61.

327
00:15:23,176 --> 00:15:25,050
Ja mis näeb välja identne
korstnat seni,

328
00:15:25,050 --> 00:15:27,190
va ma vaja teha üks muutus.

329
00:15:27,190 --> 00:15:33,680
Mul on vaja uuendada selle suurus, nii et ma lähen
nullist üheni to 02:58 nüüd.

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

331
00:15:35,760 --> 00:15:36,890
Mis juhtub dequeue?

332
00:15:36,890 --> 00:15:41,950
Kes peaks tulema välja selle nimekirja esimene
kui see rida on Apple Store?

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

334
00:15:42,780 --> 00:15:44,700
Nii et see on selline keerukam seekord.

335
00:15:44,700 --> 00:15:47,880
Kui eelmisel korral oli super
lihtne lihtsalt teha suurust miinus üks,

336
00:15:47,880 --> 00:15:51,440
Ma saan lõpuks minu rida tõhusalt
kus numbrid on, see eemaldab 61.

337
00:15:51,440 --> 00:15:52,920
Aga ma ei taha kaotada 61.

338
00:15:52,920 --> 00:15:55,030
Ma tahan olla 50, kes
oli seal 5:00

339
00:15:55,030 --> 00:15:56,790
rivistama jaoks
uus iPhone või tühi-tähi.

340
00:15:56,790 --> 00:16:01,200
Ja nii vabaneda 50, ma
ei saa lihtsalt teha seda, eks?

341
00:16:01,200 --> 00:16:02,547
Ma ei kriipsutama 50.

342
00:16:02,547 --> 00:16:04,380
Aga me lihtsalt ütles, et me
ei pea olema nii anal

343
00:16:04,380 --> 00:16:06,330
kui tühjalt läbi või peita andmed.

344
00:16:06,330 --> 00:16:08,090
Me lihtsalt unustada, kus ta on.

345
00:16:08,090 --> 00:16:12,330
>> Aga kui ma muudan suurust nüüd
kaks, on see piisav teave

346
00:16:12,330 --> 00:16:15,711
teada, mis toimub minu järjekord?

347
00:16:15,711 --> 00:16:16,680
Mitte päris.

348
00:16:16,680 --> 00:16:19,830
Nagu mu suurus on kaks, kuid
kus ei järjekorda hakkavad,

349
00:16:19,830 --> 00:16:22,980
eriti kui ma veel
samad numbrid mällu.

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

351
00:16:24,260 --> 00:16:27,090
Nii et ma pean meeles
Nüüd, kus ees on.

352
00:16:27,090 --> 00:16:29,630
Ja nii nagu ma pakutud üles
seal, me oleme just helistas

353
00:16:29,630 --> 00:16:33,729
Nth ees, kelle algne
väärtus oleks pidanud olema, mida?

354
00:16:33,729 --> 00:16:35,270
Zero, alles algus nimekirja.

355
00:16:35,270 --> 00:16:40,876
Aga nüüd lisaks decrementing
suurus, me lihtsalt juurdekasvu ees.

356
00:16:40,876 --> 00:16:42,000
Nüüd siin on veel üks probleem.

357
00:16:42,000 --> 00:16:43,030
Nii et kui ma edasi.

358
00:16:43,030 --> 00:16:47,520
Oletame, et see on number
nagu 121, 124, ja siis, kurat võtaks,

359
00:16:47,520 --> 00:16:48,610
Ma olen enam ruumi.

360
00:16:48,610 --> 00:16:50,390
Aga oota üks hetk, ma ei ole.

361
00:16:50,390 --> 00:16:55,630
Nii siinkohal lugu,
oletame, et suurus on üks, kaks,

362
00:16:55,630 --> 00:17:00,370
kolm, neli, nii oletame, et
suurus on neli, ees on üks,

363
00:17:00,370 --> 00:17:01,621
nii 51 eesmises.

364
00:17:01,621 --> 00:17:04,329
Ma tahan panna teisele numbrile siin
kuid, kurat võtaks, ma olen enam ruumi.

365
00:17:04,329 --> 00:17:06,710
Aga ma ei ole tõesti, eks?

366
00:17:06,710 --> 00:17:11,192
Kust ma panen
lisaväärtust, nagu 171?

367
00:17:11,192 --> 00:17:13,400
Jah, ma võiks lihtsalt selline
minna tagasi sinna, eks?

368
00:17:13,400 --> 00:17:18,161
Ja siis välja järgmised 50 või
lihtsalt kirjutada seda 171.

369
00:17:18,161 --> 00:17:20,410
Ja kui sa ei tea, miks
Meie numbrid sain nii juhuslik,

370
00:17:20,410 --> 00:17:24,150
need on tavaliselt tehtud arvuti
reaalerialadel Harvardi pärast CS50.

371
00:17:24,150 --> 00:17:27,510
Aga see oli hea optimeerimine,
sest nüüd ma ei raiska ruumi.

372
00:17:27,510 --> 00:17:30,750
Mul on veel meeles
kui suur see asi on kokku.

373
00:17:30,750 --> 00:17:31,500
See viis kokku.

374
00:17:31,500 --> 00:17:33,375
Sest ma ei taha
alustada kirjutaks 51.

375
00:17:33,375 --> 00:17:36,260
Nüüd ma olen ikka ruumi,
nii sama probleem nagu enne.

376
00:17:36,260 --> 00:17:39,140
Aga näed, kuidas nüüd
oma koodi, siis ilmselt

377
00:17:39,140 --> 00:17:41,910
pean kirjutama natuke rohkem
keerukuse teha, mis juhtub.

378
00:17:41,910 --> 00:17:44,510
Ja tegelikult, mida operaator
C ilmselt laseb

379
00:17:44,510 --> 00:17:48,110
sa võluväel teha ringlev?

380
00:17:48,110 --> 00:17:50,160
Jah mooduli järgi operaator,
protsenti märk.

381
00:17:50,160 --> 00:17:53,160
Mis siis selline lahe umbes järjekorda,
kuigi me hoida joonistus massiivid

382
00:17:53,160 --> 00:17:56,520
kui need nagu sirged jooned, kui te
Selline mõtle seda koole

383
00:17:56,520 --> 00:18:00,341
umbes nagu ring, siis lihtsalt
intuitiivselt seda liiki töötab vaimselt

384
00:18:00,341 --> 00:18:01,590
Ma arvan, et veidi rohkem vigadeta.

385
00:18:01,590 --> 00:18:05,190
Sa ikkagi ellu
et vaimse mudeli koodi.

386
00:18:05,190 --> 00:18:07,550
Nii ei ole nii raske,
lõpuks rakendada,

387
00:18:07,550 --> 00:18:12,430
aga me ikka kaotada size-- pigem
võime suurust, kui me seda teeme.

388
00:18:12,430 --> 00:18:15,310
>> Meil on vabaneda massiivi me
asendada see ühe pointer,

389
00:18:15,310 --> 00:18:20,010
ja siis kuskil minu kood on mul
helista mida toimida tegelikult luua

390
00:18:20,010 --> 00:18:23,720
massiivi nimetatakse numbrid?

391
00:18:23,720 --> 00:18:26,190
Malloc või samalaadse
funktsiooni, täpselt.

392
00:18:26,190 --> 00:18:30,481
Iga küsimustele korstnad või järjekorrad.

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

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

395
00:18:33,657 --> 00:18:34,240
Hea küsimus.

396
00:18:34,240 --> 00:18:35,830
Mis moodul oleks te kasutate siin.

397
00:18:35,830 --> 00:18:38,520
Nii üldisemalt kasutamisel
mod, siis teeksin seda

398
00:18:38,520 --> 00:18:40,620
koos suurust
Kogu andmestruktuur.

399
00:18:40,620 --> 00:18:44,120
Nii midagi viiest või võimsust, kui
see on pidev, on ilmselt seotud.

400
00:18:44,120 --> 00:18:47,100
Aga teeme moodul viis
ilmselt ei ole piisav,

401
00:18:47,100 --> 00:18:51,380
sest me peame teadma, kas me
ümbritsev siit või siit või siit.

402
00:18:51,380 --> 00:18:54,160
Nii et sa oled ilmselt ka
kavatse soovite kaasata

403
00:18:54,160 --> 00:18:57,220
suurusest asi või
ees muutuja samuti.

404
00:18:57,220 --> 00:19:00,140
Nii et see on lihtsalt see suhteliselt
Lihtne aritmeetika väljendus,

405
00:19:00,140 --> 00:19:02,000
aga mooduli oleks võtmetähtsusega.

406
00:19:02,000 --> 00:19:03,330
>> Nii lühifilm kui soovite.

407
00:19:03,330 --> 00:19:05,780
Animatsioon, et mõned
inimesed teises ülikoolis

408
00:19:05,780 --> 00:19:08,060
kokku panna, et me oleme
kohandatud arutelu.

409
00:19:08,060 --> 00:19:12,630
See hõlmab Jack õppimise
fakte järjekorrad ja statistika.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Kunagi ammu,
seal oli mees nimega Jack.

412
00:19:21,890 --> 00:19:25,330
Kui ta tuli sõpru,
Jack ei olnud harjumus.

413
00:19:25,330 --> 00:19:28,220
Nii Jack läks rääkima
Populaarseim poiss teadis ta.

414
00:19:28,220 --> 00:19:30,920
Ta läks Lou ja küsis, mida ma pean tegema?

415
00:19:30,920 --> 00:19:33,400
Lou nägi, et tema sõber
oli tõesti õnnetud.

416
00:19:33,400 --> 00:19:36,050
Noh, ta hakkas lihtsalt
vaata kui sa riides.

417
00:19:36,050 --> 00:19:38,680
Kas sul pole riideid
erineva ilme?

418
00:19:38,680 --> 00:19:39,660
Jah, ütles Jack.

419
00:19:39,660 --> 00:19:40,840
Ma kindlasti teha.

420
00:19:40,840 --> 00:19:43,320
Tule minu maja ja
Ma näitan neid teile.

421
00:19:43,320 --> 00:19:44,550
Nii nad läksid välja Jacki.

422
00:19:44,550 --> 00:19:47,520
Ja Jack näitas Lou kasti
kus ta jättis kõik oma särgid,

423
00:19:47,520 --> 00:19:49,260
ja tema püksid, ja tema sokid.

424
00:19:49,260 --> 00:19:52,290
Lou ütles, ma näen sa pead
kõik oma riided kuhja.

425
00:19:52,290 --> 00:19:54,870
Miks sa ei kulumine mõned
teised kord aega?

426
00:19:54,870 --> 00:19:58,020
>> Jack ütles, noh, kui ma
eemaldada riideid ja sokke,

427
00:19:58,020 --> 00:20:00,780
Ma pesta neid ja panna
neid ära kasti.

428
00:20:00,780 --> 00:20:03,210
Siis tuleb järgmine
hommikul, ja kuni ma hop.

429
00:20:03,210 --> 00:20:06,380
Ma lähen kasti ja saada
minu riided kaovad.

430
00:20:06,380 --> 00:20:09,070
Lou kiiresti aru
probleem Jack.

431
00:20:09,070 --> 00:20:12,080
Ta hoidis riideid, CD,
ja raamatud virnas.

432
00:20:12,080 --> 00:20:14,420
Kui ta jõudis jaoks
midagi lugeda või kandma,

433
00:20:14,420 --> 00:20:17,100
ta tahaks valida top raamatu või aluspesu.

434
00:20:17,100 --> 00:20:19,500
Siis, kui ta oli teinud, ta
paneks ta kohe tagasi.

435
00:20:19,500 --> 00:20:21,970
Tagasi ta ei tahaks minna, peal virnas.

436
00:20:21,970 --> 00:20:24,460
Ma tean, et lahendus,
ütles võidukas Loud.

437
00:20:24,460 --> 00:20:27,090
Sa pead õppima
hakake järjekorda.

438
00:20:27,090 --> 00:20:29,870
Lou võttis Jacki riideid ja
riputasid need kapis.

439
00:20:29,870 --> 00:20:32,710
Ja kui ta oli tühjendada
kasti, siis ta lihtsalt viskad ta.

440
00:20:32,710 --> 00:20:36,500
>> Siis ta ütles, nüüd Jack, lõpus
Päeva panna oma riideid vasakul

441
00:20:36,500 --> 00:20:37,990
kui paned neid ära.

442
00:20:37,990 --> 00:20:41,300
Siis homme hommikul, kui sa
vaata päikest, su riided

443
00:20:41,300 --> 00:20:43,440
Paremal alates rea lõppu.

444
00:20:43,440 --> 00:20:44,880
Kas sa ei näe? ütles Lou.

445
00:20:44,880 --> 00:20:46,370
See on nii kena.

446
00:20:46,370 --> 00:20:49,770
Sa kannan kõike korraga
Enne kanda midagi korda.

447
00:20:49,770 --> 00:20:52,670
Ja kõike järjekorrad
tema kapis ja riiul,

448
00:20:52,670 --> 00:20:55,160
Jack hakkas tunda
üsna enesekindel.

449
00:20:55,160 --> 00:20:59,720
Kõik tänu Lou ja
Tema imeline järjekorda.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Olgu, see on jumalik.

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

452
00:21:05,920 --> 00:21:10,080
Mis on tõesti
kohta all kapuuts nüüd?

453
00:21:10,080 --> 00:21:12,370
Et meil on viiteid,
et meil on malloc,

454
00:21:12,370 --> 00:21:15,680
et meil on võime luua
tükkideks mälu ise

455
00:21:15,680 --> 00:21:16,344
dünaamiliselt.

456
00:21:16,344 --> 00:21:18,510
Nii et see on pilt me
ühtesid just mõni päev.

457
00:21:18,510 --> 00:21:21,180
Me tegelikult ei ela
seda, kuid see pilt

458
00:21:21,180 --> 00:21:24,180
on kestnud alla
kapuuts nädalat nüüd.

459
00:21:24,180 --> 00:21:27,050
Ja nii see on, lihtsalt
ristkülik, et oleme tõmmatud,

460
00:21:27,050 --> 00:21:28,180
arvuti mällu.

461
00:21:28,180 --> 00:21:31,850
Ja võib-olla arvuti või CS50
ID, on GB mälu või RAM

462
00:21:31,850 --> 00:21:33,050
või kaks gigabaiti või neli.

463
00:21:33,050 --> 00:21:34,450
See ei ole tegelikult küsimus.

464
00:21:34,450 --> 00:21:37,240
Teie operatsioonisüsteem
Windows või Mac OS või Linux,

465
00:21:37,240 --> 00:21:41,120
sisuliselt võimaldab oma programmi
arvan, et tal on juurdepääs

466
00:21:41,120 --> 00:21:42,982
ta kõigile
arvuti mälus,

467
00:21:42,982 --> 00:21:45,440
kuigi võite olla töötab
mitut programmi korraga.

468
00:21:45,440 --> 00:21:46,990
Nii et tegelikult see ei toimi.

469
00:21:46,990 --> 00:21:49,448
Aga see on selline illusioon
anda kõik oma programmid.

470
00:21:49,448 --> 00:21:53,110
Nii et kui sul oli kaks kontserti RAM, seda
kuidas arvuti võiks mõelda.

471
00:21:53,110 --> 00:21:57,110
>> Nüüd juhuslikult, üks neist
asju, üks neist segmentides mälu,

472
00:21:57,110 --> 00:21:58,350
nimetatakse virna.

473
00:21:58,350 --> 00:22:01,680
Ja tõepoolest igal ajal
Seni kirjalikult koodi

474
00:22:01,680 --> 00:22:05,900
et olete kutsutud
funktsiooni, näiteks peamine.

475
00:22:05,900 --> 00:22:08,410
Tuletame meelde, et igal ajal ma olen
joonistatud arvuti mälus,

476
00:22:08,410 --> 00:22:10,640
Olen alati teha omamoodi
pool ristküliku siin

477
00:22:10,640 --> 00:22:12,520
ja ei viitsinud räägi
mida on eespool.

478
00:22:12,520 --> 00:22:15,980
Sest kui peamine nimetatakse, Väidan
mis sa selle Kiip mälu

479
00:22:15,980 --> 00:22:16,970
et loojub siin.

480
00:22:16,970 --> 00:22:20,650
Ja kui peamine nimetatakse funktsiooni
nagu swap, ka swap läheb siia.

481
00:22:20,650 --> 00:22:23,720
Ja selgub, et on
kus see jõuavad.

482
00:22:23,720 --> 00:22:26,277
On midagi, mida nimetatakse virna
sees arvuti mällu.

483
00:22:26,277 --> 00:22:28,360
Nüüd lõpus päeval,
see on lihtsalt aadressid.

484
00:22:28,360 --> 00:22:30,680
See on nagu bait null,
bait ühe baidi 2 miljardit.

485
00:22:30,680 --> 00:22:33,130
Aga kui sa arvad
kui see nelinurkne objekt,

486
00:22:33,130 --> 00:22:35,130
kõik me teeme iga
kord, kui me nimetame funktsiooni

487
00:22:35,130 --> 00:22:37,180
kihilisus uus tükk mälu.

488
00:22:37,180 --> 00:22:41,700
Anname selle funktsiooni viilu
omal mälu töötada.

489
00:22:41,700 --> 00:22:44,490
>> Ja meenutada nüüd, et see on oluline.

490
00:22:44,490 --> 00:22:46,400
Sest kui me ei ole
midagi swap

491
00:22:46,400 --> 00:22:51,610
ja kaks kohalikud muutujad nagu A ja B ning
muudame need väärtused ühest ja kaks

492
00:22:51,610 --> 00:22:55,130
kaks ja üks, tagasikutsumine
et kui swap naaseb,

493
00:22:55,130 --> 00:22:58,330
see on nagu oleks see tükk
mälu on lihtsalt läinud.

494
00:22:58,330 --> 00:23:00,080
Tegelikult, see on ikka
seal forensically.

495
00:23:00,080 --> 00:23:01,940
Ja midagi on ikka tegelikult olemas.

496
00:23:01,940 --> 00:23:05,410
Aga põhimõtteliselt, see on nii
Kuigi see on täiesti kadunud.

497
00:23:05,410 --> 00:23:10,910
Ja nii peamine ei tea ühtegi tööd
mis tehti, et swap funktsiooni,

498
00:23:10,910 --> 00:23:14,890
kui see on tegelikult läbinud nendes
argumendid, pointer, viitena.

499
00:23:14,890 --> 00:23:17,790
Nüüd põhiline lahendus
Selle probleemi swap

500
00:23:17,790 --> 00:23:19,970
möödub asju aadressi.

501
00:23:19,970 --> 00:23:23,250
Aga selgub ka, mis on
kestnud üle, et osa

502
00:23:23,250 --> 00:23:26,330
ristküliku kõik see aeg on
veel seal on rohkem mälu seal.

503
00:23:26,330 --> 00:23:28,790
Ja kui sa dünaamiliselt
mälu eraldada,

504
00:23:28,790 --> 00:23:32,020
kas see on sees getString, mis
oleme teinud teie jaoks on CS50

505
00:23:32,020 --> 00:23:34,710
raamatukogu, või kui te poisid
helistada malloc ja küsi

506
00:23:34,710 --> 00:23:37,950
operatsioonisüsteemi patakas
mälu, ta ei ole pärit virna.

507
00:23:37,950 --> 00:23:40,960
Ta on pärit teise koha
arvuti mällu

508
00:23:40,960 --> 00:23:42,220
seda nimetatakse hunnik.

509
00:23:42,220 --> 00:23:43,430
Ja see pole veel kõik erinevad.

510
00:23:43,430 --> 00:23:44,285
See on sama RAM.

511
00:23:44,285 --> 00:23:45,160
See on sama mälu.

512
00:23:45,160 --> 00:23:49,080
See on lihtsalt RAM, mis on üles
seal asemel siin.

513
00:23:49,080 --> 00:23:50,750
>> Ja mis see tähendab?

514
00:23:50,750 --> 00:23:53,650
Noh, kui arvuti on
piiratud kogus mälu

515
00:23:53,650 --> 00:23:57,450
ja stack kasvab üles, nii et
rääkida, ja hunnik järgi

516
00:23:57,450 --> 00:23:59,349
Selle nool, kasvab alla.

517
00:23:59,349 --> 00:24:01,140
Teisisõnu, iga
kord, kui helistada malloc,

518
00:24:01,140 --> 00:24:03,430
sa pööratakse viilu
mälu ülevalt,

519
00:24:03,430 --> 00:24:06,630
siis võibolla natuke väiksem, siis natuke
madalam, iga kord, kui helistada malloc,

520
00:24:06,630 --> 00:24:10,100
hunnik, see kasutust,
on selline kasvab,

521
00:24:10,100 --> 00:24:11,950
kasvav lähemale ja lähemale, mis?

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

523
00:24:13,382 --> 00:24:14,840
Nii see tunduda hea mõte?

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

525
00:24:18,420 --> 00:24:22,140
Ma mõtlen, kus see ei ole päris selge,
mida veel saab teha, kui sa ainult

526
00:24:22,140 --> 00:24:23,910
on piiratud mälu.

527
00:24:23,910 --> 00:24:25,200
Aga see on kindlasti halb.

528
00:24:25,200 --> 00:24:27,920
Need kaks noolt olete
kiirkursuse üksteise.

529
00:24:27,920 --> 00:24:31,930
>> Ja selgub, et paha poiss, inimesed, kes
Eriti hea programmeerimise,

530
00:24:31,930 --> 00:24:36,140
ja üritab häkkida arvuteid,
võib kasutada seda reaalsust.

531
00:24:36,140 --> 00:24:38,290
Tegelikult Vaatleme
väike väljavõte.

532
00:24:38,290 --> 00:24:41,350
Nii et see on näide saate lugeda
umbes põhjalikumalt Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Me juhtida sind
article kui uudishimulik.

534
00:24:43,100 --> 00:24:45,650
Aga seal on rünnak üldiselt
tuntud buffer overflow, et

535
00:24:45,650 --> 00:24:49,570
on eksisteerinud niikaua inimestel
pidanud manipuleerimise võimet

536
00:24:49,570 --> 00:24:53,120
arvuti mällu, eriti C.
Nii et see on väga meelevaldne programmi

537
00:24:53,120 --> 00:24:55,130
kuid olgem lugeda alt üles.

538
00:24:55,130 --> 00:24:57,650
Main arvesse Argc char star argv.

539
00:24:57,650 --> 00:24:59,830
Nii et see on programm, mis võtab
käsurea argumente.

540
00:24:59,830 --> 00:25:03,620
Ja kõik peamised see ilmselt on kõne
funktsioon, nimetame seda F lihtsuse.

541
00:25:03,620 --> 00:25:04,610
Ja see möödub mida?

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

543
00:25:05,490 --> 00:25:09,320
Nii satub F iganes
sõna on see, et kasutaja sisestatud

544
00:25:09,320 --> 00:25:11,500
käsureale pärast
Programmi nimi üldse.

545
00:25:11,500 --> 00:25:15,730
Nii palju nagu Caesar või Vigenere, mis
sa võiks meenutada, teed argv.

546
00:25:15,730 --> 00:25:16,680
>> Mis on F?

547
00:25:16,680 --> 00:25:19,760
F võtab string
kui selle ainus argument,

548
00:25:19,760 --> 00:25:22,100
AKA char star, samal
asi, kui string.

549
00:25:22,100 --> 00:25:24,920
Ja seda nimetatakse suvaliselt
baar see näide.

550
00:25:24,920 --> 00:25:27,710
Ja siis char c 12
lihtsalt üldarusaadavat mõttes,

551
00:25:27,710 --> 00:25:31,750
Mis on char c sulg 12 teeme meie jaoks?

552
00:25:31,750 --> 00:25:33,440
Mida see teeb?

553
00:25:33,440 --> 00:25:36,490
Eraldamine mälu, eriti
12 baiti 12 tähemärki.

554
00:25:36,490 --> 00:25:36,990
Täpselt.

555
00:25:36,990 --> 00:25:40,000
Ja siis viimane rida, segatakse ja
koopia, olete ilmselt ei näinud.

556
00:25:40,000 --> 00:25:43,360
See on string koopia
funktsiooni, mille eesmärk elus

557
00:25:43,360 --> 00:25:48,160
on kopeerida oma teise argumendi
arvesse oma esimese väitega,

558
00:25:48,160 --> 00:25:51,190
kuid ainult kuni
Teatud baitide arvu.

559
00:25:51,190 --> 00:25:53,860
Nii kolmas argument ütleb,
kui palju baite peaksid sa kuuled?

560
00:25:53,860 --> 00:25:56,720
Pikkus baar,
olenemata kasutaja sisestatud.

561
00:25:56,720 --> 00:25:59,320
Ja sisu
Baar, et string on

562
00:25:59,320 --> 00:26:02,330
kopeeritakse mällu osutas juures C.

563
00:26:02,330 --> 00:26:04,060
>> Nii et see tundub tobe, ja see on.

564
00:26:04,060 --> 00:26:06,300
See on kunstlik näiteks
aga see on esindaja

565
00:26:06,300 --> 00:26:10,100
klassi rünnaku vektorid,
viis rünnata programmi.

566
00:26:10,100 --> 00:26:15,050
Kõik on korras ja hea, kui kasutaja
liigid sõna, mis on 11 tähemärki

567
00:26:15,050 --> 00:26:18,040
või vähem, pluss kurakriips null.

568
00:26:18,040 --> 00:26:22,830
Mis siis, kui kasutaja tipib üle
11 või 12 või 20 või 50 tähemärki?

569
00:26:22,830 --> 00:26:25,090
Mis see programm tegema hakkad?

570
00:26:25,090 --> 00:26:29,360
Potentsiaalselt seg süü. See läheb
pimesi kopeerida kõike bar kuni

571
00:26:29,360 --> 00:26:31,750
selle pikkuse, mis on
sõna otseses mõttes kõike baar,

572
00:26:31,750 --> 00:26:36,307
aadressiribale osutas C. Aga C
on ainult ennetavalt manustada 12 baiti.

573
00:26:36,307 --> 00:26:37,640
Aga seal on mingit täiendavat kontrolli.

574
00:26:37,640 --> 00:26:38,700
Ei ole, kui tingimused.

575
00:26:38,700 --> 00:26:40,580
Pole veakontrollialgoritmide siin.

576
00:26:40,580 --> 00:26:43,270
>> Ja mis siis see programm on
lähen tegema, on lihtsalt pimesi

577
00:26:43,270 --> 00:26:45,750
kopeerida üks asi teise.

578
00:26:45,750 --> 00:26:47,880
Ja kui me tõmbame selle
kui pilt, siin

579
00:26:47,880 --> 00:26:49,860
lihtsalt Kiip mälu.

580
00:26:49,860 --> 00:26:53,470
Nii märkate allosas, me
on kohaliku muutuja baar.

581
00:26:53,470 --> 00:26:57,330
Nii et osuti, mis läheb store--
pigem, et kohalikud argument, mis on

582
00:26:57,330 --> 00:26:58,672
läheb salvestada string baar.

583
00:26:58,672 --> 00:27:00,380
Ja siis märkate lihtsalt
Ülaltoodud seda virna,

584
00:27:00,380 --> 00:27:02,505
sest iga kord, kui küsida
mälu virna,

585
00:27:02,505 --> 00:27:04,310
see läheb natuke
Ülaltoodud see piltlikult,

586
00:27:04,310 --> 00:27:06,270
teate, et meil 12 baiti seal.

587
00:27:06,270 --> 00:27:10,690
Ülemine vasakpoolne on C sulg null ja
alumine parempoolne on C sulg 11.

588
00:27:10,690 --> 00:27:12,870
See on lihtsalt, kuidas arvutid
läheb panna see välja.

589
00:27:12,870 --> 00:27:18,300
Nii lihtsalt intuitiivselt, kui baaris on rohkem
kui 12 tähemärki kokku, sh

590
00:27:18,300 --> 00:27:25,790
längkriipsu null, kus on
12 või C sulg 12 kavatse minna?

591
00:27:25,790 --> 00:27:28,440
Või õigemini, kus on 12
iseloomu või 13. iseloomu,

592
00:27:28,440 --> 00:27:30,900
sajandat iseloomu, mis
lõpuks pildil?

593
00:27:30,900 --> 00:27:33,400
Kõrgem või madalam?

594
00:27:33,400 --> 00:27:36,300
>> Õigus, sest kuigi
korstnat ise kasvab ülespoole,

595
00:27:36,300 --> 00:27:39,590
kui olete panna asjad
see, et konstruktsiooni tõttu,

596
00:27:39,590 --> 00:27:41,294
paneb mälu ülevalt alla.

597
00:27:41,294 --> 00:27:44,460
Nii et kui sul on rohkem kui 12 baiti,
sa lähed alustada kirjutada baar.

598
00:27:44,460 --> 00:27:47,280
Nüüd ongi viga, aga see on
tegelikult ei ole suur asi.

599
00:27:47,280 --> 00:27:51,130
Aga see on suur asi, sest seal on
rohkem asju toimub mälu.

600
00:27:51,130 --> 00:27:53,074
Nii et siin on, kuidas me võiksime
pane hello, peab olema selge.

601
00:27:53,074 --> 00:27:54,490
Kui ma kirjutada hello käsureale.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O kurakriips null, jõuab jooksul
need 12 baiti, ja me oleme super ohutu.

603
00:27:59,330 --> 00:28:00,330
Kõik on hästi.

604
00:28:00,330 --> 00:28:03,020
Aga kui ma kirjuta midagi
enam, potentsiaalselt on

605
00:28:03,020 --> 00:28:05,860
läheb libiseda baar ruumi.

606
00:28:05,860 --> 00:28:08,405
Aga hullem veel, selgub
välja kõik see aeg,

607
00:28:08,405 --> 00:28:11,530
kuigi me pole kunagi rääkinud
see, korstna kasutatakse muud kraami.

608
00:28:11,530 --> 00:28:13,560
See ei ole lihtsalt kohalikud muutujad.

609
00:28:13,560 --> 00:28:15,100
>> C on väga madal keeles.

610
00:28:15,100 --> 00:28:17,810
Ja see omamoodi salaja
kasutab stack ka

611
00:28:17,810 --> 00:28:21,260
meeles pidada, kui
funktsiooni nimetatakse, mida

612
00:28:21,260 --> 00:28:26,040
aadress on eelmise funktsiooni,
et ta saaks hüpata tagasi selle funktsiooni.

613
00:28:26,040 --> 00:28:29,980
Nii et kui peamine kõnesid vahetada hulgas
asjad surutakse korstnat

614
00:28:29,980 --> 00:28:34,380
ei ole lihtsalt vahetab kohalikud muutujad,
või tema argumente, ka salaja surunud

615
00:28:34,380 --> 00:28:37,510
peale virna, mida esindab
punane viil siin

616
00:28:37,510 --> 00:28:40,520
on aadress peamised füüsiliselt
arvuti mälus,

617
00:28:40,520 --> 00:28:44,180
nii, et kui swap tehakse, arvuti
teab, et ma pean minema tagasi pealehele

618
00:28:44,180 --> 00:28:46,760
ja lõpetuseks täidesaatva põhiülesanne.

619
00:28:46,760 --> 00:28:51,960
Nii et see on ohtlik nüüd, sest kui
kasutaja liigid ka rohkem kui hello,

620
00:28:51,960 --> 00:28:57,030
nii, et kasutaja sisend clobbers
või kirjutab, et punane osa,

621
00:28:57,030 --> 00:28:59,820
loogiliselt, kui arvuti
lihtsalt läheb pimesi oletada

622
00:28:59,820 --> 00:29:03,830
et baiti, et punane viil on
aadress, kuhu ta peaks tagasi,

623
00:29:03,830 --> 00:29:09,020
Mis siis, kui vastane on piisavalt targad või
õnn panna baitide järjestust

624
00:29:09,020 --> 00:29:13,450
seal, et näeb välja nagu aadress,
aga see on aadress koodi

625
00:29:13,450 --> 00:29:18,730
et ta tahab arvuti
täita asemel peamine?

626
00:29:18,730 --> 00:29:21,670
>> Teisisõnu, kui see, mida
kasutaja kirjutades käsureale,

627
00:29:21,670 --> 00:29:23,850
ei ole lihtsalt midagi
kahjutu nagu hello,

628
00:29:23,850 --> 00:29:28,210
aga see on tegelikult kood, mis on samaväärne
kustutada kõik selle kasutaja faile?

629
00:29:28,210 --> 00:29:30,060
Või e-posti oma parooli mind?

630
00:29:30,060 --> 00:29:31,940
Või alustada logides oma
klahvivajutusi, eks?

631
00:29:31,940 --> 00:29:34,920
On võimalus, olgem sätestada täna
et nad võiksid kirjutada mitte ainult hello

632
00:29:34,920 --> 00:29:36,711
maailma või oma nime,
nad võiksid sisuliselt

633
00:29:36,711 --> 00:29:39,570
pass koodi, nulle ning
ones, et arvuti

634
00:29:39,570 --> 00:29:43,450
vigu nii koodi ja aadressi.

635
00:29:43,450 --> 00:29:48,950
Nii ehkki mõnevõrra abstraktselt, kui
kasutaja liigid piisavalt võistleva koodi

636
00:29:48,950 --> 00:29:52,330
et me üldistada siin
A. A on rünnaku või vaenlased.

637
00:29:52,330 --> 00:29:53,140
Nii lihtsalt halvad asjad.

638
00:29:53,140 --> 00:29:55,306
Me ei hooli
numbrid või nulli või need

639
00:29:55,306 --> 00:29:59,470
täna, nii et sa lõpuks
kirjutaks, et punane osa,

640
00:29:59,470 --> 00:30:01,580
märgata, et baitide järjestust.

641
00:30:01,580 --> 00:30:05,020
O 835 C null kaheksa null.

642
00:30:05,020 --> 00:30:08,960
Ja nüüd, kui Wikipedia artikkel siin
on teinud ettepaneku, kui te nüüd tõesti hakata

643
00:30:08,960 --> 00:30:12,460
märgistades baiti arvuti
mälu, mida Wikipedia artikkel

644
00:30:12,460 --> 00:30:19,060
Ettepaneku, et mis siis, kui aadress
Selle ülaosas vasakul bait on 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Teisisõnu, kui halb on
piisavalt targad koos tema kood

646
00:30:22,200 --> 00:30:26,650
tegelikult panna number siin, et
vastab aadress koodi

647
00:30:26,650 --> 00:30:29,180
ta süstida
arvuti, siis

648
00:30:29,180 --> 00:30:31,050
võib petta arvuti
arvesse tee midagi.

649
00:30:31,050 --> 00:30:34,140
Failide eemaldamine, postitada
asju, nuusutamisel oma liiklust,

650
00:30:34,140 --> 00:30:36,710
sõna otseses mõttes midagi võiks olla
süstitakse arvutisse.

651
00:30:36,710 --> 00:30:39,220
Ja nii buffer overflow
rünnaku keskmes

652
00:30:39,220 --> 00:30:43,530
on lihtsalt loll, loll
ülekaalukate massiivi et

653
00:30:43,530 --> 00:30:45,840
ei oma piire kontrollida.

654
00:30:45,840 --> 00:30:48,850
Ja see on see, mis on super ohtlik
ja samal ajal super võimas

655
00:30:48,850 --> 00:30:52,560
C on see, et meil on tõepoolest
juurdepääs kõikjal mälu.

656
00:30:52,560 --> 00:30:55,320
See on kuni meile programmeerijaid,
kes kirjutavad originaal kood

657
00:30:55,320 --> 00:30:59,330
kontrollida paganama pikkus tahes
massiivid, et me manipuleerides.

658
00:30:59,330 --> 00:31:00,750
Nii et oleks selge, milline on fix?

659
00:31:00,750 --> 00:31:03,190
Kui me tagasi pöörata sellele
kood, ma ei tohiks lihtsalt

660
00:31:03,190 --> 00:31:08,000
pikkuse muutmine bar, mida
ma veel peaksin kontrollida?

661
00:31:08,000 --> 00:31:10,620
Mida ma peaksin tegema, et
vältida selle rünnaku täielikult?

662
00:31:10,620 --> 00:31:14,110
Ma ei taha lihtsalt pimesi öelda
et sa peaksid kopeerida nii palju baite

663
00:31:14,110 --> 00:31:16,140
kui on pikkus baar.

664
00:31:16,140 --> 00:31:18,910
Ma tahan öelda, kopeerib
palju baite kui on baar

665
00:31:18,910 --> 00:31:24,090
kuni eraldatud
mälu, või 12 maksimaalselt.

666
00:31:24,090 --> 00:31:27,450
Nii et ma pean mingi kui seisund
et ei vaadata pikkus baar,

667
00:31:27,450 --> 00:31:32,800
aga kui see ületab 12, me lihtsalt raske koodi
12 puhul maksimaalne võimalik kaugus.

668
00:31:32,800 --> 00:31:35,910
Vastasel niinimetatud puhvris
ülevoolu rünnak võib juhtuda.

669
00:31:35,910 --> 00:31:38,451
Allosas slaidid,
kui sa oled uudishimulik loe edasi

670
00:31:38,451 --> 00:31:41,200
on tegelik algartikkel
Kui soovite võtta pilk.

671
00:31:41,200 --> 00:31:44,550
>> Aga nüüd hulgas hinnad
makstakse siin oli ebaefektiivsust.

672
00:31:44,550 --> 00:31:46,680
Nii et oli kiire
madal pilk

673
00:31:46,680 --> 00:31:49,709
probleemid võivad tekkida nüüd, et me
on juurdepääs arvuti mällu.

674
00:31:49,709 --> 00:31:51,750
Aga teine ​​probleem meil
juba komistanud esmaspäeval

675
00:31:51,750 --> 00:31:53,800
oli lihtsalt ebaefektiivsuse
on seotud nimekirja.

676
00:31:53,800 --> 00:31:56,019
Oleme tagasi lineaarne aeg.

677
00:31:56,019 --> 00:31:57,560
Me ei pea enam külgnevas massiivi.

678
00:31:57,560 --> 00:31:58,980
Meil ei ole muutmälu.

679
00:31:58,980 --> 00:32:00,710
Me ei saa kasutada nurksulg märke.

680
00:32:00,710 --> 00:32:04,590
Me sõna otseses mõttes pea kasutama samas loop
nagu ma kirjutasin hetk tagasi.

681
00:32:04,590 --> 00:32:09,740
Aga esmaspäeval, me väita, et suudame
libiseda tagasi rüppe efektiivsuse

682
00:32:09,740 --> 00:32:13,040
saavutada midagi, mis on
logaritmiline äkki, või parimal veel

683
00:32:13,040 --> 00:32:16,120
võibolla isegi midagi, mis on
nn konstantse ajaga.

684
00:32:16,120 --> 00:32:19,840
Niisiis, kuidas me saame teha, et kasutades neid uusi
tööriistad, nende aadressid, neid viiteid,

685
00:32:19,840 --> 00:32:22,210
ja väliskeermestamiseks asju meie enda?

686
00:32:22,210 --> 00:32:23,960
Noh, oletame, et
Siin need on kamp

687
00:32:23,960 --> 00:32:27,170
Numbrite et me tahame hoida oma
andmete struktuuri ja tõhusalt otsida.

688
00:32:27,170 --> 00:32:30,960
Saame absoluutselt tagasi kerida nädal
kaks, viska need massiivi,

689
00:32:30,960 --> 00:32:33,150
ja otsida neid kasutades binaarne otsing.

690
00:32:33,150 --> 00:32:34,040
Jaga ja valitse.

691
00:32:34,040 --> 00:32:37,720
Ja tegelikult sa kirjutasid
Kahendotsimine PSET3,

692
00:32:37,720 --> 00:32:40,100
kus sa ellu leid programmi.

693
00:32:40,100 --> 00:32:40,890
Aga tead mis.

694
00:32:40,890 --> 00:32:45,060
Seal on selline rohkem
nutikas viis seda teha.

695
00:32:45,060 --> 00:32:47,390
See on veidi rohkem
kogenud ja see võib-olla

696
00:32:47,390 --> 00:32:50,830
võimaldab meil mõista, miks binaarne
otsing on nii palju kiiremini.

697
00:32:50,830 --> 00:32:52,980
Esiteks, ärgem tutvustada
mõiste puu.

698
00:32:52,980 --> 00:32:54,730
Milline kuigi
Tegelikkuses puud liiki

699
00:32:54,730 --> 00:32:57,730
kasvada niimoodi, maailma arvuti
teaduse nad omamoodi kasvada allapoole

700
00:32:57,730 --> 00:33:00,830
nagu sugupuu, kus teil on
Sinu vanavanemad või vanavanemad

701
00:33:00,830 --> 00:33:04,580
või tühi-tähi tipus, patriarh ja
matriarh pere, vaid üks

702
00:33:04,580 --> 00:33:07,930
nn root, sõlm, alla
mis on tema lapsed,

703
00:33:07,930 --> 00:33:11,442
allpool, mis on oma laste või
tema järeltulijad üldisemalt.

704
00:33:11,442 --> 00:33:13,400
Ja keegi rippumas
põhja perekonna

705
00:33:13,400 --> 00:33:16,070
puu, peale selle
Noorim perekonnas,

706
00:33:16,070 --> 00:33:19,520
võib ka lihtsalt olla üldiselt
nimetatakse puu lehed.

707
00:33:19,520 --> 00:33:21,800
>> Nii et see on lihtsalt kamp
sõnad ja mõisted

708
00:33:21,800 --> 00:33:25,790
midagi nimega puu arvuti
teadust, palju nagu sugupuu.

709
00:33:25,790 --> 00:33:28,770
Aga seal on Kasvataja kehastused
puud, millest üks

710
00:33:28,770 --> 00:33:30,780
nimetatakse kahendotsingupuu.

711
00:33:30,780 --> 00:33:34,380
Ja saate mingi kraakleja
peale mida see asi teeb.

712
00:33:34,380 --> 00:33:37,180
Noh, see on binaarne mis mõttes?

713
00:33:37,180 --> 00:33:41,455
Kui ei binaarne tulevad siit?

714
00:33:41,455 --> 00:33:41,955
Vabandust?

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

716
00:33:45,961 --> 00:33:47,210
See ei ole niivõrd kas või.

717
00:33:47,210 --> 00:33:52,000
See on rohkem, et iga sõlm pole
rohkem kui kaks last, nagu me näeme siin.

718
00:33:52,000 --> 00:33:54,990
Üldiselt tree-- ja
Teie vanemad ja vanavanemad

719
00:33:54,990 --> 00:33:57,640
võib olla nii palju lapsi või
lapselast, kui nad tegelikult tahavad,

720
00:33:57,640 --> 00:34:00,820
ja nii näiteks on meil kolm
lapsed maha, et parem käsi sõlme,

721
00:34:00,820 --> 00:34:05,480
kuid Binääripuu sõlm on
null, üks või kaks last maksimaalselt.

722
00:34:05,480 --> 00:34:08,496
Ja see on tore omadus,
sest kui see ülempiir kahte,

723
00:34:08,496 --> 00:34:10,620
me ei kavatse olla võimeline
natuke Logi baasi kaks

724
00:34:10,620 --> 00:34:11,975
tegevus toimub siin lõpuks.

725
00:34:11,975 --> 00:34:13,350
Nii et meil on midagi logaritmiline.

726
00:34:13,350 --> 00:34:14,558
Aga rohkem sellest kohe.

727
00:34:14,558 --> 00:34:19,810
Otsi puu tähendab, et numbrid
paigutatud selliselt, et vasakul lapse

728
00:34:19,810 --> 00:34:22,429
väärtus on suurem kui juurestik.

729
00:34:22,429 --> 00:34:26,010
Ja selle õige laps
suurem kui juurestik.

730
00:34:26,010 --> 00:34:29,290
Teisisõnu, kui te võtate mõnda
sõlmed, ringid see pilt,

731
00:34:29,290 --> 00:34:31,840
ja vaatab vasakule
lapse ja tema õigust lapse,

732
00:34:31,840 --> 00:34:34,739
esimese peaks olema väiksem kui,
teine ​​peab olema suurem.

733
00:34:34,739 --> 00:34:36,159
Nii meelerahu vaadata 55.

734
00:34:36,159 --> 00:34:37,780
See on jäänud lapse 33.

735
00:34:37,780 --> 00:34:38,620
See on vähem kui.

736
00:34:38,620 --> 00:34:40,929
55, oma õigust laps on 77.

737
00:34:40,929 --> 00:34:41,783
See on suurem kui.

738
00:34:41,783 --> 00:34:43,199
Ja see on rekursiivne definitsioon.

739
00:34:43,199 --> 00:34:46,480
Võiksime vaadata iga üks neist
sõlmed ja sama mustrit hoiaks.

740
00:34:46,480 --> 00:34:49,389
>> Mis on tore on
kahendotsingupuu, on

741
00:34:49,389 --> 00:34:52,204
et üks, saame seda rakendada
koos struct, vaid niimoodi.

742
00:34:52,204 --> 00:34:54,620
Ja kuigi me viskamine
palju struktuure teie,

743
00:34:54,620 --> 00:34:56,560
Nad on pisut
intuitiivne nüüd loodetavasti.

744
00:34:56,560 --> 00:35:00,570
Süntaks on veel kauge kindel,
kuid sisu sõlme selles

745
00:35:00,570 --> 00:35:02,786
context-- ja hoiame
kasutades sõna sõlme,

746
00:35:02,786 --> 00:35:04,910
kas see on ristkülik
ekraanil või ring

747
00:35:04,910 --> 00:35:08,970
see on lihtsalt mõned üldised konteiner,
sel juhul puu, nagu üks

748
00:35:08,970 --> 00:35:11,780
nägime, peame täisarv
Iga sõlmede

749
00:35:11,780 --> 00:35:15,460
ja siis ma pean kaks osuti osutab
vasakule laps ja õigus lapsega,

750
00:35:15,460 --> 00:35:16,590
võrra.

751
00:35:16,590 --> 00:35:20,730
Nii et see, kuidas me võiksime
rakendada, et oma struktuure.

752
00:35:20,730 --> 00:35:22,315
Ja kuidas võiks ma rakendab seda koodi?

753
00:35:22,315 --> 00:35:26,730
Noh, võtame kiire
vaadata selle väikese näite.

754
00:35:26,730 --> 00:35:29,820
See ei ole funktsionaalne, kuid ma olen
kopeerida ja kleepida, et struktuur.

755
00:35:29,820 --> 00:35:33,510
Ja kui minu funktsioon binaarne
search tree nimetatakse otsingumootori,

756
00:35:33,510 --> 00:35:36,980
ja see võtab kaks argumenti,
täisarv N ja osuti

757
00:35:36,980 --> 00:35:41,400
et sõlm, nii et kursor puu
või kursor puu juurt,

758
00:35:41,400 --> 00:35:43,482
kuidas ma minna otsima N?

759
00:35:43,482 --> 00:35:45,440
Noh, esiteks sellepärast, et ma olen
tegelevad suunanäitajaks,

760
00:35:45,440 --> 00:35:46,750
Ma lähen tegema meelerahu kontrolli.

761
00:35:46,750 --> 00:35:54,279
Kui puu võrdsete võrdne null, on N
Selles puu või mitte see puu?

762
00:35:54,279 --> 00:35:55,070
See ei saa olla, eks?

763
00:35:55,070 --> 00:35:56,870
Kui ma olen varem null,
seal on midagi seal.

764
00:35:56,870 --> 00:35:59,230
Ma võin ka lihtsalt
pimesi öelda tagasi vale.

765
00:35:59,230 --> 00:36:04,050
Kui sa annad mulle midagi, ma kindlasti ei saa
leia arv N. Mida veel võiks ma

766
00:36:04,050 --> 00:36:04,750
vaadake nüüd?

767
00:36:04,750 --> 00:36:12,830
Ma ütlen ka mujal kui N on
väiksem kui iganes on puu sõlme

768
00:36:12,830 --> 00:36:16,300
et olen kätte N väärtust.

769
00:36:16,300 --> 00:36:20,270
Teisisõnu, kui number Kõht
otsivad, N, on väiksem kui sõlm

770
00:36:20,270 --> 00:36:21,340
et ma vaatan.

771
00:36:21,340 --> 00:36:23,190
Ja sõlme Otsin
kell nimetatakse puu,

772
00:36:23,190 --> 00:36:26,370
ja meenutada eelmise näiteks
saada on väärtus osuti,

773
00:36:26,370 --> 00:36:28,310
Ma kasutan noolt märke.

774
00:36:28,310 --> 00:36:35,960
Nii et kui N on väiksem kui puu nool
N, ma tahan kontseptuaalselt minna vasakule.

775
00:36:35,960 --> 00:36:38,590
Kuidas ma väljendan otsinguks jäänud?

776
00:36:38,590 --> 00:36:41,560
Et asi oleks selge, kui see on
Pilti küsimus,

777
00:36:41,560 --> 00:36:44,612
ja ma olen läbinud selle tipmine
nool, mis on suunaga allapoole.

778
00:36:44,612 --> 00:36:45,570
See on minu puu pointer.

779
00:36:45,570 --> 00:36:48,060
Ma osutades puu juur.

780
00:36:48,060 --> 00:36:52,100
Ja ma otsin ütleme,
arvu 44, suvaliselt.

781
00:36:52,100 --> 00:36:55,300
Kas 44 või väiksem
suurem kui 55 ilmselt?

782
00:36:55,300 --> 00:36:56,360
Nii et see on väiksem kui.

783
00:36:56,360 --> 00:36:58,760
Ja nii see, kui tingimus kehtib.

784
00:36:58,760 --> 00:37:03,981
Nii kontseptuaalselt, mida ma tahan
otsi kõrval, kui ma otsin 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Täpselt, ma tahan
otsi vasakul laps,

788
00:37:11,100 --> 00:37:12,789
või vasakule sub-tree of this picture.

789
00:37:12,789 --> 00:37:14,830
Ja tegelikult, las ma läbi
pilt siin

790
00:37:14,830 --> 00:37:17,770
hetkeks, kuna
Ma ei kriimusta seda.

791
00:37:17,770 --> 00:37:21,150
Kui ma hakkan siin on 55, ja
Ma tean, et väärtus 44

792
00:37:21,150 --> 00:37:23,180
Otsin on
vasakul, see on selline

793
00:37:23,180 --> 00:37:26,010
ja nagu pisaravool telefoniraamat
poole või pisaravool puu pooleks.

794
00:37:26,010 --> 00:37:29,660
Ma ei pea enam hooli
kogu see pool puud.

795
00:37:29,660 --> 00:37:33,270
Ja veel, uudishimulikult poolest
struktuuri, et see asi siin, et

796
00:37:33,270 --> 00:37:36,682
algab 33, et ise
on kahendotsingupuu.

797
00:37:36,682 --> 00:37:39,890
Ma ütlesin sõna kirjutan enne, sest
tõepoolest see on andmestruktuur, et

798
00:37:39,890 --> 00:37:41,707
definitsiooni järgi on rekursiivne.

799
00:37:41,707 --> 00:37:44,540
Sul võib olla puu, mis on selle
suur, kuid igaüks oma lastele

800
00:37:44,540 --> 00:37:46,870
kujutab endast puu vaid veidi väiksem.

801
00:37:46,870 --> 00:37:50,910
Selle asemel, et oleks vanaisa
või vanaema, nüüd on see lihtsalt ema

802
00:37:50,910 --> 00:37:54,300
või-- ma ei saa say-- ole ema
või isa, et oleks imelik.

803
00:37:54,300 --> 00:37:59,000
Selle asemel kaks last olemas
Oleks nagu vend ja õde-vend.

804
00:37:59,000 --> 00:38:01,120
Uue põlvkonna sugupuu.

805
00:38:01,120 --> 00:38:02,900
Aga struktuurilt, see on sama mõte.

806
00:38:02,900 --> 00:38:06,790
Ja selgub, mul on funktsioon
mida ma otsida binaarne otsing

807
00:38:06,790 --> 00:38:07,290
puu.

808
00:38:07,290 --> 00:38:08,680
Seda nimetatakse otsing.

809
00:38:08,680 --> 00:38:17,870
Ma otsin N puude nool vasakule
else if N on suurem kui väärtus

810
00:38:17,870 --> 00:38:18,870
et ma olen praegu.

811
00:38:18,870 --> 00:38:20,800
55 lugu hetk tagasi.

812
00:38:20,800 --> 00:38:23,780
Mul on funktsioon nimega
otsing, et ma ei saa lihtsalt

813
00:38:23,780 --> 00:38:29,660
edasi N sellele ja rekursiivselt otsida
sub-tree ja lihtsalt tagasi

814
00:38:29,660 --> 00:38:30,620
mida iganes see vastus.

815
00:38:30,620 --> 00:38:33,530
Else Mul on mõned lõplik alus asjas.

816
00:38:33,530 --> 00:38:35,310
>> Mis on viimane juhtum?

817
00:38:35,310 --> 00:38:36,570
Tree on kas null.

818
00:38:36,570 --> 00:38:39,980
Väärtus ma kas otsin on
vähem kui see suurema või sellega

819
00:38:39,980 --> 00:38:42,610
või sellega võrdne.

820
00:38:42,610 --> 00:38:44,750
Ja ma võiks öelda, mis võrdub
võrdsed, kuid loogiliselt on

821
00:38:44,750 --> 00:38:46,500
võrdub lihtsalt öeldes teine ​​siin.

822
00:38:46,500 --> 00:38:49,150
Nii tõsi on see, kuidas ma leian midagi.

823
00:38:49,150 --> 00:38:51,710
Loodetavasti on see
süveneb veelgi, näiteks

824
00:38:51,710 --> 00:38:54,900
kui loll sigma funktsiooni
tegime mõned loengud tagasi,

825
00:38:54,900 --> 00:38:58,360
kus see oli lihtsalt nii lihtne kasutada loop
loendada üles kõik numbrid ühest

826
00:38:58,360 --> 00:39:02,390
N. Siin koos andmestruktuur
mis iseenesest on rekursiivselt

827
00:39:02,390 --> 00:39:07,050
määratletud ja rekursiivselt tõmmatud, nüüd
on suutlikkus väljendada ennast

828
00:39:07,050 --> 00:39:09,780
koodi, mis iseenesest on rekursiivne.

829
00:39:09,780 --> 00:39:12,580
Nii et see on täpselt sama koodi siin.

830
00:39:12,580 --> 00:39:14,400
>> Mis siis muud probleemid saame lahendada?

831
00:39:14,400 --> 00:39:18,160
Nii kiire sammu kaugusel
puud hetkeks.

832
00:39:18,160 --> 00:39:20,130
Siin on, ütleme, Saksa lipp.

833
00:39:20,130 --> 00:39:22,020
Ja seal on selgelt
muster see lipp.

834
00:39:22,020 --> 00:39:23,811
Ja seal on palju
lipud maailmas, mis

835
00:39:23,811 --> 00:39:27,560
on nii lihtne kui see nii
oma värvid ja mustrid.

836
00:39:27,560 --> 00:39:31,930
Aga oletame, et see on salvestatud kui
GIF või JPEG või bitmap või ping,

837
00:39:31,930 --> 00:39:34,240
graafiline failiformaat
millega te olete juba tuttav,

838
00:39:34,240 --> 00:39:36,460
millest mõned oleme
mängides in PSET4.

839
00:39:36,460 --> 00:39:41,550
See ei tundu mõttekas salvestada
must piksel, must piksel, must piksel

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, terve hunnik
musti piksleid esimest scanline,

841
00:39:44,790 --> 00:39:47,430
või rida, siis terve hunnik
sama, siis terve hunnik

842
00:39:47,430 --> 00:39:49,530
sama, ja seejärel
terve hunnik punane pikslit,

843
00:39:49,530 --> 00:39:53,020
punane pikslit, punane pikslit, siis kogu
kamp kollane pikslit, kollane, eks?

844
00:39:53,020 --> 00:39:55,050
>> Seal on selline ebaefektiivsus siin.

845
00:39:55,050 --> 00:39:59,040
Kuidas teile intuitiivselt
suruma Saksa lipu

846
00:39:59,040 --> 00:40:01,320
kui rakendada seda faili?

847
00:40:01,320 --> 00:40:04,940
Nagu millist teavet me ei saa
viitsinud salvestamine kettale, et

848
00:40:04,940 --> 00:40:08,040
vähendada meie faili suurus, nagu
megabaidi et kilobait, midagi

849
00:40:08,040 --> 00:40:09,430
väiksem?

850
00:40:09,430 --> 00:40:13,130
Kus asub koondamise
siin on selge?

851
00:40:13,130 --> 00:40:13,880
Mis võiks teha?

852
00:40:13,880 --> 00:40:14,380
Jah?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Täpselt.

855
00:40:21,970 --> 00:40:24,550
Miks mitte pigem mäletan
värvi iga darn piksli

856
00:40:24,550 --> 00:40:28,200
nagu sa teed PSET4
koos bitmap faili formaadis

857
00:40:28,200 --> 00:40:32,060
miks sa lihtsalt ei esinda
vasakpoolsel veerul pikslit, näiteks

858
00:40:32,060 --> 00:40:35,370
hunnik musti piksleid, kamp
punane, ja hunnik kollane,

859
00:40:35,370 --> 00:40:39,210
ja siis lihtsalt kuidagi kodeerida
Idee korrata seda 100 korda

860
00:40:39,210 --> 00:40:41,020
või korrake seda 1000 korda?

861
00:40:41,020 --> 00:40:43,430
Kus 100 või 1000 on
lihtsalt täisarv, siis

862
00:40:43,430 --> 00:40:47,290
pääse ainult üks number
asemel sadu või tuhandeid

863
00:40:47,290 --> 00:40:48,270
Täiendavate pikslit.

864
00:40:48,270 --> 00:40:50,990
Ja tõepoolest, see, kuidas me
võiks tihendada Saksa lipu.

865
00:40:50,990 --> 00:40:51,490
Ja

866
00:40:51,490 --> 00:40:53,470
Mida aga Prantsuse lipu?

867
00:40:53,470 --> 00:40:58,930
Ja natuke mingisugune
vaimne harjutus, mis lipu

868
00:40:58,930 --> 00:41:01,040
saab kokkusurutud rohkem kettal?

869
00:41:01,040 --> 00:41:05,720
Saksa lipu või Prantsuse
lipp, kui me võtame seda lähenemist?

870
00:41:05,720 --> 00:41:08,490
Saksa lipu, sest seal on
rohkem horisontaalne koondamine.

871
00:41:08,490 --> 00:41:12,190
Ja disain, paljud graafilise faili
formaate tõepoolest töötavad rastrijoont

872
00:41:12,190 --> 00:41:12,830
horisontaalselt.

873
00:41:12,830 --> 00:41:14,674
Nad võiksid teha
vertikaalselt, vaid inimkonna

874
00:41:14,674 --> 00:41:17,090
otsustas aastat tagasi, et me tulen
Üldiselt arvan, et asjad reas

875
00:41:17,090 --> 00:41:18,880
realt, mitte kolonni kolonni.

876
00:41:18,880 --> 00:41:20,820
Nii tõesti kui sa olid
et vaadata faili

877
00:41:20,820 --> 00:41:24,670
suurus Saksa lipp ja Prantsuse
lipp, nii kaua, kui resolutsioon on

878
00:41:24,670 --> 00:41:27,530
Samal, sama laiusega
ja kõrgus, see üks

879
00:41:27,530 --> 00:41:31,580
siin saab olema suurem, sest sa
kordama ennast kolm korda.

880
00:41:31,580 --> 00:41:35,570
Pead määrama sinine, korrake
ise, valge, kordan ennast, punane,

881
00:41:35,570 --> 00:41:36,740
kordama ennast.

882
00:41:36,740 --> 00:41:39,000
Sa ei saa lihtsalt minna kõik
kuidas paremale.

883
00:41:39,000 --> 00:41:41,200
Ja kui kõrvale, teha
selge compression

884
00:41:41,200 --> 00:41:43,910
on kõikjal, isegi kui need on
Nelja kaadreid video-- sa

885
00:41:43,910 --> 00:41:45,890
võiks meenutada, et filmi
või video üldiselt

886
00:41:45,890 --> 00:41:47,286
nagu 29 või 30 kaadrit sekundis.

887
00:41:47,286 --> 00:41:50,410
See on nagu väike flip raamat, kus te
lihtsalt näha, pilt, pilt, pilt,

888
00:41:50,410 --> 00:41:54,410
pilt lihtsalt super kiire, et see näeb välja nagu
näitlejad ekraanil liiguvad.

889
00:41:54,410 --> 00:41:57,130
Siin on kimalaste kohta
peal kimp lilli.

890
00:41:57,130 --> 00:41:59,790
Ja kuigi see võib olla mingi
raske näha esmapilgul

891
00:41:59,790 --> 00:42:04,020
Ainuke asi liigub
Selles filmis on bee.

892
00:42:04,020 --> 00:42:06,880
>> Mis on loll säilitan
video pakkida?

893
00:42:06,880 --> 00:42:11,420
See on selline raiskamine salvestada video
neli peaaegu identsed pildid,

894
00:42:11,420 --> 00:42:13,670
erinevad ainult niivõrd, kuivõrd kus bee on.

895
00:42:13,670 --> 00:42:16,280
Võite visata kõige
Selle info

896
00:42:16,280 --> 00:42:20,190
ja mäletan ainult, näiteks,
esimese kaadri ja viimane kaader,

897
00:42:20,190 --> 00:42:22,180
võti raamid, kui olete
kunagi kuulnud sõna,

898
00:42:22,180 --> 00:42:24,337
ja lihtsalt salvestada ka
keskel, kui mesilane on.

899
00:42:24,337 --> 00:42:26,170
Ja sa ei pea
salvestada kõik roosa,

900
00:42:26,170 --> 00:42:28,330
ja sinine, ja
roheline väärtuste samuti.

901
00:42:28,330 --> 00:42:31,200
Nii et see on ainult öelda, et
compression on kõikjal.

902
00:42:31,200 --> 00:42:34,900
See on meetod, mida me sageli kasutada
või enesestmõistetavaks nendel päevadel.

903
00:42:34,900 --> 00:42:38,750
>> Aga kuidas sa suruma teksti?

904
00:42:38,750 --> 00:42:40,450
Kuidas minna umbes kokkusurumise teksti?

905
00:42:40,450 --> 00:42:45,410
Noh, iga tähemärki
Ascii on üks bait, või kaheksa bitti.

906
00:42:45,410 --> 00:42:47,360
Ja see on selline loll, eks?

907
00:42:47,360 --> 00:42:51,160
Kuna sa ilmselt tüüpi
ja E ja I ja O ja U palju

908
00:42:51,160 --> 00:42:55,270
sagedamini kui näiteks W või Q või Z,
Sõltuvalt keelest, milles

909
00:42:55,270 --> 00:42:56,610
sa oled kirjalikult kindlasti.

910
00:42:56,610 --> 00:42:59,600
Ja miks me kasutame
kaheksa bitti iga kirja,

911
00:42:59,600 --> 00:43:02,040
sealhulgas vähemalt
Populaarseim tähed, eks?

912
00:43:02,040 --> 00:43:05,300
Miks mitte kasutada vähem bitti jaoks
super populaarne tähed,

913
00:43:05,300 --> 00:43:07,760
nagu E, mida sa vist
esimene Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
ja kasutada rohkem bitte eest
vähem populaarne tähed?

915
00:43:10,450 --> 00:43:10,950
Miks?

916
00:43:10,950 --> 00:43:13,130
Sest me lihtsalt läheb
neid kasutada harvem.

917
00:43:13,130 --> 00:43:15,838
>> Noh, tuleb välja, et seal on
püütud teha seda teha.

918
00:43:15,838 --> 00:43:18,630
Ja kui te mäletate hinne
kooli või gümnaasiumi Morse koodi.

919
00:43:18,630 --> 00:43:20,400
Morse kood on dots
ja kriipsud, mis võib olla

920
00:43:20,400 --> 00:43:24,270
edastatakse mööda traadist
Kõlab või signaalid mingi.

921
00:43:24,270 --> 00:43:25,930
Aga Morse kood on super puhas.

922
00:43:25,930 --> 00:43:29,010
See on selline binaarne süsteem
et teil on punktid või kriipsud.

923
00:43:29,010 --> 00:43:30,977
Aga kui sa näed, näiteks kaks punkti.

924
00:43:30,977 --> 00:43:33,810
Või kui te arvate tagasi operaatori
kes läheb nagu PIIKSUD, piiks,

925
00:43:33,810 --> 00:43:36,760
piiksu, lööb natuke vallandada
mis edastab signaali,

926
00:43:36,760 --> 00:43:40,360
kui sa, saaja, saab kaks
täpid, mis sõnumi olete saanud?

927
00:43:40,360 --> 00:43:43,490
Täiesti meelevaldne.

928
00:43:43,490 --> 00:43:44,450
>> Ma?

929
00:43:44,450 --> 00:43:45,060
Ma?

930
00:43:45,060 --> 00:43:47,500
Või mis about-- või olen?

931
00:43:47,500 --> 00:43:49,570
Võib-olla oli see lihtsalt kaks E õigust?

932
00:43:49,570 --> 00:43:52,480
Nii et see probleem
of decodability Morse

933
00:43:52,480 --> 00:43:54,890
kood, mille kohaselt juhul, kui
isik saadan sulle sõnumi

934
00:43:54,890 --> 00:43:59,510
tegelikult peatab nii saate sortida kohta
näha ega kuulda lõhed tähed,

935
00:43:59,510 --> 00:44:02,990
see ei ole piisav lihtsalt
Kirjuta oja ühtede ja nullide,

936
00:44:02,990 --> 00:44:05,610
või punktid ja kriipsud,
sest seal on ebaselgus.

937
00:44:05,610 --> 00:44:08,640
E on ühe dot, nii et kui sa
vaata kaks punkti või kuulda kaks punkti,

938
00:44:08,640 --> 00:44:11,254
võibolla on kaks E-või äkki see on üks I.

939
00:44:11,254 --> 00:44:13,670
Seega on meil vaja süsteemi, mis on
natuke targem kui see.

940
00:44:13,670 --> 00:44:16,851
Nii mees nimega Huffman aastat
tagasi tulid just seda.

941
00:44:16,851 --> 00:44:18,600
Nii et me lihtsalt läheb
võtta kiire pilgu

942
00:44:18,600 --> 00:44:20,114
kuidas puud Sobiv seda.

943
00:44:20,114 --> 00:44:22,530
Oletatakse, et see on mingi
loll sõnum, mida soovite saata,

944
00:44:22,530 --> 00:44:26,342
koosneb ainult A, B, C on D's ja E-ndatel,
kuid seal on palju koondamise siin.

945
00:44:26,342 --> 00:44:27,550
See ei ole mõeldud olema inglise keeles.

946
00:44:27,550 --> 00:44:28,341
See ei ole krüpteeritud.

947
00:44:28,341 --> 00:44:30,540
See on lihtsalt loll sõnum
palju kordusi.

948
00:44:30,540 --> 00:44:34,010
Nii et kui sa tegelikult loota läbi kõik
A, B, C-ndatel, D's ja E-ndatel, siin on

949
00:44:34,010 --> 00:44:34,890
sagedust.

950
00:44:34,890 --> 00:44:37,800
20% tähed
A, 45% tähed

951
00:44:37,800 --> 00:44:39,660
on E-ndatel ja kolm muud sagedused.

952
00:44:39,660 --> 00:44:41,960
Meil arvestatakse seal käsitsi
ja just tegin matemaatikat.

953
00:44:41,960 --> 00:44:44,579
>> Nii selgub, et
Huffman, mõni aeg tagasi,

954
00:44:44,579 --> 00:44:46,620
mõistsin, et sa tead
mis, kui ma hakkan hoone

955
00:44:46,620 --> 00:44:51,172
puu või metsa puid, kui soovite,
järgmine, mida ma teha saan järgmine.

956
00:44:51,172 --> 00:44:53,880
Ma annan sõlme igale
Tähtede et ma hoolin

957
00:44:53,880 --> 00:44:55,530
ja ma lähen hoida
sees, et sõlm

958
00:44:55,530 --> 00:44:58,610
sagedusi ujukoma
väärtus, või sa võiksid kasutada seda N Ka

959
00:44:58,610 --> 00:45:00,210
aga me lihtsalt kasutada float siin.

960
00:45:00,210 --> 00:45:03,100
Ja algoritmi, mis
tegi ta ettepaneku, et teil

961
00:45:03,100 --> 00:45:07,210
seda metsa ühe sõlme
puud, nii super lühike puud,

962
00:45:07,210 --> 00:45:11,920
ja sa alustada ühendavad neid
uued rühmad, uued vanemad, kui soovite.

963
00:45:11,920 --> 00:45:16,150
Ja sa seda valides
kaks väikseimat sagedustel korraga.

964
00:45:16,150 --> 00:45:18,110
Nii ma võtsin 10% ja 10%.

965
00:45:18,110 --> 00:45:19,090
Teen uue sõlme.

966
00:45:19,090 --> 00:45:20,910
Ja ma nimetan uus sõlm 20%.

967
00:45:20,910 --> 00:45:22,750
>> Millised kaks sõlmede ma ühendada edasi?

968
00:45:22,750 --> 00:45:23,810
See on veidi ebamäärane.

969
00:45:23,810 --> 00:45:26,643
Nii et mõnes nurgas juhtudel
kaaluda, kuid hoida asjad päris,

970
00:45:26,643 --> 00:45:29,300
Ma lähen valima 20% -
Ma nüüd ignoreerida lapsi.

971
00:45:29,300 --> 00:45:33,640
Ma lähen valima 20% ja
15% ja juhtida kaks uut servi.

972
00:45:33,640 --> 00:45:35,624
Ja nüüd, kus kaks sõlmede
ma loogiliselt ühendada?

973
00:45:35,624 --> 00:45:38,540
Ignoreeri kõiki lapsi, kõiki
lapselapsed, lihtsalt pilk juured

974
00:45:38,540 --> 00:45:39,070
nüüd.

975
00:45:39,070 --> 00:45:42,220
Millised kaks sõlmede ma lips koos?

976
00:45:42,220 --> 00:45:44,530
Point kaks ja 0.35.

977
00:45:44,530 --> 00:45:45,890
Ma joonistan kaks uut servi.

978
00:45:45,890 --> 00:45:47,570
Ja siis ma sain ainult üks vasakule.

979
00:45:47,570 --> 00:45:48,650
Nii et siin on puu.

980
00:45:48,650 --> 00:45:51,160
Ja see on välja töötatud teadlikult
otsida selline ilus,

981
00:45:51,160 --> 00:45:55,870
kuid teade, et servad on
Samuti on märgistatud null ja üks.

982
00:45:55,870 --> 00:45:59,510
Nii on kõik lahkunud servad on null
suvaliselt, kuid järjekindlalt.

983
00:45:59,510 --> 00:46:01,170
Kõik õige servad on ones.

984
00:46:01,170 --> 00:46:05,070
>> Ja mis siis Hoffman kavandatud tähendab,
kui sa tahad esindada B,

985
00:46:05,070 --> 00:46:10,080
mitte esindama arvu 66 kui
ASCII mis on kaheksa kogu bitti,

986
00:46:10,080 --> 00:46:13,360
sa tead, mida, vaid poest
muster null, null, null,

987
00:46:13,360 --> 00:46:17,030
null, sest see on tee
minu puu, hr Huffman puu,

988
00:46:17,030 --> 00:46:18,600
lehestiku juurest.

989
00:46:18,600 --> 00:46:20,970
Kui soovite salvestada
E seevastu ei

990
00:46:20,970 --> 00:46:26,290
Kirjuta kaheksa bitti, mis kujutavad endast E.
Selle asemel, Kirjuta, mida muster bitti?

991
00:46:26,290 --> 00:46:26,890
Üks.

992
00:46:26,890 --> 00:46:30,410
Ja mis tore on see
et E on kõige populaarsem kirja,

993
00:46:30,410 --> 00:46:32,340
ja te kasutate
lühim koodi.

994
00:46:32,340 --> 00:46:34,090
Järgmine populaarsemaid
kiri välja näeb ta

995
00:46:34,090 --> 00:46:37,380
oli A. Ja nii mitu bitti
ta ettepaneku kasutada on?

996
00:46:37,380 --> 00:46:38,270
Zero, üks.

997
00:46:38,270 --> 00:46:41,060
>> Ja kuna see on rakendatud
kui see puu, nüüd

998
00:46:41,060 --> 00:46:43,350
andke mulle ette näha pole
kahemõttelisust nagu Morse

999
00:46:43,350 --> 00:46:46,090
koodi, sest kõik
Tähtede sa hoolid

1000
00:46:46,090 --> 00:46:48,780
lõpus on nende servad.

1001
00:46:48,780 --> 00:46:50,580
Nii see on lihtsalt üks
kohaldamise puu.

1002
00:46:50,580 --> 00:46:52,538
See on-- ja ma lehvitada
minu käsi selles, kuidas

1003
00:46:52,538 --> 00:46:55,570
võiks rakendada seda kui C struktuur.

1004
00:46:55,570 --> 00:46:58,260
Meil on vaja ainult ühendada
sümbol, nagu paalia,

1005
00:46:58,260 --> 00:46:59,910
ja sagedus vasakule ja paremale.

1006
00:46:59,910 --> 00:47:02,510
Aga vaatame kaks
lõplik näiteid, et teil

1007
00:47:02,510 --> 00:47:06,070
saada üsna tuttav pärast
viktoriin null probleemi seatud viis.

1008
00:47:06,070 --> 00:47:09,210
>> Nii on andmestruktuur
tuntud kui hash tabelit.

1009
00:47:09,210 --> 00:47:12,247
Ja hash tabelis on omamoodi
jahtuda, et sellel on kopad.

1010
00:47:12,247 --> 00:47:14,830
Ja oletame seal neli ämbrid
siin, vaid nelja tühikuid.

1011
00:47:14,830 --> 00:47:20,830
Siin on kaardipakk, ja siin on
klubi, labidas, klubi, teemandid, klubi,

1012
00:47:20,830 --> 00:47:25,960
teemandid, klubi, teemandid,
clubs-- nii et see on juhuslik.

1013
00:47:25,960 --> 00:47:30,330
Hearts, hearts--, et ma olen
bucketizing kõik sisendid siin.

1014
00:47:30,330 --> 00:47:32,430
Ja hash tabelis vajadustele
vaadata oma panus,

1015
00:47:32,430 --> 00:47:34,850
ja siis pane see teatud
paigutada selle põhjal, mida sa näed.

1016
00:47:34,850 --> 00:47:35,600
See algoritm.

1017
00:47:35,600 --> 00:47:37,980
Ja ma olin kasutades super
lihtsaid visuaalseid algoritm.

1018
00:47:37,980 --> 00:47:40,030
Kõige raskem osa, mis oli
mäleta, mida pildid olid.

1019
00:47:40,030 --> 00:47:41,590
Ja siis on neli kokku asju.

1020
00:47:41,590 --> 00:47:45,440
>> Nüüd korstnad kasvasid, mis
Messil disain asi siin.

1021
00:47:45,440 --> 00:47:46,540
Aga mida veel võiks teha?

1022
00:47:46,540 --> 00:47:49,080
Nii tegelikult on meil siin
hunnik vana kooli eksam raamatuid.

1023
00:47:49,080 --> 00:47:51,240
Oletame, et kamp
õpilaste nimed on siin.

1024
00:47:51,240 --> 00:47:52,570
Siin on suurem hash tabelit.

1025
00:47:52,570 --> 00:47:54,867
Selle asemel, et neli ämbrid,
Olen oletame 26.

1026
00:47:54,867 --> 00:47:57,950
Ja me ei taha minna laenata 26
asju väljastpoolt [? Annenberg?], Et

1027
00:47:57,950 --> 00:48:00,289
Siin on viis, mis esindavad
A-Z. Ja kui ma

1028
00:48:00,289 --> 00:48:03,580
vaata õpilane, kelle nimi algab A,
Ma panen tema mängust on.

1029
00:48:03,580 --> 00:48:08,850
Kui keegi hakkab koos C, seal,
A-- tegelikult ei tahtnud seda teha.

1030
00:48:08,850 --> 00:48:10,060
B läheb siia.

1031
00:48:10,060 --> 00:48:13,390
Nii et ma sain A ja B ja C ning
Nüüd siin on veel üks õpilane.

1032
00:48:13,390 --> 00:48:16,212
Aga kui see hash tabelis on
rakendatakse array,

1033
00:48:16,212 --> 00:48:17,920
Ma olen selline kruvitud
Sel hetkel, eks?

1034
00:48:17,920 --> 00:48:19,510
Ma nagu vaja panna see kuhugi.

1035
00:48:19,510 --> 00:48:24,380
>> Nii et üks viis, kuidas ma lahendada see kõik
õige, A on hõivatud, B on hõivatud, C on hõivatud.

1036
00:48:24,380 --> 00:48:28,880
Ma panen ta D. Nii et
Esimene, mul juhuslikult vahetu juurdepääs

1037
00:48:28,880 --> 00:48:31,064
et iga kopad õpilastele.

1038
00:48:31,064 --> 00:48:33,230
Aga nüüd on selline detsentraliseeritud
millekski lineaarne,

1039
00:48:33,230 --> 00:48:36,750
sest kui ma tahan otsida keegi
kelle nimi algab A, ma kontrollin siin.

1040
00:48:36,750 --> 00:48:38,854
Aga kui see ei ole A
õpilase Otsin,

1041
00:48:38,854 --> 00:48:41,520
Ma nagu on alustada kontrollides
ämbrid, sest see, mida ma tegin

1042
00:48:41,520 --> 00:48:44,530
oli omamoodi lineaarselt
sond andmestruktuuri.

1043
00:48:44,530 --> 00:48:47,710
Rumal viis öelda lihtsalt vaadata
Esimest saadaval avamine,

1044
00:48:47,710 --> 00:48:51,850
ja panna kui plaan B, kui nii võib öelda,
või plaani D sel juhul, väärtus

1045
00:48:51,850 --> 00:48:53,340
selles kohas asemel.

1046
00:48:53,340 --> 00:48:56,470
See on lihtsalt nii, et kui olete
sain 26 kohas ja no õpilased

1047
00:48:56,470 --> 00:49:00,600
nimega Q või Z, või midagi sellist
et vähemalt te kasutate ruumi.

1048
00:49:00,600 --> 00:49:03,140
>> Aga me oleme juba näinud rohkem
targad lahendused siin, eks?

1049
00:49:03,140 --> 00:49:04,870
Mida sa teeksid, selle asemel
Kui teil on kokkupõrge?

1050
00:49:04,870 --> 00:49:06,670
Kui kaks inimest on
nimi A, mida oleks

1051
00:49:06,670 --> 00:49:09,160
on targemaks või rohkem
intuitiivne lahendus kui lihtsalt

1052
00:49:09,160 --> 00:49:12,840
Haara kus D peaks olema?

1053
00:49:12,840 --> 00:49:14,810
Miks ma just ei lähe
väljaspool [? Annenberg?]

1054
00:49:14,810 --> 00:49:19,960
nagu malloc, teise sõlme, pane see
siin, ja seejärel panna, et õpilane siin.

1055
00:49:19,960 --> 00:49:22,120
Nii et ma sisuliselt on
mingi hulga,

1056
00:49:22,120 --> 00:49:25,590
või äkki rohkem elegantselt nagu me oleme
hakanud näha ahelloend.

1057
00:49:25,590 --> 00:49:29,520
>> Ja nii räsi tabelis on struktuur
et võiks vaadata nagu see,

1058
00:49:29,520 --> 00:49:33,900
kuid nutikalt, sa midagi, mida nimetatakse
Eraldi ühendamine, millega hash tabelis

1059
00:49:33,900 --> 00:49:38,340
lihtsalt on massiiv, iga
mille elemendid ei ole number,

1060
00:49:38,340 --> 00:49:40,470
ise on seotud nimekirja.

1061
00:49:40,470 --> 00:49:45,080
Nii et sa saad super kiire juurdepääsu
otsustama, kus räsi oma väärtust.

1062
00:49:45,080 --> 00:49:48,059
Sarnaselt kaarte, näiteks
Tegin super kiireid otsuseid.

1063
00:49:48,059 --> 00:49:49,600
Hearts läheb siia, teemandid läheb siia.

1064
00:49:49,600 --> 00:49:52,180
Sama siin A läheb siin
D läheb siia, B läheb siia.

1065
00:49:52,180 --> 00:49:55,740
Nii super kiire pilk-ups, ja kui
juhtub, et joosta juhul

1066
00:49:55,740 --> 00:49:59,429
kus sul kokkupõrkeid, kaks
inimesed, kellel on sama nimi, samuti siis

1067
00:49:59,429 --> 00:50:00,970
sa lihtsalt alustada nende ühendamise.

1068
00:50:00,970 --> 00:50:03,900
Ja äkki sa hoida neid järjestatud
tähestiku, võibolla mitte.

1069
00:50:03,900 --> 00:50:05,900
Aga vähemalt nüüd on dünaamikat.

1070
00:50:05,900 --> 00:50:10,250
Nii et ühelt poolt on meil super kiire
konstantset aega, ja selline lineaarne aeg

1071
00:50:10,250 --> 00:50:14,110
seotud, kui need on seotud nimekirjad
hakkama saada veidi pikk.

1072
00:50:14,110 --> 00:50:16,880
>> Nii selline rumal,
geeky nali aastat tagasi.

1073
00:50:16,880 --> 00:50:19,590
Kell CS50 hack-a-Thon,
kui õpilased kontrollida,

1074
00:50:19,590 --> 00:50:22,040
mõned TF või CA igal aastal
arvab, et see on naljakas, et panna

1075
00:50:22,040 --> 00:50:27,772
märk, nagu see, kus ta lihtsalt
tähendab, et kui su nimi algab A,

1076
00:50:27,772 --> 00:50:28,870
minna seda teed.

1077
00:50:28,870 --> 00:50:31,110
Kui teie nimi algab
B-, minna see-- OK,

1078
00:50:31,110 --> 00:50:33,290
see on naljakas võibolla hiljem poolaastal.

1079
00:50:33,290 --> 00:50:36,420
Aga seal on veel
viis seda teha ka.

1080
00:50:36,420 --> 00:50:37,410
Tule tagasi, et.

1081
00:50:37,410 --> 00:50:38,600
>> Nii et see struktuur.

1082
00:50:38,600 --> 00:50:40,420
Ja see on meie viimane
struktuuri täna

1083
00:50:40,420 --> 00:50:42,400
mis on midagi, mida nimetatakse Prefiksipuu.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, mis mingil põhjusel on lühike
otsinguks, kuid seda nimetatakse Prefiksipuu.

1085
00:50:47,140 --> 00:50:51,389
Nii Prefiksipuu on veel üks huvitav
sulam palju neid ideid.

1086
00:50:51,389 --> 00:50:52,930
See on puu, mis me oleme näinud.

1087
00:50:52,930 --> 00:50:54,180
See ei ole kahendotsingupuu.

1088
00:50:54,180 --> 00:50:58,410
See on puu tahes laste arvu,
kuid iga lastega Prefiksipuu

1089
00:50:58,410 --> 00:51:00,090
on massiiv.

1090
00:51:00,090 --> 00:51:04,790
Array suurus, ütleme, 26 või äkki 27
Kui soovite toetada sidekriipsuga nimed

1091
00:51:04,790 --> 00:51:06,790
või ülakoma inimeste nimed.

1092
00:51:06,790 --> 00:51:08,280
>> Ja nii see on andmestruktuur.

1093
00:51:08,280 --> 00:51:10,290
Ja kui te vaatate ülevalt
alla, nagu siis, kui sa

1094
00:51:10,290 --> 00:51:13,710
vaadata top sõlme seal, M, on
osutades vasakpoolsem asi seal,

1095
00:51:13,710 --> 00:51:17,665
mis seejärel A, X, W, E, L, L. See on
vaid andmestruktuur, mis meelevaldselt

1096
00:51:17,665 --> 00:51:19,120
on talletamiseks inimeste nimed.

1097
00:51:19,120 --> 00:51:25,720
Ja Maxwell on salvestatud ainult järgmisi
teele massiivi massiivi massiivi.

1098
00:51:25,720 --> 00:51:30,050
Aga mis on hämmastav umbes Prefiksipuu on
et samas ahelloend ja isegi

1099
00:51:30,050 --> 00:51:34,520
massiivi, parim oleme kunagi saanud on
lineaarne aeg või logaritmiline aega otsin

1100
00:51:34,520 --> 00:51:35,600
keegi üles.

1101
00:51:35,600 --> 00:51:40,530
Selles andmestruktuur Prefiksipuu, kui
minu andmete struktuur on ühe nime ta

1102
00:51:40,530 --> 00:51:43,720
ja ma otsin Maxwell, ma olen
leiame teda päris kiiresti.

1103
00:51:43,720 --> 00:51:47,910
Ma lihtsalt otsida M-A-X-W-E-L-L. Kui
Selle andmestruktuur seevastu

1104
00:51:47,910 --> 00:51:51,830
kui N on miljon, kui seal on
miljonit nime selles andmestruktuur,

1105
00:51:51,830 --> 00:51:57,100
Maxwell on ikka veel olla
leitavaks pärast vaid M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
samme.

1107
00:51:58,090 --> 00:52:01,276
Ja David-- D-A-V-I-D samme.

1108
00:52:01,276 --> 00:52:03,400
Teisisõnu, ehitades
andmebaasi struktuur, mis on

1109
00:52:03,400 --> 00:52:07,240
sai kõik need massiivid, mis kõik
ise toetada muutmälu,

1110
00:52:07,240 --> 00:52:11,090
Ma ei hakata otsima üles inimesed
nimi kasutades aja jooksul, mis on

1111
00:52:11,090 --> 00:52:14,340
proportsionaalne mitte number
asju andmestruktuur,

1112
00:52:14,340 --> 00:52:16,330
nagu miljon olemasolevate nimesid.

1113
00:52:16,330 --> 00:52:20,135
Aega kulub mul leida
M-A-X-W-E-L-L selles andmestruktuuri on

1114
00:52:20,135 --> 00:52:22,260
proportsionaalne mitte
suurus andmestruktuuri,

1115
00:52:22,260 --> 00:52:25,930
kuid pikkusele nime.

1116
00:52:25,930 --> 00:52:28,440
Ja realistlikult
nimed otsime üles

1117
00:52:28,440 --> 00:52:29,970
on kunagi saab olema hull pikk.

1118
00:52:29,970 --> 00:52:32,600
Äkki keegi on 10 märk
Nime, 20 karakteri nimi.

1119
00:52:32,600 --> 00:52:33,900
See on kindlasti piiratud, eks?

1120
00:52:33,900 --> 00:52:37,110
Hetkel inimese Maal, kes
on pikim võimalik nime,

1121
00:52:37,110 --> 00:52:39,920
kuid see nimetus on pidev
väärtuse pikkus, eks?

1122
00:52:39,920 --> 00:52:41,980
See ei erine üheski mõttes.

1123
00:52:41,980 --> 00:52:45,090
Nii et sel viisil oleme
saavutatud andmestruktuuri

1124
00:52:45,090 --> 00:52:47,800
mis on pidevas aega look-up.

1125
00:52:47,800 --> 00:52:50,670
See ei võta mitmeid samme
sõltuvalt sisendandmete pikkus,

1126
00:52:50,670 --> 00:52:54,250
kuid mitte arv nimi
andmestruktuuris.

1127
00:52:54,250 --> 00:52:58,700
Nii et kui me kaks korda rohkem nimed
Järgmisel aastal miljard kuni kaks miljardit

1128
00:52:58,700 --> 00:53:03,720
leid Maxwell kavatseb võtta
täpselt sama arvu seitse sammu

1129
00:53:03,720 --> 00:53:04,650
teda leida.

1130
00:53:04,650 --> 00:53:08,810
Ja nii näib, et oleme saavutanud
meie Püha Graal sõiduaega.

1131
00:53:08,810 --> 00:53:10,860
>> Nii Paar kiiret teadaandeid.

1132
00:53:10,860 --> 00:53:11,850
Quiz null on tulemas.

1133
00:53:11,850 --> 00:53:14,600
Veel, et muidugi veebilehte
üle järgmise paari päeva jooksul.

1134
00:53:14,600 --> 00:53:17,120
Esmaspäeval lecture-- see on puhkus
siin Harvardi esmaspäeval.

1135
00:53:17,120 --> 00:53:18,850
See ei ole New Haven,
nii et me oleme võttes klassi

1136
00:53:18,850 --> 00:53:20,310
New Haven loeng esmaspäeval.

1137
00:53:20,310 --> 00:53:22,550
Kõik saab filmida
ja striimitakse live nagu tavaliselt,

1138
00:53:22,550 --> 00:53:24,900
kuid olgem end täna
koos 30 teise klipi

1139
00:53:24,900 --> 00:53:26,910
nn "Deep Mõtted"
poolt Daven Farnham, mis

1140
00:53:26,910 --> 00:53:30,850
eeskujuks oli eelmisel aastal laupäeval
Öö Live "Deep Mõtted"

1141
00:53:30,850 --> 00:53:35,700
Jack Handy, mis
Nüüd peaks mõtet.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Ja nüüd, "Deep
Mõtted "poolt Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tabelis.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Olgu, see on see nüüd.

1147
00:53:47,660 --> 00:53:48,805
Näeme järgmisel nädalal.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Et näha, kuidas see toimib.

1150
00:53:56,680 --> 00:53:58,304
Võtame pilk, et just nüüd.

1151
00:53:58,304 --> 00:53:59,890
Nii et siin on meil sorteerimata massiivi.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, võite minna ja restart
see vaid üks teine, palun.

1153
00:54:04,860 --> 00:54:08,562
Olgu, kaamerad on jooksvalt, nii
tegevus, kui sa oled valmis, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Okei, nii et see, mida me
on siin on sorteerimata massiivi.

1155
00:54:11,020 --> 00:54:13,960
Ja ma olen värviline kõik elemendid
punane, see tähendab, et see on tegelikult

1156
00:54:13,960 --> 00:54:14,460
sorteerimata.

1157
00:54:14,460 --> 00:54:17,960
Nii meenutada, et esimene asi, mida me teeme
on sortida vasakule poole massiivi.

1158
00:54:17,960 --> 00:54:20,630
Siis sortida õigus
pool massiivi.

1159
00:54:20,630 --> 00:54:22,830
Ja ya-blaa-blaa-da,
me ühinevad nendega koos.

1160
00:54:22,830 --> 00:54:24,520
Ja meil on täiesti sorteeritud massiivi.

1161
00:54:24,520 --> 00:54:25,360
Nii see on, kuidas ühendada omamoodi toimib.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Oot, oot, oot,
lõigatud, lõigatud, lõigatud, lõigatud.

1163
00:54:27,109 --> 00:54:30,130
Doug, sa ei saa lihtsalt ya-blaa-da,
ya-da, teed kaudu ühendada omamoodi.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Ma just tegin.

1165
00:54:31,970 --> 00:54:32,832
Kõik on korras.

1166
00:54:32,832 --> 00:54:33,540
Me oled hea minna.

1167
00:54:33,540 --> 00:54:34,760
Lihtsalt hoida jooksvalt.

1168
00:54:34,760 --> 00:54:35,380
Igatahes,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Sa pead selgitama
see paremini, kui on.

1170
00:54:37,800 --> 00:54:39,999
See on lihtsalt ei piisa.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, me ei
pead minema tagasi ühe.

1172
00:54:41,790 --> 00:54:42,350
Kõik on korras.

1173
00:54:42,350 --> 00:54:45,690
Igatahes, kui me jätkame merge--
Ian, me oleme keset filmimist.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Ma tean.

1175
00:54:46,612 --> 00:54:49,320
Ja me ei saa lihtsalt ya-blaa-da,
ya-da, läbi kogu protsessi.

1176
00:54:49,320 --> 00:54:52,200
Sul on selgitada, kuidas
Mõlemad pooled saavad kokku liita.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Aga me oleme juba
selgitas, kuidas kaks sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Sa oled näidanud
neid ühendamise massiivi.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Nad teavad protsessi.

1180
00:54:56,486 --> 00:54:57,172
Nad on kõik korras.

1181
00:54:57,172 --> 00:54:58,380
Me oleme läinud üle kümne korra.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Sa lihtsalt vahele paremale üle.

1183
00:55:00,330 --> 00:55:03,360
Me läheme tagasi üks, siis
ei saa sa ya-blaa-da üle.

1184
00:55:03,360 --> 00:55:05,480
Olgu, tagasi ühe.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Ma pean minema tagasi
läbi kõik slaidid?

1186
00:55:07,833 --> 00:55:08,332
Mu Jumal.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
See on nagu kuuendat korda, Ian.

1189
00:55:13,004 --> 00:55:13,940
Kõik on korras.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Okei.

1191
00:55:15,200 --> 00:55:16,590
Oled valmis?

1192
00:55:16,590 --> 00:55:17,400
Hea.

1193
00:55:17,400 --> 00:55:18,950
Action.