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

2
00:00:10,900 --> 00:00:15,860
>> 1. Előadó: Rendben, tehát ez
CS50 Ez a hét végén öt.

3
00:00:15,860 --> 00:00:19,220
És emlékszem, hogy utoljára
nekilátott a galambász adatok

4
00:00:19,220 --> 00:00:22,310
struktúrák indult, hogy megoldja
problémákat, hogy kezdte el bevezetni

5
00:00:22,310 --> 00:00:25,640
új problémák, de a legfontosabb, hogy ezt
az a fajta threading, hogy mi

6
00:00:25,640 --> 00:00:27,940
kezdett hozzá csomópontok.

7
00:00:27,940 --> 00:00:30,085
Szóval ez persze
egyszeresen láncolt lista.

8
00:00:30,085 --> 00:00:31,960
És egyszeres kapcsolódik,
Úgy értem, nem csak egy

9
00:00:31,960 --> 00:00:33,380
menet között minden egyes ilyen csomópontok.

10
00:00:33,380 --> 00:00:35,890
Kiderült, amit tehetünk cifrább
dolgok, mint kétszeresen láncolt listák

11
00:00:35,890 --> 00:00:38,470
ahol van egy nyíl
mindkét irányban, amely

12
00:00:38,470 --> 00:00:40,320
segíthet bizonyos hatékonyságot.

13
00:00:40,320 --> 00:00:42,000
De ez megoldotta a problémát?

14
00:00:42,000 --> 00:00:43,500
Mi a gond viszont ezt megoldani?

15
00:00:43,500 --> 00:00:46,620
Miért érdekel hétfőn?

16
00:00:46,620 --> 00:00:49,820
Miért, elvileg, nem törődünk hétfőn?

17
00:00:49,820 --> 00:00:50,630
Mit csinal?

18
00:00:50,630 --> 00:00:51,950
>> Közönség: Mi lehet dinamikusan méretét.

19
00:00:51,950 --> 00:00:53,740
>> 1. Előadó: OK, így tudjuk
dinamikusan méretét.

20
00:00:53,740 --> 00:00:54,710
Jól sikerült mind a ketten.

21
00:00:54,710 --> 00:00:57,560
Szóval lehet dinamikusan átméretezni ezt
adatszerkezet, mivel egy sor,

22
00:00:57,560 --> 00:01:00,760
Emlékezzünk, tudnod kell a
priori, hogy mennyi helyet szeretne

23
00:01:00,760 --> 00:01:03,870
és ha kell még egy kis
helyet, te ilyen szerencséje.

24
00:01:03,870 --> 00:01:05,560
Létre kell hozni egy teljesen új tömb.

25
00:01:05,560 --> 00:01:07,893
Meg kell mozgatni az összes
az adatokat az egyik a másikra,

26
00:01:07,893 --> 00:01:10,600
végül szabad a régi tömb
ha tudsz, majd folytassa.

27
00:01:10,600 --> 00:01:13,891
Ami csak úgy érzi, nagyon költséges és nagyon
nem hatékony, és valóban az is.

28
00:01:13,891 --> 00:01:14,890
De ez még nem minden jó.

29
00:01:14,890 --> 00:01:18,180
Mi árat fizetnek, mi volt az egyik
a nyilvánvaló árak is

30
00:01:18,180 --> 00:01:20,550
fizetni egy láncolt lista?

31
00:01:20,550 --> 00:01:22,825
>> Közönség: Meg kell használni
dupla helyet mindegyik.

32
00:01:22,825 --> 00:01:25,200
1. Előadó: Igen, így van szükségünk
legalább kétszer annyi helyet.

33
00:01:25,200 --> 00:01:27,700
Sőt, rájöttem, hogy ez kép
még egy kicsit félrevezető,

34
00:01:27,700 --> 00:01:32,200
mert a CS50 IDE a sok modern
számítógépek, egy mutatót vagy címet

35
00:01:32,200 --> 00:01:33,700
valójában nem négy bájt.

36
00:01:33,700 --> 00:01:36,090
Nagyon gyakran ezek
nap nyolc bájt, amely

37
00:01:36,090 --> 00:01:38,530
: a legalsó
téglalapok ott a valóságban

38
00:01:38,530 --> 00:01:40,900
a fajta kétszer
akkora, mint amit én kiállított,

39
00:01:40,900 --> 00:01:44,409
ami azt jelenti, amit használ háromszor
sok helyet, mint talán van más módon.

40
00:01:44,409 --> 00:01:46,700
Most ugyanabban az időben, vagyunk
Még mindig beszél bájt, ugye?

41
00:01:46,700 --> 00:01:49,140
Mi nem feltétlenül beszél
megabájt vagy gigabájt,

42
00:01:49,140 --> 00:01:51,000
kivéve, ha ezek az adatok struktúrák kap nagy.

43
00:01:51,000 --> 00:01:54,510
>> És így ma elkezdjük vizsgálni
hogyan lehet felfedezni adatok

44
00:01:54,510 --> 00:01:57,310
hatékonyabban, ha a
Valójában az adatok nagyobb lesz.

45
00:01:57,310 --> 00:02:00,360
De nézzük meg, hogy canonicalize
A műveletek első

46
00:02:00,360 --> 00:02:02,460
hogy meg tudod csinálni a következő
típusú adatok struktúrákat.

47
00:02:02,460 --> 00:02:04,790
Szóval olyasmi, mint egy kapcsolt
lista általában támogatja

48
00:02:04,790 --> 00:02:07,514
műveletek, mint a törlés,
helyezze, és keresni.

49
00:02:07,514 --> 00:02:08,639
És mit jelent az, hogy?

50
00:02:08,639 --> 00:02:11,222
Ez csak azt jelenti, hogy általában,
ha az emberek a láncolt lista,

51
00:02:11,222 --> 00:02:14,287
ők vagy valaki más által végrehajtott
funkciók, mint a törlés, betét,

52
00:02:14,287 --> 00:02:16,120
és a keresés, így Ön
valóban tenni valamit

53
00:02:16,120 --> 00:02:18,030
hasznos az adatszerkezet.

54
00:02:18,030 --> 00:02:20,760
Szóval vessünk egy gyors pillantást
meg, hogyan lehet végrehajtani

55
00:02:20,760 --> 00:02:24,530
Néhány kódot egy láncolt lista a következőképpen.

56
00:02:24,530 --> 00:02:27,885
>> Szóval ez csak néhány a C kód,
Nem is egy komplett program

57
00:02:27,885 --> 00:02:29,260
hogy igazán gyorsan felkorbácsolta.

58
00:02:29,260 --> 00:02:32,300
Ez nem online forgalmazás
kódot, mert nem a ténylegesen megtett.

59
00:02:32,300 --> 00:02:33,790
De észre Épp most
egy megjegyzést mondta,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, van valami
ott, pont pont pont, ott valami.

61
00:02:36,130 --> 00:02:38,410
És nézzük csak nézd meg
mi a szaftos részek.

62
00:02:38,410 --> 00:02:40,790
Tehát a sorban három,
Emlékeztetünk arra, hogy ez most

63
00:02:40,790 --> 00:02:45,960
Javasoltuk nyilvánító csomópont utolsó
ideje, az egyik ilyen téglalap alakú tárgyat.

64
00:02:45,960 --> 00:02:48,790
Meg van egy int, hogy fogjuk hívni N,
de nevezhetjük bárminek,

65
00:02:48,790 --> 00:02:51,920
majd a struct csomópont csillagos nevezett következő.

66
00:02:51,920 --> 00:02:55,520
És csak hogy tisztázzuk, hogy a második
vonal, a soros hathengeres, mi ez?

67
00:02:55,520 --> 00:02:57,930
Mit tesz nekünk?

68
00:02:57,930 --> 00:03:01,044
Mert úgy néz ki több
rejtélyes, mint a szokásos változók.

69
00:03:01,044 --> 00:03:02,740
>> Közönség: Azt teszi, hogy mozogni több mint egy.

70
00:03:02,740 --> 00:03:04,650
>> 1. Előadó: Azt teszi, hogy mozogni több mint egy.

71
00:03:04,650 --> 00:03:08,580
És pontosabban,
akkor tárolja a címét

72
00:03:08,580 --> 00:03:11,582
A csomópont, amely azt jelentette, hogy
szemantikailag mellette, igaz?

73
00:03:11,582 --> 00:03:13,540
Szóval ez nem fog
feltétlenül mozognak semmit.

74
00:03:13,540 --> 00:03:15,290
Ez csak fog
értéket tárolnak, amely

75
00:03:15,290 --> 00:03:17,170
lesz a cím
néhány más csomópont,

76
00:03:17,170 --> 00:03:20,810
és ezért mondtunk struct
node csillag, a csillag jelöli

77
00:03:20,810 --> 00:03:22,370
egy mutató, vagy egy címet.

78
00:03:22,370 --> 00:03:26,390
OK, így most, ha feltételezzük, hogy van
Ebben az N elérhető számunkra, és nézzük

79
00:03:26,390 --> 00:03:29,490
Feltételezem, hogy valaki másnak
beilleszteni egy csomó egészek

80
00:03:29,490 --> 00:03:30,400
egy láncolt lista.

81
00:03:30,400 --> 00:03:35,640
És hogy kapcsolódik lista
Rámutatott, hogy néhány ponton

82
00:03:35,640 --> 00:03:39,040
változó nevű lista, amelyet
telt itt, mint a paraméter,

83
00:03:39,040 --> 00:03:43,120
hogyan megy a vonalon
14 végrehajtási keresés?

84
00:03:43,120 --> 00:03:45,990
Más szóval, ha én végrehajtási
függvény, amelynek célja az életben

85
00:03:45,990 --> 00:03:48,889
az, hogy egy int, majd a
elején egy láncolt lista,

86
00:03:48,889 --> 00:03:50,430
hogy egy mutató a láncolt lista.

87
00:03:50,430 --> 00:03:52,992
Mint az első, aki azt hiszem, David
volt önkéntesünk hétfőn,

88
00:03:52,992 --> 00:03:54,700
ő mutat
Az egész láncolt lista,

89
00:03:54,700 --> 00:03:57,820
olyan, mintha mi halad
Dávid az érveink itt.

90
00:03:57,820 --> 00:03:59,990
Hogyan érjük el áthaladó ez a lista?

91
00:03:59,990 --> 00:04:04,640
Nos, kiderült, hogy bár
mutatók viszonylag új most nekünk,

92
00:04:04,640 --> 00:04:07,010
ezt meg tudjuk tenni, viszonylag
egyenesen.

93
00:04:07,010 --> 00:04:09,500
>> Megyek megy előre, és
Kijelentem, ideiglenes változó,

94
00:04:09,500 --> 00:04:12,364
egyezményesen csak megy
hogy hívják mutató vagy PTR,

95
00:04:12,364 --> 00:04:14,030
de lehet nevezni, amit akarsz.

96
00:04:14,030 --> 00:04:16,470
És fogok alaphelyzetbe
azt a kezdetét a lista.

97
00:04:16,470 --> 00:04:20,050
Szóval lehet egyfajta gondolom, ennek a
mint én a tanár a minap,

98
00:04:20,050 --> 00:04:23,580
fajta mutatva valaki
körében emberek önkéntesként.

99
00:04:23,580 --> 00:04:26,470
Szóval egy átmeneti változó, ami
Csak mutatva ugyanezt

100
00:04:26,470 --> 00:04:31,390
hogy a véletlenül nevezték
önkéntes Dávid is rámutatva.

101
00:04:31,390 --> 00:04:35,440
Most, miközben mutató
nem nulla, mert visszahívás

102
00:04:35,440 --> 00:04:40,350
hogy null valamilyen különleges sentinel értéke
A behatároló a lista végén,

103
00:04:40,350 --> 00:04:44,280
így amíg nem vagyok mutatva
földön, mint az utolsó önkéntes

104
00:04:44,280 --> 00:04:47,190
volt, menjünk előre
és tegye a következőket.

105
00:04:47,190 --> 00:04:51,820
Ha pointer-- és most valahogy akarnak
hogy amit tettünk a diák

106
00:04:51,820 --> 00:04:57,410
structure-- ha a mutató melletti pont
equals-- inkább, ha a mutató dot N egyenlő

107
00:04:57,410 --> 00:05:02,290
egyenlő az n változó, a
érv, hogy a már elfogadott,

108
00:05:02,290 --> 00:05:05,370
akkor azt akarom, hogy menjen előre
és azt mondják vissza igaz.

109
00:05:05,370 --> 00:05:11,020
Találtam száma N belsejét
egyik csomópont én láncolt lista.

110
00:05:11,020 --> 00:05:13,500
De a dot már nem
működik ebben az összefüggésben,

111
00:05:13,500 --> 00:05:17,260
mert mutatót, PTR, van
Valóban egy mutató, cím,

112
00:05:17,260 --> 00:05:20,632
mi valójában is csodálatosan
Használja végül egy darab szintaxis

113
00:05:20,632 --> 00:05:22,590
ez a fajta gyártmányú
ösztönösen érzi, és ténylegesen

114
00:05:22,590 --> 00:05:27,870
Használja a nyíl itt, ami azt jelenti, megy
ezt a címet az egész, ott.

115
00:05:27,870 --> 00:05:30,160
Tehát ez nagyon hasonlít a
szellem a dot-üzemeltető,

116
00:05:30,160 --> 00:05:33,860
hanem azért, mert a mutató nem egy pointer
és nem a tényleges struct magát,

117
00:05:33,860 --> 00:05:35,380
csak használja a nyíl.

118
00:05:35,380 --> 00:05:40,620
>> Tehát, ha az aktuális csomópont, hogy én, az
ideiglenes változó, am mutatva

119
00:05:40,620 --> 00:05:43,060
nem N, mit akarok csinálni?

120
00:05:43,060 --> 00:05:45,910
Nos, az én emberi önkéntesek
hogy mi volt itt a minap,

121
00:05:45,910 --> 00:05:49,710
Ha az első emberi nem az általam
szeretnénk, és talán a második ember nem

122
00:05:49,710 --> 00:05:52,660
Az egyik azt akarom, és a harmadik, én
kell tartani fizikai mozgatása.

123
00:05:52,660 --> 00:05:54,690
Mint hogyan lépek a listában?

124
00:05:54,690 --> 00:05:57,470
Amikor volt egy tömb,
csak tettem, mintha én plus plus.

125
00:05:57,470 --> 00:06:03,660
De ebben az esetben elegendő, ha
nem mutató, kap, mutató, a következő.

126
00:06:03,660 --> 00:06:07,580
Más szóval, a következő mező
olyan, mint minden a bal kezében

127
00:06:07,580 --> 00:06:10,880
hogy emberi önkéntesek hétfőn
-a használta, hogy rámutasson néhány más csomóponton.

128
00:06:10,880 --> 00:06:12,890
Ezek voltak azok a következő szomszédok.

129
00:06:12,890 --> 00:06:17,060
>> Tehát, ha azt akarom, hogy menj végig a listán,
Nem tudok csak tudom plus plus többé,

130
00:06:17,060 --> 00:06:20,120
Azt kell, hogy mondjam helyett
Azt, mutató, folyik

131
00:06:20,120 --> 00:06:24,650
hogy egyenlő függetlenül a következő mező,
A következő mező, a következő mező,

132
00:06:24,650 --> 00:06:28,350
következő mindazoknak bal keze
hogy mi volt a színpadon mutatóeszköz

133
00:06:28,350 --> 00:06:30,000
Egyes későbbi értékeket.

134
00:06:30,000 --> 00:06:32,590
És ha én átjutni
hogy egész iterációnál

135
00:06:32,590 --> 00:06:39,330
és végül, elütöttem null nem rendelkező
megtalált N mégis, én csak vissza hamis.

136
00:06:39,330 --> 00:06:44,100
Szóval megint minden, amit mi csinálunk itt,
mint egy a kép egy perce

137
00:06:44,100 --> 00:06:47,840
kezd mutatva a
a lista elején feltehetően.

138
00:06:47,840 --> 00:06:50,970
És akkor ellenőrizze, ez az érték
Keresem egyenlő kilenc?

139
00:06:50,970 --> 00:06:52,650
Ha igen, azt vissza igaz, és kész vagyok.

140
00:06:52,650 --> 00:06:56,450
Ha nem, akkor frissítem a kezem,
AKA mutatót, hogy pont

141
00:06:56,450 --> 00:06:59,540
A következő nyíl helyét, és
akkor a következő nyíl helyét,

142
00:06:59,540 --> 00:07:00,480
és a következő.

