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

2
00:00:00,030 --> 00:00:00,460
>> DAVID Malan: U redu.

3
00:00:00,460 --> 00:00:01,094
Vratili smo se.

4
00:00:01,094 --> 00:00:04,260
Tako je u ovom segmentu o programiranju ono
Mislio sam da ćemo učiniti je mješavina stvari.

5
00:00:04,260 --> 00:00:06,340
Jedan od njih, napraviti malo
nešto hands-on,

6
00:00:06,340 --> 00:00:08,690
iako korištenjem više razigran
programiranje environment--

7
00:00:08,690 --> 00:00:11,620
onaj koji je demonstrativno od
upravo one vrste ideja

8
00:00:11,620 --> 00:00:14,220
smo se govori o,
ali malo više formalno.

9
00:00:14,220 --> 00:00:18,200
Dva, pogled na neke od
više tehničkih načina

10
00:00:18,200 --> 00:00:21,520
da programer će zapravo riješiti
problemi kao što je traženje problema

11
00:00:21,520 --> 00:00:24,530
da smo pogledali prije i
i važnije

12
00:00:24,530 --> 00:00:26,020
Zanimljivo problem sortiranja.

13
00:00:26,020 --> 00:00:28,840
>> Mi smo samo pretpostaviti iz dobiti ići
da je taj telefonski imenik je riješeno,

14
00:00:28,840 --> 00:00:31,980
ali to samo po sebi zapravo neka vrsta
Teško je problem s mnogo različitih načina

15
00:00:31,980 --> 00:00:32,479
to riješiti.

16
00:00:32,479 --> 00:00:34,366
Dakle, mi ćemo koristiti ih kao
klasa problema

17
00:00:34,366 --> 00:00:36,740
Predstavnik stvari koje
mogla biti riješena u cjelini.

18
00:00:36,740 --> 00:00:38,980
A onda ćemo razgovarati
o u nekim detaljima što

19
00:00:38,980 --> 00:00:42,360
nazivaju podatke structures--
ljubitelj načine kao povezane liste

20
00:00:42,360 --> 00:00:46,290
i hash tablica i drveća koje
programer bi zapravo

21
00:00:46,290 --> 00:00:48,890
upotrebu i uglavnom koriste
na ploči slikati

22
00:00:48,890 --> 00:00:51,840
slika ono što on ili ona
predviđena za provedbu

23
00:00:51,840 --> 00:00:52,980
neki komad softvera.

24
00:00:52,980 --> 00:00:55,130
>> Tako ćemo učiniti ruke na dio prvi.

25
00:00:55,130 --> 00:01:00,090
Dakle, samo dobiti vaše ruke prljave s
okoliš nazivaju scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
To je alat koji koristimo
u našem preddiplomskog klasi.

27
00:01:02,636 --> 00:01:04,510
Iako je dizajniran
za mlađe od 12 i više godina,

28
00:01:04,510 --> 00:01:07,570
ćemo ga koristiti za gore
dio tog vrlo malo

29
00:01:07,570 --> 00:01:10,020
budući da je lijepa, zabavna
grafički način učenja

30
00:01:10,020 --> 00:01:12,160
Malo nešto o programiranju.

31
00:01:12,160 --> 00:01:17,600
Pa glavu na tom URL-u, gdje vas
treba vidjeti stranicu baš tako,

32
00:01:17,600 --> 00:01:23,330
i ići naprijed i kliknite
Pridružite Scratch u gornjem desnom kutu

33
00:01:23,330 --> 00:01:28,300
i odabrati korisničko ime i
lozinka i na kraju sami doći

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

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

36
00:01:32,165 --> 00:01:34,665
Mislio sam da ću koristiti kao
prilika prvi pokazati ovo.

37
00:01:34,665 --> 00:01:39,120
Pitanje je došao za vrijeme pauze
o tome što je broj zapravo izgleda.

38
00:01:39,120 --> 00:01:41,315
I razgovarali smo
tijekom pauze o C,

39
00:01:41,315 --> 00:01:45,060
u particular-- osobito
Niža razina u starijoj jeziku.

40
00:01:45,060 --> 00:01:47,750
A ja samo na brzinu
Google pretraživanje kako bi pronašli C koda

41
00:01:47,750 --> 00:01:51,574
za binarno pretraživanje, algoritam koji smo
koristiti za pretraživanje taj telefonski imenik ranije.

42
00:01:51,574 --> 00:01:54,240
Ovaj primjer, naravno,
ne traži telefonskog imenika.

43
00:01:54,240 --> 00:01:57,840
To samo traži hrpu
Brojevi u memoriju racunala.

44
00:01:57,840 --> 00:02:01,000
Ali, ako želite samo dobiti vizualni
osjećaj što stvarni programiranje

45
00:02:01,000 --> 00:02:05,370
jezik izgleda, to izgleda
malo nešto ovako.

46
00:02:05,370 --> 00:02:09,759
Dakle, riječ je o 20-plus,
30-ak linija koda,

47
00:02:09,759 --> 00:02:12,640
ali razgovor smo
imali više od odmora

48
00:02:12,640 --> 00:02:16,000
je o tome kako je to zapravo
dobiva prerasla u nula i jedinica

49
00:02:16,000 --> 00:02:19,200
a ako ne može samo vratiti da
proces i idu od nula i jedinica

50
00:02:19,200 --> 00:02:20,210
natrag na kodu.

51
00:02:20,210 --> 00:02:22,620
>> Nažalost, proces
tako je transformativni

52
00:02:22,620 --> 00:02:24,890
da je puno lakše reći nego učiniti.

53
00:02:24,890 --> 00:02:29,400
JA je otišao naprijed i zapravo okrenuo
taj program, binarna pretrage,

54
00:02:29,400 --> 00:02:32,700
u nula i jedinica na način da se
Program pod nazivom prevodilac da sam

55
00:02:32,700 --> 00:02:34,400
dogoditi da su ovdje upravo na moj Mac.

56
00:02:34,400 --> 00:02:37,850
A ako pogledate na zaslonu
ovdje, posebno usredotočuje

57
00:02:37,850 --> 00:02:43,520
na ovim srednjim šest stupaca samo
vidjet ćete samo nula i jedinica.

58
00:02:43,520 --> 00:02:48,290
I oni su nula i jedinica koje
sastaviti točno da je u potrazi program.

59
00:02:48,290 --> 00:02:53,720
>> I tako svaki komad pet bitova,
svaki bajt nula i jedinica ovdje,

60
00:02:53,720 --> 00:02:57,310
predstavljaju neke upute
obično unutar jednog računala.

61
00:02:57,310 --> 00:03:00,730
A u stvari, ako ste čuli
Marketing slogan "Intel Inside" - da je,

62
00:03:00,730 --> 00:03:04,610
Naravno, samo znači da imate
Intel CPU ili mozga u unutrašnjosti računala.

63
00:03:04,610 --> 00:03:08,000
A što to znači biti CPU
da imate skup instrukcija,

64
00:03:08,000 --> 00:03:08,840
da se tako izrazim.

65
00:03:08,840 --> 00:03:11,620
>> Svaki procesor na svijetu, mnogi od
ih je napravio Intel ovih dana,

66
00:03:11,620 --> 00:03:13,690
razumije konačan
Broj uputa.

67
00:03:13,690 --> 00:03:18,690
A oni su upute tako niska razina
kao dodaj ta dva broja zajedno,

68
00:03:18,690 --> 00:03:22,560
pomnožiti ova dva broja zajedno,
premjestiti ovaj dio podataka odavde

69
00:03:22,560 --> 00:03:27,340
ovdje u memoriji, osim toga
Informacije odavde do ovdje u memoriji,

70
00:03:27,340 --> 00:03:32,200
i tako forth-- tako jako, jako
niske razine, gotovo elektronički detalje.

71
00:03:32,200 --> 00:03:34,780
Ali, s onima koji su matematički
operacije zajedno

72
00:03:34,780 --> 00:03:37,410
s onim što smo ranije,
predstavljanje podataka

73
00:03:37,410 --> 00:03:40,450
kao nula i jedinica, mogu
ste izgraditi sve

74
00:03:40,450 --> 00:03:44,180
koje računalo može učiniti danas, da li
to je tekstualni, grafički, glazbene,

75
00:03:44,180 --> 00:03:45,580
ili drugačije.

76
00:03:45,580 --> 00:03:49,450
>> Dakle, to je vrlo lako doći
izgubljen u korova brzo.

77
00:03:49,450 --> 00:03:52,150
I tu je puno
sintaktičke izazovi

78
00:03:52,150 --> 00:03:56,630
pri čemu ako bi najjednostavnije,
najgluplji pri upisu nitko od programa

79
00:03:56,630 --> 00:03:57,860
će raditi što god.

80
00:03:57,860 --> 00:04:00,366
I tako, umjesto pomoću
jezik kao što je C jutros,

81
00:04:00,366 --> 00:04:02,240
Mislio sam da će to biti
zabavnije stvari za napraviti

82
00:04:02,240 --> 00:04:04,840
nešto više vizualni, što
dok je dizajniran za djecu

83
00:04:04,840 --> 00:04:08,079
je zapravo savršena manifestacija
stvarnog programiranja

84
00:04:08,079 --> 00:04:10,370
language-- je slučajno
korištenje slika umjesto teksta

85
00:04:10,370 --> 00:04:11,710
da predstavlja one ideje.

86
00:04:11,710 --> 00:04:15,470
>> Dakle, nakon što doista imaju
računa o scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
kliknite gumb Stvori
u gornjem lijevom kutu stranice.

88
00:04:21,070 --> 00:04:24,620
A ti bi trebao vidjeti okruženje kao što je
onaj sam vidjet na mom ekranu

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

90
00:04:26,310 --> 00:04:29,350
A mi ćemo samo malo troše
malo vremena igrajući ovdje.

91
00:04:29,350 --> 00:04:34,080
Da vidimo, ako ne možemo sve riješiti neke
Problemi zajedno na sljedeći način.

92
00:04:34,080 --> 00:04:39,420
>> Dakle, ono što ćete vidjeti u ovo
environment-- i zapravo samo neka

93
00:04:39,420 --> 00:04:40,050
mi pauza.

94
00:04:40,050 --> 00:04:42,680
Je li netko nije ovdje?

95
00:04:42,680 --> 00:04:45,070
Ne ovdje?

96
00:04:45,070 --> 00:04:45,800
U REDU.

97
00:04:45,800 --> 00:04:49,030
Dakle, dopustite mi naglasiti neke
Karakteristike ovom okruženju.

98
00:04:49,030 --> 00:04:55,024
>> Dakle, u gornjem lijevom kutu zaslona, ​​mi
imaju nule pozornici, da tako kažemo.

99
00:04:55,024 --> 00:04:57,440
Scratch je ne samo naziv
ovog programskog jezika;

100
00:04:57,440 --> 00:05:00,356
to je ujedno i naziv mačka koja
vidiš po defaultu tamo u narančasto.

101
00:05:00,356 --> 00:05:02,160
On je na pozornici, tako
baš kao što sam opisao

102
00:05:02,160 --> 00:05:05,770
kornjača ranije kao u
pravokutna bijela okolina ploča.

103
00:05:05,770 --> 00:05:09,800
Ova mačka je svijet ograničen u cijelosti
na taj pravokutnik do vrha tamo.

104
00:05:09,800 --> 00:05:12,210
>> U međuvremenu, na desnoj
ruka strana ovdje, to je

105
00:05:12,210 --> 00:05:15,610
samo skripte područje,
prazna ploča, ako će.

106
00:05:15,610 --> 00:05:18,590
Ovo je mjesto gdje ćemo pisati
naši programi u samo jednom trenutku.

107
00:05:18,590 --> 00:05:22,935
I izgrađeni da ćemo
koristiti za pisanje ovog program-- zagonetku

108
00:05:22,935 --> 00:05:25,310
komada, ako will-- su
oni ovdje u sredini,

109
00:05:25,310 --> 00:05:27,500
i oni su kategorizirane
po funkcionalnosti.

110
00:05:27,500 --> 00:05:31,000
Tako, na primjer, ja ću ići naprijed
i pokazuju barem jednu od ovih.

111
00:05:31,000 --> 00:05:33,690
Ja ću ići naprijed i kliknite
kategorija Kontrola do vrha.

112
00:05:33,690 --> 00:05:35,720
>> Dakle, to su kategorije do vrha.

113
00:05:35,720 --> 00:05:39,410
Idem kliknite kategoriju upravljanje.

114
00:05:39,410 --> 00:05:44,020
Umjesto toga, ja ću kliknuti na događaje
kategorija, prvi jednog do vrha.

115
00:05:44,020 --> 00:05:47,790
A ako želite slijediti čak
kao što smo to učinili, vi ste sasvim dobrodošli.

116
00:05:47,790 --> 00:05:52,180
Idem kliknite i povucite ovo
Prvi, "kad zelena zastava kliknuli".

117
00:05:52,180 --> 00:05:58,410
A onda ću ga odvesti samo
otprilike na vrhu mojih praznih lista.

118
00:05:58,410 --> 00:06:01,450
>> A što je lijepo o ispočetka
je da je ova zagonetka komad, kad

119
00:06:01,450 --> 00:06:04,560
isprepleteni s drugim slagalice
komada, će učiniti doslovno

120
00:06:04,560 --> 00:06:06,460
što one slagalice kažu učiniti.

121
00:06:06,460 --> 00:06:09,710
Tako, na primjer, ispočetka je u pravu
sada usred njegovog svijeta.

122
00:06:09,710 --> 00:06:14,660
Ja ću ići naprijed i birati
Sada, recimo, u kategoriji Motion,

123
00:06:14,660 --> 00:06:18,000
ako želite da učine
same-- kategoriju Motion.

124
00:06:18,000 --> 00:06:20,430
A sada primijetiti imam jednu cjelinu
hrpa slagalice ovdje

125
00:06:20,430 --> 00:06:23,370
da, opet, vrsta učiniti ono što oni kažu.

126
00:06:23,370 --> 00:06:28,110
I ja ću ići naprijed i povući i
ispustiti potez blok u pravu ovdje.

127
00:06:28,110 --> 00:06:31,860
>> I primjetite da čim ste dobili
blizu dna "zelene zastave

128
00:06:31,860 --> 00:06:34,580
kliknuo "gumb, obavijest
kako izgleda bijela linija,

129
00:06:34,580 --> 00:06:36,950
kao da je to gotovo
magnetska, on želi ići tamo.

130
00:06:36,950 --> 00:06:43,070
Samo neka idu, i to će puknuti
zajedno i oblici će odgovarati.

131
00:06:43,070 --> 00:06:46,620
A sada možete možda gotovo
pogodite gdje ćemo s ovim.

132
00:06:46,620 --> 00:06:51,570
>> Ako pogledate nule fazi
ovdje i gledati na vrhu,

133
00:06:51,570 --> 00:06:55,142
vidjet ćete crvenu svjetlost,
znak stop, i zelenu zastavu.

134
00:06:55,142 --> 00:06:57,100
I ja ću ići naprijed
i gledati screen--

135
00:06:57,100 --> 00:06:58,460
samo na trenutak, ako može.

136
00:06:58,460 --> 00:07:01,960
Idem kliknite
Zelena zastava upravo sada,

137
00:07:01,960 --> 00:07:07,850
i on se ono što se čini 10 koraka
ili 10 piksela, 10 točkice na zaslonu.

138
00:07:07,850 --> 00:07:13,390
>> I tako ne da je uzbudljivo,
ali neka mi predloži

139
00:07:13,390 --> 00:07:17,440
čak i bez poučavanja to, samo
koristeći svoj vlastiti intuition-- neka

140
00:07:17,440 --> 00:07:22,560
ja predlažem da si shvatiti kako
čine Blok Hodajte s pozornice.

141
00:07:22,560 --> 00:07:28,700
Jeste ga se napravilo mjesta za desnu stranu
ekran, sve do desne strane.

142
00:07:28,700 --> 00:07:32,200
Dopustite mi da vam dati trenutak
ili tako boriti s tim.

143
00:07:32,200 --> 00:07:37,681
Možda želite pogledati
na druge kategorije blokova.

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

145
00:07:38,180 --> 00:07:41,290
Samo da ponovimo, kada smo
zelena zastava klik ovdje

146
00:07:41,290 --> 00:07:44,850
i premjestiti 10 koraka je
samo pouku, svaki put kad

147
00:07:44,850 --> 00:07:46,720
kliknite zelenu zastavu, što se događa?

148
00:07:46,720 --> 00:07:50,070
Pa, to je trčanje moj program.

149
00:07:50,070 --> 00:07:52,450
Tako sam mogao učiniti
možda 10 puta ručno,

150
00:07:52,450 --> 00:07:55,130
ali to se osjeća malo
malo hackish, da tako kažemo,

151
00:07:55,130 --> 00:07:57,480
pri čemu nisam stvarno
rješavanju problema.

152
00:07:57,480 --> 00:08:00,530
Ja sam samo jednom pokušava i
opet i opet i opet

153
00:08:00,530 --> 00:08:03,180
dok sam nekako slučajno
postigla direktive

154
00:08:03,180 --> 00:08:05,560
da sam krenuo u postizanju ranije.

155
00:08:05,560 --> 00:08:08,200
>> Ali mi znamo iz naših
pseudokod ranije da postoji

156
00:08:08,200 --> 00:08:11,870
Taj pojam je u programiranju petlje,
radi nešto opet i opet.

157
00:08:11,870 --> 00:08:14,888
I tako sam vidio da je hrpa vas
posegnuo je za ono puzzle komada?

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

159
00:08:17,870 --> 00:08:18,730
Ponavljaj do.

160
00:08:18,730 --> 00:08:21,400
Tako smo mogli učiniti nešto
kao i ponovite sve dok.

161
00:08:21,400 --> 00:08:23,760
I što si ponavljati sve dok se točno?

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

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

164
00:08:28,540 --> 00:08:31,974
I pusti me jednima
nešto jednostavnije samo na trenutak.

165
00:08:31,974 --> 00:08:33,140
Dopustite mi ići naprijed i učiniti.

166
00:08:33,140 --> 00:08:35,559
Uočite da, kao što svibanj imati
Otkrio pod kontrolom,

167
00:08:35,559 --> 00:08:38,409
nalazi se ova ponavljanja bloka, koji
ne izgleda kao da je to velika.

168
00:08:38,409 --> 00:08:41,039
Nema puno mjesta u
između ta dva žuta linija.

169
00:08:41,039 --> 00:08:43,539
Ali, kao što neki od vas možda ima
primijetio, ako povučete i ispustite,

170
00:08:43,539 --> 00:08:45,150
primijetiti kako ona raste popuniti oblik.

171
00:08:45,150 --> 00:08:46,274
>> A čak možete strpati više.

172
00:08:46,274 --> 00:08:48,670
To će zadržati samo raste ako
povucite i lebdjeti nad njom.

173
00:08:48,670 --> 00:08:51,110
A ja ne znam što je
najbolje ovdje, pa neka

174
00:08:51,110 --> 00:08:54,760
mi barem ponavljati pet puta, na
instanca, a zatim se vratiti na pozornicu

175
00:08:54,760 --> 00:08:56,720
i kliknite na zelenu zastavu.

176
00:08:56,720 --> 00:08:59,110
I sad primijetiti da nije dosta tamo.

177
00:08:59,110 --> 00:09:02,400
>> Sada neki od vas predložio, kao
Victoria jednostavno nije, ponovite 10 puta.

178
00:09:02,400 --> 00:09:05,140
I to uglavnom ne
dobiti ga skroz,

179
00:09:05,140 --> 00:09:10,510
ali ne bi li biti robusniji
način nego samovoljno figuring out

180
00:09:10,510 --> 00:09:12,640
koliko poteza napraviti?

181
00:09:12,640 --> 00:09:17,680
Što bi moglo biti bolje blok
nego ponoviti 10 puta biti?

182
00:09:17,680 --> 00:09:20,380
>> Da, pa zašto ne učiniti nešto zauvijek?

183
00:09:20,380 --> 00:09:24,390
I sad neka mi premjestiti ovaj dio slagalice
unutra i riješi se ove.

184
00:09:24,390 --> 00:09:28,300
Sada primjetiti Bez obzira gdje ispočetka
počne, on ide do ruba.

185
00:09:28,300 --> 00:09:30,700
I srećom MIT,
koji čini nule, samo

186
00:09:30,700 --> 00:09:33,190
osigurava da on nikada
potpuno nestaje.

187
00:09:33,190 --> 00:09:35,360
Uvijek možete uhvatiti svoj rep.

188
00:09:35,360 --> 00:09:37,680
>> I samo intuitivno,
zašto je držati se kreće?

189
00:09:37,680 --> 00:09:38,892
Što se ovdje događa?

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

191
00:09:41,440 --> 00:09:43,824
On kao da je stalo, ali
onda ako sam pokupiti i povucite

192
00:09:43,824 --> 00:09:45,240
on drži žele ići tamo.

193
00:09:45,240 --> 00:09:46,123
Zašto je to?

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

195
00:09:51,610 --> 00:09:54,360
Zaista, računalo je doslovno
učiniti ono što vi to kažem.

196
00:09:54,360 --> 00:09:58,380
Dakle, ako ste ga rekli ranije učiniti
Sljedeća stvar zauvijek, pomaknuti 10 koraka,

197
00:09:58,380 --> 00:10:01,860
to će zadržati ide i ide
dok sam pogodio crveni znak stop

198
00:10:01,860 --> 00:10:04,620
i uopce zaustaviti program.

199
00:10:04,620 --> 00:10:06,610
>> Dakle, čak i ako nije
to, kako sam mogao

200
00:10:06,610 --> 00:10:09,510
napraviti Scratch brže
preko ekrana?

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

202
00:10:12,060 --> 00:10:13,280
Više koraka, zar ne?

203
00:10:13,280 --> 00:10:15,710
Dakle, umjesto da radiš 10
u isto vrijeme, zašto ne

204
00:10:15,710 --> 00:10:20,100
ići naprijed i promijeniti ga to--
što bi propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Dakle, sada ću kliknuti zelena
zastava, i doista, on ide jako brzo.

206
00:10:24,410 --> 00:10:27,180
>> A to je, naravno, samo je
manifestacija animacije.

207
00:10:27,180 --> 00:10:28,060
Što je animacija?

208
00:10:28,060 --> 00:10:33,090
To je samo ti pokazuje čovjeku
cijela hrpa fotografija zaista,

209
00:10:33,090 --> 00:10:34,160
jako, jako brzo.

210
00:10:34,160 --> 00:10:36,500
I tako, ako mi samo reći
ga premjestiti više koraka,

