1
00:00:00,000 --> 00:00:00,030

2
00:00:00,030 --> 00:00:00,460
>> DAVID MALAN: Rendben.

3
00:00:00,460 --> 00:00:01,094
Visszajöttünk.

4
00:00:01,094 --> 00:00:04,260
Tehát ebben a szegmensben a programozás mi
Azt hittem, ezt egy mix a dolgokat.

5
00:00:04,260 --> 00:00:06,340
Egy, akkor egy kicsit
valami gyakorlati,

6
00:00:06,340 --> 00:00:08,690
jóllehet egy játékosabb
programozás environment--

7
00:00:08,690 --> 00:00:11,620
az egyik, hogy demonstratív
pontosan féle gondolatok

8
00:00:11,620 --> 00:00:14,220
mi már beszélünk,
de egy kicsit több hivatalosan.

9
00:00:14,220 --> 00:00:18,200
Két, nézd meg néhány
A több technikai szempontból

10
00:00:18,200 --> 00:00:21,520
hogy egy programozó valójában megoldani
problémák, mint a keresett probléma

11
00:00:21,520 --> 00:00:24,530
néztük meg előtt és
még egy alapvetően

12
00:00:24,530 --> 00:00:26,020
Érdekes probléma a válogatás.

13
00:00:26,020 --> 00:00:28,840
>> Mi csak feltételezzük a get menni
hogy ez a telefonkönyvet rendezve,

14
00:00:28,840 --> 00:00:31,980
de ez önmagában tulajdonképpen egyfajta
kemény probléma sok különböző módon

15
00:00:31,980 --> 00:00:32,479
hogy oldja meg.

16
00:00:32,479 --> 00:00:34,366
Így fogjuk használni ezeket
egy osztály a problémák

17
00:00:34,366 --> 00:00:36,740
képviselője dolgok
lehet megoldani, általában.

18
00:00:36,740 --> 00:00:38,980
És aztán majd beszélünk
mintegy néhány részlet, amit

19
00:00:38,980 --> 00:00:42,360
nevezzük adatok structures--
szakértő módon, mint láncolt listák

20
00:00:42,360 --> 00:00:46,290
és hash táblák és fák
programozó valójában

21
00:00:46,290 --> 00:00:48,890
használni, és általában használja
egy táblára festeni

22
00:00:48,890 --> 00:00:51,840
egy képet, amit ő
képzel végrehajtására

23
00:00:51,840 --> 00:00:52,980
Néhány szoftver.

24
00:00:52,980 --> 00:00:55,130
>> Tehát lássuk a gyakorlati részével.

25
00:00:55,130 --> 00:01:00,090
Tehát csak a kezét piszkos egy
környezet úgynevezett scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Ez egy olyan eszköz, amit használunk
a mi egyetemi osztályban.

27
00:01:02,636 --> 00:01:04,510
Annak ellenére, hogy úgy tervezték,
A 12 éves és akár,

28
00:01:04,510 --> 00:01:07,570
azt használjuk fel
része, hogy egy kicsit

29
00:01:07,570 --> 00:01:10,020
mivel ez egy szép, vidám
grafikus módon a tanulás

30
00:01:10,020 --> 00:01:12,160
egy kis valamit a programozás.

31
00:01:12,160 --> 00:01:17,600
Így a feje, hogy az URL, ahol
megjelenik egy oldal elég, mint ez,

32
00:01:17,600 --> 00:01:23,330
és megy előre, és kattintson
Csatlakozz Scratch a jobb felső sarokban

33
00:01:23,330 --> 00:01:28,300
és válasszon egy felhasználónevet és egy
jelszót, és végül magad

34
00:01:28,300 --> 00:01:29,970
Egy account-- scratch.mit.edu.

35
00:01:29,970 --> 00:01:32,165

36
00:01:32,165 --> 00:01:34,665
Azt hittem, használja ezt a
lehetőséget először be kell mutatnia.

37
00:01:34,665 --> 00:01:39,120
A kérdés merült fel a szünetben
mit kód néznek ki.

38
00:01:39,120 --> 00:01:41,315
És beszéltünk
A szünetben a helyzet a C,

39
00:01:41,315 --> 00:01:45,060
a particular-- különösen a
alsó szinten egy régebbi nyelven.

40
00:01:45,060 --> 00:01:47,750
És most csináltam egy gyors
Google keresés, hogy megtalálja a C kód

41
00:01:47,750 --> 00:01:51,574
A bináris keresés, az algoritmus, hogy mi
használt keresni, hogy telefonkönyvben korábban.

42
00:01:51,574 --> 00:01:54,240
Ez a különleges példa, természetesen,
nem keres egy telefonkönyvet.

43
00:01:54,240 --> 00:01:57,840
Csak keres egy csomó
számok a számítógép memóriájában.

44
00:01:57,840 --> 00:02:01,000
De ha azt szeretné, hogy csak kap egy vizuális
értelemben, hogy mi a tényleges programozás

45
00:02:01,000 --> 00:02:05,370
nyelv néz, úgy néz ki,
egy kis valamit, mint ez.

46
00:02:05,370 --> 00:02:09,759
Tehát körülbelül 20-plus,
30, vagy úgy sornyi kódot,

47
00:02:09,759 --> 00:02:12,640
de a beszélgetés
voltak, amelyek felett szünet

48
00:02:12,640 --> 00:02:16,000
volt arról, hogy ez valójában
gets átalakult nullák és egyesek

49
00:02:16,000 --> 00:02:19,200
és ha nem lehet csak visszaállítani, hogy
feldolgozására és megy nullák és egyesek

50
00:02:19,200 --> 00:02:20,210
vissza a kódot.

51
00:02:20,210 --> 00:02:22,620
>> Sajnos, a folyamat
olyan átalakító

52
00:02:22,620 --> 00:02:24,890
hogy ez sokkal könnyebb mondani, mint megtenni.

53
00:02:24,890 --> 00:02:29,400
Mentem előre, és valóban kiderült
E program bináris keresés,

54
00:02:29,400 --> 00:02:32,700
a nullák és egyesek útján
nevű program a fordító, hogy én

55
00:02:32,700 --> 00:02:34,400
történik, hogy itt jobb a Mac-emet.

56
00:02:34,400 --> 00:02:37,850
És ha megnézi a képernyőt
Itt, specifikusan

57
00:02:37,850 --> 00:02:43,520
e középső hat oszlop csak,
meglátod csak nullák.

58
00:02:43,520 --> 00:02:48,290
És ezek a nullák és egyesek, hogy
össze, hogy pontosan keresés programot.

59
00:02:48,290 --> 00:02:53,720
>> És így minden egyes darab öt bit,
Minden byte nullák és egyesek itt,

60
00:02:53,720 --> 00:02:57,310
képviselik utasítás
jellemzően belsejében egy számítógép.

61
00:02:57,310 --> 00:03:00,730
És valóban, ha már hallottam a
marketing szlogen: "Intel Inside" - azaz,

62
00:03:00,730 --> 00:03:04,610
Persze, csak azt jelenti, hogy van egy
Intel processzor, az agy a számítógép belsejében.

63
00:03:04,610 --> 00:03:08,000
És hogy ez mit jelent, hogy a CPU
hogy van egy utasításkészlet,

64
00:03:08,000 --> 00:03:08,840
hogy úgy mondjam.

65
00:03:08,840 --> 00:03:11,620
>> Minden CPU a világon, sok
azokat az Intel ezekben a napokban,

66
00:03:11,620 --> 00:03:13,690
megérti véges
utasítások száma.

67
00:03:13,690 --> 00:03:18,690
És ezeket az utasításokat olyan alacsony szinten
mivel ezt a két számot össze,

68
00:03:18,690 --> 00:03:22,560
szaporodnak a két szám együttesen
mozog ez az adat innen

69
00:03:22,560 --> 00:03:27,340
hogy itt a memóriában, csak ez az
információt itt, hogy itt a memóriában,

70
00:03:27,340 --> 00:03:32,200
és így forth-- nagyon, nagyon
alacsony szintű, szinte az elektronikus adatokat.

71
00:03:32,200 --> 00:03:34,780
De azokkal a matematikai
műveletek párosul

72
00:03:34,780 --> 00:03:37,410
azzal, amit korábban tárgyaltuk,
A adatábrázolást

73
00:03:37,410 --> 00:03:40,450
a nullák és egyesek, lehet
felépíteni mindent

74
00:03:40,450 --> 00:03:44,180
hogy a számítógép ma megtehetsz, hogy
ez szöveges, grafikus, zenés,

75
00:03:44,180 --> 00:03:45,580
vagy más módon.

76
00:03:45,580 --> 00:03:49,450
>> Tehát ez nagyon könnyen kap
elveszett a gyomok gyorsan.

77
00:03:49,450 --> 00:03:52,150
És van egy csomó
szintaktikai kihívások

78
00:03:52,150 --> 00:03:56,630
amellyel ha a legegyszerűbb,
legostobább elírás sem a program

79
00:03:56,630 --> 00:03:57,860
működni fog nélkül.

80
00:03:57,860 --> 00:04:00,366
És így ahelyett, hogy egy
nyelv, mint a C ma reggel,

81
00:04:00,366 --> 00:04:02,240
Azt gondoltam, hogy lenne
több móka, hogy ténylegesen

82
00:04:02,240 --> 00:04:04,840
valami vizuális, amelyek
míg célja a gyerekek

83
00:04:04,840 --> 00:04:08,079
valójában egy tökéletes megnyilvánulása
A tényleges programozás

84
00:04:08,079 --> 00:04:10,370
language-- történetesen
Képek használata szöveg helyett

85
00:04:10,370 --> 00:04:11,710
képviselhetik az ötleteket.

86
00:04:11,710 --> 00:04:15,470
>> Tehát ha valóban van egy
számla scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
kattintson a Create gombra
bal felső sarkában az oldalon.

88
00:04:21,070 --> 00:04:24,620
És akkor megjelenik egy olyan környezetben, mint
Az egyik én vagyok arról, hogy a képernyő

89
00:04:24,620 --> 00:04:26,310
itt.

90
00:04:26,310 --> 00:04:29,350
És mi fogjuk tölteni csak egy kicsit
kicsit az idő játszik itt.

91
00:04:29,350 --> 00:04:34,080
Lássuk, ha nem tudjuk az összes megoldani
problémák együtt a következő módon.

92
00:04:34,080 --> 00:04:39,420
>> Tehát mit fog látni ebben a
environment-- és valójában csak hagyja

93
00:04:39,420 --> 00:04:40,050
nekem szünet.

94
00:04:40,050 --> 00:04:42,680
Ha valaki nincs itt?

95
00:04:42,680 --> 00:04:45,070
Nem itt?

96
00:04:45,070 --> 00:04:45,800
RENDBEN.

97
00:04:45,800 --> 00:04:49,030
Tehát hadd rámutatni néhány
jellemzői ebben a környezetben.

98
00:04:49,030 --> 00:04:55,024
>> Így a bal felső sarokban a képernyő, akkor
Van Scratch színpadi, hogy úgy mondjam.

99
00:04:55,024 --> 00:04:57,440
Scratch nem csak a neve
E programozási nyelv;

100
00:04:57,440 --> 00:05:00,356
ez is a neve a macska, hogy
látod alapértelmezésben ott narancs.

101
00:05:00,356 --> 00:05:02,160
Ő a színpadon, így
hasonlóan leírtam

102
00:05:02,160 --> 00:05:05,770
A teknős korábban, mint amelyek a
négyszögletes fehér tábla környezetben.

103
00:05:05,770 --> 00:05:09,800
Ez a macska világa korlátozódott kizárólag
a négyszög fel tetején van.

104
00:05:09,800 --> 00:05:12,210
>> Közben, a jobb oldalon
oldali itt, ez

105
00:05:12,210 --> 00:05:15,610
Csak egy script körzetében,
üres lappal, ha úgy tetszik.

106
00:05:15,610 --> 00:05:18,590
Ez az, ahol megyünk írni
a program csak egy pillanatra.

107
00:05:18,590 --> 00:05:22,935
És az építőkockák, hogy mi kell
használja, hogy megírjam ezt a puzzle program--

108
00:05:22,935 --> 00:05:25,310
darab, ha will-- vannak
ezek itt a közepén,

109
00:05:25,310 --> 00:05:27,500
és ők kategorizált
a működése.

110
00:05:27,500 --> 00:05:31,000
Így például, én megyek előre
és igazolja, legalább egy ilyen.

111
00:05:31,000 --> 00:05:33,690
Megyek, hogy menjen előre, és kattintson
A Control kategória fel tetején.

112
00:05:33,690 --> 00:05:35,720
>> Tehát ezek a kategóriák fel tetején.

113
00:05:35,720 --> 00:05:39,410
Megyek kattintson a Vezérlőpult kategóriában.

114
00:05:39,410 --> 00:05:44,020
Inkább megyek, hogy kattintson a Programok
kategória, a legelső fel tetején.

115
00:05:44,020 --> 00:05:47,790
És ha azt szeretné, hogy kövesse végig még
ahogy ezt tesszük, akkor elég szívesen.

116
00:05:47,790 --> 00:05:52,180
Megyek kattintson és húzza át a
elsőt ", amikor a zöld zászló kattintott."

117
00:05:52,180 --> 00:05:58,410
És akkor fogok dobni csak
durván a tetején én üres pala.

118
00:05:58,410 --> 00:06:01,450
>> És mi szép a Scratch
hogy ez a puzzle-darab, amikor

119
00:06:01,450 --> 00:06:04,560
egymásba más puzzle
darab, fog tenni a szó szoros értelmében

120
00:06:04,560 --> 00:06:06,460
mik azok a puzzle darabkái mondják, hogy nem.

121
00:06:06,460 --> 00:06:09,710
Így például, Scratch jobb
most a közepén a világ.

122
00:06:09,710 --> 00:06:14,660
Megyek, hogy menjen előre, és válassza
Most, mondjuk, a Motion létesítmény,

123
00:06:14,660 --> 00:06:18,000
Ha azt szeretné, hogy ezt a
same-- Motion kategóriában.

124
00:06:18,000 --> 00:06:20,430
És most észre van egy egész
csomó puzzle darab itt

125
00:06:20,430 --> 00:06:23,370
hogy ismét a fajta amit mondanak.

126
00:06:23,370 --> 00:06:28,110
És én megyek előre, és húzza, és
dobja a lépés blokk jobbra itt.

127
00:06:28,110 --> 00:06:31,860
>> Azt tapasztaljuk, hogy amint kapsz
közel az alján a "zöld zászló

128
00:06:31,860 --> 00:06:34,580
kattintott "gombra, értesítés
hogy egy fehér vonal jelenik meg,

129
00:06:34,580 --> 00:06:36,950
mintha ez szinte
mágneses, azt akarja, hogy menjen oda.

130
00:06:36,950 --> 00:06:43,070
Csak elengedni, és ez lesz pattintsa
együtt, és a formák is illeszkedik.

131
00:06:43,070 --> 00:06:46,620
És most talán majdnem
kitalálni, hogy hol megyünk ezzel.

132
00:06:46,620 --> 00:06:51,570
>> Ha megnézi az Scratch szakaszban
ide, és nézd, hogy a tetején,

133
00:06:51,570 --> 00:06:55,142
akkor megjelenik egy vörös fény, a
stoptábla, és a zöld zászlót.

134
00:06:55,142 --> 00:06:57,100
És én megyek előre
és nézni a screen--

135
00:06:57,100 --> 00:06:58,460
csak egy pillanatra, ha lehetne.

136
00:06:58,460 --> 00:07:01,960
Megyek kattintva
zöld zászló most,

137
00:07:01,960 --> 00:07:07,850
és ment, amit úgy tűnik, hogy 10 lépés
vagy 10 pixel, 10 pontok, a képernyőn.

138
00:07:07,850 --> 00:07:13,390
>> És így nem izgalmas,
de hadd javasol

139
00:07:13,390 --> 00:07:17,440
anélkül, hogy tanítani ezt, csak
a saját saját intuition-- let

140
00:07:17,440 --> 00:07:22,560
nekem javasolni, hogy kitaláljuk, hogyan lehet
hogy Scratch séta jobbra le a színpadról.

141
00:07:22,560 --> 00:07:28,700
Van neki helyet csináljanak a jobb oldali
a képernyőn, egészen jobbra.

142
00:07:28,700 --> 00:07:32,200
Hadd adjak egy pillanatra
vagy úgy, hogy birkózni vele.

143
00:07:32,200 --> 00:07:37,681
Érdemes egy pillantást
más kategóriába tartozó blokkokat.

144
00:07:37,681 --> 00:07:38,180
Rendben.

145
00:07:38,180 --> 00:07:41,290
Tehát csak zárja, amikor már
A zöld zászló kattintott ide

146
00:07:41,290 --> 00:07:44,850
és mozgassa 10 lépés van a
egyetlen utasítás, minden alkalommal, amikor

147
00:07:44,850 --> 00:07:46,720
kattintson a zöld zászlót, mi történik?

148
00:07:46,720 --> 00:07:50,070
Nos, ez az én futó programot.

149
00:07:50,070 --> 00:07:52,450
Így tudtam ezt
talán 10-szer manuálisan,

150
00:07:52,450 --> 00:07:55,130
de ez érzi, egy kicsit
bit Hackish, hogy úgy mondjam,

151
00:07:55,130 --> 00:07:57,480
amellyel nem vagyok igazán
A probléma megoldása.

152
00:07:57,480 --> 00:08:00,530
Csak azt próbálom újra és
újra és újra és újra

153
00:08:00,530 --> 00:08:03,180
amíg azt a fajta véletlenül
elérjék az irányelv

154
00:08:03,180 --> 00:08:05,560
hogy kitűzött céljaikat korábban.

155
00:08:05,560 --> 00:08:08,200
>> De tudjuk, hogy a mi
pszeudokód korábban, hogy ott van

156
00:08:08,200 --> 00:08:11,870
ez a fogalom a programozás a hurok,
csinál valamit újra és újra.

157
00:08:11,870 --> 00:08:14,888
És így láttam, hogy egy csomó akkor
elérte, amit puzzle-darab?

158
00:08:14,888 --> 00:08:17,870

159
00:08:17,870 --> 00:08:18,730
Ismételjük, amíg.

160
00:08:18,730 --> 00:08:21,400
Így tudnánk tenni valamit
mint addig ismételjük, amíg.

161
00:08:21,400 --> 00:08:23,760
És mit ismételjük, amíg pontosan?

162
00:08:23,760 --> 00:08:27,720

163
00:08:27,720 --> 00:08:28,540
>> RENDBEN.

164
00:08:28,540 --> 00:08:31,974
És hadd menjen az egyik, hogy
kissé egyszerűbb csak egy pillanatra.

165
00:08:31,974 --> 00:08:33,140
Hadd menjek előre, és erre a célra.

166
00:08:33,140 --> 00:08:35,559
Figyeljük meg, hogy mivel lehet, hogy
felfedezett ellenőrzés alatt,

167
00:08:35,559 --> 00:08:38,409
van ez az ismétlődés blokk, amely
nem úgy néz ki, mint ez, hogy nagy.

168
00:08:38,409 --> 00:08:41,039
Ott nem sok helyet
e két sárga vonal.

169
00:08:41,039 --> 00:08:43,539
De, mint néhány lehet, hogy
észre, ha drag and drop,

170
00:08:43,539 --> 00:08:45,150
észre, hogy növekszik, hogy töltse ki a formát.

171
00:08:45,150 --> 00:08:46,274
>> És akkor is belegyömöszölni tovább.

172
00:08:46,274 --> 00:08:48,670
Akkor csak folyamatosan növekszik, ha
drag and lebeg felette.

173
00:08:48,670 --> 00:08:51,110
És nem tudom, mi
legjobb itt, úgyhogy

174
00:08:51,110 --> 00:08:54,760
Számomra legalábbis ismételjük ötször, az
Például, majd menj vissza a színpadra

175
00:08:54,760 --> 00:08:56,720
és kattintson a zöld zászlót.

176
00:08:56,720 --> 00:08:59,110
És most észre, hogy ez nem egészen ott.

177
00:08:59,110 --> 00:09:02,400
>> Most néhányan javasolják,
Victoria csak nem, ismételje meg 10-szer.

178
00:09:02,400 --> 00:09:05,140
És ez általában nem
rávenni egészen,

179
00:09:05,140 --> 00:09:10,510
de nem ott lesz erőteljesebb
mint ahogyan önkényesen kitalálni

180
00:09:10,510 --> 00:09:12,640
hány mozog, hogy?

181
00:09:12,640 --> 00:09:17,680
Mi lehet a jobb blokk
mint ismétlés 10-szer lesz?

182
00:09:17,680 --> 00:09:20,380
>> Ja, miért nem csinál valamit örökre?

183
00:09:20,380 --> 00:09:24,390
És most hadd mozog ez a puzzle-darab
benne van, hogy eltűnjön ez.

184
00:09:24,390 --> 00:09:28,300
Most észre nem számít, ha Scratch
elindul, megy a szélére.

185
00:09:28,300 --> 00:09:30,700
És szerencsére MIT,
aki Scratch, csak

186
00:09:30,700 --> 00:09:33,190
gondoskodik arról, hogy soha nem
teljesen eltűnik.

187
00:09:33,190 --> 00:09:35,360
Akkor mindig megragad a farkát.

188
00:09:35,360 --> 00:09:37,680
>> És csak ösztönösen,
akkor miért mozogni?

189
00:09:37,680 --> 00:09:38,892
Mi történik itt?

190
00:09:38,892 --> 00:09:41,440

191
00:09:41,440 --> 00:09:43,824
Úgy tűnik, hogy megállt, de
akkor, ha azt felvenni, és húzza

192
00:09:43,824 --> 00:09:45,240
ő tartja akar menni oda.

193
00:09:45,240 --> 00:09:46,123
Miert van az?

194
00:09:46,123 --> 00:09:51,610

195
00:09:51,610 --> 00:09:54,360
Valóban, a számítógép szó szerint
csinálni, amit mondani, hogy igen.

196
00:09:54,360 --> 00:09:58,380
Tehát, ha azt mondta, hogy korábban nem a
következő dolog örökre, mozgás 10 lépést,

197
00:09:58,380 --> 00:10:01,860
ez megy folyamatosan megy és megy
amíg nem nyomja meg a piros stoptábla

198
00:10:01,860 --> 00:10:04,620
és állítsa le a program teljesen.

199
00:10:04,620 --> 00:10:06,610
>> Tehát akkor is, ha nem
Ehhez hogyan tudnám

200
00:10:06,610 --> 00:10:09,510
hogy Scratch gyorsabb
az egész képernyőt?

201
00:10:09,510 --> 00:10:12,060

202
00:10:12,060 --> 00:10:13,280
További lépések, igaz?

203
00:10:13,280 --> 00:10:15,710
Tehát ahelyett, hogy 10
egy időben, miért nem

204
00:10:15,710 --> 00:10:20,100
megy előre, és változtassa meg az alábbiakra:
mit propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Tehát most megyek, hogy kattintson a zöld
zászló, sőt, megy nagyon gyorsan.

206
00:10:24,410 --> 00:10:27,180
>> És ez természetesen csak
megnyilvánulása animáció.

