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

2
00:00:10,900 --> 00:00:15,860
>> Ræðumaður 1: Allt í lagi, þannig að þetta er
CS50 Þetta er endir viku fimm.

3
00:00:15,860 --> 00:00:19,220
Og muna að síðasta skipti sem við
byrjaði að horfa á áhugamaður gögn

4
00:00:19,220 --> 00:00:22,310
mannvirki sem byrjaði að leysa
vandamál, sem byrjaði að kynna

5
00:00:22,310 --> 00:00:25,640
ný vandamál, en lykillinn að þessu
var svoleiðis þráðum sem við

6
00:00:25,640 --> 00:00:27,940
byrjaði að gera frá hnút að hnút.

7
00:00:27,940 --> 00:00:30,085
Þannig að þetta er auðvitað
eintengdan lista.

8
00:00:30,085 --> 00:00:31,960
Og með því að ein tengd,
Ég meina það er bara eitt

9
00:00:31,960 --> 00:00:33,380
þráður milli hvert þessara hnúður.

10
00:00:33,380 --> 00:00:35,890
Snýr út að þú getur gert áhugamaður
hlutir eins og tvöfalt tengd listum

11
00:00:35,890 --> 00:00:38,470
þar sem þú ert með ör
fara í báðar áttir, sem

12
00:00:38,470 --> 00:00:40,320
getur hjálpað með ákveðnum hagkvæmni.

13
00:00:40,320 --> 00:00:42,000
En þetta leyst vandann?

14
00:00:42,000 --> 00:00:43,500
Hvaða vandamál gerði þetta leysa?

15
00:00:43,500 --> 00:00:46,620
Af hverju höfum vér sama á mánudag?

16
00:00:46,620 --> 00:00:49,820
Hvers vegna, í orði, gerði við sama á mánudag?

17
00:00:49,820 --> 00:00:50,630
Hvað þýðir það að gera?

18
00:00:50,630 --> 00:00:51,950
>> Áhorfendur: Við getum virk búa það.

19
00:00:51,950 --> 00:00:53,740
>> Ræðumaður 1: Allt í lagi, þannig að við getum
breytilega búa það.

20
00:00:53,740 --> 00:00:54,710
Vel gert bæði.

21
00:00:54,710 --> 00:00:57,560
Svo þú getur virk búa þetta
gögn uppbygging, en fylki,

22
00:00:57,560 --> 00:01:00,760
muna, þú þarft að vita
fyrirfram hversu mikið pláss þú vilt

23
00:01:00,760 --> 00:01:03,870
og ef þú þarft aðeins meira
pláss, þú ert svona út af heppni.

24
00:01:03,870 --> 00:01:05,560
Þú þarft að búa til nýjan array.

25
00:01:05,560 --> 00:01:07,893
Þú þarft að færa alla þína
gögn frá einum til annars,

26
00:01:07,893 --> 00:01:10,600
loksins frjáls gamla array
ef þú getur, og síðan haldið áfram.

27
00:01:10,600 --> 00:01:13,891
Sem bara finnst mjög dýrt og mjög
óhagkvæm, og reyndar getur það verið.

28
00:01:13,891 --> 00:01:14,890
En þetta er ekki allt gott.

29
00:01:14,890 --> 00:01:18,180
Við að greiða verð, það var einn
af the fleiri augljós verði við

30
00:01:18,180 --> 00:01:20,550
greiða með því að nota tengdan lista?

31
00:01:20,550 --> 00:01:22,825
>> Áhorfendur: Við verðum að nota
tvöfaldur pláss fyrir hvern og einn.

32
00:01:22,825 --> 00:01:25,200
Ræðumaður 1: Já, þannig að við þurfum
að minnsta kosti tvisvar sinnum eins mikið pláss.

33
00:01:25,200 --> 00:01:27,700
Í raun, áttaði ég þessi mynd er
jafnvel svolítið villandi,

34
00:01:27,700 --> 00:01:32,200
því að á CS50 IDE í fullt af nútíma
tölvur, bendi eða netfang

35
00:01:32,200 --> 00:01:33,700
er ekki í raun fjögur bæti.

36
00:01:33,700 --> 00:01:36,090
Það er mjög oft þessir
daga átta bytes, sem

37
00:01:36,090 --> 00:01:38,530
þýðir botninum
ferhyrninga þar í raun og veru

38
00:01:38,530 --> 00:01:40,900
eru eins konar tvöfalt
stór og það sem ég hef dregið,

39
00:01:40,900 --> 00:01:44,409
sem þýðir að þú ert að nota þrisvar sinnum
mikið pláss eins og við gætum ella.

40
00:01:44,409 --> 00:01:46,700
Nú á sama tíma, við erum
enn að tala bæti, ekki satt?

41
00:01:46,700 --> 00:01:49,140
Við erum ekki endilega að tala
megabæti eða gígabæta,

42
00:01:49,140 --> 00:01:51,000
nema þessi gögn mannvirki fá stór.

43
00:01:51,000 --> 00:01:54,510
>> Og svo í dag erum við að byrja að fjalla
hvernig við gætum kanna gögn

44
00:01:54,510 --> 00:01:57,310
skilvirkari ef í
Staðreyndin gögn fær stærri.

45
00:01:57,310 --> 00:02:00,360
En við skulum reyna að canonicalize
starfsemi fyrstu

46
00:02:00,360 --> 00:02:02,460
sem þú getur gert á þessum
konar gögn uppbygging.

47
00:02:02,460 --> 00:02:04,790
Svo eitthvað eins tengdur
listi styður almennt

48
00:02:04,790 --> 00:02:07,514
Rekstur eins eyða,
setja, og leita.

49
00:02:07,514 --> 00:02:08,639
Og hvað ég meina með því?

50
00:02:08,639 --> 00:02:11,222
Það þýðir bara að yfirleitt,
ef fólk er að nota tengdan lista,

51
00:02:11,222 --> 00:02:14,287
þeir eða einhver annar hefur innleitt
virka eins Eyða, Bæta í,

52
00:02:14,287 --> 00:02:16,120
og leita, svo þú getur
raunverulega gera eitthvað

53
00:02:16,120 --> 00:02:18,030
gagnlegt við gögn uppbygging.

54
00:02:18,030 --> 00:02:20,760
Svo skulum taka a fljótur líta
hvernig við gætum framkvæma

55
00:02:20,760 --> 00:02:24,530
sumir póstnúmer fyrir tengda listanum sem hér segir.

56
00:02:24,530 --> 00:02:27,885
>> Svo er þetta bara sumir C kóða,
ekki einu sinni heill forrit

57
00:02:27,885 --> 00:02:29,260
að ég mjög fljótt þeyttum upp.

58
00:02:29,260 --> 00:02:32,300
Það er ekki á netinu í dreifingu
númer, vegna þess að það mun í raun ekki að keyra.

59
00:02:32,300 --> 00:02:33,790
En eftir að ég hef bara
með athugasemd sagði,

60
00:02:33,790 --> 00:02:36,130
punktur punktur punktur eitthvað
það, punktur punktur punktur, eitthvað þar.

61
00:02:36,130 --> 00:02:38,410
Og við skulum líta bara á
hvað safaríkur hlutir eru.

62
00:02:38,410 --> 00:02:40,790
Svo á línu þremur,
muna að þetta er nú

63
00:02:40,790 --> 00:02:45,960
við lagt lýsa hnút síðasta
tíma, einn af þeim rétthyrnd hlutum.

64
00:02:45,960 --> 00:02:48,790
Það hefur int sem við munum kalla N,
en við gátum kalla það nokkuð,

65
00:02:48,790 --> 00:02:51,920
og þá struct hnút stjarna heitir næst.

66
00:02:51,920 --> 00:02:55,520
Og bara til að vera ljóst, að annað
lína, á línu sex, hvað er það?

67
00:02:55,520 --> 00:02:57,930
Hvað er það að gera fyrir okkur?

68
00:02:57,930 --> 00:03:01,044
Vegna þess að það lítur vissulega meira
dulinn en venjulega breytum okkar.

69
00:03:01,044 --> 00:03:02,740
>> Áhorfendur: Það gerir það að færa yfir eitt.

70
00:03:02,740 --> 00:03:04,650
>> Ræðumaður 1: Það gerir það að færa yfir eitt.

71
00:03:04,650 --> 00:03:08,580
Og til að vera nákvæmari,
það mun geyma heimilisfangið

72
00:03:08,580 --> 00:03:11,582
hnútarins sem er ætlað að vera
merkingu við hliðina á henni, ekki satt?

73
00:03:11,582 --> 00:03:13,540
Svo það er ekki að fara að
endilega fara neitt.

74
00:03:13,540 --> 00:03:15,290
Það er bara að fara að
geyma verðmæti, sem er

75
00:03:15,290 --> 00:03:17,170
að fara að vera netfang
einhvern annan hnút,

76
00:03:17,170 --> 00:03:20,810
og það er hvers vegna við höfum sagt struct
hnút stjarna, stjarnan gefur til kynna

77
00:03:20,810 --> 00:03:22,370
bendi eða netfang.

78
00:03:22,370 --> 00:03:26,390
OK, svo nú ef þú ráð fyrir að við höfum
þetta N boði fyrir okkur, og við skulum

79
00:03:26,390 --> 00:03:29,490
gera ráð fyrir að einhver annar hefur
sett a heild búnt af heiltölur

80
00:03:29,490 --> 00:03:30,400
í tengda listanum.

81
00:03:30,400 --> 00:03:35,640
Og það tengist listi er
benti á eftir einhverjum tímapunkti

82
00:03:35,640 --> 00:03:39,040
breytu sem heitir listi sem er
samþykkt hér sem viðfang,

83
00:03:39,040 --> 00:03:43,120
hvernig get ég farið um línu
14 innleiða leit?

84
00:03:43,120 --> 00:03:45,990
Með öðrum orðum, ef ég er að innleiða
virka sem tilgangur í lífinu

85
00:03:45,990 --> 00:03:48,889
er að taka int og svo á
upphaf tengda listanum,

86
00:03:48,889 --> 00:03:50,430
sem er bendi á tengda listanum.

87
00:03:50,430 --> 00:03:52,992
Eins og fyrsta, sem ég held að Davíð
var sjálfboðaliði okkar á mánudaginn,

88
00:03:52,992 --> 00:03:54,700
Hann var að benda á
allt tengist lista,

89
00:03:54,700 --> 00:03:57,820
það er eins og við séum liggur
David inn sem rök okkar hér.

90
00:03:57,820 --> 00:03:59,990
Hvernig eigum við að fara um að fara yfir þennan lista?

91
00:03:59,990 --> 00:04:04,640
Jæja, það kemur í ljós að jafnvel þótt
ábendingum eru tiltölulega ný nú að okkur,

92
00:04:04,640 --> 00:04:07,010
við getum gert þetta tiltölulega
einfaldur.

93
00:04:07,010 --> 00:04:09,500
>> Ég ætla að fara á undan og
lýsa tímabundið breytu sem

94
00:04:09,500 --> 00:04:12,364
samkvæmt venju er bara að fara
að vera kölluð músina, eða PTR,

95
00:04:12,364 --> 00:04:14,030
en þú gætir kalla það hvað sem þú vilt.

96
00:04:14,030 --> 00:04:16,470
Og ég ætla að frumstilla
það til the byrjun af listanum.

97
00:04:16,470 --> 00:04:20,050
Svo þú getur konar hugsað þetta
sem mér kennara um daginn,

98
00:04:20,050 --> 00:04:23,580
konar benda á einhvern
meðal manna okkar sem sjálfboðaliða.

99
00:04:23,580 --> 00:04:26,470
Þannig að ég er tímabundið breytu sem er
bara að benda á það sama

100
00:04:26,470 --> 00:04:31,390
að okkar tilviljun heitir
Sjálfboðaliðinn David var einnig að benda á.

101
00:04:31,390 --> 00:04:35,440
Nú bendillinn er á meðan
ekki null, vegna muna

102
00:04:35,440 --> 00:04:40,350
sem null er einhver sérstakur Sentinel gildi
sem demarcates enda listans

103
00:04:40,350 --> 00:04:44,280
svo á meðan ég er ekki að benda á að
jörð eins og á síðasta sjálfboðaliða okkar

104
00:04:44,280 --> 00:04:47,190
var, við skulum fara á undan
og gera eftirfarandi.

105
00:04:47,190 --> 00:04:51,820
Ef pointer-- og nú vil ég svona
að gera það sem við gerðum við nemanda

106
00:04:51,820 --> 00:04:57,410
structure-- ef bendillinn punktur næsta
equals-- frekar, ef bendillinn punktur N jafngildir

107
00:04:57,410 --> 00:05:02,290
er jafn breytilega N, er
rök sem hefur verið samþykkt í,

108
00:05:02,290 --> 00:05:05,370
þá vil ég að fara á undan
og segja aftur satt.

109
00:05:05,370 --> 00:05:11,020
Ég hef fundið fjölda N inni af
einn af hnúður tengda listanum mínum.

110
00:05:11,020 --> 00:05:13,500
En punktur ekki lengur
virkar í þessu samhengi,

111
00:05:13,500 --> 00:05:17,260
vegna músina, PTR, er
reyndar bendi, heimilisfang,

112
00:05:17,260 --> 00:05:20,632
við getum í raun frábærlega
nota lokum stykki af setningafræði

113
00:05:20,632 --> 00:05:22,590
þannig bráðabirgða
innsæi skilningi og í raun

114
00:05:22,590 --> 00:05:27,870
nota ör hér, sem þýðir að fara frá
sem heimilisfang til tölunnar þar í.

115
00:05:27,870 --> 00:05:30,160
Svo það er mjög svipað í
anda að punktur rekstraraðila,

116
00:05:30,160 --> 00:05:33,860
heldur vegna þess að bendillinn er ekki bendi
og ekki raunverulegt struct sjálft,

117
00:05:33,860 --> 00:05:35,380
við notum bara ör.

118
00:05:35,380 --> 00:05:40,620
>> Þannig að ef núverandi hnút, að ég,
tímabundið breyta, er að benda á

119
00:05:40,620 --> 00:05:43,060
er ekki N, hvað mig langar að gera?

120
00:05:43,060 --> 00:05:45,910
Jæja, með sjálfboðaliðum mínum
sem við höfðum hér um daginn,

121
00:05:45,910 --> 00:05:49,710
ef fyrsti maðurinn minn er ekki sá sem ég
vilja, og kannski er annað manna ekki

122
00:05:49,710 --> 00:05:52,660
það sem ég vil, og þriðja, ég
þurfa að halda að hreyfa.

123
00:05:52,660 --> 00:05:54,690
Eins og hvernig get ég stíga í gegnum lista?

124
00:05:54,690 --> 00:05:57,470
Þegar við höfðum fylki, þér
bara gerði eins og ég auk plús.

125
00:05:57,470 --> 00:06:03,660
En í þessu tilfelli, nægir það til að
gera músina, fær, músina, næst.

126
00:06:03,660 --> 00:06:07,580
Með öðrum orðum er næsta sviði
er eins og alla vinstri höndum

127
00:06:07,580 --> 00:06:10,880
að mönnum sjálfboðaliðarnir á mánudaginn
voru með að benda á einhvern annan hnút.

128
00:06:10,880 --> 00:06:12,890
Þeir voru næst nágrannar þeirra.

129
00:06:12,890 --> 00:06:17,060
>> Þannig að ef ég vil stíga í gegnum þennan lista,
Ég get ekki bara gera I plús plús lengur,

130
00:06:17,060 --> 00:06:20,120
Ég hef í staðinn að segja
Ég, músina, er að fara

131
00:06:20,120 --> 00:06:24,650
að jafna hvað næsta reitur er,
næsta reit er, næsta reitur er,

132
00:06:24,650 --> 00:06:28,350
Eftirfarandi allar þessar vinstri höndum
sem við höfðum á sviðinu bendir

133
00:06:28,350 --> 00:06:30,000
sumum síðari gildi.

134
00:06:30,000 --> 00:06:32,590
Og ef ég fæ í gegnum
að allt endurtekning,

135
00:06:32,590 --> 00:06:39,330
og að lokum, ég lenti null ekki hafa
fann N enn, ég aftur bara rangt.

136
00:06:39,330 --> 00:06:44,100
Svo aftur, allt sem við erum að gera hér,
eins og á myndinni í smá stund síðan,

137
00:06:44,100 --> 00:06:47,840
er að byrja með því að benda á að
upphaf listanum væntanlega.

138
00:06:47,840 --> 00:06:50,970
Og þá er ég að athuga er, gildi
Ég er að leita að jafn níu?

139
00:06:50,970 --> 00:06:52,650
Ef svo er, ég aftur satt og ég er búin.