211
00:10:36,500 --> 00:10:39,750
mi smo samo imaju efekt biti
Promjena gdje je na ekranu

212
00:10:39,750 --> 00:10:42,900
sve brže po jedinici vremena.

213
00:10:42,900 --> 00:10:46,454
>> Sada sljedeći izazov koji sam predložio
bilo da ga odbijaju ruba.

214
00:10:46,454 --> 00:10:49,120
I ne znajući što zagonetka
komada exist-- jer to je u redu

215
00:10:49,120 --> 00:10:53,030
ako ne dobiti na
faza challenge-- ono

216
00:10:53,030 --> 00:10:54,280
želiš raditi intuitivno?

217
00:10:54,280 --> 00:10:58,030
Kako bi smo ga odskočiti natrag i
dalje, između lijevo i desno?

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

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

220
00:11:03,810 --> 00:11:05,680
Dakle, treba nam nekakav
stanja, a mi

221
00:11:05,680 --> 00:11:09,710
čini se da su uvjetne, tako da se
govoriti u kategoriji kontrole.

222
00:11:09,710 --> 00:11:14,110
Koji od ovih blokova
mi vjerojatno želite?

223
00:11:14,110 --> 00:11:15,200
Da, možda ", ako, onda."

224
00:11:15,200 --> 00:11:18,780
Dakle, primijetiti da je među žutim blokovima
ovdje imamo, nalazi se ova "ako"

225
00:11:18,780 --> 00:11:23,920
ili ovo "ako drugi" blok koji će
nam omogućiti da donese odluku da to učini

226
00:11:23,920 --> 00:11:25,000
ili to učiniti.

227
00:11:25,000 --> 00:11:27,380
A možete ih i gnijezdo
raditi više stvari.

228
00:11:27,380 --> 00:11:34,910
Ili ako ne ste otišli još ovdje,
ići naprijed u kategoriju Sensing

229
00:11:34,910 --> 00:11:39,612
and-- da vidimo je li to ovdje.

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

231
00:11:43,050 --> 00:11:52,050
>> Dakle, ono blok bi moglo biti korisno ovdje
otkriti je li on s pozornice?

232
00:11:52,050 --> 00:11:56,740
Da, primijetiti da su neki od tih blokova
može biti parametrizirana, da tako kažemo.

233
00:11:56,740 --> 00:12:00,706
Oni mogu biti na neki način prilagoditi, a ne
za razliku od HTML-a jučer s atributima,

234
00:12:00,706 --> 00:12:03,330
gdje su ti atributi vrsta
prilagoditi ponašanje oznake.

235
00:12:03,330 --> 00:12:08,880
Isto tako ovdje mogu zgrabiti ovu dira
blok i promjene i postaviti pitanje,

236
00:12:08,880 --> 00:12:11,500
ti dira miš
pokazivač poput pokazivača

237
00:12:11,500 --> 00:12:13,250
ili si dira rub?

238
00:12:13,250 --> 00:12:15,210
>> Zato me pusti i to učiniti.

239
00:12:15,210 --> 00:12:18,130
Idem smanjivanje na trenutak.

240
00:12:18,130 --> 00:12:21,320
Dopustite mi da iskoristite ovu slagalice
ovdje, ova zagonetka komad toga,

241
00:12:21,320 --> 00:12:24,570
a ja ću promućkati
im se samo na trenutak.

242
00:12:24,570 --> 00:12:27,620
Idem da se presele toga,
promijeniti u dirljivim ruba,

243
00:12:27,620 --> 00:12:38,590
a ja ću pokretu to učiniti.

244
00:12:38,590 --> 00:12:40,490
Dakle, ovdje su neki sastojci.

245
00:12:40,490 --> 00:12:42,570
Mislim da imam sve što želim.

246
00:12:42,570 --> 00:12:47,710
>> Bi li netko želio predložiti kako sam
mogu povezati to možda vrha do dna

247
00:12:47,710 --> 00:12:52,020
kako bi se riješio problem koji ima
Blok potez ka lijeva na desno kako bi

248
00:12:52,020 --> 00:12:57,020
lijeva na desna na lijevo, svaki
Vrijeme samo odskakanje zidu?

249
00:12:57,020 --> 00:12:58,050
Što želim raditi?

250
00:12:58,050 --> 00:13:01,097
Koji blok bih trebao spojiti na
"Kad zelena zastava kliknuli na prvom mjestu"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, počnimo s "zauvijek".

253
00:13:06,200 --> 00:13:07,170
Ono što ide u sljedeći?

254
00:13:07,170 --> 00:13:10,290
Netko drugi.

255
00:13:10,290 --> 00:13:11,850
OK, premjestiti korake.

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

257
00:13:12,350 --> 00:13:14,470
Što onda?

258
00:13:14,470 --> 00:13:15,120
Pa onda, ako.

259
00:13:15,120 --> 00:13:17,720
I primijetiti, iako to izgleda
sendviču zajedno čvrsto,

260
00:13:17,720 --> 00:13:19,500
to će samo rasti ispuniti.

261
00:13:19,500 --> 00:13:21,500
To će samo skok u kojoj ja to želim.

262
00:13:21,500 --> 00:13:25,920
>> A što da stavim između
if i onda?

263
00:13:25,920 --> 00:13:27,180
Vjerojatno "ako dira rub."

264
00:13:27,180 --> 00:13:31,800
I napomena, opet, to je prevelika
za to, ali to će rasti ispuniti.

265
00:13:31,800 --> 00:13:35,002
A onda okrenuti za 15 stupnjeva?

266
00:13:35,002 --> 00:13:35,710
Koliko stupnjeva?

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

268
00:13:38,800 --> 00:13:41,196
Da, pa 180 će se vrtjeti
meni sve na putu oko.

269
00:13:41,196 --> 00:13:42,570
Dakle, neka je vidjeti ako sam dobio to pravo.

270
00:13:42,570 --> 00:13:43,930
Pusti me smanjivanje.

271
00:13:43,930 --> 00:13:45,130
>> Pusti me vući Scratch gore.

272
00:13:45,130 --> 00:13:50,030
Dakle, on je malo iskrivljena
sada, ali to je u redu.

273
00:13:50,030 --> 00:13:52,231
Kako ga mogu resetirati lako?

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

275
00:13:59,879 --> 00:14:01,045
Idem malo prevariti.

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

277
00:14:04,074 --> 00:14:05,990
Pa ja sam dodao još jedan
blok, samo da bude jasno.

278
00:14:05,990 --> 00:14:08,424
Želim da ukazuju 90 stupnjeva
desno po defaultu,

279
00:14:08,424 --> 00:14:10,840
tako Samo ću mu reći
to učiniti programski.

280
00:14:10,840 --> 00:14:11,632
I ovdje mi ići.

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

282
00:14:14,740 --> 00:14:15,740
Čini se da su to učinili.

283
00:14:15,740 --> 00:14:19,980
To je malo čudno, jer
Hoda naopako.

284
00:14:19,980 --> 00:14:21,250
Nazovimo to kukca.

285
00:14:21,250 --> 00:14:22,120
To je pogreška.

286
00:14:22,120 --> 00:14:27,320
Bug je greška u programu, a
logička pogreška koju sam, ljudski, napravljen.

287
00:14:27,320 --> 00:14:28,985
Zašto ide naopako?

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

289
00:14:33,560 --> 00:14:35,250
Jeste MIT zeznuo ili sam?

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

291
00:14:38,840 --> 00:14:42,550
>> Da, mislim, nije MIT-a
kvara. Dali su mi slagalice

292
00:14:42,550 --> 00:14:44,970
koja kaže okrenuti neki broj stupnjeva.

293
00:14:44,970 --> 00:14:47,672
I na Victoria prijedlog,
Ja sam okreće za 180 stupnjeva,

294
00:14:47,672 --> 00:14:48,880
koji je pravi intuicija.

295
00:14:48,880 --> 00:14:53,700
Ali okreće za 180 stupnjeva doslovno
znači okretanje za 180 stupnjeva,

296
00:14:53,700 --> 00:14:55,860
a to nije stvarno
ono što želim, očito.

297
00:14:55,860 --> 00:14:58,026
Jer barem je on u
ovo dvodimenzionalni svijet,

298
00:14:58,026 --> 00:15:00,740
tako okreće se zapravo događa
da ga okrenuti naopako.

299
00:15:00,740 --> 00:15:04,030
>> Vjerojatno želite koristiti ono što blok
umjesto toga, na temelju onoga što vidite ovdje?

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

301
00:15:11,890 --> 00:15:14,790
Kako bismo mogli popraviti?

302
00:15:14,790 --> 00:15:18,380
Da, kako bismo mogli ukazati
u suprotnom smjeru.

303
00:15:18,380 --> 00:15:22,300
A zapravo čak i da je to
neće biti dovoljno,

304
00:15:22,300 --> 00:15:26,410
jer možemo samo teško kod
na ulijevo ili udesno.

305
00:15:26,410 --> 00:15:27,920
>> Znaš što možemo učiniti?

306
00:15:27,920 --> 00:15:30,160
Čini se da imamo
praktičnost blok ovdje.

307
00:15:30,160 --> 00:15:32,987
Ako sam zumirati, vidi
nešto što nam se sviđa ovdje?

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

309
00:15:36,120 --> 00:15:40,020
Tako to izgleda kao MIT ima
apstrakcija sagrađena ovdje.

310
00:15:40,020 --> 00:15:45,440
Ovaj blok čini se da je jednaka
na koji drugi blokovi, množina?

311
00:15:45,440 --> 00:15:49,510
>> Ovaj blok čini se da je jednaka
cijeloj ovoj trio blokova

312
00:15:49,510 --> 00:15:50,880
da imamo ovdje.

313
00:15:50,880 --> 00:15:54,670
Tako ispada da se pojednostavi moj
Program uzimajući osloboditi od svega toga

314
00:15:54,670 --> 00:15:58,270
i samo staviti ovo ovdje.

315
00:15:58,270 --> 00:16:01,620
A sad je još malo
lud, i to je u redu za sada.

316
00:16:01,620 --> 00:16:03,370
Ostavit ćemo to biti.

317
00:16:03,370 --> 00:16:06,000
No, moj program je još
jednostavnije, a to je, također,

318
00:16:06,000 --> 00:16:09,060
će biti predstavnik
od cilja u programming--

319
00:16:09,060 --> 00:16:13,430
je idealno bi svoj kod kako
jednostavan, kompaktan je to moguće,

320
00:16:13,430 --> 00:16:15,650
dok je još uvijek kao
Ëitkijim.

321
00:16:15,650 --> 00:16:20,310
Vi ne želite da bude tako kratak
da je teško razumjeti.

322
00:16:20,310 --> 00:16:22,826
>> Ali primijetit sam zamijenio
tri bloka s jedne,

323
00:16:22,826 --> 00:16:24,200
i to je vjerojatno dobra stvar.

324
00:16:24,200 --> 00:16:27,280
Ja sam izdvojiti daleko pojam
provjere da li ste

325
00:16:27,280 --> 00:16:29,120
na rubu sa samo jednim blokom.

326
00:16:29,120 --> 00:16:31,520
Sada možemo zabaviti uz to, u stvari.

327
00:16:31,520 --> 00:16:35,790
To ne dodavati toliko
intelektualna vrijednost, ali razigrana vrijednost.

328
00:16:35,790 --> 00:16:39,730
Idem samo naprijed
i iskoristite ovaj zvuk ovdje.

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

330
00:16:42,900 --> 00:16:46,420
Pa neka mi ići naprijed, i neka me
zaustaviti program za trenutak.

331
00:16:46,420 --> 00:16:52,070
Idem snimati sljedeće,
omogućava pristup do mog mikrofona.

332
00:16:52,070 --> 00:16:53,181
>> Idemo.

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

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

335
00:16:58,710 --> 00:17:01,140
Pokušajmo ponovno.

336
00:17:01,140 --> 00:17:02,279
Idemo.

337
00:17:02,279 --> 00:17:03,570
OK, zabilježio sam krivu stvar.

338
00:17:03,570 --> 00:17:04,580
Idemo.

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

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

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

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

343
00:17:09,300 --> 00:17:10,791
Sada moram riješiti to.

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

345
00:17:11,290 --> 00:17:13,950
>> Tako sada imam
Snimanje samo "jao".

346
00:17:13,950 --> 00:17:18,040
Dakle, sada ću ići
naprijed i to nazivamo "jao".

347
00:17:18,040 --> 00:17:20,270
Idem se vratiti
moje skripte, a sada

348
00:17:20,270 --> 00:17:25,460
Obavijest postoji taj blok koji se zove
igrati zvuk "Mijau" ili reproducirati zvuk "jao".

349
00:17:25,460 --> 00:17:28,920
Idem povući ovo, i gdje
trebao sam staviti ovo komično snagu?

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

351
00:17:31,740 --> 00:17:37,860
Da, pa sad je to vrsta
lud, jer sada to block--

352
00:17:37,860 --> 00:17:42,050
primijetiti kako je to "ako je na rubu,
bounce "je vrsta self-sadržane.

353
00:17:42,050 --> 00:17:43,704
Dakle, moram popraviti.

354
00:17:43,704 --> 00:17:44,870
Dopustite mi ići naprijed i učiniti.

355
00:17:44,870 --> 00:17:48,630
Pusti me da biste dobili osloboditi od toga i vratiti
našem original, promišljeniji

356
00:17:48,630 --> 00:17:49,870
funkcionalnost.

357
00:17:49,870 --> 00:18:01,080
Dakle, "ako se dodiruje rub, a zatim" Želim
da se, kao što je Victoria predložio,

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

359
00:18:02,480 --> 00:18:05,497
I želim igrati
zvuk "jao" ne postoji?

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

361
00:18:11,800 --> 00:18:15,580
>> Da, primijetiti da je vani
da je žuta blok.

362
00:18:15,580 --> 00:18:17,680
Dakle, to je, također, bio bi
bug, ali sam ga primijetio.

363
00:18:17,680 --> 00:18:21,290
Tako ću ga povući ovdje,
i obavijest sada je unutar "ako".

364
00:18:21,290 --> 00:18:24,250
Dakle, "ako" je ovo vrsta
baš kao ruka nalik na mrlje

365
00:18:24,250 --> 00:18:26,260
da će samo
učiniti ono što je u njoj.

366
00:18:26,260 --> 00:18:30,216
Pa sad, ako sam smanjivanje na
rizik od annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> Računalo: Joj, joj, joj.

369
00:18:36,470 --> 00:18:39,910
>> DAVID Malan: I
samo će ići na zauvijek.

370
00:18:39,910 --> 00:18:44,160
Sada samo ubrzati stvari
Ovdje, dopusti mi ići naprijed i otvoriti,

371
00:18:44,160 --> 00:18:50,460
neka je say-- me pusti da se neki
moje vlastite stvari iz razreda.

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

373
00:18:53,000 --> 00:19:00,220
I neka mi se otvaraju, recimo, ovaj
jednom napravio jedan od naših nastavnih bližnjima

374
00:19:00,220 --> 00:19:01,500
prije par godina.

375
00:19:01,500 --> 00:19:04,732
Dakle, neki od vas možda podsjetiti
ova igra od prošle,

376
00:19:04,732 --> 00:19:05,940
i to je zapravo nevjerojatno.

377
00:19:05,940 --> 00:19:08,190
Iako smo učinili
Najjednostavniji programa upravo sada,

378
00:19:08,190 --> 00:19:09,980
neka je razmotriti što je to
zapravo izgleda.

379
00:19:09,980 --> 00:19:10,650
Pusti me pogodak igrati.

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

381
00:19:14,210 --> 00:19:18,980
>> Dakle, u ovoj igri, imamo
žaba i korištenja strelicu keys--

382
00:19:18,980 --> 00:19:23,340
on uzima veće korake nego što sam remember--
Imam kontrolu nad tom žaba.

383
00:19:23,340 --> 00:19:29,630
A cilj je da se preko zauzet
Cesta bez trčanje u automobilima.

384
00:19:29,630 --> 00:19:34,735
I neka je see-- ako idem ovdje, ja
morati čekati zapisnik se pomicati.

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

386
00:19:38,130 --> 00:19:39,274
To se osjeća kao kukca.

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

388
00:19:42,240 --> 00:19:43,495
To je vrsta kukca.

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

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

391
00:19:46,480 --> 00:19:51,550
Ja sam na ovo ovdje,
tamo, a onda držati

392
00:19:51,550 --> 00:19:54,100
ide dok ne dobijete sve
žabe na ljiljan jastučići.

393
00:19:54,100 --> 00:19:55,920
Sada bi to moglo izgledati
sve složeniji,

394
00:19:55,920 --> 00:19:57,840
ali neka je pokušati razbiti
ovo dolje psihički

395
00:19:57,840 --> 00:20:00,040
i verbalno u sastavne blokove.

396
00:20:00,040 --> 00:20:03,910
Dakle, tu je vjerojatno puzzle
komad koji još nismo vidjeli

397
00:20:03,910 --> 00:20:07,440
ali to je reagirati na tipke,
stvari sam pogodio na tipkovnici.

398
00:20:07,440 --> 00:20:11,660
>> Tako da je vjerojatno neka vrsta
blok koji kaže da, ako je ključ jednak gore,

399
00:20:11,660 --> 00:20:15,965
zatim učinite nešto s Scratch--
možda premjestiti ga 10 koraka na ovaj način.

400
00:20:15,965 --> 00:20:20,240
Ako je pritisnut tipku, pomaknite 10 koraka
na ovaj način, ili lijevu tipku, pomaknite 10 koraka

401
00:20:20,240 --> 00:20:21,710
Na taj način, 10 koraka to.

402
00:20:21,710 --> 00:20:23,644
Ja sam jasno pretvorio mačka u žabu.

403
00:20:23,644 --> 00:20:26,060
Dakle, to je samo gdje je
kostim, kao i Blok pozivi it-- mi

404
00:20:26,060 --> 00:20:28,440
Samo uvezena sliku žabe.

405
00:20:28,440 --> 00:20:29,570
>> Ali što drugo se događa?

406
00:20:29,570 --> 00:20:32,794
Ono što drugi linija koda,
što drugi slagalice

407
00:20:32,794 --> 00:20:35,460
učinio Blake, naš demonstrator,
koriste u ovom programu, očito?

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

409
00:20:38,320 --> 00:20:42,730
Što čineći sve move--
ono programiranje graditi?

410
00:20:42,730 --> 00:20:44,950
>> Motion, sure-- tako
premjestiti blok, to je sigurno.

411
00:20:44,950 --> 00:20:49,330
A što je to potez blok
unutar, najvjerojatnije?

412
00:20:49,330 --> 00:20:52,850
Da, neka vrsta petlje, možda
zauvijek blokirati, možda ponoviti block--

413
00:20:52,850 --> 00:20:54,070
ponovite sve dok blok.

414
00:20:54,070 --> 00:20:57,330
I to je ono što je stvaranje dnevnika i
ljiljan jastučići i sve ostalo potez

415
00:20:57,330 --> 00:20:57,990
naprijed-nazad.

416
00:20:57,990 --> 00:21:00,270
To je samo što se događa u nedogled.

417
00:21:00,270 --> 00:21:03,180
>> Zašto su neki od automobila
kreće brže od ostalih?

418
00:21:03,180 --> 00:21:06,607
Što je drugačije o tim programima?

419
00:21:06,607 --> 00:21:09,690
Da, vjerojatno neki od njih su uzimanje
više koraka odjednom, a neke od njih

420
00:21:09,690 --> 00:21:10,690
manje koraka odjednom.

421
00:21:10,690 --> 00:21:14,670
A vizualni efekt
je brz u odnosu na spor.

422
00:21:14,670 --> 00:21:16,030
>> Što misliš da se dogodilo?

423
00:21:16,030 --> 00:21:19,700
Kad sam je dobio moj žaba skroz
preko ulice i rijeke

424
00:21:19,700 --> 00:21:23,560
na ljiljan jastučić, nešto
pažnje dogodilo.

425
00:21:23,560 --> 00:21:26,540
Ono što se dogodilo čim sam to učinio?

426
00:21:26,540 --> 00:21:27,210
Zaustavio.

427
00:21:27,210 --> 00:21:29,680
To žaba zaustavljen, a
Dobio sam drugu žabu.

428
00:21:29,680 --> 00:21:33,155
Pa što konstrukt mora biti
koristi tamo, što je značajka?

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

430
00:21:36,020 --> 00:21:38,660
>> Da, tako je neka vrsta
"Ako" stanje tamo, previše.

431
00:21:38,660 --> 00:21:41,909
I ispada out-- nismo vidjeli učinimo
ali ima drugih blokova u bilo koje

432
00:21:41,909 --> 00:21:45,300
mogu reći, ako ste dira
još jedna stvar na ekranu,

433
00:21:45,300 --> 00:21:47,720
ako ste dodirivanje Lily Pad ", zatim".

434
00:21:47,720 --> 00:21:50,810
I onda je to kad smo
bi se pojaviti druga žaba.

435
00:21:50,810 --> 00:21:54,969
Dakle, iako je ova igra je svakako
vrlo datiran, iako na prvi pogled

436
00:21:54,969 --> 00:21:58,010
postoji toliko ide on-- i Blakea
nije bič to u dvije minute,

437
00:21:58,010 --> 00:22:00,390
to je vjerojatno uzeo ga je nekoliko
sati za izradu ove igre

438
00:22:00,390 --> 00:22:03,850
temelji se na njegovoj memoriji ili videa
prošla verzija njega.

439
00:22:03,850 --> 00:22:07,940
No, sve ove sitnice
ide na zaslonu u izolaciji

440
00:22:07,940 --> 00:22:11,550
svode se na to vrlo jednostavan
constructs-- pokreti ili izjave

441
00:22:11,550 --> 00:22:15,519
kao što smo rekli, petlje i
uvjeti, te da je o tome.

442
00:22:15,519 --> 00:22:17,060
Postoji nekoliko drugih ljubitelj značajke.

443
00:22:17,060 --> 00:22:19,130
Neki od njih su čisto
estetskog ili akustični,

444
00:22:19,130 --> 00:22:20,964
poput zvukova samo sam igrao s.

445
00:22:20,964 --> 00:22:23,380
No, za najveći dio,
ima na tom jeziku, ispočetka,

446
00:22:23,380 --> 00:22:25,350
svi temeljni
građevni blokovi koji vas

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

448
00:22:29,280 --> 00:22:32,960
i bilo koji broj drugih jezika.

449
00:22:32,960 --> 00:22:36,720
Bilo kakva pitanja o nule?

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