143
00:07:00,480 --> 00:07:03,770
Én egyszerűen csak séta ezt a tömböt.

144
00:07:03,770 --> 00:07:06,010
>> Tehát újra, kit érdekel?

145
00:07:06,010 --> 00:07:07,861
Mint mi ez az összetevő,?

146
00:07:07,861 --> 00:07:10,360
Nos, emlékszem, hogy mi vezetett
fogalmának egy halom, amely

147
00:07:10,360 --> 00:07:15,400
egy absztrakt adattípus, amennyiben ez
nem egy C dolog, hogy ez nem egy CS50 dolog,

148
00:07:15,400 --> 00:07:19,430
ez egy elvont elképzelés, ez az ötlet
egymásra dolgokat egymás tetejére

149
00:07:19,430 --> 00:07:21,820
hogy lehet végrehajtani
fürtök különböző módon.

150
00:07:21,820 --> 00:07:25,600
És egy út javasoltuk volt
egy tömb, vagy egy láncolt lista.

151
00:07:25,600 --> 00:07:29,570
És kiderül, hogy kanonikusan, a
verem támogatja legalább két művelet.

152
00:07:29,570 --> 00:07:32,320
És a buzz szavak push, hogy
nyomja valami a verembe,

153
00:07:32,320 --> 00:07:34,770
mint egy új tálcát a
étkezőben, vagy a pop,

154
00:07:34,770 --> 00:07:39,000
ami azt jelenti, hogy távolítsa el a legfelső
tálcát a verem az étkezőben

155
00:07:39,000 --> 00:07:41,500
hall, majd talán néhány
Más műveletek is.

156
00:07:41,500 --> 00:07:45,770
Tehát hogyan tudnánk szerkezetét meghatározó
hogy mi most hív egy köteg?

157
00:07:45,770 --> 00:07:50,020
>> Nos, mindannyian a szükséges
szintaxis a rendelkezésünkre a C. mondom,

158
00:07:50,020 --> 00:07:53,830
adj egy típus meghatározása
Egy struct belsejében egy köteg,

159
00:07:53,830 --> 00:07:58,030
Azt fogom mondani egy tömb, egy
csomó szám, majd méretét.

160
00:07:58,030 --> 00:08:00,930
Más szóval, ha azt akarom,
végrehajtani ezt a kódot,

161
00:08:00,930 --> 00:08:03,830
hadd menjen, és csak ilyen
felhívni, hogy ez mit mond.

162
00:08:03,830 --> 00:08:06,317
Tehát ez azt mondja, hogy nekem egy
szerkezet, van egy tömbben,

163
00:08:06,317 --> 00:08:09,400
és én nem tudom, mi kapacitása,
ez nyilván valami állandó, hogy én már

164
00:08:09,400 --> 00:08:10,858
máshol definiált, és ez jó.

165
00:08:10,858 --> 00:08:15,260
De tegyük fel, hogy csak egy,
két, három, négy, öt.

166
00:08:15,260 --> 00:08:16,700
Tehát kapacitása 5.

167
00:08:16,700 --> 00:08:21,730
Ez az elem belső én
struktúrát kell hívott számokat.

168
00:08:21,730 --> 00:08:24,020
És akkor kell egy
egyéb változó láthatóan

169
00:08:24,020 --> 00:08:27,814
nevű méretű, hogy kezdetben megyek
kikötni nullára inicializálunk.

170
00:08:27,814 --> 00:08:29,730
Ha nincs semmi
a verem, mérete nulla,

171
00:08:29,730 --> 00:08:31,420
és ez szemét értékeket számokban.

172
00:08:31,420 --> 00:08:33,450
Fogalmam sincs, hogy mi van benne, csak még.

173
00:08:33,450 --> 00:08:36,059
>> Tehát ha azt szeretné, hogy álljon
valamit a verembe,

174
00:08:36,059 --> 00:08:40,780
hiszem, hívja a funkciót push, és
Mondom tolja 50, mint a 50-,

175
00:08:40,780 --> 00:08:44,090
ahol javasolna
Én felhívni, hogy ebben a tömbben?

176
00:08:44,090 --> 00:08:47,124
Van öt különböző lehetséges válaszok.

177
00:08:47,124 --> 00:08:48,790
Hol szeretné, hogy álljon a szám 50?

178
00:08:48,790 --> 00:08:51,899
Ha a cél itt, újra, hívja a
funkciót push, át egy érvet

179
00:08:51,899 --> 00:08:52,940
50, hová tegyem meg?

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

181
00:08:55,680 --> 00:08:59,052
Öt possible-- 20% -os valószínűséggel
találgatás helyesen.

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

183
00:08:59,896 --> 00:09:00,740
>> Közönség: szélsőjobb.

184
00:09:00,740 --> 00:09:01,990
>> 1. Előadó: szélsőjobb.

185
00:09:01,990 --> 00:09:08,359
Van most egy 25% esélye
találgatás helyesen.

186
00:09:08,359 --> 00:09:09,650
Tehát, hogy valójában minden rendben lesz.

187
00:09:09,650 --> 00:09:12,770
Megegyezés alapján, azt mondom egy sor,
mi lenne általában kezdeni a bal,

188
00:09:12,770 --> 00:09:14,519
de minden bizonnyal
kezdeni a megfelelő.

189
00:09:14,519 --> 00:09:17,478
Tehát a spoiler itt lenne vagyok
valószínűleg fog rajzolni a bal oldalon,

190
00:09:17,478 --> 00:09:20,060
Csak úgy, mint egy normális tömb, ahol
Én indulj balról jobbra.

191
00:09:20,060 --> 00:09:21,780
De ha a flip
számtani, finom.

192
00:09:21,780 --> 00:09:23,060
Ez egyszerűen nem hagyományos.

193
00:09:23,060 --> 00:09:24,880
OK, azt kell, hogy egy
További változás mégis.

194
00:09:24,880 --> 00:09:27,710
Most, hogy már tolta valamit
a verembe, mi a következő lépés?

195
00:09:27,710 --> 00:09:29,400
>> Rendben, azt kell növelni a méretét.

196
00:09:29,400 --> 00:09:32,600
Szóval hadd menjen előre, és csak
frissíteni ezt, ami nulla volt.

197
00:09:32,600 --> 00:09:35,950
És ahelyett, hogy most, megyek
hogy hozzanak értéke egy.

198
00:09:35,950 --> 00:09:39,460
És most tegyük fel, megnyomom a másik
szám a verembe, mint a 51.

199
00:09:39,460 --> 00:09:42,680
Nos, azt kell, hogy még egy
változás, amely legfeljebb akkora, kettő.

200
00:09:42,680 --> 00:09:46,100
És akkor hiszem tolja még egy
szám a verembe, mint 61,

201
00:09:46,100 --> 00:09:52,530
most kell frissíteni a méret még egy
ideje, és kap az érték 3, mint a méret.

202
00:09:52,530 --> 00:09:54,690
És most tegyük fel, hívom a pop.

203
00:09:54,690 --> 00:09:57,250
Most pop, megállapodás szerint,
nem veszi érv.

204
00:09:57,250 --> 00:10:00,430
A verem, az egész
pont a tálca metafora

205
00:10:00,430 --> 00:10:03,450
az, hogy nincs mérlegelési jogköre
menni fog, hogy tálcán, minden, amit tehetünk

206
00:10:03,450 --> 00:10:06,330
a pop a legfelső egyet
a verem, csak azért, mert.

207
00:10:06,330 --> 00:10:08,010
Ez az, amit ez az adat struktúrára.

208
00:10:08,010 --> 00:10:12,250
>> Tehát, hogy a logika, ha
mondjuk pop, mi jön ki?

209
00:10:12,250 --> 00:10:13,080
Tehát 61.

210
00:10:13,080 --> 00:10:15,402
Szóval mi tényleg a számítógép
fog tenni a memóriában?

211
00:10:15,402 --> 00:10:16,610
Mit jelent a kódot kell csinálni?

212
00:10:16,610 --> 00:10:20,330
Mit javasolna
megváltoztatjuk a képernyőn?

213
00:10:20,330 --> 00:10:23,410
Mit kell változtatni?

214
00:10:23,410 --> 00:10:24,960
Bocsánat?

215
00:10:24,960 --> 00:10:26,334
Így megszabadulunk 61.

216
00:10:26,334 --> 00:10:27,500
Szóval tudom biztosan csinálni.

217
00:10:27,500 --> 00:10:28,640
És tudok megszabadulni a 61.

218
00:10:28,640 --> 00:10:30,980
És akkor mi más
változás kell történnie?

219
00:10:30,980 --> 00:10:33,160
Méret valószínűleg visszamenni kettő.

220
00:10:33,160 --> 00:10:34,210
És így ez rendben van.

221
00:10:34,210 --> 00:10:36,690
De várj egy percet, méret
Egy perccel ezelőtt volt, három.

222
00:10:36,690 --> 00:10:38,240
Nézzük csak egy gyors józanság csekket.

223
00:10:38,240 --> 00:10:41,810
Honnan tudjuk, hogy
akart megszabadulni a 61?

224
00:10:41,810 --> 00:10:42,760
Mert mi popping.

225
00:10:42,760 --> 00:10:46,450
És így van ez a második ingatlan alapterülete.

226
00:10:46,450 --> 00:10:48,470
>> Várj egy percet, én vagyok
gondoltam vissza a héten két

227
00:10:48,470 --> 00:10:51,660
amikor elkezdtünk beszélni
tömbök, ahol ez volt helye nulla,

228
00:10:51,660 --> 00:10:55,920
ez volt az egyik helyen, ez volt helye
két, ez helyen három, négy,

229
00:10:55,920 --> 00:10:58,460
úgy néz ki, mint a
közötti kapcsolat méret

230
00:10:58,460 --> 00:11:02,780
és az elem, hogy szeretnék eltávolítani
A tömb tűnik, hogy csak legyen mit?

231
00:11:02,780 --> 00:11:05,120
Méret mínusz egy.

232
00:11:05,120 --> 00:11:07,786
És ez az, hogyan, mint az emberek
Tudjuk 61 az első.

233
00:11:07,786 --> 00:11:09,160
Hogy a számítógép fog tudni?

234
00:11:09,160 --> 00:11:11,701
Amikor a kódot, ahol valószínűleg
akarok mérete mínusz egy,

235
00:11:11,701 --> 00:11:14,950
így három mínusz egy két, és hogy a
azt jelenti, hogy szeretne megszabadulni a 61.

236
00:11:14,950 --> 00:11:18,000
És akkor valóban frissítheti
A méretet úgy, hogy mérete most

237
00:11:18,000 --> 00:11:20,300
megy háromról csak két.

238
00:11:20,300 --> 00:11:24,520
És csak azért, pedáns, megyek
azt javasolni, hogy kész vagyok, ugye?

239
00:11:24,520 --> 00:11:27,660
Akkor javasolt ösztönösen
helyesen kéne megszabadulni 61.

240
00:11:27,660 --> 00:11:30,700
De nincs Valahogy
fajta ütött megszabadulni 61?

241
00:11:30,700 --> 00:11:33,790
Már elfelejtkeznek
hogy ez valóban létezik.

242
00:11:33,790 --> 00:11:37,680
És hiszem, vissza PSET4, ha elolvastátok
A cikket a kriminalisztika, a PDF-

243
00:11:37,680 --> 00:11:40,780
hogy mi volt a srácok olvasni, vagy
fogja olvasni ezen a héten PSET4.

244
00:11:40,780 --> 00:11:44,300
Emlékezzünk vissza, hogy ez valójában valaminek megfelelő
Az egész ötlet a számítógép kriminalisztika.

245
00:11:44,300 --> 00:11:47,820
Mi a számítógép általában nem az,
ez csak elfelejti, hol valami,

246
00:11:47,820 --> 00:11:51,300
de ez nem megy, és hasonlók
próbáljuk megkarcolni ki vagy felülírás

247
00:11:51,300 --> 00:11:54,560
ezeket a biteket a nullák és egyesek
vagy valamilyen más, véletlenszerű mintát

248
00:11:54,560 --> 00:11:56,690
hacsak te magad erre tudatosan.

249
00:11:56,690 --> 00:11:58,930
Tehát az intuíció volt
Rendben, hogy megszabaduljunk a 61.

250
00:11:58,930 --> 00:12:00,650
De a valóságban, nem kell bajlódnia.

251
00:12:00,650 --> 00:12:04,040
Csak meg kell elfelejteni, hogy
hogy ott van megváltoztatásával méretét.

252
00:12:04,040 --> 00:12:05,662
>> Most van egy probléma ezzel verem.

253
00:12:05,662 --> 00:12:07,620
Ha tovább nyomja a dolgokat
a verembe, mi

254
00:12:07,620 --> 00:12:11,167
Nyilvánvalóan fog történni
mindössze néhány pillanat az időben?

255
00:12:11,167 --> 00:12:12,500
Fogunk elfogy a hely.

256
00:12:12,500 --> 00:12:13,580
És mit tegyünk?

257
00:12:13,580 --> 00:12:14,680
Mi vagyunk a fajta csavarni.

258
00:12:14,680 --> 00:12:19,000
Ez a megvalósítás nem hagyja
nekünk átméretezni a tömb, mert segítségével

259
00:12:19,000 --> 00:12:21,240
ezt a szintaxist, ha
gondoljon vissza a heti két,

260
00:12:21,240 --> 00:12:23,520
ha egyszer már kijelentette,
A tömb méretét,

261
00:12:23,520 --> 00:12:26,780
nem láttunk olyan mechanizmust még, ahol
meg lehet változtatni a méret a tömb.

262
00:12:26,780 --> 00:12:29,020
És valóban C nem ezt a funkciót.

263
00:12:29,020 --> 00:12:32,524
Ha azt mondod, hogy nekem öt
Nths, hívja őket számokat,

264
00:12:32,524 --> 00:12:33,940
Ez minden, amit akarsz kapni.

265
00:12:33,940 --> 00:12:38,790
Tehát mi most, mint a hétfő, van
a képessége, hogy kifejezze a megoldás

266
00:12:38,790 --> 00:12:42,480
Bár, már csak be kell csípés
meghatározása a verem

267
00:12:42,480 --> 00:12:46,840
hogy nem lehet néhány kódolt tömb,
de csak tárolni egy címet.

268
00:12:46,840 --> 00:12:47,890
>> Most miért van ez?

269
00:12:47,890 --> 00:12:51,690
Most már csak azt kell kényelmes,
Az a tény, hogy amikor a program fut,

270
00:12:51,690 --> 00:12:53,730
Én valószínűleg fog
Meg kell kérdeznem az emberi,

271
00:12:53,730 --> 00:12:55,110
hány számot akarsz tárolni?

272
00:12:55,110 --> 00:12:56,776
Tehát a bemenő kell jönnie valahonnan.

273
00:12:56,776 --> 00:12:59,140
De ha már tudjuk, hogy
szám, akkor én is csak

274
00:12:59,140 --> 00:13:02,470
Használja milyen funkciót adni
nekem egy darab memória?

275
00:13:02,470 --> 00:13:03,580
Tudom használni malloc.

276
00:13:03,580 --> 00:13:06,710
És elmondhatom, bármennyi
bájt akarom vissza ezekre Nths.

277
00:13:06,710 --> 00:13:10,910
És azt kell tárolni a számok
változó itt belül ez a struktúra

278
00:13:10,910 --> 00:13:13,480
kell, hogy mit?

279
00:13:13,480 --> 00:13:18,440
Hogy valójában mi megy a
szám ebben a forgatókönyvben?

280
00:13:18,440 --> 00:13:21,300
Igen, egy mutatót az első
byte, hogy darab memória,

281
00:13:21,300 --> 00:13:24,940
vagy még pontosabban, a cím
Az első ilyen bájt.

282
00:13:24,940 --> 00:13:27,300
Nem számít, ha ez az egyik
bájt vagy egy milliárd byte-,

283
00:13:27,300 --> 00:13:28,890
Csak kell törődnünk az első.

284
00:13:28,890 --> 00:13:31,530
Mert amit malloc garanciák és
az operációs rendszer garantálja,

285
00:13:31,530 --> 00:13:34,170
az, hogy a darab a memória I
kap, akkor lesz egybefüggő.

286
00:13:34,170 --> 00:13:35,378
Ott nem lesz hiányos.

287
00:13:35,378 --> 00:13:38,576
Tehát, ha kértem 50
bájt vagy 1000 byte,

288
00:13:38,576 --> 00:13:40,450
ezek mind lesz
vissza háttal.