140
00:06:52,650 --> 00:06:56,450
Ef ekki, ég uppfæra hönd mína,
AKA músina, benda

141
00:06:56,450 --> 00:06:59,540
á milli næsta Arrow, og
þá staðsetningu næsti Arrow er,

142
00:06:59,540 --> 00:07:00,480
og næsta.

143
00:07:00,480 --> 00:07:03,770
Ég er einfaldlega að ganga í gegnum þetta fylki.

144
00:07:03,770 --> 00:07:06,010
>> Svo aftur, sem er ekki sama?

145
00:07:06,010 --> 00:07:07,861
Eins og það sem er þetta þáttur í?

146
00:07:07,861 --> 00:07:10,360
Jæja, muna að við kynntum
hugmyndin um stafla, sem

147
00:07:10,360 --> 00:07:15,400
er ágrip gögn slá svo miklu leyti sem það er
ekki C hlutur, er það ekki CS50 hlutur,

148
00:07:15,400 --> 00:07:19,430
það er ágrip hugmynd, þessi hugmynd um
stöflun hluti ofan á annan

149
00:07:19,430 --> 00:07:21,820
sem hægt er að hrinda í framkvæmd í
bunches af mismunandi vegu.

150
00:07:21,820 --> 00:07:25,600
Og ein leið við lagt var með
fylki, eða með tengda listanum.

151
00:07:25,600 --> 00:07:29,570
Og það kemur í ljós að canonically, a
stafla styður að minnsta kosti tvær aðgerðir.

152
00:07:29,570 --> 00:07:32,320
Og suð orð eru ýta, til
ýta eitthvað á mánudaginn,

153
00:07:32,320 --> 00:07:34,770
eins og nýtt bakkanum í
matsalur, eða pop,

154
00:07:34,770 --> 00:07:39,000
sem þýðir að fjarlægja efsta
bakki úr stafla í borðstofu

155
00:07:39,000 --> 00:07:41,500
sal, og þá kannski sumir
aðrar aðgerðir eins og heilbrigður.

156
00:07:41,500 --> 00:07:45,770
Svo hvernig getum við skilgreina uppbyggingu
sem við erum nú að kalla stafla?

157
00:07:45,770 --> 00:07:50,020
>> Jæja, höfum við öll nauðsynlegur
setningafræði ráða okkar í C. Ég segi,

158
00:07:50,020 --> 00:07:53,830
gefa mér á skilgreiningu á
a struct inni í stafla,

159
00:07:53,830 --> 00:07:58,030
Ég ætla að segja er fylki, á a
allt fullt af tölum og þá stærð.

160
00:07:58,030 --> 00:08:00,930
Svo í öðrum orðum, ef ég vil
að framkvæma þetta í kóða,

161
00:08:00,930 --> 00:08:03,830
láta mig fara og bara svona
draga hvað þetta er að segja.

162
00:08:03,830 --> 00:08:06,317
Þannig að þetta er að segja, gefa mér
uppbyggingu sem fékk fylki,

163
00:08:06,317 --> 00:08:09,400
og ég veit ekki hvað getu er,
það er víst einhver fasti sem ég hef

164
00:08:09,400 --> 00:08:10,858
skilgreind annars staðar, og það er bara fínt.

165
00:08:10,858 --> 00:08:15,260
En geri ráð fyrir að það er bara einn,
tveir, þrír, fjórir, fimm.

166
00:08:15,260 --> 00:08:16,700
Svo er 5 getu.

167
00:08:16,700 --> 00:08:21,730
Þessi þáttur inni minn
uppbygging verður gestur númer.

168
00:08:21,730 --> 00:08:24,020
Og þá er ég þörf einn
aðra breytilega virðist

169
00:08:24,020 --> 00:08:27,814
kallað stærð sem upphaflega ég ætla
að kveða á um er frumstilla á núll.

170
00:08:27,814 --> 00:08:29,730
Ef það er ekkert í
stafla, stærð er núll,

171
00:08:29,730 --> 00:08:31,420
og það er sorp gildi í tölum.

172
00:08:31,420 --> 00:08:33,450
Ég hef ekki hugmynd um hvað er þarna bara ennþá.

173
00:08:33,450 --> 00:08:36,059
>> Þannig að ef ég vil að ýta
eitthvað á mánudaginn,

174
00:08:36,059 --> 00:08:40,780
býst ég kalla virka ýta, og
Ég segi ýta 50, eins og númer 50,

175
00:08:40,780 --> 00:08:44,090
hvar á ég að leggja
Ég draga það í þessu fylki?

176
00:08:44,090 --> 00:08:47,124
Það er fimm mismunandi mögulegar svör.

177
00:08:47,124 --> 00:08:48,790
Hvar vilt þú að ýta á númerið 50?

178
00:08:48,790 --> 00:08:51,899
Ef markmiðið hér, aftur, kalla
virka ýta, fara í rifrildi

179
00:08:51,899 --> 00:08:52,940
50, hvar á ég að setja það?

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

181
00:08:55,680 --> 00:08:59,052
Fimm possible-- 20% líkur
að giska rétt.

182
00:08:59,052 --> 00:08:59,896
Já?

183
00:08:59,896 --> 00:09:00,740
>> Áhorfendur: Far rétt.

184
00:09:00,740 --> 00:09:01,990
>> Ræðumaður 1: Far rétt.

185
00:09:01,990 --> 00:09:08,359
Það er nú 25% líkur
að giska rétt.

186
00:09:08,359 --> 00:09:09,650
Svo það væri í raun að vera í lagi.

187
00:09:09,650 --> 00:09:12,770
Samkvæmt venju, ég segi með fjölda,
við myndum yfirleitt byrja á vinstri,

188
00:09:12,770 --> 00:09:14,519
en við gátum vissulega
byrja á hægri.

189
00:09:14,519 --> 00:09:17,478
Svo spoiler hér væri ég
líklega að fara að draga það á vinstri,

190
00:09:17,478 --> 00:09:20,060
rétt eins og í venjulegum array hvar
Ég byrja að fara frá vinstri til hægri.

191
00:09:20,060 --> 00:09:21,780
En ef þú getur selbiti
reiknað, fínn.

192
00:09:21,780 --> 00:09:23,060
Það er bara ekki hefðbundin.

193
00:09:23,060 --> 00:09:24,880
OK, ég þarf að gera eitt
meira breyting þó.

194
00:09:24,880 --> 00:09:27,710
Nú þegar ég hef ýtt eitthvað
á mánudaginn, hvað er næst?

195
00:09:27,710 --> 00:09:29,400
>> Allt í lagi, ég verð að hækka stærð.

196
00:09:29,400 --> 00:09:32,600
Svo láta mig fara á undan og bara
uppfæra þetta, sem var núll.

197
00:09:32,600 --> 00:09:35,950
Og í staðinn, ég ætla
að setja í gildi einum.

198
00:09:35,950 --> 00:09:39,460
Og nú ætla ég að ýta annað
númer á mánudaginn, eins og 51.

199
00:09:39,460 --> 00:09:42,680
Jæja, ég verð að gera eitt
breyting, sem er allt að stærð tvö.

200
00:09:42,680 --> 00:09:46,100
Og þá ætla ég að ýta einn meira
númer á mánudaginn eins 61,

201
00:09:46,100 --> 00:09:52,530
nú þarf ég að uppfæra stærð eitt
tími, og fá gildið 3 og stærð.

202
00:09:52,530 --> 00:09:54,690
Og nú ætla ég að hringja pop.

203
00:09:54,690 --> 00:09:57,250
Nú skjóta, samkvæmt venju,
tekur ekki rök.

204
00:09:57,250 --> 00:10:00,430
Með stafla, allt
benda á bakkanum samlíking

205
00:10:00,430 --> 00:10:03,450
er að þú þarft ekki svigrúm
að fara að fá að bakka, getur allt sem þú gera

206
00:10:03,450 --> 00:10:06,330
er skjóta hæstur einn frá
stafla, bara vegna þess.

207
00:10:06,330 --> 00:10:08,010
Það er það sem þessi gögn uppbygging gerir.

208
00:10:08,010 --> 00:10:12,250
>> Svo með því að að rökfræði ef ég
segja pop, hvað kemur út?

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

210
00:10:13,080 --> 00:10:15,402
Svo hvað raunverulega er tölva
að fara að gera í minni?

211
00:10:15,402 --> 00:10:16,610
Hvað er númerið mitt að gera?

212
00:10:16,610 --> 00:10:20,330
Hvað myndir þú leggja
við breytt á skjánum?

213
00:10:20,330 --> 00:10:23,410
Hvað ætti að breyta?

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

215
00:10:24,960 --> 00:10:26,334
Þannig að við að losna við 61.

216
00:10:26,334 --> 00:10:27,500
Svo ég get örugglega gert það.

217
00:10:27,500 --> 00:10:28,640
Og ég get að losna við 61.

218
00:10:28,640 --> 00:10:30,980
Og þá hvað annað
breyting þarf að gerast?

219
00:10:30,980 --> 00:10:33,160
Stærð hefur sennilega að fara aftur til tveggja.

220
00:10:33,160 --> 00:10:34,210
Og svo er það allt í lagi.

221
00:10:34,210 --> 00:10:36,690
En bíddu í eina mínútu, stærð
í smá stund síðan var þriggja.

222
00:10:36,690 --> 00:10:38,240
Gerum bara fljótur geðheilsu stöðva.

223
00:10:38,240 --> 00:10:41,810
Hvernig fengum við að vita að við
vildi til að losna við 61?

224
00:10:41,810 --> 00:10:42,760
Þar sem við erum að pabbi.

225
00:10:42,760 --> 00:10:46,450
Og svo ég hef þetta annað eign stærð.

226
00:10:46,450 --> 00:10:48,470
>> Bíddu, ég er
hugsa til baka til viku tvö

227
00:10:48,470 --> 00:10:51,660
þegar við byrjuðum að tala um
fylki, þar sem þetta var staðsetningu núll,

228
00:10:51,660 --> 00:10:55,920
þetta var staðsetningu einn, þetta var staðsetningu
tvö, þetta er staðsetning þrír, fjórir,

229
00:10:55,920 --> 00:10:58,460
það lítur út eins og
tengsl milli stærðar

230
00:10:58,460 --> 00:11:02,780
og þáttur sem ég vil fjarlægja
frá array virðist bara vera það?

231
00:11:02,780 --> 00:11:05,120
Stærð mínus einn.

232
00:11:05,120 --> 00:11:07,786
Og svo er það hvernig sem menn
við vitum 61 kemur fyrst.

233
00:11:07,786 --> 00:11:09,160
Hvernig er tölvan að fara að vita?

234
00:11:09,160 --> 00:11:11,701
Þegar númerið þitt, þar sem þú sennilega
langar að gera stærð mínus einn,

235
00:11:11,701 --> 00:11:14,950
Svo þrjár mínus einn er tveir, og það
þýðir að við viljum losna við 61.

236
00:11:14,950 --> 00:11:18,000
Og þá getum við örugglega að uppfæra
stærð þannig að stærð núna

237
00:11:18,000 --> 00:11:20,300
fer frá þremur til bara tveir.

238
00:11:20,300 --> 00:11:24,520
Og bara til að vera smámunasamur, ég ætla
að leggja til að ég er búin, ekki satt?

239
00:11:24,520 --> 00:11:27,660
Þú lagt innsæi
rétt ég ætti að losna við 61.

240
00:11:27,660 --> 00:11:30,700
En hafa ekki ég konar
konar fengið losa af 61?

241
00:11:30,700 --> 00:11:33,790
Ég hef í raun gleymt
að það er í raun og veru.

242
00:11:33,790 --> 00:11:37,680
Og hugsa til baka til PSET4, ef þú hefur lesið
grein um réttar, PDF

243
00:11:37,680 --> 00:11:40,780
sem við höfðum þið lesið, eða þú
verður að lesa í þessari viku fyrir PSET4.

244
00:11:40,780 --> 00:11:44,300
Muna að þetta er í raun germane að
Í heild hugmynd um réttar tölva.

245
00:11:44,300 --> 00:11:47,820
Hvað tölva almennt gerir er
hún gleymir bara hvar eitthvað er,

246
00:11:47,820 --> 00:11:51,300
en það er ekki að fara í og ​​eins
reyna að klóra það út eða hunsa

247
00:11:51,300 --> 00:11:54,560
þessir bitar með núllum og sjálfur
eða einhver önnur handahófi mynstur

248
00:11:54,560 --> 00:11:56,690
nema þú sjálfur að gera það vísvitandi.

249
00:11:56,690 --> 00:11:58,930
Svo innsæi þitt var
lagi, við skulum losna við 61.

250
00:11:58,930 --> 00:12:00,650
En í raun og veru, þá höfum við ekki að standa í.

251
00:12:00,650 --> 00:12:04,040
Við þurfum bara að gleyma því að
það er það með því að breyta stærð okkar.

252
00:12:04,040 --> 00:12:05,662
>> Nú er það vandamál með þessa stafla.

253
00:12:05,662 --> 00:12:07,620
Ef ég halda að þrýsta hluti
á mánudaginn, það er

254
00:12:07,620 --> 00:12:11,167
augljóslega að fara að gerast
í örfáum augnablikum tíma?

255
00:12:11,167 --> 00:12:12,500
Við erum að fara að keyra út af plássi.

256
00:12:12,500 --> 00:12:13,580
Og hvað gerum við?

257
00:12:13,580 --> 00:12:14,680
Við erum konar ruglaður.

258
00:12:14,680 --> 00:12:19,000
Þessi framkvæmd er ekki láta
okkur búa array, vegna þess að nota

259
00:12:19,000 --> 00:12:21,240
þetta setningafræði, ef þú
hugsa til baka til viku tvö,

260
00:12:21,240 --> 00:12:23,520
þegar þú hefur lýst
stærð fylki,

261
00:12:23,520 --> 00:12:26,780
við höfum ekki séð á kerfi enn þar
þú getur breytt stærð fylkisins.

262
00:12:26,780 --> 00:12:29,020
Og reyndar C er ekki að lögun.

263
00:12:29,020 --> 00:12:32,524
Ef þú segir að gefa mér fimm
Nths, kalla þá tölur,

264
00:12:32,524 --> 00:12:33,940
það er allt sem þú ert að fara að fá það.

265
00:12:33,940 --> 00:12:38,790
Svo við gerum nú og með mánudeginum, hafa
getu til að tjá lausn

266
00:12:38,790 --> 00:12:42,480
þurfum við bara að fínstilla
skilgreiningu á mánudaginn okkar

267
00:12:42,480 --> 00:12:46,840
að ekki vera einhver harður-dulmáli array,
en bara til að geyma ávarp.

268
00:12:46,840 --> 00:12:47,890
>> Nú hvers vegna er þetta?

269
00:12:47,890 --> 00:12:51,690
Nú höfum við bara að vera ánægð með
sú staðreynd að þegar forritið mitt keyrir,

270
00:12:51,690 --> 00:12:53,730
Ég væntanlega fara til
verður að spyrja manninn,

271
00:12:53,730 --> 00:12:55,110
hve mörg númer viltu geyma?

272
00:12:55,110 --> 00:12:56,776
Svo hefur inntak að koma frá einhvers staðar.

273
00:12:56,776 --> 00:12:59,140
En þegar ég veit að
tala, þá ég get bara

274
00:12:59,140 --> 00:13:02,470
nota það virka að gefa
mér klumpur af minni?

275
00:13:02,470 --> 00:13:03,580
Ég get notað malloc.

276
00:13:03,580 --> 00:13:06,710
Og ég get sagt hvaða fjölda
bytes Ég vil aftur fyrir þessar Nths.

277
00:13:06,710 --> 00:13:10,910
Og allt sem ég hef að geyma í tölurnar
breyta hér inni þessa strúktúr

278
00:13:10,910 --> 00:13:13,480
ætti að vera það?

279
00:13:13,480 --> 00:13:18,440
Það sem raunverulega fer í
Tölurnar í þessari atburðarás?

280
00:13:18,440 --> 00:13:21,300
Já, bendi fyrst
bæti þess klumpur af minni,

281
00:13:21,300 --> 00:13:24,940
eða nánar tiltekið, heimilisfangið
af fyrsta af þeim bæti.

282
00:13:24,940 --> 00:13:27,300
Skiptir ekki máli ef það er einn
bæti eða milljarð bytes,

283
00:13:27,300 --> 00:13:28,890
Ég þarf bara að hugsa um fyrst.

284
00:13:28,890 --> 00:13:31,530
Vegna þess að það malloc ábyrgðir og
stýrikerfi ábyrgðir mínir

285
00:13:31,530 --> 00:13:34,170
er að klumpur af minni I
fá, það er að fara að vera samfelldir.