451
00:22:37,220 --> 00:22:40,303
Pa nećemo roniti dublje ispočetka,
iako ste dobrodošli ovaj vikend,

452
00:22:40,303 --> 00:22:42,860
pogotovo ako imate djecu ili
nećakinje i nećaka i slično,

453
00:22:42,860 --> 00:22:44,220
uvesti ih ispočetka.

454
00:22:44,220 --> 00:22:47,960
To je zapravo predivno razigrano
okruženje s, kako njegovi autori kažu,

455
00:22:47,960 --> 00:22:49,120
vrlo visokim stropovima.

456
00:22:49,120 --> 00:22:51,670
Iako smo započeli s
vrlo detalji niske razine,

457
00:22:51,670 --> 00:22:54,890
zaista možete učiniti vrlo malo
s njim, a to je vjerojatno

458
00:22:54,890 --> 00:22:57,360
demonstracija upravo to.

459
00:22:57,360 --> 00:23:02,920
>> Ali neka se sada prijeći na nešto više
sofisticirane problemi, ako će,

460
00:23:02,920 --> 00:23:05,870
poznat kao "traži" i
"Sortiranje" općenito.

461
00:23:05,870 --> 00:23:09,500
Imali smo taj telefonski imenik earlier-- evo
još jedna samo za discussion--

462
00:23:09,500 --> 00:23:13,460
da smo bili u mogućnosti pretraživanja
učinkovitije jer

463
00:23:13,460 --> 00:23:15,270
značajnog pretpostavke.

464
00:23:15,270 --> 00:23:17,655
I samo da bude jasno, što
pretpostavka bila sam izradi

465
00:23:17,655 --> 00:23:19,280
kada se pretražuje putem ovog telefonskog imenika?

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

467
00:23:23,342 --> 00:23:25,300
Mike Smith je bio u
telefonski imenik, iako sam

468
00:23:25,300 --> 00:23:27,410
će biti u mogućnosti da obrađuju
scenarij bez njega

469
00:23:27,410 --> 00:23:30,720
tamo ako sam prerano prestao.

470
00:23:30,720 --> 00:23:31,806
Knjiga je abecedni.

471
00:23:31,806 --> 00:23:33,930
I to je vrlo velikodušan
pretpostavka, jer to

472
00:23:33,930 --> 00:23:36,580
znači someone-- Ja sam vrsta
rezanje kutak,

473
00:23:36,580 --> 00:23:40,580
kao što sam brže jer netko
još je puno teškog rada za mene.

474
00:23:40,580 --> 00:23:43,120
>> No, što ako je telefon
Knjiga se nerazvrstani?

475
00:23:43,120 --> 00:23:47,050
Možda Verizon dobio lijen, samo bacila
svakog čovjeka imena i brojeva tamo

476
00:23:47,050 --> 00:23:50,120
možda u redoslijedu u kojem su
prijavili za telefonske usluge.

477
00:23:50,120 --> 00:23:54,570
I koliko vremena to me odvesti
naći nekoga kao što je Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1000 stranica telefon book-- koliko
Stranice moram gledati kroz?

479
00:23:58,160 --> 00:23:58,905
>> Svi oni.

480
00:23:58,905 --> 00:24:00,030
Ti si neka vrsta sreće.

481
00:24:00,030 --> 00:24:03,420
Vi doslovno morati pogledati svaki
stranica ako je telefonski imenik je samo

482
00:24:03,420 --> 00:24:04,450
nasumce razvrstani.

483
00:24:04,450 --> 00:24:06,910
Možda ćete dobiti sretan i naći Mike
na prvoj stranici, jer je on

484
00:24:06,910 --> 00:24:08,826
Bio je to prvi kupac
naručiti telefonske usluge.

485
00:24:08,826 --> 00:24:10,760
No, on je možda bio posljednji, previše.

486
00:24:10,760 --> 00:24:12,500
>> Dakle, slučajnim redoslijedom nije dobro.

487
00:24:12,500 --> 00:24:16,750
Dakle, pretpostavimo da imamo za sortiranje
telefonski imenik ili općenito podatke sortiranja

488
00:24:16,750 --> 00:24:18,520
koje smo dobili.

489
00:24:18,520 --> 00:24:19,440
Kako ćemo to učiniti?

490
00:24:19,440 --> 00:24:21,360
>> Pa, neka mi samo probati
jednostavan primjer.

491
00:24:21,360 --> 00:24:24,290
Pusti me naprijed i bacanje
nekoliko brojeva na brodu.

492
00:24:24,290 --> 00:24:35,480
Pretpostavimo brojeve koje imamo su,
recimo, četiri, dva, jedan i tri.

493
00:24:35,480 --> 00:24:38,390
I Ben, sortiranje ove brojeve za nas.

494
00:24:38,390 --> 00:24:39,017
>> OK Dobro.

495
00:24:39,017 --> 00:24:39,850
Kako ti je to uspjelo?

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

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

498
00:24:43,230 --> 00:24:44,710
Dakle, početi s najmanji
vrijednost i najviša,

499
00:24:44,710 --> 00:24:46,084
i to je stvarno dobar intuicija.

500
00:24:46,084 --> 00:24:48,080
I shvatili da smo
ljudi su zapravo prilično

501
00:24:48,080 --> 00:24:49,913
dobar u rješavanju problema
ovako, barem

502
00:24:49,913 --> 00:24:51,810
kada su podaci relativno mali.

503
00:24:51,810 --> 00:24:54,860
Čim počnete da imaju stotine
brojeva, tisuće brojeva,

504
00:24:54,860 --> 00:24:58,440
milijuni brojeva, Ben vjerojatno
to ne mogu baš tako brzo,

505
00:24:58,440 --> 00:25:00,620
uz pretpostavku da su
praznine u tim brojevima.

506
00:25:00,620 --> 00:25:03,450
Prilično lako brojati do milijun
inače, baš vremena.

507
00:25:03,450 --> 00:25:07,150
>> Dakle, algoritam zvuči
kao što je Ben sada koristi samo

508
00:25:07,150 --> 00:25:08,930
je potraga za najmanji broj.

509
00:25:08,930 --> 00:25:12,900
Dakle, iako mi ljudi mogu uzeti
u puno informacija vizualno,

510
00:25:12,900 --> 00:25:14,830
računalo je zapravo
malo više ograničen.

511
00:25:14,830 --> 00:25:17,560
CAN računalo samo
pogledajte jedan bajt u isto vrijeme

512
00:25:17,560 --> 00:25:20,770
ili možda četiri bajta na prvi time--
ovih dana možda 8 bajta na prvi time--

513
00:25:20,770 --> 00:25:24,450
ali vrlo mali broj
bajtova u određenom trenutku.

514
00:25:24,450 --> 00:25:28,480
>> Dakle, s obzirom da smo stvarno imati
Četiri odvojene vrijednosti here--

515
00:25:28,480 --> 00:25:32,440
i možete misliti Ben kao vlasništvo
povez preko očiju da se radi o računalu, kao što

516
00:25:32,440 --> 00:25:36,450
da on ne može vidjeti ništa drugo
od jednog broja pri time--

517
00:25:36,450 --> 00:25:39,720
tako da će općenito pretpostaviti, kao u
Engleski, mi ćemo čitati s desna na lijevo.

518
00:25:39,720 --> 00:25:42,870
Tako je prvi broj Ben vjerojatno izgledala
na bilo četiri, a zatim vrlo brzo

519
00:25:42,870 --> 00:25:44,770
shvatio da je prilično velika
number-- neka mi držati obličje.

520
00:25:44,770 --> 00:25:45,357
>> Ima dva.

521
00:25:45,357 --> 00:25:45,940
Pričekaj minutu.

522
00:25:45,940 --> 00:25:47,070
Dva je manji od četiri.

523
00:25:47,070 --> 00:25:47,986
Idem za pamćenje.

524
00:25:47,986 --> 00:25:49,070
Dva je sada najmanji.

525
00:25:49,070 --> 00:25:50,417
Sada one-- to je čak i bolje.

526
00:25:50,417 --> 00:25:51,250
To je još manji.

527
00:25:51,250 --> 00:25:54,000
Idem zaboraviti dvije
i samo sjetiti sada.

528
00:25:54,000 --> 00:25:56,550
>> A mogao prestati gledati?

529
00:25:56,550 --> 00:25:58,360
Pa, mogao je na bazi
na ovoj informaciji,

530
00:25:58,360 --> 00:26:00,477
ali on je bolje pretragu
ostatak popisa.

531
00:26:00,477 --> 00:26:02,060
Jer, što ako nule su na popisu?

532
00:26:02,060 --> 00:26:03,643
Što ako je negativna su na popisu?

533
00:26:03,643 --> 00:26:07,720
On samo zna da je njegov odgovor
je ispravan ako je iscrpno

534
00:26:07,720 --> 00:26:08,729
provjeriti cijeli popis.

535
00:26:08,729 --> 00:26:10,020
Tako smo, pogledajte ostatak ove.

536
00:26:10,020 --> 00:26:11,394
Three-- to je gubljenje vremena.

537
00:26:11,394 --> 00:26:13,540
Imaš sreće, ali sam bio
još uvijek točna to učiniti.

538
00:26:13,540 --> 00:26:17,857
I tako je sada vjerojatno
odabrana najmanji broj

539
00:26:17,857 --> 00:26:20,440
i samo ga stavi na početku
popisa, kao što ću učiniti ovdje.

540
00:26:20,440 --> 00:26:23,480
Sad što si dalje, iako
ne mislite o tome gotovo

541
00:26:23,480 --> 00:26:25,962
do te mjere?

542
00:26:25,962 --> 00:26:27,670
Ponovite postupak,
pa neka vrsta petlje.

543
00:26:27,670 --> 00:26:28,920
Postoji poznata ideja.

544
00:26:28,920 --> 00:26:30,860
Dakle, ovdje je četiri.

545
00:26:30,860 --> 00:26:32,110
To je trenutno najmanji.

546
00:26:32,110 --> 00:26:33,220
To je kandidat.

547
00:26:33,220 --> 00:26:33,900
Ne više.

548
00:26:33,900 --> 00:26:34,770
Sad sam vidio dva.

549
00:26:34,770 --> 00:26:36,630
To je sljedeći najmanji element.

550
00:26:36,630 --> 00:26:40,800
Three-- to nije manja, tako da
Sada je Ben može oteti iz dva.

551
00:26:40,800 --> 00:26:44,510
>> I sada smo ponoviti postupak, a
naravno tri dobiva izvukao sljedeći.

552
00:26:44,510 --> 00:26:45,420
Ponovite postupak.

553
00:26:45,420 --> 00:26:46,990
Četiri dobiva izvukao.

554
00:26:46,990 --> 00:26:50,140
A sada smo bez brojeva,
tako da popis mora biti riješeno.

555
00:26:50,140 --> 00:26:51,960
>> I doista, ovo je formalna algoritam.

556
00:26:51,960 --> 00:26:56,610
Računalni znanstvenik
to nazivamo "Odabir vrste"

557
00:26:56,610 --> 00:27:00,880
Ideja se Poredaj A
opet navesti iteratively--

558
00:27:00,880 --> 00:27:03,807
i opet i opet odabira
najmanji broj.

559
00:27:03,807 --> 00:27:06,140
A što je lijepo o tome je
to je jednostavno tako prokleto intuitivno.

560
00:27:06,140 --> 00:27:07,470
To je tako jednostavno.

561
00:27:07,470 --> 00:27:11,100
A možete ponoviti isti
Operacija opet i opet.

562
00:27:11,100 --> 00:27:12,150
Jednostavno je.

563
00:27:12,150 --> 00:27:17,170
>> U ovom slučaju to je brzo, ali
Koliko je zapravo potrebno?

564
00:27:17,170 --> 00:27:19,880
Učinimo to činiti i
Osjećam se malo više zamoran.

565
00:27:19,880 --> 00:27:24,150
Dakle, jedan, dva, tri, četiri, pet i šest,
sedam, osam, devet, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- proizvoljan broj.

567
00:27:26,160 --> 00:27:28,780
Samo sam htjela još ovo
Vrijeme od samo četiri.

568
00:27:28,780 --> 00:27:30,780
Dakle, ako sam dobio jednu cjelinu
hrpa brojeva to now--

569
00:27:30,780 --> 00:27:32,420
ni ne smeta
što are-- Idemo

570
00:27:32,420 --> 00:27:34,380
razmišljati o tome što je to
Algoritam je stvarno slično.

571
00:27:34,380 --> 00:27:35,857
>> Pretpostavimo da postoje brojevi tamo.

572
00:27:35,857 --> 00:27:38,190
Opet, ne smeta što je
oni su, ali oni su slučajni.

573
00:27:38,190 --> 00:27:39,679
Javljam Benov algoritam.

574
00:27:39,679 --> 00:27:41,220
Moram odabrati najmanji broj.

575
00:27:41,220 --> 00:27:41,761
Što da radim?

576
00:27:41,761 --> 00:27:44,240
I ja idem na fizički
to učiniti ovaj put da ga glume.

577
00:27:44,240 --> 00:27:46,099
U potrazi, u potrazi,
gleda, gleda, gleda.

578
00:27:46,099 --> 00:27:48,140
Tek kad sam doći do
kraj popisa mogu

579
00:27:48,140 --> 00:27:51,230
Jasno mi je najmanji
broj je bio dva i ovaj put.

580
00:27:51,230 --> 00:27:52,720
Jedan nije na popisu.

581
00:27:52,720 --> 00:27:54,400
Zato sam spustio dva.

582
00:27:54,400 --> 00:27:55,590
>> Što da učinim?

583
00:27:55,590 --> 00:27:58,600
U potrazi, u potrazi, u potrazi, u potrazi.

584
00:27:58,600 --> 00:28:02,250
Sad sam našla broj sedam, jer
postoji praznina u tim numbers--

585
00:28:02,250 --> 00:28:03,300
ali samo proizvoljna.

586
00:28:03,300 --> 00:28:03,800
U redu.

587
00:28:03,800 --> 00:28:06,030
Pa sad ja mogu spustiti sedam.

588
00:28:06,030 --> 00:28:08,860
Gledajući gleda, gleda.

589
00:28:08,860 --> 00:28:11,030
>> Sada sam uz pretpostavku, od
Naravno, da Ben ne

590
00:28:11,030 --> 00:28:14,780
imati dodatni RAM, pomoćni
memorije, jer, naravno,

591
00:28:14,780 --> 00:28:16,080
Gledam u istom broju.

592
00:28:16,080 --> 00:28:18,246
Sigurno sam mogao sjetio
sve te brojeve,

593
00:28:18,246 --> 00:28:19,930
i to je apsolutno istinito.

594
00:28:19,930 --> 00:28:22,610
Ali ako Ben pamti sve
od brojeva što je vidio,

595
00:28:22,610 --> 00:28:24,430
on zapravo nije napravio
temeljni napredak

596
00:28:24,430 --> 00:28:26,170
jer on već ima
sposobnost za pretraživanje

597
00:28:26,170 --> 00:28:27,540
kroz brojeve na brodu.

598
00:28:27,540 --> 00:28:29,373
Sjećanje na sve od
Brojevi ne pomogne,

599
00:28:29,373 --> 00:28:32,490
jer on može i dalje kao računalo
samo pogledajte, mi smo navedeni, jedan broj

600
00:28:32,490 --> 00:28:33,080
u isto vrijeme.

601
00:28:33,080 --> 00:28:35,760
Dakle, nema vrsta varanja
ima koji možete iskoristiti.

602
00:28:35,760 --> 00:28:39,170
>> Dakle, u stvarnosti, kao što sam
držati koji traži popis,

603
00:28:39,170 --> 00:28:44,200
Doslovno sam se samo zadržati ide
naprijed i nazad kroz njega, čupanje

604
00:28:44,200 --> 00:28:45,710
sljedeći najmanji broj.

605
00:28:45,710 --> 00:28:48,810
I kao što možete vrsta zaključiti
iz mojih glupih pokreta,

606
00:28:48,810 --> 00:28:50,860
Ovo postaje vrlo
dosadan vrlo brzo,

607
00:28:50,860 --> 00:28:54,850
i čini mi se da ide natrag i
naprijed, natrag i naprijed vrlo malo.

608
00:28:54,850 --> 00:29:03,220
Sad da bude fer, ja ne moram ići
sasvim kao, dobro, neka je see-- da bude fer,

609
00:29:03,220 --> 00:29:06,310
Ne moram hodati sasvim
onoliko koraka svaki put.

610
00:29:06,310 --> 00:29:09,200
Jer, naravno, kao što sam
odabir brojeva s popisa,

611
00:29:09,200 --> 00:29:11,860
preostali popis je sve kraći.

612
00:29:11,860 --> 00:29:14,240
>> I tako ćemo razmišljati o
koliko koraka sam zapravo

613
00:29:14,240 --> 00:29:16,010
traipsing kroz svaki put.

614
00:29:16,010 --> 00:29:18,950
U prvom situaciji
imali smo 16 brojeva,

615
00:29:18,950 --> 00:29:22,210
pa maximally---a neka samo
to učiniti za discussion--

616
00:29:22,210 --> 00:29:25,640
Morao sam gledati kroz 16
Brojevi pronaći najmanji.

617
00:29:25,640 --> 00:29:28,420
Ali jednom sam iskopali
najmanji broj, kako

618
00:29:28,420 --> 00:29:30,590
dugo je preostalo popis, naravno?

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

620
00:29:31,420 --> 00:29:34,670
Dakle, koliko brojeva učinio Ben ili moram
gledati kroz drugi put oko?

621
00:29:34,670 --> 00:29:36,832
15, samo otići i pronaći najmanji.

622
00:29:36,832 --> 00:29:39,540
Ali sada, naravno, popis je,
također, manji nego što je bio prije.

623
00:29:39,540 --> 00:29:42,540
Pa koliko koraka zar ne
uzeti sljedeći put?

624
00:29:42,540 --> 00:29:49,970
14, a zatim 13, a zatim 12, plus dot,
točka, točka, dok sam napustio sa samo jednom.

625
00:29:49,970 --> 00:29:53,146
Tako sada računalni znanstvenik
pitam, dobro, što to svi jednaki?

626
00:29:53,146 --> 00:29:55,770
To je zapravo jednak neki beton
broj koji smo mogli sigurno

627
00:29:55,770 --> 00:30:00,490
učiniti aritmetički, ali želimo razgovarati
o učinkovitosti algoritama

628
00:30:00,490 --> 00:30:04,940
malo više formulaically,
neovisna o tome koliko dugo je popis.

629
00:30:04,940 --> 00:30:06,240
>> I tako, znate što?

630
00:30:06,240 --> 00:30:09,860
To je 16 godina, ali kao što sam rekao prije,
neka je samo poziv na veličinu problema

631
00:30:09,860 --> 00:30:10,970
n, gdje je n neki broj.

632
00:30:10,970 --> 00:30:13,220
Možda je 16, možda je
tri, možda je milijun.

633
00:30:13,220 --> 00:30:13,761
Ne znam.

634
00:30:13,761 --> 00:30:14,390
Ne zanima me.

635
00:30:14,390 --> 00:30:16,520
Ono što stvarno želim je
formula koja mogu

636
00:30:16,520 --> 00:30:19,420
koristiti za usporedbu ovog algoritma
protiv drugih algoritama

637
00:30:19,420 --> 00:30:22,350
da bi netko mogao tvrditi
su bolje ili lošije.

638
00:30:22,350 --> 00:30:25,430
>> Tako ispada, a samo ja
znam iz osnovne škole,

639
00:30:25,430 --> 00:30:34,790
da je to zapravo radi se na isto
stvar kao N iznad n plus jedan više od dva.

640
00:30:34,790 --> 00:30:40,020
I to se događa jednaka, od
Naravno, n na kvadrat plus n više od dva.

641
00:30:40,020 --> 00:30:43,250
Dakle, ako sam htjela formulu
za koliko koraka

642
00:30:43,250 --> 00:30:46,330
su bili uključeni u gleda na sve
svaki put iznova tim brojevima

643
00:30:46,330 --> 00:30:52,681
i opet i opet, rekao bih
to n je kvadrat plus n više od dva.

644
00:30:52,681 --> 00:30:53,430
Ali znate što?

645
00:30:53,430 --> 00:30:54,500
To samo izgleda neuredno.

646
00:30:54,500 --> 00:30:56,470
Samo sam stvarno želite
opći osjećaj stvari.

647
00:30:56,470 --> 00:30:58,810
A možda sjetiti iz
visoka škola koja postoji

648
00:30:58,810 --> 00:31:00,660
je pojam najvišeg reda pojam.

649
00:31:00,660 --> 00:31:05,300
Koji od ovih uvjeta, n
kvadrat, N, ili pola,

650
00:31:05,300 --> 00:31:07,550
ima najveći utjecaj tijekom vremena?

651
00:31:07,550 --> 00:31:11,920
Veći n dobiva, koji
o ovim pitanjima najviše?

652
00:31:11,920 --> 00:31:15,560
>> Drugim riječima, ako se spoji
u milijun, n na kvadrat

653
00:31:15,560 --> 00:31:17,900
koja će se najvjerojatnije
faktor u momčadi,

654
00:31:17,900 --> 00:31:21,670
jer milijun puta
Sama je puno veći

655
00:31:21,670 --> 00:31:23,682
od plus jedan dodatni milijun.

656
00:31:23,682 --> 00:31:24,390
Dakle, znate što?

657
00:31:24,390 --> 00:31:27,305
Ovo je tako prokleto velika
broj ako trg broj.

658
00:31:27,305 --> 00:31:28,430
To nije važno.

659
00:31:28,430 --> 00:31:30,596
Samo ćemo križ koji
van i zaboraviti o tome.

660
00:31:30,596 --> 00:31:34,250
I tako računalni znanstvenik će reći
da učinkovitost tog algoritma

661
00:31:34,250 --> 00:31:37,850
je reda n squared--
Mislim zaista aproksimacija.

662
00:31:37,850 --> 00:31:40,810
To je na neki način grubo n na kvadrat.

663
00:31:40,810 --> 00:31:44,130
Tijekom vremena, što je veći
i veći n dobiva, to

664
00:31:44,130 --> 00:31:47,610
je dobra procjena za ono što je
Učinkovitost ili nedostatak učinkovitosti

665
00:31:47,610 --> 00:31:49,400
ovog algoritma zapravo jest.

666
00:31:49,400 --> 00:31:52,040
I ja izvući, naravno,
od zapravo radi math.

667
00:31:52,040 --> 00:31:54,040
Ali sada sam samo maše
moje ruke, jer sam upravo

668
00:31:54,040 --> 00:31:55,790
Želite opći osjećaj tog algoritma.