289
00:13:40,450 --> 00:13:44,500
És mindaddig, amíg emlékszem, milyen nagy, milyen
sokat kértem, csak annyit kell tudni,

290
00:13:44,500 --> 00:13:46,230
az első ilyen címet.

291
00:13:46,230 --> 00:13:48,660
>> Tehát most már képes a kódot.

292
00:13:48,660 --> 00:13:51,280
Jóllehet, ez fog minket
Több időm írni ezt fel,

293
00:13:51,280 --> 00:13:55,900
tudnánk teremteni átcsoportosítása, hogy az emlékezet által
Csak tárolása eltérő címre van

294
00:13:55,900 --> 00:13:59,060
ha azt akarjuk, egy nagyobb, vagy akár
egy kisebb darab memória.

295
00:13:59,060 --> 00:14:00,170
Tehát itt egy kompromisszum.

296
00:14:00,170 --> 00:14:01,360
Most, hogy a dinamizmus.

297
00:14:01,360 --> 00:14:03,350
Még mindig van
contiguousness Én azt állítva.

298
00:14:03,350 --> 00:14:05,881
Mivel malloc ad nekünk
egy folytonos darabkája memória.

299
00:14:05,881 --> 00:14:08,630
De ez lesz a fájdalom
A nyak számunkra, a programozó,

300
00:14:08,630 --> 00:14:09,770
hogy ténylegesen kódot fel.

301
00:14:09,770 --> 00:14:10,730
Ez csak több munkát.

302
00:14:10,730 --> 00:14:13,930
Szükségünk van-kód hasonlít ahhoz, amit én
dörömböl ki csak egy pillanattal ezelőtt.

303
00:14:13,930 --> 00:14:16,120
Nagyon megvalósítható, de hozzáteszi, komplexitás.

304
00:14:16,120 --> 00:14:19,520
És így fejlesztő időt, programozó
ideje egy újabb erőforrás

305
00:14:19,520 --> 00:14:22,520
hogy mi szüksége lehet tölteni
egy kis időt, hogy új funkciókat.

306
00:14:22,520 --> 00:14:24,020
És persze van egy sorban.

307
00:14:24,020 --> 00:14:26,227
Nem fogunk menni ebbe
egy a sok részlet.

308
00:14:26,227 --> 00:14:27,560
De ez nagyon hasonlít a szellem.

309
00:14:27,560 --> 00:14:31,220
Nem tudtam végrehajtani a sorba, és
a megfelelő műveleteket,

310
00:14:31,220 --> 00:14:35,660
Enqueue vagy dequeue, mint felvenni vagy eltávolítani,
ez csak egy szakértő szóval ez,

311
00:14:35,660 --> 00:14:38,100
Enqueue vagy dequeue, az alábbiak szerint.

312
00:14:38,100 --> 00:14:41,170
Én is csak adok magamnak egy struct
hogy ismét van egy szám tömb,

313
00:14:41,170 --> 00:14:44,000
hogy ismét a mérete,
De miért most kell

314
00:14:44,000 --> 00:14:46,940
nyomon követni az első sorban?

315
00:14:46,940 --> 00:14:50,630
Nem kell tudni
Az első az én verem.

316
00:14:50,630 --> 00:14:53,570
Hát, ha ismét egy
queue-- nézzük csak kemény

317
00:14:53,570 --> 00:14:57,870
kódolnod, mint amelyek, mint öt
Egész számok itt potenciálisan.

318
00:14:57,870 --> 00:15:00,940
Tehát ez nulla, egy, kettő, három, négy.

319
00:15:00,940 --> 00:15:03,430
Ez lesz
hívott számokat újra.

320
00:15:03,430 --> 00:15:06,940
És ez lesz az úgynevezett mérete.

321
00:15:06,940 --> 00:15:10,056
>> Miért nem elegendő
hogy csak méretet?

322
00:15:10,056 --> 00:15:11,680
Nos, nézzük nyomja ugyanezen számok.

323
00:15:11,680 --> 00:15:14,220
Szóval pushed-- I enqueued, vagy tolt.

324
00:15:14,220 --> 00:15:20,150
Most akkor sorba állítását 50, majd
51, majd 61, és pont pont pont.

325
00:15:20,150 --> 00:15:21,070
Szóval ez Enqueue.

326
00:15:21,070 --> 00:15:23,176
Én enqueued 50, majd 51, majd 61.

327
00:15:23,176 --> 00:15:25,050
És hogy néz ki,
hogy egy rakás eddig,

328
00:15:25,050 --> 00:15:27,190
csak én szükség, hogy egy változás.

329
00:15:27,190 --> 00:15:33,680
Azt, hogy frissíteni kell ezt a méretet, így megyek
nulláról 1-2, hogy három most.

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

331
00:15:35,760 --> 00:15:36,890
Mi történik a dequeue?

332
00:15:36,890 --> 00:15:41,950
Kinek kell lejönni először a listán
ha ez a vonal az Apple Store?

333
00:15:41,950 --> 00:15:42,780
Tehát 50.

334
00:15:42,780 --> 00:15:44,700
Szóval ez a fajta trükkösebb ebben az időben.

335
00:15:44,700 --> 00:15:47,880
Mivel utoljára ez szuper volt
egyszerűen csak nem mérete mínusz egy,

336
00:15:47,880 --> 00:15:51,440
Azt, hogy a végén az én tömb hatékonyan
ahol a számok, hogy eltávolítja 61.

337
00:15:51,440 --> 00:15:52,920
De nem akarom, hogy távolítsa el 61.

338
00:15:52,920 --> 00:15:55,030
Azt akarom, hogy 50, akik
ott volt 05:00

339
00:15:55,030 --> 00:15:56,790
sorban a
új iPhone vagy miegymás.

340
00:15:56,790 --> 00:16:01,200
És így, hogy megszabaduljon a 50, I
Nem csak ezt, ugye?

341
00:16:01,200 --> 00:16:02,547
Én is kihúz 50.

342
00:16:02,547 --> 00:16:04,380
De mi csak azt mondta,
Nem kell, hogy így legyen anális

343
00:16:04,380 --> 00:16:06,330
hogy kihúz vagy elrejtheti az adatokat.

344
00:16:06,330 --> 00:16:08,090
Mi is csak elfelejteni, hol van.

345
00:16:08,090 --> 00:16:12,330
>> De ha tudom megváltoztatni a mérete most
Két, ez elegendő információ

346
00:16:12,330 --> 00:16:15,711
tudni, hogy mi folyik az én sorban?

347
00:16:15,711 --> 00:16:16,680
Nem igazán.

348
00:16:16,680 --> 00:16:19,830
Mint a mérete két, hanem
hol a sorban kezdődik,

349
00:16:19,830 --> 00:16:22,980
különösen, ha még mindig van
ugyanezek a számok a memóriában.

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

351
00:16:24,260 --> 00:16:27,090
Szóval kell emlékezni
Most, amikor a front.

352
00:16:27,090 --> 00:16:29,630
És ahogy javasoltam fel
ott vagyunk, már csak úgynevezett

353
00:16:29,630 --> 00:16:33,729
N-edik előtt, akinek az első
értéket kellett volna, mi?

354
00:16:33,729 --> 00:16:35,270
Zero, csak a lista elején.

355
00:16:35,270 --> 00:16:40,876
De most amellett, hogy csökkentjük
a méret, csak növeljük az első.

356
00:16:40,876 --> 00:16:42,000
Most itt van egy másik probléma.

357
00:16:42,000 --> 00:16:43,030
Tehát ha én folyamatosan megy.

358
00:16:43,030 --> 00:16:47,520
Tegyük fel, ez az a szám,
mint 121, 124, majd, a fenébe is,

359
00:16:47,520 --> 00:16:48,610
Én vagyok a hely.

360
00:16:48,610 --> 00:16:50,390
De várj egy percet, nem vagyok.

361
00:16:50,390 --> 00:16:55,630
Tehát ezen a ponton a történet,
tegyük fel, hogy a mérete egy, kettő,

362
00:16:55,630 --> 00:17:00,370
három, négy, így feltételezzük, hogy a
mérete négy, az első az egyik,

363
00:17:00,370 --> 00:17:01,621
így 51 elöl.

364
00:17:01,621 --> 00:17:04,329
Azt szeretnénk, hogy egy másik számot itt,
de a fenébe is, én vagyok a hely.

365
00:17:04,329 --> 00:17:06,710
De nem igazán vagyok, ugye?

366
00:17:06,710 --> 00:17:11,192
Hol tudnék némi
hozzáadott érték, mint a 171?

367
00:17:11,192 --> 00:17:13,400
Igen, én is csak ilyen
menj vissza oda, ugye?

368
00:17:13,400 --> 00:17:18,161
Majd húzza át a 50, vagy
Csak írja felül 171.

369
00:17:18,161 --> 00:17:20,410
És ha kíváncsi vagy, miért
a számok annyira véletlenszerű,

370
00:17:20,410 --> 00:17:24,150
Ezek általánosan vett számítógép
tudományos képzés, a Harvard után CS50.

371
00:17:24,150 --> 00:17:27,510
De ez egy jó optimalizálás,
mert most nem vagyok kiesik hely.

372
00:17:27,510 --> 00:17:30,750
Még mindig kell emlékezni
milyen nagy ez a dolog teljes.

373
00:17:30,750 --> 00:17:31,500
Ez összesen öt.

374
00:17:31,500 --> 00:17:33,375
Mert nem akarom, hogy
felülírását kezdi 51.

375
00:17:33,375 --> 00:17:36,260
Szóval most én vagyok még szabad terület,
így ugyanaz a probléma, mint korábban.

376
00:17:36,260 --> 00:17:39,140
De láthatod, hogy most
a kódban, akkor valószínűleg

377
00:17:39,140 --> 00:17:41,910
Meg kell írni egy kicsit
komplexitás, hogy ez megtörténjen.

378
00:17:41,910 --> 00:17:44,510
És valóban, mi üzemeltető
C valószínűleg lehetővé teszi,

379
00:17:44,510 --> 00:17:48,110
Ön varázslatosan ezt a körkörösség?

380
00:17:48,110 --> 00:17:50,160
Ja moduló,
A százalékos jel.

381
00:17:50,160 --> 00:17:53,160
Szóval mi egyfajta hűvös egy sorban,
még akkor is megtartjuk rajz tömbök

382
00:17:53,160 --> 00:17:56,520
mivel ezek, mint egyenesek, ha
fajta gondolni ezt a kanyargós

383
00:17:56,520 --> 00:18:00,341
körül, mint egy kör, akkor csak
ösztönösen azt a fajta működik mentálisan

384
00:18:00,341 --> 00:18:01,590
Azt hiszem, egy kicsit tisztábban.

385
00:18:01,590 --> 00:18:05,190
Azt még meg kell végrehajtani
hogy a mentális modell kódot.

386
00:18:05,190 --> 00:18:07,550
Szóval nem is olyan nehéz,
végül, hogy végre,

387
00:18:07,550 --> 00:18:12,430
de még mindig elveszítik a size-- inkább a
képes átméretezni, kivéve, ha ezt tesszük.

388
00:18:12,430 --> 00:18:15,310
>> Van, hogy megszabaduljon a tömb, akkor
helyette egy egységes mutatót,

389
00:18:15,310 --> 00:18:20,010
majd valahol a kódomat kaptam
Egy hívják, amit úgy működnek, hogy valóban létre

390
00:18:20,010 --> 00:18:23,720
A tömb hívott számokat?

391
00:18:23,720 --> 00:18:26,190
Malloc, vagy valamilyen hasonló
funkciót, pontosan.

392
00:18:26,190 --> 00:18:30,481
Bármilyen kérdésre halom, vagy sorokat.

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

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

395
00:18:33,657 --> 00:18:34,240
Jó kérdés.

396
00:18:34,240 --> 00:18:35,830
Mit modulo kíván használni itt.

397
00:18:35,830 --> 00:18:38,520
Tehát általában akkor, ha a
mod, akkor csináld

398
00:18:38,520 --> 00:18:40,620
a méret a
egész adatstruktúra.

399
00:18:40,620 --> 00:18:44,120
Szóval valami ilyesmi öt vagy kapacitás, ha
ez állandó, valószínűleg részt.

400
00:18:44,120 --> 00:18:47,100
De csak ezzel modulo öt
Valószínűleg nem elegendő,

401
00:18:47,100 --> 00:18:51,380
mert tudnunk kell, hogy mi is
kerületi itt vagy itt vagy itt.

402
00:18:51,380 --> 00:18:54,160
Szóval akkor valószínűleg azt is
akarnak bevonni

403
00:18:54,160 --> 00:18:57,220
A méret a dolog, vagy
az elülső változó is.

404
00:18:57,220 --> 00:19:00,140
Tehát csak ez a viszonylag
egyszerű aritmetikai kifejezés,

405
00:19:00,140 --> 00:19:02,000
de modulo lenne a legfontosabb összetevő.

406
00:19:02,000 --> 00:19:03,330
>> Tehát rövidfilm, ha lesz.

407
00:19:03,330 --> 00:19:05,780
Egy animáció, hogy egyes
hozzátartozók egy másik egyetemen

408
00:19:05,780 --> 00:19:08,060
össze, hogy már
adaptált ezt a vitát.

409
00:19:08,060 --> 00:19:12,630
Ez magában foglalja a tanulás a Jack
tényeket sorok és a statisztikák.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Once upon a time,
volt egy srác nevű Jack.

412
00:19:21,890 --> 00:19:25,330
Amikor eljött a barátkoznak,
Jack nem egy trükk.

413
00:19:25,330 --> 00:19:28,220
Szóval Jack elment, hogy beszéljen a
Népszerű fickó, akit ismert.

414
00:19:28,220 --> 00:19:30,920
Elment Lou, és megkérdezte, mit tegyek?

415
00:19:30,920 --> 00:19:33,400
Lou látta, hogy a barátja
tényleg szomorú.

416
00:19:33,400 --> 00:19:36,050
Nos, ő kezdte, csak
nézd, milyen úgy nézel ki.

417
00:19:36,050 --> 00:19:38,680
Ne bármilyen ruhát
egy másik pillantást?

418
00:19:38,680 --> 00:19:39,660
Igen, mondta Jack.

419
00:19:39,660 --> 00:19:40,840
Én biztos nem.

420
00:19:40,840 --> 00:19:43,320
Gyere a házamba, és
Majd én megmutatom nektek.

421
00:19:43,320 --> 00:19:44,550
Így elmentek Jack.

422
00:19:44,550 --> 00:19:47,520
És Jack megmutatta Lou mezőbe
hol tartja minden ingek,

423
00:19:47,520 --> 00:19:49,260
és a nadrágját, és a zokniját.

424
00:19:49,260 --> 00:19:52,290
Lou, látom, hogy van
az összes ruhát egy halom.

425
00:19:52,290 --> 00:19:54,870
Miért nem viselnek néhány
mások egyszer egy kicsit?

426
00:19:54,870 --> 00:19:58,020
>> Jack azt mondta, jól, amikor én
ruházatot eltávolítani és zokni,

427
00:19:58,020 --> 00:20:00,780
Én mosom őket, és tedd
őket a dobozba.

428
00:20:00,780 --> 00:20:03,210
Aztán jön a következő
Reggel, és akár azt hop.

429
00:20:03,210 --> 00:20:06,380
Megyek a dobozt, és kap
ruhámat a tetején.

430
00:20:06,380 --> 00:20:09,070
Lou gyorsan rájött,
A probléma Jack.

431
00:20:09,070 --> 00:20:12,080
Folyton ruhát, CD-k,
és könyvek a veremben.

432
00:20:12,080 --> 00:20:14,420
Amikor elérte a
valamit olvasni, vagy viselni,

433
00:20:14,420 --> 00:20:17,100
Ő dönt, az első könyv, vagy fehérnemű.

434
00:20:17,100 --> 00:20:19,500
Aztán amikor végzett, ő
mondaná vissza.

435
00:20:19,500 --> 00:20:21,970
Vissza menne, a tetején a verem.

436
00:20:21,970 --> 00:20:24,460
Tudom, hogy a megoldás,
mondta diadalmas Loud.

437
00:20:24,460 --> 00:20:27,090
Meg kell tanulni, hogy
kezdi el használni a sorban.

438
00:20:27,090 --> 00:20:29,870
Lou vette Jack ruháit és
lógott a szekrénybe.

439
00:20:29,870 --> 00:20:32,710
És mikor kiürítették
A doboz, ő csak dobta.