286
00:13:34,170 --> 00:13:35,378
Það er ekki að fara að vera eyður.

287
00:13:35,378 --> 00:13:38,576
Svo ef ég hef beðið fyrir 50
bytes eða 1.000 bytes,

288
00:13:38,576 --> 00:13:40,450
þeir eru allir að fara að vera
aftur til baka til baka.

289
00:13:40,450 --> 00:13:44,500
Og svo lengi sem ég man hversu stór, hvernig
mikið ég bað um, allt sem ég þarf að vita

290
00:13:44,500 --> 00:13:46,230
er fyrsta netfang.

291
00:13:46,230 --> 00:13:48,660
>> Svo nú höfum við möguleika í kóða.

292
00:13:48,660 --> 00:13:51,280
Að vísu, það er að fara að taka okkur
meiri tíma til að skrifa þetta upp,

293
00:13:51,280 --> 00:13:55,900
við gætum nú endurúthluta að minni með
bara að geyma annað netfang þar

294
00:13:55,900 --> 00:13:59,060
ef við viljum stærri eða jafnvel
minni klumpur af minni.

295
00:13:59,060 --> 00:14:00,170
Svo hér til vörumerkis burt.

296
00:14:00,170 --> 00:14:01,360
Nú fáum við kraft.

297
00:14:01,360 --> 00:14:03,350
Við höfum enn
contiguousness ég segja.

298
00:14:03,350 --> 00:14:05,881
Vegna malloc mun gefa okkur
Samhangandi klumpur af minni.

299
00:14:05,881 --> 00:14:08,630
En þetta er að fara til vera a sársauki í
háls fyrir okkur, forritari,

300
00:14:08,630 --> 00:14:09,770
að í raun kóða upp.

301
00:14:09,770 --> 00:14:10,730
Það er bara meiri vinna.

302
00:14:10,730 --> 00:14:13,930
Við þurfum kóða ætt við það sem ég var
lemja út bara í smá stund síðan.

303
00:14:13,930 --> 00:14:16,120
Mjög viðráðanleg, en það bætir flókið.

304
00:14:16,120 --> 00:14:19,520
Og svo verktaki tími, forritari
tími er enn annar auðlind

305
00:14:19,520 --> 00:14:22,520
að við gætum þurft að eyða
sumir tími til að fá nýja möguleika.

306
00:14:22,520 --> 00:14:24,020
Og svo auðvitað það er biðröð.

307
00:14:24,020 --> 00:14:26,227
Við munum ekki fara inn á þetta
einn í miklum smáatriðum.

308
00:14:26,227 --> 00:14:27,560
En það er mjög svipað í anda.

309
00:14:27,560 --> 00:14:31,220
Ég gæti innleiða biðröð, og
samsvarandi starfsemi þess,

310
00:14:31,220 --> 00:14:35,660
enqueue eða dequeue, eins bæta við eða fjarlægja,
það er bara áhugamaður leið til að segja það,

311
00:14:35,660 --> 00:14:38,100
enqueue eða dequeue, eins og hér segir.

312
00:14:38,100 --> 00:14:41,170
Ég get bara gefa mér strúktúr
sem aftur hefur fjölbreytta a tala er,

313
00:14:41,170 --> 00:14:44,000
sem aftur er með stærð,
en hvers vegna þarf ég nú

314
00:14:44,000 --> 00:14:46,940
til að halda utan um framan biðröð?

315
00:14:46,940 --> 00:14:50,630
Ég þarf ekki að vita
framan á stafla minni.

316
00:14:50,630 --> 00:14:53,570
Jæja, ef ég aftur fyrir a
queue-- skulum bara erfitt

317
00:14:53,570 --> 00:14:57,870
kóða það sem hafa eins og fimm
heiltölur í hér hugsanlega.

318
00:14:57,870 --> 00:15:00,940
Svo er þetta núll, einn, tveir, þrír, fjórir.

319
00:15:00,940 --> 00:15:03,430
Þetta er að fara að vera
hringt aftur.

320
00:15:03,430 --> 00:15:06,940
Og þetta mun vera kallað stærð.

321
00:15:06,940 --> 00:15:10,056
>> Hvers vegna er það ekki nóg
að hafa bara stærð?

322
00:15:10,056 --> 00:15:11,680
Jæja, við skulum ýta sömu tölur á.

323
00:15:11,680 --> 00:15:14,220
Svo ég pushed-- ég enqueued, eða ýtt.

324
00:15:14,220 --> 00:15:20,150
Nú ég enqueue 50, og þá
51, og þá 61, og punktur punktur punktur.

325
00:15:20,150 --> 00:15:21,070
Svo er það enqueue.

326
00:15:21,070 --> 00:15:23,176
Ég enqueued 50, þá 51, þá 61.

327
00:15:23,176 --> 00:15:25,050
Og það lítur út eins
að stafla svona langt,

328
00:15:25,050 --> 00:15:27,190
nema ég þarf að gera eina breytingu.

329
00:15:27,190 --> 00:15:33,680
Ég þarf að uppfæra þessa stærð, svo ég fer
frá núll til einn eða tvo til þrjá núna.

330
00:15:33,680 --> 00:15:35,760
Hvernig get ég dequeue?

331
00:15:35,760 --> 00:15:36,890
Hvað gerist með dequeue?

332
00:15:36,890 --> 00:15:41,950
Hverjir ættu að koma á þennan lista fyrst
ef það er lína á Apple Store?

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

334
00:15:42,780 --> 00:15:44,700
Svo það er góður af trickier þessu sinni.

335
00:15:44,700 --> 00:15:47,880
En síðast þegar það var frábær
auðvelt að bara gera stærð mínus einn,

336
00:15:47,880 --> 00:15:51,440
Ég fá til the endir af array minn raun
þar sem tölur eru, fjarlægir það 61.

337
00:15:51,440 --> 00:15:52,920
En ég vil ekki að fjarlægja 61.

338
00:15:52,920 --> 00:15:55,030
Ég vil taka 50, sem
var þar á 5:00 AM

339
00:15:55,030 --> 00:15:56,790
til að stilla upp fyrir
Ný iPhone eða whatnot.

340
00:15:56,790 --> 00:16:01,200
Og svo til að losna við 50, ég
getur ekki bara að gera þetta, ekki satt?

341
00:16:01,200 --> 00:16:02,547
Ég get strikað út 50.

342
00:16:02,547 --> 00:16:04,380
En við sögðum bara að við
þurfa ekki að vera svo endaþarms

343
00:16:04,380 --> 00:16:06,330
eins að klóra út eða fela gögnin.

344
00:16:06,330 --> 00:16:08,090
Við getum bara gleyma hvar það er.

345
00:16:08,090 --> 00:16:12,330
>> En ef ég breyti stærð mína núna til að
tveir, er þetta nægar upplýsingar

346
00:16:12,330 --> 00:16:15,711
að vita hvað er að gerast í biðröð mínum?

347
00:16:15,711 --> 00:16:16,680
Eiginlega ekki.

348
00:16:16,680 --> 00:16:19,830
Eins stærð minn er tveir, en
hvar biðröð byrja,

349
00:16:19,830 --> 00:16:22,980
sérstaklega ef ég hef enn
þessir sömu tölur í minni.

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

351
00:16:24,260 --> 00:16:27,090
Þannig að ég þarf að muna
nú þar sem framan er.

352
00:16:27,090 --> 00:16:29,630
Og svo eins og ég lagði upp
það munum við hafa bara kallað

353
00:16:29,630 --> 00:16:33,729
NTH framan, sem upphaflega
gildi ætti að hafa verið hvað?

354
00:16:33,729 --> 00:16:35,270
Zero, bara byrjunin á listanum.

355
00:16:35,270 --> 00:16:40,876
En nú auk þess að decrementing
stærð við hækka bara að framan.

356
00:16:40,876 --> 00:16:42,000
Nú er hér annað vandamál.

357
00:16:42,000 --> 00:16:43,030
Svo þegar ég að halda áfram.

358
00:16:43,030 --> 00:16:47,520
Segjum þetta er fjöldi
eins og 121, 124, og þá, dammit,

359
00:16:47,520 --> 00:16:48,610
Ég er út af plássi.

360
00:16:48,610 --> 00:16:50,390
En bíddu í eina mínútu, ég er ekki.

361
00:16:50,390 --> 00:16:55,630
Svo á þessum tímapunkti í sögunni,
gera ráð fyrir að stærð er einn, tveir,

362
00:16:55,630 --> 00:17:00,370
þrjá, fjóra, þannig gera ráð fyrir að
stærð er fjórir, að framan er eitt,

363
00:17:00,370 --> 00:17:01,621
svo 51 er að framan.

364
00:17:01,621 --> 00:17:04,329
Ég vil setja annað númer hér,
en dammit, ég er út af plássi.

365
00:17:04,329 --> 00:17:06,710
En ég er í raun ekki, ekki satt?

366
00:17:06,710 --> 00:17:11,192
Hvar gæti ég setti nokkrar
Umframvirði, eins 171?

367
00:17:11,192 --> 00:17:13,400
Já, ég gæti bara svona
fara aftur þarna, ekki satt?

368
00:17:13,400 --> 00:17:18,161
Og þá kross út 50, eða
bara skrifa það með 171.

369
00:17:18,161 --> 00:17:20,410
Og ef þú ert að spá í hvers vegna
númer okkar fékk svo af handahófi,

370
00:17:20,410 --> 00:17:24,150
Þetta eru almennt tekin tölvu
kenndar við Harvard eftir CS50.

371
00:17:24,150 --> 00:17:27,510
En það var gott hagræðingu,
því nú er ég ekki að sóa pláss.

372
00:17:27,510 --> 00:17:30,750
Ég er enn að muna
hversu stór þessi hlutur er alls.

373
00:17:30,750 --> 00:17:31,500
Það er fimm alls.

374
00:17:31,500 --> 00:17:33,375
Vegna þess að ég vil ekki að
byrja að skrifa yfir 51.

375
00:17:33,375 --> 00:17:36,260
Svo nú er ég enn út af plássi,
svo sama vandamál og áður.

376
00:17:36,260 --> 00:17:39,140
En þú getur séð hvernig nú
í kóðanum þínum, þú sennilega

377
00:17:39,140 --> 00:17:41,910
að skrifa smá meira
flókið að gera það gerast.

378
00:17:41,910 --> 00:17:44,510
Og í raun, hvað rekstraraðila
í C sennilega leyfir

379
00:17:44,510 --> 00:17:48,110
þú gerir dularfullur þetta circularity?

380
00:17:48,110 --> 00:17:50,160
Já það Modulo rekstraraðila,
sem prósent skilti.

381
00:17:50,160 --> 00:17:53,160
Svo hvað er góður af kaldur um biðröð,
jafnvel þótt við höldum teikna fylki

382
00:17:53,160 --> 00:17:56,520
eins og þessir eins beinar línur, ef þú
konar hugsa um þetta sem curving

383
00:17:56,520 --> 00:18:00,341
um eins og hring, þá bara
innsæi það virkar eins konar andlega

384
00:18:00,341 --> 00:18:01,590
Ég hugsa svolítið meira eðlilega.

385
00:18:01,590 --> 00:18:05,190
Þú þarft samt að framkvæma
að andleg fyrirmynd í kóða.

386
00:18:05,190 --> 00:18:07,550
Svo ekki það erfitt,
lokum, að hrinda í framkvæmd,

387
00:18:07,550 --> 00:18:12,430
en við missa enn size-- frekar,
getu til að búa, nema við gerum þetta.

388
00:18:12,430 --> 00:18:15,310
>> Við verðum að losna við fylki, við
skipta um það með einu músina,

389
00:18:15,310 --> 00:18:20,010
og þá einhvers staðar í númerið mitt sem ég hef fengið
a kalla það virka í raun að búa til

390
00:18:20,010 --> 00:18:23,720
array hringt?

391
00:18:23,720 --> 00:18:26,190
Malloc, eða einhver svipuð
virka, nákvæmlega.

392
00:18:26,190 --> 00:18:30,481
Einhverjar spurningar um stöflum eða biðröðum.

393
00:18:30,481 --> 00:18:30,980
Já?

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

395
00:18:33,657 --> 00:18:34,240
Góð spurning.

396
00:18:34,240 --> 00:18:35,830
Hvað Modulo myndir þú nota hér.

397
00:18:35,830 --> 00:18:38,520
Svo almennt, þegar
unga fólkið, myndir þú gera það

398
00:18:38,520 --> 00:18:40,620
með stærð á
heild gögn uppbygging.

399
00:18:40,620 --> 00:18:44,120
Svo eitthvað eins fimm eða getu, ef
það er stöðug, er sennilega að ræða.

400
00:18:44,120 --> 00:18:47,100
En bara að gera modulo fimm
sennilega er ekki nóg,

401
00:18:47,100 --> 00:18:51,380
vegna þess að við þurfum að vita gerum við
vefja um hér eða hér eða hér.

402
00:18:51,380 --> 00:18:54,160
Svo þú ert sennilega líka
fara til að vilja fela

403
00:18:54,160 --> 00:18:57,220
stærð hlutur, eða
framan breyta eins og heilbrigður.

404
00:18:57,220 --> 00:19:00,140
Svo það er bara þetta tiltölulega
einföld stærðfræði tjáning,

405
00:19:00,140 --> 00:19:02,000
en Modulo væri lykillinn efnið.

406
00:19:02,000 --> 00:19:03,330
>> Svo stuttmynd ef þú vilt.

407
00:19:03,330 --> 00:19:05,780
Hreyfimynd að sumir
Fólkinu á annan háskóla

408
00:19:05,780 --> 00:19:08,060
setja saman sem við höfum
aðlagað fyrir þessari umræðu.

409
00:19:08,060 --> 00:19:12,630
Það felur í sér Jack læra á
staðreyndir um biðraðir og tölfræði.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Einu sinni,
það var strákur sem heitir Jack.

412
00:19:21,890 --> 00:19:25,330
Þegar það kom að eignast vini,
Jack hafði ekki lagni.

413
00:19:25,330 --> 00:19:28,220
Svo fór Jack að tala við
Vinsælasta strákur hann vissi.

414
00:19:28,220 --> 00:19:30,920
Hann fór til Lou og spurði, hvað á ég að gera?

415
00:19:30,920 --> 00:19:33,400
Lou sá að vinur hans
var mjög nauðir.

416
00:19:33,400 --> 00:19:36,050
Jæja, byrjaði hann, bara
líta hvernig þú ert klæddur.

417
00:19:36,050 --> 00:19:38,680
Ekki þú hefur einhverjar föt
með mismunandi útlit?

418
00:19:38,680 --> 00:19:39,660
Já, sagði Jack.

419
00:19:39,660 --> 00:19:40,840
Ég viss.

420
00:19:40,840 --> 00:19:43,320
Komið til mín og
Ég skal sýna yður þær.

421
00:19:43,320 --> 00:19:44,550
Svo fóru þeir burt til Jack er.

422
00:19:44,550 --> 00:19:47,520
Og Jack sýndi Lou kassann
þar sem hann hélt alla skyrtur hans,

423
00:19:47,520 --> 00:19:49,260
og buxurnar hans og sokkar hans.

424
00:19:49,260 --> 00:19:52,290
Lou sagði, ég sé að þú hefur
allt fötin í hrúgu.

425
00:19:52,290 --> 00:19:54,870
Hví þú ekki að vera einhver
aðrir einu sinni í stutta stund?

426
00:19:54,870 --> 00:19:58,020
>> Jack sagði, vel, þegar ég
fjarlægja föt og sokka,

427
00:19:58,020 --> 00:20:00,780
Ég þvo þá og setja
þá í burtu í reitinn.

428
00:20:00,780 --> 00:20:03,210
Þá kemur næsta
morgun, og allt sem ég hoppa.

429
00:20:03,210 --> 00:20:06,380
Ég fer að kassanum og fá
fötin mín burt the toppur.

430
00:20:06,380 --> 00:20:09,070
Lou áttaði fljótt
vandamálið með Jack.

431
00:20:09,070 --> 00:20:12,080
Hann hélt föt, geisladiska,
og bækur í stafla.

432
00:20:12,080 --> 00:20:14,420
Þegar hann kom fyrir
eitthvað til að lesa eða til að klæðast,

433
00:20:14,420 --> 00:20:17,100
hann myndi velja efst bók eða nærföt.

434
00:20:17,100 --> 00:20:19,500
Svo þegar hann var búinn, hann
myndi setja það strax aftur.

435
00:20:19,500 --> 00:20:21,970
Back það myndi fara, ofan á stafla.

436
00:20:21,970 --> 00:20:24,460
Ég veit lausnina,
sagði triumphant Loud.