207
00:10:27,180 --> 00:10:28,060
Mi az animáció?

208
00:10:28,060 --> 00:10:33,090
Ez csak megmutatja a humán a
csomó állóképek tényleg,

209
00:10:33,090 --> 00:10:34,160
nagyon, nagyon gyors.

210
00:10:34,160 --> 00:10:36,500
És így, ha mi csak mondom
neki, hogy a mozgást lépéseket,

211
00:10:36,500 --> 00:10:39,750
mi csak olyan hatást kelt, hogy legyen
változás, hogy hol van a képernyőn

212
00:10:39,750 --> 00:10:42,900
annál gyorsabban egységnyi idő alatt.

213
00:10:42,900 --> 00:10:46,454
>> Most a következő kihívás, amit javasolt
az volt, hogy neki lepattan a szélét.

214
00:10:46,454 --> 00:10:49,120
És anélkül, hogy tudnánk, mi puzzle
darab exist-- mert finom

215
00:10:49,120 --> 00:10:53,030
ha nem kap a
szakaszában a challenge-- mi

216
00:10:53,030 --> 00:10:54,280
akarsz csinálni ösztönösen?

217
00:10:54,280 --> 00:10:58,030
Hogyan van vele visszapattanó és
tovább, a bal és jobb?

218
00:10:58,030 --> 00:11:02,630

219
00:11:02,630 --> 00:11:03,810
>> Igen.

220
00:11:03,810 --> 00:11:05,680
Tehát szükségünk van valamilyen
Az állapot, és mi

221
00:11:05,680 --> 00:11:09,710
úgy tűnik, hogy feltételes, így
beszélnek, az ellenőrzési kategóriában.

222
00:11:09,710 --> 00:11:14,110
Amely ezeket a blokkokat
tudjuk érdemes?

223
00:11:14,110 --> 00:11:15,200
Igen, talán "ha, akkor".

224
00:11:15,200 --> 00:11:18,780
Így észre, hogy többek között a sárga blokkok
van itt, van ez a "ha"

225
00:11:18,780 --> 00:11:23,920
vagy ez a "ha más" blokk lesz
lehetővé teszi számunkra, hogy a döntést, hogy ezt

226
00:11:23,920 --> 00:11:25,000
vagy erre.

227
00:11:25,000 --> 00:11:27,380
És akkor még fészket őket
csinálni több dolgot.

228
00:11:27,380 --> 00:11:34,910
Vagy ha már nem ment még itt,
megy előre a Érzékelési kategóriában

229
00:11:34,910 --> 00:11:39,612
és-- lássuk, ha itt van.

230
00:11:39,612 --> 00:11:43,050

231
00:11:43,050 --> 00:11:52,050
>> Tehát mi blokk hasznos lehet itt
érzékelni, hogy ő a színről?

232
00:11:52,050 --> 00:11:56,740
Igen, észre, hogy ezek közül néhány blokkok
parametrizálhatók, hogy úgy mondjam.

233
00:11:56,740 --> 00:12:00,706
Ezek a fajta egyedi, nem
ellentétben HTML tegnap attribútumokkal,

234
00:12:00,706 --> 00:12:03,330
ahol ezek az attribútumok fajta
testre a viselkedése egy címke.

235
00:12:03,330 --> 00:12:08,880
Hasonlóképpen itt is megragadom a megható
blokk és a változás, és feltenni a kérdést,

236
00:12:08,880 --> 00:12:11,500
Ön megérintette az egér
pointert a kurzor

237
00:12:11,500 --> 00:12:13,250
vagy ha megérinti a szélén?

238
00:12:13,250 --> 00:12:15,210
>> Tehát hadd menjen be, és erre a célra.

239
00:12:15,210 --> 00:12:18,130
Megyek kicsinyíteni egy pillanatra.

240
00:12:18,130 --> 00:12:21,320
Hadd fogd ezt a puzzle darab
Itt, ebben a puzzle-darab ez,

241
00:12:21,320 --> 00:12:24,570
és megyek összekever
őket egy pillanatra.

242
00:12:24,570 --> 00:12:27,620
Megyek mozgatni ezt,
megváltoztatni ezt a megható él,

243
00:12:27,620 --> 00:12:38,590
és fogok mozgás erre.

244
00:12:38,590 --> 00:12:40,490
Tehát itt van néhány összetevőjére.

245
00:12:40,490 --> 00:12:42,570
Azt hiszem, minden megvan, amit akarok.

246
00:12:42,570 --> 00:12:47,710
>> Szeretné valaki szeretné javasolni, hogyan
csatlakoztathatja ezeket talán fentről lefelé

247
00:12:47,710 --> 00:12:52,020
annak érdekében, hogy megoldják a problémát,
Scratch mozog jobbra-balra és jobbra,

248
00:12:52,020 --> 00:12:57,020
balról jobbra balra, minden
időben csak pattogó le a falat?

249
00:12:57,020 --> 00:12:58,050
Mit szeretne tenni?

250
00:12:58,050 --> 00:13:01,097
Melyik blokk kéne csatlakozni a
"Amikor a zöld zászló elsőként kattintó"?

251
00:13:01,097 --> 00:13:04,060

252
00:13:04,060 --> 00:13:06,200
>> OK, így kezdjük a "örökké".

253
00:13:06,200 --> 00:13:07,170
Mi megy belül a következő lépés?

254
00:13:07,170 --> 00:13:10,290
Valaki más.

255
00:13:10,290 --> 00:13:11,850
OK, mozgás lépéseket.

256
00:13:11,850 --> 00:13:12,350
Rendben.

257
00:13:12,350 --> 00:13:14,470
Akkor mi?

258
00:13:14,470 --> 00:13:15,120
Így aztán az, ha.

259
00:13:15,120 --> 00:13:17,720
És észre, bár úgy néz ki
szendvics össze szorosan,

260
00:13:17,720 --> 00:13:19,500
akkor csak nőnek, hogy töltse ki.

261
00:13:19,500 --> 00:13:21,500
Ez csak ugorj, ahol akarom.

262
00:13:21,500 --> 00:13:25,920
>> És mit tettem között
a ha és az akkor?

263
00:13:25,920 --> 00:13:27,180
Valószínűleg ", ha megérinti él."

264
00:13:27,180 --> 00:13:31,800
És vegyük észre, megint, ez túl nagy
érte, de nőni fog kitölteni.

265
00:13:31,800 --> 00:13:35,002
Majd kapcsolja 15 fokkal?

266
00:13:35,002 --> 00:13:35,710
Hány fok?

267
00:13:35,710 --> 00:13:38,800

268
00:13:38,800 --> 00:13:41,196
Igen, így 180 forognak
nekem egészen körül.

269
00:13:41,196 --> 00:13:42,570
Tehát lássuk, ha kaptam ezt a jogot.

270
00:13:42,570 --> 00:13:43,930
Hadd kicsinyítés.

271
00:13:43,930 --> 00:13:45,130
>> Hadd húzza Scratch fel.

272
00:13:45,130 --> 00:13:50,030
Tehát ő egy kicsit torz
most, de ez rendben van.

273
00:13:50,030 --> 00:13:52,231
Hogyan állítható vissza őt könnyen?

274
00:13:52,231 --> 00:13:59,879

275
00:13:59,879 --> 00:14:01,045
Megyek csalni egy kicsit.

276
00:14:01,045 --> 00:14:04,074

277
00:14:04,074 --> 00:14:05,990
Úgyhogy még egy
blokk, csak hogy egyértelmű legyen.

278
00:14:05,990 --> 00:14:08,424
Azt akarom, hogy pont 90 fok
jobbra alapértelmezés szerint

279
00:14:08,424 --> 00:14:10,840
így én csak elmondom neki
erre programozott.

280
00:14:10,840 --> 00:14:11,632
És kész is van.

281
00:14:11,632 --> 00:14:14,740

282
00:14:14,740 --> 00:14:15,740
Úgy tűnik, hogy megtettem.

283
00:14:15,740 --> 00:14:19,980
Ez egy kicsit fura, mert
ő sétál fejjel lefelé.

284
00:14:19,980 --> 00:14:21,250
Nevezzük, hogy a hiba.

285
00:14:21,250 --> 00:14:22,120
Ez nagy hiba.

286
00:14:22,120 --> 00:14:27,320
Egy bogár egy hiba a programban, a
logikai hiba, hogy én, az emberi készült.

287
00:14:27,320 --> 00:14:28,985
Miért megy fejjel lefelé?

288
00:14:28,985 --> 00:14:33,560

289
00:14:33,560 --> 00:14:35,250
Esetleg MIT csavart ki vagy ugye?

290
00:14:35,250 --> 00:14:38,840

291
00:14:38,840 --> 00:14:42,550
>> Igen, úgy értem, hogy nem a MIT
hiba. Adtak egy puzzle-darab

292
00:14:42,550 --> 00:14:44,970
hogy azt mondja, viszont néhány fokban.

293
00:14:44,970 --> 00:14:47,672
És Victoria javaslatára
Én fordult 180 fokot,

294
00:14:47,672 --> 00:14:48,880
ami a helyes intuíció.

295
00:14:48,880 --> 00:14:53,700
De fordult 180 fokot szó
azt jelenti, fordult 180 fokot,

296
00:14:53,700 --> 00:14:55,860
és ez nem igazán
amit akarok, úgy tűnik.

297
00:14:55,860 --> 00:14:58,026
Mert legalább ő a
A kétdimenziós világban,

298
00:14:58,026 --> 00:15:00,740
így esztergálás folyik valójában
flip fejjel lefelé.

299
00:15:00,740 --> 00:15:04,030
>> Azt érdemes használni, mi blokk
ehelyett az alapján, amit itt látsz?

300
00:15:04,030 --> 00:15:11,890

301
00:15:11,890 --> 00:15:14,790
Hogyan tudnánk ezt orvosolni?

302
00:15:14,790 --> 00:15:18,380
Igen, így tudtuk mutatni
az ellenkező irányba.

303
00:15:18,380 --> 00:15:22,300
És tulajdonképpen még ez
nem lesz elég,

304
00:15:22,300 --> 00:15:26,410
mert csak akkor tudjuk kódba
a mutató jobbra vagy balra.

305
00:15:26,410 --> 00:15:27,920
>> Tudod, mit tehetnék?

306
00:15:27,920 --> 00:15:30,160
Úgy néz ki, hogy van egy
kényelem blokk van.

307
00:15:30,160 --> 00:15:32,987
Ha nagyítás, lásd
valami, mint itt?

308
00:15:32,987 --> 00:15:36,120

309
00:15:36,120 --> 00:15:40,020
Tehát úgy néz ki, mint a MIT területén
absztrakció épült itt.

310
00:15:40,020 --> 00:15:45,440
Ez a blokk úgy tűnik, hogy ezzel egyenértékű
amelyhez más blokkok, többes?

311
00:15:45,440 --> 00:15:49,510
>> Ez egyben úgy tűnik, hogy ezzel egyenértékű
hogy ez az egész hármas blokk

312
00:15:49,510 --> 00:15:50,880
hogy itt van.

313
00:15:50,880 --> 00:15:54,670
Így kiderül, tudok egyszerűsíteni én
programot, hogy megszabaduljon az összes, hogy

314
00:15:54,670 --> 00:15:58,270
és csak hogy ezt itt.

315
00:15:58,270 --> 00:16:01,620
És most még egy kicsit
hibás, és ez rendben van most.

316
00:16:01,620 --> 00:16:03,370
Majd hagyjuk, hogy legyen.

317
00:16:03,370 --> 00:16:06,000
De a program még
egyszerűbb, és ez is

318
00:16:06,000 --> 00:16:09,060
reprezentatív lenne
A cél programming--

319
00:16:09,060 --> 00:16:13,430
hogy ideális esetben a kódot
egyszerű, minél kisebb,

320
00:16:13,430 --> 00:16:15,650
míg továbbra is a
olvasható, mint lehetséges.

321
00:16:15,650 --> 00:16:20,310
Nem akarjuk, hogy ez annyira tömör,
hogy nehéz megérteni.

322
00:16:20,310 --> 00:16:22,826
>> De észre azt váltottuk
három blokk egy,

323
00:16:22,826 --> 00:16:24,200
és ez vitathatatlanul jó dolog.

324
00:16:24,200 --> 00:16:27,280
Már absztrahált el a fogalom
ellenőrzése, hogy te

325
00:16:27,280 --> 00:16:29,120
szélén csak egy blokk.

326
00:16:29,120 --> 00:16:31,520
Most lehet szórakozni ezzel, sőt.

327
00:16:31,520 --> 00:16:35,790
Ez nem tesz hozzá annyi
szellemi érték, hanem játékos értékét.

328
00:16:35,790 --> 00:16:39,730
Megyek, hogy menjen előre
és megragad ez a hang itt.

329
00:16:39,730 --> 00:16:42,900

330
00:16:42,900 --> 00:16:46,420
Tehát hadd menjen előre, és hadd
állítsa le a program egy pillanatra.

331
00:16:46,420 --> 00:16:52,070
Megyek rögzíteni a következőket,
hogy betekintést enged a mikrofon.

332
00:16:52,070 --> 00:16:53,181
>> Essünk neki.

333
00:16:53,181 --> 00:16:53,680
Jaj.

334
00:16:53,680 --> 00:16:58,710

335
00:16:58,710 --> 00:17:01,140
Próbáljuk meg újra.

336
00:17:01,140 --> 00:17:02,279
Essünk neki.

337
00:17:02,279 --> 00:17:03,570
OK, felvettem a rossz dolog.

338
00:17:03,570 --> 00:17:04,580
Essünk neki.

339
00:17:04,580 --> 00:17:05,080
Jaj.

340
00:17:05,080 --> 00:17:07,910

341
00:17:07,910 --> 00:17:08,800
Jaj.

342
00:17:08,800 --> 00:17:09,300
Rendben.

343
00:17:09,300 --> 00:17:10,791
Most kell megszabadulni, hogy.

344
00:17:10,791 --> 00:17:11,290
Rendben.

345
00:17:11,290 --> 00:17:13,950
>> Tehát most van egy
rögzítése csak "jaj".

346
00:17:13,950 --> 00:17:18,040
Úgyhogy most megyek
előre, és ezt "jaj".

347
00:17:18,040 --> 00:17:20,270
Megyek, hogy menjen vissza
az én szkriptek, és most

348
00:17:20,270 --> 00:17:25,460
értesítés van ebben a mondatban, hogy hívják
hangot lejátszani "miau" vagy hangot lejátszani "jaj".

349
00:17:25,460 --> 00:17:28,920
Megyek húzza ezt, és ahol
rakjam ezt a komikus hatás?

350
00:17:28,920 --> 00:17:31,740

351
00:17:31,740 --> 00:17:37,860
Igen, így most ez a fajta
buggy, mert most ez block--

352
00:17:37,860 --> 00:17:42,050
észre, hogy ez a "ha az élére,
ugrál "a fajta önálló.

353
00:17:42,050 --> 00:17:43,704
Szóval kell helyrehozni.

354
00:17:43,704 --> 00:17:44,870
Hadd menjek előre, és erre a célra.

355
00:17:44,870 --> 00:17:48,630
Hadd megszabadulni ez, és menj vissza
az eredeti, több szándékos

356
00:17:48,630 --> 00:17:49,870
funkcionalitás.

357
00:17:49,870 --> 00:18:01,080
Tehát "ha megérinti él, akkor" Azt akarom,
fordulni, mint Victoria javasolt,

358
00:18:01,080 --> 00:18:02,480
180 fok.

359
00:18:02,480 --> 00:18:05,497
És akarok játszani
A hang "jaj" van?

360
00:18:05,497 --> 00:18:11,800

361
00:18:11,800 --> 00:18:15,580
>> Igen, észre, hogy ez kívül
hogy a sárga blokk.

362
00:18:15,580 --> 00:18:17,680
Tehát ez is lenne egy
bug, de azt vettem észre azt.

363
00:18:17,680 --> 00:18:21,290
Így fogok húzza fel itt,
és értesítés most már belül a "ha".

364
00:18:21,290 --> 00:18:24,250
Tehát a "ha" ez a fajta
hasonló kar-szerű folt

365
00:18:24,250 --> 00:18:26,260
ami csak akkor fog
tenni, ami a belsejébe.

366
00:18:26,260 --> 00:18:30,216
Tehát ha most kicsinyíteni a
a kockázatot a annoying--

367
00:18:30,216 --> 00:18:32,860

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Jaj, jaj, jaj.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: És
csak megy a végtelenségig.

370
00:18:39,910 --> 00:18:44,160
Most csak, hogy gyorsítsa fel a dolgokat
itt, hadd menjen előre, és nyissa fel,

371
00:18:44,160 --> 00:18:50,460
nézzük say-- hadd menjen néhány
A saját dolgaim osztályban.

372
00:18:50,460 --> 00:18:53,000

373
00:18:53,000 --> 00:19:00,220
És hadd nyissa fel, mondjuk, ez
Egy által az egyik tanítási társaik

374
00:19:00,220 --> 00:19:01,500
néhány évvel ezelőtt.

375
00:19:01,500 --> 00:19:04,732
Így néhányan talán felidézni
ezt a játékot ízlését,

376
00:19:04,732 --> 00:19:05,940
és ez valóban figyelemre méltó.

377
00:19:05,940 --> 00:19:08,190
Annak ellenére, hogy tettünk a
legegyszerűbb program most,

378
00:19:08,190 --> 00:19:09,980
nézzük meg, hogy ez mit
valóban úgy néz ki, mint.

379
00:19:09,980 --> 00:19:10,650
Hadd hit játszani.

380
00:19:10,650 --> 00:19:14,210

381
00:19:14,210 --> 00:19:18,980
>> Tehát ebben a játékban, van egy
béka, és a nyíl keys--

382
00:19:18,980 --> 00:19:23,340
elveszi nagyobb lépésből áll, mint én remember--
Van felett ez béka.

383
00:19:23,340 --> 00:19:29,630
És a cél az, hogy az egész elfoglalt
út nélkül fut be az autókat.

384
00:19:29,630 --> 00:19:34,735
És nézzük see-- ha felmegyek itt,
meg kell várni a napló gördülni.

385
00:19:34,735 --> 00:19:38,130

386
00:19:38,130 --> 00:19:39,274
Ez olyan, mint egy bogár.

387
00:19:39,274 --> 00:19:42,240

388
00:19:42,240 --> 00:19:43,495
Ez a fajta egy bogár.

389
00:19:43,495 --> 00:19:45,980

390
00:19:45,980 --> 00:19:46,480
Rendben.

391
00:19:46,480 --> 00:19:51,550
Vagyok itt ezt,
ott, és akkor tartsa

392
00:19:51,550 --> 00:19:54,100
megy, amíg nem kap minden
a békák, a liliom párna.

393
00:19:54,100 --> 00:19:55,920
Most ez lehet keresni
valamennyi a bonyolultabb,

394
00:19:55,920 --> 00:19:57,840
de próbáljuk megtörni
ez mentálisan

395
00:19:57,840 --> 00:20:00,040
és szóban bele összetevő blokkolja.

396
00:20:00,040 --> 00:20:03,910
Tehát valószínűleg egy puzzle
darab, amely nem láttuk még

397
00:20:03,910 --> 00:20:07,440
de ez reagál a billentyűk,
a dolog, amit megüt a billentyűzeten.

398
00:20:07,440 --> 00:20:11,660
>> Tehát ott valószínűleg valamiféle
blokk, amely azt mondja, ha a fő értéke fel,

399
00:20:11,660 --> 00:20:15,965
akkor valamit csinálni Scratch--
talán mozgatni 10 lépésben ezen a módon.

400
00:20:15,965 --> 00:20:20,240
Ha le gombot megnyomja, mozogni 10 lépés
Ily módon, vagy balra gombot, mozogni 10 lépés

401
00:20:20,240 --> 00:20:21,710
Ily módon 10 lépésre, hogy.

402
00:20:21,710 --> 00:20:23,644
Már világosan kiderült a macska egy béka.

403
00:20:23,644 --> 00:20:26,060
Tehát ez csak, ahol a
jelmez, mint Scratch hívások it-- mi

404
00:20:26,060 --> 00:20:28,440
csak az importált képet a béka.

405
00:20:28,440 --> 00:20:29,570
>> De mi más történik?

406
00:20:29,570 --> 00:20:32,794
Milyen más sornyi kódot,
milyen más puzzle-darabokat

407
00:20:32,794 --> 00:20:35,460
tette Blake, a tanítás ember,
használni ezt a programot, úgy tűnik?

408
00:20:35,460 --> 00:20:38,320

409
00:20:38,320 --> 00:20:42,730
Mi így minden move--
milyen programozási konstrukció?

410
00:20:42,730 --> 00:20:44,950
>> Motion, biztos magában, így a
mozogni blokkot, az biztos.

411
00:20:44,950 --> 00:20:49,330
És mi ez a lépés blokk
belsejében, a legvalószínűbb?

412
00:20:49,330 --> 00:20:52,850
Igen, valamilyen hurok, talán egy
örökre blokk, talán egy ismétlés block--

413
00:20:52,850 --> 00:20:54,070
ismételjük, amíg blokk.

414
00:20:54,070 --> 00:20:57,330
És ez az, ami így a naplók és
a liliom párna, és minden mást mozog

415
00:20:57,330 --> 00:20:57,990
előre-hátra.

416
00:20:57,990 --> 00:21:00,270
Ez csak történik a végtelenségig.

417
00:21:00,270 --> 00:21:03,180
>> Miért van néhány az autók
gyorsabban mozog, mint a többiek?

418
00:21:03,180 --> 00:21:06,607
Mi a különbség a ezeket a programokat?

419
00:21:06,607 --> 00:21:09,690
Igen, valószínűleg egy részük szed
több lépést egyszerre, és néhány közülük

420
00:21:09,690 --> 00:21:10,690
kevesebb lépésben egyszerre.

421
00:21:10,690 --> 00:21:14,670
És a vizuális hatás
gyors versus lassú.

422
00:21:14,670 --> 00:21:16,030
>> Mit gondol, mi történt?

423
00:21:16,030 --> 00:21:19,700
Amikor megkaptam a béka egészen
az utca túloldalán, és a folyó

424
00:21:19,700 --> 00:21:23,560
ra a lily pad, valami
Figyelemre méltó történt.

425
00:21:23,560 --> 00:21:26,540
Mi történt, amint tette ezt?

426
00:21:26,540 --> 00:21:27,210
Megállt.

427
00:21:27,210 --> 00:21:29,680
Ez a béka megállt, és
Van egy másik béka.

428
00:21:29,680 --> 00:21:33,155
Tehát mi konstrukciót kell
ott használt, mi jellemző?

429
00:21:33,155 --> 00:21:36,020

430
00:21:36,020 --> 00:21:38,660
>> Igen, így van valamilyen
"Ha" feltétel akár ott is.

431
00:21:38,660 --> 00:21:41,909
És kiderül out-- nem láttunk this--
de van más blokkok vannak, hogy

432
00:21:41,909 --> 00:21:45,300
lehet mondani, ha megható
Egy másik dolog a képernyőn,