440
00:20:32,710 --> 00:20:36,500
>> Aztán azt mondta, most már Jack, a végén
A nap ruháit a bal

441
00:20:36,500 --> 00:20:37,990
ha fel őket.

442
00:20:37,990 --> 00:20:41,300
Akkor holnap reggel, amikor
lásd a napsütés, hogy a ruhák

443
00:20:41,300 --> 00:20:43,440
a jobb oldalon, a sor végére.

444
00:20:43,440 --> 00:20:44,880
Hát nem látod? mondta Lou.

445
00:20:44,880 --> 00:20:46,370
Ez lesz olyan szép.

446
00:20:46,370 --> 00:20:49,770
Majd viselni mindent egyszerre
Mielőtt viselni valamit kétszer.

447
00:20:49,770 --> 00:20:52,670
És mindent sorba
a szekrényében, és polc,

448
00:20:52,670 --> 00:20:55,160
Jack kezdte érezni
egészen biztos magában.

449
00:20:55,160 --> 00:20:59,720
Minden köszönhetően Lou és
ő csodálatos sorban.

450
00:20:59,720 --> 00:21:01,220
1. Előadó: Rendben, ez imádnivaló.

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

452
00:21:05,920 --> 00:21:10,080
Szóval mi már tényleg lesz
A a motorháztető alatt most?

453
00:21:10,080 --> 00:21:12,370
Hogy van mutatók,
hogy van malloc,

454
00:21:12,370 --> 00:21:15,680
hogy megvan a képessége, hogy hozzon létre
darabokat a memória magunkat

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

456
00:21:16,344 --> 00:21:18,510
Tehát ez egy kép, amit
megpillantotta csak a minap.

457
00:21:18,510 --> 00:21:21,180
Nem igazán él
rajta, de ez a kép

458
00:21:21,180 --> 00:21:24,180
már folyik alatta
A motorháztető hete.

459
00:21:24,180 --> 00:21:27,050
És így ez azt jelenti, csak
egy téglalapot, amit rajzolt,

460
00:21:27,050 --> 00:21:28,180
a számítógép memóriáját.

461
00:21:28,180 --> 00:21:31,850
És talán a számítógép, illetve CS50
ID, egy gigabájt memória vagy RAM

462
00:21:31,850 --> 00:21:33,050
vagy két gigabájt vagy négy.

463
00:21:33,050 --> 00:21:34,450
Ez nem igazán számít.

464
00:21:34,450 --> 00:21:37,240
Az operációs rendszer
Windows vagy Mac OS vagy Linux,

465
00:21:37,240 --> 00:21:41,120
lényegében lehetővé teszi a programot
gondolni, hogy hozzá tud

466
00:21:41,120 --> 00:21:42,982
hogy a teljes egészében
a számítógép memóriájában,

467
00:21:42,982 --> 00:21:45,440
még akkor is lehet, hogy fut
több program egyszerre.

468
00:21:45,440 --> 00:21:46,990
Így a valóságban, hogy nem igazán működik.

469
00:21:46,990 --> 00:21:49,448
De ez a fajta illúzió
fordítani az összes programot.

470
00:21:49,448 --> 00:21:53,110
Tehát, ha két giga RAM, ez a
az, hogy a számítógép lehet, hogy belegondolok.

471
00:21:53,110 --> 00:21:57,110
>> Most véletlenül, az egyik ilyen
dolgok, az egyik ilyen szegmensek memória,

472
00:21:57,110 --> 00:21:58,350
nevezzük verem.

473
00:21:58,350 --> 00:22:01,680
És valóban bármikor
Eddig írásban kódot

474
00:22:01,680 --> 00:22:05,900
hogy felhívta a
funkciót, például a fő.

475
00:22:05,900 --> 00:22:08,410
Emlékezzünk vissza, hogy minden alkalommal, amikor már
húzott számítógép memóriája,

476
00:22:08,410 --> 00:22:10,640
Én mindig felhívni a fajta
felében egy téglalap itt

477
00:22:10,640 --> 00:22:12,520
és nem zavarja, beszél
mi van fent.

478
00:22:12,520 --> 00:22:15,980
Mert amikor fő hívják, azt állítják,
hogy ezt kapod szelet memória

479
00:22:15,980 --> 00:22:16,970
hogy megy le itt.

480
00:22:16,970 --> 00:22:20,650
És ha fő nevezett funkció
mint a swap, illetve a swap megy itt.

481
00:22:20,650 --> 00:22:23,720
És kiderül, hogy ez
ahol ez kiöntött.

482
00:22:23,720 --> 00:22:26,277
On egy úgynevezett verem
belsejében a számítógép memóriáját.

483
00:22:26,277 --> 00:22:28,360
Most a végén a nap,
ez csak címek.

484
00:22:28,360 --> 00:22:30,680
Ez olyan, mint byte nulla,
byte hosszú, byte 2 milliárd.

485
00:22:30,680 --> 00:22:33,130
De ha belegondolunk
mivel ez téglalap alakú tárgyat,

486
00:22:33,130 --> 00:22:35,130
Az összes csinálunk minden
alkalommal hívunk funkció

487
00:22:35,130 --> 00:22:37,180
rétegződés új szelet memória.

488
00:22:37,180 --> 00:22:41,700
Adunk, hogy a funkció egy szelet
saját memóriával dolgozni.

489
00:22:41,700 --> 00:22:44,490
>> És emlékszem most, hogy ez fontos.

490
00:22:44,490 --> 00:22:46,400
Mert ha van
olyasmi, mint a swap

491
00:22:46,400 --> 00:22:51,610
és két helyi változók, mint az A és B
megváltoztatjuk ezeket az értékeket egy és két

492
00:22:51,610 --> 00:22:55,130
két és egy, visszahívás
hogy amikor a swap visszatér,

493
00:22:55,130 --> 00:22:58,330
olyan, mintha ez a szelet
A memória csak elmentek.

494
00:22:58,330 --> 00:23:00,080
A valóságban ez még mindig
ott forensically.

495
00:23:00,080 --> 00:23:01,940
És valami még valóban ott.

496
00:23:01,940 --> 00:23:05,410
De fogalmilag, ez olyan
mintha ez teljesen eltűnt.

497
00:23:05,410 --> 00:23:10,910
És így fő nem ismer a munka
hogy azért került sor, hogy a swap,

498
00:23:10,910 --> 00:23:14,890
kivéve, ha ez valóban telt azokban
érvek mutató által vagy utalásokkal.

499
00:23:14,890 --> 00:23:17,790
Most, az alapvető megoldás
hogy ezt a problémát a swap-

500
00:23:17,790 --> 00:23:19,970
Múlik a dolgokat a címet.

501
00:23:19,970 --> 00:23:23,250
De kiderült, túl, mi
óta tart fent az a része,

502
00:23:23,250 --> 00:23:26,330
A téglalap egész idő alatt
Még van több memóriát odafent.

503
00:23:26,330 --> 00:23:28,790
És ha dinamikusan
memóriát foglalni,

504
00:23:28,790 --> 00:23:32,020
legyen szó belsejében getString, amely
mi már ennek az Ön számára a CS50

505
00:23:32,020 --> 00:23:34,710
könyvtár, vagy ha a fiúk
hívja malloc és kérje

506
00:23:34,710 --> 00:23:37,950
Az operációs rendszer egy darab
memória, ez nem jön a veremből.

507
00:23:37,950 --> 00:23:40,960
Jön egy másik helyre
a számítógép memóriájában

508
00:23:40,960 --> 00:23:42,220
hogy hívják a kupac.

509
00:23:42,220 --> 00:23:43,430
És ez még nem minden más.

510
00:23:43,430 --> 00:23:44,285
Ez ugyanaz a RAM.

511
00:23:44,285 --> 00:23:45,160
Ez ugyanaz a memória.

512
00:23:45,160 --> 00:23:49,080
Ez csak a RAM, ami akár
ott, hanem itt lent.

513
00:23:49,080 --> 00:23:50,750
>> És ez mit jelent?

514
00:23:50,750 --> 00:23:53,650
Nos, ha a számítógép
véges mennyiségű memória

515
00:23:53,650 --> 00:23:57,450
és a verem nő fel, így
beszélni, és a kupac szerint

516
00:23:57,450 --> 00:23:59,349
hogy ezt a nyilat, növekszik le.

517
00:23:59,349 --> 00:24:01,140
Más szavakkal, minden
alkalommal, amikor hívást malloc,

518
00:24:01,140 --> 00:24:03,430
te is kap egy szelet
memória felülről,

519
00:24:03,430 --> 00:24:06,630
akkor talán egy kicsit alacsonyabb, majd egy kicsit
alacsonyabb, minden alkalommal, amikor hívást malloc,

520
00:24:06,630 --> 00:24:10,100
A kupac, ez a használat,
a fajta nő,

521
00:24:10,100 --> 00:24:11,950
egyre közelebb és közelebb, mi?

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

523
00:24:13,382 --> 00:24:14,840
Így jelent ez úgy tűnik, mint egy jó ötlet?

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

525
00:24:18,420 --> 00:24:22,140
Úgy értem, ahol ez nem igazán világos,
mi mást tehet, ha csak

526
00:24:22,140 --> 00:24:23,910
Van egy véges mennyiségű memóriát.

527
00:24:23,910 --> 00:24:25,200
De ez biztosan rossz.

528
00:24:25,200 --> 00:24:27,920
Ez a két nyíl a
gyorstalpaló egymásért.

529
00:24:27,920 --> 00:24:31,930
>> És kiderül, hogy a rosszfiú, emberek, akik
különösen jó a programozás,

530
00:24:31,930 --> 00:24:36,140
és akarja feltörni a számítógépeket,
lehet kihasználni ezt a valóságot.

531
00:24:36,140 --> 00:24:38,290
Tény, hogy nézzük meg
egy kis részlet.

532
00:24:38,290 --> 00:24:41,350
Szóval ez egy példa lehet olvasni
mintegy részletesebben a Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Majd pont akkor a
cikket, ha kíváncsi.

534
00:24:43,100 --> 00:24:45,650
De van egy támadás általában
néven puffer túlcsordulás, hogy

535
00:24:45,650 --> 00:24:49,570
létezett ameddig emberekben
volt képes manipulálni

536
00:24:49,570 --> 00:24:53,120
számítógép memóriájában, különösen a C.
Tehát ez egy nagyon önkényes programot,

537
00:24:53,120 --> 00:24:55,130
de most olvasni alulról felfelé.

538
00:24:55,130 --> 00:24:57,650
Fő be argC char csillagos argv.

539
00:24:57,650 --> 00:24:59,830
Szóval ez egy program, mely
parancssori paramétereket.

540
00:24:59,830 --> 00:25:03,620
És a legfontosabb jelent látszólag hívás
függvényében, nevezzük az egyszerűség kedvéért F.

541
00:25:03,620 --> 00:25:04,610
És ez megy, mi?

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

543
00:25:05,490 --> 00:25:09,320
Így bejut F bármi
a szó, hogy a felhasználói gépelt

544
00:25:09,320 --> 00:25:11,500
A prompt után
Szak neve egyáltalán.

545
00:25:11,500 --> 00:25:15,730
Annyira, mint Caesar vagy Vigenère, amely
talán felidézni csinál argv.

546
00:25:15,730 --> 00:25:16,680
>> Tehát mi F?

547
00:25:16,680 --> 00:25:19,760
F vesz egy húr
mint a kizárólagos érvet,

548
00:25:19,760 --> 00:25:22,100
AKA egy char csillag, ugyanazon
dolog, mint egy húr.

549
00:25:22,100 --> 00:25:24,920
És ezt hívják önkényesen
Bár ebben a példában.

550
00:25:24,920 --> 00:25:27,710
És akkor char c 12,
Csak a laikus szempontból,

551
00:25:27,710 --> 00:25:31,750
mi char c konzol 12 csinál nekünk?

552
00:25:31,750 --> 00:25:33,440
Mi csinál?

553
00:25:33,440 --> 00:25:36,490
Memórialefoglalás, konkrétan
12 byte 12 karakter.

554
00:25:36,490 --> 00:25:36,990
Pontosan.

555
00:25:36,990 --> 00:25:40,000
És akkor az utolsó sort, majd kevergetve
másolatot, akkor már valószínűleg nem látta.

556
00:25:40,000 --> 00:25:43,360
Ez egy szöveg másolata
függvény, amelynek célja az életben

557
00:25:43,360 --> 00:25:48,160
az, hogy másolja a második érv
be az első érv,

558
00:25:48,160 --> 00:25:51,190
de csak egy
bizonyos számú bájt.

559
00:25:51,190 --> 00:25:53,860
Így a harmadik érv azt mondja,
hány bájtot kell másolni?

560
00:25:53,860 --> 00:25:56,720
A hossza bár,
amit a felhasználó beírt.

561
00:25:56,720 --> 00:25:59,320
És a tartalmát
bár, hogy a húr, amelyek

562
00:25:59,320 --> 00:26:02,330
bemásolja a memóriában mutatott a C.

563
00:26:02,330 --> 00:26:04,060
>> Szóval ez úgy tűnik, elég hülyén, és ez.

564
00:26:04,060 --> 00:26:06,300
Ez egy kitalált példa,
de ez képviselője

565
00:26:06,300 --> 00:26:10,100
egy osztály a támadási,
módon támadó egy programot.

566
00:26:10,100 --> 00:26:15,050
Minden rendben van, és jó, ha a felhasználó
típusok egy szó, ami 11 karakter

567
00:26:15,050 --> 00:26:18,040
vagy kevesebb, plusz a backslash nulla.

568
00:26:18,040 --> 00:26:22,830
Mi van, ha a felhasználó beírja a több mint
11 vagy 12 vagy 20 vagy 50 karakter?

569
00:26:22,830 --> 00:26:25,090
Mi ez a program fog csinálni?

570
00:26:25,090 --> 00:26:29,360
Potenciálisan seg hiba. Működik
hogy vakon másolni mindent bar

571
00:26:29,360 --> 00:26:31,750
a hosszával, amely a
Szó szerint mindent bár,

572
00:26:31,750 --> 00:26:36,307
a címet mutatott C. De C
csak megelőző jellegű adják 12 bájt.

573
00:26:36,307 --> 00:26:37,640
De nincs külön ellenőrizni.

574
00:26:37,640 --> 00:26:38,700
Nincs ha a körülmények.

575
00:26:38,700 --> 00:26:40,580
Nincs hibaellenőrzési itt.

576
00:26:40,580 --> 00:26:43,270
>> És akkor mi ez a program
eredménye, hogy vakon

577
00:26:43,270 --> 00:26:45,750
másolni egy dolog, hogy a többi.

578
00:26:45,750 --> 00:26:47,880
És így, ha felhívjuk ezt
képként, itt

579
00:26:47,880 --> 00:26:49,860
Csak egy szeletkét a memóriát.

580
00:26:49,860 --> 00:26:53,470
Tehát észre az alján, mi
Van egy helyi változó bárban.

581
00:26:53,470 --> 00:26:57,330
Szóval ez a mutató, hogy fog store--
inkább az, hogy a helyi érv, hogy ez

582
00:26:57,330 --> 00:26:58,672
fog tárolni a húr bárban.

583
00:26:58,672 --> 00:27:00,380
És akkor észre csak
fölötte egy verem,

584
00:27:00,380 --> 00:27:02,505
mert minden alkalommal, amikor kérni
A memória a veremben,

585
00:27:02,505 --> 00:27:04,310
megy egy kicsit
fölötte képileg,

586
00:27:04,310 --> 00:27:06,270
észre, hogy megvan a 12 byte van.

587
00:27:06,270 --> 00:27:10,690
A bal felső az egyik C konzol nulla és
ki a jobb alsót C konzol 11.

588
00:27:10,690 --> 00:27:12,870
Ez csak, hogy a számítógépek
majd feküdt ki.

589
00:27:12,870 --> 00:27:18,300
Tehát csak ösztönösen, ha bár több
mint 12 karakter összesen, beleértve a

590
00:27:18,300 --> 00:27:25,790
A backslash nulla, hol van a
12 vagy a C konzol 12 fog menni?

591
00:27:25,790 --> 00:27:28,440
Vagy inkább, ahol a 12-
karakter vagy a 13. karaktert,

592
00:27:28,440 --> 00:27:30,900
A századik karaktert fog
hogy a végén a képen?

593
00:27:30,900 --> 00:27:33,400
Alatt vagy felett?

594
00:27:33,400 --> 00:27:36,300
>> Jobb, mert bár
A verem magát növekszik felfelé,