437
00:20:24,460 --> 00:20:27,090
Þú þarft að læra að
byrja að nota biðröð.

438
00:20:27,090 --> 00:20:29,870
Lou tók föt Jack og
hengdi þær í skápnum.

439
00:20:29,870 --> 00:20:32,710
Og þegar hann var að tæma
kassi, hann kastaði bara það.

440
00:20:32,710 --> 00:20:36,500
>> Þá sagði hann, nú Jack, í lok
daginn, setja fötin á vinstri

441
00:20:36,500 --> 00:20:37,990
þegar þú setur þá í burtu.

442
00:20:37,990 --> 00:20:41,300
Þá á morgun í morgun þegar þú
sjá sólskin, fá fötin

443
00:20:41,300 --> 00:20:43,440
til hægri, frá enda línunnar.

444
00:20:43,440 --> 00:20:44,880
Sérðu ekki? sagði Lou.

445
00:20:44,880 --> 00:20:46,370
Það verður svo gaman.

446
00:20:46,370 --> 00:20:49,770
Þú munt vera allt einu sinni
áður en þú ferð eitthvað tvisvar.

447
00:20:49,770 --> 00:20:52,670
Og með allt í biðröð
í skápnum hans og hillu,

448
00:20:52,670 --> 00:20:55,160
Jack byrjaði að finna
alveg viss um sjálfan sig.

449
00:20:55,160 --> 00:20:59,720
Allt þökk sé Lou og
dásamlegt biðröð hans.

450
00:20:59,720 --> 00:21:01,220
Ræðumaður 1: Allt í lagi, það er yndisleg.

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

452
00:21:05,920 --> 00:21:10,080
Svo hvað hefur verið í raun að fara
á undir hetta núna?

453
00:21:10,080 --> 00:21:12,370
Að við höfum ábendingum,
sem við höfum malloc,

454
00:21:12,370 --> 00:21:15,680
að við höfum getu til að búa
klumpur af minni fyrir okkur

455
00:21:15,680 --> 00:21:16,344
virk.

456
00:21:16,344 --> 00:21:18,510
Þannig að þetta er mynd sem við
glittir bara um daginn.

457
00:21:18,510 --> 00:21:21,180
Við vildum ekki raunverulega búa
á það, en þetta mynd

458
00:21:21,180 --> 00:21:24,180
hefur verið í gangi undir
hetta vikum saman.

459
00:21:24,180 --> 00:21:27,050
Og svo stendur þetta, bara
rétthyrningi sem við höfum dregið,

460
00:21:27,050 --> 00:21:28,180
minni tölvunnar.

461
00:21:28,180 --> 00:21:31,850
Og kannski tölvunni, eða CS50
ID, hefur gígabæti af minni eða vinnsluminni

462
00:21:31,850 --> 00:21:33,050
eða tveggja gígabæta eða fjögur.

463
00:21:33,050 --> 00:21:34,450
Það skiptir ekki máli.

464
00:21:34,450 --> 00:21:37,240
Stýrikerfið þitt
Windows eða Mac OS eða Linux,

465
00:21:37,240 --> 00:21:41,120
í raun gerir program
að hugsa að það hafi aðgang

466
00:21:41,120 --> 00:21:42,982
að heild
minni tölvunnar,

467
00:21:42,982 --> 00:21:45,440
jafnvel þó að þú gætir verið að keyra
mörg forrit í einu.

468
00:21:45,440 --> 00:21:46,990
Svo í raun, það er í raun að vinna.

469
00:21:46,990 --> 00:21:49,448
En það er góður af tálsýn
gefið öll forrit.

470
00:21:49,448 --> 00:21:53,110
Svo ef þú hefðir tvo gigs af RAM, þetta
er hvernig tölva gæti hugsa um það.

471
00:21:53,110 --> 00:21:57,110
>> Nú tilviljun, einn af þessum
hlutir, einn af þessum hluta minni,

472
00:21:57,110 --> 00:21:58,350
er kallað stafla.

473
00:21:58,350 --> 00:22:01,680
Og raunar hvenær
svona langt í að skrifa kóðann

474
00:22:01,680 --> 00:22:05,900
að þú hefur kallað
virka, til dæmis helstu.

475
00:22:05,900 --> 00:22:08,410
Muna að hvenær sem ég hef
minni teiknað tölvunnar,

476
00:22:08,410 --> 00:22:10,640
Ég teikna alltaf svona
helmingur af ferhyrnings hér

477
00:22:10,640 --> 00:22:12,520
og nennir ekki að tala
um hvað er hér að ofan.

478
00:22:12,520 --> 00:22:15,980
Vegna þess að þegar helstu heitir, kröfu I
að þú færð þennan flís af minni

479
00:22:15,980 --> 00:22:16,970
sem fer niður hér.

480
00:22:16,970 --> 00:22:20,650
Og ef helstu kallað fall
eins skipti, vel skipti fer hér.

481
00:22:20,650 --> 00:22:23,720
Og það kemur í ljós, það er
þar sem það er að enda.

482
00:22:23,720 --> 00:22:26,277
Á eitthvað sem kallast a stafla
inni minni tölvunnar.

483
00:22:26,277 --> 00:22:28,360
Nú í lok dagsins,
þetta er bara fjallar.

484
00:22:28,360 --> 00:22:30,680
Það er eins og bæti núll,
bæti einn, bæti 2 milljarða.

485
00:22:30,680 --> 00:22:33,130
En ef þér finnst um það
eins og þetta rétthyrndum hlut,

486
00:22:33,130 --> 00:22:35,130
allt sem við erum að gera á hverjum
Hvenær sem við köllum virka er

487
00:22:35,130 --> 00:22:37,180
layering nýja sneið af minni.

488
00:22:37,180 --> 00:22:41,700
Við erum að gefa að virka sneið
eigin minni til þess að vinna með.

489
00:22:41,700 --> 00:22:44,490
>> Og muna nú að þetta er mikilvægt.

490
00:22:44,490 --> 00:22:46,400
Vegna þess að ef við höfum
eitthvað eins og skipti

491
00:22:46,400 --> 00:22:51,610
og tvær staðbundnar breytur eins A og B og
við breytt þessum gildum frá einum og tveimur

492
00:22:51,610 --> 00:22:55,130
til tveggja og einn, muna
að þegar skipti skilar,

493
00:22:55,130 --> 00:22:58,330
það er eins og þetta sneið
af minni er bara farið.

494
00:22:58,330 --> 00:23:00,080
Í raun og veru, það er samt
það forensically.

495
00:23:00,080 --> 00:23:01,940
Og eitthvað er enn í raun þar.

496
00:23:01,940 --> 00:23:05,410
En eðli, það er eins
þó að það er alveg horfin.

497
00:23:05,410 --> 00:23:10,910
Og svo helstu veit ekki eitthvað af vinnu
sem var gert í því skipti virka,

498
00:23:10,910 --> 00:23:14,890
nema það er í raun liðin hjá þeim
rök með músina eða með tilvísun.

499
00:23:14,890 --> 00:23:17,790
Nú er grundvallaratriði lausn
að þessi vandamál með skipti

500
00:23:17,790 --> 00:23:19,970
er komið hlutina í því heimilisfang.

501
00:23:19,970 --> 00:23:23,250
En það kemur í ljós, of, það er
verið að fara á fyrir ofan þann hluta

502
00:23:23,250 --> 00:23:26,330
rétthyrningsins allan þennan tíma er
enn það er það meira minni upp.

503
00:23:26,330 --> 00:23:28,790
Og þegar þú virk
úthluta minni,

504
00:23:28,790 --> 00:23:32,020
hvort sem það er inni GetString, sem
við höfum verið að gera fyrir þig í CS50

505
00:23:32,020 --> 00:23:34,710
bókasafn, eða ef þið
kalla malloc og spyrja

506
00:23:34,710 --> 00:23:37,950
stýrikerfi fyrir klumpur af
minni, það kemur ekki úr stafla.

507
00:23:37,950 --> 00:23:40,960
Það kemur frá öðru sæti
í minni tölvunnar

508
00:23:40,960 --> 00:23:42,220
það er kallað að hrúga.

509
00:23:42,220 --> 00:23:43,430
Og það er ekki allir mismunandi.

510
00:23:43,430 --> 00:23:44,285
Það er sama RAM.

511
00:23:44,285 --> 00:23:45,160
Það er sama minni.

512
00:23:45,160 --> 00:23:49,080
Það er bara RAM sem er upp
það í stað þess að hérna.

513
00:23:49,080 --> 00:23:50,750
>> Og svo hvað þýðir það?

514
00:23:50,750 --> 00:23:53,650
Jæja, ef tölvan þín hefur
endanlegt magn af minni

515
00:23:53,650 --> 00:23:57,450
og stafla er að vaxa upp, svo
að tala, og hrúga, samkvæmt

516
00:23:57,450 --> 00:23:59,349
þessari ör, er að vaxa niður.

517
00:23:59,349 --> 00:24:01,140
Með öðrum orðum, sérhver
skipti sem þú hringja malloc,

518
00:24:01,140 --> 00:24:03,430
þú ert að fá sneið
af minni að ofan,

519
00:24:03,430 --> 00:24:06,630
þá kannski litlu minni, þá smá
lægri, í hvert skipti sem þú hringja malloc,

520
00:24:06,630 --> 00:24:10,100
hrúga, það notkun,
er eins konar vaxandi,

521
00:24:10,100 --> 00:24:11,950
vaxandi nær og nær til hvers?

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

523
00:24:13,382 --> 00:24:14,840
Svo þýðir þetta að virðast eins og góð hugmynd?

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

525
00:24:18,420 --> 00:24:22,140
Ég meina, ef það er ekki mjög skýr
hvað annað sem þú getur gert ef þú aðeins

526
00:24:22,140 --> 00:24:23,910
hafa endanlegt magn af minni.

527
00:24:23,910 --> 00:24:25,200
En þetta er vissulega slæmt.

528
00:24:25,200 --> 00:24:27,920
Þessir tveir örvar eru á a
hrun námskeið fyrir öðrum.

529
00:24:27,920 --> 00:24:31,930
>> Og það kemur í ljós að slæmur strákur, gott fólk sem
eru sérstaklega góð með forritun,

530
00:24:31,930 --> 00:24:36,140
og reyna að hakk inn í tölvur,
getur nýta þessa veruleika.

531
00:24:36,140 --> 00:24:38,290
Í raun, við skulum íhuga
smá runu.

532
00:24:38,290 --> 00:24:41,350
Svo er þetta dæmi sem þú getur lesið
um nánar á Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Við munum benda þér á að
grein ef forvitinn.

534
00:24:43,100 --> 00:24:45,650
En það er árás almennt
þekktur sem yfirflæði að

535
00:24:45,650 --> 00:24:49,570
hefur verið til í eins lengi og menn
hafa haft möguleika á að vinna

536
00:24:49,570 --> 00:24:53,120
minni tölvunnar, sérstaklega í C
Þannig að þetta er mjög handahófskennt program,

537
00:24:53,120 --> 00:24:55,130
en við skulum lesa það frá grunni.

538
00:24:55,130 --> 00:24:57,650
Main í argc bleikju stjörnu argv.

539
00:24:57,650 --> 00:24:59,830
Svo það er forrit sem tekur
stjórn lína rifrildi.

540
00:24:59,830 --> 00:25:03,620
Og allt main er virðist er kalla
fall, kalla það F fyrir einfaldleika.

541
00:25:03,620 --> 00:25:04,610
Og það fer í hvað?

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

543
00:25:05,490 --> 00:25:09,320
Svo það fer í F hvað
orðið er að notandinn slegið

544
00:25:09,320 --> 00:25:11,500
þegar beðið eftir að
Nafnið forritsins yfirleitt.

545
00:25:11,500 --> 00:25:15,730
Svo mikið eins og Caesar eða Vigenère, sem
þú might muna að gera við argv.

546
00:25:15,730 --> 00:25:16,680
>> Svo er það F?

547
00:25:16,680 --> 00:25:19,760
F tekur í streng
sem eina röksemdafærslu sína,

548
00:25:19,760 --> 00:25:22,100
AKA bleikju stjörnu, sama
hlutur, sem streng.

549
00:25:22,100 --> 00:25:24,920
Og það er kallað geðþótta
bar í þessu dæmi.

550
00:25:24,920 --> 00:25:27,710
Og þá bleikju c 12,
bara í skilmálum leikmaður er,

551
00:25:27,710 --> 00:25:31,750
hvað er bleikju c krappi 12 að gera fyrir okkur?

552
00:25:31,750 --> 00:25:33,440
Hvað er það gert?

553
00:25:33,440 --> 00:25:36,490
Úthlutun minni, sérstaklega
12 bytes fyrir 12 stafir.

554
00:25:36,490 --> 00:25:36,990
Nákvæmlega.

555
00:25:36,990 --> 00:25:40,000
Og þá síðustu línu, hrærið og
afrita, hefur þú sennilega ekki séð.

556
00:25:40,000 --> 00:25:43,360
Þetta er band afrit
virka sem tilgangur í lífinu

557
00:25:43,360 --> 00:25:48,160
er að afrita annað rifrildi sínu
í fyrstu röksemd þess,

558
00:25:48,160 --> 00:25:51,190
en aðeins upp að
ákveðinn fjölda bæti.

559
00:25:51,190 --> 00:25:53,860
Svo þriðja rök segir,
hversu margir bæti ættir þú afrita?

560
00:25:53,860 --> 00:25:56,720
Lengd bar,
hvað notandinn slegið inn.

561
00:25:56,720 --> 00:25:59,320
Og innihald
bar, þessi band, eru

562
00:25:59,320 --> 00:26:02,330
afrita í minni benti á í C

563
00:26:02,330 --> 00:26:04,060
>> Svo virðist svona heimskur, og það er.

564
00:26:04,060 --> 00:26:06,300
Það er háttuð dæmi,
en það er dæmigert

565
00:26:06,300 --> 00:26:10,100
af flokki vektor árás,
leið að ráðast forrit.

566
00:26:10,100 --> 00:26:15,050
Allt er fínt og gott ef notandinn
gerðir í orði sem er 11 stafir

567
00:26:15,050 --> 00:26:18,040
eða færri, auk sviga núll.

568
00:26:18,040 --> 00:26:22,830
Hvað ef notandinn slær í meira en
11 eða 12 eða 20 eða 50 stafir?

569
00:26:22,830 --> 00:26:25,090
Hvað er þetta forrit að gera?

570
00:26:25,090 --> 00:26:29,360
Hugsanlega seg kenna. Það er að fara
að blindni afrita allt í bar upp

571
00:26:29,360 --> 00:26:31,750
að lengd þess, sem er
bókstaflega allt í bar,

572
00:26:31,750 --> 00:26:36,307
í heimilisfang benti á C. En C
hefur aðeins preemptively gefið 12 bæti.

573
00:26:36,307 --> 00:26:37,640
En það er engin frekari athuga.

574
00:26:37,640 --> 00:26:38,700
Það er engin ef aðstæður.

575
00:26:38,700 --> 00:26:40,580
Það er engin villuprófun hér.

576
00:26:40,580 --> 00:26:43,270
>> Og svo það sem þetta forrit er
að fara að gera er bara í blindni

577
00:26:43,270 --> 00:26:45,750
afrita eitt til annars.

578
00:26:45,750 --> 00:26:47,880
Og svo ef við draga þetta
sem mynd, hér er

579
00:26:47,880 --> 00:26:49,860
bara flís af minni.

580
00:26:49,860 --> 00:26:53,470
Svo eftir neðst, við
hafa staðbundin breytu bar.

581
00:26:53,470 --> 00:26:57,330
Þannig að bendillinn sem er að fara að store--
frekar að heimamenn rök sem er

582
00:26:57,330 --> 00:26:58,672
að fara að geyma band bar.

583
00:26:58,672 --> 00:27:00,380
Og þá taka bara
ofan það í stafla,

584
00:27:00,380 --> 00:27:02,505
því í hvert skipti sem þú spyrð
fyrir minni á stafla,

585
00:27:02,505 --> 00:27:04,310
það fer svolítið
ofan það á myndrænan,

586
00:27:04,310 --> 00:27:06,270
Takið eftir að við höfum fengið 12 bæti það.

587
00:27:06,270 --> 00:27:10,690
Efst til vinstri er einn C krappi núll og
neðst til hægri er einn C krappi 11.

588
00:27:10,690 --> 00:27:12,870
Það er bara hvernig tölvur
að fara að leggja það út.

589
00:27:12,870 --> 00:27:18,300
Svo bara innsæi, ef bar er meira
en 12 stafir samtals, þ.mt

590
00:27:18,300 --> 00:27:25,790
sem sviga núll, hvar er
12 eða C krappi 12 að fara að fara?