433
00:21:45,300 --> 00:21:47,720
ha megérinti a lily pad ", majd".

434
00:21:47,720 --> 00:21:50,810
És akkor ez mikor
hogy a második béka jelenik meg.

435
00:21:50,810 --> 00:21:54,969
Tehát annak ellenére, hogy ez a játék minden bizonnyal
nagyon kelt, bár első pillantásra

436
00:21:54,969 --> 00:21:58,010
van annyira megy on-- és Blake
nem ostor ezt fel két perc alatt,

437
00:21:58,010 --> 00:22:00,390
valószínűleg elvitte több
óra, hogy létrehozza ezt a játékot

438
00:22:00,390 --> 00:22:03,850
alapján a memóriája vagy videó
a múlt változata is.

439
00:22:03,850 --> 00:22:07,940
De mindezen kis dolgok
folyik a képernyőn elszigetelten

440
00:22:07,940 --> 00:22:11,550
szűkülnek le ezeket a nagyon egyszerű
constructs-- mozgások vagy nyilatkozatok

441
00:22:11,550 --> 00:22:15,519
mint már említettük, a hurkok és
feltételeket, és ennyi.

442
00:22:15,519 --> 00:22:17,060
Van néhány más szakértő jellemzői.

443
00:22:17,060 --> 00:22:19,130
Néhány ezek közül a tisztán
esztétikai vagy akusztikus,

444
00:22:19,130 --> 00:22:20,964
mint a hangok csak játszottam.

445
00:22:20,964 --> 00:22:23,380
De a legtöbb esetben, akkor
Van ezen a nyelven, Scratch,

446
00:22:23,380 --> 00:22:25,350
az összes alapvető
építőelemeket, hogy

447
00:22:25,350 --> 00:22:29,280
Van C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
és számos más nyelven.

449
00:22:32,960 --> 00:22:36,720
Bármilyen kérdése van Scratch?

450
00:22:36,720 --> 00:22:37,220
Rendben.

451
00:22:37,220 --> 00:22:40,303
Így nem fogunk merülni a mélyebb semmiből,
bár szívesen ezen a hétvégén,

452
00:22:40,303 --> 00:22:42,860
különösen, ha gyerekek vagy
unokahúga és unokaöccse, és az ilyen,

453
00:22:42,860 --> 00:22:44,220
bevezetni őket a semmiből.

454
00:22:44,220 --> 00:22:47,960
Ez valójában egy csodálatosan játékos
környezetben, mint a szerzők szerint,

455
00:22:47,960 --> 00:22:49,120
Nagyon magas mennyezettel.

456
00:22:49,120 --> 00:22:51,670
Annak ellenére, hogy kezdődött
nagyon alacsony szintű részleteket

457
00:22:51,670 --> 00:22:54,890
akkor tényleg egy kicsit
vele, és ez talán

458
00:22:54,890 --> 00:22:57,360
bemutatót, hogy pontosan.

459
00:22:57,360 --> 00:23:02,920
>> De nézzük most átmenet néhány
kifinomult problémák, ha úgy tetszik,

460
00:23:02,920 --> 00:23:05,870
ismert, mint "keresés" és a
"Válogatás", általában.

461
00:23:05,870 --> 00:23:09,500
Mi volt ez a telefon könyvet earlier-- itt
egy másikat csak discussion--

462
00:23:09,500 --> 00:23:13,460
hogy képesek voltunk keresni
hatékonyabban, mert

463
00:23:13,460 --> 00:23:15,270
jelentős feltételezés.

464
00:23:15,270 --> 00:23:17,655
És csak hogy tisztázzuk, milyen
feltételezés azt, hogy

465
00:23:17,655 --> 00:23:19,280
ha keres ezen keresztül telefonkönyv?

466
00:23:19,280 --> 00:23:23,342

467
00:23:23,342 --> 00:23:25,300
Hogy Mike Smith volt
A telefonkönyv, bár

468
00:23:25,300 --> 00:23:27,410
lenne képes kezelni
A forgatókönyv nélküle

469
00:23:27,410 --> 00:23:30,720
ott, ha csak megállt idő előtt.

470
00:23:30,720 --> 00:23:31,806
A könyv ábécé.

471
00:23:31,806 --> 00:23:33,930
És ez egy nagyon nagylelkű
feltételezés, mert

472
00:23:33,930 --> 00:23:36,580
jelenti someone-- Olyan vagyok
A vágás egy sarokba,

473
00:23:36,580 --> 00:23:40,580
mint én vagyok a gyorsabb, mert valaki
más tette a sok kemény munka számomra.

474
00:23:40,580 --> 00:23:43,120
>> De mi van, ha a telefon
könyvben szétválogatott?

475
00:23:43,120 --> 00:23:47,050
Talán Verizon kapott lusta, csak dobott
mindenki nevek és a számok ott

476
00:23:47,050 --> 00:23:50,120
talán abban a sorrendben, amelyben
feliratkozott telefon szolgáltatás.

477
00:23:50,120 --> 00:23:54,570
És mennyi idő telik nekem
találni valakit, mint Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1000 oldal telefon book-- hány
oldalak nem azt kell nézni rajta?

479
00:23:58,160 --> 00:23:58,905
>> Mindegyikük.

480
00:23:58,905 --> 00:24:00,030
Maga a fajta jártál.

481
00:24:00,030 --> 00:24:03,420
Ha szó szerint meg kell nézni minden
oldalon, ha a telefonkönyvben csak

482
00:24:03,420 --> 00:24:04,450
véletlenszerűen rendezve.

483
00:24:04,450 --> 00:24:06,910
Lehet, hogy szerencsés és megtalálja Mike
a legelső oldalon, mert

484
00:24:06,910 --> 00:24:08,826
volt az első vevő
rendelni telefon szolgáltatás.

485
00:24:08,826 --> 00:24:10,760
De lehetett volna az utolsó is.

486
00:24:10,760 --> 00:24:12,500
>> Tehát véletlen sorrendben nem jó.

487
00:24:12,500 --> 00:24:16,750
Tegyük fel, hogy van, hogy rendezze a
telefonkönyv, illetve általában a fajta adat

488
00:24:16,750 --> 00:24:18,520
hogy már kapott.

489
00:24:18,520 --> 00:24:19,440
Hogyan tudjuk ezt?

490
00:24:19,440 --> 00:24:21,360
>> Nos, hadd próbálja
Egy egyszerű példa erre.

491
00:24:21,360 --> 00:24:24,290
Hadd menjek előre, és dobálják
néhány számot a táblára.

492
00:24:24,290 --> 00:24:35,480
Tegyük fel, hogy a számok már vannak,
mondjuk, négy, kettő, egy, és három.

493
00:24:35,480 --> 00:24:38,390
És Ben, rendezni ezeket a számokat a számunkra.

494
00:24:38,390 --> 00:24:39,017
>> Ok, rendben.

495
00:24:39,017 --> 00:24:39,850
Hogyan csináltad, hogy?

496
00:24:39,850 --> 00:24:42,731

497
00:24:42,731 --> 00:24:43,230
Rendben.

498
00:24:43,230 --> 00:24:44,710
Így kezdődik a legkisebb
érték és a legmagasabb,

499
00:24:44,710 --> 00:24:46,084
és ez igazán jó intuíció.

500
00:24:46,084 --> 00:24:48,080
És észre, hogy mi
emberek valójában nagyon

501
00:24:48,080 --> 00:24:49,913
jó problémák megoldására
mint ez, legalábbis

502
00:24:49,913 --> 00:24:51,810
amikor az adatok viszonylag kicsi.

503
00:24:51,810 --> 00:24:54,860
Amint elkezdi, hogy több száz
A számok, több ezer szám,

504
00:24:54,860 --> 00:24:58,440
Több millió szám, Ben valószínűleg
nem tudta megtenni, hogy elég gyors,

505
00:24:58,440 --> 00:25:00,620
feltételezve, hogy voltak
hiányosságok a számokat.

506
00:25:00,620 --> 00:25:03,450
Elég könnyen számolni egymillió
egyébként, csak időigényes.

507
00:25:03,450 --> 00:25:07,150
>> Tehát az algoritmus úgy hangzik,
mint Ben használt most

508
00:25:07,150 --> 00:25:08,930
volt keresést a legkisebb számot.

509
00:25:08,930 --> 00:25:12,900
Így, bár mi, emberek is igénybe vehet
egy csomó információt vizuálisan,

510
00:25:12,900 --> 00:25:14,830
a számítógép valójában
egy kicsit korlátozott.

511
00:25:14,830 --> 00:25:17,560
A számítógép csak
nézd meg egy byte egy időben

512
00:25:17,560 --> 00:25:20,770
vagy talán négy byte-os time--
Manapság talán 8 byte-os time--

513
00:25:20,770 --> 00:25:24,450
de egy nagyon kis számú
bájtok egy adott időben.

514
00:25:24,450 --> 00:25:28,480
>> Tehát, mivel már tényleg
Négy különböző értékeket here--

515
00:25:28,480 --> 00:25:32,440
és akkor úgy gondolja, Ben, mint amelyek
szemellenzőt mintha egy számítógép, mint

516
00:25:32,440 --> 00:25:36,450
hogy nem lát mást,
mint egy szám egy time--

517
00:25:36,450 --> 00:25:39,720
tehát általában feltételezzük, mint
Angol, akkor jobbról balra.

518
00:25:39,720 --> 00:25:42,870
Tehát az első számú Ben valószínűleg nézett
A négy éves volt, és aztán nagyon gyorsan

519
00:25:42,870 --> 00:25:44,770
rájött, hogy ez egy elég nagy
number-- hadd keresd.

520
00:25:44,770 --> 00:25:45,357
>> Van kettő.

521
00:25:45,357 --> 00:25:45,940
Várj egy percet.

522
00:25:45,940 --> 00:25:47,070
Két kisebb, mint négy.

523
00:25:47,070 --> 00:25:47,986
Megyek, hogy emlékezzen.

524
00:25:47,986 --> 00:25:49,070
Két most a legkisebb.

525
00:25:49,070 --> 00:25:50,417
Most one-- ez még jobb.

526
00:25:50,417 --> 00:25:51,250
Ez még kisebb.

527
00:25:51,250 --> 00:25:54,000
Megyek elfelejteni két
és csak emlékezni egyet.

528
00:25:54,000 --> 00:25:56,550
>> És tudta megállítani keres?

529
00:25:56,550 --> 00:25:58,360
Nos, nem tudott alapján
ezt az információt,

530
00:25:58,360 --> 00:26:00,477
de jobb lenne, ha a keresés
a többi a lista.

531
00:26:00,477 --> 00:26:02,060
Mert mi van, ha nulla volt a listán?

532
00:26:02,060 --> 00:26:03,643
Mi van, ha negatív volt a listán?

533
00:26:03,643 --> 00:26:07,720
Ő csak azt tudja, hogy a válasz
akkor helyes, ha ő kimerítően

534
00:26:07,720 --> 00:26:08,729
ellenőrizni a teljes lista.

535
00:26:08,729 --> 00:26:10,020
Tehát nézzük a többi ezt.

536
00:26:10,020 --> 00:26:11,394
Hár volt időpocsékolás.

537
00:26:11,394 --> 00:26:13,540
Megvan szerencsétlen, de én
még helyes megtenni.

538
00:26:13,540 --> 00:26:17,857
És így most feltehetően
választotta ki a legkisebb számot

539
00:26:17,857 --> 00:26:20,440
és csak tedd az elején
A lista, mint én itt.

540
00:26:20,440 --> 00:26:23,480
Most mit csinálni, még akkor is
Ön nem gondolt, hogy majdnem

541
00:26:23,480 --> 00:26:25,962
ilyen mértékben?

542
00:26:25,962 --> 00:26:27,670
Ismételjük meg az eljárást,
így valamiféle hurok.

543
00:26:27,670 --> 00:26:28,920
Van egy ismerős ötlet.

544
00:26:28,920 --> 00:26:30,860
Tehát itt van négy.

545
00:26:30,860 --> 00:26:32,110
Ez jelenleg a legkisebb.

546
00:26:32,110 --> 00:26:33,220
Ez egy jelöltet.

547
00:26:33,220 --> 00:26:33,900
Többé nem.

548
00:26:33,900 --> 00:26:34,770
Most láttam kettőt.

549
00:26:34,770 --> 00:26:36,630
Ez a következő legkisebb eleme.

550
00:26:36,630 --> 00:26:40,800
Hár ez nem kisebb, így
most Ben tudja tépni ki a kettő.

551
00:26:40,800 --> 00:26:44,510
>> És most ismételje meg a folyamatot, és
Természetesen a három nő húzta ki legközelebb.

552
00:26:44,510 --> 00:26:45,420
Ismételje meg a folyamatot.

553
00:26:45,420 --> 00:26:46,990
Négy nő húzta ki.

554
00:26:46,990 --> 00:26:50,140
És most éppen ki a számokat,
így a lista kell válogatni.

555
00:26:50,140 --> 00:26:51,960
>> És valóban, ez egy formális algoritmus.

556
00:26:51,960 --> 00:26:56,610
A számítógép-tudós lenne
ezt "kiválasztás sort,"

557
00:26:56,610 --> 00:27:00,880
Az ötlet az volt, egyfajta a
list iteratively-- újra

558
00:27:00,880 --> 00:27:03,807
és újra és újra kiválasztja
a legkisebb szám.

559
00:27:03,807 --> 00:27:06,140
És mi szép, hogy az,
ez csak olyan rohadt intuitív.

560
00:27:06,140 --> 00:27:07,470
Ez ilyen egyszerű.

561
00:27:07,470 --> 00:27:11,100
És akkor ismételje meg ugyanezt a
műveletet újra és újra.

562
00:27:11,100 --> 00:27:12,150
Ez egyszerű.

563
00:27:12,150 --> 00:27:17,170
>> Ebben az esetben az volt, gyors, de
meddig történik mindez?

564
00:27:17,170 --> 00:27:19,880
Nézzük, hogy úgy tűnik, és
egy kicsit több unalmas.

565
00:27:19,880 --> 00:27:24,150
Tehát egy, kettő, három, négy, öt hat,
hét, nyolc, kilenc, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15. 16-- tetszőleges számú.

567
00:27:26,160 --> 00:27:28,780
Csak azt akartam többet ezt
idő, mint a négy.

568
00:27:28,780 --> 00:27:30,780
Tehát ha van egy egész
csomó számot now-- azt

569
00:27:30,780 --> 00:27:32,420
nem is számít
amit are-- nézzük

570
00:27:32,420 --> 00:27:34,380
úgy gondolja, hogy ez mit
algoritmus nagyon tetszik.

571
00:27:34,380 --> 00:27:35,857
>> Tegyük fel, hogy a számok vannak.

572
00:27:35,857 --> 00:27:38,190
Ismét nem számít, hogy mit
vannak, de ők véletlen.

573
00:27:38,190 --> 00:27:39,679
Én alkalmazásával Ben algoritmus.

574
00:27:39,679 --> 00:27:41,220
Azt kell, hogy válassza ki a legkisebb számot.

575
00:27:41,220 --> 00:27:41,761
Mit tegyek?

576
00:27:41,761 --> 00:27:44,240
És megyek, hogy fizikailag
csináld ezt az ideje cselekedni ki.

577
00:27:44,240 --> 00:27:46,099
Keresi, keresi,
látszó, néz, néz.

578
00:27:46,099 --> 00:27:48,140
Csak mire eljut
a végén a lista

579
00:27:48,140 --> 00:27:51,230
Rájöttem a legkisebb
szám volt két ebben az időben.

580
00:27:51,230 --> 00:27:52,720
Egy nem szerepel a listában.

581
00:27:52,720 --> 00:27:54,400
Így tettem le két.

582
00:27:54,400 --> 00:27:55,590
>> Mi a teendőm?

583
00:27:55,590 --> 00:27:58,600
Látszó, látszó, néz, néz.

584
00:27:58,600 --> 00:28:02,250
Most találtam a hetes szám, mert
ott hiányos ezen numbers--

585
00:28:02,250 --> 00:28:03,300
de csak önkényes.

586
00:28:03,300 --> 00:28:03,800
Rendben.

587
00:28:03,800 --> 00:28:06,030
Így most már tudom letenni hét.

588
00:28:06,030 --> 00:28:08,860
Looking, néz.

589
00:28:08,860 --> 00:28:11,030
>> Most feltételezve, a
Persze, hogy Ben nem

590
00:28:11,030 --> 00:28:14,780
extra RAM, extra
memória, mert, természetesen,

591
00:28:14,780 --> 00:28:16,080
Nézem ugyanazt a számot.

592
00:28:16,080 --> 00:28:18,246
Bizonyára én is emlékeznék
Mindezen számok,

593
00:28:18,246 --> 00:28:19,930
és ez teljesen igaz.

594
00:28:19,930 --> 00:28:22,610
De ha Ben emlékszik minden
A számok azt látta,

595
00:28:22,610 --> 00:28:24,430
még nem igazán készült
alapvető előrelépés

596
00:28:24,430 --> 00:28:26,170
mert már van
képes keresni

597
00:28:26,170 --> 00:28:27,540
a számok a táblán.

598
00:28:27,540 --> 00:28:29,373
Emlékezés az összes
számok nem segít,

599
00:28:29,373 --> 00:28:32,490
mert még mindig, mint egy számítógépes
Csak nézd meg, mi mondtuk, egy szám

600
00:28:32,490 --> 00:28:33,080
egy időben.

601
00:28:33,080 --> 00:28:35,760
Tehát nincs valami cheat
nézve, hogy képes kihasználni.

602
00:28:35,760 --> 00:28:39,170
>> Így a valóságban, mint én
tovább keresni a listában,

603
00:28:39,170 --> 00:28:44,200
A szó szoros értelmében, hogy csak folyamatosan megy
oda-vissza rajta, kopasztás ki

604
00:28:44,200 --> 00:28:45,710
A következő legkisebb számot.

605
00:28:45,710 --> 00:28:48,810
És akkor milyen következtetni
én buta mozgások,

606
00:28:48,810 --> 00:28:50,860
ez egyre csak nagyon
unalmas nagyon gyorsan,

607
00:28:50,860 --> 00:28:54,850
és úgy tűnik, hogy megy vissza, és
oda, oda-vissza egy kicsit.

608
00:28:54,850 --> 00:29:03,220
Most, hogy tisztességes, nem kell menni
annyira, nos, see-- hogy tisztességes,

609
00:29:03,220 --> 00:29:06,310
Nem kell járni elég
annyi lépést minden egyes alkalommal.

610
00:29:06,310 --> 00:29:09,200
Mert, persze, ahogy
válasszon a listából a számok,

611
00:29:09,200 --> 00:29:11,860
A fennmaradó lista egyre rövidebb.

612
00:29:11,860 --> 00:29:14,240
>> És így gondoljuk végig,
hány lépést én valójában

613
00:29:14,240 --> 00:29:16,010
traipsing keresztül minden egyes alkalommal.

614
00:29:16,010 --> 00:29:18,950
Az első helyzet
mi volt 16 szám,

615
00:29:18,950 --> 00:29:22,210
és így maximally-- nézzük csak
Ehhez egy discussion--

616
00:29:22,210 --> 00:29:25,640
Volt, hogy nézze át 16
számokat, hogy megtalálják a legkisebb.

617
00:29:25,640 --> 00:29:28,420
De ha már váj ki
a legkisebb szám, hogyan

618
00:29:28,420 --> 00:29:30,590
Hosszú volt a maradék listát, természetesen?

619
00:29:30,590 --> 00:29:31,420
Csak 15.

620
00:29:31,420 --> 00:29:34,670
Tehát, hogy hány szám volt Ben, vagy én
átnézni a második alkalommal?

621
00:29:34,670 --> 00:29:36,832
15, csak hogy menjen, és megtalálja a legkisebb.

622
00:29:36,832 --> 00:29:39,540
De most, persze, a lista,
is, kisebb, mint korábban volt.

623
00:29:39,540 --> 00:29:42,540
Tehát hány lépést tettem
van, hogy a következő alkalommal?

624
00:29:42,540 --> 00:29:49,970
14, majd 13, majd 12, plusz pont,
dot, dot, amíg én maradt csak egy.

625
00:29:49,970 --> 00:29:53,146
Tehát most egy számítógép tudós lenne
kérni, illetve, hogy mit csinál, hogy minden egyenlő?

626
00:29:53,146 --> 00:29:55,770
Ez tulajdonképpen megegyezik néhány konkrét
szám, amit minden bizonnyal

627
00:29:55,770 --> 00:30:00,490
do számtanilag, de szeretnénk beszélni
hatékonyságáról algoritmusok

628
00:30:00,490 --> 00:30:04,940
egy kicsit formulaically,
független, milyen hosszú a lista.

629
00:30:04,940 --> 00:30:06,240
>> És tudod mit?

630
00:30:06,240 --> 00:30:09,860
Ez 16, de mint már mondtam,
hívjuk csak a méret a probléma

631
00:30:09,860 --> 00:30:10,970
n, ahol n jelentése egyes számot.

632
00:30:10,970 --> 00:30:13,220
Lehet, hogy 16, talán
három, talán egy millió.

633
00:30:13,220 --> 00:30:13,761
Nem tudom.

634
00:30:13,761 --> 00:30:14,390
Nem érdekel.

635
00:30:14,390 --> 00:30:16,520
Amit igazán szeretnék,
a képlet, hogy én is

636
00:30:16,520 --> 00:30:19,420
használja összehasonlítani ezt az algoritmust
szemben más algoritmusok

637
00:30:19,420 --> 00:30:22,350
hogy valaki igényt
jobb, vagy rosszabb.

638
00:30:22,350 --> 00:30:25,430
>> Így kiderül, és csak
tudjuk ezt a általános iskolában

639
00:30:25,430 --> 00:30:34,790
hogy ez tényleg működik ki az ugyanazon
dolog, mint n keresztül n, plusz egy több mint kettő.

640
00:30:34,790 --> 00:30:40,020
És ez történik, hogy egyenlő, a
Természetesen n négyzetes plusz n két.

641
00:30:40,020 --> 00:30:43,250
Tehát, ha akartam formula
hány lépést

642
00:30:43,250 --> 00:30:46,330
vettek részt néztem az összes
ezeket a számokat, újra és újra

643
00:30:46,330 --> 00:30:52,681
és újra és újra, azt mondanám,
ez n négyzetes plusz n két.

644
00:30:52,681 --> 00:30:53,430
De tudod mit?

645
00:30:53,430 --> 00:30:54,500
Ez csak úgy néz ki rendetlen.

646
00:30:54,500 --> 00:30:56,470
Csak nagyon szeretnék egy
Általános értelemben a dolgok.

647
00:30:56,470 --> 00:30:58,810
És lehet előhívni
középiskolában, hogy

648
00:30:58,810 --> 00:31:00,660
ez a fogalom legmagasabb rendű távon.

649
00:31:00,660 --> 00:31:05,300
Amely ezeket a feltételeket, a n
négyzete, a N vagy a felét,

650
00:31:05,300 --> 00:31:07,550
van a legnagyobb hatása az idő múlásával?

651
00:31:07,550 --> 00:31:11,920
Minél nagyobb n kap, amely
Ezen ügyek leginkább?