669
00:31:55,790 --> 00:31:58,850
>> Dakle, koristeći istu logiku, u međuvremenu,
Razmotrimo još jedan algoritam

670
00:31:58,850 --> 00:32:01,162
mi već gledao at-- linearno pretraživanje.

671
00:32:01,162 --> 00:32:02,870
Kad sam bio u potrazi
za telefon book--

672
00:32:02,870 --> 00:32:05,980
Nije ga sortiranje, pretraživanje
putem telefona book--

673
00:32:05,980 --> 00:32:09,197
mi je stalno govorio da je to
1.000 koraka, ili 500 koraka.

674
00:32:09,197 --> 00:32:10,280
Ali neka se generalizirati to.

675
00:32:10,280 --> 00:32:12,860
Ako postoji n stranice u
telefonski imenik, što je

676
00:32:12,860 --> 00:32:17,250
Računanje vremena ili
Učinkovitost linearno pretraživanje?

677
00:32:17,250 --> 00:32:19,750
To je na red
koliko koraka kako bi pronašli

678
00:32:19,750 --> 00:32:24,210
Mike Smith linearnom pretraživanje,
Prvi algoritam, ili čak i drugi?

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

680
00:32:27,240 --> 00:32:31,710
>> U najgorem slučaju, Mike
se nalazi na kraju knjige.

681
00:32:31,710 --> 00:32:35,590
Dakle, ako je telefon knjiga ima 1.000 stranica,
mi je rekao prošli put, u najgorem slučaju,

682
00:32:35,590 --> 00:32:38,380
to bi moglo potrajati otprilike koliko
mnoge stranice kako bi pronašli Mike?

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

684
00:32:38,990 --> 00:32:39,830
To je gornja granica.

685
00:32:39,830 --> 00:32:41,790
To je najgora moguća situacija.

686
00:32:41,790 --> 00:32:44,410
Ali opet, idemo dalje
od brojeva kao što su 1000 sada.

687
00:32:44,410 --> 00:32:45,730
To je samo n.

688
00:32:45,730 --> 00:32:47,470
>> Dakle, što je logičan zaključak?

689
00:32:47,470 --> 00:32:50,210
Pronalaženje Mike u telefonu
Knjiga koja ima n stranice

690
00:32:50,210 --> 00:32:55,280
bi moglo potrajati, u najgorem slučaju,
koliko koraka reda veličine n?

691
00:32:55,280 --> 00:32:58,110
I doista računalo
znanstvenik će reći

692
00:32:58,110 --> 00:33:02,340
da je vrijeme rada, odnosno
performansi ili učinkovitosti

693
00:33:02,340 --> 00:33:07,470
ili neučinkovitost, algoritma kao
linearna pretraživanje na red n.

694
00:33:07,470 --> 00:33:10,010
I možemo primijeniti isti
Logika prelaska nešto

695
00:33:10,010 --> 00:33:13,170
kao što sam upravo učinio u sekundu
Algoritam smo imali s telefonskog imenika,

696
00:33:13,170 --> 00:33:16,040
gdje smo išli dvije stranice odjednom.

697
00:33:16,040 --> 00:33:20,120
>> Dakle 1000 stranica telefonski imenik možda
će nas 500 stranica okreta, plus jedan

698
00:33:20,120 --> 00:33:21,910
ako smo dvostruko natrag malo.

699
00:33:21,910 --> 00:33:26,590
Dakle, ako telefon knjiga ima n stranica, ali
radimo dvije stranice u isto vrijeme,

700
00:33:26,590 --> 00:33:28,900
to je otprilike što?

701
00:33:28,900 --> 00:33:33,190
N iznad dvije, tako da je kao N iznad dva.

702
00:33:33,190 --> 00:33:38,490
Ali ja napravio tvrditi
Trenutak prije da n nad two--

703
00:33:38,490 --> 00:33:41,060
to je vrsta isto kao i samo n.

704
00:33:41,060 --> 00:33:44,050
To je samo konstantan faktor,
računalni znanstvenici će reći.

705
00:33:44,050 --> 00:33:45,970
Recimo samo da se usredotočite na
varijable, really--

706
00:33:45,970 --> 00:33:47,780
najveće varijable u jednadžbi.

707
00:33:47,780 --> 00:33:52,530
>> Dakle linearno pretraživanje, je li učinjeno jedno
stranica odjednom ili dvije stranice odjednom,

708
00:33:52,530 --> 00:33:54,810
je vrsta u osnovi isti.

709
00:33:54,810 --> 00:33:56,880
To je još uvijek na red n.

710
00:33:56,880 --> 00:34:01,930
Ali ja tvrdio sa svojom slikom ranije
da je treći algoritam nije bilo

711
00:34:01,930 --> 00:34:02,480
linearna.

712
00:34:02,480 --> 00:34:03,605
To nije bio ravna crta.

713
00:34:03,605 --> 00:34:08,659
Bilo je to zakrivljena linija, a
algebarska formula je bilo što?

714
00:34:08,659 --> 00:34:11,812
Prijavite od n- tako log baze dvije n.

715
00:34:11,812 --> 00:34:14,520
I ne moramo ići u previše
mnogo detalja o logaritmi danas,

716
00:34:14,520 --> 00:34:17,394
ali većina računalni znanstvenici ne bi
čak vam reći što je baza.

717
00:34:17,394 --> 00:34:20,639
Jer to je sve samo
stalne čimbenici, da tako kažemo,

718
00:34:20,639 --> 00:34:22,659
samo male brojčani razlike.

719
00:34:22,659 --> 00:34:31,179
I tako će to biti vrlo čest
način posebno formalno računala

720
00:34:31,179 --> 00:34:33,949
znanstvenici na brodu ili
programera na bijeloj ploči

721
00:34:33,949 --> 00:34:36,889
zapravo tvrdeći koji
Algoritam će koristiti

722
00:34:36,889 --> 00:34:39,500
ili što je učinkovitost
od njihova algoritam je.

723
00:34:39,500 --> 00:34:42,960
>> I to ne mora nužno biti nešto
raspravljate na bilo vrlo detaljno,

724
00:34:42,960 --> 00:34:47,889
ali dobar programer je onaj
koji ima solidnu, formalnu pozadinu.

725
00:34:47,889 --> 00:34:50,120
On je u stanju razgovarati s
što u ovoj vrsti način

726
00:34:50,120 --> 00:34:53,350
i zapravo napraviti
kvalitativne argumente

727
00:34:53,350 --> 00:34:56,870
zašto jedan algoritam ili
jedan komad softvera

728
00:34:56,870 --> 00:35:00,165
je superioran na neki način u drugi.

729
00:35:00,165 --> 00:35:02,540
Zato što bi svakako
samo pokrenuti program za jedne osobe

730
00:35:02,540 --> 00:35:04,980
i brojati broj sekundi
što je potrebno za sortiranje neke brojeve,

731
00:35:04,980 --> 00:35:06,710
i možete pokrenuti neke
Program druge osobe

732
00:35:06,710 --> 00:35:08,418
i brojati broj
sekundi je potrebno.

733
00:35:08,418 --> 00:35:12,840
No, to je nešto širi način na koji
možete koristiti za analizu algoritama,

734
00:35:12,840 --> 00:35:15,520
ako hoćete, samo na
papir ili samo verbalno.

735
00:35:15,520 --> 00:35:18,430
Čak i bez da radi bez
čak i težak uzorak ulaza,

736
00:35:18,430 --> 00:35:20,180
možete samo razmišljati kroz nju.

737
00:35:20,180 --> 00:35:24,670
I tako s bicikla programer ili ako
ima mu ili joj na neki način raspravljati s tobom

738
00:35:24,670 --> 00:35:28,460
zašto je njihov algoritam, njihova tajna
Umak za pretraživanje milijarde

739
00:35:28,460 --> 00:35:30,580
web stranica za vaš
Tvrtka je bolje, to

740
00:35:30,580 --> 00:35:33,302
su vrste argumenata se
idealno bi trebao biti u mogućnosti napraviti.

741
00:35:33,302 --> 00:35:35,010
Ili barem to su
vrste stvari

742
00:35:35,010 --> 00:35:40,211
da bi se u raspravi, na
barem u vrlo formalne rasprave.

743
00:35:40,211 --> 00:35:40,710
U redu.

744
00:35:40,710 --> 00:35:44,400
Dakle, Ben predložio nešto
zove odabir vrsta.

745
00:35:44,400 --> 00:35:48,200
Ali ja ću predložiti da postoji
drugi načini za to, previše.

746
00:35:48,200 --> 00:35:50,400
Ono što nisam stvarno volio
oko Benova algoritam

747
00:35:50,400 --> 00:35:54,400
je da je hodao, ili
što mi je hodati, naprijed i natrag

748
00:35:54,400 --> 00:35:56,930
i natrag i naprijed i natrag i naprijed.

749
00:35:56,930 --> 00:36:04,130
Što ako umjesto toga sam bila napraviti
nešto poput ovih brojeva ovdje

750
00:36:04,130 --> 00:36:08,200
i ja se samo nositi sa svakim
Broj opet kao što sam ga dao?

751
00:36:08,200 --> 00:36:10,780
>> Drugim riječima, ovdje je
moj popis brojeva.

752
00:36:10,780 --> 00:36:12,944
Četiri, jedan, tri, dva.

753
00:36:12,944 --> 00:36:14,360
I ja ću učiniti sljedeće.

754
00:36:14,360 --> 00:36:17,230
Idem ubaciti brojeve
gdje pripadaju a

755
00:36:17,230 --> 00:36:18,980
od odabira ih jednu po jednu.

756
00:36:18,980 --> 00:36:20,820
Drugim riječima, ovdje je broj četiri.

757
00:36:20,820 --> 00:36:22,430
>> Evo moj izvorni popis.

758
00:36:22,430 --> 00:36:25,290
A ja ću za održavanje
u suštini novi popis ovdje.

759
00:36:25,290 --> 00:36:26,710
Dakle, ovo je stari popis.

760
00:36:26,710 --> 00:36:28,560
Ovo je nova lista.

761
00:36:28,560 --> 00:36:30,220
Vidim broj četiri na prvom mjestu.

762
00:36:30,220 --> 00:36:34,500
Moj novi popis početku je prazan
tako da je trivijalno slučaj

763
00:36:34,500 --> 00:36:36,410
da su četiri sada ponekog popis.

764
00:36:36,410 --> 00:36:39,560
Ja samo da broj sam dao,
a ja sam ga stavljajući u mom novom popisu.

765
00:36:39,560 --> 00:36:41,460
>> Je li to novi popis razvrstani?

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

767
00:36:41,990 --> 00:36:45,090
To je glupo, jer postoji samo jedan
Element, ali to apsolutno je riješeno.

768
00:36:45,090 --> 00:36:46,390
Nema ništa izvan mjesta.

769
00:36:46,390 --> 00:36:49,290
To je još zanimljivije, ovaj algoritam,
kad sam premjestiti na sljedeći korak.

770
00:36:49,290 --> 00:36:50,550
>> Sada imam jedan.

771
00:36:50,550 --> 00:36:55,430
Dakle, jedan, naravno, pripada Na
početku ili na kraju ovog novog popisa?

772
00:36:55,430 --> 00:36:56,360
Početak.

773
00:36:56,360 --> 00:36:58,530
Dakle, moram napraviti neki posao sada.

774
00:36:58,530 --> 00:37:01,410
Ive 'bio uzimajući neke
slobode s markerom mom

775
00:37:01,410 --> 00:37:03,120
za samo crtanje stvari
gdje želim ih,

776
00:37:03,120 --> 00:37:05,320
ali to nije stvarno
točan u računalu.

777
00:37:05,320 --> 00:37:08,530
Računalo, kao što znamo, ima
RAM ili Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
i to je jedan bajt i
još jedan bajt a drugi bajt.

779
00:37:12,411 --> 00:37:14,910
A ako imate gigabajt
RAM-a, imate milijardu bajtova,

780
00:37:14,910 --> 00:37:16,680
ali oni su fizički na jednom mjestu.

781
00:37:16,680 --> 00:37:19,540
Ne možete samo premjestiti stvari oko
tako da je crtež na brodu

782
00:37:19,540 --> 00:37:20,750
gdje god želiš.

783
00:37:20,750 --> 00:37:24,090
Dakle, ako je moj novi popis ima
četiri lokacije u memoriji,

784
00:37:24,090 --> 00:37:27,480
nažalost četiri je
Već na krivom mjestu.

785
00:37:27,480 --> 00:37:30,410
>> Dakle umetnuti broj jedan
Ne mogu ga izvući ovdje.

786
00:37:30,410 --> 00:37:31,901
Ova memorija lokacija ne postoji.

787
00:37:31,901 --> 00:37:35,150
To bi bilo varanje, i ja sam bio
varanje slikovno za nekoliko minuta

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

789
00:37:35,800 --> 00:37:40,950
Pa stvarno, ako želim staviti ga ovdje,
Moram privremeno kopirati četiri

790
00:37:40,950 --> 00:37:43,030
a zatim staviti onu tamo.

791
00:37:43,030 --> 00:37:45,500
>> To je u redu, to je točno,
to je tehnički moguće,

792
00:37:45,500 --> 00:37:48,410
ali shvatite da je dodatni rad.

793
00:37:48,410 --> 00:37:50,460
Nisam samo staviti broj na mjestu.

794
00:37:50,460 --> 00:37:53,026
Prvi put sam morao pomaknuti
broj, a zatim ga staviti na mjesto,

795
00:37:53,026 --> 00:37:54,650
pa sam nekako udvostručio svoju količinu rada.

796
00:37:54,650 --> 00:37:55,660
Dakle, imajte to na umu.

797
00:37:55,660 --> 00:37:57,120
>> Ali ja sam sada učinjeno s ovim elementom.

798
00:37:57,120 --> 00:37:59,056
Sada želim da zgrabite broj tri.

799
00:37:59,056 --> 00:38:00,430
Gdje je, naravno, to pripada?

800
00:38:00,430 --> 00:38:01,480
Između.

801
00:38:01,480 --> 00:38:03,650
Ne mogu varati više
i samo ga tamo stavio,

802
00:38:03,650 --> 00:38:06,770
jer, opet, ove memorije
u fizičkim lokacijama.

803
00:38:06,770 --> 00:38:10,900
Pa moram kopirati četiri
i stavi tri ovamo.

804
00:38:10,900 --> 00:38:11,550
Nije velika stvar.

805
00:38:11,550 --> 00:38:14,610
To je samo jedan dodatni korak
again-- osjeća vrlo jeftin.

806
00:38:14,610 --> 00:38:16,445
>> Ali sada sam prijeći na dva.

807
00:38:16,445 --> 00:38:17,820
Njih dvoje, naravno, pripada ovdje.

808
00:38:17,820 --> 00:38:20,990
Sada počinjete vidjeti kako
rad može nagomilati.

809
00:38:20,990 --> 00:38:23,520
Sada ono što moram napraviti?

810
00:38:23,520 --> 00:38:28,570
Da, moram premjestiti četiri,
I onda moram kopirati tri,

811
00:38:28,570 --> 00:38:31,200
i sada mogu umetnuti dvije.

812
00:38:31,200 --> 00:38:34,460
A kvaka s tim
Algoritam Zanimljivo

813
00:38:34,460 --> 00:38:41,050
je da pretpostavimo imamo više ekstremnih
slučaj u kojemu je recimo osam, sedam,

814
00:38:41,050 --> 00:38:45,150
šest, pet, četiri, tri, dva, jedan.

815
00:38:45,150 --> 00:38:49,450
To je, u mnogim kontekstima,
najgori mogući scenarij,

816
00:38:49,450 --> 00:38:51,570
jer je prokleto stvar
je doslovno unatrag.

817
00:38:51,570 --> 00:38:53,670
>> To ne stvarno
utjecati na Benovu algoritam,

818
00:38:53,670 --> 00:38:55,940
jer u Benove odabir
sortirati on će zadržati

819
00:38:55,940 --> 00:38:58,359
ide natrag i naprijed kroz popis.

820
00:38:58,359 --> 00:39:01,150
A budući da je uvijek u potrazi
kroz cijeli preostali popisu

821
00:39:01,150 --> 00:39:02,858
nije važno
gdje su elementi.

822
00:39:02,858 --> 00:39:05,630
No, u ovom slučaju s mojim umetanje
approach-- pokušajmo.

823
00:39:05,630 --> 00:39:08,616
>> Dakle, jedan, dva, tri, četiri,
pet, šest, sedam, osam.

824
00:39:08,616 --> 00:39:11,630
Jedan dva tri četiri,
pet, šest, sedam, osam.

825
00:39:11,630 --> 00:39:14,320
Idem uzeti osam,
i gdje sam ga stavio?

826
00:39:14,320 --> 00:39:17,260
Pa, na početku moje liste,
jer je ova nova Popis je sortiran.

827
00:39:17,260 --> 00:39:18,760
I ja sam ga prekrižiti.

828
00:39:18,760 --> 00:39:20,551
>> Gdje da stavim sedam?

829
00:39:20,551 --> 00:39:21,050
Prokleti.

830
00:39:21,050 --> 00:39:23,174
To treba da ide tamo, pa
Moram obaviti neke kopiranja.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
A sada sedam ide ovdje.

833
00:39:28,480 --> 00:39:29,860
Sada sam prijeći na šest.

834
00:39:29,860 --> 00:39:30,980
Sada je još više posla.

835
00:39:30,980 --> 00:39:32,570
>> Osam mora ići ovdje.

836
00:39:32,570 --> 00:39:33,920
Sedam mora ići ovdje.

837
00:39:33,920 --> 00:39:35,450
Sada je šest može ići ovdje.

838
00:39:35,450 --> 00:39:37,950
Sad sam uzeo pet.

839
00:39:37,950 --> 00:39:40,560
Sada je osam mora otići
ovdje, sedam mora ići ovdje,

840
00:39:40,560 --> 00:39:43,650
šest mora ići ovdje, a
sada pet i ponoviti.

841
00:39:43,650 --> 00:39:46,610
I ja sam prilično mnogo
pomičući ga stalno.

842
00:39:46,610 --> 00:39:52,950
>> Tako je na kraju, ovaj algorithm-- mi ćemo
zovu ga umetanje sort-- zapravo

843
00:39:52,950 --> 00:39:55,020
ima puno posla, previše.

844
00:39:55,020 --> 00:39:56,970
To je samo drugačiji
vrsta posla nego Benov.

845
00:39:56,970 --> 00:40:00,090
Benov rad imao me ide
natrag i naprijed cijelo vrijeme,

846
00:40:00,090 --> 00:40:03,510
Odabirom sljedeći najmanji
Element opet i opet.

847
00:40:03,510 --> 00:40:06,660
Tako da je to vrlo vizualna vrsta posla.

848
00:40:06,660 --> 00:40:10,600
>> Taj drugi algoritam, koji je još
correct-- da će dobiti posao done--

849
00:40:10,600 --> 00:40:12,800
samo mijenja količinu rada.

850
00:40:12,800 --> 00:40:15,420
Čini se da u početku si
štedi, jer ti si samo

851
00:40:15,420 --> 00:40:19,190
bave svaki element
up front ne hodaju sve

852
00:40:19,190 --> 00:40:20,930
put kroz popis kao Ben bio.

853
00:40:20,930 --> 00:40:25,300
No, problem je, osobito u ovim
ludi slučajevi u kojima je sve unatrag,

854
00:40:25,300 --> 00:40:27,830
ti si samo vrsta
odgađanje teško raditi

855
00:40:27,830 --> 00:40:30,360
dok imate popraviti svoje pogreške.

856
00:40:30,360 --> 00:40:33,919
>> I tako, ako možete zamisliti
osam i sedam i šest i pet

857
00:40:33,919 --> 00:40:36,710
a kasnije četiri, a tri i dva
kreće put kroz popis,

858
00:40:36,710 --> 00:40:39,060
smo upravo promijenio
vrsta posla radimo.

859
00:40:39,060 --> 00:40:42,340
Umjesto da radi u
počevši od mog iteracije,

860
00:40:42,340 --> 00:40:45,250
Ja sam samo to radio u
kraj svake iteracije.

861
00:40:45,250 --> 00:40:50,550
Tako ispada da je ovaj algoritam,
također, općenito nazivaju umetanje sortiranje,

862
00:40:50,550 --> 00:40:52,190
Također je na red od n na kvadrat.

863
00:40:52,190 --> 00:40:56,480
To je zapravo ništa bolja,
Nema boljeg na sve.

864
00:40:56,480 --> 00:41:00,810
>> Međutim, postoji i treći pristup
Ja bi nas potaknuti da razmislite,

865
00:41:00,810 --> 00:41:02,970
što je ovo.

866
00:41:02,970 --> 00:41:07,850
Dakle, pretpostavimo da moj popis, zbog jednostavnosti
Ponovno je četiri, jedan, tri,

867
00:41:07,850 --> 00:41:11,080
two-- samo četiri broja.

868
00:41:11,080 --> 00:41:13,300
Ben je imao dobru intuiciju,
dobar čovjek intuicija

869
00:41:13,300 --> 00:41:16,340
prije, kojima smo fiksne cijeli
popis eventually-- umetanja vrsta.

870
00:41:16,340 --> 00:41:18,020
natjerane da nas zajedno.

871
00:41:18,020 --> 00:41:22,530
Ali neka se uzeti u obzir
Najjednostavniji način da se riješi ovaj popis.

872
00:41:22,530 --> 00:41:24,110
>> Ovaj popis nije riješeno.

873
00:41:24,110 --> 00:41:26,130
Zašto?

874
00:41:26,130 --> 00:41:31,920
U engleskom jeziku, objasniti zašto
to nije zapravo riješeno.

875
00:41:31,920 --> 00:41:33,400
Što to znači da ne mogu izdvojiti?

876
00:41:33,400 --> 00:41:34,220
>> STUDENT: To nije linearan.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Malan: Nije sekvencijalno.

878
00:41:34,990 --> 00:41:35,822
Daj mi jedan primjer.

879
00:41:35,822 --> 00:41:37,180
>> STUDENT: Stavi ih u red.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Malan: U redu.

881
00:41:37,440 --> 00:41:38,790
Daj mi više specifičan primjer.

882
00:41:38,790 --> 00:41:39,832
>> STUDENT: uzlaznim redoslijedom.

883
00:41:39,832 --> 00:41:41,206
DAVID Malan: Nije uzlaznim redoslijedom.

884
00:41:41,206 --> 00:41:42,100
Budi precizniji.

885
00:41:42,100 --> 00:41:45,190
Ne znam što misliš pod uzlazno.