595
00:27:36,300 --> 00:27:39,590
ha egyszer már fel cuccot
, ez a dizájn miatt

596
00:27:39,590 --> 00:27:41,294
helyezi a memória felülről lefelé.

597
00:27:41,294 --> 00:27:44,460
Tehát, ha már van több mint 12 bájt,
fogsz kezdeni, hogy felülírja bárban.

598
00:27:44,460 --> 00:27:47,280
Most, hogy egy hiba, de ez
Nem igazán nagy dolog.

599
00:27:47,280 --> 00:27:51,130
De ez egy nagy dolog, mert van
Több dolog történik a memóriában.

600
00:27:51,130 --> 00:27:53,074
Tehát itt, hogy hogyan tudnánk
tedd hello, hogy egyértelmű legyen.

601
00:27:53,074 --> 00:27:54,490
Ha beírtam helló a billentyűket.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash nulla, végül belül
a 12 byte, és mi szuper biztonságos.

603
00:27:59,330 --> 00:28:00,330
Minden rendben.

604
00:28:00,330 --> 00:28:03,020
De ha én írja valamit
hosszabb, esetleg ez

605
00:28:03,020 --> 00:28:05,860
fog szivárogni a bárban helyet.

606
00:28:05,860 --> 00:28:08,405
De ami még rosszabb, kiderül
az összes ebben az időben,

607
00:28:08,405 --> 00:28:11,530
még akkor is, soha nem beszéltünk
ez a verem használják egyéb dolgokat.

608
00:28:11,530 --> 00:28:13,560
Ez nem csak a helyi változókat.

609
00:28:13,560 --> 00:28:15,100
>> C egy nagyon alacsony szintű nyelven.

610
00:28:15,100 --> 00:28:17,810
És ez a fajta titokban
használja a verem is

611
00:28:17,810 --> 00:28:21,260
emlékezni, amikor egy
funkciót nevezik, mi

612
00:28:21,260 --> 00:28:26,040
A cím az előző funkciót,
így ugrik vissza, hogy a funkció.

613
00:28:26,040 --> 00:28:29,980
Tehát amikor a fő hívások cserélni között
A dolgok a verembe

614
00:28:29,980 --> 00:28:34,380
nem csak felcseréli a helyi változókat,
vagy érveit, szintén titokban tolta

615
00:28:34,380 --> 00:28:37,510
a verembe képviselt
A piros szelet itt,

616
00:28:37,510 --> 00:28:40,520
a címe fő fizikailag
a számítógép memóriájában,

617
00:28:40,520 --> 00:28:44,180
úgy, hogy amikor a swap történik, a számítógép
tudja, hogy vissza kell mennie a fő

618
00:28:44,180 --> 00:28:46,760
és befejezni a végrehajtó a fő funkciója.

619
00:28:46,760 --> 00:28:51,960
Szóval ez veszélyes most, mert ha
a felhasználó által is több mint hello,

620
00:28:51,960 --> 00:28:57,030
úgy, hogy a felhasználó által megadott clobbers
vagy felülírja, hogy piros pont,

621
00:28:57,030 --> 00:28:59,820
logikusan, ha a számítógép
csak fog vakon vállalnak

622
00:28:59,820 --> 00:29:03,830
hogy a bájtok a piros szelet is
a címet, amelyre ad vissza,

623
00:29:03,830 --> 00:29:09,020
mi van, ha az ellenség elég okos ahhoz, vagy
szerencsés, hogy egy bájtsorozatok

624
00:29:09,020 --> 00:29:13,450
van, hogy néz ki, mint egy cím,
de ez a címe kód

625
00:29:13,450 --> 00:29:18,730
hogy ő akarja a számítógép
hogy végre ahelyett fő?

626
00:29:18,730 --> 00:29:21,670
>> Más szóval, ha az, amit az
felhasználó beírja a parancssorba

627
00:29:21,670 --> 00:29:23,850
nem csak valami
ártalmatlan, mint a Hello,

628
00:29:23,850 --> 00:29:28,210
de ez valójában kódot, ami egyenértékű
törölni mindezt a felhasználó fájljai?

629
00:29:28,210 --> 00:29:30,060
Vagy e-mailben a jelszót, hogy nekem?

630
00:29:30,060 --> 00:29:31,940
Vagy indul naplózása
billentyűleütéseket, ugye?

631
00:29:31,940 --> 00:29:34,920
Van egy módja, hadd kikötik ma,
hogy tudtak írja nemcsak helló

632
00:29:34,920 --> 00:29:36,711
világ, vagy a nevüket,
tudtak lényegében

633
00:29:36,711 --> 00:29:39,570
át a kódot, és nullák
is, hogy a számítógép

634
00:29:39,570 --> 00:29:43,450
hibák mindkét kódot, és egy címet.

635
00:29:43,450 --> 00:29:48,950
Így bár kissé absztrakt, ha a
felhasználó beír elég ellenséges kódot

636
00:29:48,950 --> 00:29:52,330
hogy mi lesz általánosítani itt
A. A jelentése támadás vagy ellenfelek.

637
00:29:52,330 --> 00:29:53,140
Tehát csak rossz dolgokat.

638
00:29:53,140 --> 00:29:55,306
Nem érdekel a
számát vagy a nullát vagy egyest

639
00:29:55,306 --> 00:29:59,470
ma, mint, amit a végén
felülírását, hogy piros pont,

640
00:29:59,470 --> 00:30:01,580
észre, hogy bájtsorozatok.

641
00:30:01,580 --> 00:30:05,020
O 835 C nulla nyolc nulla.

642
00:30:05,020 --> 00:30:08,960
És most, ahogy a Wikipedia cikket itt
azt javasolta, ha már tényleg kezd

643
00:30:08,960 --> 00:30:12,460
címkézéshez bájtok számítógép
memória, amit a Wikipedia cikket

644
00:30:12,460 --> 00:30:19,060
javaslattevő, hogy mi van, ha a cím
Az, hogy a bal felső bájt 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Más szóval, ha a rosszfiú
elég okos a saját kódját

646
00:30:22,200 --> 00:30:26,650
hogy egyszerűen egy számmal, hogy itt
megfelel a címet a kódot

647
00:30:26,650 --> 00:30:29,180
ő injektált
a számítógépbe, akkor

648
00:30:29,180 --> 00:30:31,050
trükk a számítógép
csinál semmit.

649
00:30:31,050 --> 00:30:34,140
Eltávolítja a fájlokat, e-mailezés
dolgokat, szippantás a forgalom,

650
00:30:34,140 --> 00:30:36,710
Szó szerint bármi lehet
fecskendeznek a számítógép.

651
00:30:36,710 --> 00:30:39,220
És így a puffer túlcsordulás
támadást középpontban

652
00:30:39,220 --> 00:30:43,530
ez csak egy hülye, hülye
nyomós tömb, hogy

653
00:30:43,530 --> 00:30:45,840
Nem volt annak határait ellenőrizni.

654
00:30:45,840 --> 00:30:48,850
És ez az, ami szuper veszélyes
és ezzel egyidejűleg szuper erős

655
00:30:48,850 --> 00:30:52,560
C-ben az, hogy valóban van
hozzáférést biztosít bárhol a memóriában.

656
00:30:52,560 --> 00:30:55,320
Rajtunk múlik, hogy velünk, a programozók,
akik írni az eredeti kódot

657
00:30:55,320 --> 00:30:59,330
hogy ellenőrizze a rohadt hosszú bármely
tömbök, hogy mi manipulálni.

658
00:30:59,330 --> 00:31:00,750
Tehát, hogy világos legyen, mi a fix?

659
00:31:00,750 --> 00:31:03,190
Ha visszaállíthatja erre
kódot, amit nem kellene csak

660
00:31:03,190 --> 00:31:08,000
megváltoztatni a hossza bár, mit
mást kéne megnézni?

661
00:31:08,000 --> 00:31:10,620
Mit kell még csinálni, hogy
ennek kivédésére teljesen?

662
00:31:10,620 --> 00:31:14,110
Nem akarom, hogy csak vakon mondani
hogy meg kell másolni annyi bájt

663
00:31:14,110 --> 00:31:16,140
mint a hossza bar.

664
00:31:16,140 --> 00:31:18,910
Azt akarom mondani, másolni, mint
hány bájt, mint a bar

665
00:31:18,910 --> 00:31:24,090
akár a kiosztott
memória, vagy 12 maximálisan.

666
00:31:24,090 --> 00:31:27,450
Szóval kell valami, ha állapota
hogy nem ellenőrzi a hossza bár,

667
00:31:27,450 --> 00:31:32,800
de ha az meghaladja a 12, csak kemény kódot
12, mint a lehető legnagyobb távolságot.

668
00:31:32,800 --> 00:31:35,910
Ellenkező esetben az úgynevezett puffer
túlcsordulás támadás megtörténhet.

669
00:31:35,910 --> 00:31:38,451
Alján a tárgylemezeket,
Ha kíváncsi vagy, hogy tovább

670
00:31:38,451 --> 00:31:41,200
a tényleges eredeti cikk
Ha azt szeretné, hogy vessen egy pillantást.

671
00:31:41,200 --> 00:31:44,550
>> De most, többek között az árak
fordítani volt hiányosságok.

672
00:31:44,550 --> 00:31:46,680
Szóval ez volt a gyors
alacsony nézd meg, mi

673
00:31:46,680 --> 00:31:49,709
problémák merülhetnek fel most, hogy
férhetnek hozzá számítógép memóriájában.

674
00:31:49,709 --> 00:31:51,750
De egy másik probléma is
Már megbotlott hétfőn

675
00:31:51,750 --> 00:31:53,800
csak az eredménytelenség
A láncolt lista.

676
00:31:53,800 --> 00:31:56,019
Mi vissza a lineáris időt.

677
00:31:56,019 --> 00:31:57,560
Már nincs egy összefüggő tömbben.

678
00:31:57,560 --> 00:31:58,980
Nincs véletlen hozzáférésű.

679
00:31:58,980 --> 00:32:00,710
Nem tudjuk használni szögletes zárójel jelöléssel.

680
00:32:00,710 --> 00:32:04,590
Szó van, hogy egy while ciklus
amilyet én írtam az imént.

681
00:32:04,590 --> 00:32:09,740
De hétfőn azt állította, hogy tudjuk
kúsznak vissza a birodalmába hatékonyság

682
00:32:09,740 --> 00:32:13,040
elérése valamit, ami
logaritmikus vagy talán eddigi legjobb,

683
00:32:13,040 --> 00:32:16,120
talán még valamit, ami
úgynevezett konstans idő.

684
00:32:16,120 --> 00:32:19,840
Szóval hogyan lehet csinálni, hogy segítségével ezek az új
szerszámok, ezeket a címeket, ezeket a mutatókat,

685
00:32:19,840 --> 00:32:22,210
és threading dolgokat a saját?

686
00:32:22,210 --> 00:32:23,960
Nos, tegyük fel, hogy
Itt, ezek egy csomó

687
00:32:23,960 --> 00:32:27,170
A számok, hogy szeretnénk tárolni egy
adatok szerkezete és keresés hatékonyan.

688
00:32:27,170 --> 00:32:30,960
Mi lehet teljesen visszatekerni a héten
két, dobja ezeket egy tömbben,

689
00:32:30,960 --> 00:32:33,150
és keresni őket bináris kereséssel.

690
00:32:33,150 --> 00:32:34,040
Oszd meg és uralkodj.

691
00:32:34,040 --> 00:32:37,720
És valóban írtál
bináris keresés PSET3,

692
00:32:37,720 --> 00:32:40,100
ahol végre a find programot.

693
00:32:40,100 --> 00:32:40,890
De tudod, mit.

694
00:32:40,890 --> 00:32:45,060
Van egyfajta többet
okos módja ennek.

695
00:32:45,060 --> 00:32:47,390
Ez egy kicsit
kifinomult és ez talán

696
00:32:47,390 --> 00:32:50,830
lehetővé teszi számunkra, hogy miért bináris
Keresés annyira sokkal gyorsabb.

697
00:32:50,830 --> 00:32:52,980
Először is, hadd vezessen be
a fogalom a fán.

698
00:32:52,980 --> 00:32:54,730
Mely, bár a
valóság fák fajta

699
00:32:54,730 --> 00:32:57,730
nőnek, mint ez, a világ számítógép
a tudomány azt a fajta nő lefelé

700
00:32:57,730 --> 00:33:00,830
mint egy családfát, ahol van,
a nagyszülők vagy a dédszüleim

701
00:33:00,830 --> 00:33:04,580
vagy miegymás tetején, a pátriárka és
A családfő anya a család, csak egy

702
00:33:04,580 --> 00:33:07,930
úgynevezett gyökér, csomópont, az alábbiakban
amelyek a gyermekek,

703
00:33:07,930 --> 00:33:11,442
alatt, amelyek a gyermekek, illetve
leszármazottai általában.

704
00:33:11,442 --> 00:33:13,400
És bárki lógott le
az alján a család

705
00:33:13,400 --> 00:33:16,070
fa, amellett, hogy a
legfiatalabb a családban,

706
00:33:16,070 --> 00:33:19,520
is csak legyen általánosan
az úgynevezett levelek a fa.

707
00:33:19,520 --> 00:33:21,800
>> Tehát ez csak egy csomó
A szavak és kifejezések

708
00:33:21,800 --> 00:33:25,790
valami úgynevezett fa számítógép
a tudomány, mint egy családfát.

709
00:33:25,790 --> 00:33:28,770
De van cifrább inkarnációja
a fák, amelyek közül az egyik

710
00:33:28,770 --> 00:33:30,780
az úgynevezett bináris kereső fa.

711
00:33:30,780 --> 00:33:34,380
És akkor milyen kötekedik
eltekintve mi ez a dolog nem.

712
00:33:34,380 --> 00:33:37,180
Nos, ez a bináris milyen értelemben?

713
00:33:37,180 --> 00:33:41,455
Amennyiben ez a bináris származik itt?

714
00:33:41,455 --> 00:33:41,955
Bocsánat?

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

716
00:33:45,961 --> 00:33:47,210
Ez nem is annyira sem vagy.

717
00:33:47,210 --> 00:33:52,000
Ez több, hogy az egyes csomópontok nem rendelkezik
Több mint két gyerek, mint látjuk itt.

718
00:33:52,000 --> 00:33:54,990
Általában egy tree-- és
a szülők és nagyszülők

719
00:33:54,990 --> 00:33:57,640
Egyszerre annyi gyerek, vagy
unoka, mert valójában akar,

720
00:33:57,640 --> 00:34:00,820
és így például ott van három
a gyerekek ki, hogy jobb csomópont,

721
00:34:00,820 --> 00:34:05,480
de egy bináris fa, egy csomópont
nulla, egy vagy két gyermek maximálisan.

722
00:34:05,480 --> 00:34:08,496
És ez egy jó tulajdonság,
mert ha ez a két kupakkal,

723
00:34:08,496 --> 00:34:10,620
fogunk tudni
egy kicsit napló bázis két

724
00:34:10,620 --> 00:34:11,975
akció folyik itt végül.

725
00:34:11,975 --> 00:34:13,350
Tehát van valami logaritmikus.

726
00:34:13,350 --> 00:34:14,558
De még az, hogy egy pillanat alatt.

727
00:34:14,558 --> 00:34:19,810
Keresés fa azt jelenti, hogy a számok
elrendezve, hogy a bal oldali gyermek

728
00:34:19,810 --> 00:34:22,429
érték nagyobb, mint a gyökér.

729
00:34:22,429 --> 00:34:26,010
És a jobb fia
nagyobb, mint a gyökér.

730
00:34:26,010 --> 00:34:29,290
Más szóval, ha Ön bármely
csomópontok, a körök ezt a képet,

731
00:34:29,290 --> 00:34:31,840
és megnézi a bal
gyermek és jobb fia,

732
00:34:31,840 --> 00:34:34,739
az első legyen kisebb, mint,
a második nagyobbnak kell lennie, mint.

733
00:34:34,739 --> 00:34:36,159
Így a józanság ellenőrizheti 55.

734
00:34:36,159 --> 00:34:37,780
Ez maradt gyermek 33.

735
00:34:37,780 --> 00:34:38,620
Ez kevesebb, mint.

736
00:34:38,620 --> 00:34:40,929
55, a jobb fia 77.

737
00:34:40,929 --> 00:34:41,783
Ez nagyobb, mint.

738
00:34:41,783 --> 00:34:43,199
És ez egy rekurzív definíció.