591
00:27:25,790 --> 00:27:28,440
Eða öllu heldur þar er 12.
eðli eða 13. eðli,

592
00:27:28,440 --> 00:27:30,900
hundraðasta eðli fara
að enda á myndinni?

593
00:27:30,900 --> 00:27:33,400
Fyrir ofan eða neðan?

594
00:27:33,400 --> 00:27:36,300
>> Hægri, því jafnvel þótt
stafla sjálft vex upp,

595
00:27:36,300 --> 00:27:39,590
Þegar þú hefur sett efni í
það, það ástæðum er varða hönnun

596
00:27:39,590 --> 00:27:41,294
setur minni frá toppur til botn.

597
00:27:41,294 --> 00:27:44,460
Þannig að ef þú hefur fengið meira en 12 bæti,
þú ert að fara að byrja að skrifa bar.

598
00:27:44,460 --> 00:27:47,280
Nú er það galla, en það er
í raun ekki máli.

599
00:27:47,280 --> 00:27:51,130
En það er stór samningur, vegna þess að það er
meira efni að fara á í minni.

600
00:27:51,130 --> 00:27:53,074
Svo hér er hvernig við gætum
setja halló, að vera ljóst.

601
00:27:53,074 --> 00:27:54,490
Ef ég slóst í halló þegar beðið.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O sviga núll, endar upp innan
þessir 12 bytes, og við erum frábær öruggur.

603
00:27:59,330 --> 00:28:00,330
Allt er vel.

604
00:28:00,330 --> 00:28:03,020
En ef ég slá eitthvað
lengur, hugsanlega er það

605
00:28:03,020 --> 00:28:05,860
að fara að skríða inn í bar rúm.

606
00:28:05,860 --> 00:28:08,405
En verri enn, það kemur
út allan þennan tíma,

607
00:28:08,405 --> 00:28:11,530
jafnvel þó að við höfum aldrei talað um
það, stafla er notað fyrir önnur efni.

608
00:28:11,530 --> 00:28:13,560
Það er ekki bara staðbundnar breytur.

609
00:28:13,560 --> 00:28:15,100
>> C er mjög lágt tungumál.

610
00:28:15,100 --> 00:28:17,810
Og það er tegund af leynilega
notar stafla einnig

611
00:28:17,810 --> 00:28:21,260
að muna þegar
aðgerð er kölluð, hvað

612
00:28:21,260 --> 00:28:26,040
heimilisfangið er af fyrri virka,
svo það getur hoppað aftur til að virka.

613
00:28:26,040 --> 00:28:29,980
Svo þegar helstu símtöl skipta, meðal
það ýtt á stafla

614
00:28:29,980 --> 00:28:34,380
eru ekki bara skiptasamninga staðværar breytur,
eða rök hennar, einnig leynilega ýtt

615
00:28:34,380 --> 00:28:37,510
á mánudaginn eins fulltrúa
með rauða sneið hér,

616
00:28:37,510 --> 00:28:40,520
er heimilisfang helstu líkamlega
í minni tölvunnar,

617
00:28:40,520 --> 00:28:44,180
þannig að þegar skipti er gert, the tölva
veit að ég þarf að fara aftur til main

618
00:28:44,180 --> 00:28:46,760
og klára framkvæmd helstu virka.

619
00:28:46,760 --> 00:28:51,960
Svo er þetta hættulegt núna, vegna þess að ef
sem notandinn slær í vel meira en halló,

620
00:28:51,960 --> 00:28:57,030
þannig að inntak notanda clobbers
eða birtist sem rauður kafla,

621
00:28:57,030 --> 00:28:59,820
rökrétt ef tölvan er
bara að fara að blindni ráð

622
00:28:59,820 --> 00:29:03,830
að bæti í því rauða sneið eru
heimilisfangið sem það ætti að fara aftur,

623
00:29:03,830 --> 00:29:09,020
hvað ef andstæðingurinn er sviði nógur eða
heppin að setja röð af bytes

624
00:29:09,020 --> 00:29:13,450
það sem lítur út eins og heimilisfang,
en það er veffang kóða

625
00:29:13,450 --> 00:29:18,730
að hann eða hún vill tölvuna
að framkvæma í stað þess að main?

626
00:29:18,730 --> 00:29:21,670
>> Með öðrum orðum, ef það á
notandi er að skrifa á að hvetja,

627
00:29:21,670 --> 00:29:23,850
er ekki bara eitthvað
innocuous eins halló,

628
00:29:23,850 --> 00:29:28,210
en það er í raun númer sem er jafngilt
til að eyða öllum skrám notanda?

629
00:29:28,210 --> 00:29:30,060
Eða email lykilorðinu sínu til mín?

630
00:29:30,060 --> 00:29:31,940
Eða byrja skógarhögg þeirra
mínútum, ekki satt?

631
00:29:31,940 --> 00:29:34,920
There er a vegur, við skulum kveða dag,
að þeir gætu slegið í ekki bara halló

632
00:29:34,920 --> 00:29:36,711
heimurinn eða nafn sitt,
þeir gátu í raun

633
00:29:36,711 --> 00:29:39,570
fara í kóða, núll og
sjálfur, að tölvan

634
00:29:39,570 --> 00:29:43,450
mistök fyrir bæði kóða og heimilisfang.

635
00:29:43,450 --> 00:29:48,950
Svo að vísu nokkuð abstrakt, ef
notandinn slær í nógu andstæðinga kóða

636
00:29:48,950 --> 00:29:52,330
sem við munum alhæfa hér sem
A. A er árás eða mótstöðumenn.

637
00:29:52,330 --> 00:29:53,140
Svo bara slæmt efni.

638
00:29:53,140 --> 00:29:55,306
Við sama um
númera eða núll eða þau

639
00:29:55,306 --> 00:29:59,470
í dag, svo að þú endar
skrifa yfir þessi rauða kafla,

640
00:29:59,470 --> 00:30:01,580
eftir því að röð bæti.

641
00:30:01,580 --> 00:30:05,020
O 835 C núll átta núll.

642
00:30:05,020 --> 00:30:08,960
Og nú eins og grein Wikipedia hér
hefur lagt til, ef þú nú í raun að byrja

643
00:30:08,960 --> 00:30:12,460
merkingu bæti í Computer þíns
minni, hvað Wikipedia grein er

644
00:30:12,460 --> 00:30:19,060
að leggja er það, hvað ef netfang
þess efst í vinstra bæti er 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Með öðrum orðum, ef slæmur strákur er
klár nóg með kóða hans

646
00:30:22,200 --> 00:30:26,650
að í raun setja númer hér að
samsvarar heimilisfang kóða

647
00:30:26,650 --> 00:30:29,180
hann eða hún sprautað
inn í tölvuna, þú

648
00:30:29,180 --> 00:30:31,050
getur bragð tölvuna
í að gera neitt.

649
00:30:31,050 --> 00:30:34,140
Fjarlægi skrár, póst
hlutir, sjúga upp í nefið umferð,

650
00:30:34,140 --> 00:30:36,710
bókstaflega nokkuð gæti verið
sprautað inn í tölvuna.

651
00:30:36,710 --> 00:30:39,220
Og svo gnægð biðminni
árás á kjarna þess

652
00:30:39,220 --> 00:30:43,530
er bara heimskur, heimskur
vega þyngra af fjölda sem

653
00:30:43,530 --> 00:30:45,840
ekki hafa mörk hennar köflóttur.

654
00:30:45,840 --> 00:30:48,850
Og þetta er það sem er frábær hættulegt
og samtímis frábær öflugur

655
00:30:48,850 --> 00:30:52,560
í C er að við örugglega hafa
aðgang að einhvers staðar í minninu.

656
00:30:52,560 --> 00:30:55,320
Það er allt að okkur, forritari,
sem skrifa upprunalega kóðann

657
00:30:55,320 --> 00:30:59,330
að athuga fjári lengd eitthvað
fylki sem við erum notfæra.

658
00:30:59,330 --> 00:31:00,750
Svo til að vera skýr, það er festa?

659
00:31:00,750 --> 00:31:03,190
Ef við rúlla aftur á þessa
kóða, ég ætti ekki bara að

660
00:31:03,190 --> 00:31:08,000
breyta lengd bar, hvað
annars ætti ég að haka?

661
00:31:08,000 --> 00:31:10,620
Hvað annað ætti ég að gera til að
koma í veg fyrir þessa árás algjörlega?

662
00:31:10,620 --> 00:31:14,110
Ég vil ekki að bara í blindni segja
sem þú ættir að afrita eins mörg bæti

663
00:31:14,110 --> 00:31:16,140
eins og er lengd bar.

664
00:31:16,140 --> 00:31:18,910
Ég vil segja, afrita og
margir bæti sem eru í bar

665
00:31:18,910 --> 00:31:24,090
upp í úthlutað
minni, eða 12 hámarks.

666
00:31:24,090 --> 00:31:27,450
Þannig að ég þarf einhvers konar ef ástand
sem gerir að athuga lengd bar,

667
00:31:27,450 --> 00:31:32,800
en ef það fer yfir 12, við bara harður kóða
12 sem hámarks mögulega fjarlægð.

668
00:31:32,800 --> 00:31:35,910
Annars svokallaða stuðpúða
flæða árás getur gerst.

669
00:31:35,910 --> 00:31:38,451
Á the botn af þeim glærum,
ef þú ert forvitinn að lesa meira

670
00:31:38,451 --> 00:31:41,200
er í raun upprunalega grein
ef þú vilt kíkja.

671
00:31:41,200 --> 00:31:44,550
>> En nú, meðal verð
greitt hér var inefficiencies.

672
00:31:44,550 --> 00:31:46,680
Svo það var fljótur
lágt líta á það

673
00:31:46,680 --> 00:31:49,709
vandamál geta komið upp nú þegar við
hafa aðgang að minni tölvunnar.

674
00:31:49,709 --> 00:31:51,750
En annað vandamál við
þegar lenti á mánudag

675
00:31:51,750 --> 00:31:53,800
var bara óhagkvæmni
af tengda listanum.

676
00:31:53,800 --> 00:31:56,019
Við erum aftur að línulegum tíma.

677
00:31:56,019 --> 00:31:57,560
Við höfum ekki lengur aðlægur array.

678
00:31:57,560 --> 00:31:58,980
Við höfum ekki handahófi aðgang.

679
00:31:58,980 --> 00:32:00,710
Við getum ekki notað ferningur krappi tákn.

680
00:32:00,710 --> 00:32:04,590
Við höfum bókstaflega að nota while lykkju
eins og einn sem ég skrifaði áðan.

681
00:32:04,590 --> 00:32:09,740
En á mánudaginn, hélt að við getum
skríða aftur inn í ríki skilvirkni

682
00:32:09,740 --> 00:32:13,040
ná eitthvað sem er
lógaritmískum kannski, eða besta enn,

683
00:32:13,040 --> 00:32:16,120
kannski jafnvel eitthvað sem er
svokallaða föstu tíma.

684
00:32:16,120 --> 00:32:19,840
Og hvernig getum við gert það með því að nota þessar nýju
verkfæri, þessar tölur, þessar ábendingar,

685
00:32:19,840 --> 00:32:22,210
og þráður hluti af okkar eigin?

686
00:32:22,210 --> 00:32:23,960
Jæja, ætla að
hér eru þetta fullt

687
00:32:23,960 --> 00:32:27,170
talna sem við viljum geyma í
gögn uppbygging og leita vel.

688
00:32:27,170 --> 00:32:30,960
Við getum alveg til baka til viku
tveir, kasta þeim inn í array,

689
00:32:30,960 --> 00:32:33,150
og leita þá nota tvöfaldur leit.

690
00:32:33,150 --> 00:32:34,040
Skipta og sigra.

691
00:32:34,040 --> 00:32:37,720
Og í raun þú skrifar
Tvíundarleit í PSET3,

692
00:32:37,720 --> 00:32:40,100
þar sem þú innleitt þitt finna forrit.

693
00:32:40,100 --> 00:32:40,890
En þú veist hvað.

694
00:32:40,890 --> 00:32:45,060
Það er góður af a fleiri
sniðug leið til að gera þetta.

695
00:32:45,060 --> 00:32:47,390
Það er lítið meira
háþróuð og það kannski

696
00:32:47,390 --> 00:32:50,830
gerir okkur kleift að sjá hvers vegna tvöfaldur
Leitin er svo miklu hraðar.

697
00:32:50,830 --> 00:32:52,980
Í fyrsta lagi skulum kynna
hugmyndin um tré.

698
00:32:52,980 --> 00:32:54,730
Sem jafnvel þó í
veruleika tré konar

699
00:32:54,730 --> 00:32:57,730
vaxa svona, í heimi tölva
vísindi og þeir vaxa konar niður

700
00:32:57,730 --> 00:33:00,830
eins og ættartré, þar sem þú þarft
Amma þín og afi eða mikill afi

701
00:33:00,830 --> 00:33:04,580
eða whatnot efst, patriarcha og
kristin fjölskyldunni, bara einn

702
00:33:04,580 --> 00:33:07,930
svokallaða rót, hnút, hér fyrir neðan
sem eru börn hans,

703
00:33:07,930 --> 00:33:11,442
neðan sem eru börn hans, eða
afkomendur hennar almennt.

704
00:33:11,442 --> 00:33:13,400
Og einhver hangandi burt
neðst í fjölskyldunni

705
00:33:13,400 --> 00:33:16,070
tré, auk þess að vera
yngsti í fjölskyldunni,

706
00:33:16,070 --> 00:33:19,520
getur líka bara verið generically
kallaði blöð trésins.

707
00:33:19,520 --> 00:33:21,800
>> Svo er þetta bara fullt
orðum og skilgreiningum

708
00:33:21,800 --> 00:33:25,790
fyrir eitthvað sem kallast tré í tölvunni
vísindi, líkt og ættartré.

709
00:33:25,790 --> 00:33:28,770
En það er áhugamaður lífum
trjáa, einn sem

710
00:33:28,770 --> 00:33:30,780
er kallað tvöfaldur leita tré.

711
00:33:30,780 --> 00:33:34,380
Og þú getur konar stríða
sundur hvað þetta gerir.

712
00:33:34,380 --> 00:33:37,180
Jæja, það er tvöfaldur í hvaða skilningi?

713
00:33:37,180 --> 00:33:41,455
Hvar er tvöfaldur koma héðan?

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

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

716
00:33:45,961 --> 00:33:47,210
Það er ekki svo mikið annað hvort eða.

717
00:33:47,210 --> 00:33:52,000
Það er meira að hvert hnúður hefur engin
meira en tvö börn, eins og við sjáum hér.

718
00:33:52,000 --> 00:33:54,990
Almennt tree-- og
foreldrar þínir og ömmur

719
00:33:54,990 --> 00:33:57,640
getur haft eins marga krakka eða
grandkids eins og þeir vilja í raun,

720
00:33:57,640 --> 00:34:00,820
og svo til dæmis þar sem við höfum þrjú
börn af því að hægra hnút,

721
00:34:00,820 --> 00:34:05,480
en í tvíundartré, hnúturinn hefur
núll, einn, eða tvö börn hámarks.

722
00:34:05,480 --> 00:34:08,496
Og það er gott eign,
því ef það er lokað með tveimur,

723
00:34:08,496 --> 00:34:10,620
við erum að fara að vera fær um að
fá smá log stöð tvö

724
00:34:10,620 --> 00:34:11,975
aðgerð að fara á hér að lokum.

725
00:34:11,975 --> 00:34:13,350
Þannig að við höfum eitthvað lógaritmískum.

726
00:34:13,350 --> 00:34:14,558
En meira um það í smá stund.

727
00:34:14,558 --> 00:34:19,810
Leita tré þýðir að tölurnar eru
komið er fyrir þannig að vinstri barnsins

728
00:34:19,810 --> 00:34:22,429
gildi er meiri en rót.

729
00:34:22,429 --> 00:34:26,010
Og rétt barn hennar er
stærri en rót.

730
00:34:26,010 --> 00:34:29,290
Með öðrum orðum, ef þú tekur eitthvað af
hnúður, hringirnir í þessari mynd,

731
00:34:29,290 --> 00:34:31,840
og lítur á vinstri hennar
barn og rétt barn hennar,

732
00:34:31,840 --> 00:34:34,739
fyrsta ætti að vera minna en,
annað ætti að vera hærri en.

733
00:34:34,739 --> 00:34:36,159
Svo geðheilsan stöðva 55.

734
00:34:36,159 --> 00:34:37,780
Það sem eftir er barnið er 33.

735
00:34:37,780 --> 00:34:38,620
Það er minna en.

736
00:34:38,620 --> 00:34:40,929
55, rétt barn hennar er 77.