652
00:31:11,920 --> 00:31:15,560
>> Más szavakkal, ha azt dugja
egy millió, n négyzetes

653
00:31:15,560 --> 00:31:17,900
lesz a legvalószínűbb
az uralkodó tényező,

654
00:31:17,900 --> 00:31:21,670
mert milliószor
maga egy sokkal nagyobb

655
00:31:21,670 --> 00:31:23,682
mint eggyel több millió.

656
00:31:23,682 --> 00:31:24,390
Szóval tudod mit?

657
00:31:24,390 --> 00:31:27,305
Ez egy ilyen rohadt nagy
számot, ha tér egy számot.

658
00:31:27,305 --> 00:31:28,430
Ez nem igazán számít.

659
00:31:28,430 --> 00:31:30,596
Mi csak a határokat átlépő, hogy
ki, és felejtsd el.

660
00:31:30,596 --> 00:31:34,250
És így egy számítógép tudós azt mondaná
hogy a hatékonyságot ezen algoritmus

661
00:31:34,250 --> 00:31:37,850
van a sorrendben a N squared--
Úgy értem igazán közelítés.

662
00:31:37,850 --> 00:31:40,810
Ez a fajta durván n négyzeten.

663
00:31:40,810 --> 00:31:44,130
Idővel, a nagyobb
és nagyobb n lesz, ezt

664
00:31:44,130 --> 00:31:47,610
egy jó becslés, amit a
hatékonyságát, illetve a hatékonyság hiánya

665
00:31:47,610 --> 00:31:49,400
az algoritmus valójában.

666
00:31:49,400 --> 00:31:52,040
És azt levezetni, hogy persze,
re valójában csinál a matek.

667
00:31:52,040 --> 00:31:54,040
De most csak integetett
kezem, mert én csak

668
00:31:54,040 --> 00:31:55,790
szeretnék egy általános értelemben az algoritmus.

669
00:31:55,790 --> 00:31:58,850
>> Tehát ugyanazt a logikát, eközben
nézzük meg egy másik algoritmust

670
00:31:58,850 --> 00:32:01,162
már látszott figyeléssel lineáris keresés.

671
00:32:01,162 --> 00:32:02,870
Amikor kerestem
A telefon book--

672
00:32:02,870 --> 00:32:05,980
nem válogatás, keres
telefonon keresztül book--

673
00:32:05,980 --> 00:32:09,197
azt hajtogatta, hogy ez
1000 lépéseket, vagy 500 lépésre.

674
00:32:09,197 --> 00:32:10,280
De nézzük, hogy általánosítani.

675
00:32:10,280 --> 00:32:12,860
Ha van n oldalak
A telefonkönyv, mi

676
00:32:12,860 --> 00:32:17,250
A futási idő vagy a
hatékonyságát lineáris keresés?

677
00:32:17,250 --> 00:32:19,750
Ez a sorrend
hány lépés, hogy megtalálják

678
00:32:19,750 --> 00:32:24,210
Mike Smith lineáris keresés, a
első algoritmus, vagy akár a második?

679
00:32:24,210 --> 00:32:27,240

680
00:32:27,240 --> 00:32:31,710
>> A legrosszabb esetben, Mike
a végén a könyv.

681
00:32:31,710 --> 00:32:35,590
Tehát, ha a telefon könyv 1000 oldal,
mondtuk legutóbb, a legrosszabb esetben,

682
00:32:35,590 --> 00:32:38,380
ez eltarthat körülbelül mennyi
sok oldalt találni Mike?

683
00:32:38,380 --> 00:32:38,990
Mint 1000.

684
00:32:38,990 --> 00:32:39,830
Ez egy felső korlátot.

685
00:32:39,830 --> 00:32:41,790
Ez egy lehető legrosszabb helyzetben.

686
00:32:41,790 --> 00:32:44,410
De ismétlem, mi távolodik
számokról, mint 1000 most.

687
00:32:44,410 --> 00:32:45,730
Ez csak n.

688
00:32:45,730 --> 00:32:47,470
>> Tehát mi a logikus következtetést?

689
00:32:47,470 --> 00:32:50,210
Megtalálása Mike egy telefon
könyv, amely n oldalak

690
00:32:50,210 --> 00:32:55,280
eltarthat, a legrosszabb esetben,
hány lépés a sorrendben n?

691
00:32:55,280 --> 00:32:58,110
És valóban egy számítógépes
tudós azt mondaná

692
00:32:58,110 --> 00:33:02,340
hogy a futási idő vagy a
teljesítmény, illetve a hatékonyság

693
00:33:02,340 --> 00:33:07,470
vagy eredménytelensége, az algoritmus, mint a
lineáris keresés a sorrendben N.

694
00:33:07,470 --> 00:33:10,010
És mi is ugyanezt a
logikája átkelés valamit

695
00:33:10,010 --> 00:33:13,170
ahogy én csináltam, hogy a második
algoritmus volt a telefonkönyvben,

696
00:33:13,170 --> 00:33:16,040
ahol mentünk két oldalt egy időben.

697
00:33:16,040 --> 00:33:20,120
>> Tehát 1000 oldal telefonkönyv talán
minket 500 lapozás, plusz egy

698
00:33:20,120 --> 00:33:21,910
megduplázásuk vissza egy kicsit.

699
00:33:21,910 --> 00:33:26,590
Tehát ha egy telefonkönyv n oldalt, de
csinálunk két oldalt egy időben,

700
00:33:26,590 --> 00:33:28,900
Ez nagyjából mi?

701
00:33:28,900 --> 00:33:33,190
N két, úgy, hogy olyan, mint n két.

702
00:33:33,190 --> 00:33:38,490
De tettem a követelés a
perce, hogy n keresztül two--

703
00:33:38,490 --> 00:33:41,060
ez a fajta ugyanaz, mint csak n.

704
00:33:41,060 --> 00:33:44,050
Ez csak egy állandó tényezőt,
számítógépes szakemberek azt mondják.

705
00:33:44,050 --> 00:33:45,970
Nézzük csak összpontosítani
változók, really--

706
00:33:45,970 --> 00:33:47,780
a legnagyobb változó az egyenletben.

707
00:33:47,780 --> 00:33:52,530
>> Tehát a lineáris keresés, legyen az egy
oldal egy időben, vagy két oldalt egy időben,

708
00:33:52,530 --> 00:33:54,810
egyfajta alapvetően ugyanaz.

709
00:33:54,810 --> 00:33:56,880
Még mindig a sorrendben n.

710
00:33:56,880 --> 00:34:01,930
De én azt állította képem korábbi
hogy a harmadik algoritmus nem volt

711
00:34:01,930 --> 00:34:02,480
lineáris.

712
00:34:02,480 --> 00:34:03,605
Nem volt egy egyenes vonal.

713
00:34:03,605 --> 00:34:08,659
Úgy volt, hogy görbe vonal, és a
algebrai képlet volt, mi?

714
00:34:08,659 --> 00:34:11,812
Belépés a n-- így alapú logaritmus két n.

715
00:34:11,812 --> 00:34:14,520
És nem kell bemenni túl
sokkal részletesebben a logaritmus ma,

716
00:34:14,520 --> 00:34:17,394
de a legtöbb számítógépes szakemberek nem
még mondani, mi a bázis.

717
00:34:17,394 --> 00:34:20,639
Mert ez az egész csak
állandó tényező, hogy úgy mondjam,

718
00:34:20,639 --> 00:34:22,659
Csak enyhe numerikus különbségeket.

719
00:34:22,659 --> 00:34:31,179
És így ez egy nagyon gyakori
módja különösen hivatalos számítógépes

720
00:34:31,179 --> 00:34:33,949
tudósok egy tábla vagy
programozók egy fehér tábla

721
00:34:33,949 --> 00:34:36,889
valójában arra hivatkozva, amely
algoritmus fogják használni

722
00:34:36,889 --> 00:34:39,500
vagy mi a hatékonyság
az algoritmus.

723
00:34:39,500 --> 00:34:42,960
>> És ez nem feltétlenül valami
megbeszélitek, hogy bármilyen nagy részletességgel,

724
00:34:42,960 --> 00:34:47,889
de egy jó programozó valaki
akinek van egy szilárd, hivatalos háttérrel.

725
00:34:47,889 --> 00:34:50,120
Ő képes beszélni
Önnek ez a módja

726
00:34:50,120 --> 00:34:53,350
és valóban
kvalitatív érveket

727
00:34:53,350 --> 00:34:56,870
hogy miért egy algoritmust vagy
Egy szoftver

728
00:34:56,870 --> 00:35:00,165
kiváló valamilyen módon a másikba.

729
00:35:00,165 --> 00:35:02,540
Mert akkor minden bizonnyal
csak futni egy ember programja

730
00:35:02,540 --> 00:35:04,980
és számolja a másodpercek száma
kell ahhoz, hogy rendezni néhány számot,

731
00:35:04,980 --> 00:35:06,710
és lehet futtatni néhány
más személy programja

732
00:35:06,710 --> 00:35:08,418
és számolja
másodpercek tart.

733
00:35:08,418 --> 00:35:12,840
De ez egy általánosabb módon, hogy
akkor elemezni algoritmusok

734
00:35:12,840 --> 00:35:15,520
ha úgy tetszik, csak
papír vagy csak szóban.

735
00:35:15,520 --> 00:35:18,430
Anélkül, hogy fut, anélkül, hogy
is próbál mintát bemenet,

736
00:35:18,430 --> 00:35:20,180
ha csak érvelni rajta.

737
00:35:20,180 --> 00:35:24,670
És így a bérleti fejlesztő vagy ha
amelynek neki valami azt állítják, hogy Ön

738
00:35:24,670 --> 00:35:28,460
Ezért azok algoritmus, a titkos
szósz keres milliárdokat

739
00:35:28,460 --> 00:35:30,580
A weboldalakat
cég jobb, ezek

740
00:35:30,580 --> 00:35:33,302
azok a fajta érveiket
ideális esetben képes.

741
00:35:33,302 --> 00:35:35,010
Vagy legalábbis ezek
a dolgokat

742
00:35:35,010 --> 00:35:40,211
hogy jön fel a vitát, a
Legalább egy nagyon formális vitát.

743
00:35:40,211 --> 00:35:40,710
Rendben.

744
00:35:40,710 --> 00:35:44,400
Tehát Ben javasolt valamit
nevezett kiválasztás sort.

745
00:35:44,400 --> 00:35:48,200
De fogom javasolni, hogy ott van
Más módon teheti ezt is.

746
00:35:48,200 --> 00:35:50,400
Amit nem igazán tetszik
körülbelül Ben algoritmus

747
00:35:50,400 --> 00:35:54,400
hogy ő csak ment tovább, vagy
Miután nekem járni, oda-vissza

748
00:35:54,400 --> 00:35:56,930
és oda-vissza, és oda-vissza.

749
00:35:56,930 --> 00:36:04,130
Mi lenne, ha inkább én is csinálni
olyasmi, mint ezek a számok itt

750
00:36:04,130 --> 00:36:08,200
és én csak kezelni az egyes
száma viszont ahogy én adtam azt?

751
00:36:08,200 --> 00:36:10,780
>> Más szavakkal, itt
én számok listája.

752
00:36:10,780 --> 00:36:12,944
Négy, egy, három, kettő.

753
00:36:12,944 --> 00:36:14,360
És fogok csinálni a következő.

754
00:36:14,360 --> 00:36:17,230
Megyek illessze be a számokat
ahová tartoznak, hanem

755
00:36:17,230 --> 00:36:18,980
mint kiválasztja azokat egyesével.

756
00:36:18,980 --> 00:36:20,820
Más szavakkal, itt a négyes szám.

757
00:36:20,820 --> 00:36:22,430
>> Itt az eredeti listán.

758
00:36:22,430 --> 00:36:25,290
És én fogom fenntartani
lényegében egy új lista itt.

759
00:36:25,290 --> 00:36:26,710
Tehát ez a régi lista.

760
00:36:26,710 --> 00:36:28,560
Ez az új listát.

761
00:36:28,560 --> 00:36:30,220
Látom a négyes első.

762
00:36:30,220 --> 00:36:34,500
Az új lista kezdetben üres,
így triviális esetében

763
00:36:34,500 --> 00:36:36,410
hogy négy most válogatott lista.

764
00:36:36,410 --> 00:36:39,560
Én csak figyelembe a számot én adott,
és én üzembe azt az új lista.

765
00:36:39,560 --> 00:36:41,460
>> Ez az új lista sorrendje?

766
00:36:41,460 --> 00:36:41,990
Igen.

767
00:36:41,990 --> 00:36:45,090
Ez hülye, mert csak egy van
elem, de ez teljesen rendezve.

768
00:36:45,090 --> 00:36:46,390
Nincs semmi a helyén.

769
00:36:46,390 --> 00:36:49,290
Ez érdekes, ez az algoritmus,
mikor léphet a következő lépésre.

770
00:36:49,290 --> 00:36:50,550
>> Most van egy.

771
00:36:50,550 --> 00:36:55,430
Tehát az egyik természetesen tartozik a
elejére vagy végére ennek az új lista?

772
00:36:55,430 --> 00:36:56,360
A kezdet.

773
00:36:56,360 --> 00:36:58,530
Szóval van, hogy némi munkát most.

774
00:36:58,530 --> 00:37:01,410
Már vesz néhány
szabadságjogok én marker

775
00:37:01,410 --> 00:37:03,120
mindössze rajz dolgokat
ahol akarom őket,

776
00:37:03,120 --> 00:37:05,320
de ez nem igazán
pontos a számítógépen.

777
00:37:05,320 --> 00:37:08,530
Egy számítógép, mint tudjuk, van
RAM, vagy a Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
és ez az egyik bájt
byte másik byte.

779
00:37:12,411 --> 00:37:14,910
És ha van egy gigabájt
RAM, van egy milliárd bájt,

780
00:37:14,910 --> 00:37:16,680
de ők fizikailag egy helyen.

781
00:37:16,680 --> 00:37:19,540
Nem lehet csak mozgatni dolog körül
támaszkodva a táblára

782
00:37:19,540 --> 00:37:20,750
ahova akarod.

783
00:37:20,750 --> 00:37:24,090
Tehát, ha az új listának
négy helyszínen a memóriában,

784
00:37:24,090 --> 00:37:27,480
sajnos a négyes
Már a rossz helyen.

785
00:37:27,480 --> 00:37:30,410
>> Tehát, hogy helyezze az első számú
Nem tudom csak felhívni itt.

786
00:37:30,410 --> 00:37:31,901
Ez a memória hely nem létezik.

787
00:37:31,901 --> 00:37:35,150
Ez lenne csalás, és én már
csaló képileg néhány percig

788
00:37:35,150 --> 00:37:35,800
itt.

789
00:37:35,800 --> 00:37:40,950
Tehát valóban, ha azt szeretnénk, hogy egy van,
Meg kell ideiglenesen másolja a négy

790
00:37:40,950 --> 00:37:43,030
majd tegye az ott.

791
00:37:43,030 --> 00:37:45,500
>> Ez rendben van, így van,
ez technikailag lehetséges,

792
00:37:45,500 --> 00:37:48,410
de észre, hogy ez plusz munkát.

793
00:37:48,410 --> 00:37:50,460
Nem csak fel a számot a helyére.

794
00:37:50,460 --> 00:37:53,026
Először meg kellett mozgatni
számot, majd tegye a helyére,

795
00:37:53,026 --> 00:37:54,650
úgyhogy egyfajta megduplázta mennyiségű munkát.

796
00:37:54,650 --> 00:37:55,660
Így tartsa szem előtt.

797
00:37:55,660 --> 00:37:57,120
>> De én most történik ez az elem.

798
00:37:57,120 --> 00:37:59,056
Most azt akarom, hogy megragad a hármas szám.

799
00:37:59,056 --> 00:38:00,430
Ahol természetesen nem is tartozik?

800
00:38:00,430 --> 00:38:01,480
Közte.

801
00:38:01,480 --> 00:38:03,650
Nem tudok csalni többé
és csak tedd oda,

802
00:38:03,650 --> 00:38:06,770
mert megint ez a memória
a fizikai helyszíneken.

803
00:38:06,770 --> 00:38:10,900
Tehát azt kell másolni a négy
és tegye a három ide.

804
00:38:10,900 --> 00:38:11,550
Nem nagy ügy.

805
00:38:11,550 --> 00:38:14,610
Ez csak egy plusz lépést
again-- úgy érzi, nagyon olcsó.

806
00:38:14,610 --> 00:38:16,445
>> De most már lépni a kettő.

807
00:38:16,445 --> 00:38:17,820
A két, természetesen, ide tartozik.

808
00:38:17,820 --> 00:38:20,990
Most kezd látni, hogyan
a munka felhalmozódik.

809
00:38:20,990 --> 00:38:23,520
Most mi kell még tenni?

810
00:38:23,520 --> 00:38:28,570
Ja, azt meg kell mozgatni a négy,
Aztán kell másolni a három,

811
00:38:28,570 --> 00:38:31,200
és most helyezze be a kettő.

812
00:38:31,200 --> 00:38:34,460
És a fogás ezzel
algoritmus, érdekes módon,

813
00:38:34,460 --> 00:38:41,050
az, hogy tegyük fel, hogy van egy szélsőségesebb
Amennyiben ez mondjuk nyolc, hét,

814
00:38:41,050 --> 00:38:45,150
hat, öt, négy, három, kettő, egy.

815
00:38:45,150 --> 00:38:49,450
Ez, számos helyzetben,
A legrosszabb forgatókönyv esetén,

816
00:38:49,450 --> 00:38:51,570
mert a rohadt dolog
szó visszafelé.

817
00:38:51,570 --> 00:38:53,670
>> Nem igazán
hatással Ben-algoritmust,

818
00:38:53,670 --> 00:38:55,940
mert Ben kiválasztási
rendezés ő fog tartani

819
00:38:55,940 --> 00:38:58,359
oda-vissza végig a listát.

820
00:38:58,359 --> 00:39:01,150
És mert mindig keresi
az egész fennmaradó lista,

821
00:39:01,150 --> 00:39:02,858
nem számít
ahol az elemek.

822
00:39:02,858 --> 00:39:05,630
De ebben az esetben az én behelyezése
approach-- próbáljuk meg.

823
00:39:05,630 --> 00:39:08,616
>> Tehát egy, kettő, három, négy,
öt, hat, hét, nyolc.

824
00:39:08,616 --> 00:39:11,630
Egy kettő három négy,
öt, hat, hét, nyolc.

825
00:39:11,630 --> 00:39:14,320
Megyek, hogy a nyolc,
és hová tegyem meg?

826
00:39:14,320 --> 00:39:17,260
Nos, az elején listámon,
mert ez az új lista.

827
00:39:17,260 --> 00:39:18,760
És én áthúzáshoz.

828
00:39:18,760 --> 00:39:20,551
>> Hova tegyem a hét?

829
00:39:20,551 --> 00:39:21,050
A fene egye meg.

830
00:39:21,050 --> 00:39:23,174
El kell menni oda, így
Van némi másolás.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
És most a hét megy itt.

833
00:39:28,480 --> 00:39:29,860
Most lépni a hat.

834
00:39:29,860 --> 00:39:30,980
Most még több munka.

835
00:39:30,980 --> 00:39:32,570
>> Nyolc olyan, hogy megy itt.

836
00:39:32,570 --> 00:39:33,920
Hét van, hogy megy itt.

837
00:39:33,920 --> 00:39:35,450
Most a hat mehet itt.

838
00:39:35,450 --> 00:39:37,950
Most fogd az öt.

839
00:39:37,950 --> 00:39:40,560
Most nyolc van, hogy menjen
Itt hét van, hogy megy itt,

840
00:39:40,560 --> 00:39:43,650
Hat van, hogy megy itt, és
most öt és ismételje meg.

841
00:39:43,650 --> 00:39:46,610
És én elég sokat
mozgatja folyamatosan.

842
00:39:46,610 --> 00:39:52,950
>> Így a végén, ez algorithm-- fogunk
hívják behelyezés sort-- ténylegesen

843
00:39:52,950 --> 00:39:55,020
van egy csomó munka is.

844
00:39:55,020 --> 00:39:56,970
Ez csak a különböző
a fajta munka, mint Ben.

845
00:39:56,970 --> 00:40:00,090
Ben munkája volt nekem megy
oda-vissza minden alkalommal,

846
00:40:00,090 --> 00:40:03,510
kiválasztja a következő legkisebb
elem újra és újra.

847
00:40:03,510 --> 00:40:06,660
Így volt ez a nagyon vizuális fajta munka.

848
00:40:06,660 --> 00:40:10,600
>> Ez a másik algoritmus, amely még mindig
correct-- ez lesz a feladat done--

849
00:40:10,600 --> 00:40:12,800
csak megváltoztatja a munka mennyiségét.

850
00:40:12,800 --> 00:40:15,420
Úgy néz ki, kezdetben maga
mentés, mert te csak

851
00:40:15,420 --> 00:40:19,190
foglalkozik az egyes elemek
elöl nélkül séta az

852
00:40:19,190 --> 00:40:20,930
az utat a listán, mint Ben.

853
00:40:20,930 --> 00:40:25,300
De a probléma, különösen ezekben
őrült az esetben, ha ez az egész visszafelé,

854
00:40:25,300 --> 00:40:27,830
te csak egyfajta
elhalasztása a kemény munka

855
00:40:27,830 --> 00:40:30,360
amíg van kijavítani a hibákat.

856
00:40:30,360 --> 00:40:33,919
>> És így ha lehet ezt elképzelni
Nyolc hét, illetve hat és öt

857
00:40:33,919 --> 00:40:36,710
majd négy és három és két
mozgó útjukat végig a listán,

858
00:40:36,710 --> 00:40:39,060
éppen most változott a
típusú munkát csinálunk.

859
00:40:39,060 --> 00:40:42,340
Ahelyett, hogy azt a
kezdve az én iteráció

860
00:40:42,340 --> 00:40:45,250
Én csak csinálom a
végén minden iteráció.

861
00:40:45,250 --> 00:40:50,550
Így kiderül, hogy ez az algoritmus,
is, általában az úgynevezett beillesztés sort,

862
00:40:50,550 --> 00:40:52,190
is a sorrendben n négyzeten.

863
00:40:52,190 --> 00:40:56,480
Ez valójában nem jobb,
nem jobb egyáltalán.

864
00:40:56,480 --> 00:41:00,810
>> Azonban van egy harmadik megközelítés
Azt javasoljuk, hogy megvizsgáljuk,

865
00:41:00,810 --> 00:41:02,970
ami ezt.

866
00:41:02,970 --> 00:41:07,850
Tegyük fel, hogy a listát, az egyszerűség kedvéért
ismét, négy, egy, három,

867
00:41:07,850 --> 00:41:11,080
two-- csak négy számot.

868
00:41:11,080 --> 00:41:13,300
Ben már jó intuíció,
jó emberi intuíció

869
00:41:13,300 --> 00:41:16,340
előtt, ami által rögzített teljes
list eventually-- beillesztés sort.

870
00:41:16,340 --> 00:41:18,020
Azt coaxed minket.