739
00:34:43,199 --> 00:34:46,480
Mi lehetett ellenőrizni minden egyike azoknak
csomópontok és ugyanazt a mintát tartana.

740
00:34:46,480 --> 00:34:49,389
>> Szóval mi szép egy
bináris kereső fa, az

741
00:34:49,389 --> 00:34:52,204
hogy az egyik, akkor végrehajtja
egy struct, mint ez.

742
00:34:52,204 --> 00:34:54,620
És bár mi dobott
Sok struktúrák a,

743
00:34:54,620 --> 00:34:56,560
ők valamelyest
intuitív most remélhetőleg.

744
00:34:56,560 --> 00:35:00,570
A szintaxis mindig misztikus biztos,
de a tartalmát egy csomópont ebben

745
00:35:00,570 --> 00:35:02,786
context-- és mi folyamatosan
szó használata a csomópont,

746
00:35:02,786 --> 00:35:04,910
hogy ez egy téglalap
a képernyőn, vagy egy kör,

747
00:35:04,910 --> 00:35:08,970
ez csak néhány általános tároló,
Ebben az esetben egy fa, mint az egyik

748
00:35:08,970 --> 00:35:11,780
láttuk, szükségünk van egy egész szám
az egyes csomópontok

749
00:35:11,780 --> 00:35:15,460
és aztán kell két mutató mutató
balra a gyermek és a megfelelő gyermek,

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

751
00:35:16,590 --> 00:35:20,730
Szóval így talán
végre, hogy egy struktúra.

752
00:35:20,730 --> 00:35:22,315
És hogyan lehet azt megvalósítani, hogy a kódot?

753
00:35:22,315 --> 00:35:26,730
Nos, vessünk egy gyors
nézd meg ezt a kis példát.

754
00:35:26,730 --> 00:35:29,820
Ez nem működőképes, de már
vágólapra másolni, hogy a struktúra.

755
00:35:29,820 --> 00:35:33,510
És ha én a funkció egy bináris
keresési fa az úgynevezett kereső,

756
00:35:33,510 --> 00:35:36,980
és ez a két paramétert,
n egész és egy mutatót

757
00:35:36,980 --> 00:35:41,400
A csomóponthoz, így egy mutatót a fán
vagy egy mutatót a fa gyökerét,

758
00:35:41,400 --> 00:35:43,482
hogyan megy körülbelül keresi N?

759
00:35:43,482 --> 00:35:45,440
Nos, először is, mert én vagyok
foglalkozó mutatók,

760
00:35:45,440 --> 00:35:46,750
Azt fogom tenni a józanság csekket.

761
00:35:46,750 --> 00:35:54,279
Ha fa egyenlők egyenlő null, N
a fán vagy nem a fán?

762
00:35:54,279 --> 00:35:55,070
Nem lehet, nem?

763
00:35:55,070 --> 00:35:56,870
Ha én vagyok már null,
nincs ott semmi.

764
00:35:56,870 --> 00:35:59,230
Én akár azt is csak
vakon mondják vissza hamis.

765
00:35:59,230 --> 00:36:04,050
Ha adsz nekem semmi, én biztosan nem
találtunk száma N. Szóval mi mást én

766
00:36:04,050 --> 00:36:04,750
ellenőrizd most?

767
00:36:04,750 --> 00:36:12,830
Azt fogom mondani jól mást, ha N
kevesebb, mint amit az a facsomópont

768
00:36:12,830 --> 00:36:16,300
hogy én már átadta N értéket.

769
00:36:16,300 --> 00:36:20,270
Más szóval, ha a szám én
keres, az N, kevesebb, mint a csomópont

770
00:36:20,270 --> 00:36:21,340
hogy nézem.

771
00:36:21,340 --> 00:36:23,190
És a csomópont keresem
A nevezik fa,

772
00:36:23,190 --> 00:36:26,370
és emlékszem az előző példában
eljutni az értéket egy mutatót,

773
00:36:26,370 --> 00:36:28,310
Én a nyíl jelöléssel.

774
00:36:28,310 --> 00:36:35,960
Tehát, ha az N-nél kisebb fa nyíl
N, azt akarom, hogy koncepcionálisan menni balra.

775
00:36:35,960 --> 00:36:38,590
Hogyan kifejezetten keresi maradt?

776
00:36:38,590 --> 00:36:41,560
Ahhoz, hogy tiszta, ha ez
a kép a szóban forgó,

777
00:36:41,560 --> 00:36:44,612
és én már át, hogy a legfelső
nyíl, ami lefelé mutat.

778
00:36:44,612 --> 00:36:45,570
Ez az én fa mutató.

779
00:36:45,570 --> 00:36:48,060
Én mutatott a gyökér a fa.

780
00:36:48,060 --> 00:36:52,100
És keresem mondjuk,
száma 44, önkényesen.

781
00:36:52,100 --> 00:36:55,300
44-nél kisebb, vagy
nagyobb, mint 55 nyilvánvalóan?

782
00:36:55,300 --> 00:36:56,360
Szóval ez kevesebb, mint.

783
00:36:56,360 --> 00:36:58,760
És így ez, ha a feltétel.

784
00:36:58,760 --> 00:37:03,981
Tehát elméletileg, mit akarok
keresés jövő, ha keresem 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Pontosan, szeretnék
keresés a bal gyermek,

788
00:37:11,100 --> 00:37:12,789
vagy a bal oldali részfa kép.

789
00:37:12,789 --> 00:37:14,830
És valóban, hadd keresztül
A képet itt lent

790
00:37:14,830 --> 00:37:17,770
csak egy pillanatra, hiszen
Nem tudom karcolja meg ezt.

791
00:37:17,770 --> 00:37:21,150
Ha elkezdek itt a 55., és a
Tudom, hogy az érték 44

792
00:37:21,150 --> 00:37:23,180
Keresem az, hogy
A bal, ez a fajta

793
00:37:23,180 --> 00:37:26,010
hasonló tépte a telefonkönyvből
fél- vagy könnyezés a fa felét.

794
00:37:26,010 --> 00:37:29,660
Én már nem kell törődnünk
ezt az egész fele a fa.

795
00:37:29,660 --> 00:37:33,270
És mégis, kíváncsian szempontjából a
szerkezete, ez a dolog itt, hogy

796
00:37:33,270 --> 00:37:36,682
kezdődik a 33., hogy maga
egy bináris kereső fa.

797
00:37:36,682 --> 00:37:39,890
Azt mondta, a szó rekurzív előtt, mert
Valóban ez egy adatstruktúrát, amely

798
00:37:39,890 --> 00:37:41,707
definíció rekurzív.

799
00:37:41,707 --> 00:37:44,540
Lehet, hogy egy fát, hogy ez
nagy, de minden embernél a gyerekeknek

800
00:37:44,540 --> 00:37:46,870
jelent egy fa, csak egy kicsit kisebb.

801
00:37:46,870 --> 00:37:50,910
Ahelyett hogy a nagypapa
vagy a nagymama, most már csak anya

802
00:37:50,910 --> 00:37:54,300
or-- nem tudok say-- nem anya
vagy apa, hogy furcsa lenne.

803
00:37:54,300 --> 00:37:59,000
Ehelyett a két gyerek van
lenne, mint testvére és a testvér.

804
00:37:59,000 --> 00:38:01,120
Az új generációs családfáját.

805
00:38:01,120 --> 00:38:02,900
De szerkezetileg, ez ugyanaz a gondolat.

806
00:38:02,900 --> 00:38:06,790
És kiderül, van egy funkció
amellyel tudok keresni egy bináris keresés

807
00:38:06,790 --> 00:38:07,290
fa.

808
00:38:07,290 --> 00:38:08,680
Úgy hívják keresést.

809
00:38:08,680 --> 00:38:17,870
Én keresni N fa nyíl balra
mást ha n értéke nagyobb, mint az érték

810
00:38:17,870 --> 00:38:18,870
hogy én vagyok jelenleg.

811
00:38:18,870 --> 00:38:20,800
55 A történet egy perce.

812
00:38:20,800 --> 00:38:23,780
Van olyan függvény is
kereső, amely tudok csak

813
00:38:23,780 --> 00:38:29,660
át N ezt, és rekurzív keresés
Az al-fát, és csak vissza

814
00:38:29,660 --> 00:38:30,620
akármit is választ.

815
00:38:30,620 --> 00:38:33,530
Mást kaptam néhány végső alapeset itt.

816
00:38:33,530 --> 00:38:35,310
>> Mi a végső esetben?

817
00:38:35,310 --> 00:38:36,570
Fa vagy null.

818
00:38:36,570 --> 00:38:39,980
Az érték Engem sem keres
kevesebb, mint ez, vagy nagyobb, mint a

819
00:38:39,980 --> 00:38:42,610
vagy egyenlő vele.

820
00:38:42,610 --> 00:38:44,750
És azt is mondhatnám egyenlő
egyenlő, de logikusan ez

821
00:38:44,750 --> 00:38:46,500
egyenértékű csak azt mondom, itt még.

822
00:38:46,500 --> 00:38:49,150
Tehát igaz az, hogy hogyan találok valamit.

823
00:38:49,150 --> 00:38:51,710
Így remélhetőleg ez egy
még vonzóbb például

824
00:38:51,710 --> 00:38:54,900
mint a hülye szigma funkció
csináltunk egy pár előadásra vissza,

825
00:38:54,900 --> 00:38:58,360
ahol éppen olyan könnyen használható a hurok
számoljon el a számokat az egyik

826
00:38:58,360 --> 00:39:02,390
N. Itt egy adatstruktúrát
hogy maga rekurzív

827
00:39:02,390 --> 00:39:07,050
meghatározott és rekurzív húzott, most
megvan a képessége, hogy kifejezze magunkat

828
00:39:07,050 --> 00:39:09,780
A kód, amely önmagában rekurzív.

829
00:39:09,780 --> 00:39:12,580
Tehát ez pontosan ugyanazt a kódot itt.

830
00:39:12,580 --> 00:39:14,400
>> Tehát mi más problémák tudjuk megoldani?

831
00:39:14,400 --> 00:39:18,160
Tehát egy gyors lépésre
fák csak egy pillanatra.

832
00:39:18,160 --> 00:39:20,130
Itt van, mondjuk, a német zászló.

833
00:39:20,130 --> 00:39:22,020
És ott egyértelműen a
minta ez a zászló.

834
00:39:22,020 --> 00:39:23,811
És van sok
zászlók a világ, hogy

835
00:39:23,811 --> 00:39:27,560
olyan egyszerű, mint ez szempontjából
a színek és minták.

836
00:39:27,560 --> 00:39:31,930
De tegyük fel, hogy ez tárolja a
GIF, vagy JPEG, vagy bitmap, vagy egy ping,

837
00:39:31,930 --> 00:39:34,240
egy grafikus fájlformátum
amellyel még nem ismeri,

838
00:39:34,240 --> 00:39:36,460
amelyek közül néhány vagyunk
játszik a PSET4.

839
00:39:36,460 --> 00:39:41,550
Ez nem tűnik érdemes tárolni
fekete pixel, fekete pixel, fekete pixel,

840
00:39:41,550 --> 00:39:44,790
dot, pont, pont, egy csomó
fekete képpont az első soronkénti,

841
00:39:44,790 --> 00:39:47,430
vagy sor, akkor egy csomó
ugyanaz, akkor egy csomó

842
00:39:47,430 --> 00:39:49,530
az azonos, majd egy
csomó piros pixel,

843
00:39:49,530 --> 00:39:53,020
piros pixel, piros pixel, majd egy egész
csokor sárga képpont, sárga, ugye?

844
00:39:53,020 --> 00:39:55,050
>> Van egy ilyen eredménytelenség itt.

845
00:39:55,050 --> 00:39:59,040
Hogyan írnád intuitívan
tömöríteni a német zászló

846
00:39:59,040 --> 00:40:01,320
Ha azt végrehajtó fájlként?

847
00:40:01,320 --> 00:40:04,940
Például mit információt nem tudunk
zavarja tárolása a lemezen érdekében

848
00:40:04,940 --> 00:40:08,040
csökkenti a fájl mérete, mint a
egy megabyte egy kilobyte, valami

849
00:40:08,040 --> 00:40:09,430
kisebb?

850
00:40:09,430 --> 00:40:13,130
Ahol rejlik a redundancia
Itt tisztázni kell?

851
00:40:13,130 --> 00:40:13,880
Mit tehetett volna?

852
00:40:13,880 --> 00:40:14,380
Igen?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Pontosan.

855
00:40:21,970 --> 00:40:24,550
Miért nem inkább emlékezni
a színe minden rohadt pixel

856
00:40:24,550 --> 00:40:28,200
mint te csinálsz itt PSET4
A bitmap file formátum,

857
00:40:28,200 --> 00:40:32,060
miért nem csak képviseli a
bal szélső oszlopában pixel, például

858
00:40:32,060 --> 00:40:35,370
Egy csomó fekete képpontok, egy csomó
vörös, és egy csomó sárga,

859
00:40:35,370 --> 00:40:39,210
és aztán csak valahogy kódolják
ötlete ismételje ezt 100-szor

860
00:40:39,210 --> 00:40:41,020
vagy ismételje meg ezt a 1000-szer?

861
00:40:41,020 --> 00:40:43,430
Amennyiben 100 vagy 1000 van
Csak egy egész szám, így

862
00:40:43,430 --> 00:40:47,290
lehet megúszni csak egy számot
helyett száz vagy több ezer

863
00:40:47,290 --> 00:40:48,270
további pixel.

864
00:40:48,270 --> 00:40:50,990
És valóban, mi így
lehet tömöríteni a német zászlót.

865
00:40:50,990 --> 00:40:51,490
És

866
00:40:51,490 --> 00:40:53,470
Most mi a helyzet a francia zászló?

867
00:40:53,470 --> 00:40:58,930
És egy kicsit valamiféle
mentális gyakorlat, amely zászló

868
00:40:58,930 --> 00:41:01,040
lehet tömörített több lemezen?

869
00:41:01,040 --> 00:41:05,720
A német zászló, vagy a francia
zászló, ha vesszük ezt a megközelítést?

870
00:41:05,720 --> 00:41:08,490
A német zászló, mert van
több vízszintes redundancia.

871
00:41:08,490 --> 00:41:12,190
És a programok kialakítása, sok grafikus fájl
formátumok valóban működik nevén képsorok

872
00:41:12,190 --> 00:41:12,830
vízszintesen.

873
00:41:12,830 --> 00:41:14,674
Tudtak dolgozni
függőlegesen, csak az emberiség

874
00:41:14,674 --> 00:41:17,090
úgy döntött évvel ezelőtt, hogy mi lesz
általában gondolni a dolgokat sorban

875
00:41:17,090 --> 00:41:18,880
által, hanem egymás oszlopról oszlopra.

876
00:41:18,880 --> 00:41:20,820
Tehát valóban, ha volt
hogy nézd meg a fájl

877
00:41:20,820 --> 00:41:24,670
akkora, mint egy német és egy francia zászló
zászló, mindaddig, amíg a felbontás

878
00:41:24,670 --> 00:41:27,530
az azonos, azonos szélességű
és a magasság, ez az egy

879
00:41:27,530 --> 00:41:31,580
Itt lesz nagyobb, mert
meg kell ismételni magát háromszor.

880
00:41:31,580 --> 00:41:35,570
Meg kell adnia a kék, ismételje
magad, fehér, ismételje meg magad, piros,

881
00:41:35,570 --> 00:41:36,740
ismételje magát.

882
00:41:36,740 --> 00:41:39,000
Nem lehet csak úgy megy minden
Az utat a jobb oldalon.

883
00:41:39,000 --> 00:41:41,200
És mint félre, hogy
törölje a kompressziós

884
00:41:41,200 --> 00:41:43,910
mindenütt jelen van, ha ezek
négy kép egy video-- akkor

885
00:41:43,910 --> 00:41:45,890
Lehet emlékeztetnek arra, hogy egy film
vagy video általában

886
00:41:45,890 --> 00:41:47,286
mint 29 vagy 30 képkocka másodpercenként.

887
00:41:47,286 --> 00:41:50,410
Ez olyan, mint egy kis flip könyv, ahol
csak lásd kép, kép, kép, képek,

888
00:41:50,410 --> 00:41:54,410
A kép csak szuper gyors, így néz ki
A szereplők a képernyőn mozog.

889
00:41:54,410 --> 00:41:57,130
Itt egy poszméh a
tetején egy csokor virágot.

890
00:41:57,130 --> 00:41:59,790
És bár lehet, hogy egyfajta
nehéz belátni, hogy az első pillantásra,