886
00:41:45,190 --> 00:41:47,150
Što nije u redu?

887
00:41:47,150 --> 00:41:49,930
>> STUDENT: Najmanji od
Brojevi nije u prvom prostoru.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Malan: Najmanji broj je
ne u prvom prostoru.

889
00:41:51,140 --> 00:41:52,120
Budi određeniji.

890
00:41:52,120 --> 00:41:55,000
Počinjem shvaćati.

891
00:41:55,000 --> 00:41:59,470
Brojimo, ali
ono što je izvan reda ovdje?

892
00:41:59,470 --> 00:42:00,707
>> STUDENT: Numerički slijed.

893
00:42:00,707 --> 00:42:02,040
DAVID Malan: Numerički slijed.

894
00:42:02,040 --> 00:42:04,248
Svatko je vrsta čuvanja
to here-- vrlo visoku razinu.

895
00:42:04,248 --> 00:42:07,450
Samo doslovno mi reći što je
krivo kao pet-godišnje moći.

896
00:42:07,450 --> 00:42:08,310
>> STUDENT: plus jedan.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Malan: Što je to?

898
00:42:08,750 --> 00:42:09,610
>> STUDENT: plus jedan.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Malan: Što misliš plus jedan?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Daj mi drugačiji od pet godina.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Što nije u redu, mama?

904
00:42:18,330 --> 00:42:19,940
Što nije u redu, tata?

905
00:42:19,940 --> 00:42:22,808
Što misliš to nije razvrstani?

906
00:42:22,808 --> 00:42:24,370
>> STUDENT: To nije pravo mjesto.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Malan: Što je
nije na pravom mjestu?

908
00:42:25,580 --> 00:42:26,174
>> STUDENT: Četiri.

909
00:42:26,174 --> 00:42:27,090
DAVID Malan: OK, dobro.

910
00:42:27,090 --> 00:42:29,110
Dakle, četiri nije tamo gdje bi trebao biti.

911
00:42:29,110 --> 00:42:30,590
Konkretno, je li to u redu?

912
00:42:30,590 --> 00:42:33,000
Četiri i jedan prvi
dva broja ja vidim.

913
00:42:33,000 --> 00:42:34,930
Je li to u redu?

914
00:42:34,930 --> 00:42:36,427
Ne, oni su iz reda, zar ne?

915
00:42:36,427 --> 00:42:38,135
U stvari, mislim da je sada
o računalu, previše.

916
00:42:38,135 --> 00:42:40,824
To može samo gledati na možda jedan,
možda dvije stvari na once--

917
00:42:40,824 --> 00:42:43,240
i zapravo samo jedna stvar
u isto vrijeme, ali može barem

918
00:42:43,240 --> 00:42:45,790
pogledajte jednu stvar onda
Sljedeća stvar tik do nje.

919
00:42:45,790 --> 00:42:47,380
>> Tako su to u redu?

920
00:42:47,380 --> 00:42:48,032
Naravno da ne.

921
00:42:48,032 --> 00:42:48,740
Dakle, znate što?

922
00:42:48,740 --> 00:42:51,020
Zašto ne uzeti dijete
korake kako riješiti ovaj problem

923
00:42:51,020 --> 00:42:53,410
umjesto da radi ove maštu
algoritmi poput Bena, gdje je

924
00:42:53,410 --> 00:42:56,440
on je na neki način popravljanja strane
petlje kroz popis

925
00:42:56,440 --> 00:42:59,670
umjesto da radiš ono što sam učinio, gdje
Ja samo vrsta je fiksiran kao idemo?

926
00:42:59,670 --> 00:43:03,650
Recimo samo doslovno razbiti
Pojam order-- brojčanom redoslijedu,

927
00:43:03,650 --> 00:43:06,990
nazovite ga što god want--
u tim parovima usporedbe.

928
00:43:06,990 --> 00:43:07,590
>> Četiri i jedan.

929
00:43:07,590 --> 00:43:09,970
Je li to ispravan nalog?

930
00:43:09,970 --> 00:43:11,310
Tako ćemo popraviti.

931
00:43:11,310 --> 00:43:14,700
Jedan i četiri, a onda
mi ćemo samo kopirati to.

932
00:43:14,700 --> 00:43:15,560
U redu, dobro.

933
00:43:15,560 --> 00:43:17,022
fiksna sam jedan i četiri.

934
00:43:17,022 --> 00:43:18,320
Tri i dva?

935
00:43:18,320 --> 00:43:18,820
Ne.

936
00:43:18,820 --> 00:43:21,690
Neka moje riječi odgovara prste.

937
00:43:21,690 --> 00:43:23,695
Četiri i tri?

938
00:43:23,695 --> 00:43:27,930
>> To nije u redu, pa ću
napraviti jedan, tri, četiri, dva.

939
00:43:27,930 --> 00:43:28,680
OK Dobro.

940
00:43:28,680 --> 00:43:32,310
Sada četiri i dva?

941
00:43:32,310 --> 00:43:33,370
Moramo popraviti ovo.

942
00:43:33,370 --> 00:43:36,700
Dakle, jedan, tri, dva, četiri.

943
00:43:36,700 --> 00:43:39,820
Tako je to razvrstani?

944
00:43:39,820 --> 00:43:43,170
Ne, ali je to bliže razvrstani?

945
00:43:43,170 --> 00:43:48,930
>> To je zato što fiksne ovo
pogreška, fiksne mi ovu grešku,

946
00:43:48,930 --> 00:43:50,370
a mi fiksne ovu pogrešku.

947
00:43:50,370 --> 00:43:52,420
Tako smo fiksne tri greške nedvojbeno.

948
00:43:52,420 --> 00:43:58,100
Još se zapravo ne izgleda riješeno, ali
to je objektivno bliža sortirati

949
00:43:58,100 --> 00:44:00,080
jer smo fiksne neke od tih pogrešaka.

950
00:44:00,080 --> 00:44:02,047
>> Sada što da učinim?

951
00:44:02,047 --> 00:44:03,630
Ja vrsta došla do kraja popisa.

952
00:44:03,630 --> 00:44:05,680
Činilo se da sam fiksni
sve pogreške, ali ne.

953
00:44:05,680 --> 00:44:08,510
Budući da u ovom slučaju, neki brojevi
možda u obliku mjehurića se bliži

954
00:44:08,510 --> 00:44:10,410
na druge brojeve koji
su još uvijek izvan reda.

955
00:44:10,410 --> 00:44:12,951
Tako ćemo to učiniti opet, i ja ću
upravo to učiniti na mjestu ovaj put.

956
00:44:12,951 --> 00:44:14,170
Jedan i tri?

957
00:44:14,170 --> 00:44:14,720
U redu je.

958
00:44:14,720 --> 00:44:16,070
Tri i dva?

959
00:44:16,070 --> 00:44:17,560
Naravno ne, pa neka je to promijeniti.

960
00:44:17,560 --> 00:44:19,160
Dakle, dva, tri.

961
00:44:19,160 --> 00:44:21,340
Tri i četiri?

962
00:44:21,340 --> 00:44:24,370
A sada neka je samo biti
osobito pedantan ovdje.

963
00:44:24,370 --> 00:44:26,350
Je li izdvojiti?

964
00:44:26,350 --> 00:44:29,280
Ti ljudi znaju da je riješeno.

965
00:44:29,280 --> 00:44:30,400
>> Trebao bih probati ponovno.

966
00:44:30,400 --> 00:44:31,900
Dakle, Olivia predlaže pokušam ponovno.

967
00:44:31,900 --> 00:44:32,530
Zašto?

968
00:44:32,530 --> 00:44:35,810
Budući da računalo nema
raskoš naše ljudske oči

969
00:44:35,810 --> 00:44:38,080
samo gledajući back-- OK, ja sam učinio.

970
00:44:38,080 --> 00:44:41,610
Kako se računalo odrediti
da je popis sada je sortiran?

971
00:44:41,610 --> 00:44:44,590
Mehanički.

972
00:44:44,590 --> 00:44:47,650
>> Ja bi trebao ići kroz
još jednom, i to samo ako sam

973
00:44:47,650 --> 00:44:51,190
ne čine / pronaći bilo kakve pogreške mogu
onda zaključiti kako je računalo, yep,

974
00:44:51,190 --> 00:44:51,980
mi smo dobro ide.

975
00:44:51,980 --> 00:44:54,850
Dakle, jedan i dva, dva i
tri, tri i četiri.

976
00:44:54,850 --> 00:44:58,030
Sada sam se definitivno može reći da je ovo
riješeno, jer sam napravio nikakve promjene.

977
00:44:58,030 --> 00:45:01,940
Sada će biti bug i samo
glupo ako sam, računalo,

978
00:45:01,940 --> 00:45:05,640
upita ona ista pitanja opet
očekujući različite odgovore.

979
00:45:05,640 --> 00:45:07,110
ne bi trebalo dogoditi.

980
00:45:07,110 --> 00:45:08,600
>> I tako sada Popis je sortiran.

981
00:45:08,600 --> 00:45:12,630
Nažalost, vrijeme rada
Ovaj algoritam je također n na kvadrat.

982
00:45:12,630 --> 00:45:13,130
Zašto?

983
00:45:13,130 --> 00:45:19,520
Budući da imate n broj, te u
najgorem slučaju morate premjestiti n brojeva

984
00:45:19,520 --> 00:45:23,637
n puta jer morate nastaviti
nazad na provjeru i potencijalno popraviti

985
00:45:23,637 --> 00:45:24,220
ti brojevi.

986
00:45:24,220 --> 00:45:26,280
I mi možemo učiniti više
formalna analiza, previše.

987
00:45:26,280 --> 00:45:29,530
>> Dakle, to je sve što za reći da smo uzeti
tri različita pristupa, jedan

988
00:45:29,530 --> 00:45:32,210
od njih odmah intuitivno
isključiti šišmiš iz Benu

989
00:45:32,210 --> 00:45:35,170
mom predložene umetanja
sortirati na ovaj

990
00:45:35,170 --> 00:45:38,540
gdje se vrsta izgubiti iz vida
šuma za drveće početku.

991
00:45:38,540 --> 00:45:41,760
Ali onda, ako se uzme jedan korak nazad,
voila smo popravili sortiranje pojam.

992
00:45:41,760 --> 00:45:43,824
Dakle, ovo je, usudio bih se reći,
niža razina možda

993
00:45:43,824 --> 00:45:45,740
nego neki od onih drugih
algoritmi, ali neka je

994
00:45:45,740 --> 00:45:48,550
vidi ako ne možemo vizualizirati
to putem ovoga.

995
00:45:48,550 --> 00:45:51,450
>> Dakle, ovo je nešto lijepo
softver koji je netko

996
00:45:51,450 --> 00:45:56,110
napisao je korištenjem šarene trake koja se
učiniti sljedeće za nas.

997
00:45:56,110 --> 00:45:57,736
Svaka od tih šipki predstavlja broj.

998
00:45:57,736 --> 00:46:00,026
Viši bar, veći
broj, manji bar,

999
00:46:00,026 --> 00:46:00,990
manji broj.

1000
00:46:00,990 --> 00:46:05,880
Dakle, idealno želimo lijep piramida
gdje počinje mala i dobiva veliki,

1001
00:46:05,880 --> 00:46:08,330
a to bi značilo da
ti barovi su razvrstani.

1002
00:46:08,330 --> 00:46:11,200
Tako ću ići naprijed i birati,
Na primjer, Benova algoritam

1003
00:46:11,200 --> 00:46:13,990
first-- odabir vrsta.

1004
00:46:13,990 --> 00:46:16,220
>> A primijetiti ono što radi.

1005
00:46:16,220 --> 00:46:18,670
Način na koji su si izabrali
vizualizirati ovaj algoritam

1006
00:46:18,670 --> 00:46:22,090
je da, baš kao što sam bio
hodanje kroz moje liste,

1007
00:46:22,090 --> 00:46:24,710
ovaj program je hodanje
preko svog popisa brojeva,

1008
00:46:24,710 --> 00:46:28,160
isticanje u roza svakom
broj koji se gleda.

1009
00:46:28,160 --> 00:46:32,360
A što će se dogoditi upravo sada?

1010
00:46:32,360 --> 00:46:35,154
>> Najmanji broj koji
I ili Ben pronašao odjednom

1011
00:46:35,154 --> 00:46:36,820
dobiva se preselili na početak popisa.

1012
00:46:36,820 --> 00:46:40,037
I primijetiti jesu neprihvaćanju
broj koji je bio tamo,

1013
00:46:40,037 --> 00:46:41,120
i to je savršeno u redu.

1014
00:46:41,120 --> 00:46:42,600
Nisam se u tom razinom detalja.

1015
00:46:42,600 --> 00:46:44,308
Ali trebamo staviti
taj broj negdje,

1016
00:46:44,308 --> 00:46:47,775
pa smo ga samo preselili na
otvorena spot koji je izrađen.

1017
00:46:47,775 --> 00:46:49,900
Tako ću ubrzati ova
gore, jer inače

1018
00:46:49,900 --> 00:46:51,871
postaje vrlo zamoran brzo.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animacija speed-- tamo idemo.

1021
00:46:58,600 --> 00:47:01,850
Tako sada isti princip
Bio sam nanošenja, ali ti

1022
00:47:01,850 --> 00:47:06,540
možete početi osjećati algoritam, ako
hoću, ili ga malo jasnije.

1023
00:47:06,540 --> 00:47:13,190
I to algoritam ima učinak
Odabirom sljedeći najmanji element,

1024
00:47:13,190 --> 00:47:16,422
tako da ćeš početi
vidi se rampa na lijevoj strani.

1025
00:47:16,422 --> 00:47:19,130
I na svakoj iteraciji, kao što sam
predložio, to ne malo manje posla.

1026
00:47:19,130 --> 00:47:21,921
To ne mora da ide sve na putu
natrag na lijevom kraju popisa,

1027
00:47:21,921 --> 00:47:23,900
jer je već
zna one su razvrstani.

1028
00:47:23,900 --> 00:47:28,129
Tako je vrsta osjeća kao da je
ubrzava, iako je svaki korak

1029
00:47:28,129 --> 00:47:29,420
uzimajući istu količinu vremena.

1030
00:47:29,420 --> 00:47:31,600
Postoji samo manje korake.

1031
00:47:31,600 --> 00:47:35,240
A sada možete vrsta osjetiti
Algoritam čišćenje kraj nje,

1032
00:47:35,240 --> 00:47:37,040
i doista sada je riješeno.

1033
00:47:37,040 --> 00:47:41,620
>> Dakle, umetanje sorta je sve učinio.

1034
00:47:41,620 --> 00:47:43,600
Moram ponovno slučajnom polje.

1035
00:47:43,600 --> 00:47:45,940
I primijetit ja mogu samo
držati ga randomizirano,

1036
00:47:45,940 --> 00:47:50,630
a mi ćemo dobiti približan
Isti pristup, umetanje vrsta.

1037
00:47:50,630 --> 00:47:55,050
Dopustite mi da to uspori do ovdje.

1038
00:47:55,050 --> 00:47:56,915
Počnimo da više.

1039
00:47:56,915 --> 00:47:57,414
Stop.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Idemo preskočiti četiri.

1042
00:48:02,410 --> 00:48:03,200
Idemo tamo.

1043
00:48:03,200 --> 00:48:04,190
Nasumce su niz.

1044
00:48:04,190 --> 00:48:05,555
I ovdje smo go-- umetanja vrsta.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Igrati.

1047
00:48:12,800 --> 00:48:17,280
Obavijest da je to bave svaki
Element naiđe odmah,

1048
00:48:17,280 --> 00:48:20,282
ali ako to spada u
Obavijest krivo mjesto

1049
00:48:20,282 --> 00:48:21,740
sve o radu koji mora dogoditi.

1050
00:48:21,740 --> 00:48:24,700
Moramo držati se kreće više
i više elemenata kako bi napravili mjesta

1051
00:48:24,700 --> 00:48:27,340
za onoga želimo staviti na mjesto.

1052
00:48:27,340 --> 00:48:30,740
>> Tako ćemo se usredotočiti na
Lijevi kraj samo popis.

1053
00:48:30,740 --> 00:48:34,460
Obavijest nismo ni pogledao at-- mi
nisu označene u ružičastom ništa

1054
00:48:34,460 --> 00:48:35,610
nadesno.

1055
00:48:35,610 --> 00:48:38,180
Mi samo bave
problemi kako idemo,

1056
00:48:38,180 --> 00:48:40,430
ali mi stvara puno
raditi za sebe i dalje.

1057
00:48:40,430 --> 00:48:44,410
I tako, ako smo brzinu ovo gore
sada da ide do kraja,

1058
00:48:44,410 --> 00:48:46,210
ona ima drugačiji osjećaj za njega, istina.

1059
00:48:46,210 --> 00:48:50,150
To je samo s naglaskom na lijevom kraju, ali
radi malo više posla kao needed--

1060
00:48:50,150 --> 00:48:53,230
vrsta izglađivanje stvari
više, popravljajući stvari,

1061
00:48:53,230 --> 00:48:58,350
ali se bave konačnici s
svaki element jedan po jedan

1062
00:48:58,350 --> 00:49:07,740
dok ne dođemo do the-- dobro, mi
svi znamo kako će se to završiti,

1063
00:49:07,740 --> 00:49:09,700
tako da je malo underwhelming možda.

1064
00:49:09,700 --> 00:49:12,830
>> No, popis u end--
spoiler-- će biti riješeno.

1065
00:49:12,830 --> 00:49:15,300
Pa pogledajmo jedan posljednji.

1066
00:49:15,300 --> 00:49:16,840
Ne možemo preskočiti.

1067
00:49:16,840 --> 00:49:18,000
Mi smo skoro tamo.

1068
00:49:18,000 --> 00:49:19,980
Dva ići, jedan.

1069
00:49:19,980 --> 00:49:22,680
I voila.

1070
00:49:22,680 --> 00:49:23,450
Izvrsno.

1071
00:49:23,450 --> 00:49:27,220
>> Dakle, sada ćemo napraviti jedan posljednji,
ponovno randomizirano s bubble sort.

1072
00:49:27,220 --> 00:49:31,690
I obavijest ovdje, pogotovo ako sam ga usporiti
dolje, to ne vodi swooping preko.

1073
00:49:31,690 --> 00:49:36,830
Ali primijetit to samo čini par po par,
comparisons-- vrsta lokalnih rješenja.

1074
00:49:36,830 --> 00:49:39,050
No, čim smo dobili
kraj popisa na roza,

1075
00:49:39,050 --> 00:49:40,690
što će se morati ponoviti?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Da, to će morati
početi ispočetka, jer je to jedini

1078
00:49:46,830 --> 00:49:49,870
fiksni parovima greške.

1079
00:49:49,870 --> 00:49:53,120
I to je možda otkrila još druge.

1080
00:49:53,120 --> 00:49:58,950
I tako, ako ubrzati ovaj gore, vi ćete
vidjeti da, mnogo kao i ime implicira,

1081
00:49:58,950 --> 00:50:01,870
manji elements-- ili bolje rečeno,
veće elements-- počinju

1082
00:50:01,870 --> 00:50:03,740
mjehurić do vrha, ako hoćete.

1083
00:50:03,740 --> 00:50:07,380
I manji elementi
s početkom u mjehuru dolje lijevo.

1084
00:50:07,380 --> 00:50:10,780
I doista, to je vrsta
vizualni efekt, kao dobro.

1085
00:50:10,780 --> 00:50:17,150
I tako će to završiti završnu obradu
na vrlo sličan način, previše.

1086
00:50:17,150 --> 00:50:19,160
>> Mi ne moramo živjeti
na ovaj jedan.

1087
00:50:19,160 --> 00:50:21,010
Pusti me da otvori ovo sada, previše.

1088
00:50:21,010 --> 00:50:24,040
Postoji nekoliko drugih algoritam za sortiranje
u svijetu, od kojih su neke

1089
00:50:24,040 --> 00:50:25,580
zarobljeni ovdje.

1090
00:50:25,580 --> 00:50:29,960
A pogotovo za učenike koji nisu
nužno vizualna ili matematički,

1091
00:50:29,960 --> 00:50:31,930
kao što smo učinili prije, možemo
Također to audially

1092
00:50:31,930 --> 00:50:34,210
ako se povezati zvuk s ovim.

1093
00:50:34,210 --> 00:50:36,990
I samo za zabavu, ovdje je
nekoliko različitih algoritama,

1094
00:50:36,990 --> 00:50:40,950
a jedan od njih posebno si
će primijetiti zove se "stapaju vrsta."

1095
00:50:40,950 --> 00:50:43,250
>> To je zapravo bitno
bolji algoritam,

1096
00:50:43,250 --> 00:50:45,860
tako da spajanje vrsta, jedan od
one kojima namjeravate vidjeti,

1097
00:50:45,860 --> 00:50:49,170
Nije red n na kvadrat.

1098
00:50:49,170 --> 00:50:57,280
To je na red za n puta log
n, koji je zapravo manji i time

1099
00:50:57,280 --> 00:50:58,940
brže od one druge tri.

1100
00:50:58,940 --> 00:51:00,670
I tu je drugi par
glup one koje ćemo vidjeti.

1101
00:51:00,670 --> 00:51:01,933
>> Dakle, ovdje mi ići s nekim zvukom.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
To je umetanje vrsta, pa opet
to je samo bavi elementima

1104
00:51:10,490 --> 00:51:13,420
kao i oni dolaze.

1105
00:51:13,420 --> 00:51:17,180
To je balon vrsta, tako da je
smatrajući ih parova u isto vrijeme.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
I opet, najveći elementi
su mjehurića do vrha.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Dalje se izbor vrsta.

1110
00:51:41,710 --> 00:51:45,420
To je Benova algoritam, gdje
opet on odabirom iterativno

1111
00:51:45,420 --> 00:51:46,843
sljedeći najmanji element.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
I opet, sada možete zaista čuti da
to je ubrzanje ali samo u mjeri u kojoj

1114
00:51:53,900 --> 00:51:58,230
kao što se to radi sve manje i manje
rad na svakoj iteraciji.

1115
00:51:58,230 --> 00:52:04,170
To je brži jednom, spajanje vrsta,
koji je sortiranje nakupine brojeva

1116
00:52:04,170 --> 00:52:05,971
zajedno i onda ih se kombinira.

1117
00:52:05,971 --> 00:52:07,720
Dakle look-- lijevu
polovica je već riješeno.

1118
00:52:07,720 --> 00:52:14,165
>> Sada je sortiranje desnu polovicu, a
sada će ih kombinirati u jedan.

1119
00:52:14,165 --> 00:52:19,160
To je nešto što se zove "Gnome vrsta."