871
00:41:18,020 --> 00:41:22,530
De nézzük meg a
legegyszerűbb módja annak, hogy erősít ez a lista.

872
00:41:22,530 --> 00:41:24,110
>> Ez a lista nincs rendezve.

873
00:41:24,110 --> 00:41:26,130
Miért?

874
00:41:26,130 --> 00:41:31,920
Az angol, miért
ez valójában nem rendezve.

875
00:41:31,920 --> 00:41:33,400
Mit jelent, hogy nem lehet válogatni?

876
00:41:33,400 --> 00:41:34,220
>> DIÁK: Ez nem szekvenciálisan.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: Nem szekvenciálisan.

878
00:41:34,990 --> 00:41:35,822
Mondj egy példát.

879
00:41:35,822 --> 00:41:37,180
>> DIÁK: Tedd őket sorrendben.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Adj egy konkrét példa.

882
00:41:38,790 --> 00:41:39,832
>> DIÁK: Növekvő sorrendben.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Nem növekvő sorrendben.

884
00:41:41,206 --> 00:41:42,100
Pontosabban.

885
00:41:42,100 --> 00:41:45,190
Nem tudom, mit jelent a növekvő.

886
00:41:45,190 --> 00:41:47,150
Mi a baj?

887
00:41:47,150 --> 00:41:49,930
>> DIÁK: A legkisebb a
számok nem az első helyet.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: legkisebb számot a
Nem az első helyet.

889
00:41:51,140 --> 00:41:52,120
Konkrétabb.

890
00:41:52,120 --> 00:41:55,000
Kezdek fogás.

891
00:41:55,000 --> 00:41:59,470
Számítunk, de
mi elromlott itt?

892
00:41:59,470 --> 00:42:00,707
>> DIÁK: Numerikus sorrendben.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: Numerikus sorrendben.

894
00:42:02,040 --> 00:42:04,248
Mindenki egyfajta vezetése
ez here-- nagyon magas szinten.

895
00:42:04,248 --> 00:42:07,450
Csak szó mondja meg, mi van
rossz, mint egy öt éves erejét.

896
00:42:07,450 --> 00:42:08,310
>> DIÁK: plusz egy.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Mi ez?

898
00:42:08,750 --> 00:42:09,610
>> DIÁK: plusz egy.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Mit jelent plusz egy?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Adj egy másik öt éves.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Mi a baj, anya?

904
00:42:18,330 --> 00:42:19,940
Mi a baj, apa?

905
00:42:19,940 --> 00:42:22,808
Mit jelent ez nincs rendezve?

906
00:42:22,808 --> 00:42:24,370
>> DIÁK: Ez nem a megfelelő hely.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Mi
nem a megfelelő helyen?

908
00:42:25,580 --> 00:42:26,174
>> DIÁK: Négy.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, jó.

910
00:42:27,090 --> 00:42:29,110
Tehát négy nem, ahol lennie kellene.

911
00:42:29,110 --> 00:42:30,590
Különösen ez igaz?

912
00:42:30,590 --> 00:42:33,000
Négy és egy, az első
Két szám látok.

913
00:42:33,000 --> 00:42:34,930
Ez igaz?

914
00:42:34,930 --> 00:42:36,427
Nem, ők elromlott, nem igaz?

915
00:42:36,427 --> 00:42:38,135
Sőt, úgy gondolja most
körülbelül egy számítógép is.

916
00:42:38,135 --> 00:42:40,824
Ez csak akkor nézd meg, talán egy,
talán két dolgot once--

917
00:42:40,824 --> 00:42:43,240
és valójában csak egy dolog
egy időben, de lehet legalább

918
00:42:43,240 --> 00:42:45,790
nézd meg egy dolog, akkor a
következő dolog közvetlenül mellette.

919
00:42:45,790 --> 00:42:47,380
>> Tehát ezek érdekében?

920
00:42:47,380 --> 00:42:48,032
Természetesen nem.

921
00:42:48,032 --> 00:42:48,740
Szóval tudod mit?

922
00:42:48,740 --> 00:42:51,020
Miért nem veszünk baba
lépéseket a probléma elhárításán

923
00:42:51,020 --> 00:42:53,410
ahelyett, hogy ezeket a díszes
algoritmusok, mint Ben, ahol

924
00:42:53,410 --> 00:42:56,440
ő egyfajta rögzítése által
átkötése a listán

925
00:42:56,440 --> 00:42:59,670
ahelyett, hogy amit tettem, ahol
Én csak ilyen fix, hogy ahogy haladunk?

926
00:42:59,670 --> 00:43:03,650
Nézzük csak a szó szoros értelmében lebontják
fogalma order-- számsorrendben

927
00:43:03,650 --> 00:43:06,990
nevezni, amit want--
ezekbe páros összehasonlítás.

928
00:43:06,990 --> 00:43:07,590
>> Négy és egy.

929
00:43:07,590 --> 00:43:09,970
Ez a helyes sorrendben?

930
00:43:09,970 --> 00:43:11,310
Tehát lássuk javítani.

931
00:43:11,310 --> 00:43:14,700
Egy és négy, majd
akkor csak másolja.

932
00:43:14,700 --> 00:43:15,560
Rendben, jó.

933
00:43:15,560 --> 00:43:17,022
Én fix, egy és négy.

934
00:43:17,022 --> 00:43:18,320
Három és két?

935
00:43:18,320 --> 00:43:18,820
Nem.

936
00:43:18,820 --> 00:43:21,690
Legyen az én szó egyezik az ujjaim.

937
00:43:21,690 --> 00:43:23,695
Négy és három?

938
00:43:23,695 --> 00:43:27,930
>> Ez nem azért, úgyhogy megyek
hogy nem egy, három, négy, kettő.

939
00:43:27,930 --> 00:43:28,680
Ok, rendben.

940
00:43:28,680 --> 00:43:32,310
Most négy és kettő?

941
00:43:32,310 --> 00:43:33,370
Meg kell, hogy erősít ez is.

942
00:43:33,370 --> 00:43:36,700
Tehát egy, három, kettő, négy.

943
00:43:36,700 --> 00:43:39,820
Így van ez válogatni?

944
00:43:39,820 --> 00:43:43,170
Nem, de ez közelebb válogatni?

945
00:43:43,170 --> 00:43:48,930
>> Igen, mert a mi fix ezt
hibát javítottuk ezt a hibát,

946
00:43:48,930 --> 00:43:50,370
és fix ezt a hibát.

947
00:43:50,370 --> 00:43:52,420
Tehát rögzített három hibák vitathatatlanul.

948
00:43:52,420 --> 00:43:58,100
Még nem igazán néz ki a rendezett, de
objektíve közelebb sorba rendezett

949
00:43:58,100 --> 00:44:00,080
mert fix néhány ilyen hibákat.

950
00:44:00,080 --> 00:44:02,047
>> Most mi a teendőm?

951
00:44:02,047 --> 00:44:03,630
Valahogy a végére ért a listán.

952
00:44:03,630 --> 00:44:05,680
Úgy tűnt, hogy fix
a hibákat, de nem.

953
00:44:05,680 --> 00:44:08,510
Mivel ebben az esetben bizonyos számok
Lehet, hogy lassan kialakult szorosabb

954
00:44:08,510 --> 00:44:10,410
más számokat
még elromlott.

955
00:44:10,410 --> 00:44:12,951
Tehát lássuk újra, és én
csak csináld helyett ebben az időben.

956
00:44:12,951 --> 00:44:14,170
Egy és három?

957
00:44:14,170 --> 00:44:14,720
Rendben van.

958
00:44:14,720 --> 00:44:16,070
Három és két?

959
00:44:16,070 --> 00:44:17,560
Természetesen nem, úgyhogy változtatni.

960
00:44:17,560 --> 00:44:19,160
Tehát kettő, három.

961
00:44:19,160 --> 00:44:21,340
Három és négy?

962
00:44:21,340 --> 00:44:24,370
És most nézzük csak lehet
Különösen pedáns itt.

963
00:44:24,370 --> 00:44:26,350
Vajon rendezve?

964
00:44:26,350 --> 00:44:29,280
Ti emberek tudják, ez rendezve.

965
00:44:29,280 --> 00:44:30,400
>> Meg kell próbálni újra.

966
00:44:30,400 --> 00:44:31,900
Tehát Olivia javasolja megpróbálom újra.

967
00:44:31,900 --> 00:44:32,530
Miért?

968
00:44:32,530 --> 00:44:35,810
Mivel a számítógép nem rendelkezik
A luxus a mi emberi szem

969
00:44:35,810 --> 00:44:38,080
csak nézett back-- OK, kész vagyok.

970
00:44:38,080 --> 00:44:41,610
Hogyan működik a számítógép határozza meg
hogy a lista most rendezett?

971
00:44:41,610 --> 00:44:44,590
Mechanikusan.

972
00:44:44,590 --> 00:44:47,650
>> Azt kell átmenni
még egyszer, és csak akkor, ha

973
00:44:47,650 --> 00:44:51,190
nem tesznek / valamilyen hibára tudok
majd kötni, mint a számítógép, aha,

974
00:44:51,190 --> 00:44:51,980
vagyunk jó menni.

975
00:44:51,980 --> 00:44:54,850
Tehát egy és két, két és
három, három és négy.

976
00:44:54,850 --> 00:44:58,030
Most már véglegesen mondják, hogy ez
válogatni, mert nem tett változások.

977
00:44:58,030 --> 00:45:01,940
Most lenne egy hiba, és csak
ostoba, ha a számítógépet,

978
00:45:01,940 --> 00:45:05,640
Megkérdeztük a ugyanazokat a kérdéseket újra
várta különböző válaszokat.

979
00:45:05,640 --> 00:45:07,110
Nem történhet meg.

980
00:45:07,110 --> 00:45:08,600
>> És így most a lista.

981
00:45:08,600 --> 00:45:12,630
Sajnos, futási ideje
ez az algoritmus is n négyzeten.

982
00:45:12,630 --> 00:45:13,130
Miért?

983
00:45:13,130 --> 00:45:19,520
Mert van n számokat, és a
legrosszabb esetben meg kell mozgatni n számok

984
00:45:19,520 --> 00:45:23,637
n-szer, mert meg kell tartani fog
vissza, hogy ellenőrizze és potenciálisan erősít

985
00:45:23,637 --> 00:45:24,220
ezeket a számokat.

986
00:45:24,220 --> 00:45:26,280
És nem tehetünk egy
formai elemzése is.

987
00:45:26,280 --> 00:45:29,530
>> Tehát ez az egész, hogy azt mondják, amit tett
Három különböző megközelítések egyike

988
00:45:29,530 --> 00:45:32,210
Ezekről azonnal intuitív
kapásból Ben

989
00:45:32,210 --> 00:45:35,170
az általam javasolt beillesztése
sort egy ehhez

990
00:45:35,170 --> 00:45:38,540
ahol a fajta szabad szem elől téveszteni
Az erdőben a fák kezdetben.

991
00:45:38,540 --> 00:45:41,760
De akkor, ha egy lépést hátra,
íme, kijavítottuk a rendezési fogalom.

992
00:45:41,760 --> 00:45:43,824
Tehát ez, mer mondani,
egy alacsonyabb szinten talán

993
00:45:43,824 --> 00:45:45,740
mint néhány ilyen egyéb
algoritmusok, de most

994
00:45:45,740 --> 00:45:48,550
hátha nem tudjuk elképzelni
ezek útján ezt.

995
00:45:48,550 --> 00:45:51,450
>> Tehát ez nagyon szép
szoftver, hogy valaki

996
00:45:51,450 --> 00:45:56,110
írta segítségével színes sávok, ami
fog tenni a következő számunkra.

997
00:45:56,110 --> 00:45:57,736
Mindegyik rúd számot jelent.

998
00:45:57,736 --> 00:46:00,026
Taller bárban, a nagyobb
a szám, annál kisebb a bárban,

999
00:46:00,026 --> 00:46:00,990
Minél kisebb a szám.

1000
00:46:00,990 --> 00:46:05,880
Tehát ideális esetben szeretnénk egy szép piramis
ahol kezdődik a kis és nagy lesz,

1001
00:46:05,880 --> 00:46:08,330
és hogy azt jelentené, hogy
Ezek a sávok vannak rendezve.

1002
00:46:08,330 --> 00:46:11,200
Így fogok menni előre, és válassza ki,
például Ben algoritmus

1003
00:46:11,200 --> 00:46:13,990
first-- kiválasztás sort.

1004
00:46:13,990 --> 00:46:16,220
>> És észre, mit csinál.

1005
00:46:16,220 --> 00:46:18,670
Az, ahogyan azt választotta, hogy
vizualizálni ezt az algoritmust

1006
00:46:18,670 --> 00:46:22,090
hogy, mint én
séta listámon,

1007
00:46:22,090 --> 00:46:24,710
ez a program sétál
révén számok listája,

1008
00:46:24,710 --> 00:46:28,160
kiemelve rózsaszín minden
szám, amely azt nézi.

1009
00:46:28,160 --> 00:46:32,360
És mi fog történni most?

1010
00:46:32,360 --> 00:46:35,154
>> A legkisebb szám, amely
I. vagy Ben találtam hirtelen

1011
00:46:35,154 --> 00:46:36,820
gets költözött a lista elejére.

1012
00:46:36,820 --> 00:46:40,037
És vegyük észre, ők elkergeti
a számot, hogy ott volt,

1013
00:46:40,037 --> 00:46:41,120
és ez tökéletesen megfelel.

1014
00:46:41,120 --> 00:46:42,600
Nem bejutni, hogy részletességgel.

1015
00:46:42,600 --> 00:46:44,308
De meg kell tenni
ez a szám valahol,

1016
00:46:44,308 --> 00:46:47,775
így csak át azt a
nyitott helyre jött létre.

1017
00:46:47,775 --> 00:46:49,900
Így fogom gyorsítani
fel, mert különben

1018
00:46:49,900 --> 00:46:51,871
lesz nagyon unalmas gyorsan.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animáció célozza meg is vagyunk.

1021
00:46:58,600 --> 00:47:01,850
Tehát most ugyanezt az elvet
Azt alkalmazása, de

1022
00:47:01,850 --> 00:47:06,540
lehet kezdeni, hogy úgy érzi, az algoritmus, ha
lesz, vagy nézzük meg egy kicsit tisztábban.

1023
00:47:06,540 --> 00:47:13,190
És ez az algoritmus az a hatása,
kiválasztja a következő legkisebb eleme,

1024
00:47:13,190 --> 00:47:16,422
így fogsz kezdeni
látni rámpa fel a bal oldalon.

1025
00:47:16,422 --> 00:47:19,130
És minden iterációban, ahogyan azt
javasolt, mégis egy kicsit kevesebb munka.

1026
00:47:19,130 --> 00:47:21,921
Nem kell menni egészen
vissza a bal a lista végére,

1027
00:47:21,921 --> 00:47:23,900
mert már
tudja, hogy azok vannak rendezve.

1028
00:47:23,900 --> 00:47:28,129
Tehát ez a fajta érzés, mintha
gyorsuló, bár mindegyik lépés

1029
00:47:28,129 --> 00:47:29,420
figyelembe ugyanannyi idő alatt.

1030
00:47:29,420 --> 00:47:31,600
Már csak kevesebb lépésben megmaradt.

1031
00:47:31,600 --> 00:47:35,240
És most akkor milyen érezni a
algoritmus megtisztítása a vége,

1032
00:47:35,240 --> 00:47:37,040
sőt most már rendezve.

1033
00:47:37,040 --> 00:47:41,620
>> Tehát behelyezés rendezés mindezt.

1034
00:47:41,620 --> 00:47:43,600
Azt, hogy újra kell véletlenszerű a tömbben.

1035
00:47:43,600 --> 00:47:45,940
És észre tudok csak
tartsa randomizing azt,

1036
00:47:45,940 --> 00:47:50,630
és mi lesz közelítése
Ugyanezt a megközelítést, beillesztés sort.

1037
00:47:50,630 --> 00:47:55,050
Hadd lelassítják itt.

1038
00:47:55,050 --> 00:47:56,915
Kezdjük a dolgot.

1039
00:47:56,915 --> 00:47:57,414
Állj meg.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Hagyjuk négy.

1042
00:48:02,410 --> 00:48:03,200
Ott vagyunk.

1043
00:48:03,200 --> 00:48:04,190
Véletlenszerű azok tömb.

1044
00:48:04,190 --> 00:48:05,555
És itt go-- beillesztés sort.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Játszani.

1047
00:48:12,800 --> 00:48:17,280
Figyeljük meg, hogy ez foglalkozik az egyes
elem találkozik rögtön,

1048
00:48:17,280 --> 00:48:20,282
de ha ez tartozik
rossz helyen közlemény

1049
00:48:20,282 --> 00:48:21,740
az egész munkát, hogy meg kell történnie.

1050
00:48:21,740 --> 00:48:24,700
Meg kell tartani változó több
több eleme, hogy helyet

1051
00:48:24,700 --> 00:48:27,340
Az egyik akarunk bevezetni.

1052
00:48:27,340 --> 00:48:30,740
>> Tehát mi összpontosítva
elhagyta a lista végére csak.

1053
00:48:30,740 --> 00:48:34,460
Figyeljük mi még nem is nézett figyeléssel mi
nem kiemelt rózsaszín semmit

1054
00:48:34,460 --> 00:48:35,610
jobbra.

1055
00:48:35,610 --> 00:48:38,180
Mi csak foglalkozik
A probléma, ahogy haladunk,

1056
00:48:38,180 --> 00:48:40,430
De mi hozzuk létre a sok
dolgozni magunk is.

1057
00:48:40,430 --> 00:48:44,410
És így, ha ezt felgyorsíthatja
Most megy a befejezésig,

1058
00:48:44,410 --> 00:48:46,210
van egy másik úgy érzi, hogy ez valóban.

1059
00:48:46,210 --> 00:48:50,150
Ez csak összpontosítva a bal végén, de
ezzel egy kicsit több munkát, mint needed--

1060
00:48:50,150 --> 00:48:53,230
fajta elsimítani
felett, rögzítő dolgokat,

1061
00:48:53,230 --> 00:48:58,350
de foglalkozunk végső soron
minden elem egyesével

1062
00:48:58,350 --> 00:49:07,740
amíg eljutunk the-- jól, mi
mindannyian tudjuk, hogy ez lesz a vége,

1063
00:49:07,740 --> 00:49:09,700
így ez egy kicsit underwhelming talán.

1064
00:49:09,700 --> 00:49:12,830
>> De a lista a end--
spoiler-- fog rendezni.

1065
00:49:12,830 --> 00:49:15,300
Tehát nézzük meg egy utolsó.

1066
00:49:15,300 --> 00:49:16,840
Nem csak most kihagyja.

1067
00:49:16,840 --> 00:49:18,000
Már majdnem ott vagyunk.

1068
00:49:18,000 --> 00:49:19,980
Két menni, az egyik megy.

1069
00:49:19,980 --> 00:49:22,680
És íme.

1070
00:49:22,680 --> 00:49:23,450
Kiváló.

1071
00:49:23,450 --> 00:49:27,220
>> Tehát most lássuk egy utolsó,
újra randomizing buborék sort.

1072
00:49:27,220 --> 00:49:31,690
És észre, főként, ha azt lassú ez
le, ez folyamatosan lecsapó keresztül.

1073
00:49:31,690 --> 00:49:36,830
De észre ez csak teszi páronként
comparisons-- egyfajta helyi megoldásokat.

1074
00:49:36,830 --> 00:49:39,050
De amint megkapjuk
Az a lista végén rózsaszín,

1075
00:49:39,050 --> 00:49:40,690
mi lesz, hogy újra megtörténjen?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Igen, ez lesz, hogy
kezdeni, hiszen csak

1078
00:49:46,830 --> 00:49:49,870
fix páros hibákat.

1079
00:49:49,870 --> 00:49:53,120
És ez talán kiderült még mások.

1080
00:49:53,120 --> 00:49:58,950
És így ha ezt felgyorsíthatja, akkor
látni, hogy mennyi a neve is mutatja,

1081
00:49:58,950 --> 00:50:01,870
A kisebb elements-- vagy inkább
A nagyobb elements-- kezdik

1082
00:50:01,870 --> 00:50:03,740
buborék fel a csúcsra, ha úgy tetszik.

1083
00:50:03,740 --> 00:50:07,380
És a kisebb elemek
kezd buborék lefelé a bal oldalon.

1084
00:50:07,380 --> 00:50:10,780
És valóban, ez a fajta
a vizuális hatás is.

1085
00:50:10,780 --> 00:50:17,150
És így ez lesz a vége befejező
egy nagyon hasonló módon is.

1086
00:50:17,150 --> 00:50:19,160
>> Nem kell lakni
ezen a bizonyos egy.

1087
00:50:19,160 --> 00:50:21,010
Hadd nyissa meg ezt most is.

1088
00:50:21,010 --> 00:50:24,040
Van néhány más rendezési algoritmusok
a világon, néhány, amely

1089
00:50:24,040 --> 00:50:25,580
elfogják itt.

1090
00:50:25,580 --> 00:50:29,960
És különösen a tanulók, akik nem
szükségképpen vizuális vagy matematikai,

1091
00:50:29,960 --> 00:50:31,930
mint azelőtt, tudjuk
is ezt audially

1092
00:50:31,930 --> 00:50:34,210
ha társítani a hangot ezzel.

1093
00:50:34,210 --> 00:50:36,990
És csak a móka kedvéért, itt egy
Néhány különböző algoritmusok,

1094
00:50:36,990 --> 00:50:40,950
és egyikük különösen te
fog észrevenni az úgynevezett "egyesítés sort."

1095
00:50:40,950 --> 00:50:43,250
>> Ez valójában egy alapvetően
jobb algoritmust,

1096
00:50:43,250 --> 00:50:45,860
oly módon, hogy egyesíti a fajta, az egyik
az is fogsz látni,

1097
00:50:45,860 --> 00:50:49,170
nem sorrendben n négyzeten.

1098
00:50:49,170 --> 00:50:57,280
Ez a sorrend n-szer napló
N, ami valójában kisebb, és így

1099
00:50:57,280 --> 00:50:58,940
gyorsabb, mint a másik három.

1100
00:50:58,940 --> 00:51:00,670
És van egy pár más
buta is, hogy majd meglátjuk.

1101
00:51:00,670 --> 00:51:01,933
>> Tehát itt vagyunk néhány hang.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Ez beillesztés sort, így ismét
ez csak foglalkozik az elemeket

1104
00:51:10,490 --> 00:51:13,420
ahogy jönnek.

1105
00:51:13,420 --> 00:51:17,180
Ez a fajta buborék, így
figyelembe véve azokat párok egy időben.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
És ismét, a legnagyobb elemei
vannak bugyogott fel a csúcsra.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Következik kiválasztás sort.

1110
00:51:41,710 --> 00:51:45,420
Ez Ben-algoritmust, ahol
ismét ő adja iteratív

1111
00:51:45,420 --> 00:51:46,843
A következő legkisebb eleme.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
És ismét, most már tényleg hallani, hogy
ez felgyorsítja, de csak annyiban, amennyiben

1114
00:51:53,900 --> 00:51:58,230
mivel csinál kevésbé
dolgozni minden iterációban.