737
00:34:40,929 --> 00:34:41,783
Það er meiri en.

738
00:34:41,783 --> 00:34:43,199
Og það er endurkvæma skilgreiningu.

739
00:34:43,199 --> 00:34:46,480
Við gætum athuga hver og einn þeirra
hnúður og sama mynstur myndi halda.

740
00:34:46,480 --> 00:34:49,389
>> Svo er það gott í
tvíleitartré, er

741
00:34:49,389 --> 00:34:52,204
sem einn, við getum framkvæma það
með strúktúr, bara eins og þetta.

742
00:34:52,204 --> 00:34:54,620
Og jafnvel þó að við erum að henda
hellingur af mannvirkja á þitt,

743
00:34:54,620 --> 00:34:56,560
þeir eru nokkuð
innsæi nú vonandi.

744
00:34:56,560 --> 00:35:00,570
The setningafræði er enn yfirnáttúrulegt fyrir víst,
en innihald hnút í þetta

745
00:35:00,570 --> 00:35:02,786
context-- og við höldum
nota orðið hnút,

746
00:35:02,786 --> 00:35:04,910
hvort sem það er rétthyrningur
á skjánum eða hring,

747
00:35:04,910 --> 00:35:08,970
það er bara sumir almenn gámur,
í þessu tilfelli á tré, eins og einn

748
00:35:08,970 --> 00:35:11,780
við sáum, að við þurfum heiltala
í hverjum tengipunkta

749
00:35:11,780 --> 00:35:15,460
og þá þarf ég tvær ábendingum bendir
til vinstri barnið og hægri barn,

750
00:35:15,460 --> 00:35:16,590
í sömu röð.

751
00:35:16,590 --> 00:35:20,730
Svo það er hvernig við gætum
framkvæma að í strúktúr.

752
00:35:20,730 --> 00:35:22,315
Og hvernig gæti ég framkvæma það í númerið?

753
00:35:22,315 --> 00:35:26,730
Jæja, við skulum taka a fljótur
líta á pínulitlum dæmi.

754
00:35:26,730 --> 00:35:29,820
Það er ekki virk, en ég hef
afrita og líma þessi uppbygging.

755
00:35:29,820 --> 00:35:33,510
Og ef virka minn fyrir tvöfaldur
search tree er kallað leit,

756
00:35:33,510 --> 00:35:36,980
og þetta tekur tvær breytur,
heil tala N og bendi

757
00:35:36,980 --> 00:35:41,400
til hnút, svo bendi á tré
eða bendi á rót á tré,

758
00:35:41,400 --> 00:35:43,482
hvernig get ég fara að leita að N?

759
00:35:43,482 --> 00:35:45,440
Jæja, fyrst, því ég er
að takast á við ábendingum,

760
00:35:45,440 --> 00:35:46,750
Ég ætla að gera geðheilsu stöðva.

761
00:35:46,750 --> 00:35:54,279
Ef tré jafngildir jafngildir null, er N
í þessu tré eða ekki í þessu tré?

762
00:35:54,279 --> 00:35:55,070
Það getur ekki verið, ekki satt?

763
00:35:55,070 --> 00:35:56,870
Ef ég er framhjá null,
það er ekkert þar.

764
00:35:56,870 --> 00:35:59,230
Ég gæti eins vel bara
blindni segja return false.

765
00:35:59,230 --> 00:36:04,050
Ef þú gefur mér ekkert, ég get örugglega ekki
finna allir tala N. Svo hvað gæti ég

766
00:36:04,050 --> 00:36:04,750
athuga nú?

767
00:36:04,750 --> 00:36:12,830
Ég ætla að segja vel annað ef N er
minna en hvað er tré hnút

768
00:36:12,830 --> 00:36:16,300
sem ég hef verið afhent N gildi.

769
00:36:16,300 --> 00:36:20,270
Með öðrum orðum, ef númer ég
að leita að, N, er minna en hnút

770
00:36:20,270 --> 00:36:21,340
að ég er að horfa á.

771
00:36:21,340 --> 00:36:23,190
Og hnúturinn Ég er að leita
á er kallað tré,

772
00:36:23,190 --> 00:36:26,370
og muna frá fyrra dæmi
að fá á verðmæti í músina,

773
00:36:26,370 --> 00:36:28,310
Ég nota arrow tákn.

774
00:36:28,310 --> 00:36:35,960
Þannig að ef n er minna en tré ör
N, ég vil eðli fara eftir.

775
00:36:35,960 --> 00:36:38,590
Hvernig get ég tjáð leita eftir?

776
00:36:38,590 --> 00:36:41,560
Til að vera skýr, ef þetta er
myndin sem um ræðir,

777
00:36:41,560 --> 00:36:44,612
og ég hef verið samþykkt að hæstur
arrow sem er að benda niður.

778
00:36:44,612 --> 00:36:45,570
Það er tré bendi minn.

779
00:36:45,570 --> 00:36:48,060
Ég er að benda á rót trésins.

780
00:36:48,060 --> 00:36:52,100
Og ég er að leita td að
fjöldi 44, geðþótta.

781
00:36:52,100 --> 00:36:55,300
Er 44 minna en eða
meiri en 55 augljóslega?

782
00:36:55,300 --> 00:36:56,360
Svo er það minna en.

783
00:36:56,360 --> 00:36:58,760
Og svo þetta ef gildir ástand.

784
00:36:58,760 --> 00:37:03,981
Svo hugtök, hvað mig langar að
leita næst ef ég er að leita að 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Einmitt, ég vil
leita vinstri barn,

788
00:37:11,100 --> 00:37:12,789
eða vinstri undir-tré af þessari mynd.

789
00:37:12,789 --> 00:37:14,830
Og í raun, láta mig í gegnum
myndin hérna

790
00:37:14,830 --> 00:37:17,770
fyrir aðeins augnablik, síðan
Ég get ekki klóra þetta út.

791
00:37:17,770 --> 00:37:21,150
Ef ég byrja hér á 55, og
Ég veit að verðmæti 44

792
00:37:21,150 --> 00:37:23,180
Ég er að leita að er að
vinstri, það er góður

793
00:37:23,180 --> 00:37:26,010
af eins rífa símaskrána í
helmingur eða rífa tré í tvennt.

794
00:37:26,010 --> 00:37:29,660
Ég hef ekki lengur að hugsa um
þetta allt helmingur trénu.

795
00:37:29,660 --> 00:37:33,270
Og enn, forvitinn í skilmálar af the
uppbyggingu, þetta hérna að

796
00:37:33,270 --> 00:37:36,682
byrjar með 33, sem sjálfu sér
er tvöfaldur leita tré.

797
00:37:36,682 --> 00:37:39,890
Ég sagði orðið endurkvæma áður vegna
reyndar er þetta gagnagrind sem

798
00:37:39,890 --> 00:37:41,707
samkvæmt skilgreiningu er endurkvæma.

799
00:37:41,707 --> 00:37:44,540
Þú gætir hafa tré sem er þetta
stór, en hver og einn barna sinna

800
00:37:44,540 --> 00:37:46,870
táknar tré bara lítið minni.

801
00:37:46,870 --> 00:37:50,910
Í stað þess að vera afa
eða amma, nú er það bara mamma

802
00:37:50,910 --> 00:37:54,300
or-- Ég get ekki say-- ekki mamma
eða pabbi, það væri undarlegt.

803
00:37:54,300 --> 00:37:59,000
Í stað þess að tvö börn þar
væri eins og bróðir og bróðir.

804
00:37:59,000 --> 00:38:01,120
Ný kynslóð af ættartré.

805
00:38:01,120 --> 00:38:02,900
En byggingu, það er sama hugmynd.

806
00:38:02,900 --> 00:38:06,790
Og það kemur í ljós ég er með virka
sem ég get leitað til tvöfaldur leit

807
00:38:06,790 --> 00:38:07,290
tré.

808
00:38:07,290 --> 00:38:08,680
Það er kallað leit.

809
00:38:08,680 --> 00:38:17,870
Ég leita að N í tré arrow vinstri
Annars ef n er meiri en verðmæti

810
00:38:17,870 --> 00:38:18,870
sem ég er nú á.

811
00:38:18,870 --> 00:38:20,800
55 í sögunni í smá stund síðan.

812
00:38:20,800 --> 00:38:23,780
Ég er með fall sem kallast
Leita að ég get bara

813
00:38:23,780 --> 00:38:29,660
fara N þetta og undirmöppum leita
sub-tré og bara aftur

814
00:38:29,660 --> 00:38:30,620
hvað sem svarið.

815
00:38:30,620 --> 00:38:33,530
Annað sem ég hef fengið nokkrar endanlega grunntilvikið hér.

816
00:38:33,530 --> 00:38:35,310
>> Hvað er það sem kemur síðas málið?

817
00:38:35,310 --> 00:38:36,570
Tree er annaðhvort null.

818
00:38:36,570 --> 00:38:39,980
Gildi er ég annaðhvort að leita að er
minna en það eða hærra en það

819
00:38:39,980 --> 00:38:42,610
eða jafn það.

820
00:38:42,610 --> 00:38:44,750
Og ég gæti sagt jafn
jöfn, en rökrétt er það

821
00:38:44,750 --> 00:38:46,500
jafngildir bara að segja annað hér.

822
00:38:46,500 --> 00:38:49,150
Svo satt er hvernig ég finn eitthvað.

823
00:38:49,150 --> 00:38:51,710
Svo vonandi er þetta
enn meira sannfærandi dæmi

824
00:38:51,710 --> 00:38:54,900
en heimskur Sigma virka
við gerðum nokkrar fyrirlestra aftur,

825
00:38:54,900 --> 00:38:58,360
þar sem það var bara eins auðvelt að nota lykkju
að telja upp allar tölur frá einum

826
00:38:58,360 --> 00:39:02,390
við N. hér með gögn uppbygging
sem sjálft er endurkvæmt

827
00:39:02,390 --> 00:39:07,050
skilgreint og endurkvæmt dregin, nú erum við
hafa getu til að tjá okkur

828
00:39:07,050 --> 00:39:09,780
í kóða sem sjálft er endurkvæma.

829
00:39:09,780 --> 00:39:12,580
Þannig að þetta er nákvæmlega sama kóða hér.

830
00:39:12,580 --> 00:39:14,400
>> Svo hvað annað vandamál getum við leyst?

831
00:39:14,400 --> 00:39:18,160
Svo fljótur skref í burtu frá
tré fyrir réttlátur a augnablik.

832
00:39:18,160 --> 00:39:20,130
Hér er sagt, þýska fána.

833
00:39:20,130 --> 00:39:22,020
Og það er greinilega
Mynstur þessari fána.

834
00:39:22,020 --> 00:39:23,811
Og það er hellingur af
fánar í heiminum sem

835
00:39:23,811 --> 00:39:27,560
eru eins einfalt og þetta í skilmálar
af litum og mynstrum.

836
00:39:27,560 --> 00:39:31,930
En geri ráð fyrir að þetta er geymt sem
GIF, eða JPEG, eða punktamynd, eða Ping,

837
00:39:31,930 --> 00:39:34,240
allir grafísku skráarsnið
sem þú ert kunnug,

838
00:39:34,240 --> 00:39:36,460
sem sum hver við erum
spila með í PSET4.

839
00:39:36,460 --> 00:39:41,550
Þetta virðist ekki þess virði að geyma
svartur punkta, svartur pixla, svartur punkta,

840
00:39:41,550 --> 00:39:44,790
punktur, punktur, punktur, allt fullt af
svartur punktar fyrir fyrsta scanline,

841
00:39:44,790 --> 00:39:47,430
eða röð, þá er allt fullt af
sama, þá er allt fullt

842
00:39:47,430 --> 00:39:49,530
á sama, og þá
allt fullt af rauðum punktum,

843
00:39:49,530 --> 00:39:53,020
rauður pixlar, rauður pixlar, þá heild
fullt af gulum dílar, gult, ekki satt?

844
00:39:53,020 --> 00:39:55,050
>> Það er svo óhagkvæmni hér.

845
00:39:55,050 --> 00:39:59,040
Hvernig myndir þú innsæi
þjappa þýska fána

846
00:39:59,040 --> 00:40:01,320
ef að innleiða það sem skrá?

847
00:40:01,320 --> 00:40:04,940
Eins hvaða upplýsingar við getum ekki
nennir að geyma á diski til

848
00:40:04,940 --> 00:40:08,040
að minnka stærð okkar frá eins
megabæti á kílóbæti, eitthvað

849
00:40:08,040 --> 00:40:09,430
minni?

850
00:40:09,430 --> 00:40:13,130
Þar liggur offramboð
hér til að vera ljóst?

851
00:40:13,130 --> 00:40:13,880
Hvað getur þú gert?

852
00:40:13,880 --> 00:40:14,380
Já?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Nákvæmlega.

855
00:40:21,970 --> 00:40:24,550
Hvers vegna ekki frekar en muna
litur hverjum fjári pixla

856
00:40:24,550 --> 00:40:28,200
bara eins og þú ert að gera í PSET4
með punktamynd skrá snið,

857
00:40:28,200 --> 00:40:32,060
hví þú ekki tákna bara
Lengst til vinstri dálkur dílar, til dæmis

858
00:40:32,060 --> 00:40:35,370
fullt af svörtum punktum, fullt
af rauðu, og fullt af gulum,

859
00:40:35,370 --> 00:40:39,210
og þá bara einhvern veginn umrita
Hugmyndin um að endurtaka þetta 100 sinnum

860
00:40:39,210 --> 00:40:41,020
eða endurtaka þetta 1.000 sinnum?

861
00:40:41,020 --> 00:40:43,430
Þar sem 100 eða 1000 er
bara heiltala, svo þú

862
00:40:43,430 --> 00:40:47,290
er hægt að fá í burtu með aðeins einni tölu
í stað þess að hundruð eða þúsundir

863
00:40:47,290 --> 00:40:48,270
viðbótarútgáfu pixlar.

864
00:40:48,270 --> 00:40:50,990
Og reyndar, það er hvernig við
gæti þjappa þýska fána.

865
00:40:50,990 --> 00:40:51,490
Og

866
00:40:51,490 --> 00:40:53,470
Nú hvað um franska fána?

867
00:40:53,470 --> 00:40:58,930
Og smá einhvers konar
andlegt æfing, sem merkja

868
00:40:58,930 --> 00:41:01,040
að þjappa meira á diski?

869
00:41:01,040 --> 00:41:05,720
Þýska flag eða French
merkja, ef við tökum þessi nálgun?

870
00:41:05,720 --> 00:41:08,490
Þýska flag, vegna þess að það er
meira lárétt offramboð.

871
00:41:08,490 --> 00:41:12,190
Og af ásettu ráði, margir grafísku skrá
snið virka örugglega eins skanna línur

872
00:41:12,190 --> 00:41:12,830
lárétt.

873
00:41:12,830 --> 00:41:14,674
Þeir gætu unnið
lóðrétt, bara mannkynið

874
00:41:14,674 --> 00:41:17,090
ákvað ár síðan að við munum
almennt hugsa um hlutina röð

875
00:41:17,090 --> 00:41:18,880
fyrir röð í stað dálk eftir dálk.

876
00:41:18,880 --> 00:41:20,820
Svo reyndar ef þú varst
að líta á skrá

877
00:41:20,820 --> 00:41:24,670
stærð þýska fána og frönsku
merkja, svo lengi sem upplausn er

878
00:41:24,670 --> 00:41:27,530
það sama, sama breidd
og hæð, þetta

879
00:41:27,530 --> 00:41:31,580
hér er að fara að vera stærri, vegna þess að þú
að endurtaka þig þrisvar sinnum.

880
00:41:31,580 --> 00:41:35,570
Þú verður að gefa blár, endurtaka
sjálfur, hvítur, endurtaka þig, rauður,

881
00:41:35,570 --> 00:41:36,740
endurtaka þig.

882
00:41:36,740 --> 00:41:39,000
Þú getur ekki bara farið allt
leiðin til hægri.

883
00:41:39,000 --> 00:41:41,200
Og eins og til hliðar, til að gera
hreinsa þjöppun

884
00:41:41,200 --> 00:41:43,910
er alls staðar, ef þau eru
fjórir rammar frá video-- þú

885
00:41:43,910 --> 00:41:45,890
gæti muna að bíómynd
eða vídeó er almennt

886
00:41:45,890 --> 00:41:47,286
eins 29 eða 30 rammar á sekúndu.

887
00:41:47,286 --> 00:41:50,410
Það er eins og lítið selbiti bók þar þig
bara sjá mynd, mynd, mynd, mynd,

888
00:41:50,410 --> 00:41:54,410
mynd bara frábær fljótur svo það lítur út eins og
leikarar á skjánum eru að flytja.