1120
00:52:19,160 --> 00:52:23,460
A možete vrsta vidi da je
to ide natrag i naprijed,

1121
00:52:23,460 --> 00:52:27,950
popravljajući rad malo i ovdje
tamo prije nego što prijeđe u novi posao.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
I to je to.

1124
00:52:33,692 --> 00:52:36,400
Postoji još jedna vrsta, što je
stvarno samo za akademske svrhe,

1125
00:52:36,400 --> 00:52:40,980
pod nazivom "glupo vrsta", koji se
podatke, sortira ga slučajno,

1126
00:52:40,980 --> 00:52:43,350
a zatim provjerava da li je to riješeno.

1127
00:52:43,350 --> 00:52:47,880
A ako to nije, on ponovno sortira ga
slučajno, provjerava da li je to riješeno,

1128
00:52:47,880 --> 00:52:49,440
a ako ne ponavlja.

1129
00:52:49,440 --> 00:52:52,660
I u teoriji, probabilistically
to će se završiti,

1130
00:52:52,660 --> 00:52:54,140
ali nakon vrlo malo vremena.

1131
00:52:54,140 --> 00:52:56,930
Nije to najviše
učinkovit algoritama.

1132
00:52:56,930 --> 00:53:02,550
Dakle, bilo kakva pitanja o onima
Posebni algoritmi ili ništa

1133
00:53:02,550 --> 00:53:04,720
vezane tamo?

1134
00:53:04,720 --> 00:53:09,430
>> Pa, sada zafrkavati, osim što je sve
ove linije su da sam bio crtež

1135
00:53:09,430 --> 00:53:15,090
i što sam uz pretpostavku računalo
može učiniti ispod haube.

1136
00:53:15,090 --> 00:53:18,650
Ja smatram da su svi od tih brojeva
Držim drawing-- što im je potrebno da se

1137
00:53:18,650 --> 00:53:21,330
pohranjene negdje u memoriji.

1138
00:53:21,330 --> 00:53:24,130
Mi ćemo se riješiti tog tipa sad, previše.

1139
00:53:24,130 --> 00:53:30,110
>> Dakle, komad memorije u
computer-- tako RAM DIMM

1140
00:53:30,110 --> 00:53:35,480
ono što smo tražili jučer, dual
inline memory module-- izgleda ovako.

1141
00:53:35,480 --> 00:53:39,370
A svaki od tih malih crnih žetona
neki broj bajtova, tipično.

1142
00:53:39,370 --> 00:53:44,380
A onda su zlatne igle su poput
žice koje se spajaju na računalo,

1143
00:53:44,380 --> 00:53:47,521
a zeleni silicij odbor je upravo
ono što drži sve zajedno.

1144
00:53:47,521 --> 00:53:48,770
Dakle, što to zapravo znači?

1145
00:53:48,770 --> 00:53:53,180
Ako sam nekako izvući ovu istu sliku,
pretpostavimo zbog jednostavnosti

1146
00:53:53,180 --> 00:53:55,280
da je ovaj DIMM, dual
inline memorijski modul,

1147
00:53:55,280 --> 00:54:00,530
jedan gigabajt RAM-a, jedan gigabajt
memorije, što je koliko bajtova ukupno?

1148
00:54:00,530 --> 00:54:02,100
Jedan gigabajt je koliko je bajtova?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Više od toga.

1151
00:54:06,030 --> 00:54:09,960
1124 je kilogram, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega je milijun.

1153
00:54:11,730 --> 00:54:14,570
Giga je milijardu.

1154
00:54:14,570 --> 00:54:15,070
>> Jesam li lagao?

1155
00:54:15,070 --> 00:54:16,670
Možemo čak i pročitati etiketu?

1156
00:54:16,670 --> 00:54:19,920
To je zapravo 128
gigabajta, tako da je više.

1157
00:54:19,920 --> 00:54:22,130
No, mi ćemo se pretvarati ovo
je samo jedan gigabajt.

1158
00:54:22,130 --> 00:54:25,640
Dakle, to znači da postoji milijarde
bajtova memorije dostupne za mene

1159
00:54:25,640 --> 00:54:29,770
ili 8 milijardi bita, ali idemo
razgovarati u smislu bajtova sada,

1160
00:54:29,770 --> 00:54:30,750
ići naprijed.

1161
00:54:30,750 --> 00:54:36,330
>> Dakle, što znači da je to
jedan bajt, ovo je još jedan bajt,

1162
00:54:36,330 --> 00:54:38,680
ovo je još jedan bajt,
a ako smo htjeli

1163
00:54:38,680 --> 00:54:43,280
biti specifičan da bi morao
izvući milijardu malo kvadrata.

1164
00:54:43,280 --> 00:54:44,320
No, što to znači?

1165
00:54:44,320 --> 00:54:46,420
Pa, neka mi samo uvećanje
u na ovoj slici.

1166
00:54:46,420 --> 00:54:50,900
Ako imam nešto što izgleda
ovako sada, to je četiri bajta.

1167
00:54:50,900 --> 00:54:53,710
>> I tako sam mogao staviti četiri brojeve ovdje.

1168
00:54:53,710 --> 00:54:54,990
Jedan dva tri četiri.

1169
00:54:54,990 --> 00:55:00,170
Ili sam mogao staviti četiri slova ili simbole.

1170
00:55:00,170 --> 00:55:02,620
"Hej!" mogao ići upravo tamo,
jer svaki od slova,

1171
00:55:02,620 --> 00:55:04,370
smo raspravljali ranije,
mogu se prikazati

1172
00:55:04,370 --> 00:55:06,650
s osam bita ili ASCII ili bajt.

1173
00:55:06,650 --> 00:55:09,370
Dakle, drugim riječima, možete
stavi 8 milijardi stvari u

1174
00:55:09,370 --> 00:55:11,137
ovog jednog stick memorije.

1175
00:55:11,137 --> 00:55:14,345
Sad što to znači staviti stvari natrag
natrag na leđa u spomen na ovako?

1176
00:55:14,345 --> 00:55:17,330
To je ono što programer
će nazvati "niz".

1177
00:55:17,330 --> 00:55:21,250
U računalnom programu, ne mislim
o podlozi hardvera, sam po sebi.

1178
00:55:21,250 --> 00:55:24,427
Vi samo misliti o sebi kao vlasništvo
Pristup ukupno milijardu bajtova,

1179
00:55:24,427 --> 00:55:26,010
i možete sve što želite s njim.

1180
00:55:26,010 --> 00:55:27,880
No, za praktičnost
to je općenito korisno

1181
00:55:27,880 --> 00:55:31,202
zadržati svoju memorijsku pravo
jedni pored drugih se ovo sviđa.

1182
00:55:31,202 --> 00:55:33,660
Dakle, ako sam zumirati učinimo
jer mi sigurno ne ide

1183
00:55:33,660 --> 00:55:39,310
privući milijarde malo squares--
pretpostavimo da je ova ploča predstavlja

1184
00:55:39,310 --> 00:55:40,610
da štap memorije sada.

1185
00:55:40,610 --> 00:55:43,800
A ja ću samo izvući što više moj
marker završi davanje me ovdje.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Tako sada imamo štap
memorije na ploči

1188
00:55:52,300 --> 00:55:56,400
koji je dobio jedan, dva, tri, četiri, pet,
šest, jedan, dva, tri, četiri, pet, šest,

1189
00:55:56,400 --> 00:56:01,130
seven-- tako 42 bajtova
memorije na ukupno na ekranu.

1190
00:56:01,130 --> 00:56:01,630
Hvala ti.

1191
00:56:01,630 --> 00:56:02,838
Da, nije mi aritmetika pravu.

1192
00:56:02,838 --> 00:56:05,120
Tako 42 bajta memorije ovdje.

1193
00:56:05,120 --> 00:56:06,660
Dakle, što to zapravo znači?

1194
00:56:06,660 --> 00:56:09,830
Pa, računalni programer
zapravo bi se općenito

1195
00:56:09,830 --> 00:56:12,450
mislite o ovom sjećanju kao upućujc.

1196
00:56:12,450 --> 00:56:16,630
Drugim riječima, svaki od njih
lokacija u memoriji, u hardver,

1197
00:56:16,630 --> 00:56:18,030
ima jedinstvenu adresu.

1198
00:56:18,030 --> 00:56:22,020
>> To nije tako kompliciran kao jedan Brattle
Trg, Cambridge, Mass., 02.138.

1199
00:56:22,020 --> 00:56:23,830
Umjesto toga, to je samo broj.

1200
00:56:23,830 --> 00:56:27,930
To je bajt broj nula, to je
on, ova dva, to je tri,

1201
00:56:27,930 --> 00:56:30,327
a to je 41.

1202
00:56:30,327 --> 00:56:30,910
Pričekaj minutu.

1203
00:56:30,910 --> 00:56:32,510
Mislio sam da sam rekao 42 maloprije.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
počela sam brojati od nule,
tako da je zapravo točno.

1206
00:56:37,772 --> 00:56:40,980
Sada nemamo zapravo ga izvući
kao mreža, a ako ga izvući kao mreža

1207
00:56:40,980 --> 00:56:43,520
Mislim da stvari zapravo
dobiti malo zabludu.

1208
00:56:43,520 --> 00:56:46,650
Što programer bi,
u svom vlastitom umu,

1209
00:56:46,650 --> 00:56:50,310
općenito misli o ovome
memorije kao što je to baš kao i kasetu,

1210
00:56:50,310 --> 00:56:53,340
kao komad samoljepljiva traka
koji samo ide na i na zauvijek

1211
00:56:53,340 --> 00:56:54,980
ili dok ne ponestane memorije.

1212
00:56:54,980 --> 00:56:59,200
Dakle češći način za crtanje
i samo razmišljam o memoriji

1213
00:56:59,200 --> 00:57:03,710
bi se da je to bajt nula,
dva, tri, a onda točka, točka, točkica.

1214
00:57:03,710 --> 00:57:07,650
A imate ukupno 42 takvih bajtova, čak
iako je fizički to bi zapravo

1215
00:57:07,650 --> 00:57:09,480
biti nešto više ovako.

1216
00:57:09,480 --> 00:57:12,850
>> Dakle, ako se sada sjetiti svoje
memorije što je to, baš kao i kasetu,

1217
00:57:12,850 --> 00:57:17,640
to je ono što programer opet
bih nazvao niz memorije.

1218
00:57:17,640 --> 00:57:20,660
A kad želite da se zapravo pohranu
nešto u memoriju računala,

1219
00:57:20,660 --> 00:57:23,290
općenito Čuvati stvari
back-to-back u back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Tako smo se govori o brojevima.

1221
00:57:25,010 --> 00:57:30,880
A kad sam htio riješiti probleme
kao i četiri, jedan, tri, dva,

1222
00:57:30,880 --> 00:57:33,820
iako sam samo bio crtanje
samo brojevi četiri, jedan, tri,

1223
00:57:33,820 --> 00:57:39,490
dva na brodu, računalo će
Stvarno su ove postava u memoriju.

1224
00:57:39,490 --> 00:57:43,347
>> A što će biti sljedeći na
dva u memoriju racunala?

1225
00:57:43,347 --> 00:57:44,680
Pa, nema odgovor na to.

1226
00:57:44,680 --> 00:57:45,770
Mi zapravo ne znamo.

1227
00:57:45,770 --> 00:57:48,200
I tako dugo dok
Računalo ne treba,

1228
00:57:48,200 --> 00:57:51,440
to ne mora brinuti što je sljedeće
brojevima on ne brine o tome.

1229
00:57:51,440 --> 00:57:55,130
A kad sam rekao ranije da je na računalu
mogu samo gledati na jednu adresu u isto vrijeme,

1230
00:57:55,130 --> 00:57:56,170
to je vrsta zašto.

1231
00:57:56,170 --> 00:57:59,490
>> Nije za razliku od rekordnih
player i glava za čitanje

1232
00:57:59,490 --> 00:58:03,030
samo biti u mogućnosti pogledati neki
utor u fizičkom old-school rekord

1233
00:58:03,030 --> 00:58:06,500
u isto vrijeme, na sličan način
mogu se računalo hvala

1234
00:58:06,500 --> 00:58:09,810
svog procesora i njegovog
Intel skup instrukcija,

1235
00:58:09,810 --> 00:58:12,480
među čijim uputama
čita iz memorije

1236
00:58:12,480 --> 00:58:15,590
ili spremiti u memory--
računalo može samo gledati

1237
00:58:15,590 --> 00:58:19,210
na jednom mjestu u isto time--
ponekad kombinacija od njih,

1238
00:58:19,210 --> 00:58:21,770
ali zapravo samo na jednom mjestu u isto vrijeme.

1239
00:58:21,770 --> 00:58:24,770
Dakle, kada smo radili
ovi razni algoritmi,

1240
00:58:24,770 --> 00:58:28,110
Nisam samo pisanje u
vacuum-- četiri, jedan, tri, dva.

1241
00:58:28,110 --> 00:58:30,849
Ti brojevi zapravo pripadaju
negdje fizički u memoriji.

1242
00:58:30,849 --> 00:58:32,890
Dakle, postoje maleni malo
tranzistori ili neki

1243
00:58:32,890 --> 00:58:35,840
elektronike ispod
napa spremanje te vrijednosti.

1244
00:58:35,840 --> 00:58:40,460
>> A ukupno, koliko bita su
uključeni sada, samo da bude jasno?

1245
00:58:40,460 --> 00:58:45,580
Dakle, ovo je četiri bajta ili
sada je ukupno 32 bita.

1246
00:58:45,580 --> 00:58:49,280
Dakle, postoje zapravo 32 nula i
Oni koji čine ove četiri stvari.

1247
00:58:49,280 --> 00:58:52,070
Tu je još ovdje, ali
opet mi nije stalo do toga.

1248
00:58:52,070 --> 00:58:55,120
>> Dakle, sada ćemo postaviti još
Pitanje pomoću memorije,

1249
00:58:55,120 --> 00:58:57,519
jer je na kraju
dana je u suprotnosti.

1250
00:58:57,519 --> 00:59:00,310
Bez obzira što smo mogli učiniti s
računalo, na kraju dan

1251
00:59:00,310 --> 00:59:02,560
hardver je još uvijek
Isto ispod haube.

1252
00:59:02,560 --> 00:59:04,670
Kako bih pohraniti riječ ovdje?

1253
00:59:04,670 --> 00:59:09,710
Pa, riječ je u računalu kao što su
"Hej!" će biti pohranjen samo ovako.

1254
00:59:09,710 --> 00:59:12,300
A ako si htio duže
riječ, možete jednostavno

1255
00:59:12,300 --> 00:59:19,120
prebrisati to i reći nešto
kao što je "zdravo" i pohraniti ovdje.

1256
00:59:19,120 --> 00:59:23,930
>> I tako i ovdje, također, ovaj contiguousness
je zapravo prednost,

1257
00:59:23,930 --> 00:59:26,530
jer računalo može jednostavno
čitati s desna na lijevo.

1258
00:59:26,530 --> 00:59:28,680
No, ovdje je pitanje.

1259
00:59:28,680 --> 00:59:33,480
U kontekstu ove riječi,
h-e-l-l-o, uskličnik,

1260
00:59:33,480 --> 00:59:38,740
Kako bi se računalo zna gdje je
Riječ počinje i gdje završava riječ?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
U kontekstu brojeva
kako se računalo

1263
00:59:43,800 --> 00:59:48,396
znam koliko je slijed
Brojevi ni gdje to počinje?

1264
00:59:48,396 --> 00:59:50,270
Pa, ispada out--
i nećemo ići previše

1265
00:59:50,270 --> 00:59:54,970
u ovu razinu detail--
računala premjestiti stvari okolo u memoriji

1266
00:59:54,970 --> 00:59:57,800
doslovno putem te adrese.

1267
00:59:57,800 --> 01:00:02,080
Tako je u računalu, ako ste
pisanja koda za pohranu stvari

1268
01:00:02,080 --> 01:00:05,800
kao i riječi, što si
stvarno radi piše

1269
01:00:05,800 --> 01:00:11,320
Izrazi koji se sjećaju gdje su u
memoriji računala te riječi.

1270
01:00:11,320 --> 01:00:14,370
Pa neka mi to jako,
vrlo jednostavan primjer.

1271
01:00:14,370 --> 01:00:18,260
>> Ja ću ići naprijed i
otvoriti jednostavan tekst programa,

1272
01:00:18,260 --> 01:00:20,330
a ja ću stvoriti
datoteka zove hello.c.

1273
01:00:20,330 --> 01:00:22,849
Većina ovih informacija mi
neće ići u vrlo detaljno,

1274
01:00:22,849 --> 01:00:25,140
ali ja ću napisati
Program u tom istom jeziku,

1275
01:00:25,140 --> 01:00:31,140
C. To je daleko više zastrašujuće,
Ja smatram, nego ispočetka,

1276
01:00:31,140 --> 01:00:32,490
ali to je vrlo slično u duhu.

1277
01:00:32,490 --> 01:00:34,364
U stvari, to kovrčava
braces-- možete vrsta

1278
01:00:34,364 --> 01:00:37,820
razmišljati o tome što sam upravo učinio što je ovaj.

1279
01:00:37,820 --> 01:00:39,240
>> Učinimo to, zapravo.

1280
01:00:39,240 --> 01:00:45,100
Kada zelena zastava pritisne,
učinite sljedeće.

1281
01:00:45,100 --> 01:00:50,210
Želim ispisati "pozdrav".

1282
01:00:50,210 --> 01:00:51,500
Dakle, ovo je sada pseudokod.

1283
01:00:51,500 --> 01:00:53,000
Ja sam vrsta zamućivanje linije.

1284
01:00:53,000 --> 01:00:56,750
U C, taj jezik sam govori
o, ova linija ispisa Pozdrav

1285
01:00:56,750 --> 01:01:01,940
zapravo postaje "printf" s
neke zagrade i zarez.

1286
01:01:01,940 --> 01:01:03,480
>> No, to je točno ista ideja.

1287
01:01:03,480 --> 01:01:06,730
I to vrlo razumljiv
"Kad zelena zastava kliknuo" postaje

1288
01:01:06,730 --> 01:01:10,182
mnogo više kompliciranih "int glavni nevažeće."

1289
01:01:10,182 --> 01:01:12,890
A to stvarno nema mapiranje,
tako Samo ću ignorirati to.

1290
01:01:12,890 --> 01:01:17,210
No, vitičastim zagradama su poput
zakrivljena slagalice kao što je ovaj.

1291
01:01:17,210 --> 01:01:18,700
>> Dakle, možete vrsta pogoditi.

1292
01:01:18,700 --> 01:01:22,357
Čak i ako ste nikada nije programiran prije,
Što je ovaj program vjerojatno učiniti?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Vjerojatno ispisuje pozdrav
s uskličnikom.

1295
01:01:28,000 --> 01:01:29,150
>> Tako ćemo pokušati.

1296
01:01:29,150 --> 01:01:30,800
Idem da ga spasi.

1297
01:01:30,800 --> 01:01:34,000
A to je, opet, vrlo
stara škola okoliša.

1298
01:01:34,000 --> 01:01:35,420
Ne mogu kliknuti, ne mogu povući.

1299
01:01:35,420 --> 01:01:36,910
Moram upisati naredbe.

1300
01:01:36,910 --> 01:01:41,320
Dakle, želim pokrenuti svoj program, tako da
Možda ću to učiniti, kao što hello.c.

1301
01:01:41,320 --> 01:01:42,292
To je datoteka trčao sam.

1302
01:01:42,292 --> 01:01:43,500
Ali čekajte, Nedostaje mi korak.

1303
01:01:43,500 --> 01:01:46,470
Što smo rekli je potrebno
korak za jezik poput C?

1304
01:01:46,470 --> 01:01:49,470
Ja sam upravo napisao izvora
broj, ali što mi je potrebno?

1305
01:01:49,470 --> 01:01:50,670
Da, treba mi prevodilac.

1306
01:01:50,670 --> 01:01:57,670
Dakle, na moj Mac ovdje, imam
Program pod nazivom GCC, GNU C prevodilac,

1307
01:01:57,670 --> 01:02:03,990
koja mi omogućuje da to učinimo zaokret
moj izvorni kod u, mi ćemo ga nazvati,

1308
01:02:03,990 --> 01:02:04,930
Stroj kod.

1309
01:02:04,930 --> 01:02:10,180
>> I vidim da,
Ponovno, kao što slijedi, ovi

1310
01:02:10,180 --> 01:02:14,090
su nula i one koje sam upravo
izrađen od mog izvornog koda,

1311
01:02:14,090 --> 01:02:15,730
sve nula i jedinica.

1312
01:02:15,730 --> 01:02:17,770
A ako želim pokrenuti
moj program-- se to dogodi

1313
01:02:17,770 --> 01:02:23,010
da se zove a.out za
Povijesna reasons-- "zdravo".

1314
01:02:23,010 --> 01:02:24,070
Mogu ga pokrenuti ponovno.

1315
01:02:24,070 --> 01:02:25,690
Bok bok bok.

1316
01:02:25,690 --> 01:02:27,430
A čini se da se radi.

1317
01:02:27,430 --> 01:02:31,000
>> No, to znači da je negdje u mom
memorije računala su riječi

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, uskličnik.

1319
01:02:35,279 --> 01:02:38,070
I ispostavilo se, baš kao i na stranu,
što računalo će obično

1320
01:02:38,070 --> 01:02:40,550
učiniti tako da se zna gdje je
stvari se počinju i end-- je

1321
01:02:40,550 --> 01:02:42,460
će staviti poseban simbol ovdje.

1322
01:02:42,460 --> 01:02:46,064
I Konvencija je staviti
broj nula na kraju riječi

1323
01:02:46,064 --> 01:02:48,230
tako da znate gdje se
zapravo završava, tako da

1324
01:02:48,230 --> 01:02:52,750
ne držati ispis više
znakova nego što zapravo namjeravaju.

1325
01:02:52,750 --> 01:02:55,400
>> Ali takeaway ovdje, čak
iako je to prilično kompliciranih,

1326
01:02:55,400 --> 01:02:58,140
je da je to u konačnici
relativno jednostavan.

1327
01:02:58,140 --> 01:03:04,550
Ti su dobili neku vrstu kasete, prazan
Prostor na kojem možete pisati pisma.

1328
01:03:04,550 --> 01:03:07,150
Vi jednostavno morate imati
poseban simbol, kao što je samovoljno

1329
01:03:07,150 --> 01:03:10,316
broj nula, staviti na kraju
tvoje riječi tako da se računalo zna,