1115
00:51:58,230 --> 00:52:04,170
Ez a gyorsabb, összeolvad sort,
amely válogatás klaszterek számát

1116
00:52:04,170 --> 00:52:05,971
együtt, majd egyesíti őket.

1117
00:52:05,971 --> 00:52:07,720
Tehát look-- bal
fele már rendezve.

1118
00:52:07,720 --> 00:52:14,165
>> Most ez a válogatás a jobb oldalát, és
most ez lesz, hogy összekapcsolják őket egy.

1119
00:52:14,165 --> 00:52:19,160
Ez egy úgynevezett "Gnome sort."

1120
00:52:19,160 --> 00:52:23,460
És akkor milyen látni, hogy
ez megy oda-vissza,

1121
00:52:23,460 --> 00:52:27,950
rögzítő munka egy kicsit itt és
ott mielőtt megkezdené az új munkát.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
És ez az.

1124
00:52:33,692 --> 00:52:36,400
Van egy másik fajta, ami
tényleg csak tudományos célokra,

1125
00:52:36,400 --> 00:52:40,980
az úgynevezett "buta sort", amely úgy
Adatai rendezi meg véletlenszerűen,

1126
00:52:40,980 --> 00:52:43,350
majd leellenőrzi, hogy van rendezve.

1127
00:52:43,350 --> 00:52:47,880
És ha ez nem, akkor újra rendezi It
véletlenszerűen ellenőrzi, hogy ez rendezve,

1128
00:52:47,880 --> 00:52:49,440
és ha nem ismétlődik.

1129
00:52:49,440 --> 00:52:52,660
És elméletileg véletlenszerűen
ez a teljes,

1130
00:52:52,660 --> 00:52:54,140
de miután egy kicsit az időben.

1131
00:52:54,140 --> 00:52:56,930
Ez nem a leginkább
hatékony algoritmusok.

1132
00:52:56,930 --> 00:53:02,550
Tehát bármilyen kérdése azokon
Különösen algoritmusok vagy bármi

1133
00:53:02,550 --> 00:53:04,720
kapcsolódó ott is?

1134
00:53:04,720 --> 00:53:09,430
>> Nos, most már ugratni egymástól, mi minden
ezek a vonalak, hogy én már rajz

1135
00:53:09,430 --> 00:53:15,090
és amit én feltételezve, hogy a számítógép
tehet a motorháztető alatt.

1136
00:53:15,090 --> 00:53:18,650
Azt állítják, hogy az összes ezeket a számokat
Folyton drawing-- hogy szükséged van

1137
00:53:18,650 --> 00:53:21,330
tárolni valahol a memóriában.

1138
00:53:21,330 --> 00:53:24,130
Majd megszabadulni ez a srác most is.

1139
00:53:24,130 --> 00:53:30,110
>> Tehát egy darab memória egy
computer-- így RAM DIMM

1140
00:53:30,110 --> 00:53:35,480
amit keresett tegnap, kettős
belső memória module-- néz ki.

1141
00:53:35,480 --> 00:53:39,370
És minden egyes ilyen kis fekete chipek
néhány byte-ok száma, jellemzően.

1142
00:53:39,370 --> 00:53:44,380
És akkor az arany csapok, mint a
vezetékek csatlakoztassa a számítógéphez,

1143
00:53:44,380 --> 00:53:47,521
és a zöld szilícium tábla csak
mit tart mindent együtt.

1144
00:53:47,521 --> 00:53:48,770
Tehát mit jelent ez valójában?

1145
00:53:48,770 --> 00:53:53,180
Ha valahogy felhívni a ugyanazt a képet,
Tegyük fel az egyszerűség kedvéért

1146
00:53:53,180 --> 00:53:55,280
hogy ez a DIMM, dual
inline memória modul,

1147
00:53:55,280 --> 00:54:00,530
egy gigabájt RAM-mal, egy gigabájt
memória, ami hány bájt összesen?

1148
00:54:00,530 --> 00:54:02,100
Egy gigabájt hány bájt?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Több annàl.

1151
00:54:06,030 --> 00:54:09,960
1124 az kilo, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega millió.

1153
00:54:11,730 --> 00:54:14,570
Giga egy milliárd.

1154
00:54:14,570 --> 00:54:15,070
>> Vagyok hazudik?

1155
00:54:15,070 --> 00:54:16,670
Tudunk még olvasni a címkét?

1156
00:54:16,670 --> 00:54:19,920
Ez valójában 128
gigabyte, így tovább.

1157
00:54:19,920 --> 00:54:22,130
De majd, mintha ez
csak egy gigabájt.

1158
00:54:22,130 --> 00:54:25,640
Tehát ez azt jelenti, van egy milliárd
byte memóriát elérhető számomra

1159
00:54:25,640 --> 00:54:29,770
vagy 8 milliárd bit, de megyünk
beszélni szempontjából byte most,

1160
00:54:29,770 --> 00:54:30,750
haladni előre.

1161
00:54:30,750 --> 00:54:36,330
>> Tehát mit jelent az, hogy ez
Egy bájt, ez egy másik byte,

1162
00:54:36,330 --> 00:54:38,680
ez egy másik byte,
és ha igazán akart

1163
00:54:38,680 --> 00:54:43,280
egyedinek mi lett volna
felhívni egymilliárd kis négyzetek.

1164
00:54:43,280 --> 00:54:44,320
De mit jelent ez?

1165
00:54:44,320 --> 00:54:46,420
Nos, hadd zoom
az ezen a képen.

1166
00:54:46,420 --> 00:54:50,900
Ha van valami, hogy úgy néz ki,
mint ez most, ez a négy bájt.

1167
00:54:50,900 --> 00:54:53,710
>> És így tudtam tenni négy szám van.

1168
00:54:53,710 --> 00:54:54,990
Egy kettő három négy.

1169
00:54:54,990 --> 00:55:00,170
Vagy akár fel négy betű vagy szimbólum.

1170
00:55:00,170 --> 00:55:02,620
"Hé!" mehet ott,
mert az egyes betűk,

1171
00:55:02,620 --> 00:55:04,370
korábban beszéltünk,
ábrázolható

1172
00:55:04,370 --> 00:55:06,650
Nyolc bit vagy ASCII vagy egy bájt.

1173
00:55:06,650 --> 00:55:09,370
Más szóval, akkor
tegye 8000000000 dolog benne

1174
00:55:09,370 --> 00:55:11,137
Ennek az egy bottal a memória.

1175
00:55:11,137 --> 00:55:14,345
Most ez mit jelent, hogy a dolgokat vissza
hogy háttal a memóriában, mint ez?

1176
00:55:14,345 --> 00:55:17,330
Ez az, amit a programozó
neveznék egy "tömbben".

1177
00:55:17,330 --> 00:55:21,250
Egy számítógépes program, akkor nem hiszem,
a mögöttes hardver önmagában.

1178
00:55:21,250 --> 00:55:24,427
Te csak gondolsz magadra, mint amelyek
hozzáférést egy milliárd byte teljes,

1179
00:55:24,427 --> 00:55:26,010
és akkor bármit akarsz vele.

1180
00:55:26,010 --> 00:55:27,880
De az egyszerűség kedvéért
sokszor hasznos

1181
00:55:27,880 --> 00:55:31,202
megtartani a memória jobb
egymás mellett, mint ez.

1182
00:55:31,202 --> 00:55:33,660
Tehát ha Ráközelíthetek this--
mert mi biztosan nem fog

1183
00:55:33,660 --> 00:55:39,310
felhívni egymilliárd kis squares--
Tegyük fel, hogy ez a testület képviseli

1184
00:55:39,310 --> 00:55:40,610
hogy bottal a memória most.

1185
00:55:40,610 --> 00:55:43,800
És én csak felhívni annyi, mint a
marker végül, hogy nekem itt.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Tehát most van egy bot
A memória a fedélzeten

1188
00:55:52,300 --> 00:55:56,400
hogy van egy, kettő, három, négy, öt,
hat, egy, kettő, három, négy, öt, hat,

1189
00:55:56,400 --> 00:56:01,130
seven-- így 42 byte
memória a képernyőn teljes.

1190
00:56:01,130 --> 00:56:01,630
Köszönöm.

1191
00:56:01,630 --> 00:56:02,838
Igen, nem az én aritmetikai jobbra.

1192
00:56:02,838 --> 00:56:05,120
Tehát 42 bájt memóriát itt.

1193
00:56:05,120 --> 00:56:06,660
Mit is jelent ez valójában?

1194
00:56:06,660 --> 00:56:09,830
Nos, egy számítógép programozó
valójában általában

1195
00:56:09,830 --> 00:56:12,450
gondolni ezt emlékezet címezhető.

1196
00:56:12,450 --> 00:56:16,630
Más szóval, minden ilyen
helyek memóriájában, a hardver,

1197
00:56:16,630 --> 00:56:18,030
egyedi címmel rendelkezik.

1198
00:56:18,030 --> 00:56:22,020
>> Ez nem olyan bonyolult, mint egy Brattle
Square, Cambridge, Mass., 02.138.

1199
00:56:22,020 --> 00:56:23,830
Ehelyett csak egy szám.

1200
00:56:23,830 --> 00:56:27,930
Ez bájtos szám nulla, ez az
egy, ez két, ez a három,

1201
00:56:27,930 --> 00:56:30,327
és ez a 41.

1202
00:56:30,327 --> 00:56:30,910
Várj egy percet.

1203
00:56:30,910 --> 00:56:32,510
Azt hittem, azt mondta, 42 perccel ezelőtt.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Elkezdtem számolni nulla,
így valójában helyes.

1206
00:56:37,772 --> 00:56:40,980
Most nem kell ténylegesen rajzolni
mint egy rács, és ha rajzolni, mint a rács

1207
00:56:40,980 --> 00:56:43,520
Azt hiszem, a dolgok valóban
egy kicsit félrevezető.

1208
00:56:43,520 --> 00:56:46,650
Mi egy programozó lenne,
a saját szem előtt tartva,

1209
00:56:46,650 --> 00:56:50,310
Általában úgy gondoljuk, ennek az
memória, olyan, mint egy szalag,

1210
00:56:50,310 --> 00:56:53,340
mint egy darab szalaggal
hogy csak megy, és a végtelenségig

1211
00:56:53,340 --> 00:56:54,980
vagy amíg elfogy a memória.

1212
00:56:54,980 --> 00:56:59,200
Így egy sokkal gyakoribb módon felhívni
és gondoljunk csak a memória

1213
00:56:59,200 --> 00:57:03,710
lenne, hogy ez a bájt nulla, egy,
kettő, három, majd pont, pont, pont.

1214
00:57:03,710 --> 00:57:07,650
És van 42 ilyen bájt teljes, még
bár fizikailag is veszélybe

1215
00:57:07,650 --> 00:57:09,480
valami több, mint ez.

1216
00:57:09,480 --> 00:57:12,850
>> Tehát ha most úgy a
memória, mint ez, mint egy szalag,

1217
00:57:12,850 --> 00:57:17,640
ez az, amit a programozó újra
nevezném tömb memória.

1218
00:57:17,640 --> 00:57:20,660
És ha azt szeretné, hogy ténylegesen készlet
valamit a számítógép memóriájában,

1219
00:57:20,660 --> 00:57:23,290
Ön általában nem tárolja a dolgokat
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Tehát mi már számokról beszélünk.

1221
00:57:25,010 --> 00:57:30,880
És amikor akartam megoldani a problémákat
mint négy, egy, három, kettő,

1222
00:57:30,880 --> 00:57:33,820
bár én csak rajz
Csak a számok négy, egy, három,

1223
00:57:33,820 --> 00:57:39,490
két a táblán, a számítógép lenne
tényleg ez a beállítás a memóriában.

1224
00:57:39,490 --> 00:57:43,347
>> És mi lesz a következő, hogy a
kettő a számítógép memóriájában?

1225
00:57:43,347 --> 00:57:44,680
Nos, nincs válasz.

1226
00:57:44,680 --> 00:57:45,770
Nem igazán tudom.

1227
00:57:45,770 --> 00:57:48,200
És olyan hosszú, mint a
számítógép nem kell azt,

1228
00:57:48,200 --> 00:57:51,440
nem kell törődni, mi mellett
A számok igen törődik.

1229
00:57:51,440 --> 00:57:55,130
És amikor azt mondta korábban, hogy a számítógép
Csak nézd meg egy címet, egy időben,

1230
00:57:55,130 --> 00:57:56,170
ez a fajta, hogy miért.

1231
00:57:56,170 --> 00:57:59,490
>> Nem eltérően rekord
lejátszó és egy olvasó fej

1232
00:57:59,490 --> 00:58:03,030
csak, hogy képes nézni egy bizonyos
groove fizikai old-school rekord

1233
00:58:03,030 --> 00:58:06,500
egy időben, hasonlóképpen
lehet egy számítógép köszönhetően

1234
00:58:06,500 --> 00:58:09,810
a CPU és
Intel utasításkészlet,

1235
00:58:09,810 --> 00:58:12,480
között, amelynek használati
olvasni a memóriából

1236
00:58:12,480 --> 00:58:15,590
vagy mentse memory-- egy
számítógép csak nézd

1237
00:58:15,590 --> 00:58:19,210
az egyik helyen egy time--
Néha ezek kombinációja,

1238
00:58:19,210 --> 00:58:21,770
de tényleg csak egy helyen egy időben.

1239
00:58:21,770 --> 00:58:24,770
Tehát, ha csinálunk
A különböző algoritmusok,

1240
00:58:24,770 --> 00:58:28,110
Én nem csak az írás a
vacuum-- négy, egy, három, kettő.

1241
00:58:28,110 --> 00:58:30,849
Ezek a számok valójában tartozik
valahol a fizikai memória.

1242
00:58:30,849 --> 00:58:32,890
Tehát vannak apró
tranzisztorok, vagy valamilyen

1243
00:58:32,890 --> 00:58:35,840
az elektronika alatt
motorháztető tárolására ezeket az értékeket.

1244
00:58:35,840 --> 00:58:40,460
>> És összesen hány bitet
részt most, csak hogy világos?

1245
00:58:40,460 --> 00:58:45,580
Tehát ez a négy bájt, vagy
most már 32 bit összesen.

1246
00:58:45,580 --> 00:58:49,280
Tehát vannak valójában 32 nullákkal
azok alkotó ezt a négy dolgot.

1247
00:58:49,280 --> 00:58:52,070
Van még itt, de
megint nem érdekel.

1248
00:58:52,070 --> 00:58:55,120
>> Tehát most kérdezzük meg a másik
kérdés a memória,

1249
00:58:55,120 --> 00:58:57,519
mert, hogy a végén
A nap a variancia.

1250
00:58:57,519 --> 00:59:00,310
Nem számít, mit tehetünk a
A számítógép, a végén a nap

1251
00:59:00,310 --> 00:59:02,560
a hardver még mindig a
ugyanaz a motorháztető alatt.

1252
00:59:02,560 --> 00:59:04,670
Hogyan tudom tárolni egy szót itt?

1253
00:59:04,670 --> 00:59:09,710
Nos, egy szó, egy számítógép, mint a
"Hé!" kellene tárolni, mint ez.

1254
00:59:09,710 --> 00:59:12,300
És ha volna egy hosszabb
szó, akkor egyszerűen

1255
00:59:12,300 --> 00:59:19,120
felülírja ezt, és azt mondják, valami
mint a "hello", és tárolja, hogy itt.

1256
00:59:19,120 --> 00:59:23,930
>> És így itt is, ez contiguousness
valójában előny,

1257
00:59:23,930 --> 00:59:26,530
mert a számítógép már csak
jobbról balra.

1258
00:59:26,530 --> 00:59:28,680
De itt van egy kérdés.

1259
00:59:28,680 --> 00:59:33,480
Ebben az összefüggésben a szó,
H-E-L-L-O, felkiáltójel,

1260
00:59:33,480 --> 00:59:38,740
hogyan lehet a számítógép tudja, hol a
szó kezdődik és hol végződik a szó?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
Az összefüggésben számok,
hogyan működik a számítógép

1263
00:59:43,800 --> 00:59:48,396
tudom, milyen hosszú a sorrend
számok vagy hol kezdődik?

1264
00:59:48,396 --> 00:59:50,270
Nos, kiderült out--
és nem megyünk túl sokat

1265
00:59:50,270 --> 00:59:54,970
ebbe szintje detail--
számítógépek mozog dolog körül a memóriában

1266
00:59:54,970 --> 00:59:57,800
szó útján ezeket a címeket.

1267
00:59:57,800 --> 01:00:02,080
Tehát egy számítógép, ha
kód írása tárolni dolgokat

1268
01:00:02,080 --> 01:00:05,800
mint a szavak, amit te
tényleg csinál gépel

1269
01:00:05,800 --> 01:00:11,320
kifejezések, amelyek megjegyzik, ahol a
A számítógép memóriája ezek a szavak.

1270
01:00:11,320 --> 01:00:14,370
Tehát hadd csinálni egy nagyon,
nagyon egyszerű példát.

1271
01:00:14,370 --> 01:00:18,260
>> Megyek megy előre, és
nyit egy egyszerű szöveges programot,

1272
01:00:18,260 --> 01:00:20,330
és megyek, hogy hozzon létre
nevű fájlt hello.c.

1273
01:00:20,330 --> 01:00:22,849
Ezen információk többsége azt
Nem megyek bele a részletekbe menően,

1274
01:00:22,849 --> 01:00:25,140
de fogok írni egy
programot, hogy ugyanazon a nyelven,

1275
01:00:25,140 --> 01:00:31,140
C. Ez sokkal megfélemlítő,
Azt állítani, mint Scratch,

1276
01:00:31,140 --> 01:00:32,490
de ez nagyon hasonlít a szellem.

1277
01:00:32,490 --> 01:00:34,364
Valójában ezek a göndör
braces-- akkor milyen

1278
01:00:34,364 --> 01:00:37,820
gondolni, amit én csináltam, mint ez.

1279
01:00:37,820 --> 01:00:39,240
>> Csináljuk, valóban.

1280
01:00:39,240 --> 01:00:45,100
Amikor zöld zászló kattint,
tegye a következőket.

1281
01:00:45,100 --> 01:00:50,210
Szeretnék kinyomtatni "hello".

1282
01:00:50,210 --> 01:00:51,500
Tehát ez most pszeudokód.

1283
01:00:51,500 --> 01:00:53,000
Én fajta összemosódnak a vonalak.

1284
01:00:53,000 --> 01:00:56,750
A C-ben, ezen a nyelven beszélek
körülbelül ez a sor nyomtatási szia

1285
01:00:56,750 --> 01:01:01,940
valóban lesz "printf" a
Néhány zárójelben, és pontosvessző.

1286
01:01:01,940 --> 01:01:03,480
>> De ez pontosan ugyanaz a gondolat.

1287
01:01:03,480 --> 01:01:06,730
És ez nagyon felhasználóbarát
"Amikor a zöld zászló kattintott" válik

1288
01:01:06,730 --> 01:01:10,182
a sokkal misztikus "int main semmis."

1289
01:01:10,182 --> 01:01:12,890
És ez tényleg nincs feltérképezése,
úgyhogy csak fog figyelmen kívül.

1290
01:01:12,890 --> 01:01:17,210
De a kapcsos zárójelek, mint a
ívelt puzzle darab, mint ez.

1291
01:01:17,210 --> 01:01:18,700
>> Így a fajta kitalálni.

1292
01:01:18,700 --> 01:01:22,357
Akkor is, ha soha nem beprogramozott,
mit jelent ez a program valószínűleg nem?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Valószínűleg kinyomtatja szia
felkiáltójellel.

1295
01:01:28,000 --> 01:01:29,150
>> Úgyhogy próbáljuk ezt.

1296
01:01:29,150 --> 01:01:30,800
Megyek megmenteni.

1297
01:01:30,800 --> 01:01:34,000
És ez ismét egy nagyon
régi iskolai környezetben.

1298
01:01:34,000 --> 01:01:35,420
Nem tudok rákattintani, én nem húzza.

1299
01:01:35,420 --> 01:01:36,910
Van parancsokat.

1300
01:01:36,910 --> 01:01:41,320
Szóval azt akarom, hogy fut a program, így
Talán ezt, mint hello.c.

1301
01:01:41,320 --> 01:01:42,292
Ez a fájl futottam.

1302
01:01:42,292 --> 01:01:43,500
De várjunk csak, én eltűnt egy lépést.

1303
01:01:43,500 --> 01:01:46,470
Mit is mondtunk szükséges
lépés a nyelv, mint a C?

1304
01:01:46,470 --> 01:01:49,470
Most írott forrás
kódot, de mit kell tennem?

1305
01:01:49,470 --> 01:01:50,670
Igen, kell egy fordító.

1306
01:01:50,670 --> 01:01:57,670
Tehát az én Mac itt van egy
nevű program GCC, GNU C fordító,

1307
01:01:57,670 --> 01:02:03,990
amely lehetővé teszi, hogy tegyek this-- viszont
én forráskódot, hívjuk meg,

1308
01:02:03,990 --> 01:02:04,930
gépi kód.

1309
01:02:04,930 --> 01:02:10,180
>> És látom, hogy
ismét, az alábbiak szerint, ezek a

1310
01:02:10,180 --> 01:02:14,090
a nullák és egyesek csak
készítette az én forráskódját,

1311
01:02:14,090 --> 01:02:15,730
mind a nullák.

1312
01:02:15,730 --> 01:02:17,770
És ha azt szeretnénk, hogy futtatni
én program-- ez történik

1313
01:02:17,770 --> 01:02:23,010
hogy hívják a.out számára
történelmi reasons-- "hello".

1314
01:02:23,010 --> 01:02:24,070
Tudok futni újra.

1315
01:02:24,070 --> 01:02:25,690
Helló helló helló.

1316
01:02:25,690 --> 01:02:27,430
És úgy tűnik, hogy működik.

1317
01:02:27,430 --> 01:02:31,000
>> De ez azt jelenti, valahol az én
számítógép memóriája a szavak

1318
01:02:31,000 --> 01:02:35,279
H-E-L-L-O, felkiáltójel.

1319
01:02:35,279 --> 01:02:38,070
És kiderül, ahogy félre,
mi az a számítógép jellemzően

1320
01:02:38,070 --> 01:02:40,550
Ehhez, hogy tudja, hol
a dolgok kezdenek és end-- ez

1321
01:02:40,550 --> 01:02:42,460
megy, hogy egy speciális szimbólum van.

1322
01:02:42,460 --> 01:02:46,064
És az egyezmény az, hogy a
szám nulla végén egy szó

1323
01:02:46,064 --> 01:02:48,230
úgy, hogy tudja, hol
ténylegesen véget ér, úgy, hogy

1324
01:02:48,230 --> 01:02:52,750
ne tartsa kinyomtatásával egyre
karakterek, mint amit valójában szeretnék.

1325
01:02:52,750 --> 01:02:55,400
>> De az elvihető, mégha
bár ez meglehetősen bonyolult,

1326
01:02:55,400 --> 01:02:58,140
az, hogy ez végső soron
viszonylag egyszerű.