891
00:41:59,790 --> 00:42:04,020
Az egyetlen dolog, mozgó
ez a film a méhek.

892
00:42:04,020 --> 00:42:06,880
>> Milyen buta tárolásával kapcsolatban
videó tömörítés nélkül?

893
00:42:06,880 --> 00:42:11,420
Elég egy hulladék tárolására videó
négy, közel azonos képek

894
00:42:11,420 --> 00:42:13,670
különböznek csak annyiban, amennyiben a méh.

895
00:42:13,670 --> 00:42:16,280
Akkor dobja el a legtöbb
Ezen információk

896
00:42:16,280 --> 00:42:20,190
és emlékszem csak, például,
Az első keret és az utolsó képkocka,

897
00:42:20,190 --> 00:42:22,180
fő kereteket, ha már
Hallottál már a szó,

898
00:42:22,180 --> 00:42:24,337
és csak tárolja az
közepén, ahol a méh.

899
00:42:24,337 --> 00:42:26,170
És akkor nem kell
tárolja az összes a rózsaszín,

900
00:42:26,170 --> 00:42:28,330
és a kék, és a
zöld értékeket is.

901
00:42:28,330 --> 00:42:31,200
Tehát ez csak azt jelenti, hogy
tömörítés mindenhol.

902
00:42:31,200 --> 00:42:34,900
Ez egy technika, gyakran használja
vagy magától értetődőnek ezekben a napokban.

903
00:42:34,900 --> 00:42:38,750
>> De hogyan tömöríteni szöveget?

904
00:42:38,750 --> 00:42:40,450
Hogyan megy körülbelül tömörítése szöveget?

905
00:42:40,450 --> 00:42:45,410
Nos, mind a karakterek
Az ASCII egy bájt, illetve nyolc bit.

906
00:42:45,410 --> 00:42:47,360
És ez a fajta buta, ugye?

907
00:42:47,360 --> 00:42:51,160
Mert akkor valószínűleg típusú
és E I és O, U sokat

908
00:42:51,160 --> 00:42:55,270
gyakrabban, mint, mint a W vagy Q vagy Z,
attól függően, hogy milyen nyelven

909
00:42:55,270 --> 00:42:56,610
írsz biztosan.

910
00:42:56,610 --> 00:42:59,600
És így miért is használ
nyolc bit minden levelet,

911
00:42:59,600 --> 00:43:02,040
köztük a legkevésbé
népszerű leveleket, ugye?

912
00:43:02,040 --> 00:43:05,300
Miért nem használ kevesebb bitet
A szuper népszerű betűk,

913
00:43:05,300 --> 00:43:07,760
mint az E, a dolgok akkor hiszem,
első Szerencsekerék,

914
00:43:07,760 --> 00:43:10,450
és több bitet
A kevésbé népszerű leveleket?

915
00:43:10,450 --> 00:43:10,950
Miért?

916
00:43:10,950 --> 00:43:13,130
Mert mi csak fog
használja őket ritkábban.

917
00:43:13,130 --> 00:43:15,838
>> Nos, kiderült, hogy ott van
Történtek próbálkozások erre.

918
00:43:15,838 --> 00:43:18,630
És ha visszahívja évfolyam
iskolában vagy középiskolában, morze.

919
00:43:18,630 --> 00:43:20,400
Morse kód pontok
és gondolatjelek, hogy lehet

920
00:43:20,400 --> 00:43:24,270
adódik át egy vezetéket, mint
hangok vagy jelek néhány sort.

921
00:43:24,270 --> 00:43:25,930
De morze egy szuper tiszta.

922
00:43:25,930 --> 00:43:29,010
Elég egy bináris rendszer
hogy van a pontok vagy gondolatjelek.

923
00:43:29,010 --> 00:43:30,977
De ha úgy látja, hogy például két pont.

924
00:43:30,977 --> 00:43:33,810
Vagy ha úgy gondolja, vissza a kezelő
aki megy, mint sípszó sípszó, sípszó,

925
00:43:33,810 --> 00:43:36,760
sípolás, ütő egy kicsit ravaszt
hogy egy jelet,

926
00:43:36,760 --> 00:43:40,360
ha a címzett, kap két
pöttyök, milyen üzenetet kaptál?

927
00:43:40,360 --> 00:43:43,490
Teljesen önkényes.

928
00:43:43,490 --> 00:43:44,450
>> Én?

929
00:43:44,450 --> 00:43:45,060
Én?

930
00:43:45,060 --> 00:43:47,500
Vagy mi about-- vagy én?

931
00:43:47,500 --> 00:43:49,570
Lehet, hogy csak két E jogát?

932
00:43:49,570 --> 00:43:52,480
Szóval van ez a probléma
A decodability Morse

933
00:43:52,480 --> 00:43:54,890
kódot, amellyel kivéve, ha a
küldője akkor az üzenet

934
00:43:54,890 --> 00:43:59,510
valóban szünetel, így egyfajta
lát vagy hall a rések között levelek,

935
00:43:59,510 --> 00:44:02,990
ez nem elegendő csupán
Levél egy patak nullák,

936
00:44:02,990 --> 00:44:05,610
vagy pontok és vonalak,
mert ott van a kétértelműség.

937
00:44:05,610 --> 00:44:08,640
E egyetlen pont, így ha
hogy két pont, vagy hallani két pont,

938
00:44:08,640 --> 00:44:11,254
talán két E által vagy talán ez az egyik I.

939
00:44:11,254 --> 00:44:13,670
Tehát szükségünk van egy olyan rendszer, amely egy
kicsit okosabb annál.

940
00:44:13,670 --> 00:44:16,851
Tehát egy ember nevű Huffman év
ezelőtt jött össze pontosan ezt.

941
00:44:16,851 --> 00:44:18,600
Szóval csak úgy
hogy egy gyors pillantást

942
00:44:18,600 --> 00:44:20,114
hogy milyen fák illenek ehhez.

943
00:44:20,114 --> 00:44:22,530
Tegyük fel, hogy ez az egyes
hülye üzenetet küldeni szeretné,

944
00:44:22,530 --> 00:44:26,342
tagjai: csak A, B, C a D és az E-k,
de van egy csomó redundancia itt.

945
00:44:26,342 --> 00:44:27,550
Ez nem azt jelentette, hogy az angol.

946
00:44:27,550 --> 00:44:28,341
Ez nem titkosított.

947
00:44:28,341 --> 00:44:30,540
Ez csak egy hülye üzenetet
sok az ismétlés.

948
00:44:30,540 --> 00:44:34,010
Tehát, ha valóban számít ki az összes
A., B., C-, D és E a, itt van

949
00:44:34,010 --> 00:44:34,890
A frekvencia.

950
00:44:34,890 --> 00:44:37,800
20% -a a betűk
A., 45% -a a betűk

951
00:44:37,800 --> 00:44:39,660
az E-k, és három másik frekvencián.

952
00:44:39,660 --> 00:44:41,960
Mi számít ott kézzel
és csak nem a matek.

953
00:44:41,960 --> 00:44:44,579
>> Így kiderül, hogy a
Huffman, néhány évvel ezelőtt,

954
00:44:44,579 --> 00:44:46,620
rájött, hogy, tudod,
mit, ha elkezdek épület

955
00:44:46,620 --> 00:44:51,172
egy fa, vagy erdei fák, ha úgy tetszik,
az alábbiak szerint, meg tudom csinálni a következő.

956
00:44:51,172 --> 00:44:53,880
Megyek, hogy egy csomópont minden
A betűk érdekel

957
00:44:53,880 --> 00:44:55,530
és megyek tárolni
belsejében a csomóponton

958
00:44:55,530 --> 00:44:58,610
A frekvenciák lebegőpontos
értéket, vagy ha lehet használni egy N is

959
00:44:58,610 --> 00:45:00,210
de majd csak használ egy úszó van.

960
00:45:00,210 --> 00:45:03,100
És az algoritmus, hogy
azt javasolta, hogy meg

961
00:45:03,100 --> 00:45:07,210
ezt erdő egyes csomópont
fák, így szuper rövid fák,

962
00:45:07,210 --> 00:45:11,920
és elkezd összekötő őket
Új csoportok, új szülők, ha úgy tetszik.

963
00:45:11,920 --> 00:45:16,150
És akkor ezt választotta a
két legkisebb frekvencia egy időben.

964
00:45:16,150 --> 00:45:18,110
Szóval vettem 10% és 10%.

965
00:45:18,110 --> 00:45:19,090
Én hozzon létre egy új csomópontot.

966
00:45:19,090 --> 00:45:20,910
És hívom az új csomópont 20%.

967
00:45:20,910 --> 00:45:22,750
>> Melyik két csomópont egyszerre többféle jövő?

968
00:45:22,750 --> 00:45:23,810
Ez egy kicsit félreérthető.

969
00:45:23,810 --> 00:45:26,643
Szóval egy kis sarok ügyek
fontolja meg, de a dolgokat elég,

970
00:45:26,643 --> 00:45:29,300
Megyek választhat 20% -
Én most figyelmen kívül hagyja a gyerekeket.

971
00:45:29,300 --> 00:45:33,640
Megyek választhat 20% és
15% és felhívni két új élek.

972
00:45:33,640 --> 00:45:35,624
És most, amely két csomópontot
tudom logikailag összekapcsolják?

973
00:45:35,624 --> 00:45:38,540
Figyelmen kívül hagyja a gyerekek, mind a
unokái, csak nézd meg a gyökereket

974
00:45:38,540 --> 00:45:39,070
Most.

975
00:45:39,070 --> 00:45:42,220
Melyik két csomópont tudom köti össze?

976
00:45:42,220 --> 00:45:44,530
Pont két és 0,35.

977
00:45:44,530 --> 00:45:45,890
Szóval hadd hívjam két új élek.

978
00:45:45,890 --> 00:45:47,570
És akkor már csak egy maradt.

979
00:45:47,570 --> 00:45:48,650
Tehát itt egy fa.

980
00:45:48,650 --> 00:45:51,160
És ez már kiállított szándékosan
nézni milyen szép,

981
00:45:51,160 --> 00:45:55,870
de észrevettem, hogy a széleken is
is jelzett nulla és egy.

982
00:45:55,870 --> 00:45:59,510
Tehát mind a bal szélétől nulla
önkényesen, de következetesen.

983
00:45:59,510 --> 00:46:01,170
Minden a megfelelő élek is.

984
00:46:01,170 --> 00:46:05,070
>> És akkor mi van Hoffman javasolt,
Ha azt szeretnénk, hogy képviselje a B,

985
00:46:05,070 --> 00:46:10,080
ahelyett képviseli a szám 66, mint
ASCII amely nyolc teljes bit,

986
00:46:10,080 --> 00:46:13,360
tudod mit, csak boltba
A minta nulla, nulla, nulla,

987
00:46:13,360 --> 00:46:17,030
nulla, mert ez az út
az én fa, Mr. Huffman fája,

988
00:46:17,030 --> 00:46:18,600
A levél a gyökér.

989
00:46:18,600 --> 00:46:20,970
Ha szeretnéd tárolni
E ezzel szemben nem

990
00:46:20,970 --> 00:46:26,290
Levél nyolc bit, hogy képviselje az E.
Ehelyett küldeni, milyen mintát bitek?

991
00:46:26,290 --> 00:46:26,890
Egy.

992
00:46:26,890 --> 00:46:30,410
És mi a szép ez,
hogy az E a legnépszerűbb írni,

993
00:46:30,410 --> 00:46:32,340
valamint ha a
legrövidebb kódot hozzá.

994
00:46:32,340 --> 00:46:34,090
A következő legnépszerűbb
levél néz ki, hogy

995
00:46:34,090 --> 00:46:37,380
volt A. És így hány bitet
mondott javaslatot használ ez?

996
00:46:37,380 --> 00:46:38,270
Nulla, egy.

997
00:46:38,270 --> 00:46:41,060
>> És mert ez végre
mivel ez a fa, most

998
00:46:41,060 --> 00:46:43,350
hadd kikötik van
egyértelműen meg a Morse-

999
00:46:43,350 --> 00:46:46,090
kódot, mert az összes
betűk törődsz

1000
00:46:46,090 --> 00:46:48,780
vannak végén ezeket élek.

1001
00:46:48,780 --> 00:46:50,580
Szóval ez csak egy
alkalmazása egy fa.

1002
00:46:50,580 --> 00:46:52,538
Ez is-- és én hullám
kezem ebben hogyan

1003
00:46:52,538 --> 00:46:55,570
Lehet végrehajtani ezt a C szerkezetet.

1004
00:46:55,570 --> 00:46:58,260
Csak meg kell kombinálni
egy szimbólum, mint egy char,

1005
00:46:58,260 --> 00:46:59,910
és a frekvencia balra és jobbra.

1006
00:46:59,910 --> 00:47:02,510
De nézzük meg a két
utolsó példa, hogy akkor

1007
00:47:02,510 --> 00:47:06,070
kap elég ismerős után
kvíz nulla probléma meg öt.

1008
00:47:06,070 --> 00:47:09,210
>> Tehát van az adatstruktúra
néven hash tábla.

1009
00:47:09,210 --> 00:47:12,247
És egy hash tábla fajta
király, mivel úgy rendelkezik vödrök.

1010
00:47:12,247 --> 00:47:14,830
És tegyük fel, van négy vödör
itt van, csak négy üres helyeket.

1011
00:47:14,830 --> 00:47:20,830
Itt egy pakli kártyát, és itt van
klub, ásó, klub, gyémánt, klub,

1012
00:47:20,830 --> 00:47:25,960
gyémánt, klub, gyémánt,
clubs-- így ez a véletlen.

1013
00:47:25,960 --> 00:47:30,330
Szívek, hearts-- úgyhogy
bucketizing az összes bemenet van.

1014
00:47:30,330 --> 00:47:32,430
És egy hash table-nek
hogy nézd meg a bemeneti,

1015
00:47:32,430 --> 00:47:34,850
majd betette egy bizonyos
helyezze az alapján, amit látsz.

1016
00:47:34,850 --> 00:47:35,600
Ez egy algoritmust.

1017
00:47:35,600 --> 00:47:37,980
És én is használtam egy szuper
egyszerű vizuális algoritmus.

1018
00:47:37,980 --> 00:47:40,030
A legnehezebb része az volt,
eszébe jutott, amit a képek voltak.

1019
00:47:40,030 --> 00:47:41,590
És akkor ott van négy teljes dolgokat.

1020
00:47:41,590 --> 00:47:45,440
>> Most a halom nőttek, ami
egy tudatos tervezés dolog itt.

1021
00:47:45,440 --> 00:47:46,540
De mi mást tehetek?

1022
00:47:46,540 --> 00:47:49,080
Szóval tényleg itt van egy
csomó régi iskolai vizsga könyveket.

1023
00:47:49,080 --> 00:47:51,240
Tegyük fel, hogy egy csomó
hallgatók nevek itt.

1024
00:47:51,240 --> 00:47:52,570
Itt egy nagyobb hash tábla.

1025
00:47:52,570 --> 00:47:54,867
Négy helyett vödrök,
Én, mondjuk 26.

1026
00:47:54,867 --> 00:47:57,950
És nem akartunk menni kölcsönkérni 26
dolgokat kívülről [? Annenberg?], Így

1027
00:47:57,950 --> 00:48:00,289
Itt van öt képviselő
A-tól Z És ha én

1028
00:48:00,289 --> 00:48:03,580
hogy egy diák, akinek a neve kezdődik,
Megyek tegye saját kvíz ott.

1029
00:48:03,580 --> 00:48:08,850
Ha valaki kezdődik C, ott,
Egy-- valójában, nem akartam ezt tenni.

1030
00:48:08,850 --> 00:48:10,060
B megy át ide.

1031
00:48:10,060 --> 00:48:13,390
Így kaptam az A és B és C és
Most itt egy másik diák.

1032
00:48:13,390 --> 00:48:16,212
De ha ez a hash tábla
végre egy sor,

1033
00:48:16,212 --> 00:48:17,920
Én ilyen csavarni
Ezen a ponton, igaz?

1034
00:48:17,920 --> 00:48:19,510
Valahogy meg kell tenni ennek valahol.

1035
00:48:19,510 --> 00:48:24,380
>> Tehát az egyik mód arra, hogy megoldja ezt, minden
Jobbra egy forgalmas, B foglalt, C foglalt.

1036
00:48:24,380 --> 00:48:28,880
Megyek, hogy őt D. Tehát
Először is, én véletlen azonnali hozzáférést