1330
01:03:10,316 --> 01:03:13,410
oh, ja bi trebao prestati s ispisivanjem kad
Vidim uskličnik.

1331
01:03:13,410 --> 01:03:16,090
Budući da je sljedeća stvar tamo
je ASCII vrijednost nula,

1332
01:03:16,090 --> 01:03:19,125
ili nul znak kao
netko bi to nazvao.

1333
01:03:19,125 --> 01:03:21,500
No, tu je vrsta problema
ovdje, i neka je vratiti

1334
01:03:21,500 --> 01:03:23,320
brojeva za trenutak.

1335
01:03:23,320 --> 01:03:28,720
Pretpostavimo da ja, u stvari,
imaju niz brojeva,

1336
01:03:28,720 --> 01:03:30,730
i pretpostavimo da je
Program Pišem je

1337
01:03:30,730 --> 01:03:34,680
kao razred knjiga za nastavnika
i učitelja.

1338
01:03:34,680 --> 01:03:38,720
I ovaj program mu ili joj omogućuje
upisati rezultate svojih učenika

1339
01:03:38,720 --> 01:03:39,960
na kvizovima.

1340
01:03:39,960 --> 01:03:43,750
I pretpostavimo da je učenik dobiva
100 na njihov prvi kviz, možda

1341
01:03:43,750 --> 01:03:49,920
kao 80 na sljedeći jedan, a zatim i
75, zatim 90 na četvrtom kvizu.

1342
01:03:49,920 --> 01:03:54,150
>> Dakle, u ovom trenutku u priči,
polje je veličine četiri.

1343
01:03:54,150 --> 01:03:58,470
Ne postoji apsolutno više memorije u
računalo, ali je polje, da tako kažemo,

1344
01:03:58,470 --> 01:04:00,350
je veličine četiri.

1345
01:04:00,350 --> 01:04:06,060
Pretpostavimo sada da učitelj želi
dodijeliti peti kviz na klase.

1346
01:04:06,060 --> 01:04:08,510
Pa, jedna od stvari koje je
ili ona će morati učiniti

1347
01:04:08,510 --> 01:04:10,650
Sada je pohraniti dodatnu vrijednost ovdje.

1348
01:04:10,650 --> 01:04:15,490
No, ako je niz nastavnik ima
stvorena u ovom programu je veličine za,

1349
01:04:15,490 --> 01:04:22,440
jedan od problema s nizom je da
ne možete samo držati dodajući da memorije.

1350
01:04:22,440 --> 01:04:26,470
Jer, što ako drugi dio
Program ima riječ "hej" upravo tamo?

1351
01:04:26,470 --> 01:04:29,650
>> Drugim riječima, moja memorija može biti
koristi se za ništa u programu.

1352
01:04:29,650 --> 01:04:33,250
A ako unaprijed sam utipkao, hej,
Želim ulaz četiri kviz rezultate,

1353
01:04:33,250 --> 01:04:34,784
oni mogu ići ovdje i ovdje.

1354
01:04:34,784 --> 01:04:37,700
A ako odjednom se predomislite
kasnije i reći želim peti kviz

1355
01:04:37,700 --> 01:04:40,872
rezultat, ne možeš samo
stavi ga gdje god želite,

1356
01:04:40,872 --> 01:04:42,580
jer što ako se to
memorija se koristi

1357
01:04:42,580 --> 01:04:45,990
nešto else-- neki drugi program
ili neki drugi karakteristika programa

1358
01:04:45,990 --> 01:04:46,910
da radite?

1359
01:04:46,910 --> 01:04:50,650
Dakle, morate razmišljati unaprijed
kako želite za pohranu podataka,

1360
01:04:50,650 --> 01:04:54,480
jer sada ste slikano
sebe u digitalni kutu.

1361
01:04:54,480 --> 01:04:57,280
>> Dakle, učitelj možda umjesto
kažu prilikom pisanja programa

1362
01:04:57,280 --> 01:04:59,360
pohraniti njegov ili njezin
razreda, znaš što?

1363
01:04:59,360 --> 01:05:04,180
Ja ću tražiti,
prilikom pisanja moj program,

1364
01:05:04,180 --> 01:05:12,070
da želim nula, jedan, dva, tri,
četiri, pet, šest, osam razreda ukupno.

1365
01:05:12,070 --> 01:05:15,320
Dakle, jedan, dva, tri, četiri,
pet, šest, sedam, osam.

1366
01:05:15,320 --> 01:05:18,612
Nastavnik može samo preko dodijeliti
memorije prilikom pisanja svoju programa

1367
01:05:18,612 --> 01:05:19,570
i reći, znate što?

1368
01:05:19,570 --> 01:05:22,236
Nikada neću dodijeliti više
od osam kvizova u semestru.

1369
01:05:22,236 --> 01:05:23,130
To je samo lud.

1370
01:05:23,130 --> 01:05:24,470
Nikad neću izdvojiti to.

1371
01:05:24,470 --> 01:05:28,270
Tako da je to način na koji on ili ona ima
fleksibilnost za pohranu rezultatima učenika,

1372
01:05:28,270 --> 01:05:33,010
kao što su 75, 90, a možda i jednim pomoćnim, gdje
student dobio dodatni kredit, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Ali ako se nikad učitelj
koristi ova tri mjesta,

1374
01:05:36,130 --> 01:05:38,860
postoji intuitivno takeaway ovdje.

1375
01:05:38,860 --> 01:05:41,410
On ili ona samo troši prostor.

1376
01:05:41,410 --> 01:05:44,790
Dakle, drugim riječima, ima ova
zajednički kompromis u programiranju

1377
01:05:44,790 --> 01:05:48,241
gdje možete ili dodijeliti
točno onoliko koliko memorije kao što želite,

1378
01:05:48,241 --> 01:05:51,490
Naopako a to je da ste super
efficient-- niste bude razoran

1379
01:05:51,490 --> 01:05:54,640
na all-- ali je downside od kojih
je što ako se predomislite kada

1380
01:05:54,640 --> 01:05:58,780
pomoću programa koji želite pohraniti
više podataka nego što ste namjeravali.

1381
01:05:58,780 --> 01:06:03,030
>> Dakle, možda je rješenje, a onda,
pisati svoje programe na takav način

1382
01:06:03,030 --> 01:06:05,605
da oni koriste više memorije
nego što je zapravo potrebno.

1383
01:06:05,605 --> 01:06:07,730
Na taj način nećeš
upasti u taj problem,

1384
01:06:07,730 --> 01:06:09,730
ali ste se razoran.

1385
01:06:09,730 --> 01:06:12,960
I više memorije vaš program koristi,
kao što je objašnjeno jučer, manje

1386
01:06:12,960 --> 01:06:15,410
memorije koja je dostupna
za ostale programe,

1387
01:06:15,410 --> 01:06:18,790
prije računalo može usporiti
dolje zbog virtualne memorije.

1388
01:06:18,790 --> 01:06:22,670
I tako idealno rješenje bi moglo biti što?

1389
01:06:22,670 --> 01:06:24,610
>> Pod-dodjele izgleda loše.

1390
01:06:24,610 --> 01:06:27,030
Over-alociranje izgleda loše.

1391
01:06:27,030 --> 01:06:31,120
Dakle, ono što bi moglo biti bolje rješenje?

1392
01:06:31,120 --> 01:06:32,390
Preraspodjelom.

1393
01:06:32,390 --> 01:06:33,590
Budite dinamičniji.

1394
01:06:33,590 --> 01:06:37,520
Ne silite sebe da odaberete
priori, na početku, ono što želite.

1395
01:06:37,520 --> 01:06:41,370
A sigurno ne pretjerano izdvojiti,
da ne bude razoran.

1396
01:06:41,370 --> 01:06:45,770
>> I tako bi se postigao taj cilj,
morati baciti ove strukture podataka,

1397
01:06:45,770 --> 01:06:48,100
da tako kažemo, daleko.

1398
01:06:48,100 --> 01:06:51,080
I što programer
obično će koristiti

1399
01:06:51,080 --> 01:06:55,940
je nešto što ne zove
Niz ali vezana lista.

1400
01:06:55,940 --> 01:07:00,860
Drugim riječima, on ili ona će
početi razmišljati o svojoj memoriji

1401
01:07:00,860 --> 01:07:05,280
kao vrsta oblik koji im
može privući na sljedeći način.

1402
01:07:05,280 --> 01:07:08,520
Ako želim pohraniti jedan broj u
program-- tako da je rujan,

1403
01:07:08,520 --> 01:07:12,600
Ja sam dao moje studente kviz; Želim
pohraniti studenata prvi kviz,

1404
01:07:12,600 --> 01:07:16,220
a dobio 100 na it-- I.
idem pitati moje računalo,

1405
01:07:16,220 --> 01:07:19,540
putem programa sam
pisano za jedan komad memorije.

1406
01:07:19,540 --> 01:07:22,570
I ja ću pohraniti
Broj 100 u njemu, i to je to.

1407
01:07:22,570 --> 01:07:24,820
>> Tada je nekoliko tjedana kasnije
a ja dobijem drugi kviz,

1408
01:07:24,820 --> 01:07:27,890
i da je vrijeme da se upišete
u tom 90%, ja odlazim

1409
01:07:27,890 --> 01:07:32,129
pitati računalo, hej, računalo,
mogu li dobiti još jedan komad memorije?

1410
01:07:32,129 --> 01:07:34,170
To će mi dati taj
prazan komad memorije.

1411
01:07:34,170 --> 01:07:39,370
Idem staviti u broj 90,
ali u svom programu nekako other--

1412
01:07:39,370 --> 01:07:42,100
i nećemo brinuti o
sintaksa za učinimo, mi treba

1413
01:07:42,100 --> 01:07:44,430
nekako lanac ove stvari zajedno.

1414
01:07:44,430 --> 01:07:47,430
A ja ću ih lanac skupa s
ono što izgleda kao strijela ovdje.

1415
01:07:47,430 --> 01:07:50,050
>> Treći kviz koji dolazi,
Ja ću reći, hej, računalo,

1416
01:07:50,050 --> 01:07:51,680
daj mi još jedan komad memorije.

1417
01:07:51,680 --> 01:07:54,660
I ja ću staviti dolje
što god to bilo, kao što su 75,

1418
01:07:54,660 --> 01:07:56,920
i moram lanac ovom
zajedno sada nekako.

1419
01:07:56,920 --> 01:08:00,290
Četvrto kviz dolazi zajedno, a možda
to je prema kraju semestra.

1420
01:08:00,290 --> 01:08:03,140
I tog trenutka moj program
Možda korištenjem memorije

1421
01:08:03,140 --> 01:08:05,540
posvuda, posvuda fizički.

1422
01:08:05,540 --> 01:08:08,170
I tako samo za slatkiš, ja sam
će privući ova naprijed

1423
01:08:08,170 --> 01:08:11,260
quiz-- zaboravim što je bilo; ja
da je možda 80 ili something--

1424
01:08:11,260 --> 01:08:12,500
način ovdje.

1425
01:08:12,500 --> 01:08:15,920
>> No, to je u redu, jer je slikovito
Idem izvući ovu liniju.

1426
01:08:15,920 --> 01:08:19,063
Drugim riječima, u stvarnosti,
u hardveru računala,

1427
01:08:19,063 --> 01:08:20,979
Prvi rezultat možda
završiti ovdje, jer to je

1428
01:08:20,979 --> 01:08:22,529
odmah na početku semestra.

1429
01:08:22,529 --> 01:08:25,810
Sljedeći moglo bi se završiti ovdje
jer malo vremena je prošlo

1430
01:08:25,810 --> 01:08:27,210
a program nastavlja raditi.

1431
01:08:27,210 --> 01:08:30,060
Sljedeći rezultat, koji je bio
75, može biti ovdje.

1432
01:08:30,060 --> 01:08:33,420
I posljednji rezultat bi mogao biti
80, što je ovdje.

1433
01:08:33,420 --> 01:08:38,729
>> Dakle, u stvarnosti, fizički, to bi moglo biti
što memorije računala izgleda.

1434
01:08:38,729 --> 01:08:41,569
Ali ovo nije korisna mentalna
paradigma za računalni programer.

1435
01:08:41,569 --> 01:08:44,649
Zašto bi se brinete gdje je
kritički vaši podaci će završiti?

1436
01:08:44,649 --> 01:08:46,200
Vi samo želite spremiti podatke.

1437
01:08:46,200 --> 01:08:49,390
>> To je vrsta kao što su naše rasprave
prije crtanja kocku.

1438
01:08:49,390 --> 01:08:52,200
Zašto te briga što
je kut kocke

1439
01:08:52,200 --> 01:08:53,740
i kako se okrenuti ga izvući?

1440
01:08:53,740 --> 01:08:54,950
Vi samo želite kocku.

1441
01:08:54,950 --> 01:08:57,359
Isto tako ovdje,
Samo želim razred knjige.

1442
01:08:57,359 --> 01:08:59,559
Vi samo želite razmišljati o
ovo kao popis brojeva.

1443
01:08:59,559 --> 01:09:01,350
Koga briga kako je to
ugraditi u hardver?

1444
01:09:01,350 --> 01:09:05,180
>> Tako je apstrakcija sada
je ova slika ovdje.

1445
01:09:05,180 --> 01:09:07,580
To je povezano popis, kao i
programer bi to nazvao,

1446
01:09:07,580 --> 01:09:10,640
ukoliko imate
popis, očito brojeva.

1447
01:09:10,640 --> 01:09:14,990
No, to je povezano u slikama
putem ove strelice,

1448
01:09:14,990 --> 01:09:18,510
i sve te strelice are-- ispod
sjenilo, ako ste znatiželjni,

1449
01:09:18,510 --> 01:09:23,210
Podsjetimo da je naš fizički hardverski ima
adrese nula, jedan, dva, tri, četiri.

1450
01:09:23,210 --> 01:09:28,465
Sve ove strijele su se kao karta
ili upute, u kojem, ako 90 is-- sada

1451
01:09:28,465 --> 01:09:29,090
Dobio sam brojati.

1452
01:09:29,090 --> 01:09:31,750
>> Nula, jedan, dva, tri,
četiri, pet, šest, sedam.

1453
01:09:31,750 --> 01:09:35,640
To izgleda kao 90 na
memorijska adresa broj sedam.

1454
01:09:35,640 --> 01:09:38,460
Sve ove strijele su se
kao mali komadić papira

1455
01:09:38,460 --> 01:09:42,439
da je davanje smjera za
program koji kaže da slijedite ove karte

1456
01:09:42,439 --> 01:09:43,880
doći do položaja sedam.

1457
01:09:43,880 --> 01:09:46,680
I tu ćete naći
studenta drugi rezultat kviz.

1458
01:09:46,680 --> 01:09:52,100
U međuvremenu, 75-- ako sam i dalje ovo,
To je sedam, osam, devet, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Ova druga strelica predstavlja samo
mapa na memorijsku lokaciju 15.

1461
01:09:59,080 --> 01:10:02,550
Ali opet, programer općenito ne
ne brine o ovoj razini detalja.

1462
01:10:02,550 --> 01:10:05,530
I u većini svakom programiranju
Jezik danas, programer

1463
01:10:05,530 --> 01:10:10,490
neće ni znati gdje je u memoriji
ti brojevi su zapravo.

1464
01:10:10,490 --> 01:10:14,830
Sve što on ili ona mora brinuti o je
koji su na neki način povezani

1465
01:10:14,830 --> 01:10:18,390
u strukture podataka kao što je ovaj.

1466
01:10:18,390 --> 01:10:21,580
>> No, ispostavilo se ne
da se previše tehnički.

1467
01:10:21,580 --> 01:10:27,430
Ali samo zato što možda može
priuštiti da imaju ovu raspravu ovdje,

1468
01:10:27,430 --> 01:10:33,630
Pretpostavljam da smo ponovno
ovo pitanje ovdje u polje.

1469
01:10:33,630 --> 01:10:35,780
Da vidimo žalimo se ovdje događa.

1470
01:10:35,780 --> 01:10:42,950
To je 100, 90, 75 i 80.

1471
01:10:42,950 --> 01:10:44,980
>> Dopustite mi da ukratko bi ovu tvrdnju.

1472
01:10:44,980 --> 01:10:48,980
To je niz, a opet,
Istaknuta karakteristika niza

1473
01:10:48,980 --> 01:10:52,400
je da sve svoje podatke je natrag
natrag na leđa u memory-- doslovno

1474
01:10:52,400 --> 01:10:56,830
jedan bajt ili možda četiri bajta,
neki fiksni broj bajtova daleko.

1475
01:10:56,830 --> 01:11:00,710
U povezanom popisu, koje smo mogli izvući
ovako, ispod poklopca motora koji

1476
01:11:00,710 --> 01:11:02,000
zna gdje je to stvar je?

1477
01:11:02,000 --> 01:11:03,630
To ni ne treba da teče ovako.

1478
01:11:03,630 --> 01:11:06,050
Neki podaci mogu biti
natrag na lijevo gore.

1479
01:11:06,050 --> 01:11:07,530
Vi ni ne znaju.

1480
01:11:07,530 --> 01:11:15,430
>> I tako s nizom, imate
značajka poznat kao slučajni pristup.

1481
01:11:15,430 --> 01:11:20,570
A što Random Access sredstvo
koje računalo može skočiti odmah

1482
01:11:20,570 --> 01:11:22,730
na bilo koje mjesto u nizu.

1483
01:11:22,730 --> 01:11:23,580
Zašto?

1484
01:11:23,580 --> 01:11:26,000
Budući da računalo zna
da je prva lokacija

1485
01:11:26,000 --> 01:11:29,540
nula, jedan, dva, tri,

1486
01:11:29,540 --> 01:11:33,890
>> I tako, ako želite ići od
ovaj element na sljedeći element,

1487
01:11:33,890 --> 01:11:36,099
doslovno, u
računala um, samo dodati.

1488
01:11:36,099 --> 01:11:39,140
Ako želite ići na treći element
samo dodajte one-- sljedeći element, samo

1489
01:11:39,140 --> 01:11:40,290
dodati.

1490
01:11:40,290 --> 01:11:42,980
Međutim, u ovoj verziji
priče, recimo

1491
01:11:42,980 --> 01:11:46,080
računalo trenutno gleda
na ili se bave s brojem 100.

1492
01:11:46,080 --> 01:11:49,770
Kako ste dobili na sljedeću
grade u knjizi razred?

1493
01:11:49,770 --> 01:11:52,560
>> Morate uzeti sedam
koraka, koji je proizvoljna.

1494
01:11:52,560 --> 01:11:58,120
Da biste dobili na sljedeću, morate
uzeti još osam koraka doći do 15 godina.

1495
01:11:58,120 --> 01:12:02,250
Drugim riječima, to nije
konstantan razmak između brojeva,

1496
01:12:02,250 --> 01:12:04,857
pa to samo uzima
Računalo više vremena je točka.

1497
01:12:04,857 --> 01:12:06,940
Računalo mora tražiti
kroz memoriju kako

1498
01:12:06,940 --> 01:12:08,990
kako bi pronašli ono što tražite.

1499
01:12:08,990 --> 01:12:14,260
>> Dakle, dok je niz teži da bude
brzo podaci structure-- zbog vas

1500
01:12:14,260 --> 01:12:17,610
doslovno može samo učiniti jednostavna aritmetička
i dobili gdje želite dodavanjem jednog,

1501
01:12:17,610 --> 01:12:21,300
za instance-- povezanog popisa,
li žrtvovati tu značajku.

1502
01:12:21,300 --> 01:12:24,020
Ne možeš samo otići iz prvog
do drugog na treće mjesto na četvrtom mjestu.

1503
01:12:24,020 --> 01:12:25,240
Morate slijediti kartu.

1504
01:12:25,240 --> 01:12:28,160
Morate uzeti više koraka
doći do tih vrijednosti, koje

1505
01:12:28,160 --> 01:12:30,230
Čini se da se dodavanjem troškova.

1506
01:12:30,230 --> 01:12:35,910
Tako smo plaćati cijenu, ali ono što je
značajka koja je Dan traži ovdje?

1507
01:12:35,910 --> 01:12:38,110
Što povezani popis
očito nam omogućiti da učinite,

1508
01:12:38,110 --> 01:12:40,240
koji je podrijetlo
ova priča?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Točno.

1511
01:12:43,830 --> 01:12:46,220
Dinamična veličina na njega.

1512
01:12:46,220 --> 01:12:48,040
Možemo dodati na ovaj popis.

1513
01:12:48,040 --> 01:12:51,430
Možemo čak i smanjiti popis, tako da
da smo samo pomoću što više memorije

1514
01:12:51,430 --> 01:12:55,560
što mi zapravo želimo i tako
mi smo nikad pretjerano dodjele.

1515
01:12:55,560 --> 01:12:58,470
>> Sada samo da se stvarno NIT-izbirljiva,
postoji skrivenih troškova.

1516
01:12:58,470 --> 01:13:01,980
Tako da ne treba samo neka mi uvjeriti
li da je to uvjerljiv kompromis.

1517
01:13:01,980 --> 01:13:04,190
Postoji još jedan skriveni troškovi ovdje.

1518
01:13:04,190 --> 01:13:06,550
Korist, da bude jasno,
je da smo dobili dinamiku.

1519
01:13:06,550 --> 01:13:10,359
Ako želim još jedan element, samo da mogu
izvući ga i staviti broj u tamo.

1520
01:13:10,359 --> 01:13:12,150
I onda ja to mogu povezati
sa slikom ovdje

1521
01:13:12,150 --> 01:13:14,970
dok je ovdje, opet, ako sam
naslikao sebe u kut,

1522
01:13:14,970 --> 01:13:19,410
ako je nešto drugo već koristi
sjećanje ovdje, ja sam od sreće.

1523
01:13:19,410 --> 01:13:21,700
Ja sam sebe naslikao u kutu.

1524
01:13:21,700 --> 01:13:24,390
>> No, ono što je skriveno
cijene na ovoj slici?

1525
01:13:24,390 --> 01:13:27,690
To je ne samo iznos
vremena koje je potrebno

1526
01:13:27,690 --> 01:13:29,870
ići odavde do ovdje,
što je sedam koraka, a zatim

1527
01:13:29,870 --> 01:13:32,820
Osam koraka, što je više nego jednom.

1528
01:13:32,820 --> 01:13:34,830
Što je još jedan skriveni troškovi?

1529
01:13:34,830 --> 01:13:35,440
Ne samo vremena.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Dodatne informacije
potrebne za postizanje ovu sliku.

1532
01:13:49,940 --> 01:13:53,210
>> Da, to karta, one malo komadići
papir, kao što sam držati opisujući ih kao.