1327
01:02:58,140 --> 01:03:04,550
Akkor kaptak egyfajta szalag, egy üres
hely, amely akkor leveleket.

1328
01:03:04,550 --> 01:03:07,150
Egyszerűen csak meg, hogy egy
speciális szimbólum, mint önkényesen

1329
01:03:07,150 --> 01:03:10,316
a szám nulla, hogy a végén
a szóval, hogy a gép tudja,

1330
01:03:10,316 --> 01:03:13,410
ó, le kell állítani a nyomtatást követően
Látom a felkiáltójel.

1331
01:03:13,410 --> 01:03:16,090
Mert a következő dolog van
egy ASCII értéke nulla,

1332
01:03:16,090 --> 01:03:19,125
vagy a null karaktert
valaki nevezném.

1333
01:03:19,125 --> 01:03:21,500
De van egyfajta probléma
itt, és menjünk visszaállítsák

1334
01:03:21,500 --> 01:03:23,320
a számok egy pillanatra.

1335
01:03:23,320 --> 01:03:28,720
Tegyük fel, hogy én nem, sőt,
Van egy sor számok,

1336
01:03:28,720 --> 01:03:30,730
és tegyük fel, hogy a
programot írok is

1337
01:03:30,730 --> 01:03:34,680
mint egy évfolyam könyv egy tanár
és a tanárok osztályteremben.

1338
01:03:34,680 --> 01:03:38,720
És ez a program lehetővé teszi a neki
írja be diákjaik pontszámok

1339
01:03:38,720 --> 01:03:39,960
A vetélkedők.

1340
01:03:39,960 --> 01:03:43,750
És tegyük fel, hogy a tanuló kap
100 első kvíz, talán

1341
01:03:43,750 --> 01:03:49,920
mint a 80 a következő, majd a
75, majd 90, a negyedik kvíz.

1342
01:03:49,920 --> 01:03:54,150
>> Tehát ezen a ponton a történet,
a tömb mérete négy.

1343
01:03:54,150 --> 01:03:58,470
Egyáltalán több memóriát a
számítógépet, de a tömb, hogy úgy mondjam,

1344
01:03:58,470 --> 01:04:00,350
ez a méret négy.

1345
01:04:00,350 --> 01:04:06,060
Tegyük fel most, hogy a tanár akar
hozzárendelni egy ötödik kvíz az osztály.

1346
01:04:06,060 --> 01:04:08,510
Nos, az egyik dolog, amit
vagy ő megy, hogy meg kell csinálni

1347
01:04:08,510 --> 01:04:10,650
most tárolja további értéket.

1348
01:04:10,650 --> 01:04:15,490
De ha a tömb a tanár
létre ez a program a méret,

1349
01:04:15,490 --> 01:04:22,440
az egyik probléma egy tömb, amely
akkor nem csak folyamatosan növeli a memória.

1350
01:04:22,440 --> 01:04:26,470
Mert mi van, ha egy másik része a
program a "hé" ott?

1351
01:04:26,470 --> 01:04:29,650
>> Más szavakkal, a memóriát lehet
használt semmit a program.

1352
01:04:29,650 --> 01:04:33,250
És ha előre beírtam, hé,
Azt akarom, hogy input négy kvíz pontszámok,

1353
01:04:33,250 --> 01:04:34,784
lehet, hogy megy itt, és itt.

1354
01:04:34,784 --> 01:04:37,700
És ha hirtelen meggondolja magát
később mondani akarok egy ötödik kvíz

1355
01:04:37,700 --> 01:04:40,872
pontszámot, akkor nem csak
tedd, ahol csak akar,

1356
01:04:40,872 --> 01:04:42,580
mert mi van, ha ez a
a felhasznált memória

1357
01:04:42,580 --> 01:04:45,990
valami else-- más programot
vagy valamilyen más jellemzője a program

1358
01:04:45,990 --> 01:04:46,910
hogy futsz?

1359
01:04:46,910 --> 01:04:50,650
Tehát meg kell gondolni előre
hogyan szeretné tárolni az adatokat,

1360
01:04:50,650 --> 01:04:54,480
mert most már festett
magát egy digitális sarokban.

1361
01:04:54,480 --> 01:04:57,280
>> Tehát egy tanár helyett
mondjuk írásakor a program

1362
01:04:57,280 --> 01:04:59,360
tárolására ő
évfolyamon, tudod mit?

1363
01:04:59,360 --> 01:05:04,180
Fogok kérni,
írásakor a programot,

1364
01:05:04,180 --> 01:05:12,070
hogy szeretnék nulla, egy, kettő, három,
négy, öt, hat, nyolc évfolyamon összesen.

1365
01:05:12,070 --> 01:05:15,320
Tehát egy, kettő, három, négy,
öt, hat, hét, nyolc.

1366
01:05:15,320 --> 01:05:18,612
A tanár csak túlzott kiosztani
memória írásakor ő programja

1367
01:05:18,612 --> 01:05:19,570
és azt mondják, tudod mit?

1368
01:05:19,570 --> 01:05:22,236
Én soha nem fog rendelni több
mint nyolc vetélkedők a félévben.

1369
01:05:22,236 --> 01:05:23,130
Ez csak egy őrült.

1370
01:05:23,130 --> 01:05:24,470
Soha nem fogom kiosztani ezt.

1371
01:05:24,470 --> 01:05:28,270
Annak érdekében, hogy ily módon ő is a
rugalmasság tárolására pontszámokat,

1372
01:05:28,270 --> 01:05:33,010
mint 75, 90, és talán egy plusz, ha
A diák kapott extra hitel, 105.

1373
01:05:33,010 --> 01:05:36,130
>> De ha a tanár nem
használja a három terek,

1374
01:05:36,130 --> 01:05:38,860
van egy intuitív elvihető itt.

1375
01:05:38,860 --> 01:05:41,410
Ő csak kiesik hely.

1376
01:05:41,410 --> 01:05:44,790
Más szóval, van ezen
közös kompromisszum programozás

1377
01:05:44,790 --> 01:05:48,241
ahol akár kiosztani
Pontosan annyi memóriát, amennyit csak akar,

1378
01:05:48,241 --> 01:05:51,490
A fejjel, amely az, hogy te szuper
efficient-- te nem vagy pazarló

1379
01:05:51,490 --> 01:05:54,640
A all-- de a hátránya az, amely
amit ha meggondolja magát, amikor

1380
01:05:54,640 --> 01:05:58,780
A program használata, hogy a tárolni kívánt
több adatot, mint eredetileg tervezte.

1381
01:05:58,780 --> 01:06:03,030
>> Így talán az a megoldás, akkor
írja meg programokat olyan módon

1382
01:06:03,030 --> 01:06:05,605
hogy több memóriát használ
mint amennyi valójában szükséges.

1383
01:06:05,605 --> 01:06:07,730
Így nem mész
befut a problémát,

1384
01:06:07,730 --> 01:06:09,730
De Te pazarló.

1385
01:06:09,730 --> 01:06:12,960
És minél több memóriát a program által használt,
ahogy megbeszéltük tegnap, a kevésbé

1386
01:06:12,960 --> 01:06:15,410
memória, amely elérhető
más programok,

1387
01:06:15,410 --> 01:06:18,790
Az előbb a számítógép lelassulhat
le, mert a virtuális memóriát.

1388
01:06:18,790 --> 01:06:22,670
És így ideális megoldás lehet, hogy mi?

1389
01:06:22,670 --> 01:06:24,610
>> Under-elosztásának tűnik rossz.

1390
01:06:24,610 --> 01:06:27,030
Túlzott elosztásának tűnik rossz.

1391
01:06:27,030 --> 01:06:31,120
Tehát mi lehet a jobb megoldás?

1392
01:06:31,120 --> 01:06:32,390
Átcsoportosítása,.

1393
01:06:32,390 --> 01:06:33,590
Sokkal dinamikusabb.

1394
01:06:33,590 --> 01:06:37,520
Ne erőltesse magát, hogy válasszon egy
priori, az elején, hogy mit akar.

1395
01:06:37,520 --> 01:06:41,370
És biztos, hogy nem túl kiosztani,
nehogy pazarlás.

1396
01:06:41,370 --> 01:06:45,770
>> És így, hogy elérjék ezt a célt,
kell dobni adatstruktúrát,

1397
01:06:45,770 --> 01:06:48,100
hogy úgy mondjam, el.

1398
01:06:48,100 --> 01:06:51,080
És akkor mi van a programozó
általában használ

1399
01:06:51,080 --> 01:06:55,940
az úgynevezett nem
tömb, hanem egy láncolt lista.

1400
01:06:55,940 --> 01:07:00,860
Más szóval, ő lesz
elkezd gondolkodni az emléküket

1401
01:07:00,860 --> 01:07:05,280
mint egyfajta alakja, hogy azok
levonhatjuk a következő módon.

1402
01:07:05,280 --> 01:07:08,520
Ha szeretnék tárolni egy számot
Egy program-- így szeptemberben,

1403
01:07:08,520 --> 01:07:12,600
Megadtam a tanítványaim egy kvíz; Azt akarom
tárolja a tanulók első teszt,

1404
01:07:12,600 --> 01:07:16,220
és van egy 100 it-- I
fogom kérni a számítógépet,

1405
01:07:16,220 --> 01:07:19,540
útján a program, amit
írva egy darab memóriát.

1406
01:07:19,540 --> 01:07:22,570
És én fogom tárolni a
száma 100, és ennyi.

1407
01:07:22,570 --> 01:07:24,820
>> Aztán néhány héttel később
mikor kapom meg a második kvíz,

1408
01:07:24,820 --> 01:07:27,890
és itt az ideje, hogy írja
az, hogy 90%, megyek

1409
01:07:27,890 --> 01:07:32,129
hogy kérje a számítógép, hé, számítógép,
lehet még egy darab a memória?

1410
01:07:32,129 --> 01:07:34,170
Meg fog adni nekem ezt
üres darab memória.

1411
01:07:34,170 --> 01:07:39,370
Azt fogom tenni a szám 90,
de az én programban valahogy other--

1412
01:07:39,370 --> 01:07:42,100
és akkor nem kell aggódnia
A szintaxis this-- szükségem

1413
01:07:42,100 --> 01:07:44,430
valahogy lánc ezeket a dolgokat együtt.

1414
01:07:44,430 --> 01:07:47,430
És én láncolni őket együtt
ami úgy néz ki, mint egy nyíl van.

1415
01:07:47,430 --> 01:07:50,050
>> A harmadik kvíz, hogy jön fel,
Azt fogom mondani, hé, számítógép,

1416
01:07:50,050 --> 01:07:51,680
adj még egy darab a memóriát.

1417
01:07:51,680 --> 01:07:54,660
És én fogom letenni
Bármi is volt, mint a 75,

1418
01:07:54,660 --> 01:07:56,920
és azt kell lánc ezt
együtt most valahogy.

1419
01:07:56,920 --> 01:08:00,290
Negyedik kvíz jön, és talán
ez a vége felé a félévben.

1420
01:08:00,290 --> 01:08:03,140
És ezen a ponton a programot
Lehet, hogy a memória

1421
01:08:03,140 --> 01:08:05,540
az egész hely, az egész fizikailag.

1422
01:08:05,540 --> 01:08:08,170
És így csak a hecc kedvéért, én
fog felhívni a negyedik

1423
01:08:08,170 --> 01:08:11,260
quiz-- emlékszem, mi volt; én
úgy gondolja, talán egy 80 vagy something--

1424
01:08:11,260 --> 01:08:12,500
idefelé.

1425
01:08:12,500 --> 01:08:15,920
>> De ez rendben van, mert képileg
Megyek felhívni a vonalat.

1426
01:08:15,920 --> 01:08:19,063
Más szóval, a valóságban,
a számítógép hardver,

1427
01:08:19,063 --> 01:08:20,979
Az első pont talán
kerül ide, mert

1428
01:08:20,979 --> 01:08:22,529
Rögtön az elején a félévben.

1429
01:08:22,529 --> 01:08:25,810
A következő, hogy végül itt
mert egy kis idő telt el

1430
01:08:25,810 --> 01:08:27,210
és a program folyamatosan fut.

1431
01:08:27,210 --> 01:08:30,060
A következő pont, amely
75, lehet itt.

1432
01:08:30,060 --> 01:08:33,420
És az utolsó pont lehet
egy 80, amely több mint itt.

1433
01:08:33,420 --> 01:08:38,729
>> Így a valóságban, fizikailag, ez lehet
amit a számítógép memóriájában néz ki.

1434
01:08:38,729 --> 01:08:41,569
De ez nem egy hasznos mentális
paradigma egy programozó.

1435
01:08:41,569 --> 01:08:44,649
Miért fontos, ahol a
fene az adatok kiöntött?

1436
01:08:44,649 --> 01:08:46,200
Csak azt, hogy az adatok tárolására.

1437
01:08:46,200 --> 01:08:49,390
>> Ez olyan, mint a vita
korábbi rajz a kocka.

1438
01:08:49,390 --> 01:08:52,200
Miért érdekel, hogy mit
a szög a kocka

1439
01:08:52,200 --> 01:08:53,740
és hogyan kell fordulni rajzolni?

1440
01:08:53,740 --> 01:08:54,950
Csak akar egy kocka.

1441
01:08:54,950 --> 01:08:57,359
Hasonlóképpen, itt
csak azt, hogy grade könyvet.

1442
01:08:57,359 --> 01:08:59,559
Csak azt, hogy úgy gondolja, a
ezt a listát a számok.

1443
01:08:59,559 --> 01:09:01,350
Kit érdekel, hogy milyen ez az
megvalósított hardver?

1444
01:09:01,350 --> 01:09:05,180
>> Tehát a kivételi most
ez a kép itt.

1445
01:09:05,180 --> 01:09:07,580
Ez egy láncolt lista, mint
egy programozó nevezném,

1446
01:09:07,580 --> 01:09:10,640
amennyiben van egy
listáját, nyilvánvalóan a számok.

1447
01:09:10,640 --> 01:09:14,990
De ez kapcsolódik képileg
útján a nyilakat,

1448
01:09:14,990 --> 01:09:18,510
és ezek mind nyilak are-- alatta
A motorháztető, ha kíváncsi,

1449
01:09:18,510 --> 01:09:23,210
Emlékeztetünk arra, hogy a fizikai hardvert
címek nulla, egy, kettő, három, négy.

1450
01:09:23,210 --> 01:09:28,465
Mindezek nyilak olyan, mint egy térkép
vagy irány, ahol, ha a 90 is-- most

1451
01:09:28,465 --> 01:09:29,090
Megvan számolni.

1452
01:09:29,090 --> 01:09:31,750
>> Nulla, egy, kettő, három,
négy, öt, hat, hét.

1453
01:09:31,750 --> 01:09:35,640
Úgy néz ki, mint a 90 van
memóriacím száma hét.

1454
01:09:35,640 --> 01:09:38,460
Mindezek nyilak jelentése
mint egy kis darab papír

1455
01:09:38,460 --> 01:09:42,439
ami így irány a
program, amely azt mondja, kövesse ezt a térképet

1456
01:09:42,439 --> 01:09:43,880
eljutni helyét hét.

1457
01:09:43,880 --> 01:09:46,680
És ott meg fogja találni a
hallgató második kvíz pontszámot.

1458
01:09:46,680 --> 01:09:52,100
Eközben a 75-- ha továbbra is ezt,
ez hét, nyolc, kilenc, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Ez a másik nyilat, jelentése
Egy térkép memóriahely 15.

1461
01:09:59,080 --> 01:10:02,550
De ismétlem, a programozó általában nem
nem érdekli ez részletességgel.

1462
01:10:02,550 --> 01:10:05,530
És a legtöbb minden programozási
nyelv ma, a programozó

1463
01:10:05,530 --> 01:10:10,490
Nem is tudom, hol a memóriában
ezek a számok valójában.

1464
01:10:10,490 --> 01:10:14,830
Minden ő kell törődnünk
hogy azok valahogy kapcsolódnak egymáshoz

1465
01:10:14,830 --> 01:10:18,390
egy adatszerkezet, mint ez.

1466
01:10:18,390 --> 01:10:21,580
>> De kiderül, nem
hogy túlságosan technikai.

1467
01:10:21,580 --> 01:10:27,430
De csak azért, mert talán
engedheti meg magának, hogy ezt a vitát itt,

1468
01:10:27,430 --> 01:10:33,630
tegyük fel, hogy újra
ezt a kérdést itt a tömb.

1469
01:10:33,630 --> 01:10:35,780
Lássuk Sajnálattal megy itt.

1470
01:10:35,780 --> 01:10:42,950
Ez a 100, 90, 75, és 80.

1471
01:10:42,950 --> 01:10:44,980
>> Hadd röviden, hogy ezt az állítást.

1472
01:10:44,980 --> 01:10:48,980
Ez egy tömb, és újra, a
legfeltűnőbb jellemzője tömb

1473
01:10:48,980 --> 01:10:52,400
az, hogy az összes adat vissza
háttal memory-- szó

1474
01:10:52,400 --> 01:10:56,830
Egy bájt vagy talán négy bájt,
néhány fix számú byte-re található.

1475
01:10:56,830 --> 01:11:00,710
A láncolt lista, amit levonhatunk
mint ez, a motorháztető alatt, aki

1476
01:11:00,710 --> 01:11:02,000
tudja, hol van a cucc?

1477
01:11:02,000 --> 01:11:03,630
Nem is kell, hogy áramlás, mint ezt.

1478
01:11:03,630 --> 01:11:06,050
Néhány adat lehetne
vissza a bal ott.

1479
01:11:06,050 --> 01:11:07,530
Nem is tudom.

1480
01:11:07,530 --> 01:11:15,430
>> És így egy sor, akkor a
jellemző az úgynevezett véletlen hozzáférésű.

1481
01:11:15,430 --> 01:11:20,570
És mi véletlen hozzáférésű eszközökkel van
hogy a számítógép képes ugrani azonnal

1482
01:11:20,570 --> 01:11:22,730
bármely részén egy tömbben.

1483
01:11:22,730 --> 01:11:23,580
Miért?

1484
01:11:23,580 --> 01:11:26,000
Mivel a számítógép tudja,
hogy az első hely

1485
01:11:26,000 --> 01:11:29,540
nulla, egy, kettő és három.

1486
01:11:29,540 --> 01:11:33,890
>> És így, ha azt szeretné, hogy megy
ez az elem a következő elemre,

1487
01:11:33,890 --> 01:11:36,099
szó szerint, a
számítógép agya, csak adjunk hozzá egy.

1488
01:11:36,099 --> 01:11:39,140
Ha azt szeretnénk, hogy menjen a harmadik elem,
csak add one-- következő elem, csak

1489
01:11:39,140 --> 01:11:40,290
adjunk hozzá egy.

1490
01:11:40,290 --> 01:11:42,980
Azonban ez a verzió
A történet, tegyük fel,

1491
01:11:42,980 --> 01:11:46,080
A számítógép jelenleg keresi
vagy annak foglalkozó száma 100.

1492
01:11:46,080 --> 01:11:49,770
Hogyan juthat a következő
évfolyamon az évfolyam könyv?

1493
01:11:49,770 --> 01:11:52,560
>> Meg kell venni a hét
lépéseket, ami önkényes.

1494
01:11:52,560 --> 01:11:58,120
Ahhoz, hogy a következő, meg kell
Újabb nyolc lépés, hogy 15.

1495
01:11:58,120 --> 01:12:02,250
Más szóval, ez nem egy
állandó különbség a számok,

1496
01:12:02,250 --> 01:12:04,857
és így ez csak úgy
számítógép több időt a lényeg.

1497
01:12:04,857 --> 01:12:06,940
A számítógép keresni
a memóriában érdekében

1498
01:12:06,940 --> 01:12:08,990
hogy megtalálja, amit keres.

1499
01:12:08,990 --> 01:12:14,260
>> Tehát mivel a tömb kezd lenni
az adatok gyors structure-- mert

1500
01:12:14,260 --> 01:12:17,610
szó szerint csak nem egyszerű számtani
és kap, ha akar egy hozzáadásával,

1501
01:12:17,610 --> 01:12:21,300
A instance-- egy láncolt lista,
áldozatot, hogy a funkció.

1502
01:12:21,300 --> 01:12:24,020
Nem lehet csak menni az első
a második, harmadik és negyedik.

1503
01:12:24,020 --> 01:12:25,240
Meg kell, hogy kövesse a térképet.

1504
01:12:25,240 --> 01:12:28,160
Meg kell venni több lépést
hogy azokat az értékeket, amelyek

1505
01:12:28,160 --> 01:12:30,230
úgy tűnik, hogy egy inflációs.

1506
01:12:30,230 --> 01:12:35,910
Így fizetünk az ára, de mi volt
a jellemzője, hogy Dan keresett itt?

1507
01:12:35,910 --> 01:12:38,110
Mit csinál egy láncolt lista
látszólag lehetővé teszik számunkra, hogy nem,

1508
01:12:38,110 --> 01:12:40,240
ez volt az eredete
ebben a konkrét történetet?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Pontosan.

1511
01:12:43,830 --> 01:12:46,220
A dinamikus méretű hozzá.

1512
01:12:46,220 --> 01:12:48,040
Mi adhat ehhez a listához.

1513
01:12:48,040 --> 01:12:51,430
Mi is csökken a listán, így
hogy mi csak használ annyi memóriát

1514
01:12:51,430 --> 01:12:55,560
ahogy valójában akar, és így
soha nem vagyunk túl elosztásának.

1515
01:12:55,560 --> 01:12:58,470
>> Most csak az igazán NIT-válogatós,
van egy rejtett költség.

1516
01:12:58,470 --> 01:13:01,980
Szóval nem kell csak hadd meggyőzni
Ön, hogy ez egy meggyőző kompromisszum.

1517
01:13:01,980 --> 01:13:04,190
Van egy rejtett költség itt.

1518
01:13:04,190 --> 01:13:06,550
Az előny, hogy világos legyen,
hogy megkapjuk a dinamizmus.

1519
01:13:06,550 --> 01:13:10,359
Ha akarok egy másik elem, tudok csak
felhívni, és tedd egy szám van.

1520
01:13:10,359 --> 01:13:12,150
És aztán azt összekapcsolhatja
egy képet ide,

1521
01:13:12,150 --> 01:13:14,970
mivel ide, újra, ha én már
festett magam a sarokba,

1522
01:13:14,970 --> 01:13:19,410
Ha valami más már használja
a memória itt, én meg a szerencse.

1523
01:13:19,410 --> 01:13:21,700
Már festett magam a sarokban.

1524
01:13:21,700 --> 01:13:24,390
>> De mi a rejtett
költség ezen a képen?

1525
01:13:24,390 --> 01:13:27,690
Ez nem csak az összeg
Az hogy mennyi ideig tart

1526
01:13:27,690 --> 01:13:29,870
menni innen van,
amely hét lépésben, majd

1527
01:13:29,870 --> 01:13:32,820
nyolc lépés, ami több, mint egy.

1528
01:13:32,820 --> 01:13:34,830
Mi egy rejtett költség?

1529
01:13:34,830 --> 01:13:35,440
Nem csak időben.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
További információ
eléréséhez szükséges ezt a képet.