1037
00:48:28,880 --> 00:48:31,064
az egyes kanalak a diákok számára.

1038
00:48:31,064 --> 00:48:33,230
De most ez a fajta decentralizált
valami lineáris,

1039
00:48:33,230 --> 00:48:36,750
mert ha akarok keresni valakit
akinek a neve kezdődik, megnézem itt.

1040
00:48:36,750 --> 00:48:38,854
De ha ez nem az A
hallgató keresem,

1041
00:48:38,854 --> 00:48:41,520
Valahogy el kell kezdeni ellenőrzése
A vödrök, mert amit tettem

1042
00:48:41,520 --> 00:48:44,530
afféle lineárisan
szonda adatok szerkezetét.

1043
00:48:44,530 --> 00:48:47,710
Egy hülye szóval csak nézz
az első rendelkezésre álló nyitó,

1044
00:48:47,710 --> 00:48:51,850
és tedd egy B terv, hogy úgy mondjam,
vagy terv D ebben az esetben az értéket

1045
00:48:51,850 --> 00:48:53,340
e helyett.

1046
00:48:53,340 --> 00:48:56,470
Ez csak úgy, hogy ha már
Van 26 helyszínen, és nem a diákok

1047
00:48:56,470 --> 00:49:00,600
A név Q vagy Z, vagy valami ilyesmi
hogy legalábbis, amit használ a teret.

1048
00:49:00,600 --> 00:49:03,140
>> De már látott több
Okos megoldás itt van, ugye?

1049
00:49:03,140 --> 00:49:04,870
Mit tennél helyett
ha van egy ütközés?

1050
00:49:04,870 --> 00:49:06,670
Ha két ember
A megnevezés, mi lenne

1051
00:49:06,670 --> 00:49:09,160
már egy okosabb vagy több
intuitív megoldás, mint

1052
00:49:09,160 --> 00:49:12,840
Elhelyezés egy D helyére kéne lennie?

1053
00:49:12,840 --> 00:49:14,810
Miért nem csak megy
kívül [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
mint a malloc, egy másik csomópont, tedd
itt, és aztán, hogy egy diák itt.

1055
00:49:19,960 --> 00:49:22,120
Szóval, hogy én alapvetően van
valamiféle tömb,

1056
00:49:22,120 --> 00:49:25,590
vagy talán elegánsabb, mint mi vagyunk
kezdik látni a láncolt lista.

1057
00:49:25,590 --> 00:49:29,520
>> És így a hash tábla egy olyan szerkezet
amelyek úgy néznek ki, mint ez,

1058
00:49:29,520 --> 00:49:33,900
de ügyesen, akkor egy úgynevezett
Külön láncolás, ahol egy hash tábla

1059
00:49:33,900 --> 00:49:38,340
egészen egyszerűen egy tömb, egyenként
melynek elemei nem szám,

1060
00:49:38,340 --> 00:49:40,470
maga a láncolt lista.

1061
00:49:40,470 --> 00:49:45,080
Úgy, hogy Önnek szuper gyors hozzáférést
döntés, hogy hol hash meg értéket.

1062
00:49:45,080 --> 00:49:48,059
Hasonlóan a kártyák például
Csináltam szuper gyors döntéseket.

1063
00:49:48,059 --> 00:49:49,600
Szívek megy itt, gyémánt megy itt.

1064
00:49:49,600 --> 00:49:52,180
Ugyanez itt, egy megy itt,
D megy itt, a B megy itt.

1065
00:49:52,180 --> 00:49:55,740
Szóval szuper gyors pillantást-up, és ha
akkor megtörténhet, hogy befut egy esetben

1066
00:49:55,740 --> 00:49:59,429
ahol van ütközés, két
az emberek az azonos nevű, majd jól

1067
00:49:59,429 --> 00:50:00,970
csak elkezd őket összekapcsolni.

1068
00:50:00,970 --> 00:50:03,900
És talán nem tartjuk őket válogatni
betűrendben, talán nem.

1069
00:50:03,900 --> 00:50:05,900
De legalább most már a dinamizmus.

1070
00:50:05,900 --> 00:50:10,250
Tehát az egyik oldalon ott van szupergyors
konstans időt, és egyfajta lineáris idő

1071
00:50:10,250 --> 00:50:14,110
szó, ha ezek a láncolt listák
kezdenek egy kicsit hosszú.

1072
00:50:14,110 --> 00:50:16,880
>> Tehát ez a fajta egy buta,
geeky vicc évvel ezelőtt.

1073
00:50:16,880 --> 00:50:19,590
A CS50 hack-a-Thon,
amikor a diákok ellenőrzi,

1074
00:50:19,590 --> 00:50:22,040
Néhány TF vagy CA évente
hiszi, hogy vicces, hogy tegye fel

1075
00:50:22,040 --> 00:50:27,772
jele, mint ez, ahol csak
azt jelenti, ha a neve kezdődik egy A,

1076
00:50:27,772 --> 00:50:28,870
erre kell menni.

1077
00:50:28,870 --> 00:50:31,110
Ha a neve kezdődik
a B, menjen this-- OK,

1078
00:50:31,110 --> 00:50:33,290
ez vicces, talán később a félévben.

1079
00:50:33,290 --> 00:50:36,420
De van egy másik
módja ennek is.

1080
00:50:36,420 --> 00:50:37,410
Gyere vissza, hogy a.

1081
00:50:37,410 --> 00:50:38,600
>> Szóval van ez a szerkezet.

1082
00:50:38,600 --> 00:50:40,420
És ez az utolsó
struktúra ma,

1083
00:50:40,420 --> 00:50:42,400
amely egy úgynevezett Trie.

1084
00:50:42,400 --> 00:50:47,140
A T-R-I-E, amely valamilyen okból rövid
visszakeresés, de ezt hívják Trie.

1085
00:50:47,140 --> 00:50:51,389
Tehát egy Trie egy másik érdekes
amalgám sok ilyen ötletek.

1086
00:50:51,389 --> 00:50:52,930
Ez egy fa, amit eddig láttam.

1087
00:50:52,930 --> 00:50:54,180
Ez nem egy bináris kereső fa.

1088
00:50:54,180 --> 00:50:58,410
Ez egy fa, minden gyermekek száma,
de minden a gyerekek egy Trie

1089
00:50:58,410 --> 00:51:00,090
egy tömb.

1090
00:51:00,090 --> 00:51:04,790
Egy sor mérete, mondjuk, 26 vagy talán 27
Ha szeretnéd támogatni kötőjeles neveket

1091
00:51:04,790 --> 00:51:06,790
vagy aposztróf az emberek neveit.

1092
00:51:06,790 --> 00:51:08,280
>> És így ez egy adatstruktúra.

1093
00:51:08,280 --> 00:51:10,290
És ha megnézzük felülről
A végére, mint ha

1094
00:51:10,290 --> 00:51:13,710
Nézd meg a felső csomópont van, M, az
rámutatva, hogy a bal szélső dolog van,

1095
00:51:13,710 --> 00:51:17,665
amelyet ezután A, X, W, E, L, L. Ez
csak egy adatstruktúra, hogy önkényesen

1096
00:51:17,665 --> 00:51:19,120
a tároló emberek neveit.

1097
00:51:19,120 --> 00:51:25,720
És Maxwell tárolja csak a következő
az utat a tömb tömb tömb.

1098
00:51:25,720 --> 00:51:30,050
De mi Elképesztő egy Trie van
hogy míg a láncolt lista, és még

1099
00:51:30,050 --> 00:51:34,520
tömb, a legjobb, amit valaha kaptál van
lineáris idő vagy logaritmikus ideje keres

1100
00:51:34,520 --> 00:51:35,600
valakit.

1101
00:51:35,600 --> 00:51:40,530
Ebben adatstruktúra egy Trie, ha
én adatszerkezet egy név benne

1102
00:51:40,530 --> 00:51:43,720
és keresem Maxwell, én vagyok
fog találni elég gyorsan.

1103
00:51:43,720 --> 00:51:47,910
Én csak keresni M-A-X-W-E-L-L. Ha
ez az adat struktúra, ezzel szemben,

1104
00:51:47,910 --> 00:51:51,830
ha N egy millió, ha van egy
millió nevek ezen adatok szerkezete,

1105
00:51:51,830 --> 00:51:57,100
Maxwell még lesz
felderíthető után csak az M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
lépéseket.

1107
00:51:58,090 --> 00:52:01,276
És David-- D-A-V-I-D lépésben.

1108
00:52:01,276 --> 00:52:03,400
Más szóval, az épület
adatstruktúrát, ami

1109
00:52:03,400 --> 00:52:07,240
kapott összes ilyen tömbök, amelyek mindegyike
magukat támogatják véletlenszerű hozzáférés,

1110
00:52:07,240 --> 00:52:11,090
Kezdhetem keresi fel az emberek
nevet egy ideig, ez

1111
00:52:11,090 --> 00:52:14,340
arányos Nem száma
a dolgok az adatok szerkezete,

1112
00:52:14,340 --> 00:52:16,330
mint egy millió nevekkel.

1113
00:52:16,330 --> 00:52:20,135
Az időt vesz igénybe, hogy megtaláljam
M-A-X-W-E-L-L ezen adat struktúra

1114
00:52:20,135 --> 00:52:22,260
arányos nem a
mérete az adatok szerkezete,

1115
00:52:22,260 --> 00:52:25,930
de, hogy a hossza a név.

1116
00:52:25,930 --> 00:52:28,440
És reálisan
nevek keresünk fel

1117
00:52:28,440 --> 00:52:29,970
soha nem lesz őrült hosszú.

1118
00:52:29,970 --> 00:52:32,600
Lehet, hogy valaki egy 10 karakter
Íme, 20 karakter neve.

1119
00:52:32,600 --> 00:52:33,900
Ez természetesen véges, nem igaz?

1120
00:52:33,900 --> 00:52:37,110
Van egy ember a Földön, aki
a leghosszabb lehetséges nevet,

1121
00:52:37,110 --> 00:52:39,920
bár ez az elnevezés állandó
érték hossza, ugye?

1122
00:52:39,920 --> 00:52:41,980
Ez nem változik semmi értelme.

1123
00:52:41,980 --> 00:52:45,090
Tehát ily módon, most már
elérni egy adatstruktúra

1124
00:52:45,090 --> 00:52:47,800
hogy állandó idő look-up.

1125
00:52:47,800 --> 00:52:50,670
Ez nem fog egy több lépésből
attól függően, hogy a hossza a bemenet,

1126
00:52:50,670 --> 00:52:54,250
de nem a több név
az adatszerkezet.

1127
00:52:54,250 --> 00:52:58,700
Tehát, ha megduplázza a nevek száma
jövőre egy milliárd kétmilliárd,

1128
00:52:58,700 --> 00:53:03,720
megállapítás Maxwell fog tartani
pontosan ugyanannyi hét lépésben

1129
00:53:03,720 --> 00:53:04,650
hogy megtalálja őt.

1130
00:53:04,650 --> 00:53:08,810
És így úgy tűnik, hogy elérték
a szent grál a futási idő.

1131
00:53:08,810 --> 00:53:10,860
>> Tehát néhány gyors bejelentések.

1132
00:53:10,860 --> 00:53:11,850
Kvíz nulla jön ki.

1133
00:53:11,850 --> 00:53:14,600
Több az, hogy a pályán honlapján
Az elkövetkező pár nap.

1134
00:53:14,600 --> 00:53:17,120
A hétfői lecture-- ez egy ünnep
Itt a Harvardon hétfőn.

1135
00:53:17,120 --> 00:53:18,850
Ez nem New Haven,
így elvisszük az osztály

1136
00:53:18,850 --> 00:53:20,310
New Haven Tantermi hétfőn.

1137
00:53:20,310 --> 00:53:22,550
Minden forgatják
és élőben, mint rendesen,

1138
00:53:22,550 --> 00:53:24,900
de most véget ma
egy 30 másodperces klip

1139
00:53:24,900 --> 00:53:26,910
az úgynevezett "mély gondolatokat"
által Daven Farnham, amely

1140
00:53:26,910 --> 00:53:30,850
ihlette tavaly a szombat
Night Live "mély gondolatok"

1141
00:53:30,850 --> 00:53:35,700
Jack Handy, amely
Most már semmi értelme.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: És most, "Deep
Gondolatok "a Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tábla.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> 1. Előadó: Rendben, ennyi egyelőre.

1147
00:53:47,660 --> 00:53:48,805
Találkozunk a jövő héten.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Hogy látni működés közben.

1150
00:53:56,680 --> 00:53:58,304
Szóval vessünk egy pillantást, hogy most.

1151
00:53:58,304 --> 00:53:59,890
Tehát itt, van egy rendezetlen tömb.

1152
00:53:59,890 --> 00:54:04,860
>> Ian: Doug, akkor megy előre, és indítsa újra
ez csak egy második, kérem.

1153
00:54:04,860 --> 00:54:08,562
Rendben, kamera gördülő, így
fellépés, amikor csak akarja, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Rendben, akkor mi vagyunk
Van itt egy rendezetlen tömb.

1155
00:54:11,020 --> 00:54:13,960
És én már színes valamennyi elemét
piros, jelezve, hogy ez, sőt,

1156
00:54:13,960 --> 00:54:14,460
szétválogatás nélkül.

1157
00:54:14,460 --> 00:54:17,960
Így emlékeztetni arra, hogy az első dolog, amit
Mi vagyunk rendezni a bal fele a tömbben.

1158
00:54:17,960 --> 00:54:20,630
Aztán rendezni a jobb
a fele a tömb.

1159
00:54:20,630 --> 00:54:22,830
És ya-da, da ya-, ya-da,
mi egyesítése őket.

1160
00:54:22,830 --> 00:54:24,520
És van egy teljesen rendezett tömbben.

1161
00:54:24,520 --> 00:54:25,360
Szóval így egyesíti a fajta működik.

1162
00:54:25,360 --> 00:54:27,109
>> Ian: Hé, hé, hé,
vág, vág, vág, vág.

1163
00:54:27,109 --> 00:54:30,130
Doug, akkor nem csak ya-da, da ya-,
ya-da, végig merge sort.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: én csináltam.

1165
00:54:31,970 --> 00:54:32,832
Rendben van.

1166
00:54:32,832 --> 00:54:33,540
Mi még jól jöhet.

1167
00:54:33,540 --> 00:54:34,760
Nézzük csak tartsa gördülési.

1168
00:54:34,760 --> 00:54:35,380
Mindegy,

1169
00:54:35,380 --> 00:54:37,800
>> Ian: Meg kell magyarázni
ez jobban, mint ezt.

1170
00:54:37,800 --> 00:54:39,999
Ez egyszerűen nem elég.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, mi nem
kell, hogy menjen vissza az egyik.

1172
00:54:41,790 --> 00:54:42,350
Rendben van.

1173
00:54:42,350 --> 00:54:45,690
Mindegy, ha továbbra is a merge--
Ian, mi vagyunk a közepén forgatás.

1174
00:54:45,690 --> 00:54:46,612
>> Ian: Tudom.

1175
00:54:46,612 --> 00:54:49,320
És nem csak a ya-da, da ya-,
ya-da, az egész folyamatot.

1176
00:54:49,320 --> 00:54:52,200
Meg kell magyarázni, hogy a
két fél kap összefűzve.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: De már
elmagyarázta, hogy a két sides--

1178
00:54:53,570 --> 00:54:55,321
>> Ian: épp most látható
nekik egy merge tömb.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Ismerik a folyamatot.

1180
00:54:56,486 --> 00:54:57,172
Jól vannak.

1181
00:54:57,172 --> 00:54:58,380
Mentünk rajta tízszer.

1182
00:54:58,380 --> 00:55:00,330
>> Ian: Csak kimarad jobb rajta.

1183
00:55:00,330 --> 00:55:03,360
Megyünk vissza az egyik, akkor
nem tudsz ya-da, da ya-felette.

1184
00:55:03,360 --> 00:55:05,480
Rendben, vissza az egyik.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: mennem kell vissza
végig a csúszda?

1186
00:55:07,833 --> 00:55:08,332
Istenem.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Ez olyan, mint a hatodik alkalommal, Ian.

1189
00:55:13,004 --> 00:55:13,940
Rendben van.

1190
00:55:13,940 --> 00:55:15,200
>> Ian: Rendben.

1191
00:55:15,200 --> 00:55:16,590
Készen állsz?

1192
00:55:16,590 --> 00:55:17,400
Nagy.

1193
00:55:17,400 --> 00:55:18,950
Akció.