1533
01:13:53,210 --> 01:13:55,650
To arrows-- oni nisu slobodni.

1534
01:13:55,650 --> 01:13:57,660
Computer-- znaš
što računalo ima.

1535
01:13:57,660 --> 01:13:58,790
Ona ima nula i jedinica.

1536
01:13:58,790 --> 01:14:03,170
Ako želite predstavlja strijelu, ili njegov
map ili broj, trebate neke memorije.

1537
01:14:03,170 --> 01:14:05,950
Dakle, s druge cijenu koju
platiti za povezanu listu,

1538
01:14:05,950 --> 01:14:09,070
zajednička računalna znanost
resursa, je i prostor.

1539
01:14:09,070 --> 01:14:11,710
>> I doista je tako, tako često,
među tradeoffs

1540
01:14:11,710 --> 01:14:15,580
u izradi softverskog inženjerstva
sustava je vrijeme i space--

1541
01:14:15,580 --> 01:14:18,596
su dvije od svojih sastojaka, dva
svojim najčešće skupih sastojaka.

1542
01:14:18,596 --> 01:14:21,220
To je koštalo mi još vremena
jer moram slijediti tu kartu,

1543
01:14:21,220 --> 01:14:25,730
ali i košta me više prostora
jer moram zadržati ovu kartu okolo.

1544
01:14:25,730 --> 01:14:28,730
Tako je nada, jer mi smo vrsta
raspravljalo tijekom jučerašnjeg dana i danas,

1545
01:14:28,730 --> 01:14:31,720
je da su prednosti
će prevagnuti troškove.

1546
01:14:31,720 --> 01:14:33,870
>> Ali nema Očito rješenje ovdje.

1547
01:14:33,870 --> 01:14:35,870
Možda je better--
la brz i prljav,

1548
01:14:35,870 --> 01:14:38,660
kao Kareem predložio earlier--
baciti memorije na problem.

1549
01:14:38,660 --> 01:14:42,520
Dovoljno je kupiti više memorije, mislim manje
teško o rješavanju problema,

1550
01:14:42,520 --> 01:14:44,595
i riješiti ga na lakši način.

1551
01:14:44,595 --> 01:14:46,720
I doista ranije, kada
razgovarali smo o tradeoffs,

1552
01:14:46,720 --> 01:14:49,190
to nije bilo prostora u
računalo i vrijeme.

1553
01:14:49,190 --> 01:14:51,810
To je bio razvijen vrijeme, koje
još je jedan izvor.

1554
01:14:51,810 --> 01:14:54,829
>> Pa opet, to je ovaj čin balansiranja
pokušavajući odlučiti koji od tih stvari

1555
01:14:54,829 --> 01:14:55,870
ste spremni potrošiti?

1556
01:14:55,870 --> 01:14:57,380
Koji je najjeftiniji?

1557
01:14:57,380 --> 01:15:01,040
Koji daje bolje rezultate?

1558
01:15:01,040 --> 01:15:01,540
Da?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Doista.

1561
01:15:12,580 --> 01:15:15,970
U tom slučaju, ako ste
predstavlja brojeve u maps--

1562
01:15:15,970 --> 01:15:18,820
nazivaju se u mnogim jezicima
"upućuje" ili "adrese" -

1563
01:15:18,820 --> 01:15:20,390
to je dvostruko više prostora.

1564
01:15:20,390 --> 01:15:24,390
To ne mora biti tako loše kao dvostruki ako
sada mi samo spremanje brojeva.

1565
01:15:24,390 --> 01:15:27,410
Pretpostavimo da smo spremanje
zapisi o bolesnicima u hospital--

1566
01:15:27,410 --> 01:15:30,870
pa Piersonovu imena, telefonskih brojeva,
brojevi socijalnog osiguranja, liječnik

1567
01:15:30,870 --> 01:15:31,540
povijest.

1568
01:15:31,540 --> 01:15:34,160
Ovaj okvir može biti puno,
puno veći, u kojem slučaju

1569
01:15:34,160 --> 01:15:38,000
maleni malo pokazivač, adresu
sljedeći element-- to nije velika stvar.

1570
01:15:38,000 --> 01:15:40,620
To je takva skuta
košta to ne smeta.

1571
01:15:40,620 --> 01:15:43,210
No, u ovom slučaju, da, to je udvostručenje.

1572
01:15:43,210 --> 01:15:45,290
Dobro pitanje.

1573
01:15:45,290 --> 01:15:47,900
>> Razgovarajmo o vremenu a
malo konkretnije.

1574
01:15:47,900 --> 01:15:50,380
Što je vrijeme izvršavanja
traženja ovaj popis?

1575
01:15:50,380 --> 01:15:53,640
Recimo ja sam htjela za pretraživanje
kroz sve razrede studenata,

1576
01:15:53,640 --> 01:15:55,980
a tu je n ocjene
u ovoj strukturi podataka.

1577
01:15:55,980 --> 01:15:58,830
Ovdje, također, možemo posuditi
Vokabular ranije.

1578
01:15:58,830 --> 01:16:00,890
To je linearna struktura podataka.

1579
01:16:00,890 --> 01:16:04,570
>> Big O n je ono što je potrebno da se
na kraju ove strukture podataka,

1580
01:16:04,570 --> 01:16:08,410
whereas-- i nismo vidjeli
ovo before-- niz vam daje

1581
01:16:08,410 --> 01:16:13,555
ono što se naziva konstanta vrijeme, što znači
korak ili dva koraka ili 10 steps--

1582
01:16:13,555 --> 01:16:14,180
ne smeta.

1583
01:16:14,180 --> 01:16:15,440
To je fiksni broj.

1584
01:16:15,440 --> 01:16:17,440
To nema nikakve veze s
veličina polja.

1585
01:16:17,440 --> 01:16:20,130
A razlog za to,
opet, s izravnim pristupom.

1586
01:16:20,130 --> 01:16:23,180
Računalo može samo odmah
skok na drugo mjesto,

1587
01:16:23,180 --> 01:16:27,770
jer oni su svi isti
udaljenost od svega ostalog.

1588
01:16:27,770 --> 01:16:29,112
Nema razmišljanja su uključeni.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
U redu.

1591
01:16:32,400 --> 01:16:39,230
Dakle, ako mogu, neka me pokušaju
slikati dvije konačne slike.

1592
01:16:39,230 --> 01:16:42,830
Vrlo čest jedna poznata kao hash tablicu.

1593
01:16:42,830 --> 01:16:51,120
Tako motivirati ovu raspravu,
neka mi misliti o tome kako to učiniti.

1594
01:16:51,120 --> 01:16:52,610
>> Pa kako o tome?

1595
01:16:52,610 --> 01:16:55,160
Pretpostavimo da je problem
želimo riješiti sada

1596
01:16:55,160 --> 01:16:58,360
provodi se u dictionary--
pa cijela hrpa engleskih riječi

1597
01:16:58,360 --> 01:16:59,330
ili bilo što drugo.

1598
01:16:59,330 --> 01:17:02,724
A cilj je biti u mogućnosti odgovoriti
Pitanja obliku je to riječ?

1599
01:17:02,724 --> 01:17:04,640
Dakle, želite provesti
čarolija provjeru, samo

1600
01:17:04,640 --> 01:17:07,220
kao fizički rječnik
da možete gledati stvari u.

1601
01:17:07,220 --> 01:17:10,490
Recimo da su to učiniti s nizom.

1602
01:17:10,490 --> 01:17:12,590
Mogao sam to učiniti.

1603
01:17:12,590 --> 01:17:20,756
>> A valjda su riječi od jabuka
a banana i dinja.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
I ne mogu se sjetiti voća
koji počinju s D, tako da smo samo

1606
01:17:26,465 --> 01:17:27,590
će imati tri plodova.

1607
01:17:27,590 --> 01:17:31,510
Dakle, ovo je polje, a mi smo
čuvanje svih tih riječi

1608
01:17:31,510 --> 01:17:34,200
u ovom rječniku, kao polje.

1609
01:17:34,200 --> 01:17:39,350
Pitanje je, dakle, koliko je ostalo
možeš li čuvati te podatke?

1610
01:17:39,350 --> 01:17:43,160
>> Pa, ja sam vrsta varanja ovdje, jer
svaki od ovih slova u riječi

1611
01:17:43,160 --> 01:17:44,490
stvarno pojedinac bajt.

1612
01:17:44,490 --> 01:17:46,740
Dakle, ako sam stvarno htjela biti
nit-izbirljiva, ja stvarno bi trebao

1613
01:17:46,740 --> 01:17:49,600
se podijeli ovo gore u mnogo
manji komadi memorije,

1614
01:17:49,600 --> 01:17:51,289
i da bismo mogli učiniti upravo to.

1615
01:17:51,289 --> 01:17:53,580
Ali ćemo naletjeti na
isti problem kao i prije.

1616
01:17:53,580 --> 01:17:56,674
Što ako, kao što je Merriam Webster ili Oxfordu
radi svaki year-- dodaju riječi

1617
01:17:56,674 --> 01:17:59,340
na dictionary-- mi ne
nužno želite da se bojite

1618
01:17:59,340 --> 01:18:00,780
u kut s polja?

1619
01:18:00,780 --> 01:18:05,710
>> Umjesto toga, možda pametniji pristup
je staviti jabuku u svom čvor ili kutiji,

1620
01:18:05,710 --> 01:18:11,190
rekli bismo, banana, i
onda ovdje imamo dinja.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
A mi niz ove stvari zajedno.

1623
01:18:16,790 --> 01:18:19,980
Dakle, ovo je polje, a
to je popis povezani.

1624
01:18:19,980 --> 01:18:23,300
Ako ne možete baš vidjeti, to je samo
kaže: "polje", a ovaj kaže: "popis".

1625
01:18:23,300 --> 01:18:25,780
>> Dakle, imamo isti
Točni pitanja kao i prije,

1626
01:18:25,780 --> 01:18:28,600
pri čemu mi sada imamo
dinamizam u našem povezanom popisu.

1627
01:18:28,600 --> 01:18:31,090
No, imamo prilično sporo rječnika.

1628
01:18:31,090 --> 01:18:32,870
Pretpostavimo da želim gledati ni riječi.

1629
01:18:32,870 --> 01:18:35,430
To bi moglo potrajati mi veliku O n
koraka, jer je riječ možda

1630
01:18:35,430 --> 01:18:37,840
biti skroz na kraju
popis, kao i dinja.

1631
01:18:37,840 --> 01:18:40,600
I ispada da
u programiranju, sortiranje

1632
01:18:40,600 --> 01:18:42,700
Svetog grala podataka
strukture, je nešto

1633
01:18:42,700 --> 01:18:46,620
koji vam daje konstantan
Vrijeme kao niz

1634
01:18:46,620 --> 01:18:50,870
ali to još uvijek vam daje dinamiku.

1635
01:18:50,870 --> 01:18:52,940
>> Tako možemo imati najbolje od oba svijeta?

1636
01:18:52,940 --> 01:18:55,570
I doista, ima nešto
naziva hash tablicu

1637
01:18:55,570 --> 01:18:59,320
koji vam omogućuje da učinite upravo
da, iako otprilike.

1638
01:18:59,320 --> 01:19:03,140
Hash tablica je ljubitelj
struktura podataka koje smo

1639
01:19:03,140 --> 01:19:06,340
mogu misliti kako je
Kombinacija array--

1640
01:19:06,340 --> 01:19:12,390
i ja ću ga izvući
kao što učinimo i povezanim listama

1641
01:19:12,390 --> 01:19:17,310
da ću nacrtati ovako ovdje.

1642
01:19:17,310 --> 01:19:19,760
>> A način na koji je ova stvar
Radovi se kako slijedi.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Ako se to now-- hash table--
je moj treći struktura podataka,

1645
01:19:29,540 --> 01:19:32,590
i želim se pohraniti
riječi na to, ne znam

1646
01:19:32,590 --> 01:19:35,440
žele samo pohraniti sve od
riječi natrag na leđa na leđa na leđa.

1647
01:19:35,440 --> 01:19:37,430
Želim iskoristiti neke
podatak

1648
01:19:37,430 --> 01:19:40,330
o riječima koje će pustiti
ja ga dobiti gdje je brže.

1649
01:19:40,330 --> 01:19:43,666
>> Dakle, s obzirom na riječi jabuku
a banana i dinja,

1650
01:19:43,666 --> 01:19:45,040
Namjerno sam izabrao te riječi.

1651
01:19:45,040 --> 01:19:45,340
Zašto?

1652
01:19:45,340 --> 01:19:47,631
Koja je vrsta temelja
različito u tri?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Što je očito?

1655
01:19:51,484 --> 01:19:52,900
Počinju sa različitim slovima.

1656
01:19:52,900 --> 01:19:53,900
>> Dakle, znate što?

1657
01:19:53,900 --> 01:19:57,120
Umjesto da stavi sve svoje riječi u
ista kanta, da tako kažemo,

1658
01:19:57,120 --> 01:20:00,390
kao u jednoj velikoj listi, zašto ne
Ja barem isprobati optimizaciju

1659
01:20:00,390 --> 01:20:04,180
i da moji popisi 1/26 dokle.

1660
01:20:04,180 --> 01:20:07,440
Uvjerljiv optimizacija
možda zašto ne

1661
01:20:07,440 --> 01:20:10,650
I-- prilikom umetanja riječi
u ovu strukturu podataka,

1662
01:20:10,650 --> 01:20:14,300
u memoriju računala, zašto
ja ne staviti sve 'A' riječi ovdje,

1663
01:20:14,300 --> 01:20:17,270
svi oznakom 'b' riječi ovdje,
i sve 'c' riječi ovdje?

1664
01:20:17,270 --> 01:20:24,610
Dakle, ovo završi stavljanjem jabuku
Ovdje, banana ovdje, dinja ovdje

1665
01:20:24,610 --> 01:20:25,730
i tako dalje.

1666
01:20:25,730 --> 01:20:31,700
>> A ako imam dodatnih
Riječ volimo-članovima što je još jedan?

1667
01:20:31,700 --> 01:20:36,640
Apple, banana, kruška.

1668
01:20:36,640 --> 01:20:39,370
Svatko misliti na plod
koja počinje sa a, b, ili c?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- savršen.

1670
01:20:40,570 --> 01:20:43,990
To će završiti ovdje.

1671
01:20:43,990 --> 01:20:47,530
I tako mi se čini da imaju
marginalno bolje rješenje,

1672
01:20:47,530 --> 01:20:50,820
jer sada ako želim
u potrazi za jabuke, ja

1673
01:20:50,820 --> 01:20:53,200
first-- ja ne samo roniti
u moju strukture podataka.

1674
01:20:53,200 --> 01:20:54,850
Ja ne zaroniti u memoriji mog računala.

1675
01:20:54,850 --> 01:20:56,530
Prvi put sam, pogledajte prvo slovo.

1676
01:20:56,530 --> 01:20:58,610
>> A to je ono što računalo
znanstvenik će reći.

1677
01:20:58,610 --> 01:21:00,760
Vi raspršiti u svoje strukture podataka.

1678
01:21:00,760 --> 01:21:04,100
Vi uzmite ulaz, koji je u
ovaj slučaj je riječ poput jabuke.

1679
01:21:04,100 --> 01:21:07,150
Možete ga analizirati, gledajući
prvo slovo u ovom slučaju,

1680
01:21:07,150 --> 01:21:08,340
time se raspršivanja.

1681
01:21:08,340 --> 01:21:10,950
Raspršivanja je opći pojam kojim
uzmete nešto kao ulaz

1682
01:21:10,950 --> 01:21:12,116
i proizvoditi neki izlaz.

1683
01:21:12,116 --> 01:21:15,090
A izlaz u tome
Slučaj je lokacija

1684
01:21:15,090 --> 01:21:18,150
Želite li pretraživati, prvi
mjesto, drugo mjesto, treće mjesto.

1685
01:21:18,150 --> 01:21:22,160
Dakle, ulaz je jabuka,
izlaz je na prvom mjestu.

1686
01:21:22,160 --> 01:21:25,054
Ulaz je banana je
Izlaz bi trebao biti drugi.

1687
01:21:25,054 --> 01:21:27,220
Ulaz je dinja,
izlaz bi trebao biti treći.

1688
01:21:27,220 --> 01:21:30,320
Ulaz je borovnica je
Izlaz bi trebao opet biti drugi.

1689
01:21:30,320 --> 01:21:34,010
I to je ono što vam pomaže preuzeti
prečaci kroz memoriju

1690
01:21:34,010 --> 01:21:39,050
kako bi se na riječi
ili podatke učinkovitije.

1691
01:21:39,050 --> 01:21:43,330
>> Sada je to smanjuje naše vrijeme potencijalno
po koliko je jedan od 26,

1692
01:21:43,330 --> 01:21:45,850
jer ako pretpostavimo da vas
imati što više "A" riječi kao što su "z"

1693
01:21:45,850 --> 01:21:48,080
riječi kao "Q", odnosno koji
zapravo nije realistic--

1694
01:21:48,080 --> 01:21:50,830
ti si idući u morati izvrtati preko
određene slova alphabet--

1695
01:21:50,830 --> 01:21:53,204
ali to će biti inkrementalni
pristup koji dopušta

1696
01:21:53,204 --> 01:21:55,930
li doći do riječi mnogo brže.

1697
01:21:55,930 --> 01:21:59,660
A u stvarnosti, sofisticirani
Program je Googleova svijeta,

1698
01:21:59,660 --> 01:22:02,180
Facebooks od svijet-
oni će koristiti hash tablicu

1699
01:22:02,180 --> 01:22:03,740
za puno različitih namjena.

1700
01:22:03,740 --> 01:22:06,590
Ali, oni ne bi bili toliko naivan
samo pogledajte prvo slovo

1701
01:22:06,590 --> 01:22:09,700
u jabuke ili banane ili
kruške ili dinja,

1702
01:22:09,700 --> 01:22:13,420
jer kao što možete vidjeti to
popisi još uvijek mogao dugo.

1703
01:22:13,420 --> 01:22:17,130
>> I tako bi to moglo ipak biti neka vrsta
od linear-- tako nekako sporo,

1704
01:22:17,130 --> 01:22:19,980
kao i sa velikim O n
da smo raspravljali ranije.

1705
01:22:19,980 --> 01:22:25,290
Dakle, što je pravi dobar hash tablicu će
do-- to će imati puno veću lepezu.

1706
01:22:25,290 --> 01:22:28,574
I to će se koristiti mnogo više
sofisticirane funkcije raspršivanja,

1707
01:22:28,574 --> 01:22:30,240
tako da ne samo gledati na "a".

1708
01:22:30,240 --> 01:22:35,480
Možda to izgleda na "a-p-p-l-e" i
nekako pretvara tih pet slova

1709
01:22:35,480 --> 01:22:38,400
u mjestu gdje
Apple bi trebao biti pohranjen.

1710
01:22:38,400 --> 01:22:42,660
Mi samo naivno koristi slovo "A"
sama, jer je lijepo i jednostavno.

1711
01:22:42,660 --> 01:22:44,600
>> No, hash tablicu u
kraj, možete misliti

1712
01:22:44,600 --> 01:22:47,270
u obliku kombinacije
niz, od kojih je svaki

1713
01:22:47,270 --> 01:22:51,700
ima povezanu listu koja je idealno
treba biti što je moguće kraće.

1714
01:22:51,700 --> 01:22:54,364
I to nije očito rješenje.

1715
01:22:54,364 --> 01:22:57,280
U stvari, mnogo fino ugađanje
da ide na ispod haube kada je

1716
01:22:57,280 --> 01:22:59,654
provođenje ove vrste
sofisticirane strukture podataka

1717
01:22:59,654 --> 01:23:01,640
je ono što je pravo
Duljina niza?

1718
01:23:01,640 --> 01:23:03,250
Koji je pravi hash funkcija?

1719
01:23:03,250 --> 01:23:04,830
Kako spremiti stvari u memoriji?

1720
01:23:04,830 --> 01:23:07,249
>> Ali shvatili koliko brzo
ova vrsta rasprave

1721
01:23:07,249 --> 01:23:10,540
eskalirali, bilo tako daleko da je to vrsta
od nad glavom u ovom trenutku, što

1722
01:23:10,540 --> 01:23:11,360
dobro je.

1723
01:23:11,360 --> 01:23:18,820
Ali počeli smo, podsjetimo, s uistinu
nešto niske razine i elektronski.

1724
01:23:18,820 --> 01:23:20,819
I tako opet je to
Tema apstrakcije,

1725
01:23:20,819 --> 01:23:23,610
gdje je nakon što počnete da se za
gotovo, u redu, imam it-- postoji

1726
01:23:23,610 --> 01:23:26,680
fizičke memorije, OK, shvaćam, svaki
fizička lokacija ima adresu,

1727
01:23:26,680 --> 01:23:29,910
U redu, ja sam ga dobio, mogu predstavljati
te adrese kao arrows--

1728
01:23:29,910 --> 01:23:34,650
možete vrlo brzo početi imati
više sofisticirane razgovore koje

1729
01:23:34,650 --> 01:23:38,360
na kraju Čini se da nam omogućava
za rješavanje problema kao što su tražili

1730
01:23:38,360 --> 01:23:41,620
i sortiranje učinkovitije.

1731
01:23:41,620 --> 01:23:44,190
I budite uvjereni, too--
jer mislim da to

1732
01:23:44,190 --> 01:23:48,700
je najdublji smo otišli u neki
tih CS tema proper-- smo

1733
01:23:48,700 --> 01:23:51,880
učinjeno u dan i pol na to
ukazati ono što bi mogli obično učiniti preko

1734
01:23:51,880 --> 01:23:55,520
roku od osam tjedana u semestru.

1735
01:23:55,520 --> 01:23:59,670
>> Bilo kakva pitanja o njima?

1736
01:23:59,670 --> 01:24:01,100
Ne?

1737
01:24:01,100 --> 01:24:01,940
U redu.

1738
01:24:01,940 --> 01:24:05,610
Pa, zašto ne bismo pauzu tamo,
započeti ručak nekoliko minuta ranije,

1739
01:24:05,610 --> 01:24:07,052
nastaviti u samo oko sat vremena?

1740
01:24:07,052 --> 01:24:08,760
A ja ću se vući
malo s pitanjima.

1741
01:24:08,760 --> 01:24:11,343
Onda ću morati otići
potrajati nekoliko poziva ako je to u redu.

1742
01:24:11,343 --> 01:24:15,000
Ja ću okrenuti na neku glazbu u međuvremenu,
ali ručak bi trebao biti oko kutu.

1743
01:24:15,000 --> 01:24:17,862