1532
01:13:49,940 --> 01:13:53,210
>> Ja, hogy a térképen, azok a kis darabka
papír, ahogy én is leírja őket.

1533
01:13:53,210 --> 01:13:55,650
Ezek arrows-- azokat nem szabad.

1534
01:13:55,650 --> 01:13:57,660
A computer-- tudja
amit egy számítógép.

1535
01:13:57,660 --> 01:13:58,790
Meg nullák.

1536
01:13:58,790 --> 01:14:03,170
Ha azt szeretnénk, hogy képviselje a nyíl, vagy egy
térkép vagy egy számot, akkor kell egy kis memóriát.

1537
01:14:03,170 --> 01:14:05,950
Így a többi árat
fizetni egy láncolt lista,

1538
01:14:05,950 --> 01:14:09,070
közös számítástechnika
forrás, szintén helyet.

1539
01:14:09,070 --> 01:14:11,710
>> És valóban így van, így általában,
között a kompromisszumok

1540
01:14:11,710 --> 01:14:15,580
tervezése szoftverfejlesztés
rendszerek időt és space--

1541
01:14:15,580 --> 01:14:18,596
kettő a hozzávalókat, két
a legköltségesebb összetevőket.

1542
01:14:18,596 --> 01:14:21,220
Ez olcsóbb több időt
mert van, hogy kövesse ezt a térképet,

1543
01:14:21,220 --> 01:14:25,730
de ez is olcsóbb nekem több helyet
mert meg kell tartani ezt a térképet körül.

1544
01:14:25,730 --> 01:14:28,730
Így a remény, ahogy azt már a fajta
megbeszéltük tegnap és ma,

1545
01:14:28,730 --> 01:14:31,720
az, hogy az előnyök
meghaladják a költségeket.

1546
01:14:31,720 --> 01:14:33,870
>> De nincs egyértelmű megoldást.

1547
01:14:33,870 --> 01:14:35,870
Lehet, hogy ez better--
a la gyors és piszkos,

1548
01:14:35,870 --> 01:14:38,660
mint Kareem javasolt earlier--
hogy dobja memória a problémát.

1549
01:14:38,660 --> 01:14:42,520
Csak vásárolni több memóriát, gondolom kevesebb
nehéz erről a probléma megoldásának,

1550
01:14:42,520 --> 01:14:44,595
és megoldani, hogy egy könnyebb út.

1551
01:14:44,595 --> 01:14:46,720
És valóban korábban, amikor
beszéltünk kompromisszumokat,

1552
01:14:46,720 --> 01:14:49,190
nem volt hely
a számítógép és az időt.

1553
01:14:49,190 --> 01:14:51,810
Ez volt fejlesztő idő, ami
még egy másik forrás.

1554
01:14:51,810 --> 01:14:54,829
>> Tehát újra, ez Mindezeket mérlegelve
próbálta eldönteni, hogy melyek azok a dolgok,

1555
01:14:54,829 --> 01:14:55,870
vagy hajlandó költeni?

1556
01:14:55,870 --> 01:14:57,380
Melyik a legolcsóbb?

1557
01:14:57,380 --> 01:15:01,040
Amelynek eredményeként a jobb eredményeket?

1558
01:15:01,040 --> 01:15:01,540
Igen?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Valóban.

1561
01:15:12,580 --> 01:15:15,970
Ebben az esetben, ha
képviselő számok a maps--

1562
01:15:15,970 --> 01:15:18,820
ezek az úgynevezett több nyelven
"Útmutatását" vagy "címeket" -

1563
01:15:18,820 --> 01:15:20,390
ez kétszerese a teret.

1564
01:15:20,390 --> 01:15:24,390
Hogy nem kell olyan rossz, mint a kettős, ha
Most mi csak számok tárolása.

1565
01:15:24,390 --> 01:15:27,410
Tegyük fel, hogy mi volt tárolása
beteg nyilvántartás egy hospital--

1566
01:15:27,410 --> 01:15:30,870
így Pierson nevek, telefonszámok,
társadalombiztosítási számokat, orvos

1567
01:15:30,870 --> 01:15:31,540
történelem.

1568
01:15:31,540 --> 01:15:34,160
Ez a doboz lehet sok,
sokkal nagyobb, amely esetben

1569
01:15:34,160 --> 01:15:38,000
Egy apró kis mutató, a címe
A következő element-- ez nem egy nagy ügy.

1570
01:15:38,000 --> 01:15:40,620
Ez egy ilyen béren kívüli
költség nem számít.

1571
01:15:40,620 --> 01:15:43,210
De ebben az esetben, igen, ez megduplázását.

1572
01:15:43,210 --> 01:15:45,290
Jó kérdés.

1573
01:15:45,290 --> 01:15:47,900
>> Beszéljünk alkalommal
kicsit konkrétabban.

1574
01:15:47,900 --> 01:15:50,380
Mi a futási idő
A keresést a listában?

1575
01:15:50,380 --> 01:15:53,640
Tegyük fel akartam keresni
végig a diákok évfolyamon,

1576
01:15:53,640 --> 01:15:55,980
és van n fokozat
ebben adatszerkezet.

1577
01:15:55,980 --> 01:15:58,830
Itt is tudunk kölcsönözni
a szókincs korábban.

1578
01:15:58,830 --> 01:16:00,890
Ez egy lineáris adatszerkezet.

1579
01:16:00,890 --> 01:16:04,570
>> Big O n mi szükséges ahhoz, hogy
a végén ez a adatstruktúra,

1580
01:16:04,570 --> 01:16:08,410
whereas-- és nem láttunk
ez before-- tömb ad

1581
01:16:08,410 --> 01:16:13,555
az úgynevezett konstans idő, ami azt jelenti,
egy lépésben vagy két lépésben, vagy 10 steps--

1582
01:16:13,555 --> 01:16:14,180
nem számít.

1583
01:16:14,180 --> 01:16:15,440
Ez egy fix szám.

1584
01:16:15,440 --> 01:16:17,440
Ennek semmi köze a
a méret a tömb.

1585
01:16:17,440 --> 01:16:20,130
És az oka, hogy a
megint, véletlenszerű hozzáférés.

1586
01:16:20,130 --> 01:16:23,180
A számítógép csak közvetlenül a
ugrás egy másik helyre,

1587
01:16:23,180 --> 01:16:27,770
mert ők mind egyformák
távolság minden mást.

1588
01:16:27,770 --> 01:16:29,112
Nincs gondolkodás szó.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Rendben.

1591
01:16:32,400 --> 01:16:39,230
Tehát, ha tudok, hadd próbálja
festék két utolsó kép.

1592
01:16:39,230 --> 01:16:42,830
Egy nagyon gyakori az úgynevezett hash tábla.

1593
01:16:42,830 --> 01:16:51,120
Tehát, hogy motiválja ezt a vitát,
hadd gondoljon, hogyan kell ezt csinálni.

1594
01:16:51,120 --> 01:16:52,610
>> Szóval mi a helyzet ez?

1595
01:16:52,610 --> 01:16:55,160
Tegyük fel, hogy a probléma
akarjuk megoldani most

1596
01:16:55,160 --> 01:16:58,360
hajt végre egy dictionary--
így egy csomó angol szavak

1597
01:16:58,360 --> 01:16:59,330
vagy mindegy.

1598
01:16:59,330 --> 01:17:02,724
És a cél az, hogy képes legyen válaszolni
kérdések formájában ez a szó?

1599
01:17:02,724 --> 01:17:04,640
Tehát azt szeretnénk, hogy végre
a helyesírás-ellenőrző, csak

1600
01:17:04,640 --> 01:17:07,220
mint egy fizikai szótár
hogy meg lehet keresni dolgokat az.

1601
01:17:07,220 --> 01:17:10,490
Tegyük fel, hogy én is ezt a tömböt.

1602
01:17:10,490 --> 01:17:12,590
Tehettem ezt.

1603
01:17:12,590 --> 01:17:20,756
>> És tegyük fel, a szavak alma
és a banán és a sárgadinnye.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
És nem tudok gondolni gyümölcsök
kezdődő d, úgyhogy mi csak

1606
01:17:26,465 --> 01:17:27,590
megy, hogy három gyümölcsöt.

1607
01:17:27,590 --> 01:17:31,510
Tehát ez egy tömb, és mi vagyunk
tárolására ezeket a szavakat

1608
01:17:31,510 --> 01:17:34,200
ebben a szótárban, mint egy tömb.

1609
01:17:34,200 --> 01:17:39,350
A kérdés tehát az, hogy mást
lehet tárolni az adatokat?

1610
01:17:39,350 --> 01:17:43,160
>> Nos, én vagyok a fajta csalás itt, mert
mindegyik betűket

1611
01:17:43,160 --> 01:17:44,490
valóban egyedi bájt.

1612
01:17:44,490 --> 01:17:46,740
Tehát, ha nagyon akartam lenni
nit-válogatós, én tényleg

1613
01:17:46,740 --> 01:17:49,600
lehet osztani ezt fel sok
kisebb darabokat memória,

1614
01:17:49,600 --> 01:17:51,289
és tudnánk csinálni, hogy pontosan.

1615
01:17:51,289 --> 01:17:53,580
De megyünk befut
ugyanaz a probléma, mint korábban.

1616
01:17:53,580 --> 01:17:56,674
Mi van, ha a Merriam Webster vagy Oxford
nem minden year-- hozzáteszik szavak

1617
01:17:56,674 --> 01:17:59,340
A dictionary-- mi nem
feltétlenül akar festeni magunkat

1618
01:17:59,340 --> 01:18:00,780
az egyik sarokban egy sor?

1619
01:18:00,780 --> 01:18:05,710
>> Tehát ahelyett, talán okosabb megközelítés
az, hogy az Apple a saját csomópont vagy doboz,

1620
01:18:05,710 --> 01:18:11,190
ahogy mi mondjuk, banán, és
akkor itt van sárgadinnye.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
És mi húr ezeket a dolgokat együtt.

1623
01:18:16,790 --> 01:18:19,980
Tehát ez a tömb, és
ez a láncolt lista.

1624
01:18:19,980 --> 01:18:23,300
Ha nem egészen értem, ez csak
azt mondja: "array", és ez azt mondja: "listát."

1625
01:18:23,300 --> 01:18:25,780
>> Tehát ugyanaz
pontos kérdések, mint korábban,

1626
01:18:25,780 --> 01:18:28,600
amellyel most már van
dinamizmusa a láncolt lista.

1627
01:18:28,600 --> 01:18:31,090
De van egy viszonylag lassú szótárban.

1628
01:18:31,090 --> 01:18:32,870
Tegyük fel, hogy meg akarom nézni egy szót sem.

1629
01:18:32,870 --> 01:18:35,430
Lehet, hogy nekem nagy O n
lépéseket, mert a szó esetleg

1630
01:18:35,430 --> 01:18:37,840
lennie egészen a végén
A lista, mint a sárgadinnye.

1631
01:18:37,840 --> 01:18:40,600
És kiderül, hogy
programozás, sort

1632
01:18:40,600 --> 01:18:42,700
A szent grál adatok
szerkezetek, valami

1633
01:18:42,700 --> 01:18:46,620
hogy ad állandó
idő, mint egy tömb

1634
01:18:46,620 --> 01:18:50,870
de még mindig ad dinamikát.

1635
01:18:50,870 --> 01:18:52,940
>> Így tudjuk a legjobb mindkét világból?

1636
01:18:52,940 --> 01:18:55,570
És valóban, van valami
az úgynevezett hash tábla

1637
01:18:55,570 --> 01:18:59,320
amely lehetővé teszi, hogy pontosan
hogy, bár kb.

1638
01:18:59,320 --> 01:19:03,140
A hash tábla egy szakértő
adatszerkezet, hogy mi

1639
01:19:03,140 --> 01:19:06,340
lehet gondolni, mint a
kombinációja egy array--

1640
01:19:06,340 --> 01:19:12,390
és fogok rajzolni
Így-- és láncolt listák

1641
01:19:12,390 --> 01:19:17,310
hogy fogom felhívni, mint ez itt.

1642
01:19:17,310 --> 01:19:19,760
>> És ahogy ez a dolog
művek a következő.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Ha ez now-- hash table--
az én harmadik adatstruktúra

1645
01:19:29,540 --> 01:19:32,590
és szeretnék tárolni
szóval ebben, én nem

1646
01:19:32,590 --> 01:19:35,440
szeretnénk, hogy csak tárolja az összes a
szavak háttal háttal.

1647
01:19:35,440 --> 01:19:37,430
Azt akarom, hogy kihasználja néhány
darab információ

1648
01:19:37,430 --> 01:19:40,330
a szó, amely segítségével
térjek meg, ahol ez gyorsabb.

1649
01:19:40,330 --> 01:19:43,666
>> Tehát adott szava alma
és a banán és a sárgadinnye,

1650
01:19:43,666 --> 01:19:45,040
Szándékosan választottam ezeket a szavakat.

1651
01:19:45,040 --> 01:19:45,340
Miért?

1652
01:19:45,340 --> 01:19:47,631
Mi a fajta alapvetően
különbözik a három?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Mi a nyilvánvaló?

1655
01:19:51,484 --> 01:19:52,900
Kezdik a különböző betűk.

1656
01:19:52,900 --> 01:19:53,900
>> Szóval tudod mit?

1657
01:19:53,900 --> 01:19:57,120
Ahelyett, hogy minden az én beszédeimet
ugyanazt a vödröt, hogy úgy mondjam,

1658
01:19:57,120 --> 01:20:00,390
mint egy nagy listát, hogy miért nem
Azt legalább próbálni az optimalizálást

1659
01:20:00,390 --> 01:20:04,180
és hogy az én listák 26/01 mindaddig.

1660
01:20:04,180 --> 01:20:07,440
A kényszerítő optimalizálás
Lehet, hogy miért nem

1661
01:20:07,440 --> 01:20:10,650
Én-- behelyezésekor egy szó
ebbe adatstruktúra,

1662
01:20:10,650 --> 01:20:14,300
a számítógép memóriájában, hogy miért
Nem tettem a 'a' szó van,

1663
01:20:14,300 --> 01:20:17,270
az összes "b" szó itt,
és az összes "C" szó itt?

1664
01:20:17,270 --> 01:20:24,610
Tehát ez végül véget alma
Itt, banán van, sárgadinnye itt,

1665
01:20:24,610 --> 01:20:25,730
és így tovább.

1666
01:20:25,730 --> 01:20:31,700
>> És ha van egy további
szó, így: mi a másik?

1667
01:20:31,700 --> 01:20:36,640
Alma, banán, körte.

1668
01:20:36,640 --> 01:20:39,370
Bárki úgy gondolja, a gyümölcs
hogy kezdődik a, b vagy c?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- tökéletes.

1670
01:20:40,570 --> 01:20:43,990
Hogy megy, hogy kerül ide.

1671
01:20:43,990 --> 01:20:47,530
És így úgy tűnik, hogy van egy
marginálisan jobb megoldás,

1672
01:20:47,530 --> 01:20:50,820
mert most, ha akarom
keresni alma, I

1673
01:20:50,820 --> 01:20:53,200
first-- én nem csak búvár
az én adatszerkezet.

1674
01:20:53,200 --> 01:20:54,850
Nem belevetik magukat a számítógép memóriájában.

1675
01:20:54,850 --> 01:20:56,530
Először nézd meg az első levelet.

1676
01:20:56,530 --> 01:20:58,610
>> És ez az, amit egy számítógépes
tudós mondaná.

1677
01:20:58,610 --> 01:21:00,760
Te hash be adatszerkezet.

1678
01:21:00,760 --> 01:21:04,100
Veszel a bemenet, amely
Ebben az esetben van szó, mint az Apple.

1679
01:21:04,100 --> 01:21:07,150
Te elemezni, nézi
az első levél Ebben az esetben,

1680
01:21:07,150 --> 01:21:08,340
ezáltal hash értékének azt.

1681
01:21:08,340 --> 01:21:10,950
Hash egy általános kifejezés, amely szerint
veszel valamit bemenet

1682
01:21:10,950 --> 01:21:12,116
és készítsen egy kimenetet.

1683
01:21:12,116 --> 01:21:15,090
És a kimeneti, hogy
esetében az a hely,

1684
01:21:15,090 --> 01:21:18,150
szeretne keresni, az első
helyen, második helyen, a harmadik.

1685
01:21:18,150 --> 01:21:22,160
Tehát a bemenet alma,
a kimenet az első.

1686
01:21:22,160 --> 01:21:25,054
A bemenet banán, a
kimenet legyen a második.

1687
01:21:25,054 --> 01:21:27,220
A bemenet sárgadinnye,
az eredmény a harmadik.

1688
01:21:27,220 --> 01:21:30,320
A bemenet áfonya, a
kimenet ismét második.

1689
01:21:30,320 --> 01:21:34,010
És ez az, ami segít szedése
hivatkozások révén a memória

1690
01:21:34,010 --> 01:21:39,050
annak érdekében, hogy a szavak
vagy az adatok hatékonyabb.

1691
01:21:39,050 --> 01:21:43,330
>> Most ez lecsökkenti korunk potenciálisan
nem kevesebb, mint egy 26-ból,

1692
01:21:43,330 --> 01:21:45,850
mert ha feltételezzük, hogy
annyi "a" szót a "z"

1693
01:21:45,850 --> 01:21:48,080
szavak, mint a "q" szavakat, amelyek
nem igazán realistic--

1694
01:21:48,080 --> 01:21:50,830
mész, hogy ferdeség szerte
egyes betűket az alphabet--

1695
01:21:50,830 --> 01:21:53,204
de ez lenne egy inkrementális
megközelítés, amely nem teszi lehetővé

1696
01:21:53,204 --> 01:21:55,930
teszi, hogy a szavak sokkal gyorsabban.

1697
01:21:55,930 --> 01:21:59,660
És a valóságban, kifinomult
program, a Googles a világ

1698
01:21:59,660 --> 01:22:02,180
A Facebooks a world--
akkor használja a hash tábla

1699
01:22:02,180 --> 01:22:03,740
A sok különböző célra.

1700
01:22:03,740 --> 01:22:06,590
De nem lenne olyan naiv,
csak nézd meg az első betű

1701
01:22:06,590 --> 01:22:09,700
alma vagy banán vagy
körte vagy a sárgadinnye,

1702
01:22:09,700 --> 01:22:13,420
mert mint látható, ezek a
jegyzékek még mindig hosszú.

1703
01:22:13,420 --> 01:22:17,130
>> És így ez talán még a fajta
A linear-- így egyfajta lassú,

1704
01:22:17,130 --> 01:22:19,980
mint a nagy O n
hogy a korábban tárgyalt.

1705
01:22:19,980 --> 01:22:25,290
Tehát mi egy igazi jó hash tábla
do-- ez lesz egy sokkal nagyobb tömb.

1706
01:22:25,290 --> 01:22:28,574
És akkor használja a sokkal
kifinomult tördelési funkció,

1707
01:22:28,574 --> 01:22:30,240
úgy, hogy ne csak nézd meg az "a".

1708
01:22:30,240 --> 01:22:35,480
Lehet, hogy úgy néz ki, "egy-p-p-l-e", és
valahogy átalakítja azokat öt betű

1709
01:22:35,480 --> 01:22:38,400
a hely, ahol
alma kell tárolni.

1710
01:22:38,400 --> 01:22:42,660
Mi csak naivan az "a" betűt
egyedül, mert szép és egyszerű.

1711
01:22:42,660 --> 01:22:44,600
>> De egy hash tábla, a
A végén, akkor úgy gondolja,

1712
01:22:44,600 --> 01:22:47,270
AS kombinációja
egy sor, amelyek mindegyike

1713
01:22:47,270 --> 01:22:51,700
egy láncolt lista, hogy ideális esetben
legrövidebbnek kell lennie, amennyire csak lehetséges.

1714
01:22:51,700 --> 01:22:54,364
És ez nem kézenfekvő megoldás.

1715
01:22:54,364 --> 01:22:57,280
Tény, hogy sok a finomhangolás
hogy megy a motorháztető alatt, amikor

1716
01:22:57,280 --> 01:22:59,654
alkalmaz hasonló
kifinomult adatstruktúrák

1717
01:22:59,654 --> 01:23:01,640
az, ami a helyes
hossza a tömb?

1718
01:23:01,640 --> 01:23:03,250
Mi a helyes hash függvény?

1719
01:23:03,250 --> 01:23:04,830
Hogyan dolgok tárolására a memóriában?

1720
01:23:04,830 --> 01:23:07,249
>> De hogy milyen gyorsan
ez a fajta vita

1721
01:23:07,249 --> 01:23:10,540
eszkalálódott, sem eddig, hogy ez a fajta
A több mint egy feje ezen a ponton, ami

1722
01:23:10,540 --> 01:23:11,360
rendben van.

1723
01:23:11,360 --> 01:23:18,820
De elkezdtük, visszahívás, az igazán
valami alacsony szintű és elektronikus.

1724
01:23:18,820 --> 01:23:20,819
És így ez megint ez a
téma az absztrakció,

1725
01:23:20,819 --> 01:23:23,610
ahol ha egyszer elkezd magától
nyújtott, OK, megvan it-- van

1726
01:23:23,610 --> 01:23:26,680
fizikai memóriát, OK, megvan, minden
fizikai helyét egy cím,

1727
01:23:26,680 --> 01:23:29,910
OK, megvan, azt is képviseli
ezeket a címeket a arrows--

1728
01:23:29,910 --> 01:23:34,650
akkor nagyon gyorsan elindul, hogy
kifinomultabb beszélgetések

1729
01:23:34,650 --> 01:23:38,360
a végén úgy tűnik, hogy lehetővé teszi számunkra,
problémák megoldására, mint a kereső

1730
01:23:38,360 --> 01:23:41,620
és válogatás hatékonyabban.

1731
01:23:41,620 --> 01:23:44,190
És biztos lehetsz benne, too--
mert azt hiszem, ez

1732
01:23:44,190 --> 01:23:48,700
a legmélyebb mentünk a néhány
Ezen CS témák proper-- voltunk

1733
01:23:48,700 --> 01:23:51,880
tenni egy nap és fél ebben a
pont, amit tipikusan úgy csinálni felett

1734
01:23:51,880 --> 01:23:55,520
során nyolc hétig félévben.

1735
01:23:55,520 --> 01:23:59,670
>> Bármilyen kérdése van ilyen?

1736
01:23:59,670 --> 01:24:01,100
Nem?

1737
01:24:01,100 --> 01:24:01,940
Rendben.

1738
01:24:01,940 --> 01:24:05,610
Nos, miért nem szünet van,
indul ebéd néhány perccel korábban,

1739
01:24:05,610 --> 01:24:07,052
folytatódik, csak körülbelül egy óra?

1740
01:24:07,052 --> 01:24:08,760
És én időzzön
egy kicsit a kérdések.

1741
01:24:08,760 --> 01:24:11,343
Akkor fogok menni
egy pár hívásokat, ha nem gond.

1742
01:24:11,343 --> 01:24:15,000
Majd kapcsolja be egy kis zenét az időközben
de az ebéd legyen a sarkon.

1743
01:24:15,000 --> 01:24:17,862