889
00:41:54,410 --> 00:41:57,130
Hér er Bumble Bee á
toppur af fullt af blómum.

890
00:41:57,130 --> 00:41:59,790
Og þó það gæti verið eins konar
erfitt að sjá við fyrstu sýn,

891
00:41:59,790 --> 00:42:04,020
það eina færa í
þetta bíómynd er flugan.

892
00:42:04,020 --> 00:42:06,880
>> Hvað er heimsk um að geyma
video uncompressed?

893
00:42:06,880 --> 00:42:11,420
Það er góður af a úrgangs til að geyma vídeó
og fjórum næstum eins myndir sem

894
00:42:11,420 --> 00:42:13,670
mismunandi aðeins að því marki sem þar flugan er.

895
00:42:13,670 --> 00:42:16,280
Er hægt að henda flest
af þeim upplýsingum

896
00:42:16,280 --> 00:42:20,190
og muna aðeins, til dæmis,
fyrsta ramma og síðasta ramma,

897
00:42:20,190 --> 00:42:22,180
lykill rammar ef þú hefur
heyrt orðið,

898
00:42:22,180 --> 00:42:24,337
og bara geyma í
miðja þar sem bí er.

899
00:42:24,337 --> 00:42:26,170
Og þú þarft ekki að
geyma öll bleiku,

900
00:42:26,170 --> 00:42:28,330
og bláa, og
Græn gildi eins vel.

901
00:42:28,330 --> 00:42:31,200
Svo er þetta aðeins segja að
þjöppun er alls staðar.

902
00:42:31,200 --> 00:42:34,900
Það er tækni sem við notum oft
eða taka sem sjálfsögðum hlut þessa dagana.

903
00:42:34,900 --> 00:42:38,750
>> En hvernig gera þú þjappa texta?

904
00:42:38,750 --> 00:42:40,450
Hvernig gera þú fara óður þjappa texta?

905
00:42:40,450 --> 00:42:45,410
Jæja, hver persóna í
Ascii er eitt bæti, eða átta bita.

906
00:42:45,410 --> 00:42:47,360
Og það er góður af heimsk, ekki satt?

907
00:42:47,360 --> 00:42:51,160
Vegna þess að þú skrifar líklega
og E og ég og O og U mikið

908
00:42:51,160 --> 00:42:55,270
oftar en eins W eða Q eða Z,
eftir því á hvaða tungumáli

909
00:42:55,270 --> 00:42:56,610
þú ert að skrifa örugglega.

910
00:42:56,610 --> 00:42:59,600
Og svo hvers vegna erum við að nota
átta bitar fyrir hvert bréf,

911
00:42:59,600 --> 00:43:02,040
þar á meðal amk
Vinsælast bréf, ekki satt?

912
00:43:02,040 --> 00:43:05,300
Hvers vegna ekki að nota færri bita fyrir
Super vinsæll bréf,

913
00:43:05,300 --> 00:43:07,760
eins og E, það sem þú giska
fyrst í Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
og nota fleiri bita fyrir
því minna vinsæll bréf?

915
00:43:10,450 --> 00:43:10,950
Hvers vegna?

916
00:43:10,950 --> 00:43:13,130
Vegna þess að við erum bara að fara að
nota þá sjaldnar.

917
00:43:13,130 --> 00:43:15,838
>> Jæja, það kemur í ljós að það hefur
verið reynt að gera þetta.

918
00:43:15,838 --> 00:43:18,630
Og ef þú manst frá bekk
skóla eða menntaskóla, Morse kóða.

919
00:43:18,630 --> 00:43:20,400
Morse kóða hefur punkta
og bandstrik sem hægt er að

920
00:43:20,400 --> 00:43:24,270
flutt um þráð sem
hljóð eða merki um einhvers konar.

921
00:43:24,270 --> 00:43:25,930
En Morse kóða er frábær hreint.

922
00:43:25,930 --> 00:43:29,010
Það er góður af a tvöfaldur kerfi í
að þú hafir punkta eða bandstrik.

923
00:43:29,010 --> 00:43:30,977
En ef þú sérð, til dæmis, tveir punktar.

924
00:43:30,977 --> 00:43:33,810
Eða ef þú heldur aftur til rekstraraðila
sem fer eins og píp, píp, píp,

925
00:43:33,810 --> 00:43:36,760
píp, hitting smá gikkur
sem sendir merki,

926
00:43:36,760 --> 00:43:40,360
ef þú, viðtakandinn fær tvo
punktar, hvað skilaboð hefur þú fengið?

927
00:43:40,360 --> 00:43:43,490
Alveg handahófskennt.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Eða hvað about-- eða ég?

931
00:43:47,500 --> 00:43:49,570
Kannski var það bara tvö til hægri E er?

932
00:43:49,570 --> 00:43:52,480
Svo er það þetta vandamál
af decodability með Morse

933
00:43:52,480 --> 00:43:54,890
númer, þar nema
maður að senda þér skilaboð

934
00:43:54,890 --> 00:43:59,510
reyndar þagnar svo þú getur raða á
sjá eða heyra bil milli bókstafa,

935
00:43:59,510 --> 00:44:02,990
það er ekki nóg bara að
senda straum af núllum og sjálfur,

936
00:44:02,990 --> 00:44:05,610
eða punkta og bandstrik,
vegna þess að það er tvíræðni.

937
00:44:05,610 --> 00:44:08,640
E er einn punktur, þannig að ef þig
sjá tvær punkta eða heyra tvær punkta,

938
00:44:08,640 --> 00:44:11,254
kannski er það tveimur E eða kannski er það einn I.

939
00:44:11,254 --> 00:44:13,670
Þannig að við þurfum að kerfi sem er a
lítið meira snjall en það.

940
00:44:13,670 --> 00:44:16,851
Svo maður að nafni Huffman ár
síðan kom upp með nákvæmlega þetta.

941
00:44:16,851 --> 00:44:18,600
Þannig að við erum bara að fara
að taka a fljótur tillit

942
00:44:18,600 --> 00:44:20,114
hvernig tré eru germane að þessu.

943
00:44:20,114 --> 00:44:22,530
Segjum að þetta er einhver
heimskur skilaboðin sem þú vilt senda,

944
00:44:22,530 --> 00:44:26,342
samanstendur af aðeins A, B, D C er s og E er,
en það er mikið offramboð hér.

945
00:44:26,342 --> 00:44:27,550
Það er ekki ætlað að vera á ensku.

946
00:44:27,550 --> 00:44:28,341
Það er ekki dulkóðuð.

947
00:44:28,341 --> 00:44:30,540
Það er bara heimskulegt skilaboð
með fullt af endurtekningu.

948
00:44:30,540 --> 00:44:34,010
Svo ef þú telur í raun út öllum
A er, B er, C er, D's, og E er, hér er

949
00:44:34,010 --> 00:44:34,890
tíðni.

950
00:44:34,890 --> 00:44:37,800
20% af bréfum eru
A er 45% af bréfum

951
00:44:37,800 --> 00:44:39,660
eru E, og þrír aðrir tíðni.

952
00:44:39,660 --> 00:44:41,960
Við talin þar upp með höndunum
og bara gerði stærðfræðina.

953
00:44:41,960 --> 00:44:44,579
>> Svo kemur í ljós að
Huffman, sumir tími síðan,

954
00:44:44,579 --> 00:44:46,620
komust að því að, þú veist
hvað, ef ég byrja að byggja

955
00:44:46,620 --> 00:44:51,172
tré eða skógur af trjám, ef þú vilt,
eins og hér segir, ég get gert eftirfarandi.

956
00:44:51,172 --> 00:44:53,880
Ég ætla að gefa hnút við hvert
af bréfum sem mér þykir vænt um

957
00:44:53,880 --> 00:44:55,530
og ég ætla að geyma
inni hnút

958
00:44:55,530 --> 00:44:58,610
tíðni sem fleytitölu
gildi, eða þú getur notað það sem N líka,

959
00:44:58,610 --> 00:45:00,210
en við verðum bara að nota fljóta hér.

960
00:45:00,210 --> 00:45:03,100
Og algrím sem
hann lagði er að þú

961
00:45:03,100 --> 00:45:07,210
taka þetta skógur einum hnút
tré, svo frábær stutt tré,

962
00:45:07,210 --> 00:45:11,920
og þú byrjar að tengja þá með
Nýir, nýja foreldra, ef þú vilt.

963
00:45:11,920 --> 00:45:16,150
Og þú gerir þetta með því að velja
tveir minnstu tíðni í einu.

964
00:45:16,150 --> 00:45:18,110
Svo ég tók 10% og 10%.

965
00:45:18,110 --> 00:45:19,090
Ég að búa til nýjan hnút.

966
00:45:19,090 --> 00:45:20,910
Og ég kalla nýja hnút 20%.

967
00:45:20,910 --> 00:45:22,750
>> Sem tveir hnútar ég sameinað næst?

968
00:45:22,750 --> 00:45:23,810
Það er svolítið óljós.

969
00:45:23,810 --> 00:45:26,643
Svo er nokkur horn tilvikum að það
íhuga, en að halda nokkuð,

970
00:45:26,643 --> 00:45:29,300
Ég ætla að velja 20% -
Ég hunsa nú börnin.

971
00:45:29,300 --> 00:45:33,640
Ég ætla að velja 20% og
15% og draga tvær nýjar brúnir.

972
00:45:33,640 --> 00:45:35,624
Og nú sem tveir hnútar
ekki ég sameinað rökrétt?

973
00:45:35,624 --> 00:45:38,540
Hunsa öll börn, allar
barnabörn, bara líta á rætur

974
00:45:38,540 --> 00:45:39,070
núna.

975
00:45:39,070 --> 00:45:42,220
Hvaða tveir hnútar á ég binda saman?

976
00:45:42,220 --> 00:45:44,530
Point tvö og 0.35.

977
00:45:44,530 --> 00:45:45,890
Svo láta mig draga tvær nýjar brúnir.

978
00:45:45,890 --> 00:45:47,570
Og þá hef ég aðeins fengið einn vinstri.

979
00:45:47,570 --> 00:45:48,650
Svo hér er tré.

980
00:45:48,650 --> 00:45:51,160
Og það er verið dregin vísvitandi
að líta svona nokkuð,

981
00:45:51,160 --> 00:45:55,870
en eftir því að brúnir hafa
Einnig hefur verið merkt núll og einn.

982
00:45:55,870 --> 00:45:59,510
Svo öll á vinstri brúnir eru núll
geðþótta, en stöðugt.

983
00:45:59,510 --> 00:46:01,170
Allt rétt brúnir eru þau.

984
00:46:01,170 --> 00:46:05,070
>> Og svo hvað Hoffman lagt er,
ef þú vilt að tákna B,

985
00:46:05,070 --> 00:46:10,080
frekar en að tákna fjölda 66 eins og
ASCII sem er átta allt bits,

986
00:46:10,080 --> 00:46:13,360
þú veist hvað, bara geyma
mynstur núll, núll, núll,

987
00:46:13,360 --> 00:46:17,030
núll, því það er leiðin
frá trénu mínu, tré Mr Huffman er,

988
00:46:17,030 --> 00:46:18,600
að blaða frá rót.

989
00:46:18,600 --> 00:46:20,970
Ef þú vilt geyma a
E, hins vegar ekki

990
00:46:20,970 --> 00:46:26,290
senda átta bita sem jafngilda E.
Þess í stað senda hvaða mynstur bita?

991
00:46:26,290 --> 00:46:26,890
Einn.

992
00:46:26,890 --> 00:46:30,410
Og hvað er gott um þetta er
að E er vinsælasta bréf,

993
00:46:30,410 --> 00:46:32,340
og þú ert að nota
Stysta póstnúmer fyrir hana.

994
00:46:32,340 --> 00:46:34,090
Næsta Vinsælasta
bréf lítur út eins og það

995
00:46:34,090 --> 00:46:37,380
var A. Og svo hversu margir bitar
gerði hann leggja nota fyrir það?

996
00:46:37,380 --> 00:46:38,270
Núll, einn.

997
00:46:38,270 --> 00:46:41,060
>> Og vegna þess að það er hrint í framkvæmd
eins og þetta tré, fyrir nú

998
00:46:41,060 --> 00:46:43,350
láta mig mæla fyrir það er
engin tvíræðni eins og í Morse

999
00:46:43,350 --> 00:46:46,090
númer, því öll að
bréf sem þér þykir vænt um

1000
00:46:46,090 --> 00:46:48,780
eru í lok þessara brúnir.

1001
00:46:48,780 --> 00:46:50,580
Svo er það bara einn
umsókn um tré.

1002
00:46:50,580 --> 00:46:52,538
Þetta is-- og ég veifa
hönd mín á þetta hvernig þér

1003
00:46:52,538 --> 00:46:55,570
might framkvæma þetta sem C byggingu.

1004
00:46:55,570 --> 00:46:58,260
Við þurfum bara að sameina
tákn, eins og bleikju,

1005
00:46:58,260 --> 00:46:59,910
og tíðni í vinstri og hægri.

1006
00:46:59,910 --> 00:47:02,510
En við skulum líta á tvo
endanlegar dæmi sem þú munt

1007
00:47:02,510 --> 00:47:06,070
fá alveg kunnugur eftir
quiz núll í Heimadæmi fimm.

1008
00:47:06,070 --> 00:47:09,210
>> Svo er það að gögn uppbygging
þekktur sem kjötkássa töflunni.

1009
00:47:09,210 --> 00:47:12,247
Og kjötkássa borð er góður af
er kælt í að það hefur hópa.

1010
00:47:12,247 --> 00:47:14,830
Og ætla það er fjórum fötunum
hér, aðeins fjórum eyða rými.

1011
00:47:14,830 --> 00:47:20,830
Hér er þilfari á spil, og hér er
Club, Spade, club, demöntum, club,

1012
00:47:20,830 --> 00:47:25,960
demöntum, club, demöntum,
clubs-- svo er þetta handahófi.

1013
00:47:25,960 --> 00:47:30,330
Hearts, hearts-- þannig að ég er
bucketizing öllum aðföngum hér.

1014
00:47:30,330 --> 00:47:32,430
Og a kjötkássa borð þarf
að líta á hjálpina,

1015
00:47:32,430 --> 00:47:34,850
og þá setja það í ákveðinn
setja miðað við það sem þú sérð.

1016
00:47:34,850 --> 00:47:35,600
Það er reiknirit.

1017
00:47:35,600 --> 00:47:37,980
Og ég var með frábær
einfalt sjón reiknirit.

1018
00:47:37,980 --> 00:47:40,030
Það erfiðasta hluta sem var
muna hvað myndirnar voru.

1019
00:47:40,030 --> 00:47:41,590
Og þá er það fjórum samtals hluti.

1020
00:47:41,590 --> 00:47:45,440
>> Nú stafla voru vaxandi, sem
er vísvitandi hönnun hlutur hér.

1021
00:47:45,440 --> 00:47:46,540
En hvað annað gæti ég gert?

1022
00:47:46,540 --> 00:47:49,080
Svo í raun hér höfum við
fullt af gamla skólanum exam bækur.

1023
00:47:49,080 --> 00:47:51,240
Segjum sem svo að fullt af
nemendur nöfn eru hér.

1024
00:47:51,240 --> 00:47:52,570
Hér er stærri kjötkássa borð.

1025
00:47:52,570 --> 00:47:54,867
Í stað þess að fjórum fötu,
Ég hef, við skulum segja 26.

1026
00:47:54,867 --> 00:47:57,950
Og við vildum ekki að fara að taka lán 26
hlutina frá utanaðkomandi [? Annenberg?], Svo

1027
00:47:57,950 --> 00:48:00,289
hér er fimm að tákna
A í gegnum Ö Og ef ég

1028
00:48:00,289 --> 00:48:03,580
sjá nemandi hét byrjar A,
Ég ætla að setja hans eða quiz hana þar.

1029
00:48:03,580 --> 00:48:08,850
Ef einhver byrjar með C, þarna,
A-- raun, vildi ekki gera það.

1030
00:48:08,850 --> 00:48:10,060
B fer hérna.

1031
00:48:10,060 --> 00:48:13,390
Svo ég hef fengið A og B og C. Og
nú er hér annar nemandi.

1032
00:48:13,390 --> 00:48:16,212
En ef þetta kjötkássa borð er
útfærð með fjölda,

1033
00:48:16,212 --> 00:48:17,920
Ég er góður af ruglaður
á þessum tímapunkti, ekki satt?

1034
00:48:17,920 --> 00:48:19,510
Ég þarf svona til að setja þetta einhversstaðar.

1035
00:48:19,510 --> 00:48:24,380
>> Svo ein leið sem ég get leyst þetta er allt
rétt, A er upptekinn, B er upptekinn, C er upptekinn.

1036
00:48:24,380 --> 00:48:28,880
Ég ætla að setja hann í D. Svo á
fyrst ég handahófi augnablik aðgangur

1037
00:48:28,880 --> 00:48:31,064
að hvert fötunum fyrir nemendur.

1038
00:48:31,064 --> 00:48:33,230
En nú er eins konar Devolved
í eitthvað línuleg,

1039
00:48:33,230 --> 00:48:36,750
því ef ég vil leita að einhverjum
Hvaða nafn byrjar með, athuga ég hér.

1040
00:48:36,750 --> 00:48:38,854
En ef þetta er ekki A
nemandi Ég er að leita að,

1041
00:48:38,854 --> 00:48:41,520
Ég hef konar að byrja að skoða
í fötunum, því það sem ég gerði

1042
00:48:41,520 --> 00:48:44,530
var svona línulega
rannsaka gögn uppbygging.

1043
00:48:44,530 --> 00:48:47,710
A heimskur leið til að segja bara að líta
í fyrsta boði opnun,

1044
00:48:47,710 --> 00:48:51,850
og setja sem plan B, ef svo má segja,
eða áætlun D í þessu tilviki er gildi

1045
00:48:51,850 --> 00:48:53,340
í þeim stað í staðinn.

1046
00:48:53,340 --> 00:48:56,470
Þetta er bara þannig að ef þú hefur
fékk 26 stöðum og enga nemendur

1047
00:48:56,470 --> 00:49:00,600
með nafni Q eða Z, eða eitthvað svoleiðis
að minnsta kosti að þú ert að nota plássið.

1048
00:49:00,600 --> 00:49:03,140
>> En við höfum þegar séð meira
snjall lausnir hér, ekki satt?

1049
00:49:03,140 --> 00:49:04,870
Hvað myndir þú gera í staðinn
ef þú ert með árekstri?

1050
00:49:04,870 --> 00:49:06,670
Ef tveir menn hafa
nafn A, hvað myndi

1051
00:49:06,670 --> 00:49:09,160
hafa verið betri eða fleiri
innsæi lausn en bara

1052
00:49:09,160 --> 00:49:12,840
Setja þar sem D er ætlað að vera?

1053
00:49:12,840 --> 00:49:14,810
Hvers vegna get ég ekki farið bara
utan [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
eins malloc, annan hnút, setja það
hér, og þá setja það nemandi hér.

1055
00:49:19,960 --> 00:49:22,120
Þannig að ég hef í raun
einhvers konar fylki,

1056
00:49:22,120 --> 00:49:25,590
eða kannski meira glæsilegur og við erum
farin að sjá tengda lista.

1057
00:49:25,590 --> 00:49:29,520
>> Og svo er kjötkássa borð uppbygging
sem gæti líta bara eins og þetta,

1058
00:49:29,520 --> 00:49:33,900
en meira snjall, þú eitthvað sem kallast
sérstakt chaining, þar a kjötkássa borð

1059
00:49:33,900 --> 00:49:38,340
einfaldlega er fylki, sem hver um
sem þættir er ekki tala,

1060
00:49:38,340 --> 00:49:40,470
er sjálf tengd lista.

1061
00:49:40,470 --> 00:49:45,080
Þannig að þú færð frábær fljótur aðgangur
ákvörðun um hvar á að kjötkássa gildi þitt til.

1062
00:49:45,080 --> 00:49:48,059
Líkt með spil td
Ég gerði frábær fljótur ákvarðanir.

1063
00:49:48,059 --> 00:49:49,600
Hearts fer hér, demöntum fer hér.

1064
00:49:49,600 --> 00:49:52,180
Sama hér, A fer hér,
D fer hér, B fer hér.

1065
00:49:52,180 --> 00:49:55,740
Svo frábær fljótur uppflettinga og ef
þú verður að hlaupa inn í tilfelli

1066
00:49:55,740 --> 00:49:59,429
hvar þú hefur fengið árekstrar tveggja
fólk með sama nafni, og þá

1067
00:49:59,429 --> 00:50:00,970
þú byrjar bara að tengja þá saman.

1068
00:50:00,970 --> 00:50:03,900
Og kannski þú halda þeim raðað
stafrófsröð, kannski ekki.

1069
00:50:03,900 --> 00:50:05,900
En að minnsta kosti nú höfum við kraft.

1070
00:50:05,900 --> 00:50:10,250
Svo annars vegar höfum við frábær fljótur
stöðug tími, og eins konar línulegum tíma

1071
00:50:10,250 --> 00:50:14,110
ræða ef þessi tengd listum
byrja að fá smá lengi.

1072
00:50:14,110 --> 00:50:16,880
>> Svo af þessu tagi kjánalegt,
geeky brandari árum.

1073
00:50:16,880 --> 00:50:19,590
Á CS50 hakk-þon,
þegar nemendur innrita

1074
00:50:19,590 --> 00:50:22,040
sumir TF eða CA á hverju ári
telur að það er fyndið að setja upp

1075
00:50:22,040 --> 00:50:27,772
merki eins og þetta, þar sem það bara
þýðir að ef nafnið þitt byrjar með A,

1076
00:50:27,772 --> 00:50:28,870
fara þessa leið.

1077
00:50:28,870 --> 00:50:31,110
Ef nafnið þitt byrjar
með B, fara this-- OK,

1078
00:50:31,110 --> 00:50:33,290
það er fyndið kannski seinna í önn.

1079
00:50:33,290 --> 00:50:36,420
En það er önnur
leið til að gera þetta líka.

1080
00:50:36,420 --> 00:50:37,410
Koma aftur til að.

1081
00:50:37,410 --> 00:50:38,600
>> Svo er það þessi uppbygging.

1082
00:50:38,600 --> 00:50:40,420
Og þetta er síðasta vor
uppbygging í dag,

1083
00:50:40,420 --> 00:50:42,400
sem er eitthvað sem kallast Trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, sem af einhverjum ástæðum er stutt
fyrir sókn, en það er kallað Trie.

1085
00:50:47,140 --> 00:50:51,389
Svo er Trie annar áhugaverður
amalgam af a einhver fjöldi af þessum hugmyndum.

1086
00:50:51,389 --> 00:50:52,930
Það er tré, sem við höfum séð áður.

1087
00:50:52,930 --> 00:50:54,180
Það er ekki tvöfaldur leita tré.

1088
00:50:54,180 --> 00:50:58,410
Það er tré með hvaða fjölda barna,
en hver börnunum í Trie

1089
00:50:58,410 --> 00:51:00,090
er fylki.

1090
00:51:00,090 --> 00:51:04,790
An array af stærð, segja, 26 eða kannski 27
ef þú vilt styðja hyphenated nöfn

1091
00:51:04,790 --> 00:51:06,790
eða úrfellingarmerki í mannanöfnum.

1092
00:51:06,790 --> 00:51:08,280
>> Og svo er þetta gögn uppbygging.

1093
00:51:08,280 --> 00:51:10,290
Og ef þú horfir frá toppi
til botn, eins og ef þú

1094
00:51:10,290 --> 00:51:13,710
líta á the toppur hnút þar, M, er
bendir til lengst til vinstri hlutur þarna,

1095
00:51:13,710 --> 00:51:17,665
sem er síðan A, X, W, E, L, L. Þetta er
bara gagnagrind sem geðþótta

1096
00:51:17,665 --> 00:51:19,120
er að geyma nöfn fólks.

1097
00:51:19,120 --> 00:51:25,720
Og Maxwell er geymt bara með eftirfarandi
a leið array array til array.

1098
00:51:25,720 --> 00:51:30,050
En hvað er ótrúlegt um að Trie er
að, en tengda listanum og jafnvel

1099
00:51:30,050 --> 00:51:34,520
fylki, sá besti sem við höfum nokkru sinni fengið er
línuleg tími eða lógaritmískum tíma í að leita

1100
00:51:34,520 --> 00:51:35,600
einhver upp.

1101
00:51:35,600 --> 00:51:40,530
Í þessum gögnum uppbyggingu Trie, ef
gögn uppbygging minn hefur eitt nafn í það

1102
00:51:40,530 --> 00:51:43,720
og ég er að leita að Maxwell, ég er
fara að finna hann ansi fljótt.

1103
00:51:43,720 --> 00:51:47,910
Ég lít bara fyrir M-A-X-W-E-L-L. Ef
þessi gögn uppbygging, hins vegar

1104
00:51:47,910 --> 00:51:51,830
ef N er milljón, ef það er
milljón nöfn í þessum gögnum uppbyggingu,

1105
00:51:51,830 --> 00:51:57,100
Maxwell er enn að fara að vera
aðgengilegar á eftir aðeins M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
skref.

1107
00:51:58,090 --> 00:52:01,276
Og David-- D-A-V-I-D skref.

1108
00:52:01,276 --> 00:52:03,400
Með öðrum orðum, með því að byggja
gögn uppbygging sem er

1109
00:52:03,400 --> 00:52:07,240
fékk allar þessar fylki, sem allt
sjálfir styðja handahófi aðgang,

1110
00:52:07,240 --> 00:52:11,090
Ég get byrjað að horfa upp fólksins
nefna að nota tíma sem er

1111
00:52:11,090 --> 00:52:14,340
í réttu hlutfalli við ekki að tala
af hlutum í gögn uppbygging,

1112
00:52:14,340 --> 00:52:16,330
eins milljón núverandi nöfn.

1113
00:52:16,330 --> 00:52:20,135
Tíminn sem það tekur mig að finna
M-A-X-W-E-L-L í þessari gögn uppbygging er

1114
00:52:20,135 --> 00:52:22,260
í réttu hlutfalli ekki til
Stærð gögn uppbygging,

1115
00:52:22,260 --> 00:52:25,930
en að lengd nafn.

1116
00:52:25,930 --> 00:52:28,440
Og raunhæft að
nöfnum sem við erum að horfa upp

1117
00:52:28,440 --> 00:52:29,970
ert aldrei að fara að vera brjálaður lengi.

1118
00:52:29,970 --> 00:52:32,600
Kannski hefur einhver með 10 staf
nafn, 20 staf nafn.

1119
00:52:32,600 --> 00:52:33,900
Það er vissulega tímabundið, ekki satt?

1120
00:52:33,900 --> 00:52:37,110
Það er mannleg á jörðinni sem
hefur lengstu mögulegu nafn,

1121
00:52:37,110 --> 00:52:39,920
en það nafn er fasti
gildi lengd, ekki satt?

1122
00:52:39,920 --> 00:52:41,980
Það breytist ekki í hvaða skilningi.

1123
00:52:41,980 --> 00:52:45,090
Svo á þennan hátt, höfum við
náð gögn uppbygging

1124
00:52:45,090 --> 00:52:47,800
sem er stöðug tími líta upp.

1125
00:52:47,800 --> 00:52:50,670
Það þýðir að taka nokkur skref
eftir lengd inntak,

1126
00:52:50,670 --> 00:52:54,250
en ekki tölu nafns
í gögn uppbygging.

1127
00:52:54,250 --> 00:52:58,700
Þannig að ef við tvöfalda fjölda nafna
á næsta ári frá milljarð til tvo milljarða,

1128
00:52:58,700 --> 00:53:03,720
niðurstaða Maxwell er að fara að taka
nákvæmlega sama fjölda sjö skrefum

1129
00:53:03,720 --> 00:53:04,650
að finna hann.

1130
00:53:04,650 --> 00:53:08,810
Og svo við virðast hafa náð
okkar Gral keyra tíma.

1131
00:53:08,810 --> 00:53:10,860
>> Svo a par af fljótur tilkynningum.

1132
00:53:10,860 --> 00:53:11,850
Quiz núll er að koma upp.

1133
00:53:11,850 --> 00:53:14,600
Meira um það á heimasíðu námskeiðsins er
á næstu dögum.

1134
00:53:14,600 --> 00:53:17,120
Mánudagur lecture-- það er frí
hér á Harvard á mánudaginn.

1135
00:53:17,120 --> 00:53:18,850
Það er ekki í New Haven,
þannig að við erum að taka í bekknum

1136
00:53:18,850 --> 00:53:20,310
New Haven til fyrirlestur á mánudaginn.

1137
00:53:20,310 --> 00:53:22,550
Allt verður tekið
og streyma lifandi eins og venjulega,

1138
00:53:22,550 --> 00:53:24,900
en við skulum enda í dag
með 30 sekúndu bút

1139
00:53:24,900 --> 00:53:26,910
kallast "Deep Thoughts"
eftir Daven Farnham, sem

1140
00:53:26,910 --> 00:53:30,850
var innblásin síðasta ári með laugardaginn
"Deep Thoughts" Night Live er

1141
00:53:30,850 --> 00:53:35,700
Jack Handy, sem
ætti nú skynsamleg.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Og nú, "Deep
Hugsun "eftir Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Kjötkássa borð.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> Ræðumaður 1: Allt í lagi, þá er það núna.

1147
00:53:47,660 --> 00:53:48,805
Við munum sjá þig í næstu viku.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Til að sjá það í aðgerð.

1150
00:53:56,680 --> 00:53:58,304
Svo skulum taka a líta á það núna.

1151
00:53:58,304 --> 00:53:59,890
Svo hér höfum við óflokkuðu fylki.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, getur þú farið á undan og endurræsa
þetta fyrir einni sekúndu, vinsamlegast.

1153
00:54:04,860 --> 00:54:08,562
Allt í lagi, myndavélar eru veltingur, svo
aðgerð þegar þú ert tilbúin, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Allt í lagi, þannig að það sem við
höfum hér er Óflokkaður array.

1155
00:54:11,020 --> 00:54:13,960
Og ég hef litað alla þá þætti
rautt til að sýna að það er í raun,

1156
00:54:13,960 --> 00:54:14,460
Óflokkaður.

1157
00:54:14,460 --> 00:54:17,960
Svo muna að það fyrsta sem við gerum
er við að raða vinstri helming fylkisins.

1158
00:54:17,960 --> 00:54:20,630
Þá erum við að raða rétt
helmingur fylkisins.

1159
00:54:20,630 --> 00:54:22,830
Og ya-da, ya-da, ya-da,
við sameina þær saman.

1160
00:54:22,830 --> 00:54:24,520
Og við höfum alveg flokkað array.

1161
00:54:24,520 --> 00:54:25,360
Svo er það hvernig Mergesort virkar.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, hó, hó,
skera, skera, skera, skera.

1163
00:54:27,109 --> 00:54:30,130
Doug, þú getur ekki bara ya-da, ya-da,
ya-da, leið gegnum sameiningu tagi.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Ég gerði bara.

1165
00:54:31,970 --> 00:54:32,832
Það er fínt.

1166
00:54:32,832 --> 00:54:33,540
Við ert góður til fara.

1167
00:54:33,540 --> 00:54:34,760
Við skulum halda bara veltingur.

1168
00:54:34,760 --> 00:54:35,380
Svo engu að síður,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Þú þarft að útskýra
það betur en það.

1170
00:54:37,800 --> 00:54:39,999
Það er bara ekki nóg.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, eigum við ekki
þarf að fara aftur til einn.

1172
00:54:41,790 --> 00:54:42,350
Það er fínt.

1173
00:54:42,350 --> 00:54:45,690
Svo engu að síður, ef við höldum áfram með merge--
Ian, við erum í the miðja af kvikmynda.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Ég veit.

1175
00:54:46,612 --> 00:54:49,320
Og við getum ekki bara ya-da, ya-da,
ya-da, í gegnum allt ferlið.

1176
00:54:49,320 --> 00:54:52,200
Þú þarft að útskýra hvernig
tvær hliðar að steypa saman.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: En við höfum nú þegar
útskýrði hvernig tveir sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Þú hefur bara sýnt
þá a sameinast array.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Þeir vita the aðferð.

1180
00:54:56,486 --> 00:54:57,172
Þeir eru í lagi.

1181
00:54:57,172 --> 00:54:58,380
Við höfum farið yfir það tíu sinnum.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Þú sleppt bara rétt yfir það.

1183
00:55:00,330 --> 00:55:03,360
Við erum að fara aftur til einn, þú
getur þú ekki ya-da, ya-da yfir það.

1184
00:55:03,360 --> 00:55:05,480
Allt í lagi, aftur til einn.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Ég verð að fara aftur
gegnum allar renna?

1186
00:55:07,833 --> 00:55:08,332
Guð minn.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Það er eins og í sjötta sinn, Ian.

1189
00:55:13,004 --> 00:55:13,940
Það er fínt.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Allt í lagi.

1191
00:55:15,200 --> 00:55:16,590
Ertu tilbúin?

1192
00:55:16,590 --> 00:55:17,400
Great.

1193
00:55:17,400 --> 00:55:18,950
Aðgerð.