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

2
00:00:00,030 --> 00:00:00,460
>> DAVID MALAN: W porządku.

3
00:00:00,460 --> 00:00:01,094
Jesteśmy z powrotem.

4
00:00:01,094 --> 00:00:04,260
Tak więc w tym segmencie na temat programowania, co
Myślałam, że robimy to mieszanka rzeczy.

5
00:00:04,260 --> 00:00:06,340
Jeden z nich, zrobić trochę
czegoś hands-on,

6
00:00:06,340 --> 00:00:08,690
aczkolwiek przy użyciu bardziej zabawny
programowanie environment--

7
00:00:08,690 --> 00:00:11,620
taki, który jest poglądowe od
dokładnie te rodzaje pomysłów

8
00:00:11,620 --> 00:00:14,220
rozmawialiśmy o,
ale trochę bardziej formalnie.

9
00:00:14,220 --> 00:00:18,200
Dwa, spojrzeć na niektóre
sposoby bardziej techniczne

10
00:00:18,200 --> 00:00:21,520
że programista faktycznie rozwiąże
Problemy takie jak problem poszukiwania

11
00:00:21,520 --> 00:00:24,530
że przyjrzeliśmy się przed i
również bardziej fundamentalnie

12
00:00:24,530 --> 00:00:26,020
ciekawy problem sortowania.

13
00:00:26,020 --> 00:00:28,840
>> Po prostu zakłada się od uzyskania go
że książka telefoniczna została posortowana,

14
00:00:28,840 --> 00:00:31,980
ale że sam jest w rzeczywistości rodzajem
Trudno problem z wielu różnych sposobów

15
00:00:31,980 --> 00:00:32,479
go rozwiązać.

16
00:00:32,479 --> 00:00:34,366
Więc użyjemy je jako
klasa problemów

17
00:00:34,366 --> 00:00:36,740
Przedstawiciel rzeczy
może być rozwiązany w ogóle.

18
00:00:36,740 --> 00:00:38,980
A potem pogadamy
o dość szczegółowo, co

19
00:00:38,980 --> 00:00:42,360
nazywane są dane structures--
bardziej wyszukane sposoby jak połączonych listach

20
00:00:42,360 --> 00:00:46,290
i tabele mieszania i drzewa, które
programista faktycznie

21
00:00:46,290 --> 00:00:48,890
obsłudze i zazwyczaj używają
na tablicy malować

22
00:00:48,890 --> 00:00:51,840
obraz tego, co on lub ona
przewiduje dla realizacji

23
00:00:51,840 --> 00:00:52,980
niektóre kawałek oprogramowania.

24
00:00:52,980 --> 00:00:55,130
>> Więc zróbmy rąk na części pierwsze.

25
00:00:55,130 --> 00:01:00,090
Więc po prostu dostać w swoje ręce brudne ze związkiem
środowisko zwane scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Jest to narzędzie, którego używamy
w naszym licencjackich klasy.

27
00:01:02,636 --> 00:01:04,510
Mimo, że jest ono przeznaczone
od wieków 12 i do góry

28
00:01:04,510 --> 00:01:07,570
używamy go w górę
część tego całkiem sporo

29
00:01:07,570 --> 00:01:10,020
ponieważ jest to miłe, zabawa
Graficzny sposób uczenia

30
00:01:10,020 --> 00:01:12,160
trochę coś o programowaniu.

31
00:01:12,160 --> 00:01:17,600
Więc głowa do tego adresu URL, gdzie
powinien zobaczyć stronę zupełnie jak ta,

32
00:01:17,600 --> 00:01:23,330
i iść do przodu, a następnie kliknij
Dołącz do podstaw w prawym górnym rogu

33
00:01:23,330 --> 00:01:28,300
i wybrać nazwę użytkownika i
hasło i ostatecznie dostać się

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
Myślałam, że to wykorzystać jako
Pierwsza okazja, aby pokazać to.

37
00:01:34,665 --> 00:01:39,120
Pytanie wpadł podczas przerwy
o tym, co kod faktycznie wygląda.

38
00:01:39,120 --> 00:01:41,315
I rozmawialiśmy
przerwę o C,

39
00:01:41,315 --> 00:01:45,060
w szczególności do: szczególniej
Niższy poziom w starym języku.

40
00:01:45,060 --> 00:01:47,750
A ja po prostu nie szybkie
wyszukiwarki Google, aby znaleźć kod C

41
00:01:47,750 --> 00:01:51,574
dla wyszukiwania binarnego, że algorytm
wykorzystywany do wyszukiwania tę książkę telefoniczną wcześniej.

42
00:01:51,574 --> 00:01:54,240
Ten szczególny przykład oczywiście
nie szukaj książkę telefoniczną.

43
00:01:54,240 --> 00:01:57,840
To po prostu przeszukuje całą masę
Liczby w pamięci komputera.

44
00:01:57,840 --> 00:02:01,000
Ale jeśli chcesz po prostu wizualnym
poczucie tego, co rzeczywiste programowania

45
00:02:01,000 --> 00:02:05,370
Język wygląda, wygląda
trochę coś takiego.

46
00:02:05,370 --> 00:02:09,759
Więc to jest około 20-plus,
30 lub tak wierszy kodu,

47
00:02:09,759 --> 00:02:12,640
ale rozmowa mamy
mieli na przerwie

48
00:02:12,640 --> 00:02:16,000
o tym, jak to było w rzeczywistości
dostaje przekształcił zer i jedynek

49
00:02:16,000 --> 00:02:19,200
a jeśli nie można po prostu wrócić, że
przetwarzać i przejść z zer i jedynek

50
00:02:19,200 --> 00:02:20,210
powrót do kodu.

51
00:02:20,210 --> 00:02:22,620
>> Niestety, proces
jest tak przekształcające

52
00:02:22,620 --> 00:02:24,890
że o wiele łatwiej powiedzieć niż zrobić.

53
00:02:24,890 --> 00:02:29,400
I poszedł do przodu i rzeczywiście okazało
ten program, Binary Search,

54
00:02:29,400 --> 00:02:32,700
do zer i jedynek w drodze
Program zwany kompilator, że

55
00:02:32,700 --> 00:02:34,400
zdarzy się, że tutaj, w prawo na moim Macu.

56
00:02:34,400 --> 00:02:37,850
A jeśli spojrzeć na ekran
tutaj, koncentrując się w szczególności

57
00:02:37,850 --> 00:02:43,520
na tych sześciu środkowych kolumn tylko,
zobaczysz tylko zer i jedynek.

58
00:02:43,520 --> 00:02:48,290
A ci są zer i jedynek, które
skomponowania dokładnie ten program wyszukiwania.

59
00:02:48,290 --> 00:02:53,720
>> I tak każda porcja pięciu bitów,
każdy bajt zer i jedynek tutaj

60
00:02:53,720 --> 00:02:57,310
reprezentują jakąś instrukcję
Zazwyczaj wewnątrz komputera.

61
00:02:57,310 --> 00:03:00,730
I rzeczywiście, jeśli słyszałeś
marketing slogan "Intel inside" - które,

62
00:03:00,730 --> 00:03:04,610
Oczywiście, oznacza to po prostu mieć
Intel CPU lub mózgu wewnątrz komputera.

63
00:03:04,610 --> 00:03:08,000
A co to znaczy być CPU
że masz zestaw instrukcji,

64
00:03:08,000 --> 00:03:08,840
że tak powiem.

65
00:03:08,840 --> 00:03:11,620
>> Każdy procesor na świecie, wielu
im wykonany przez firmę Intel w tych dniach,

66
00:03:11,620 --> 00:03:13,690
rozumie skończonym
liczba instrukcji.

67
00:03:13,690 --> 00:03:18,690
A te instrukcje są tak niskie
jak dodać te dwie liczby,

68
00:03:18,690 --> 00:03:22,560
pomnożyć te dwie liczby,
przenieść ten kawałek danych stąd

69
00:03:22,560 --> 00:03:27,340
tu w pamięci, z wyjątkiem tego
Informacje stąd tu w pamięci,

70
00:03:27,340 --> 00:03:32,200
i tak forth-- tak bardzo
niskiego poziomu, dane prawie elektroniczne.

71
00:03:32,200 --> 00:03:34,780
Ale z tych matematycznych
operacje w połączeniu

72
00:03:34,780 --> 00:03:37,410
z tym, co mówiliśmy wcześniej,
reprezentacja danych

73
00:03:37,410 --> 00:03:40,450
jak zer i jedynek, można
budować wszystko

74
00:03:40,450 --> 00:03:44,180
że komputer może zrobić dzisiaj, czy
to tekstowe, graficzne, muzyczne,

75
00:03:44,180 --> 00:03:45,580
lub w przeciwnym wypadku.

76
00:03:45,580 --> 00:03:49,450
>> Więc to jest bardzo łatwo dostać
zagubiony w chwastów szybko.

77
00:03:49,450 --> 00:03:52,150
I nie ma wiele
składniowych wyzwania

78
00:03:52,150 --> 00:03:56,630
przy czym jeśli się najprostsze,
najgłupsza literówek żadnego programu

79
00:03:56,630 --> 00:03:57,860
będzie działać w ogóle.

80
00:03:57,860 --> 00:04:00,366
I tak, zamiast przy użyciu
język jak C rano,

81
00:04:00,366 --> 00:04:02,240
Myślałem, że byłoby
więcej zabawy faktycznie zrobić

82
00:04:02,240 --> 00:04:04,840
coś bardziej wizualne, które
zaś przeznaczony dla dzieci

83
00:04:04,840 --> 00:04:08,079
jest rzeczywiście doskonały manifestacją
o rzeczywistej programowania

84
00:04:08,079 --> 00:04:10,370
language-- właśnie dzieje
wykorzystywać zdjęcia zamiast tekstu

85
00:04:10,370 --> 00:04:11,710
do reprezentowania tych pomysłów.

86
00:04:11,710 --> 00:04:15,470
>> Więc kiedy rzeczywiście mieć
Konto na scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
kliknij przycisk Utwórz
W lewej górnej części strony.

88
00:04:21,070 --> 00:04:24,620
I powinieneś zobaczyć jak środowisko
jeden mam zamiar zobaczyć na ekranie

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

90
00:04:26,310 --> 00:04:29,350
A my spędzić trochę
Trochę czasu grając tutaj.

91
00:04:29,350 --> 00:04:34,080
Zobaczmy, czy nie możemy wszystkim rozwiązać niektóre
Problemy ze sobą w następujący sposób.

92
00:04:34,080 --> 00:04:39,420
>> Więc to, co zobaczysz w obrębie tego
environment-- i faktycznie po prostu pozwolić

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

94
00:04:40,050 --> 00:04:42,680
Czy ktoś tu nie ma?

95
00:04:42,680 --> 00:04:45,070
Nie tutaj?

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

97
00:04:45,800 --> 00:04:49,030
Więc pozwól mi zwrócić uwagę na kilka
Właściwości tego środowiska.

98
00:04:49,030 --> 00:04:55,024
>> Więc w lewym górnym rogu ekranu, mamy
mają etap Scratch jest, że tak powiem.

99
00:04:55,024 --> 00:04:57,440
Scratch jest nie tylko nazwa
tego języka programowania;

100
00:04:57,440 --> 00:05:00,356
jest to również nazwa kota, który
widać tam domyślnie w kolorze pomarańczowym.

101
00:05:00,356 --> 00:05:02,160
On jest na scenie, więc
tak jak opisałem

102
00:05:02,160 --> 00:05:05,770
żółw wcześniej jako bycie w
prostokątna biała środowiska pokładzie.

103
00:05:05,770 --> 00:05:09,800
Tego kota świat ogranicza się do końca
do tego prostokąta up there górze.

104
00:05:09,800 --> 00:05:12,210
>> W międzyczasie, po prawej
hand side tutaj, to

105
00:05:12,210 --> 00:05:15,610
tylko obszar skrypty, A
tabula rasa, jeśli będzie.

106
00:05:15,610 --> 00:05:18,590
To gdzie będziemy pisać
Nasze programy za chwilę.

107
00:05:18,590 --> 00:05:22,935
A cegiełki, że będziemy
użyć do napisania tego program-- zagadkę

108
00:05:22,935 --> 00:05:25,310
sztuk, jeśli są will--
te właśnie tu, w środku,

109
00:05:25,310 --> 00:05:27,500
i są skategoryzowane
przez funkcjonalność.

110
00:05:27,500 --> 00:05:31,000
Tak więc, na przykład, mam zamiar iść do przodu
i wykazują co najmniej jedną z nich.

111
00:05:31,000 --> 00:05:33,690
Mam zamiar iść do przodu, a następnie kliknij
kategoria sterowania maksymalnie górze.

112
00:05:33,690 --> 00:05:35,720
>> Więc to są kategorie up górze.

113
00:05:35,720 --> 00:05:39,410
Idę kliknij kategorię sterowania.

114
00:05:39,410 --> 00:05:44,020
Raczej będę kliknij Events
kategorii, pierwszy na prowadzenie w góry.

115
00:05:44,020 --> 00:05:47,790
A jeśli chcesz podążać nawet
jak to zrobić, jesteś bardzo mile widziane.

116
00:05:47,790 --> 00:05:52,180
Idę kliknąć i przeciągnąć tę
Pierwszy z nich, "gdy zielona flaga kliknięciu".

117
00:05:52,180 --> 00:05:58,410
A potem mam zamiar upuść go po prostu
z grubsza na szczycie moich pustych łupki.

118
00:05:58,410 --> 00:06:01,450
>> I co jest miłe o Scratch
jest to, że ten kawałek układanki, kiedy

119
00:06:01,450 --> 00:06:04,560
zblokowane z drugiej układanki
sztuk, zrobi dosłownie

120
00:06:04,560 --> 00:06:06,460
co te kawałki układanki powiedzieć robić.

121
00:06:06,460 --> 00:06:09,710
Tak więc, na przykład, Scratch ma rację
Teraz w środku jego świata.

122
00:06:09,710 --> 00:06:14,660
Mam zamiar iść do przodu i wybrać
Teraz, powiedzmy, w kategorii Motion,

123
00:06:14,660 --> 00:06:18,000
jeśli chcesz wykonać
same-- kategorię Motion.

124
00:06:18,000 --> 00:06:20,430
A teraz muszę zauważyć całość
pęczek puzzli tutaj

125
00:06:20,430 --> 00:06:23,370
że kolejny rodzaj robić to, co mówią.

126
00:06:23,370 --> 00:06:28,110
I zamierzam iść do przodu i przeciągnąć
upuść bloku Przesuń w prawo tutaj.

127
00:06:28,110 --> 00:06:31,860
>> I zauważ, że tak szybko, jak można dostać
blisko dna "zieloną flagą

128
00:06:31,860 --> 00:06:34,580
kliknął przycisk ", zawiadomienie
Jak pojawi się biała linia,

129
00:06:34,580 --> 00:06:36,950
jakby to prawie
magnetyczne, chce tam iść.

130
00:06:36,950 --> 00:06:43,070
Wystarczy puścić, a to przystawki
razem i kształty będą pasować.

131
00:06:43,070 --> 00:06:46,620
I teraz można chyba prawie
odgadnąć, gdzie jedziemy z tym.

132
00:06:46,620 --> 00:06:51,570
>> Jeśli spojrzeć na etapie Scratch
tu i patrzeć na wierzchu,

133
00:06:51,570 --> 00:06:55,142
zobaczysz czerwone światło,
znak stopu i zieloną flagę.

134
00:06:55,142 --> 00:06:57,100
I zamierzam iść do przodu
i oglądać moje screen--

135
00:06:57,100 --> 00:06:58,460
na chwilę, jeśli można.

136
00:06:58,460 --> 00:07:01,960
Idę kliknij
Zielona flaga teraz,

137
00:07:01,960 --> 00:07:07,850
i przeniósł się co wydaje się być 10 kroków
lub 10 pikseli, 10 kropki na ekranie.

138
00:07:07,850 --> 00:07:13,390
>> A więc nie tak ekscytujące,
ale pozwól mi zaproponować

139
00:07:13,390 --> 00:07:17,440
nawet nie uczy tego, po prostu
przy użyciu własnego własnego intuition-- let

140
00:07:17,440 --> 00:07:22,560
ja proponuję, aby dowiedzieć się, w jaki sposób
dokonać Scratch spacer tuż przy scenie.

141
00:07:22,560 --> 00:07:28,700
Czy mu ustąpić po prawej stronie
ekran, aż po prawej stronie.

142
00:07:28,700 --> 00:07:32,200
Podam chwilę
lub tak, aby walczyć z tym.

143
00:07:32,200 --> 00:07:37,681
Czasami warto spojrzeć
w innych kategoriach bloków.

144
00:07:37,681 --> 00:07:38,180
W porządku.

145
00:07:38,180 --> 00:07:41,290
Więc po prostu zakręcić, gdy mamy
zielona flaga kliknięciu tutaj

146
00:07:41,290 --> 00:07:44,850
i przejść 10 kroków jest
tylko instrukcja, za każdym razem

147
00:07:44,850 --> 00:07:46,720
kliknij zieloną flagę, co się dzieje?

148
00:07:46,720 --> 00:07:50,070
Dobrze, że mój program jest uruchomiony.

149
00:07:50,070 --> 00:07:52,450
Więc może to zrobić
może 10 razy ręcznie

150
00:07:52,450 --> 00:07:55,130
ale czuje się trochę
nieco hackish, że tak powiem,

151
00:07:55,130 --> 00:07:57,480
przy czym ja naprawdę nie jestem
rozwiązywania problemu.

152
00:07:57,480 --> 00:08:00,530
Próbuję tylko raz i
znowu i znowu i znowu

153
00:08:00,530 --> 00:08:03,180
aż rodzaju przypadek
osiągnąć dyrektywę

154
00:08:03,180 --> 00:08:05,560
że chciał osiągnąć wcześniej.

155
00:08:05,560 --> 00:08:08,200
>> Ale wiemy z
pseudokod wcześniej, że nie ma

156
00:08:08,200 --> 00:08:11,870
Pojęcie to w programowaniu pętli,
robić coś znowu i znowu.

157
00:08:11,870 --> 00:08:14,888
I tak widziałem, że grono Ciebie
sięgnął po kawałek układanki, co?

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

159
00:08:17,870 --> 00:08:18,730
Powtarzaj aż.

160
00:08:18,730 --> 00:08:21,400
Więc możemy coś zrobić
jak powtarzać aż.

161
00:08:21,400 --> 00:08:23,760
I co pan powtórzyć, aż dokładnie?

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

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

164
00:08:28,540 --> 00:08:31,974
I pozwól mi iść z takim, który jest
nieco prostsze przez chwilę.

165
00:08:31,974 --> 00:08:33,140
Pozwólcie mi iść do przodu i to zrobić.

166
00:08:33,140 --> 00:08:35,559
Należy zauważyć, że, jak można mieć
odkryto pod kontrolą,

167
00:08:35,559 --> 00:08:38,409
nie jest to powtórzenie bloku, który
nie wygląda na to, że jest duży.

168
00:08:38,409 --> 00:08:41,039
Niewiele pokoju
między tymi dwoma żółtymi liniami.

169
00:08:41,039 --> 00:08:43,539
Ale jak niektórzy z was mogą mieć
Zauważyłem, jeśli przeciągnij i upuść,

170
00:08:43,539 --> 00:08:45,150
zauważyć, jak to rośnie do wypełnienia kształtu.

171
00:08:45,150 --> 00:08:46,274
>> I można nawet dopchać więcej.

172
00:08:46,274 --> 00:08:48,670
To będzie po prostu stale rosnąć, jeśli
przeciągnij i unoszą się nad nim.

173
00:08:48,670 --> 00:08:51,110
A ja nie wiem, co jest
Najlepszym tutaj, więc pozwól

174
00:08:51,110 --> 00:08:54,760
mnie przynajmniej powtórzyć pięć razy, na
instancji, a następnie wrócić na scenę

175
00:08:54,760 --> 00:08:56,720
i kliknij zieloną flagę.

176
00:08:56,720 --> 00:08:59,110
A teraz zauważyć, że nie jest całkiem tam.

177
00:08:59,110 --> 00:09:02,400
>> Teraz niektórzy z was proponowany jako
Victoria po prostu nie, powtórz 10 razy.

178
00:09:02,400 --> 00:09:05,140
I to na ogół robi
zabrać go przez całą drogę,

179
00:09:05,140 --> 00:09:10,510
ale nie tam być bardziej wytrzymałe
sposób niż zastanawianie się arbitralnie

180
00:09:10,510 --> 00:09:12,640
jak wiele ruchów zrobić?

181
00:09:12,640 --> 00:09:17,680
Co może być lepszego bloku
niż powtórzyć 10 razy być?

182
00:09:17,680 --> 00:09:20,380
>> Tak, więc dlaczego nie zrobić czegoś na zawsze?

183
00:09:20,380 --> 00:09:24,390
A teraz pozwól mi przenieść ten kawałek układanki
Wewnątrz i pozbyć się tego.

184
00:09:24,390 --> 00:09:28,300
Zauważmy teraz nieważne gdzie Scratch
rozpoczyna się, idzie do brzegu.

185
00:09:28,300 --> 00:09:30,700
I na szczęście MIT,
który sprawia, że ​​nowa, po prostu

186
00:09:30,700 --> 00:09:33,190
upewnia się, że nigdy
znika całkowicie.

187
00:09:33,190 --> 00:09:35,360
Zawsze można chwycić ogonem.

188
00:09:35,360 --> 00:09:37,680
>> I tak intuicyjnie,
dlaczego on ruszać?

189
00:09:37,680 --> 00:09:38,892
Co tu się dzieje?

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

191
00:09:41,440 --> 00:09:43,824
Wydaje się, że zatrzymał się, ale
Następnie, jeśli mogę odebrać i przeciągnij

192
00:09:43,824 --> 00:09:45,240
Trzyma chcąc iść tam.

193
00:09:45,240 --> 00:09:46,123
Dlaczego?

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

195
00:09:51,610 --> 00:09:54,360
Zaprawdę, komputer jest dosłownie
zrobi to, czego powiedzieć to zrobić.

196
00:09:54,360 --> 00:09:58,380
Więc jeśli to powiedziano wcześniej, wykonaj
następujące rzeczy zawsze, przenieść 10 kroków,

197
00:09:58,380 --> 00:10:01,860
to się nie poddawać się i odchodzą
dopóki nie uderzył w czerwony znak stopu

198
00:10:01,860 --> 00:10:04,620
i zatrzymać program w ogóle.

199
00:10:04,620 --> 00:10:06,610
>> Więc nawet jeśli nie
to zrobić, jak mogłem

200
00:10:06,610 --> 00:10:09,510
dokonać Scratch szybciej
po ekranie?

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

202
00:10:12,060 --> 00:10:13,280
Więcej kroków, prawda?

203
00:10:13,280 --> 00:10:15,710
Więc zamiast robić 10
na raz, dlaczego nie

204
00:10:15,710 --> 00:10:20,100
iść dalej i zmienić go to--
co byś propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Więc teraz mam zamiar kliknąć zielony
flaga i rzeczywiście idzie bardzo szybko.

206
00:10:24,410 --> 00:10:27,180
>> I to, oczywiście, jest po prostu
przejawem animacji.

207
00:10:27,180 --> 00:10:28,060
Czym jest animacja?

208
00:10:28,060 --> 00:10:33,090
To jest po prostu pokazujące ludzkich a
cała masa zdjęć wciąż naprawdę,

209
00:10:33,090 --> 00:10:34,160
naprawdę szybko.

210
00:10:34,160 --> 00:10:36,500
I tak, jeśli mamy tylko mówię
żeby przenieść więcej kroków,

211
00:10:36,500 --> 00:10:39,750
jesteśmy tylko o efekt być
Zmiana gdzie on jest na ekranie

212
00:10:39,750 --> 00:10:42,900
bardziej gwałtownie na jednostkę czasu.

213
00:10:42,900 --> 00:10:46,454
>> Teraz kolejnym wyzwaniem, które zaproponowałem
było mieć go odbijają się od krawędzi.

214
00:10:46,454 --> 00:10:49,120
I nie wiedząc, co logiczna
sztuk exist-- bo to jest w porządku

215
00:10:49,120 --> 00:10:53,030
jeśli nie dostać się do
etap challenge-- co

216
00:10:53,030 --> 00:10:54,280
chcesz zrobić intuicyjnie?

217
00:10:54,280 --> 00:10:58,030
Jak mielibyśmy mu odbijać i
dalej, pomiędzy lewym i prawym?

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

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

220
00:11:03,810 --> 00:11:05,680
Więc musimy jakąś
stanu, i

221
00:11:05,680 --> 00:11:09,710
Wydaje się, że warunkowe, tak aby
niejako w kategorii sterowania.

222
00:11:09,710 --> 00:11:14,110
Które z tych bloków
mamy prawdopodobnie chcesz?

223
00:11:14,110 --> 00:11:15,200
Tak, może ", jeśli potem."

224
00:11:15,200 --> 00:11:18,780
Tak więc zauważyć, że wśród żółtych blokach
Mamy tu, nie jest to "jeśli"

225
00:11:18,780 --> 00:11:23,920
czy ta "if, else" bloku, który będzie
pozwalają nam podjąć decyzję, aby to zrobić

226
00:11:23,920 --> 00:11:25,000
czy to zrobić.

227
00:11:25,000 --> 00:11:27,380
I można je nawet gniazdo
zrobić wiele rzeczy.

228
00:11:27,380 --> 00:11:34,910
Albo jeśli nie odeszłaś tu jeszcze
idź do kategorii Sensing

229
00:11:34,910 --> 00:11:39,612
and-- zobaczmy, czy to tutaj.

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

231
00:11:43,050 --> 00:11:52,050
>> Więc co może być pomocne bloku tutaj
wykryć, czy jest on poza sceną?

232
00:11:52,050 --> 00:11:56,740
Tak, zauważyć, że niektóre z tych bloków
Możliwa jest parametryzacja, że ​​tak powiem.

233
00:11:56,740 --> 00:12:00,706
Mogą one być dostosowane rodzaju nie
w przeciwieństwie do HTML wczoraj z atrybutami

234
00:12:00,706 --> 00:12:03,330
gdzie te atrybuty rodzaju
dostosować zachowanie etykiety.

235
00:12:03,330 --> 00:12:08,880
Podobnie tutaj, mogę pobrać ten dotknięcia
bloku i zmiana i zadać sobie pytanie,

236
00:12:08,880 --> 00:12:11,500
ty dotykania myszy
wskaźnik jak kursora

237
00:12:11,500 --> 00:12:13,250
czy może dotykać krawędzi?

238
00:12:13,250 --> 00:12:15,210
>> Więc pozwól mi iść i to zrobić.

239
00:12:15,210 --> 00:12:18,130
Mam zamiar pomniejszyć przez chwilę.

240
00:12:18,130 --> 00:12:21,320
Pozwól mi pobrać ten kawałek układanki
tutaj, to ten kawałek układanki,

241
00:12:21,320 --> 00:12:24,570
a ja zamierzam jumble
im się przez chwilę.

242
00:12:24,570 --> 00:12:27,620
Mam zamiar przenieść tego,
zmienić na dotykania krawędzi,

243
00:12:27,620 --> 00:12:38,590
a ja jadę do ruchu to zrobić.

244
00:12:38,590 --> 00:12:40,490
Więc oto kilka składników.

245
00:12:40,490 --> 00:12:42,570
Myślę, że mam wszystko, co chcę.

246
00:12:42,570 --> 00:12:47,710
>> Czy ktoś chciał zaproponować jak ja
Może można podłączyć je od góry do dołu

247
00:12:47,710 --> 00:12:52,020
W celu rozwiązania tego problemu konieczności
Scratch ruch od prawej do lewej do prawej, aby

248
00:12:52,020 --> 00:12:57,020
od lewej do prawej strony do lewej, z których każda
Czas po prostu odbijając się od ściany?

249
00:12:57,020 --> 00:12:58,050
Co chcę robić?

250
00:12:58,050 --> 00:13:01,097
Który blok należy podłączyć do
"Kiedy zielona flaga kliknięciu pierwszy"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, więc zacznijmy z "zawsze".

253
00:13:06,200 --> 00:13:07,170
To, co dzieje się wewnątrz następny?

254
00:13:07,170 --> 00:13:10,290
Ktoś inny.

255
00:13:10,290 --> 00:13:11,850
OK, przesuń kroki.

256
00:13:11,850 --> 00:13:12,350
W porządku.

257
00:13:12,350 --> 00:13:14,470
Więc co?

258
00:13:14,470 --> 00:13:15,120
Więc wtedy, gdy.

259
00:13:15,120 --> 00:13:17,720
I zauważył, mimo to wygląda
wciśnięte razem mocno,

260
00:13:17,720 --> 00:13:19,500
będzie to tylko rosnąć, aby wypełnić.

261
00:13:19,500 --> 00:13:21,500
To po prostu wskoczyć gdzie chcę go.

262
00:13:21,500 --> 00:13:25,920
>> I co mogę umieścić między
if a potem?

263
00:13:25,920 --> 00:13:27,180
Prawdopodobnie ", jeśli dotyka krawędzi".

264
00:13:27,180 --> 00:13:31,800
A informacja, ponownie, jest zbyt duży
za to, ale będzie rosnąć do wypełnienia.

265
00:13:31,800 --> 00:13:35,002
A następnie skręcić o 15 stopni?

266
00:13:35,002 --> 00:13:35,710
Ile stopni?

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

268
00:13:38,800 --> 00:13:41,196
Tak, więc 180 będzie wirować
mnie dookoła.

269
00:13:41,196 --> 00:13:42,570
Zobaczmy więc, czy mam takie prawo.

270
00:13:42,570 --> 00:13:43,930
Pozwól mi pomniejszyć.

271
00:13:43,930 --> 00:13:45,130
>> Pozwól mi przeciągnij Scratch górę.

272
00:13:45,130 --> 00:13:50,030
Więc trochę zniekształcone
teraz, ale to jest w porządku.

273
00:13:50,030 --> 00:13:52,231
Jak mogę przywrócić go łatwo?

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

275
00:13:59,879 --> 00:14:01,045
Zamierzam trochę oszukiwać.

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

277
00:14:04,074 --> 00:14:05,990
Więc dodaję kolejny
Blok, żeby była jasność.

278
00:14:05,990 --> 00:14:08,424
Chcę, żeby wskazywać 90 stopni
w prawo domyślnie

279
00:14:08,424 --> 00:14:10,840
więc jestem po prostu będzie mu powiedzieć
aby to zrobić programowo.

280
00:14:10,840 --> 00:14:11,632
I jedziemy.

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

282
00:14:14,740 --> 00:14:15,740
Wydaje się to zrobić.

283
00:14:15,740 --> 00:14:19,980
To trochę dziwne, bo
on chodzenie do góry nogami.

284
00:14:19,980 --> 00:14:21,250
Nazwijmy to błąd.

285
00:14:21,250 --> 00:14:22,120
To pomyłka.

286
00:14:22,120 --> 00:14:27,320
Błąd to błąd w programie, a
błąd logiczny, że ja, człowiek, wykonana.

287
00:14:27,320 --> 00:14:28,985
Dlaczego on idzie do góry nogami?

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

289
00:14:33,560 --> 00:14:35,250
Czy MIT zepsuć czy ja?

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

291
00:14:38,840 --> 00:14:42,550
>> Tak, to znaczy, że nie jest MIT
wina. Dali mi kawałek układanki

292
00:14:42,550 --> 00:14:44,970
który mówi włączyć jakąś liczbę stopni.

293
00:14:44,970 --> 00:14:47,672
A na sugestię Wiktorii,
Jestem obracając się o 180 stopni,

294
00:14:47,672 --> 00:14:48,880
która jest właściwym intuicji.

295
00:14:48,880 --> 00:14:53,700
Lecz On obrócił się o 180 stopni dosłownie
oznacza obrót o 180 stopni,

296
00:14:53,700 --> 00:14:55,860
a to nie jest tak naprawdę
co chcę, widocznie.

297
00:14:55,860 --> 00:14:58,026
Bo przynajmniej on jest w
to dwuwymiarowy świat,

298
00:14:58,026 --> 00:15:00,740
tak naprawdę się dzieje zwrotnym
odwrócić go do góry nogami.

299
00:15:00,740 --> 00:15:04,030
>> Pewnie chcą wykorzystać to, co blok
Zamiast tego, na podstawie tego co tu widzisz?

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

301
00:15:11,890 --> 00:15:14,790
Jak możemy rozwiązać ten problem?

302
00:15:14,790 --> 00:15:18,380
Tak, więc możemy wskazać
w przeciwnym kierunku.

303
00:15:18,380 --> 00:15:22,300
I rzeczywiście, nawet to
Nie będzie za mało,

304
00:15:22,300 --> 00:15:26,410
ponieważ możemy tylko ciężka kod
wskazując na lewo lub w prawo.

305
00:15:26,410 --> 00:15:27,920
>> Wiesz, co możemy zrobić?

306
00:15:27,920 --> 00:15:30,160
Wygląda na to mamy
Blok o wygodę.

307
00:15:30,160 --> 00:15:32,987
Gdybym powiększyć, patrz
coś, czego się tu podoba?

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

309
00:15:36,120 --> 00:15:40,020
Wygląda więc na to MIT posiada
abstrakcji zbudowany tutaj.

310
00:15:40,020 --> 00:15:45,440
Blok ten wydaje się być równoważne
do których inne bloki, w liczbie mnogiej?

311
00:15:45,440 --> 00:15:49,510
>> To jeden blok wydaje się być równoważne
do tej całej trójki bloków

312
00:15:49,510 --> 00:15:50,880
że mamy tutaj.

313
00:15:50,880 --> 00:15:54,670
Tak więc okazuje się, mogę uprościć moje
Program pozbywając się tego wszystkiego

314
00:15:54,670 --> 00:15:58,270
i po prostu umieścić to tutaj.

315
00:15:58,270 --> 00:16:01,620
A teraz jest jeszcze trochę
buggy, i to jest w porządku teraz.

316
00:16:01,620 --> 00:16:03,370
Zostawimy to będzie.

317
00:16:03,370 --> 00:16:06,000
Ale mój program jest jeszcze
prostsze, a to również

318
00:16:06,000 --> 00:16:09,060
byłaby reprezentatywna
stanowi cel sam w programming--

319
00:16:09,060 --> 00:16:13,430
to najlepiej zrobić swój kod jako
proste, a możliwie jak najbardziej zwartych

320
00:16:13,430 --> 00:16:15,650
a jednocześnie jest tak
odczytu, jak to możliwe.

321
00:16:15,650 --> 00:16:20,310
Nie chcemy, aby było tak zwięzłe
że jest to trudne do zrozumienia.

322
00:16:20,310 --> 00:16:22,826
>> Należy jednak zauważyć, że zastąpiliśmy
trzy bloki z jednym,

323
00:16:22,826 --> 00:16:24,200
i to prawdopodobnie jest dobrą rzeczą.

324
00:16:24,200 --> 00:16:27,280
Mam wydobywane dala pojęcie
sprawdzenia, czy jesteś

325
00:16:27,280 --> 00:16:29,120
na granicy z jednego bloku.

326
00:16:29,120 --> 00:16:31,520
Teraz możemy bawić się z tego w rzeczywistości.

327
00:16:31,520 --> 00:16:35,790
To nie dodaje tyle
wartości intelektualnej, lecz wartość zabawy.

328
00:16:35,790 --> 00:16:39,730
Mam zamiar iść do przodu
i złapać ten dźwięk tutaj.

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

330
00:16:42,900 --> 00:16:46,420
Więc pozwól mi iść do przodu, a niech mnie
zatrzymać program na chwilę.

331
00:16:46,420 --> 00:16:52,070
Zamierzam nagrać następujące,
umożliwiając dostęp do mojego mikrofonu.

332
00:16:52,070 --> 00:16:53,181
>> No to ruszamy.

333
00:16:53,181 --> 00:16:53,680
Ała.

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

335
00:16:58,710 --> 00:17:01,140
Spróbujmy jeszcze raz.

336
00:17:01,140 --> 00:17:02,279
No to ruszamy.

337
00:17:02,279 --> 00:17:03,570
OK, nagrałem coś złego.

338
00:17:03,570 --> 00:17:04,580
No to ruszamy.

339
00:17:04,580 --> 00:17:05,080
Ała.

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

341
00:17:07,910 --> 00:17:08,800
Ała.

342
00:17:08,800 --> 00:17:09,300
W porządku.

343
00:17:09,300 --> 00:17:10,791
Teraz muszę się pozbyć tego.

344
00:17:10,791 --> 00:17:11,290
W porządku.

345
00:17:11,290 --> 00:17:13,950
>> Więc teraz mam
zapis tylko "Ouch".

346
00:17:13,950 --> 00:17:18,040
Więc teraz mam zamiar iść
naprzód i nazywają to "au".

347
00:17:18,040 --> 00:17:20,270
Mam zamiar wrócić
do moich skryptów, a teraz

348
00:17:20,270 --> 00:17:25,460
Ogłoszenie jest ten blok, który się nazywa
odtwarzać dźwięk "meow" lub odtwarzania dźwięku "au".

349
00:17:25,460 --> 00:17:28,920
Mam zamiar przeciągnąć tego, a gdzie
należy umieścić to dla efektu komicznego?

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

351
00:17:31,740 --> 00:17:37,860
Tak, więc teraz to niby
buggy, bo teraz to block--

352
00:17:37,860 --> 00:17:42,050
zauważyć jak to ", jeśli na krawędzi,
bounce "to rodzaj samowystarczalny.

353
00:17:42,050 --> 00:17:43,704
trzeba więc, aby to naprawić.

354
00:17:43,704 --> 00:17:44,870
Pozwólcie mi iść do przodu i to zrobić.

355
00:17:44,870 --> 00:17:48,630
Pozwól mi pozbyć się tego i wrócić
do naszego pierwotnego, bardziej celowe

356
00:17:48,630 --> 00:17:49,870
funkcjonalności.

357
00:17:49,870 --> 00:18:01,080
Tak ", jeśli dotyka krawędzi, a następnie" Chcę
obrócić, zgodnie z propozycją Victoria,

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

359
00:18:02,480 --> 00:18:05,497
I chcę grać
dźwięk "au" istnieje?

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

361
00:18:11,800 --> 00:18:15,580
>> Tak, zauważy to na zewnątrz
że żółty blok.

362
00:18:15,580 --> 00:18:17,680
Więc to też byłoby
bug, ale zauważyłem go.

363
00:18:17,680 --> 00:18:21,290
Więc mam zamiar przeciągnąć go tutaj
i nota teraz jest wewnątrz "if".

364
00:18:21,290 --> 00:18:24,250
Tak więc "jeśli" jest tego rodzaju
podobnego arm-like blot

365
00:18:24,250 --> 00:18:26,260
że tylko będzie
robić to, co znajduje się w jej wnętrzu.

366
00:18:26,260 --> 00:18:30,216
Więc teraz, jeśli pomniejszyć przy
ryzyko annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> Komputer: Ała, au, au.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: I
po prostu iść na zawsze.

370
00:18:39,910 --> 00:18:44,160
Teraz wystarczy, aby przyspieszyć rzeczy
tu, pozwól mi iść do przodu i otworzyć,

371
00:18:44,160 --> 00:18:50,460
niech say-- mnie puścić do niektórych
z własnej rzeczy z klasą.

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

373
00:18:53,000 --> 00:19:00,220
I pozwól mi otworzyć się, powiedzmy, w tym
jeden wykonany przez jednego z naszych towarzyszy dydaktycznych

374
00:19:00,220 --> 00:19:01,500
kilka lat temu.

375
00:19:01,500 --> 00:19:04,732
Więc niektórzy z was mogą przypomnieć
Ta gra z przeszłości,

376
00:19:04,732 --> 00:19:05,940
i to jest rzeczywiście niezwykłe.

377
00:19:05,940 --> 00:19:08,190
Mimo, że zrobiliśmy
Najprostsze programy w tej chwili,

378
00:19:08,190 --> 00:19:09,980
rozważmy, co to
w rzeczywistości wygląda.

379
00:19:09,980 --> 00:19:10,650
Pozwól mi uderzyć luz.

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

381
00:19:14,210 --> 00:19:18,980
>> Tak więc w tej grze, mamy
żaba, i za pomocą strzałek keys--

382
00:19:18,980 --> 00:19:23,340
on ma większe kroki niż remember--
Mam kontrolę nad tym żaby.

383
00:19:23,340 --> 00:19:29,630
A celem jest przedostać się zajęty
Droga bez w samochodach.

384
00:19:29,630 --> 00:19:34,735
I niech see-- jeśli pójdę się tutaj,
trzeba czekać na dziennik, aby zmieniać.

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

386
00:19:38,130 --> 00:19:39,274
To czuje się jak robaka.

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

388
00:19:42,240 --> 00:19:43,495
Jest to rodzaj błędu.

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

390
00:19:45,980 --> 00:19:46,480
W porządku.

391
00:19:46,480 --> 00:19:51,550
Jestem na to tutaj,
tam, a następnie zachować

392
00:19:51,550 --> 00:19:54,100
dzieje, aż do uzyskania wszystkich
żaby do lily pads.

393
00:19:54,100 --> 00:19:55,920
Teraz to może wyglądać
bardziej skomplikowane

394
00:19:55,920 --> 00:19:57,840
ale spróbujmy przełamać
to w dół psychicznie

395
00:19:57,840 --> 00:20:00,040
oraz ustnie do swoich bloków składowych.

396
00:20:00,040 --> 00:20:03,910
Więc to chyba logiczne
kawałek, który jeszcze nie widział

397
00:20:03,910 --> 00:20:07,440
ale to reaguje na naciśnięcia klawiszy,
rzeczy uderzę na klawiaturze.

398
00:20:07,440 --> 00:20:11,660
>> Więc nie ma chyba jakiś
Blok, który mówi, jeśli klucz równa się,

399
00:20:11,660 --> 00:20:15,965
zrób coś z Scratch--
Może przenieść go 10 kroków w ten sposób.

400
00:20:15,965 --> 00:20:20,240
Jeśli naciśnięty zostanie przycisk DOWN, przenieść 10 kroków
w ten sposób, albo lewy klawisz, przenieść 10 kroków

401
00:20:20,240 --> 00:20:21,710
w ten sposób, że 10 kroków.

402
00:20:21,710 --> 00:20:23,644
Ja wyraźnie odwrócił kota w żabę.

403
00:20:23,644 --> 00:20:26,060
Tak to tylko w przypadku gdy
Kostium, ponieważ rozmowy Scratch it-- my

404
00:20:26,060 --> 00:20:28,440
tylko importowany obraz żaby.

405
00:20:28,440 --> 00:20:29,570
>> Ale co jeszcze się dzieje?

406
00:20:29,570 --> 00:20:32,794
Jakie inne linie kodu,
jakie inne kawałki układanki

407
00:20:32,794 --> 00:20:35,460
zrobił Blake, nasze nauczanie towarzysz,
zastosować w tym programie, jak widać?

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

409
00:20:38,320 --> 00:20:42,730
Co czyni wszystko move--
co programowania wybudować?

410
00:20:42,730 --> 00:20:44,950
>> Ruch, sure-- więc
przesunąć blok, na pewno.

411
00:20:44,950 --> 00:20:49,330
A co to takiego bloku Przesuń
wewnątrz, najprawdopodobniej?

412
00:20:49,330 --> 00:20:52,850
Tak, coś w rodzaju pętli, może
zawsze blokować, może powtórzyć block--

413
00:20:52,850 --> 00:20:54,070
powtarzać aż do bloku.

414
00:20:54,070 --> 00:20:57,330
A to, co czyni i dzienniki
lilia poduszki i wszystko inne posunięcie

415
00:20:57,330 --> 00:20:57,990
w przód i w tył.

416
00:20:57,990 --> 00:21:00,270
To właśnie dzieje się w nieskończoność.

417
00:21:00,270 --> 00:21:03,180
>> Dlaczego niektóre z samochodów
porusza się szybciej niż inni?

418
00:21:03,180 --> 00:21:06,607
Czym różni się o tych programach?

419
00:21:06,607 --> 00:21:09,690
Tak, prawdopodobnie niektóre z nich biorą
więcej stopni na raz, a niektóre z nich

420
00:21:09,690 --> 00:21:10,690
mniej etapów naraz.

421
00:21:10,690 --> 00:21:14,670
I efekt wizualny
Jest szybka kontra powolny.

422
00:21:14,670 --> 00:21:16,030
>> Jak myślisz, co się stało?

423
00:21:16,030 --> 00:21:19,700
Gdy dostałem żaba na drodze
po drugiej stronie ulicy i rzeki

424
00:21:19,700 --> 00:21:23,560
na lily pad, coś
Warto zauważyć stało.

425
00:21:23,560 --> 00:21:26,540
Co stało się tak szybko, jak to zrobiłem?

426
00:21:26,540 --> 00:21:27,210
Zatrzymało się.

427
00:21:27,210 --> 00:21:29,680
To żaba zatrzymany i
Dostałem drugą żabę.

428
00:21:29,680 --> 00:21:33,155
Więc co konstrukt musi być
wykorzystywane tam, co funkcja?

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

430
00:21:36,020 --> 00:21:38,660
>> Tak, więc jest jakaś
"If" uzależnić się tam, too.

431
00:21:38,660 --> 00:21:41,909
I okazuje out-- nie widzieliśmy this--
ale nie ma tam innych bloków, które

432
00:21:41,909 --> 00:21:45,300
Można powiedzieć, jeśli dotykają
Inną rzeczą, na ekranie

433
00:21:45,300 --> 00:21:47,720
jeśli dotyka lily pad ", a następnie".

434
00:21:47,720 --> 00:21:50,810
I wtedy właśnie, kiedy
aby pojawić się druga żaba.

435
00:21:50,810 --> 00:21:54,969
Dlatego, mimo że ta gra jest z pewnością
bardzo stary, choć na pierwszy rzut oka

436
00:21:54,969 --> 00:21:58,010
jest tak wiele dzieje on-- i Blake
Nie to wzbudzać w ciągu dwóch minut,

437
00:21:58,010 --> 00:22:00,390
prawdopodobnie zabrał mu kilka
godzin, aby stworzyć tę grę

438
00:22:00,390 --> 00:22:03,850
na podstawie jego pamięci lub filmy
Od wersji przeszłości za nim.

439
00:22:03,850 --> 00:22:07,940
Ale wszystkie te małe rzeczy
dzieje się na ekranie w izolacji

440
00:22:07,940 --> 00:22:11,550
sprowadzają się do nich bardzo prosta
constructs-- ruchy lub oświadczenia

441
00:22:11,550 --> 00:22:15,519
jak omówiliśmy, pętle i
warunki i to wszystko.

442
00:22:15,519 --> 00:22:17,060
Istnieje kilka innych bardziej wyszukane funkcje.

443
00:22:17,060 --> 00:22:19,130
Niektóre z nich są czysto
estetyczne i akustyczne,

444
00:22:19,130 --> 00:22:20,964
jak dźwięki po prostu grał.

445
00:22:20,964 --> 00:22:23,380
Jednak dla większości,
mają w tym języku, scratch,

446
00:22:23,380 --> 00:22:25,350
wszystkie podstawowe
cegiełki to ty

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

448
00:22:29,280 --> 00:22:32,960
i wielu innych językach.

449
00:22:32,960 --> 00:22:36,720
Wszelkie pytania dotyczące zera?

450
00:22:36,720 --> 00:22:37,220
W porządku.

451
00:22:37,220 --> 00:22:40,303
Nie będziemy więc zanurkować głębiej do zera,
jeśli jesteś mile widziany w ten weekend,

452
00:22:40,303 --> 00:22:42,860
zwłaszcza jeśli masz dzieci lub
siostrzenice i siostrzeńcy i takie,

453
00:22:42,860 --> 00:22:44,220
aby wprowadzić je do zera.

454
00:22:44,220 --> 00:22:47,960
To rzeczywiście cudownie zabawny
środowiska z, a jego autorzy twierdzą,

455
00:22:47,960 --> 00:22:49,120
bardzo wysokie sufity.

456
00:22:49,120 --> 00:22:51,670
Nawet mimo tego, że zaczęło się od
bardzo szczegółowe niskopoziomowe,

457
00:22:51,670 --> 00:22:54,890
można naprawdę sporo
z tym, co jest być może

458
00:22:54,890 --> 00:22:57,360
demonstracja dokładnie to.

459
00:22:57,360 --> 00:23:02,920
>> Ale bądźmy teraz przejść do nieco bardziej
wyszukane problemy, jeśli chcesz,

460
00:23:02,920 --> 00:23:05,870
znany jako "poszukiwanie", a
"Sortowania", bardziej ogólnie.

461
00:23:05,870 --> 00:23:09,500
Mieliśmy to książka telefoniczna earlier-- tutaj
drugi tylko dla discussion--

462
00:23:09,500 --> 00:23:13,460
że byliśmy w stanie wyszukiwać
bardziej skutecznie, ponieważ

463
00:23:13,460 --> 00:23:15,270
znaczącej założeniu.

464
00:23:15,270 --> 00:23:17,655
I żeby była jasność, co
Założenie było takie, że co

465
00:23:17,655 --> 00:23:19,280
przy przeszukiwaniu tej książce telefonicznej?

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

467
00:23:23,342 --> 00:23:25,300
Mike Smith był w
książka telefoniczna, choć

468
00:23:25,300 --> 00:23:27,410
byłaby w stanie obsłużyć
scenariusz bez niego

469
00:23:27,410 --> 00:23:30,720
tam, jeśli tylko zatrzyma się przedwcześnie.

470
00:23:30,720 --> 00:23:31,806
Książka jest alfabetyczna.

471
00:23:31,806 --> 00:23:33,930
I to jest bardzo hojny
Założenie, ponieważ

472
00:23:33,930 --> 00:23:36,580
Oznacza someone-- jestem miły
cięcia narożnik,

473
00:23:36,580 --> 00:23:40,580
jak ja się szybciej, ponieważ ktoś
inny tego nie zrobił dużo ciężkiej pracy dla mnie.

474
00:23:40,580 --> 00:23:43,120
>> Ale co wtedy, gdy telefon
Książka została nieposortowane?

475
00:23:43,120 --> 00:23:47,050
Może Verizon dostaje leniwy, po prostu wyrzucił
Nazwy i numery każdego z nas tam

476
00:23:47,050 --> 00:23:50,120
może w kolejności, w jakiej
przystąpił do usług telefonicznych.

477
00:23:50,120 --> 00:23:54,570
A ile czasu zajmie mi
znaleźć kogoś takiego jak Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1000 strona telefonu book-- ilu
strony muszę przejrzeć?

479
00:23:58,160 --> 00:23:58,905
>> Wszyscy.

480
00:23:58,905 --> 00:24:00,030
Jesteś rodzaju pecha.

481
00:24:00,030 --> 00:24:03,420
Dosłownie trzeba patrzeć na każde
Strona, jeśli jest tylko książka telefoniczna

482
00:24:03,420 --> 00:24:04,450
losowo klasyfikowane.

483
00:24:04,450 --> 00:24:06,910
Możesz mieć szczęście i znaleźć Mike
na pierwszej stronie, bo

484
00:24:06,910 --> 00:24:08,826
Był to pierwszy Klient
zamówić usługę telefoniczną.

485
00:24:08,826 --> 00:24:10,760
Ale mógł być ostatni, też.

486
00:24:10,760 --> 00:24:12,500
>> Więc losowego nie jest dobre.

487
00:24:12,500 --> 00:24:16,750
Więc załóżmy, że mamy do sortowania
książka telefoniczna lub ogólnych danych sortowania

488
00:24:16,750 --> 00:24:18,520
że mamy dano.

489
00:24:18,520 --> 00:24:19,440
Jak możemy to zrobić?

490
00:24:19,440 --> 00:24:21,360
>> Dobrze, niech po prostu spróbować
prosty przykład tutaj.

491
00:24:21,360 --> 00:24:24,290
Pozwólcie mi iść do przodu i wrzucić
Kilka liczb na planszy.

492
00:24:24,290 --> 00:24:35,480
Załóżmy, że mamy numery są
powiedzmy, cztery, dwa, jeden i trzy.

493
00:24:35,480 --> 00:24:38,390
I, Ben uporządkować te numery dla nas.

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

495
00:24:39,017 --> 00:24:39,850
Jak to zrobiłeś?

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

497
00:24:42,731 --> 00:24:43,230
W porządku.

498
00:24:43,230 --> 00:24:44,710
Więc zacząć od najmniejszych
Wartość i najwyższa,

499
00:24:44,710 --> 00:24:46,084
i to jest bardzo dobra intuicja.

500
00:24:46,084 --> 00:24:48,080
I uświadomić sobie, że
ludzie są faktycznie dość

501
00:24:48,080 --> 00:24:49,913
dobry w rozwiązywaniu problemów
w ten sposób, co najmniej

502
00:24:49,913 --> 00:24:51,810
gdy dane jest stosunkowo mała.

503
00:24:51,810 --> 00:24:54,860
Jak tylko zaczniesz mieć setki
numerów, tysiące numerów,

504
00:24:54,860 --> 00:24:58,440
miliony numerów Ben pewnie
nie mógł go dość, że szybko,

505
00:24:58,440 --> 00:25:00,620
przy założeniu, że
luki w liczbach.

506
00:25:00,620 --> 00:25:03,450
Dość łatwo policzyć do miliona
inaczej, po prostu czasochłonne.

507
00:25:03,450 --> 00:25:07,150
>> Więc algorytm brzmi
jak Ben wykorzystane dopiero teraz

508
00:25:07,150 --> 00:25:08,930
było poszukiwanie najmniejszej liczby.

509
00:25:08,930 --> 00:25:12,900
Więc mimo, że ludzie mogą podjąć
w wielu informacji wizualnej,

510
00:25:12,900 --> 00:25:14,830
komputer jest rzeczywiście
trochę bardziej ograniczone.

511
00:25:14,830 --> 00:25:17,560
Komputer może tylko
spojrzeć na jeden bajt na raz

512
00:25:17,560 --> 00:25:20,770
a może cztery bajty przy time--
w tych dniach może 8 bajtów przy time--

513
00:25:20,770 --> 00:25:24,450
ale bardzo mała liczba
Liczba bajtów w danym czasie.

514
00:25:24,450 --> 00:25:28,480
>> Tak więc biorąc pod uwagę, że naprawdę mamy
cztery oddzielne wartości here--

515
00:25:28,480 --> 00:25:32,440
i można myśleć o Ben jako posiadające
Przesłony na gdyby komputer takie

516
00:25:32,440 --> 00:25:36,450
że nie widzi niczego innego
niż jeden numer przy time--

517
00:25:36,450 --> 00:25:39,720
więc generalnie zakłada, podobnie jak w
Angielski, będziemy czytać od prawej do lewej.

518
00:25:39,720 --> 00:25:42,870
Więc pierwsza liczba Ben pewnie wyglądał
co było czterech, a następnie bardzo szybko

519
00:25:42,870 --> 00:25:44,770
sobie sprawę, że jest to dość duży
number-- pozwól mi szukać dalej.

520
00:25:44,770 --> 00:25:45,357
>> Nie ma dwóch.

521
00:25:45,357 --> 00:25:45,940
Poczekaj chwilę.

522
00:25:45,940 --> 00:25:47,070
Nimi jest mniejsza niż cztery.

523
00:25:47,070 --> 00:25:47,986
Idę do zapamiętania.

524
00:25:47,986 --> 00:25:49,070
Dwa to obecnie najmniejszy.

525
00:25:49,070 --> 00:25:50,417
Teraz jedno-, że nawet lepiej.

526
00:25:50,417 --> 00:25:51,250
To jeszcze mniejszy.

527
00:25:51,250 --> 00:25:54,000
Idę zapomnieć o dwóch
i po prostu pamiętam teraz.

528
00:25:54,000 --> 00:25:56,550
>> A mógł przestać patrzeć?

529
00:25:56,550 --> 00:25:58,360
Cóż, mógł na podstawie
na tej informacji,

530
00:25:58,360 --> 00:26:00,477
ale lepiej wyszukiwanie
reszta listy.

531
00:26:00,477 --> 00:26:02,060
Bo co, jeśli zera było w liście?

532
00:26:02,060 --> 00:26:03,643
Co zrobić, jeśli negatywny było w liście?

533
00:26:03,643 --> 00:26:07,720
Wie tylko, że jego odpowiedź
jest poprawna, jeśli jest on wyczerpujący

534
00:26:07,720 --> 00:26:08,729
Sprawdziłem całą listę.

535
00:26:08,729 --> 00:26:10,020
Więc patrzymy na resztę tego.

536
00:26:10,020 --> 00:26:11,394
Three--, że to strata czasu.

537
00:26:11,394 --> 00:26:13,540
Masz pecha, ale byłem
nadal poprawne, aby to zrobić.

538
00:26:13,540 --> 00:26:17,857
I tak teraz on przypuszczalnie
wybrany najmniejszy numer

539
00:26:17,857 --> 00:26:20,440
i po prostu umieścić go na początku
listy, jak będę tu robić.

540
00:26:20,440 --> 00:26:23,480
Teraz to, co robiłeś w przyszłym, choć
nie myśleli o nim prawie

541
00:26:23,480 --> 00:26:25,962
do tego stopnia?

542
00:26:25,962 --> 00:26:27,670
Powtórz ten proces,
więc pewnego rodzaju pętli.

543
00:26:27,670 --> 00:26:28,920
Jest znanym pomysłem.

544
00:26:28,920 --> 00:26:30,860
Więc tutaj jest cztery.

545
00:26:30,860 --> 00:26:32,110
To obecnie najmniejszy.

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

547
00:26:33,220 --> 00:26:33,900
Nigdy więcej.

548
00:26:33,900 --> 00:26:34,770
Teraz widziałem dwa.

549
00:26:34,770 --> 00:26:36,630
To kolejna najmniejszy element.

550
00:26:36,630 --> 00:26:40,800
Three-- to nie jest mniejsza, więc
Teraz Ben może wyrwać dwa.

551
00:26:40,800 --> 00:26:44,510
>> A teraz powtórzyć proces i
Oczywiście trzy zostaje wyciągnięta dalej.

552
00:26:44,510 --> 00:26:45,420
Powtórz ten proces.

553
00:26:45,420 --> 00:26:46,990
Cztery zostanie wyciągnięta.

554
00:26:46,990 --> 00:26:50,140
A teraz jesteśmy na liczbach,
więc lista musi być sortowane.

555
00:26:50,140 --> 00:26:51,960
>> I rzeczywiście, jest to formalny algorytm.

556
00:26:51,960 --> 00:26:56,610
Informatyk będzie
Nazywamy to "wybór rodzaju"

557
00:26:56,610 --> 00:27:00,880
idea bycia Sortowanie
listy iteratively-- ponownie

558
00:27:00,880 --> 00:27:03,807
i znowu wybierając
najmniejsza liczba.

559
00:27:03,807 --> 00:27:06,140
I co jest ładne o to
to jest po prostu tak cholernie intuicyjne.

560
00:27:06,140 --> 00:27:07,470
To takie proste.

561
00:27:07,470 --> 00:27:11,100
I można powtórzyć ten sam
Operacja ponownie.

562
00:27:11,100 --> 00:27:12,150
To proste.

563
00:27:12,150 --> 00:27:17,170
>> W tym przypadku była szybka, ale
Jak długo trzeba rzeczywiście wziąć?

564
00:27:17,170 --> 00:27:19,880
Zróbmy to wydawać i
czuję się trochę bardziej uciążliwe.

565
00:27:19,880 --> 00:27:24,150
Tak jeden, dwa, trzy, cztery, pięć sześć
siedem, osiem, dziewięć, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- dowolną liczbą.

567
00:27:26,160 --> 00:27:28,780
Chciałem tylko bardziej ten
Czas niż tylko czterech.

568
00:27:28,780 --> 00:27:30,780
Więc jeśli mam całość
pęczek liczb now-- go

569
00:27:30,780 --> 00:27:32,420
nawet nie ma znaczenia
co are-- LET'S

570
00:27:32,420 --> 00:27:34,380
myśleć o tym, co to
Algorytm jest bardzo podobne.

571
00:27:34,380 --> 00:27:35,857
>> Załóżmy, że istnieją jakieś numery.

572
00:27:35,857 --> 00:27:38,190
Ponownie, nie ma znaczenia, co
są, ale są przypadkowe.

573
00:27:38,190 --> 00:27:39,679
Ja zastosowaniu algorytmu Bena.

574
00:27:39,679 --> 00:27:41,220
Muszę wybrać najmniejszą liczbę.

575
00:27:41,220 --> 00:27:41,761
Co ja robię?

576
00:27:41,761 --> 00:27:44,240
I mam zamiar fizycznie
zrób to ten czas działania to.

577
00:27:44,240 --> 00:27:46,099
Szuka, szuka,
szuka, szuka, szuka.

578
00:27:46,099 --> 00:27:48,140
Tylko do czasu mogę
Zakończenie puszki listy

579
00:27:48,140 --> 00:27:51,230
Zdaję sobie sprawę, najmniejsza
liczba była dwa i tym razem.

580
00:27:51,230 --> 00:27:52,720
Jeden nie jest na liście.

581
00:27:52,720 --> 00:27:54,400
Więc odłożyć dwa.

582
00:27:54,400 --> 00:27:55,590
>> Co mam teraz zrobić?

583
00:27:55,590 --> 00:27:58,600
Szuka, szuka, szuka, szuka.

584
00:27:58,600 --> 00:28:02,250
Teraz znalazłem numer siedem, ponieważ
nie ma luki w tych numbers--

585
00:28:02,250 --> 00:28:03,300
ale po prostu arbitralne.

586
00:28:03,300 --> 00:28:03,800
W porządku.

587
00:28:03,800 --> 00:28:06,030
Więc teraz mogę odłożyć siedem.

588
00:28:06,030 --> 00:28:08,860
Patrząc patrząc, patrząc.

589
00:28:08,860 --> 00:28:11,030
>> Teraz jestem zakładając
Oczywiście, że Ben nie

590
00:28:11,030 --> 00:28:14,780
mają dodatkowy RAM, dodatkowe
pamięć, ponieważ, oczywiście,

591
00:28:14,780 --> 00:28:16,080
Patrzę na ten sam numer.

592
00:28:16,080 --> 00:28:18,246
Z pewnością mógłbym pamiętał
Wszystkie z tych numerów

593
00:28:18,246 --> 00:28:19,930
i to absolutnie prawdziwe.

594
00:28:19,930 --> 00:28:22,610
Ale jeśli Ben pamięta wszystko
numerów widział,

595
00:28:22,610 --> 00:28:24,430
że nie ma rzeczywiście wykonane
istotnego postępu

596
00:28:24,430 --> 00:28:26,170
bo już ma
Możliwość wyszukiwania

597
00:28:26,170 --> 00:28:27,540
za pośrednictwem numerów na płycie.

598
00:28:27,540 --> 00:28:29,373
Pamiętając wszystkie z
Liczby nie pomoże,

599
00:28:29,373 --> 00:28:32,490
bo może jeszcze jak komputer
tylko patrzeć, jakie powiedział jeden numer

600
00:28:32,490 --> 00:28:33,080
na czas.

601
00:28:33,080 --> 00:28:35,760
Więc nie ma swego rodzaju oszustwo
tam, że można wykorzystać.

602
00:28:35,760 --> 00:28:39,170
>> Tak więc w rzeczywistości, tak jak ja
utrzymać przeszukiwania listy

603
00:28:39,170 --> 00:28:44,200
Dosłownie trzeba po prostu wracamy
tam iz powrotem przez to, wyrywanie

604
00:28:44,200 --> 00:28:45,710
następna najmniejsza liczba.

605
00:28:45,710 --> 00:28:48,810
I jak można wywnioskować rodzaj
z moich głupich ruchów,

606
00:28:48,810 --> 00:28:50,860
to po prostu staje się bardzo
nużące bardzo szybko,

607
00:28:50,860 --> 00:28:54,850
i wydaje mi się, że będzie z powrotem i
powrotem, tam iz powrotem, całkiem sporo.

608
00:28:54,850 --> 00:29:03,220
Teraz aby być uczciwym, nie muszę iść
aż tak dobrze, niech see-- aby być uczciwym,

609
00:29:03,220 --> 00:29:06,310
Nie trzeba chodzić dość
jak wiele kroków za każdym razem.

610
00:29:06,310 --> 00:29:09,200
Ponieważ, oczywiście, jak
wybieranie numerów z listy,

611
00:29:09,200 --> 00:29:11,860
Pozostała lista jest coraz krótszy.

612
00:29:11,860 --> 00:29:14,240
>> A więc pomyślmy o
ile kroków jestem naprawdę

613
00:29:14,240 --> 00:29:16,010
traipsing za każdym razem.

614
00:29:16,010 --> 00:29:18,950
W pierwszej sytuacji
mieliśmy 16 numerów,

615
00:29:18,950 --> 00:29:22,210
i tak maximally-- niech po prostu
zrobić to za discussion--

616
00:29:22,210 --> 00:29:25,640
Musiałem patrzeć przez 16
Numery znaleźć najmniejszy.

617
00:29:25,640 --> 00:29:28,420
Ale kiedy wyrwana
najmniejsza liczba, jak

618
00:29:28,420 --> 00:29:30,590
długo był pozostałą listę, oczywiście?

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

620
00:29:31,420 --> 00:29:34,670
Więc ile numerów zrobił Ben czy mam
do zapoznania się za drugim razem?

621
00:29:34,670 --> 00:29:36,832
15, po prostu iść i znaleźć najmniejszy.

622
00:29:36,832 --> 00:29:39,540
Ale teraz, oczywiście, lista jest,
Także mniejsze niż to było wcześniej.

623
00:29:39,540 --> 00:29:42,540
Tak jak wiele kroków ja
trzeba wziąć następnym razem?

624
00:29:42,540 --> 00:29:49,970
14 i 13, a potem 12, a także kropki,
kropka, kropka, dopóki pozostaje mi tylko jedno.

625
00:29:49,970 --> 00:29:53,146
Więc teraz informatyk będzie
zapytać, dobrze, co robi, że wszyscy równi?

626
00:29:53,146 --> 00:29:55,770
To faktycznie równa konkretne
numer, który mogliśmy pewnością

627
00:29:55,770 --> 00:30:00,490
zrobić arytmetycznie, ale chcemy rozmawiać
o wydajności algorytmów

628
00:30:00,490 --> 00:30:04,940
trochę bardziej formulaically,
niezależne od tego jak długo lista jest.

629
00:30:04,940 --> 00:30:06,240
>> I tak wiesz, co?

630
00:30:06,240 --> 00:30:09,860
Jest to 16, ale tak jak powiedziałem wcześniej,
niech po prostu zadzwonić do rozmiaru problemu

631
00:30:09,860 --> 00:30:10,970
n, gdzie n jest pewną liczbę.

632
00:30:10,970 --> 00:30:13,220
Może to jest 16, może to
trzy, może to milion.

633
00:30:13,220 --> 00:30:13,761
Nie wiem

634
00:30:13,761 --> 00:30:14,390
Nie obchodzi mnie to.

635
00:30:14,390 --> 00:30:16,520
Co naprawdę chcę to
formuła, że ​​mogę

636
00:30:16,520 --> 00:30:19,420
użyć do porównania tego algorytmu
w stosunku do innych algorytmów

637
00:30:19,420 --> 00:30:22,350
że ktoś może twierdzić,
są lepsze lub gorsze.

638
00:30:22,350 --> 00:30:25,430
>> Tak więc okazuje się, a tylko ja
wiem to z podstawówki,

639
00:30:25,430 --> 00:30:34,790
że to faktycznie działa się tak samo
coś takiego jak n na n plus jeden na dwóch.

640
00:30:34,790 --> 00:30:40,020
I to dzieje się równać, z
Oczywiście, n oraz n kwadratu nad nimi.

641
00:30:40,020 --> 00:30:43,250
Więc gdybym chciał formułę
dla ilu krokach

642
00:30:43,250 --> 00:30:46,330
zajmowali się patrząc na wszystko
od raz po raz te numery

643
00:30:46,330 --> 00:30:52,681
i znowu, i znowu, powiedziałbym,
to n do kwadratu oraz n nad nimi.

644
00:30:52,681 --> 00:30:53,430
Ale wiesz co?

645
00:30:53,430 --> 00:30:54,500
To po prostu wygląda niechlujnie.

646
00:30:54,500 --> 00:30:56,470
Po prostu naprawdę chcą
ogólne poczucie rzeczy.

647
00:30:56,470 --> 00:30:58,810
A może pamiętacie z
liceum, że istnieje

648
00:30:58,810 --> 00:31:00,660
jest pojęcie najwyższego terminu zamówienia.

649
00:31:00,660 --> 00:31:05,300
Który z tych terminów, n
kwadratu, z N, albo połowę,

650
00:31:05,300 --> 00:31:07,550
ma największy wpływ na przestrzeni czasu?

651
00:31:07,550 --> 00:31:11,920
Im większe n dostaje, co
Spośród nich większość spraw?

652
00:31:11,920 --> 00:31:15,560
>> Innymi słowy, jeśli podłączę
na milion, n do kwadratu

653
00:31:15,560 --> 00:31:17,900
będzie najprawdopodobniej
współczynnik wyróżniającym,

654
00:31:17,900 --> 00:31:21,670
bo milion razy
Sam jest dużo większy

655
00:31:21,670 --> 00:31:23,682
niż plus jeden dodatkowy milion.

656
00:31:23,682 --> 00:31:24,390
Więc wiesz co?

657
00:31:24,390 --> 00:31:27,305
To jest taki cholernie duża
Numer jeśli kwadrat numer.

658
00:31:27,305 --> 00:31:28,430
To naprawdę nie ma znaczenia.

659
00:31:28,430 --> 00:31:30,596
Jesteśmy po prostu będzie krzyż, który
się i zapomnieć o nim.

660
00:31:30,596 --> 00:31:34,250
I tak informatykiem powiedzieliby
że skuteczność tego algorytmu

661
00:31:34,250 --> 00:31:37,850
jest rzędu n squared--
Mam na myśli naprawdę zbliżenia.

662
00:31:37,850 --> 00:31:40,810
To jest rodzaj grubsza n do kwadratu.

663
00:31:40,810 --> 00:31:44,130
W miarę upływu czasu, tym większa
i większe n dostaje, ten

664
00:31:44,130 --> 00:31:47,610
jest dobrym szacunkiem za to, co
efektywności lub braku skuteczności

665
00:31:47,610 --> 00:31:49,400
tego algorytmu w rzeczywistości.

666
00:31:49,400 --> 00:31:52,040
I czerpać to, oczywiście,
od rzeczywiście robi matematyki.

667
00:31:52,040 --> 00:31:54,040
Ale teraz jestem po prostu macha
moje ręce, bo po prostu

668
00:31:54,040 --> 00:31:55,790
chcą ogólny sens tego algorytmu.

669
00:31:55,790 --> 00:31:58,850
>> Tak więc stosując tę ​​samą logikę, w międzyczasie,
rozważmy inny algorytm

670
00:31:58,850 --> 00:32:01,162
już spojrzał at-- przeszukiwanie liniowe.

671
00:32:01,162 --> 00:32:02,870
Gdy szukałem
dla book-- telefonu

672
00:32:02,870 --> 00:32:05,980
Nie sortowania go, szukając
przez book-- telefonu

673
00:32:05,980 --> 00:32:09,197
nam powtarzał, że to
1000 kroków lub 500 kroków.

674
00:32:09,197 --> 00:32:10,280
Ale załóżmy, że uogólnienia.

675
00:32:10,280 --> 00:32:12,860
Jeśli istnieje n stron w
książka telefoniczna, jaka jest

676
00:32:12,860 --> 00:32:17,250
czas pracy lub
Sprawność przeszukiwanie liniowe?

677
00:32:17,250 --> 00:32:19,750
To na zlecenie
ile kroków do znalezienia

678
00:32:19,750 --> 00:32:24,210
Mike Smith stosując przeszukiwanie liniowe, The
Pierwszy algorytm lub nawet drugi?

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

680
00:32:27,240 --> 00:32:31,710
>> W najgorszym przypadku, Mike
na końcu książki.

681
00:32:31,710 --> 00:32:35,590
Więc jeśli książka telefoniczna ma 1000 stron,
mówiliśmy po raz ostatni, w najgorszym przypadku,

682
00:32:35,590 --> 00:32:38,380
może minąć mniej więcej jak
wiele stron, aby znaleźć Mike?

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

684
00:32:38,990 --> 00:32:39,830
Jest to górna granica.

685
00:32:39,830 --> 00:32:41,790
Jest to najgorszy z możliwych sytuacji.

686
00:32:41,790 --> 00:32:44,410
Ale znowu, jesteśmy odejście
z numerów, takich jak 1000 teraz.

687
00:32:44,410 --> 00:32:45,730
To jest po prostu brak.

688
00:32:45,730 --> 00:32:47,470
>> Więc co jest logiczny wniosek?

689
00:32:47,470 --> 00:32:50,210
Znalezienie Mike w telefonie
Książka, która zawiera strony n

690
00:32:50,210 --> 00:32:55,280
może podjąć, w najgorszym przypadku,
ile kroków na zlecenie n?

691
00:32:55,280 --> 00:32:58,110
I rzeczywiście komputer
Naukowiec powie

692
00:32:58,110 --> 00:33:02,340
że czas uruchomiona albo
wydajności lub efektywności

693
00:33:02,340 --> 00:33:07,470
lub nieefektywność, algorytmu podobnego
poszukiwanie linear jest rzędu n.

694
00:33:07,470 --> 00:33:10,010
I możemy zastosować te same
Logika przekraczania coś

695
00:33:10,010 --> 00:33:13,170
a ja po prostu nie do sekundy
Algorytm mieliśmy z książki telefonicznej,

696
00:33:13,170 --> 00:33:16,040
gdzie udaliśmy dwóch stron na raz.

697
00:33:16,040 --> 00:33:20,120
>> Więc 1000 strona książka telefoniczna może
zabierze nas strona 500 obrotów, plus jeden

698
00:33:20,120 --> 00:33:21,910
jeśli zawrócić trochę.

699
00:33:21,910 --> 00:33:26,590
Więc jeśli książka telefoniczna zawiera strony N, ale
robimy dwie strony na raz,

700
00:33:26,590 --> 00:33:28,900
to mniej więcej co?

701
00:33:28,900 --> 00:33:33,190
N na dwie części, tak, aby jak n nad nimi.

702
00:33:33,190 --> 00:33:38,490
Ale zrobiłem dochodzić
Chwilę temu, że n nad two--

703
00:33:38,490 --> 00:33:41,060
że niby takie same, jak tylko n.

704
00:33:41,060 --> 00:33:44,050
To tylko czynnik stały,
informatycy powie.

705
00:33:44,050 --> 00:33:45,970
Skupmy się tylko na
zmienne, really--

706
00:33:45,970 --> 00:33:47,780
Największe zmienne w równaniu.

707
00:33:47,780 --> 00:33:52,530
>> szukaj więc liniowa, czy odbywa się jedną
Strona naraz lub dwie strony na raz,

708
00:33:52,530 --> 00:33:54,810
jest rodzajem zasadniczo taka sama.

709
00:33:54,810 --> 00:33:56,880
To wciąż rzędu n.

710
00:33:56,880 --> 00:34:01,930
Ale twierdził wcześniej z moim obrazie
że trzeci algorytm nie

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

712
00:34:02,480 --> 00:34:03,605
To nie była prosta.

713
00:34:03,605 --> 00:34:08,659
To było to, że linia krzywa, a
Formuła nie algebraiczne było to, co?

714
00:34:08,659 --> 00:34:11,812
Log n- więc logarytm przy podstawie dwa n.

715
00:34:11,812 --> 00:34:14,520
I nie musimy iść do zbyt
dużo szczegółów na logarytmów dziś

716
00:34:14,520 --> 00:34:17,394
ale większość informatycy nie chciał
nawet powiedzieć, jaka jest podstawa.

717
00:34:17,394 --> 00:34:20,639
Bo to wszystko jest po prostu
stałe czynniki, by tak rzec,

718
00:34:20,639 --> 00:34:22,659
zaledwie nieznaczne różnice liczbowe.

719
00:34:22,659 --> 00:34:31,179
I tak będzie to bardzo często
sposób szczególnie formalnego komputera

720
00:34:31,179 --> 00:34:33,949
Naukowcy na pokładzie lub
programiści na tablicy

721
00:34:33,949 --> 00:34:36,889
argumentując, które faktycznie
Algorytm będą używać

722
00:34:36,889 --> 00:34:39,500
albo co sprawność
z ich algorytm jest.

723
00:34:39,500 --> 00:34:42,960
>> I nie jest koniecznie coś
omówić w jakikolwiek sposób bardzo szczegółowy,

724
00:34:42,960 --> 00:34:47,889
ale dobry programista to ktoś
który posiada solidną, formalne tło.

725
00:34:47,889 --> 00:34:50,120
On jest w stanie rozmawiać
jesteś w tego rodzaju sposób

726
00:34:50,120 --> 00:34:53,350
i rzeczywiście zrobić
argumenty jakościowe jak

727
00:34:53,350 --> 00:34:56,870
dlaczego jeden lub algorytm
jeden kawałek oprogramowania

728
00:34:56,870 --> 00:35:00,165
jest lepsze w pewnym stopniu do drugiej.

729
00:35:00,165 --> 00:35:02,540
Bo z pewnością może
wystarczy uruchomić program, jedna osoba

730
00:35:02,540 --> 00:35:04,980
i policzyć liczbę sekund
trzeba, aby uporządkować kilka liczb,

731
00:35:04,980 --> 00:35:06,710
i można uruchomić niektórych
Program Inne osoby

732
00:35:06,710 --> 00:35:08,418
i policzyć liczbę
sekund trwa.

733
00:35:08,418 --> 00:35:12,840
Ale jest to bardziej ogólny sposób, że
można wykorzystać do analizy algorytmów,

734
00:35:12,840 --> 00:35:15,520
jeśli chcesz, tylko na
papier lub tylko werbalnie.

735
00:35:15,520 --> 00:35:18,430
Nawet nie uruchamiając go bez
nawet nie próbuje wejść przykładowych

736
00:35:18,430 --> 00:35:20,180
można po prostu rozumieć przez nią.

737
00:35:20,180 --> 00:35:24,670
I tak z zatrudnieniem dewelopera lub jeśli
mając mu lub jej rodzaju twierdzą ciebie

738
00:35:24,670 --> 00:35:28,460
dlaczego ich algorytm ich sekret
Sos do wyszukiwania miliardy

739
00:35:28,460 --> 00:35:30,580
stron WWW dla Twojej
firma jest lepsza, to

740
00:35:30,580 --> 00:35:33,302
są rodzaje argumentów one
powinny najlepiej być w stanie dokonać.

741
00:35:33,302 --> 00:35:35,010
Albo przynajmniej są
takie rzeczy

742
00:35:35,010 --> 00:35:40,211
które pojawiały się w dyskusji na
przynajmniej w bardzo formalnej dyskusji.

743
00:35:40,211 --> 00:35:40,710
W porządku.

744
00:35:40,710 --> 00:35:44,400
Więc Ben zaproponował coś
nazywa wybór sortowania.

745
00:35:44,400 --> 00:35:48,200
Ale mam zamiar zaproponować, że nie ma
inne sposoby na zrobienie tego, too.

746
00:35:48,200 --> 00:35:50,400
Co mi się nie bardzo lubię
o algorytmie Bena

747
00:35:50,400 --> 00:35:54,400
jest to, że szedł, albo
po mnie chodzić tam iz powrotem

748
00:35:54,400 --> 00:35:56,930
tam iz powrotem iz powrotem.

749
00:35:56,930 --> 00:36:04,130
Co będzie, jeśli zamiast tego było zrobić
coś w tych liczbach tutaj

750
00:36:04,130 --> 00:36:08,200
i ja się po prostu do czynienia z każdym
Numer z kolei jak ja dał je?

751
00:36:08,200 --> 00:36:10,780
>> Innymi słowy, oto
moja lista numerów.

752
00:36:10,780 --> 00:36:12,944
Czterech, jeden, trzy, dwa.

753
00:36:12,944 --> 00:36:14,360
A ja zamierzam wykonać następujące czynności.

754
00:36:14,360 --> 00:36:17,230
Mam zamiar wstawić numery
której należą raczej

755
00:36:17,230 --> 00:36:18,980
niż wybierając je jeden na raz.

756
00:36:18,980 --> 00:36:20,820
Innymi słowy, tu jest numer cztery.

757
00:36:20,820 --> 00:36:22,430
>> Oto moja lista oryginału.

758
00:36:22,430 --> 00:36:25,290
I mam zamiar utrzymać
zasadniczo nowa lista tutaj.

759
00:36:25,290 --> 00:36:26,710
Więc to jest stara lista.

760
00:36:26,710 --> 00:36:28,560
Jest nowa lista.

761
00:36:28,560 --> 00:36:30,220
Widzę numer cztery pierwsze.

762
00:36:30,220 --> 00:36:34,500
Moja nowa lista jest początkowo pusta,
tak to jest trywialnie sprawa

763
00:36:34,500 --> 00:36:36,410
że cztery obecnie dobierane listę.

764
00:36:36,410 --> 00:36:39,560
Po prostu biorę numer mam podane,
a ja wprowadzenie go w mojej nowej listy.

765
00:36:39,560 --> 00:36:41,460
>> Czy to nowa lista posortowana?

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

767
00:36:41,990 --> 00:36:45,090
To głupie, bo jest tylko jeden
elementem, ale to absolutnie sortowane.

768
00:36:45,090 --> 00:36:46,390
Nic się nie na miejscu.

769
00:36:46,390 --> 00:36:49,290
To ciekawe, ten algorytm,
kiedy przejść do następnego kroku.

770
00:36:49,290 --> 00:36:50,550
>> Teraz mam jeden.

771
00:36:50,550 --> 00:36:55,430
Tak jeden, oczywiście, należy u
początku lub na końcu tej nowej liście?

772
00:36:55,430 --> 00:36:56,360
Początek.

773
00:36:56,360 --> 00:36:58,530
Więc muszę popracować teraz.

774
00:36:58,530 --> 00:37:01,410
Byłem przy niektórych
Swobody z moim markerem

775
00:37:01,410 --> 00:37:03,120
po prostu rysunek rzeczy
gdzie chcę je,

776
00:37:03,120 --> 00:37:05,320
ale to naprawdę nie jest
dokładna w komputerze.

777
00:37:05,320 --> 00:37:08,530
Komputer, jak wiemy, ma
RAM lub Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
i to jest jeden bajt i
kolejny bajt, a drugi bajt.

779
00:37:12,411 --> 00:37:14,910
A jeśli masz gigabajt
RAM, masz miliard bajtów,

780
00:37:14,910 --> 00:37:16,680
ale są fizycznie w jednym miejscu.

781
00:37:16,680 --> 00:37:19,540
Nie można po prostu przenieść rzeczy wokół
rysując go na pokładzie

782
00:37:19,540 --> 00:37:20,750
gdziekolwiek chcesz.

783
00:37:20,750 --> 00:37:24,090
Więc jeśli moja nowa lista ma
Cztery miejsca w pamięci,

784
00:37:24,090 --> 00:37:27,480
niestety jest cztery
już w niewłaściwym miejscu.

785
00:37:27,480 --> 00:37:30,410
>> Tak, aby wstawić numer jeden
Nie można po prostu wyciągnąć go tutaj.

786
00:37:30,410 --> 00:37:31,901
To miejsce pamięci nie istnieje.

787
00:37:31,901 --> 00:37:35,150
To byłoby oszustwo, i byłem
oszustwo obrazowo na kilka minut

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

789
00:37:35,800 --> 00:37:40,950
Tak naprawdę, jeśli chcę, aby umieścić je tutaj,
Mam tymczasowo skopiować cztery

790
00:37:40,950 --> 00:37:43,030
a następnie umieścić jeden tam.

791
00:37:43,030 --> 00:37:45,500
>> To dobrze, to jest prawidłowe,
to technicznie możliwe,

792
00:37:45,500 --> 00:37:48,410
ale uświadomić sobie, że to dodatkowa praca.

793
00:37:48,410 --> 00:37:50,460
Nie wystarczy umieścić numer na swoim miejscu.

794
00:37:50,460 --> 00:37:53,026
Po raz pierwszy musiał przesunąć
numer, a następnie umieścić go w miejscu,

795
00:37:53,026 --> 00:37:54,650
więc rodzaj podwoiła mój ilości pracy.

796
00:37:54,650 --> 00:37:55,660
Miejcie to na uwadze.

797
00:37:55,660 --> 00:37:57,120
>> Ale jestem teraz zrobić z tym elementem.

798
00:37:57,120 --> 00:37:59,056
Teraz chcę, aby pobrać numer trzy.

799
00:37:59,056 --> 00:38:00,430
Jeżeli, oczywiście, to należy?

800
00:38:00,430 --> 00:38:01,480
Pomiędzy.

801
00:38:01,480 --> 00:38:03,650
Nie mogę się już oszukać
i po prostu umieścić go tam,

802
00:38:03,650 --> 00:38:06,770
bo znowu tej pamięci
w lokalizacjach fizycznych.

803
00:38:06,770 --> 00:38:10,900
Więc muszę skopiować cztery
i umieścić trzy tutaj.

804
00:38:10,900 --> 00:38:11,550
Nic takiego.

805
00:38:11,550 --> 00:38:14,610
To tylko jeden dodatkowy krok
again-- czuje się bardzo tanie.

806
00:38:14,610 --> 00:38:16,445
>> Ale teraz przejść do dwóch.

807
00:38:16,445 --> 00:38:17,820
Dwa oczywiście należy tutaj.

808
00:38:17,820 --> 00:38:20,990
Teraz można rozpocząć, aby zobaczyć, jak
praca może piętrzyć.

809
00:38:20,990 --> 00:38:23,520
I co teraz mam zrobić?

810
00:38:23,520 --> 00:38:28,570
Tak, muszę przenieść cztery,
Mam następnie skopiować trzy,

811
00:38:28,570 --> 00:38:31,200
i teraz mogę wstawić dwa.

812
00:38:31,200 --> 00:38:34,460
A z tym jest haczyk
Algorytm, co ciekawe,

813
00:38:34,460 --> 00:38:41,050
jest to, że załóżmy, że mamy bardziej ekstremalne
przypadku, gdy jest to powiedzmy, osiem, siedem,

814
00:38:41,050 --> 00:38:45,150
sześć, pięć, cztery, trzy, dwa, jeden.

815
00:38:45,150 --> 00:38:49,450
Jest to w wielu kontekstach
najgorszy scenariusz,

816
00:38:49,450 --> 00:38:51,570
bo absolutnie znakomite rzeczy
jest dosłownie tyłu.

817
00:38:51,570 --> 00:38:53,670
>> To naprawdę nie ma
wpływa algorytm Bena,

818
00:38:53,670 --> 00:38:55,940
bo w wyborze Bena
sort ma zamiar utrzymać

819
00:38:55,940 --> 00:38:58,359
tam iz powrotem przez liście.

820
00:38:58,359 --> 00:39:01,150
A ponieważ był zawsze szuka
całej listy pozostały,

821
00:39:01,150 --> 00:39:02,858
to nie ma znaczenia
gdzie elementy.

822
00:39:02,858 --> 00:39:05,630
Ale w tym przypadku z moim wkładania
approach-- spróbujmy.

823
00:39:05,630 --> 00:39:08,616
>> Tak jeden, dwa, trzy, cztery,
pięć, sześć, siedem, osiem.

824
00:39:08,616 --> 00:39:11,630
Jeden dwa trzy cztery,
pięć, sześć, siedem, osiem.

825
00:39:11,630 --> 00:39:14,320
Mam zamiar wziąć osiem,
i gdzie mogę umieścić go?

826
00:39:14,320 --> 00:39:17,260
Cóż, na początku mojej listy,
ponieważ ta nowa lista jest sortowana.

827
00:39:17,260 --> 00:39:18,760
A ja je skreślić.

828
00:39:18,760 --> 00:39:20,551
>> Gdzie mam umieścić siedem?

829
00:39:20,551 --> 00:39:21,050
Cholernie go.

830
00:39:21,050 --> 00:39:23,174
Trzeba tam pojechać, więc
Muszę zrobić jakieś kopiowanie.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
A teraz siedem idzie tutaj.

833
00:39:28,480 --> 00:39:29,860
Teraz przechodzimy do sześciu.

834
00:39:29,860 --> 00:39:30,980
Teraz jeszcze więcej pracy.

835
00:39:30,980 --> 00:39:32,570
>> Osiem musi udać się tutaj.

836
00:39:32,570 --> 00:39:33,920
Siedem musi udać się tutaj.

837
00:39:33,920 --> 00:39:35,450
Teraz sześć może udać się tutaj.

838
00:39:35,450 --> 00:39:37,950
Teraz weź pięć.

839
00:39:37,950 --> 00:39:40,560
Teraz osiem musi odejść
tu siedem musi iść tutaj,

840
00:39:40,560 --> 00:39:43,650
sześć ma iść tutaj, i
teraz pięć i powtórzyć.

841
00:39:43,650 --> 00:39:46,610
I jestem prawie
przesuwając go stale.

842
00:39:46,610 --> 00:39:52,950
>> Tak na końcu tego algorithm-- we''ll
nazwać wstawiania sort-- rzeczywistości

843
00:39:52,950 --> 00:39:55,020
ma dużo pracy, też.

844
00:39:55,020 --> 00:39:56,970
To jest po prostu inna
rodzaj pracy niż Ben.

845
00:39:56,970 --> 00:40:00,090
Prace Bena miał mnie dzieje
tam iz powrotem przez cały czas,

846
00:40:00,090 --> 00:40:03,510
wybierając następna najmniejsza
Element ponownie.

847
00:40:03,510 --> 00:40:06,660
Więc było to bardzo wizualne rodzaj pracy.

848
00:40:06,660 --> 00:40:10,600
>> Ten drugi algorytm, który jest wciąż
correct-- będzie dostać pracę done--

849
00:40:10,600 --> 00:40:12,800
po prostu zmienia się ilość pracy.

850
00:40:12,800 --> 00:40:15,420
Wygląda na to, że jesteś na początku
oszczędności, bo jesteś po prostu

851
00:40:15,420 --> 00:40:19,190
czynienia z każdym elementem
z góry bez chodzenia wszystkim

852
00:40:19,190 --> 00:40:20,930
droga przez liście, jak Ben.

853
00:40:20,930 --> 00:40:25,300
Jednak problemem jest to, w szczególności w tych
szalone przypadki, w których to wszystko wstecz,

854
00:40:25,300 --> 00:40:27,830
jesteś po prostu rodzaj
odroczenie ciężką pracę

855
00:40:27,830 --> 00:40:30,360
aż trzeba naprawić swoje błędy.

856
00:40:30,360 --> 00:40:33,919
>> A więc jeśli można to sobie wyobrazić
osiem i siedem i sześć i pięć

857
00:40:33,919 --> 00:40:36,710
a następnie cztery i trzy i dwa
przesuwając się przez liście,

858
00:40:36,710 --> 00:40:39,060
my właśnie zmienił
rodzaj pracy robimy.

859
00:40:39,060 --> 00:40:42,340
Zamiast robić to u
początku mojego iteracji

860
00:40:42,340 --> 00:40:45,250
Robię go u
koniec każdej iteracji.

861
00:40:45,250 --> 00:40:50,550
Tak więc okazuje się, że ten algorytm,
Także ogólnie nazywane Sortowanie przez wstawianie,

862
00:40:50,550 --> 00:40:52,190
Jest również na zlecenie n do kwadratu.

863
00:40:52,190 --> 00:40:56,480
To rzeczywiście nie jest lepsza,
nie lepiej w ogóle.

864
00:40:56,480 --> 00:41:00,810
>> Jednakże, istnieje Trzecie podejście
Chciałbym zachęcić nas do zastanowienia się,

865
00:41:00,810 --> 00:41:02,970
która jest następująca.

866
00:41:02,970 --> 00:41:07,850
Więc przypuszczam moją listę, dla uproszczenia
znowu wynosi cztery, trzy,

867
00:41:07,850 --> 00:41:11,080
two-- tylko cztery numery.

868
00:41:11,080 --> 00:41:13,300
Ben miał dobrą intuicję,
dobra intuicja ludzka

869
00:41:13,300 --> 00:41:16,340
wcześniej, przez którą stała cała
listy eventually-- Sortowanie przez wstawianie.

870
00:41:16,340 --> 00:41:18,020
I namówił nas wzdłuż.

871
00:41:18,020 --> 00:41:22,530
Ale rozważmy
Najprostszym sposobem, aby naprawić tę listę.

872
00:41:22,530 --> 00:41:24,110
>> Ta lista nie jest posortowana.

873
00:41:24,110 --> 00:41:26,130
Czemu?

874
00:41:26,130 --> 00:41:31,920
W języku angielskim, dlaczego
nie faktycznie sortowane.

875
00:41:31,920 --> 00:41:33,400
Co to znaczy nie być sortowane?

876
00:41:33,400 --> 00:41:34,220
>> Student: To nie jest sekwencyjnym.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: Nie sekwencyjnym.

878
00:41:34,990 --> 00:41:35,822
Daj mi przykład.

879
00:41:35,822 --> 00:41:37,180
>> Student: Umieść je w kolejności.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Daj mi bardziej konkretny przykład.

882
00:41:38,790 --> 00:41:39,832
>> Student: porządku rosnącym.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Nie porządku rosnącym.

884
00:41:41,206 --> 00:41:42,100
Być bardziej precyzyjne.

885
00:41:42,100 --> 00:41:45,190
Nie wiem, co masz na myśli rosnąco.

886
00:41:45,190 --> 00:41:47,150
Co jest nie tak?

887
00:41:47,150 --> 00:41:49,930
>> Student: Najmniejszy z
Liczby nie znajduje się w pierwszej pozycji.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: Najmniejsza liczba użytkownika
nie w pierwszym polu.

889
00:41:51,140 --> 00:41:52,120
Bądź bardziej dokładny.

890
00:41:52,120 --> 00:41:55,000
Zaczynam łapać dalej.

891
00:41:55,000 --> 00:41:59,470
Liczymy, ale
co jest w porządku tutaj?

892
00:41:59,470 --> 00:42:00,707
>> Student: numeryczna sekwencja.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: numeryczna sekwencja.

894
00:42:02,040 --> 00:42:04,248
rodzaj każdego człowieka, jakim jest utrzymanie
to here-- bardzo wysoki poziom.

895
00:42:04,248 --> 00:42:07,450
Wystarczy dosłownie mi powiedzieć, co jest
źle jak pięć-letniego sił.

896
00:42:07,450 --> 00:42:08,310
>> Student: plus jeden.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Co to jest?

898
00:42:08,750 --> 00:42:09,610
>> Student: plus jeden.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Co masz na myśli plus jeden?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Daj mi inny pięć lat.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Co się stało, mamo?

904
00:42:18,330 --> 00:42:19,940
Co się stało, tato?

905
00:42:19,940 --> 00:42:22,808
Co masz na myśli to nie jest klasyfikowane?

906
00:42:22,808 --> 00:42:24,370
>> Student: To nie jest właściwe miejsce.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Co
Nie we właściwym miejscu?

908
00:42:25,580 --> 00:42:26,174
>> Student: Cztery.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, dobra.

910
00:42:27,090 --> 00:42:29,110
Więc cztery nie jest tam, gdzie powinien być.

911
00:42:29,110 --> 00:42:30,590
W szczególności, czy to prawda?

912
00:42:30,590 --> 00:42:33,000
Cztery i pierwszy
dwa numery rozumiem.

913
00:42:33,000 --> 00:42:34,930
Czy to jest poprawne?

914
00:42:34,930 --> 00:42:36,427
Nie, oni są w porządku, prawda?

915
00:42:36,427 --> 00:42:38,135
W rzeczywistości, że teraz
o komputera też.

916
00:42:38,135 --> 00:42:40,824
Może to być może patrzeć tylko na jednym,
być może dwie rzeczy na once--

917
00:42:40,824 --> 00:42:43,240
a właściwie tylko jedno
w czasie, ale może przynajmniej

918
00:42:43,240 --> 00:42:45,790
spojrzeć na jednej rzeczy, to
Następną rzeczą, tuż obok niego.

919
00:42:45,790 --> 00:42:47,380
>> Więc to są w porządku?

920
00:42:47,380 --> 00:42:48,032
Oczywiście nie.

921
00:42:48,032 --> 00:42:48,740
Więc wiesz co?

922
00:42:48,740 --> 00:42:51,020
Dlaczego nie bierzemy dziecko
Kroki rozwiązywania tego problemu

923
00:42:51,020 --> 00:42:53,410
zamiast robić te fantazję
algorytmy, takie jak Ben, gdzie

924
00:42:53,410 --> 00:42:56,440
on rodzaj mocowania go
przelotowego listy

925
00:42:56,440 --> 00:42:59,670
zamiast robić to, co zrobiłem, gdzie
I właśnie niby naprawić go jak idziemy?

926
00:42:59,670 --> 00:43:03,650
Miejmy tylko dosłownie rozbić
Pojęcie order-- porządku numerycznym,

927
00:43:03,650 --> 00:43:06,990
nazwać cokolwiek want--
do tych porównań parami.

928
00:43:06,990 --> 00:43:07,590
>> Cztery i jeden.

929
00:43:07,590 --> 00:43:09,970
Czy to prawidłowa kolejność?

930
00:43:09,970 --> 00:43:11,310
Warto więc naprawić.

931
00:43:11,310 --> 00:43:14,700
Jeden i cztery, a następnie
musimy po prostu skopiować to.

932
00:43:14,700 --> 00:43:15,560
Dobra, dobra.

933
00:43:15,560 --> 00:43:17,022
Poprawiłem jeden i cztery.

934
00:43:17,022 --> 00:43:18,320
Trzy i dwa?

935
00:43:18,320 --> 00:43:18,820
Nie.

936
00:43:18,820 --> 00:43:21,690
Niech moje słowa pasuje palce.

937
00:43:21,690 --> 00:43:23,695
Cztery i trzy?

938
00:43:23,695 --> 00:43:27,930
>> To nie jest w porządku, więc mam zamiar
zrobić jeden, trzy, cztery, dwa.

939
00:43:27,930 --> 00:43:28,680
Ok dobrze.

940
00:43:28,680 --> 00:43:32,310
Teraz cztery i dwa?

941
00:43:32,310 --> 00:43:33,370
Musimy rozwiązać ten problem, too.

942
00:43:33,370 --> 00:43:36,700
Tak jeden, trzy, dwie, cztery.

943
00:43:36,700 --> 00:43:39,820
Więc to jest klasyfikowane?

944
00:43:39,820 --> 00:43:43,170
No, ale to jest bliżej sortowane?

945
00:43:43,170 --> 00:43:48,930
>> To jest dlatego, że ten ustalony
pomyłka, naprawiliśmy ten błąd,

946
00:43:48,930 --> 00:43:50,370
i naprawiliśmy ten błąd.

947
00:43:50,370 --> 00:43:52,420
Więc zapewne stały trzy błędy.

948
00:43:52,420 --> 00:43:58,100
Jeszcze nie naprawdę wyglądają sortowane, ale
jest obiektywnie bliżej brakowanych

949
00:43:58,100 --> 00:44:00,080
ponieważ stałe niektóre z tych błędów.

950
00:44:00,080 --> 00:44:02,047
>> I co teraz mam zrobić?

951
00:44:02,047 --> 00:44:03,630
I niby osiągnął koniec listy.

952
00:44:03,630 --> 00:44:05,680
I wydawało się, że ustalona
wszystkie błędy, ale nie.

953
00:44:05,680 --> 00:44:08,510
Ponieważ w tym przypadku, niektóre numery
mogło pęcherzykami bliżej

954
00:44:08,510 --> 00:44:10,410
do innych numerów
nadal są poza kolejnością.

955
00:44:10,410 --> 00:44:12,951
Więc zróbmy to jeszcze raz, i będę
po prostu zrobić to w miejscu tym razem.

956
00:44:12,951 --> 00:44:14,170
Jeden i trzy?

957
00:44:14,170 --> 00:44:14,720
W porządku.

958
00:44:14,720 --> 00:44:16,070
Trzy i dwa?

959
00:44:16,070 --> 00:44:17,560
Oczywiście nie, więc zmieńmy to.

960
00:44:17,560 --> 00:44:19,160
Tak więc dwa, trzy.

961
00:44:19,160 --> 00:44:21,340
Trzy i cztery?

962
00:44:21,340 --> 00:44:24,370
A teraz po prostu być
Szczególnie pedantyczne tutaj.

963
00:44:24,370 --> 00:44:26,350
Jest klasyfikowane?

964
00:44:26,350 --> 00:44:29,280
Wy, ludzie wiedzą, że jest posortowana.

965
00:44:29,280 --> 00:44:30,400
>> powinienem spróbować ponownie.

966
00:44:30,400 --> 00:44:31,900
Więc Olivia proponuje spróbować ponownie.

967
00:44:31,900 --> 00:44:32,530
Czemu?

968
00:44:32,530 --> 00:44:35,810
Ponieważ komputer nie ma
luksus naszych ludzkich oczu

969
00:44:35,810 --> 00:44:38,080
po prostu spoglądając back-- OK, skończę.

970
00:44:38,080 --> 00:44:41,610
Jak ustalić, czy komputer
że lista jest teraz posortowana?

971
00:44:41,610 --> 00:44:44,590
Mechanicznie.

972
00:44:44,590 --> 00:44:47,650
>> muszę przejść przez
po raz kolejny, i tylko wówczas, gdy

973
00:44:47,650 --> 00:44:51,190
nie rób / znaleźliśmy żadnych błędów mogę
następnie zawrzeć jak komputer, yep,

974
00:44:51,190 --> 00:44:51,980
jesteśmy dobrze iść.

975
00:44:51,980 --> 00:44:54,850
Tak więc pierwszy i drugi, i dwa
trzy, trzy i cztery.

976
00:44:54,850 --> 00:44:58,030
Teraz mogę powiedzieć, że to definitywnie
sortowane, bo wprowadzono żadnych zmian.

977
00:44:58,030 --> 00:45:01,940
Teraz byłoby to błąd i po prostu
głupie, gdybym, komputer,

978
00:45:01,940 --> 00:45:05,640
zadawane te same pytania raz
oczekiwać różnych odpowiedzi.

979
00:45:05,640 --> 00:45:07,110
nie powinno się zdarzyć.

980
00:45:07,110 --> 00:45:08,600
>> A więc teraz lista jest sortowana.

981
00:45:08,600 --> 00:45:12,630
Niestety, czasu prowadzenia
algorytm ten jest również n do kwadratu.

982
00:45:12,630 --> 00:45:13,130
Czemu?

983
00:45:13,130 --> 00:45:19,520
Ponieważ masz numery n, aw
najgorszym przypadku trzeba przenieść numery n

984
00:45:19,520 --> 00:45:23,637
n razy, bo trzeba iść dalej
Powrót do sprawdzenia i ewentualnie naprawić

985
00:45:23,637 --> 00:45:24,220
te numery.

986
00:45:24,220 --> 00:45:26,280
I możemy zrobić więcej
analiza formalna, too.

987
00:45:26,280 --> 00:45:29,530
>> Więc to wszystko powiedzieć podjęliśmy
trzy różne sposoby, jeden

988
00:45:29,530 --> 00:45:32,210
z nich natychmiast intuicyjne
przy bat z Benem

989
00:45:32,210 --> 00:45:35,170
do mojego proponowane umieszczenie
porządek do tego

990
00:45:35,170 --> 00:45:38,540
gdzie rodzaj zapominać
las na pierwotnie drzew.

991
00:45:38,540 --> 00:45:41,760
Ale jeśli zrobić krok do tyłu,
voila, mamy ustalone pojęcie sortowania.

992
00:45:41,760 --> 00:45:43,824
Tak to jest, śmiem twierdzić,
niższy poziom może

993
00:45:43,824 --> 00:45:45,740
niż niektóre z tych innych
algorytmy, ale spójrzmy prawdzie

994
00:45:45,740 --> 00:45:48,550
sprawdzić, czy nie możemy wizualizować
ich drodze tego.

995
00:45:48,550 --> 00:45:51,450
>> Więc to jest jakiś ładny
Oprogramowanie, że ktoś

996
00:45:51,450 --> 00:45:56,110
napisał użyciu kolorowych pasków to
zamiar wykonać następujące czynności za nas.

997
00:45:56,110 --> 00:45:57,736
Każdy z tych prętów stanowi liczbę.

998
00:45:57,736 --> 00:46:00,026
Wyższy pasek, tym większa
liczba, mniejszy bar,

999
00:46:00,026 --> 00:46:00,990
Im mniejsza liczba.

1000
00:46:00,990 --> 00:46:05,880
Więc idealnie chcemy piękny piramidę
gdzie zaczyna się mały i robi się duży,

1001
00:46:05,880 --> 00:46:08,330
a to oznaczałoby, że
Te paski są klasyfikowane.

1002
00:46:08,330 --> 00:46:11,200
Więc mam zamiar iść do przodu i wyboru,
na przykład algorytm Bena

1003
00:46:11,200 --> 00:46:13,990
first-- wyboru sortowania.

1004
00:46:13,990 --> 00:46:16,220
>> I zauważyć, co robi.

1005
00:46:16,220 --> 00:46:18,670
Sposób, w jaki wybrałeś do
wizualizację tego algorytmu

1006
00:46:18,670 --> 00:46:22,090
jest to, że podobnie jak ja
chodząc mojej liście,

1007
00:46:22,090 --> 00:46:24,710
Ten program idzie
poprzez liście numerów

1008
00:46:24,710 --> 00:46:28,160
podkreślając w różowym każdego
Numer że to patrzy.

1009
00:46:28,160 --> 00:46:32,360
A co wydarzy się teraz?

1010
00:46:32,360 --> 00:46:35,154
>> Najmniejsza liczba, która
I albo Ben znalazł się nagle

1011
00:46:35,154 --> 00:46:36,820
zostaje przeniesiona do początku listy.

1012
00:46:36,820 --> 00:46:40,037
I zauważ zrobili eksmisji
numer, który był tam,

1013
00:46:40,037 --> 00:46:41,120
i to jest całkowicie w porządku.

1014
00:46:41,120 --> 00:46:42,600
I nie dostać się do tego poziomu szczegółowości.

1015
00:46:42,600 --> 00:46:44,308
Ale musimy umieścić
liczba gdzieś

1016
00:46:44,308 --> 00:46:47,775
więc po prostu przeniósł go do
open spot, który został utworzony.

1017
00:46:47,775 --> 00:46:49,900
Więc mam zamiar przyspieszyć ten
w górę, ponieważ w przeciwnym wypadku

1018
00:46:49,900 --> 00:46:51,871
Szybko staje się bardzo uciążliwe.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animacja speed-- tam idziemy.

1021
00:46:58,600 --> 00:47:01,850
Więc teraz sama zasada
Byłem stosowania, ale

1022
00:47:01,850 --> 00:47:06,540
może zacząć czuć się algorytm, jeśli
woli lub zobaczyć trochę jaśniej.

1023
00:47:06,540 --> 00:47:13,190
I to algorytm daje efekt
Wybór następnego najmniejszy element,

1024
00:47:13,190 --> 00:47:16,422
więc masz zamiar zacząć
zobaczyć to na ziemi się po lewej stronie.

1025
00:47:16,422 --> 00:47:19,130
I na każdej iteracji, jak ja
Proponuje, robi się trochę mniej pracy.

1026
00:47:19,130 --> 00:47:21,921
To nie musi przejść całą drogę
z powrotem do lewego końca listy,

1027
00:47:21,921 --> 00:47:23,900
dlatego, że już
zna te są klasyfikowane.

1028
00:47:23,900 --> 00:47:28,129
Więc to rodzaj czuje się jak to jest
przyspieszenie, choć każdy krok jest

1029
00:47:28,129 --> 00:47:29,420
biorąc taką samą ilość czasu.

1030
00:47:29,420 --> 00:47:31,600
Jest po prostu mniej etapów pozostałe.

1031
00:47:31,600 --> 00:47:35,240
I teraz można poczuć rodzaju
Algorytm oczyszczenie koniec,

1032
00:47:35,240 --> 00:47:37,040
a nawet teraz jest posortowana.

1033
00:47:37,040 --> 00:47:41,620
>> Więc Sortowanie przez wstawianie jest wszystko zrobione.

1034
00:47:41,620 --> 00:47:43,600
Muszę ponownie losowy tablicy.

1035
00:47:43,600 --> 00:47:45,940
A może po prostu zauważyć, że
utrzymać go losowanie,

1036
00:47:45,940 --> 00:47:50,630
a my przybliżenie
To samo podejście, Sortowanie przez wstawianie.

1037
00:47:50,630 --> 00:47:55,050
Pozwól mi go spowolnić tutaj.

1038
00:47:55,050 --> 00:47:56,915
Zacznijmy że ponad.

1039
00:47:56,915 --> 00:47:57,414
Zatrzymaj się.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Pomińmy cztery.

1042
00:48:02,410 --> 00:48:03,200
No to jedziemy.

1043
00:48:03,200 --> 00:48:04,190
Losowy, one tablicę.

1044
00:48:04,190 --> 00:48:05,555
I tu go-- Sortowanie przez wstawianie.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Grać.

1047
00:48:12,800 --> 00:48:17,280
Zauważ, że ma do czynienia ze sobą
Element napotka od razu,

1048
00:48:17,280 --> 00:48:20,282
jeśli jednak przynależy
złe miejsce zawiadomienie

1049
00:48:20,282 --> 00:48:21,740
wszystkie prace, które ma się wydarzyć.

1050
00:48:21,740 --> 00:48:24,700
Musimy zachować przesunięcie więcej
i więcej elementów, aby zrobić miejsce

1051
00:48:24,700 --> 00:48:27,340
dla jednej chcemy wprowadzić w życie.

1052
00:48:27,340 --> 00:48:30,740
>> Dlatego skupiamy się na
lewy koniec tylko listy.

1053
00:48:30,740 --> 00:48:34,460
Zauważ, że nawet nie spojrzał at-- my
nie podkreślono w różowej niczym

1054
00:48:34,460 --> 00:48:35,610
w prawo.

1055
00:48:35,610 --> 00:48:38,180
Jesteśmy po prostu do czynienia z
problemy jak idziemy,

1056
00:48:38,180 --> 00:48:40,430
ale my tworzymy dużo
pracować dla siebie miejscu.

1057
00:48:40,430 --> 00:48:44,410
A więc jeśli to przyspieszyć
Teraz, aby przejść do końca,

1058
00:48:44,410 --> 00:48:46,210
ma inny klimat do niego rzeczywiście.

1059
00:48:46,210 --> 00:48:50,150
To jest po prostu skupienie się na lewym końcu, ale
robi trochę więcej pracy jako needed--

1060
00:48:50,150 --> 00:48:53,230
rodzaj wygładzania rzeczy
powyżej, naprawie,

1061
00:48:53,230 --> 00:48:58,350
ale ostatecznie do czynienia z
każdy element pojedynczo

1062
00:48:58,350 --> 00:49:07,740
aż dojdziemy dobrze the--, mamy
Wszyscy wiemy, jak to się skończy,

1063
00:49:07,740 --> 00:49:09,700
więc jest to trochę rozczarowująca może.

1064
00:49:09,700 --> 00:49:12,830
>> Ale lista w end--
spoiler-- ma być sortowana.

1065
00:49:12,830 --> 00:49:15,300
Więc spójrzmy na jeden ostatni.

1066
00:49:15,300 --> 00:49:16,840
Nie możemy teraz przejść dalej.

1067
00:49:16,840 --> 00:49:18,000
Prawie jesteśmy na miejscu.

1068
00:49:18,000 --> 00:49:19,980
Dwa iść, jeden iść.

1069
00:49:19,980 --> 00:49:22,680
I voila.

1070
00:49:22,680 --> 00:49:23,450
Doskonały.

1071
00:49:23,450 --> 00:49:27,220
>> Więc teraz zróbmy jeden ostatni,
ponowne losowanie z bubble rodzaju.

1072
00:49:27,220 --> 00:49:31,690
I tutaj odnotować, szczególnie jeśli go zwolnić
w dół, ten nie zachowuje swooping wskroś.

1073
00:49:31,690 --> 00:49:36,830
Należy jednak zauważyć, że po prostu sprawia, parami
comparisons-- rodzaju lokalnych rozwiązań.

1074
00:49:36,830 --> 00:49:39,050
Ale jak tylko dostać się do
Koniec listy w kolorze różowym,

1075
00:49:39,050 --> 00:49:40,690
co się ma zdarzyć się ponownie?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Tak, to będzie musiał
zacząć od nowa, bo tylko

1078
00:49:46,830 --> 00:49:49,870
stałe parami błędy.

1079
00:49:49,870 --> 00:49:53,120
A to może jeszcze ujawnił innych.

1080
00:49:53,120 --> 00:49:58,950
A więc jeśli to przyspieszyć, będziesz
zobaczyć, że, podobnie jak sama nazwa wskazuje,

1081
00:49:58,950 --> 00:50:01,870
mniejsze elements-- lub raczej
większe elements-- zaczynają

1082
00:50:01,870 --> 00:50:03,740
bulgotać do góry, jeśli będzie.

1083
00:50:03,740 --> 00:50:07,380
A mniejsze elementy są
zaczynają bańki do lewej.

1084
00:50:07,380 --> 00:50:10,780
I rzeczywiście, to jest rodzaj
efekt wizualny, jak również.

1085
00:50:10,780 --> 00:50:17,150
I tak będzie to skończyć wykończenia
w podobny sposób także.

1086
00:50:17,150 --> 00:50:19,160
>> Nie musimy mieszkać
w tym konkretnym jeden.

1087
00:50:19,160 --> 00:50:21,010
Pozwól mi otworzyć to teraz też.

1088
00:50:21,010 --> 00:50:24,040
Istnieje kilka innych algorytmów sortowania
na świecie, spośród których kilka

1089
00:50:24,040 --> 00:50:25,580
są ujęte tutaj.

1090
00:50:25,580 --> 00:50:29,960
A zwłaszcza dla uczniów, którzy nie są
niekoniecznie wizualne czy matematyczne,

1091
00:50:29,960 --> 00:50:31,930
jak przedtem, możemy
tak samo postępują audially

1092
00:50:31,930 --> 00:50:34,210
jeśli skojarzyć dźwięk z tym.

1093
00:50:34,210 --> 00:50:36,990
I tylko dla zabawy, tu jest
Kilka różnych algorytmów,

1094
00:50:36,990 --> 00:50:40,950
a jeden z nich, w szczególności, że jesteś
odnotuje nazywa się "scalania sortowania."

1095
00:50:40,950 --> 00:50:43,250
>> Właściwie jest to zasadniczy
lepszy algorytm,

1096
00:50:43,250 --> 00:50:45,860
takie, które łączą się porządek, jeden z
te, które sami zobaczycie,

1097
00:50:45,860 --> 00:50:49,170
Kolejność nie jest n do kwadratu.

1098
00:50:49,170 --> 00:50:57,280
To na zlecenie n razy logarytmicznej
n, która jest faktycznie mniejsza, a zatem

1099
00:50:57,280 --> 00:50:58,940
szybciej niż tych pozostałych trzech.

1100
00:50:58,940 --> 00:51:00,670
I tam jest kilka innych
głupie te, które zobaczymy.

1101
00:51:00,670 --> 00:51:01,933
>> Więc jedziemy z jakimś dźwiękiem.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
To Sortowanie przez wstawianie, więc ponownie
to jest po prostu do czynienia z elementami

1104
00:51:10,490 --> 00:51:13,420
jak przychodzą.

1105
00:51:13,420 --> 00:51:17,180
Jest to sortowanie bąbelkowe, dlatego
biorąc pod uwagę ich par na raz.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
I znowu największe elementy
pęcherzyków są do góry.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Następna w kolejce wyboru sortowania.

1110
00:51:41,710 --> 00:51:45,420
Ben jest algorytmem, w którym
znowu się wybierając iteracyjnie

1111
00:51:45,420 --> 00:51:46,843
następny najmniejszy element.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
I znowu, teraz naprawdę można usłyszeć, że
to przyspieszenie, ale tylko w takim zakresie,

1114
00:51:53,900 --> 00:51:58,230
jak to robi się coraz mniej
pracować w każdej iteracji.

1115
00:51:58,230 --> 00:52:04,170
Jest to szybszy, scalanie sortowanie,
który jest sortowaniu skupiska liczbach

1116
00:52:04,170 --> 00:52:05,971
razem, a następnie ich łączenie.

1117
00:52:05,971 --> 00:52:07,720
Więc look-- lewy
połowa jest już posortowana.

1118
00:52:07,720 --> 00:52:14,165
>> Teraz to sortowaniu prawą połowę, a
Teraz to się je połączyć w jeden.

1119
00:52:14,165 --> 00:52:19,160
To jest coś, co nazywa "Gnom porządek".

1120
00:52:19,160 --> 00:52:23,460
I można zobaczyć, że rodzaj
to tam iz powrotem,

1121
00:52:23,460 --> 00:52:27,950
ustalające pracy trochę tu i
tam, zanim przystąpi do nowej pracy.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
I to wszystko.

1124
00:52:33,692 --> 00:52:36,400
Jest jeszcze inny porządek, który jest
naprawdę tylko do celów naukowych,

1125
00:52:36,400 --> 00:52:40,980
nazywa się "głupi porządek", który trwa
Twoje dane, sortuje je losowo,

1126
00:52:40,980 --> 00:52:43,350
a następnie sprawdza, czy jest posortowana.

1127
00:52:43,350 --> 00:52:47,880
A jeśli nie jest, to ponownie sortuje się
losowo, sprawdza, czy to sortowane,

1128
00:52:47,880 --> 00:52:49,440
a jeśli nie powtarza.

1129
00:52:49,440 --> 00:52:52,660
I teoretycznie probabilistycznie
to zakończy,

1130
00:52:52,660 --> 00:52:54,140
ale po całkiem sporo czasu.

1131
00:52:54,140 --> 00:52:56,930
To nie jest najbardziej
efektywne algorytmy.

1132
00:52:56,930 --> 00:53:02,550
Więc wszelkie pytania dotyczące tych
Poszczególne algorytmy lub cokolwiek

1133
00:53:02,550 --> 00:53:04,720
związane też tam?

1134
00:53:04,720 --> 00:53:09,430
>> No cóż, teraz odciąć co wszyscy
linie te są takie, że byłem rysunek

1135
00:53:09,430 --> 00:53:15,090
i co ja zakładając komputer
może to zrobić pod maską.

1136
00:53:15,090 --> 00:53:18,650
Uważam, że wszystkie te numery
Trzymam drawing-- muszą się

1137
00:53:18,650 --> 00:53:21,330
gdzie przechowywane w pamięci.

1138
00:53:21,330 --> 00:53:24,130
Będziemy pozbyć się tego faceta, teraz też.

1139
00:53:24,130 --> 00:53:30,110
>> Więc kawałek pamięci w
computer-- więc RAM DIMM

1140
00:53:30,110 --> 00:53:35,480
czego szukaliśmy wczoraj, podwójny
inline memory module-- wygląda następująco.

1141
00:53:35,480 --> 00:53:39,370
I każdy z tych małych czarnych żetonów
pewna liczba bajtów, zwykle.

1142
00:53:39,370 --> 00:53:44,380
A potem złote szpilki są jak
przewody łączące go do komputera,

1143
00:53:44,380 --> 00:53:47,521
a zielona deska krzemu jest po prostu
co trzyma wszystko razem.

1144
00:53:47,521 --> 00:53:48,770
Więc co to tak naprawdę znaczy?

1145
00:53:48,770 --> 00:53:53,180
Gdybym rodzaju wyciągnąć ten sam obraz,
Załóżmy dla uproszczenia

1146
00:53:53,180 --> 00:53:55,280
że ten DIMM, podwójny
wbudowany moduł pamięci,

1147
00:53:55,280 --> 00:54:00,530
jest jeden gigabajt pamięci RAM, jeden gigabajt
Pamięć, która jest, jak wiele bajtów całkowita?

1148
00:54:00,530 --> 00:54:02,100
Jeden gigabajt to ile bajtów?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Więcej niż to.

1151
00:54:06,030 --> 00:54:09,960
1124 jest kilo, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega jest miliony.

1153
00:54:11,730 --> 00:54:14,570
Giga jest miliard.

1154
00:54:14,570 --> 00:54:15,070
>> Ja kłamie?

1155
00:54:15,070 --> 00:54:16,670
Możemy nawet czytać etykiety?

1156
00:54:16,670 --> 00:54:19,920
To jest rzeczywiście 128
gigabajtów, więc jest to bardziej.

1157
00:54:19,920 --> 00:54:22,130
Ale będziemy udawać, że to
Jest tylko jeden gigabajt.

1158
00:54:22,130 --> 00:54:25,640
To znaczy, nie ma miliard
bajtów pamięci dostępnej do mnie

1159
00:54:25,640 --> 00:54:29,770
lub 8 miliardów bitów, ale będziemy
mówić w bajtach teraz

1160
00:54:29,770 --> 00:54:30,750
posuwa się naprzód.

1161
00:54:30,750 --> 00:54:36,330
>> Więc co to znaczy, to jest
jeden bajt, to kolejny bajt

1162
00:54:36,330 --> 00:54:38,680
Jest to kolejny bajt
a jeśli bardzo chcieliśmy

1163
00:54:38,680 --> 00:54:43,280
za szczególne musielibyśmy
narysować mld małe kwadraty.

1164
00:54:43,280 --> 00:54:44,320
Ale co to znaczy?

1165
00:54:44,320 --> 00:54:46,420
Dobrze, niech mi tylko powiększyć
w na tym zdjęciu.

1166
00:54:46,420 --> 00:54:50,900
Jeśli mam coś, co wygląda
jak to teraz, to cztery bajty.

1167
00:54:50,900 --> 00:54:53,710
>> A więc mogłem umieścić tu cztery cyfry.

1168
00:54:53,710 --> 00:54:54,990
Jeden dwa trzy cztery.

1169
00:54:54,990 --> 00:55:00,170
Albo może umieścić cztery litery lub symbole.

1170
00:55:00,170 --> 00:55:02,620
"Hej!" może pójść tam,
ponieważ każda z liter

1171
00:55:02,620 --> 00:55:04,370
omówiliśmy wcześniej,
może być reprezentowany

1172
00:55:04,370 --> 00:55:06,650
z ośmiu bitów lub ASCII lub bajt.

1173
00:55:06,650 --> 00:55:09,370
Więc innymi słowy, można
umieścić rzeczy w środku 8 mld

1174
00:55:09,370 --> 00:55:11,137
tego jednego kija pamięci.

1175
00:55:11,137 --> 00:55:14,345
Teraz co to znaczy, aby to odwrócić
z powrotem do tyłu w pamięci w taki sposób?

1176
00:55:14,345 --> 00:55:17,330
To jest to, co programista
nazwałbym to "tablicę".

1177
00:55:17,330 --> 00:55:21,250
W programie komputerowym, nie sądzę
o sprzęcie bazowych, per se.

1178
00:55:21,250 --> 00:55:24,427
Wystarczy myśleć o sobie jako posiadające
Dostęp do miliard bajtów sumie

1179
00:55:24,427 --> 00:55:26,010
i można cokolwiek chcesz z nim.

1180
00:55:26,010 --> 00:55:27,880
Ale dla wygody
to ogólnie przydatne

1181
00:55:27,880 --> 00:55:31,202
aby utrzymać prawo pamięci
obok siebie w taki sposób.

1182
00:55:31,202 --> 00:55:33,660
Więc gdybym powiększyć this--
dlatego, że nie jesteśmy na pewno będzie

1183
00:55:33,660 --> 00:55:39,310
narysować mld małe squares--
załóżmy, że ta płyta reprezentuje

1184
00:55:39,310 --> 00:55:40,610
że kij pamięci teraz.

1185
00:55:40,610 --> 00:55:43,800
A ja po prostu wyciągnąć tyle, ile moja
Znacznik kończy się dając mnie tutaj.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Więc teraz mamy kij
pamięci na pokładzie

1188
00:55:52,300 --> 00:55:56,400
który ma jeden, dwa, trzy, cztery, pięć,
sześciu, jeden, dwa, trzy, cztery, pięć, sześć,

1189
00:55:56,400 --> 00:56:01,130
seven-- więc 42 bajtów
Pamięć w całości na ekranie.

1190
00:56:01,130 --> 00:56:01,630
Dziękuję Ci.

1191
00:56:01,630 --> 00:56:02,838
Tak, tak moja arytmetyczne w prawo.

1192
00:56:02,838 --> 00:56:05,120
So 42 bajtów pamięci tutaj.

1193
00:56:05,120 --> 00:56:06,660
Więc co to właściwie znaczy?

1194
00:56:06,660 --> 00:56:09,830
Dobrze, programista komputerowy
faktycznie na ogół

1195
00:56:09,830 --> 00:56:12,450
myśleć o tej pamięci jako adresowalnych.

1196
00:56:12,450 --> 00:56:16,630
Innymi słowy, każdy z nich
miejsca w pamięci, w sprzęcie,

1197
00:56:16,630 --> 00:56:18,030
ma unikalny adres.

1198
00:56:18,030 --> 00:56:22,020
>> To nie jest tak skomplikowane jak One Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Zamiast tego, to tylko liczba.

1200
00:56:23,830 --> 00:56:27,930
Liczba bajtów jest zero, to jest
Jeden z nich, to jest dwie, to jest trzy

1201
00:56:27,930 --> 00:56:30,327
i jest 41.

1202
00:56:30,327 --> 00:56:30,910
Poczekaj chwilę.

1203
00:56:30,910 --> 00:56:32,510
Myślałem, że powiedziałem 42 przed chwilą.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Zacząłem odliczanie od zera,
tak, że rzeczywiście poprawne.

1206
00:56:37,772 --> 00:56:40,980
Teraz nie mamy rzeczywiście wyciągnąć go
w postaci siatki, a jeśli zwrócić go w postaci siatki

1207
00:56:40,980 --> 00:56:43,520
Myślę, że w rzeczywistości rzeczy
się nieco mylące.

1208
00:56:43,520 --> 00:56:46,650
Co programista będzie,
w swoim własnym umyśle,

1209
00:56:46,650 --> 00:56:50,310
generalnie myślę o tym
Pamięć tak jest jak taśmy,

1210
00:56:50,310 --> 00:56:53,340
jak kawałek taśmy maskującej
że właśnie trwa i trwa wiecznie

1211
00:56:53,340 --> 00:56:54,980
lub dopóki nie zabraknie pamięci.

1212
00:56:54,980 --> 00:56:59,200
Więc bardziej popularnym sposobem rysowania
i po prostu myśleć o pamięci

1213
00:56:59,200 --> 00:57:03,710
jest to, że jest to bajt zero, jeden,
dwa, trzy, a następnie kropka, kropka, kropka.

1214
00:57:03,710 --> 00:57:07,650
I masz 42 bajtów sumie takie, nawet
choć fizycznie to może faktycznie

1215
00:57:07,650 --> 00:57:09,480
być czymś więcej jak ten.

1216
00:57:09,480 --> 00:57:12,850
>> Więc jeśli teraz myśleć o
Pamięć jak ten, podobnie jak taśmy,

1217
00:57:12,850 --> 00:57:17,640
to co programista ponownie
nazwałbym tablicę pamięci.

1218
00:57:17,640 --> 00:57:20,660
A jeśli chcesz faktycznie przechowywać
Coś w pamięci komputera,

1219
00:57:20,660 --> 00:57:23,290
generalnie należy przechowywać rzeczy
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Tak więc już mówić o liczbach.

1221
00:57:25,010 --> 00:57:30,880
A kiedy chciał rozwiązywać problemy
jak cztery, jeden, trzy, dwie,

1222
00:57:30,880 --> 00:57:33,820
chociaż właśnie rysunek
jedynie cztery cyfry, jeden, trzy,

1223
00:57:33,820 --> 00:57:39,490
dwa na płycie, komputer będzie
naprawdę mają tę konfigurację w pamięci.

1224
00:57:39,490 --> 00:57:43,347
>> A co byłoby obok
dwa w pamięci komputera?

1225
00:57:43,347 --> 00:57:44,680
Cóż, nie ma odpowiedzi na to.

1226
00:57:44,680 --> 00:57:45,770
Naprawdę nie wiem.

1227
00:57:45,770 --> 00:57:48,200
I tak długo, jak
Komputer nie jest potrzebny,

1228
00:57:48,200 --> 00:57:51,440
nie musisz się martwić, co będzie dalej
do numerów to nie zależy.

1229
00:57:51,440 --> 00:57:55,130
A kiedy powiedziałem wcześniej, że komputer
może wyglądać tylko jeden adres na raz

1230
00:57:55,130 --> 00:57:56,170
Jest to rodzaj dlaczego.

1231
00:57:56,170 --> 00:57:59,490
>> Nie inaczej rekordu
Player i głowica odczytująca

1232
00:57:59,490 --> 00:58:03,030
tylko jest w stanie spojrzeć na pewne
rowek w fizycznym rekordu starej szkoły

1233
00:58:03,030 --> 00:58:06,500
jednocześnie, w podobny
Czy komputer dzięki

1234
00:58:06,500 --> 00:58:09,810
jego procesora i jego
Intel zestaw instrukcji,

1235
00:58:09,810 --> 00:58:12,480
wśród których instrukcji
jest odczytywany z pamięci

1236
00:58:12,480 --> 00:58:15,590
lub zapisać memory--
komputer może tylko patrzeć

1237
00:58:15,590 --> 00:58:19,210
w jednym miejscu przy time--
Czasami ich kombinacji,

1238
00:58:19,210 --> 00:58:21,770
ale tak naprawdę tylko jedno miejsce w danym czasie.

1239
00:58:21,770 --> 00:58:24,770
Więc kiedy robiliśmy
te różne algorytmy,

1240
00:58:24,770 --> 00:58:28,110
Nie jestem tylko piśmie w
vacuum-- czterech, jeden, trzy, dwa.

1241
00:58:28,110 --> 00:58:30,849
Liczby te faktycznie należą
gdzie fizycznej pamięci.

1242
00:58:30,849 --> 00:58:32,890
Więc nie są malutkie
tranzystory lub jakiś

1243
00:58:32,890 --> 00:58:35,840
elektroniki pod
Okap przechowywania tych wartości.

1244
00:58:35,840 --> 00:58:40,460
>> A w sumie, ile bitów
udział już teraz, żeby była jasność?

1245
00:58:40,460 --> 00:58:45,580
Więc to jest cztery bajty lub
teraz jest to 32 bity całkowite.

1246
00:58:45,580 --> 00:58:49,280
Więc nie są w rzeczywistości i 32 zer
te tworzące te cztery rzeczy.

1247
00:58:49,280 --> 00:58:52,070
Jest jeszcze tutaj, ale
znowu nie dbam o to.

1248
00:58:52,070 --> 00:58:55,120
>> Więc teraz niech zadać kolejny
Pytanie używana jest pamięć,

1249
00:58:55,120 --> 00:58:57,519
dlatego, że na koniec
dnia w wariancji.

1250
00:58:57,519 --> 00:59:00,310
Bez względu na to, co możemy zrobić z
komputer, na koniec dnia

1251
00:59:00,310 --> 00:59:02,560
sprzęt jest nadal
samo pod wyciągiem.

1252
00:59:02,560 --> 00:59:04,670
Jak bym się zapisać słowo tutaj?

1253
00:59:04,670 --> 00:59:09,710
Cóż, słowo w komputerze jak
"Hej!" będą przechowywane właśnie w taki sposób.

1254
00:59:09,710 --> 00:59:12,300
A jeśli chcieliśmy dłużej
Słowo, można po prostu

1255
00:59:12,300 --> 00:59:19,120
nadpisać i powiedzieć coś
jak "cześć" i sklep, który tutaj.

1256
00:59:19,120 --> 00:59:23,930
>> I tak i tu, to contiguousness
jest rzeczywiście korzystne,

1257
00:59:23,930 --> 00:59:26,530
ponieważ komputer może po prostu
czytać od prawej do lewej.

1258
00:59:26,530 --> 00:59:28,680
Ale tu jest pytanie.

1259
00:59:28,680 --> 00:59:33,480
W związku z tym słowo
h-pl-l-l-o, Wykrzyknik,

1260
00:59:33,480 --> 00:59:38,740
jak może komputer wie, gdzie
Słowo zaczyna się i gdzie kończy się słowo?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
W kontekście liczb
Jak działa komputer

1263
00:59:43,800 --> 00:59:48,396
wiedzieć, jak długo sekwencja
Liczby są lub gdzie zaczyna?

1264
00:59:48,396 --> 00:59:50,270
Cóż, okazuje out--
i nie będziemy się zbytnio

1265
00:59:50,270 --> 00:59:54,970
na tym poziomie detail--
komputery przenieść rzeczy wokół w pamięci

1266
00:59:54,970 --> 00:59:57,800
dosłownie za pomocą tych adresów.

1267
00:59:57,800 --> 01:00:02,080
Więc w komputerze, jeśli jesteś
pisanie kodu do przechowywania rzeczy

1268
01:00:02,080 --> 01:00:05,800
jak słowa, co masz
naprawdę robi pisze

1269
01:00:05,800 --> 01:00:11,320
Wyrażenia, które pamiętają gdzie w
Pamięć komputera są te słowa.

1270
01:00:11,320 --> 01:00:14,370
Więc pozwól mi bardzo,
bardzo prosty przykład.

1271
01:00:14,370 --> 01:00:18,260
>> Mam zamiar iść do przodu i
otworzyć prosty program tekstowy,

1272
01:00:18,260 --> 01:00:20,330
i mam zamiar stworzyć
plik o nazwie hello.c.

1273
01:00:20,330 --> 01:00:22,849
Większość tych informacji możemy
Nie będę wchodził w najdrobniejszych szczegółach,

1274
01:00:22,849 --> 01:00:25,140
ale mam zamiar napisać
Program w tym samym języku,

1275
01:00:25,140 --> 01:00:31,140
C. Jest to o wiele bardziej zastraszające,
Uważam, niż Scratch,

1276
01:00:31,140 --> 01:00:32,490
ale to jest bardzo podobne w duchu.

1277
01:00:32,490 --> 01:00:34,364
W rzeczywistości, te kręcone
braces-- można rodzaju

1278
01:00:34,364 --> 01:00:37,820
myśleć o tym, co właśnie zrobił jak ten.

1279
01:00:37,820 --> 01:00:39,240
>> Zróbmy to, faktycznie.

1280
01:00:39,240 --> 01:00:45,100
Po kliknięciu zielona flaga,
rób następująco.

1281
01:00:45,100 --> 01:00:50,210
Chcę wydrukować "cześć".

1282
01:00:50,210 --> 01:00:51,500
Więc teraz jest pseudokod.

1283
01:00:51,500 --> 01:00:53,000
Jestem rodzaju rozmycia linii.

1284
01:00:53,000 --> 01:00:56,750
W C, ten język mówię
o, ta linia wydruku komentarzy

1285
01:00:56,750 --> 01:01:01,940
faktycznie staje się "printf" z
niektóre nawiasy i średnik.

1286
01:01:01,940 --> 01:01:03,480
>> Ale to jest dokładnie ten sam pomysł.

1287
01:01:03,480 --> 01:01:06,730
I to bardzo łatwy w obsłudze
"Kiedy zielona flaga kliknięciu" staje

1288
01:01:06,730 --> 01:01:10,182
znacznie bardziej ezoteryczne "int main nieważne."

1289
01:01:10,182 --> 01:01:12,890
I to naprawdę nie ma odwzorowania,
więc jestem po prostu się do tego zignorować.

1290
01:01:12,890 --> 01:01:17,210
Ale nawiasy klamrowe są jak
wygięte kawałki układanki lubią to.

1291
01:01:17,210 --> 01:01:18,700
>> Więc może trochę zgadywać.

1292
01:01:18,700 --> 01:01:22,357
Nawet jeśli nigdy wcześniej zaprogramowane wcześniej,
co robi ten program chyba zrobić?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Prawdopodobnie drukuje komentarzy
z wykrzyknikiem.

1295
01:01:28,000 --> 01:01:29,150
>> Warto więc spróbować.

1296
01:01:29,150 --> 01:01:30,800
Zamierzam ją uratować.

1297
01:01:30,800 --> 01:01:34,000
I to jest znowu bardzo
stare środowisko szkolne.

1298
01:01:34,000 --> 01:01:35,420
Nie mogę klikać, nie mogę przeciągać.

1299
01:01:35,420 --> 01:01:36,910
Mam wpisywać komendy.

1300
01:01:36,910 --> 01:01:41,320
Więc chcę uruchomić mój program, więc
Mogę to zrobić, jak hello.c.

1301
01:01:41,320 --> 01:01:42,292
To plik wpadłem.

1302
01:01:42,292 --> 01:01:43,500
Ale czekaj, jestem brakuje krok.

1303
01:01:43,500 --> 01:01:46,470
Co mówimy, jest to konieczne
krok na języku jak C?

1304
01:01:46,470 --> 01:01:49,470
Właśnie pisane źródła
Kod, ale co mi potrzebne?

1305
01:01:49,470 --> 01:01:50,670
Tak, muszę kompilator.

1306
01:01:50,670 --> 01:01:57,670
Więc na moim Macu tutaj, mam
Program nazywa się GCC, kompilatora GNU C,

1307
01:01:57,670 --> 01:02:03,990
która pozwala mi robić this-- kolej
mój kod źródłowy pod będziemy nazywać,

1308
01:02:03,990 --> 01:02:04,930
kod maszynowy.

1309
01:02:04,930 --> 01:02:10,180
>> I widzę, że
znowu, takie jak te

1310
01:02:10,180 --> 01:02:14,090
są zer i jedynek Właśnie
utworzone z mojego kodu źródłowego,

1311
01:02:14,090 --> 01:02:15,730
wszystkich zer i jedynek.

1312
01:02:15,730 --> 01:02:17,770
A jeśli chcę uruchomić
Mój program-- zdarza

1313
01:02:17,770 --> 01:02:23,010
nazywać a.out dla
historyczne reasons-- "cześć".

1314
01:02:23,010 --> 01:02:24,070
Mogę go uruchomić ponownie.

1315
01:02:24,070 --> 01:02:25,690
Witam Witam Witam.

1316
01:02:25,690 --> 01:02:27,430
I wydaje się działać.

1317
01:02:27,430 --> 01:02:31,000
>> Ale to oznacza, gdzieś w moim
Pamięć komputera są słowa

1318
01:02:31,000 --> 01:02:35,279
h-pl-l-l-o, Wykrzyknik.

1319
01:02:35,279 --> 01:02:38,070
I okazuje się, tak na marginesie,
co komputer typowo

1320
01:02:38,070 --> 01:02:40,550
zrobić tak, że wie, gdzie
wszystko zaczyna i end-- to

1321
01:02:40,550 --> 01:02:42,460
zamiar umieścić specjalny symbol tutaj.

1322
01:02:42,460 --> 01:02:46,064
I Konwencji jest umieszczenie
liczbę zero na końcu słowa

1323
01:02:46,064 --> 01:02:48,230
aby wiedzieć, gdzie jest
faktycznie kończy się, więc, że

1324
01:02:48,230 --> 01:02:52,750
nie trzymaj drukując coraz
znaków niż faktycznie zamierzają.

1325
01:02:52,750 --> 01:02:55,400
>> Ale tutaj, na wynos, nawet
choć jest to dość ezoteryczne,

1326
01:02:55,400 --> 01:02:58,140
jest to, że ostatecznie
stosunkowo prosta.

1327
01:02:58,140 --> 01:03:04,550
Ty dano rodzaju taśmy, puste
Powierzchnia, na której można pisać listy.

1328
01:03:04,550 --> 01:03:07,150
Po prostu musisz mieć
specjalny symbol, jak arbitralnie

1329
01:03:07,150 --> 01:03:10,316
liczbę zero, aby umieścić na koniec
Twoje słowa tak, że komputer wie

1330
01:03:10,316 --> 01:03:13,410
och, muszę zatrzymać drukowanie po
Widzę wykrzyknik.

1331
01:03:13,410 --> 01:03:16,090
Ponieważ Następną rzeczą jest
Jest to wartość ASCII zera,

1332
01:03:16,090 --> 01:03:19,125
lub jako znak null
ktoś by to nazwać.

1333
01:03:19,125 --> 01:03:21,500
Ale jest to rodzaj problemu
tutaj, i niech powróci

1334
01:03:21,500 --> 01:03:23,320
do numerów na chwilę.

1335
01:03:23,320 --> 01:03:28,720
Załóżmy, że mam w rzeczywistości,
tablicę liczb,

1336
01:03:28,720 --> 01:03:30,730
i załóżmy, że
Program Piszę to

1337
01:03:30,730 --> 01:03:34,680
jak książka dla nauczyciela klasy
i nauczycieli w klasie.

1338
01:03:34,680 --> 01:03:38,720
A ten program pozwala mu
wpisać w wyniki swoich uczniów

1339
01:03:38,720 --> 01:03:39,960
na quizów.

1340
01:03:39,960 --> 01:03:43,750
I załóżmy, że student dostaje
100 na swoim pierwszym quizie, może

1341
01:03:43,750 --> 01:03:49,920
jak 80 na następny, a potem
75, następnie 90 na czwartym quiz.

1342
01:03:49,920 --> 01:03:54,150
>> Więc w tym momencie w historii,
matryca ma rozmiar cztery.

1343
01:03:54,150 --> 01:03:58,470
Nie ma absolutnie więcej pamięci w
komputer, ale tablica, by tak rzec,

1344
01:03:58,470 --> 01:04:00,350
ma wielkość czterech.

1345
01:04:00,350 --> 01:04:06,060
Przypuśćmy teraz, że nauczyciel chce
przypisać piąty quizu do klasy.

1346
01:04:06,060 --> 01:04:08,510
Cóż, jedna z rzeczy,
czy ona ma zamiar zrobić

1347
01:04:08,510 --> 01:04:10,650
Teraz jest przechowywać dodatkową wartość tutaj.

1348
01:04:10,650 --> 01:04:15,490
Ale jeśli tablicy nauczyciel ma
stworzone w tym programie nie ma rozmiaru dla,

1349
01:04:15,490 --> 01:04:22,440
jednego problemu z tablicy jest
nie można po prostu dodajemy do pamięci.

1350
01:04:22,440 --> 01:04:26,470
Bo co, jeśli inna część
Program posiada słowo "hej" właśnie tam?

1351
01:04:26,470 --> 01:04:29,650
>> Innymi słowy, moja pamięć może być
wykorzystane do niczego w programie.

1352
01:04:29,650 --> 01:04:33,250
A jeśli z góry Wpisałem się, hej,
Chcę wejście czterech punktów konkursowe

1353
01:04:33,250 --> 01:04:34,784
Może idą tutaj i tutaj.

1354
01:04:34,784 --> 01:04:37,700
A jeśli nagle zmienić zdanie
później i że chcę piąty quizu

1355
01:04:37,700 --> 01:04:40,872
Wynik, nie można po prostu
umieścić go w dowolnym miejscu,

1356
01:04:40,872 --> 01:04:42,580
bo co, jeśli to
Pamięć jest używany

1357
01:04:42,580 --> 01:04:45,990
czegoś else-- innego programu
lub inna cechą programu

1358
01:04:45,990 --> 01:04:46,910
że używasz?

1359
01:04:46,910 --> 01:04:50,650
Więc trzeba myśleć z wyprzedzeniem
jak chcesz przechowywać swoje dane,

1360
01:04:50,650 --> 01:04:54,480
bo teraz już malowane
Sam do cyfrowej rogu.

1361
01:04:54,480 --> 01:04:57,280
>> Więc może zamiast nauczycielem
powiedzieć, pisząc program

1362
01:04:57,280 --> 01:04:59,360
do przechowywania jego lub jej
klas, wiesz co?

1363
01:04:59,360 --> 01:05:04,180
Mam zamiar poprosić,
pisząc swój program,

1364
01:05:04,180 --> 01:05:12,070
że chce zero, jeden, dwa, trzy,
cztery, pięć, sześć, osiem klas łącznie.

1365
01:05:12,070 --> 01:05:15,320
Tak jeden, dwa, trzy, cztery,
pięć, sześć, siedem, osiem.

1366
01:05:15,320 --> 01:05:18,612
Nauczyciel może nieco ponad przydzielić
Pamięć przy pisaniu swojego programu

1367
01:05:18,612 --> 01:05:19,570
i powiedzieć, wiesz co?

1368
01:05:19,570 --> 01:05:22,236
Nigdy nie będę przypisać więcej
niż osiem quizów w semestrze.

1369
01:05:22,236 --> 01:05:23,130
To jest po prostu szalony.

1370
01:05:23,130 --> 01:05:24,470
Nigdy nie przydziela tego.

1371
01:05:24,470 --> 01:05:28,270
Więc w ten sposób, że on lub ona ma
elastyczność w punktacji sklepu studenckich,

1372
01:05:28,270 --> 01:05:33,010
jak 75, 90, a może i jedno dodatkowe, gdzie
student dostał dodatkowy kredyt, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Ale jeśli nie nauczyciel
wykorzystuje te trzy przestrzenie,

1374
01:05:36,130 --> 01:05:38,860
jest intuicyjny wynos tutaj.

1375
01:05:38,860 --> 01:05:41,410
On lub ona jest tylko marnowanie miejsca.

1376
01:05:41,410 --> 01:05:44,790
Tak więc, innymi słowy, jest to
wspólny kompromis w programowaniu

1377
01:05:44,790 --> 01:05:48,241
gdzie można albo przydzielić
dokładnie tyle pamięci, ile chcesz,

1378
01:05:48,241 --> 01:05:51,490
Plusem jest to, z czego bardzo jesteś
efficient-- jesteś nie jest marnotrawstwem

1379
01:05:51,490 --> 01:05:54,640
w żadnym stopniu ale minusem których
to co, jeśli zmienisz zdanie, gdy

1380
01:05:54,640 --> 01:05:58,780
za pomocą programu, który chcesz zapisać
więcej danych niż pierwotnie przeznaczone.

1381
01:05:58,780 --> 01:06:03,030
>> Może więc rozwiązanie jest zatem
pisać swoje programy w taki sposób,

1382
01:06:03,030 --> 01:06:05,605
że używają więcej pamięci
niż faktycznie potrzeba.

1383
01:06:05,605 --> 01:06:07,730
W ten sposób nie będziemy
do przedostania się do tego problemu,

1384
01:06:07,730 --> 01:06:09,730
ale masz być marnotrawstwem.

1385
01:06:09,730 --> 01:06:12,960
A im więcej pamięci program używa
jak mówiliśmy wczoraj, tym mniej

1386
01:06:12,960 --> 01:06:15,410
Pamięć to dostępne
dla innych programów,

1387
01:06:15,410 --> 01:06:18,790
tym szybciej komputer może zwolnić
w dół ze względu na pamięć wirtualną.

1388
01:06:18,790 --> 01:06:22,670
A więc idealnym rozwiązaniem może być to, co?

1389
01:06:22,670 --> 01:06:24,610
>> Under-przydzielania wydaje złe.

1390
01:06:24,610 --> 01:06:27,030
Nadmierne Alokacja wydaje złe.

1391
01:06:27,030 --> 01:06:31,120
Więc co może być lepszym rozwiązaniem?

1392
01:06:31,120 --> 01:06:32,390
Realokacji.

1393
01:06:32,390 --> 01:06:33,590
Bądź bardziej dynamiczna.

1394
01:06:33,590 --> 01:06:37,520
Nie zmuszaj się do wyboru
priori, na początku, co chcesz.

1395
01:06:37,520 --> 01:06:41,370
A już na pewno nie w ciągu przyznać,
abyście nie marnotrawstwo.

1396
01:06:41,370 --> 01:06:45,770
>> I tak, aby osiągnąć ten cel,
trzeba rzucić tę strukturę danych,

1397
01:06:45,770 --> 01:06:48,100
by tak rzec, z dala.

1398
01:06:48,100 --> 01:06:51,080
A więc to, co programista
zazwyczaj wykorzystywać

1399
01:06:51,080 --> 01:06:55,940
jest coś nie jest nazywany
Tablica ale połączonej listy.

1400
01:06:55,940 --> 01:07:00,860
Innymi słowy, on lub ona będzie
zacząć myśleć o ich pamięci

1401
01:07:00,860 --> 01:07:05,280
jako swego rodzaju kształt, że
może zwrócić się w następujący sposób.

1402
01:07:05,280 --> 01:07:08,520
Jeśli chcesz zapisać jedną liczbę w
program-- więc września

1403
01:07:08,520 --> 01:07:12,600
Dałem moich uczniów quiz; chcę
przechowywanie pierwszy quiz uczniów,

1404
01:07:12,600 --> 01:07:16,220
i dostali 100 na it-- I
Zamierzam zapytać mojego komputera,

1405
01:07:16,220 --> 01:07:19,540
w drodze programu Mam
napisano na jednym fragmencie pamięci.

1406
01:07:19,540 --> 01:07:22,570
I mam zamiar przechowywać
Numer 100 w nim, i to wszystko.

1407
01:07:22,570 --> 01:07:24,820
>> Potem kilka tygodni później
kiedy się moją drugą quizu,

1408
01:07:24,820 --> 01:07:27,890
i nadszedł czas, aby wpisać
w tym 90% jadę

1409
01:07:27,890 --> 01:07:32,129
zwrócić się do komputera, hej, komputer,
Mogę mieć inny fragment pamięci?

1410
01:07:32,129 --> 01:07:34,170
To będzie dać mi tego
pusty fragment pamięci.

1411
01:07:34,170 --> 01:07:39,370
Mam zamiar umieścić w liczbie 90,
ale w moim programie jakoś other--

1412
01:07:39,370 --> 01:07:42,100
i nie będziemy martwić
składnia this-- muszę

1413
01:07:42,100 --> 01:07:44,430
jakoś połączyć te rzeczy razem.

1414
01:07:44,430 --> 01:07:47,430
A ja je razem z łańcucha
wygląda jak strzała tutaj.

1415
01:07:47,430 --> 01:07:50,050
>> Trzeci quizu, który pojawia się,
Idę powiedzieć, hej, komputer,

1416
01:07:50,050 --> 01:07:51,680
daj mi jeszcze kawałek pamięci.

1417
01:07:51,680 --> 01:07:54,660
I zamierzam odłożyć
cokolwiek to było, jak 75,

1418
01:07:54,660 --> 01:07:56,920
i mam do tego łańcucha
teraz razem jakoś.

1419
01:07:56,920 --> 01:08:00,290
Czwarty quizu przychodzi, a może
to pod koniec semestru.

1420
01:08:00,290 --> 01:08:03,140
I w tym momencie mojego programu
Może być używana jest pamięć

1421
01:08:03,140 --> 01:08:05,540
wszędzie, na całym fizycznie.

1422
01:08:05,540 --> 01:08:08,170
I tak po prostu dla zabawy, jestem
zamiar wyciągnąć to dalej

1423
01:08:08,170 --> 01:08:11,260
quiz-- zapomniałem co to było; ja
że być może 80 lub something--

1424
01:08:11,260 --> 01:08:12,500
sposób tutaj.

1425
01:08:12,500 --> 01:08:15,920
>> Ale to dobrze, bo obrazowo
Zamierzam wyciągnąć tę linię.

1426
01:08:15,920 --> 01:08:19,063
Innymi słowy, w rzeczywistości
w sprzęcie komputera,

1427
01:08:19,063 --> 01:08:20,979
pierwszy wynik może
kończy się tutaj, ponieważ jest to

1428
01:08:20,979 --> 01:08:22,529
zaraz na początku semestru.

1429
01:08:22,529 --> 01:08:25,810
Kolejny może skończyć się tutaj
bo trochę czasu minęło

1430
01:08:25,810 --> 01:08:27,210
a program ciągle działa.

1431
01:08:27,210 --> 01:08:30,060
Następny wynik, który był
75, może być tutaj.

1432
01:08:30,060 --> 01:08:33,420
I ostatni wynik może być
80, co jest tutaj.

1433
01:08:33,420 --> 01:08:38,729
>> Tak więc w rzeczywistości, fizycznie, to może być
co pamięci komputera wygląda.

1434
01:08:38,729 --> 01:08:41,569
Ale nie jest to psychicznym użyteczne
Paradygmat dla programisty komputerowego.

1435
01:08:41,569 --> 01:08:44,649
Dlaczego warto dbać gdzie
cholery dane są kończąc?

1436
01:08:44,649 --> 01:08:46,200
Chcesz tylko do przechowywania danych.

1437
01:08:46,200 --> 01:08:49,390
>> Jest to coś w rodzaju naszej dyskusji
wcześniej rysowania sześcian.

1438
01:08:49,390 --> 01:08:52,200
Dlaczego cię to obchodzi, co
kąt jest sześcianu

1439
01:08:52,200 --> 01:08:53,740
i jak trzeba skręcić, żeby go wyciągnąć?

1440
01:08:53,740 --> 01:08:54,950
Chcesz tylko kostkę.

1441
01:08:54,950 --> 01:08:57,359
Podobnie Tutaj
po prostu chcą książki gatunku.

1442
01:08:57,359 --> 01:08:59,559
Po prostu chcę myśleć o
to jako lista numerów.

1443
01:08:59,559 --> 01:09:01,350
Kogo to obchodzi, jak to jest
realizowane sprzętowo?

1444
01:09:01,350 --> 01:09:05,180
>> Więc teraz abstrakcji
Ten obraz jest tutaj.

1445
01:09:05,180 --> 01:09:07,580
Jest to związane listy, a
programista byłoby to nazwać,

1446
01:09:07,580 --> 01:09:10,640
ile masz
Lista oczywiście liczb.

1447
01:09:10,640 --> 01:09:14,990
Ale to związane obrazowo
poprzez te strzałkami

1448
01:09:14,990 --> 01:09:18,510
i wszystkie te strzały are-- spodu
kaptur, jeśli jesteś ciekaw,

1449
01:09:18,510 --> 01:09:23,210
Przypomnijmy, że nasza fizyczna sprzęt ma
Adresy zero, jeden, dwa, trzy, cztery.

1450
01:09:23,210 --> 01:09:28,465
Wszystkie te strzały są to jak mapa
lub kierunki, gdzie jeśli 90 is-- teraz

1451
01:09:28,465 --> 01:09:29,090
Muszę policzyć.

1452
01:09:29,090 --> 01:09:31,750
>> Zero, jeden, dwa, trzy,
cztery, pięć, sześć, siedem lat.

1453
01:09:31,750 --> 01:09:35,640
Wygląda na to, że 90 jest
pamięć numeru adresu siedem.

1454
01:09:35,640 --> 01:09:38,460
Wszystkie te strzały są to
jak mały skrawek papieru

1455
01:09:38,460 --> 01:09:42,439
która daje wskazówki do
Program, który mówi, zgodnie z mapą

1456
01:09:42,439 --> 01:09:43,880
aby dostać się do miejsca siódmego.

1457
01:09:43,880 --> 01:09:46,680
I nie znajdziesz
Drugi wynik quizu studenta.

1458
01:09:46,680 --> 01:09:52,100
Tymczasem 75-- gdybym dalej,
to jest siedem, osiem, dziewięć, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Ta druga strzałka po prostu reprezentuje
mapa do lokalizacji pamięci 15.

1461
01:09:59,080 --> 01:10:02,550
Ale znowu, programista zazwyczaj robi
Nie dbają o takim poziomie szczegółowości.

1462
01:10:02,550 --> 01:10:05,530
I w większości każdym programowaniu
dziś język, programista

1463
01:10:05,530 --> 01:10:10,490
nawet nie wiem, gdzie w pamięci
Liczby te są w rzeczywistości.

1464
01:10:10,490 --> 01:10:14,830
Wszystko on lub ona musi dbać o to,
które są w pewien sposób ze sobą powiązane

1465
01:10:14,830 --> 01:10:18,390
w strukturze danych, takich jak to.

1466
01:10:18,390 --> 01:10:21,580
>> Ale okazuje się, nie
dostać się zbyt techniczne.

1467
01:10:21,580 --> 01:10:27,430
Ale tylko dlatego, że może być może
sobie pozwolić na tę dyskusję tutaj

1468
01:10:27,430 --> 01:10:33,630
załóżmy, że mamy ponownie
Ten problem tutaj tablicy.

1469
01:10:33,630 --> 01:10:35,780
Zobaczmy, czy żałujemy tutaj.

1470
01:10:35,780 --> 01:10:42,950
To 100, 90, 75 i 80.

1471
01:10:42,950 --> 01:10:44,980
>> Pozwolę sobie pokrótce dokonać tego twierdzenia.

1472
01:10:44,980 --> 01:10:48,980
Jest to tablica, a kolejny
znamienną cechą tablicy

1473
01:10:48,980 --> 01:10:52,400
jest to, że wszystkie dane są z powrotem do
plecami do siebie w memory-- dosłownie

1474
01:10:52,400 --> 01:10:56,830
jeden bajt lub może cztery bajty,
część stała liczba bajtów dalej.

1475
01:10:56,830 --> 01:11:00,710
W połączonej listy, które możemy wyciągnąć
jak ten, który pod maską

1476
01:11:00,710 --> 01:11:02,000
wie, gdzie te rzeczy jest?

1477
01:11:02,000 --> 01:11:03,630
To nawet nie musi płynąć w ten sposób.

1478
01:11:03,630 --> 01:11:06,050
Niektóre dane mogą być
z powrotem do lewej na górze.

1479
01:11:06,050 --> 01:11:07,530
Nawet nie wiem.

1480
01:11:07,530 --> 01:11:15,430
>> I tak z tablicą, masz
Funkcja zwana losowego dostępu.

1481
01:11:15,430 --> 01:11:20,570
A co oznacza swobodnym dostępie
że komputer może przeskoczyć od razu

1482
01:11:20,570 --> 01:11:22,730
do dowolnego miejsca w tablicy.

1483
01:11:22,730 --> 01:11:23,580
Czemu?

1484
01:11:23,580 --> 01:11:26,000
Ponieważ komputer wie
że pierwsze położenie jest

1485
01:11:26,000 --> 01:11:29,540
zero, jeden, dwa, trzy.

1486
01:11:29,540 --> 01:11:33,890
>> A więc jeśli chcesz jechać z
ten element do następnego elementu,

1487
01:11:33,890 --> 01:11:36,099
dosłownie, w
Umysł komputera, wystarczy dodać jeden.

1488
01:11:36,099 --> 01:11:39,140
Jeśli chcesz, aby przejść do trzeciego elementu,
wystarczy dodać jedno- następnego elementu, po prostu

1489
01:11:39,140 --> 01:11:40,290
dodać.

1490
01:11:40,290 --> 01:11:42,980
Jednakże, w tej wersji
historii, przypuśćmy

1491
01:11:42,980 --> 01:11:46,080
komputer jest obecnie poszukuje
na lub do czynienia z numerem 100.

1492
01:11:46,080 --> 01:11:49,770
W jaki sposób można dostać się do następnego
klasy w książce klasy?

1493
01:11:49,770 --> 01:11:52,560
>> Trzeba wziąć siedem
Kroki, które jest arbitralne.

1494
01:11:52,560 --> 01:11:58,120
Aby dostać się do następnego, trzeba
podjąć kolejne osiem kroków, aby dostać się do 15.

1495
01:11:58,120 --> 01:12:02,250
Innymi słowy, nie jest
stały odstęp między liczbami,

1496
01:12:02,250 --> 01:12:04,857
i tak to właśnie bierze
komputer jeszcze raz o to chodzi.

1497
01:12:04,857 --> 01:12:06,940
Komputer musi szukać
przez pamięć w celu

1498
01:12:06,940 --> 01:12:08,990
znaleźć to, czego szukasz.

1499
01:12:08,990 --> 01:12:14,260
>> Więc podczas gdy tablica wydaje się być
structure-- szybka danych, bo ciebie

1500
01:12:14,260 --> 01:12:17,610
dosłownie można po prostu zrobić prostą arytmetykę
i dotrzeć tam, gdzie chcesz, dodając jeden,

1501
01:12:17,610 --> 01:12:21,300
dla instance-- połączonej listy,
poświęcić tej funkcji.

1502
01:12:21,300 --> 01:12:24,020
Nie można po prostu przejść od pierwszego
z drugiej do trzeciej, czwartej.

1503
01:12:24,020 --> 01:12:25,240
Trzeba śledzić mapę.

1504
01:12:25,240 --> 01:12:28,160
Trzeba podjąć kolejne kroki
aby dostać się do tych wartości, które

1505
01:12:28,160 --> 01:12:30,230
wydaje się być dodanie kosztów.

1506
01:12:30,230 --> 01:12:35,910
Więc płacimy cenę, ale to, co było
Cechą, która Dan szukał tutaj?

1507
01:12:35,910 --> 01:12:38,110
Co połączonej listy
widocznie pozwalają nam robić,

1508
01:12:38,110 --> 01:12:40,240
co było pochodzenie
ta szczególna historia?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Dokładnie.

1511
01:12:43,830 --> 01:12:46,220
Dynamiczny rozmiar do niego.

1512
01:12:46,220 --> 01:12:48,040
Możemy dodać do tej listy.

1513
01:12:48,040 --> 01:12:51,430
Możemy nawet kurczą listę, więc
że jesteśmy tylko przy tak dużej ilości pamięci

1514
01:12:51,430 --> 01:12:55,560
tak właściwie chcemy i tak
Nigdy nie jesteś zbyt przydzielania.

1515
01:12:55,560 --> 01:12:58,470
>> Teraz wystarczy, aby być naprawdę nit-wybredna,
istnieje ukrytych kosztów.

1516
01:12:58,470 --> 01:13:01,980
Więc nie należy po prostu pozwolił mi przekonać
Ci, że jest to przekonujące kompromis.

1517
01:13:01,980 --> 01:13:04,190
Jest jeszcze jeden ukryty koszt tutaj.

1518
01:13:04,190 --> 01:13:06,550
Korzyść, być jasne,
jest to, że możemy uzyskać dynamikę.

1519
01:13:06,550 --> 01:13:10,359
Jeśli chcę kolejny element, mogę po prostu
wyciągnąć go i umieścić numer tam.

1520
01:13:10,359 --> 01:13:12,150
A potem mogę go połączyć
z obrazem tutaj

1521
01:13:12,150 --> 01:13:14,970
natomiast tutaj znowu, jeśli mam
malowane sobie w kącie,

1522
01:13:14,970 --> 01:13:19,410
czy coś innego nie jest już używane
pamięć tu jestem pecha.

1523
01:13:19,410 --> 01:13:21,700
Mam pomalowane się w rogu.

1524
01:13:21,700 --> 01:13:24,390
>> Ale to, co jest ukryte
kosztuje na tym obrazku?

1525
01:13:24,390 --> 01:13:27,690
To nie tylko ilość
czas, który potrzebny

1526
01:13:27,690 --> 01:13:29,870
aby przejść stąd tu,
czyli siedem kroków, a następnie

1527
01:13:29,870 --> 01:13:32,820
osiem kroków, których jest więcej niż jeden.

1528
01:13:32,820 --> 01:13:34,830
Co znajduje się w innym ukryte koszty?

1529
01:13:34,830 --> 01:13:35,440
Nie tylko czas.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Dodatkowe informacje o firmie
konieczne do osiągnięcia tego obrazu.

1532
01:13:49,940 --> 01:13:53,210
>> Tak, to mapa, te małe skrawki
papier, jak utrzymać opisując je jako.

1533
01:13:53,210 --> 01:13:55,650
Są arrows-- te nie są wolne.

1534
01:13:55,650 --> 01:13:57,660
Computer-- wiesz
co komputer ma.

1535
01:13:57,660 --> 01:13:58,790
Ma zer i jedynek.

1536
01:13:58,790 --> 01:14:03,170
Jeśli chcesz do reprezentowania strzałkę lub grupę
map lub numer, trzeba trochę pamięci.

1537
01:14:03,170 --> 01:14:05,950
Więc drugiej cenie
zapłacić za połączonej listy,

1538
01:14:05,950 --> 01:14:09,070
wspólny informatyka
zasobów, jest także przestrzenią.

1539
01:14:09,070 --> 01:14:11,710
>> I rzeczywiście, tak, tak często,
wśród kompromisów

1540
01:14:11,710 --> 01:14:15,580
w projektowaniu inżynierii oprogramowania
System jest czas i space--

1541
01:14:15,580 --> 01:14:18,596
Są dwie swoich składników, dwa
swoich najbardziej kosztownych składników.

1542
01:14:18,596 --> 01:14:21,220
To kosztuje mnie więcej czasu
bo mam do tej mapy,

1543
01:14:21,220 --> 01:14:25,730
ale to też kosztuje mnie więcej miejsca
bo muszę utrzymać tę mapę wokół.

1544
01:14:25,730 --> 01:14:28,730
Więc jest nadzieja, ponieważ mamy rodzaj
omówione powyżej wczoraj i dziś,

1545
01:14:28,730 --> 01:14:31,720
jest to, że korzyści
będą przeważać nad kosztami.

1546
01:14:31,720 --> 01:14:33,870
>> Ale nie ma tu oczywiste rozwiązanie.

1547
01:14:33,870 --> 01:14:35,870
Może to better--
a la szybkie i brudne,

1548
01:14:35,870 --> 01:14:38,660
jak Kareem zaproponował earlier--
rzucać pamięć na problem.

1549
01:14:38,660 --> 01:14:42,520
Wystarczy kupić więcej pamięci, mniej myśleć
Trudno o rozwiązaniu problemu,

1550
01:14:42,520 --> 01:14:44,595
i rozwiązać go w prostszy sposób.

1551
01:14:44,595 --> 01:14:46,720
I rzeczywiście wcześniej, kiedy
rozmawialiśmy o kompromisach,

1552
01:14:46,720 --> 01:14:49,190
nie było przestrzeń
komputer i czas.

1553
01:14:49,190 --> 01:14:51,810
To był czas, deweloper, który
Jeszcze innym źródłem.

1554
01:14:51,810 --> 01:14:54,829
>> Więc jeszcze raz, to jest to balansowanie
próbując zdecydować, które z tych rzeczy

1555
01:14:54,829 --> 01:14:55,870
jesteś skłonny wydać?

1556
01:14:55,870 --> 01:14:57,380
Jaki jest najtańszy?

1557
01:14:57,380 --> 01:15:01,040
Co daje lepsze rezultaty?

1558
01:15:01,040 --> 01:15:01,540
Tak?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> W rzeczy samej.

1561
01:15:12,580 --> 01:15:15,970
W tym przypadku, jeśli jesteś
reprezentujące liczby w maps--

1562
01:15:15,970 --> 01:15:18,820
nazywane są one w wielu językach
"Wskaźniki" lub "adresy" -

1563
01:15:18,820 --> 01:15:20,390
jest to dwa razy więcej miejsca.

1564
01:15:20,390 --> 01:15:24,390
To nie musi być tak źle, jak w przypadku podwójnego
teraz jesteśmy po prostu przechowywania numerów.

1565
01:15:24,390 --> 01:15:27,410
Załóżmy, że byliśmy przechowywania
rekordów pacjenta w hospital--

1566
01:15:27,410 --> 01:15:30,870
więc nazwy Pierson jest, numery telefonów,
numery ubezpieczenia społecznego, lekarz

1567
01:15:30,870 --> 01:15:31,540
historia.

1568
01:15:31,540 --> 01:15:34,160
To pole może być wiele,
znacznie większy, w którym to przypadku

1569
01:15:34,160 --> 01:15:38,000
malutkie wskaźnik, adres
następny element-- to nie jest wielka sprawa.

1570
01:15:38,000 --> 01:15:40,620
To taka grzywka
kosztuje to nie ma znaczenia.

1571
01:15:40,620 --> 01:15:43,210
Ale w tym przypadku, tak, to podwojenie.

1572
01:15:43,210 --> 01:15:45,290
Dobre pytanie.

1573
01:15:45,290 --> 01:15:47,900
>> Porozmawiajmy o czasie
trochę bardziej konkretnie.

1574
01:15:47,900 --> 01:15:50,380
Jaki jest czas pracy
poszukiwania tej listy?

1575
01:15:50,380 --> 01:15:53,640
Załóżmy, że chcę, aby szukać
przez wszystkie stopnie uczniów,

1576
01:15:53,640 --> 01:15:55,980
a tam stopni n
W tej strukturze danych.

1577
01:15:55,980 --> 01:15:58,830
Tutaj też możemy pożyczać
słownictwo wcześniej.

1578
01:15:58,830 --> 01:16:00,890
Ta liniowa struktura danych.

1579
01:16:00,890 --> 01:16:04,570
>> Big O n to, co jest wymagane, aby uzyskać
na końcu tej struktury danych

1580
01:16:04,570 --> 01:16:08,410
whereas-- i nie widzieliśmy
Ten before-- tablica daje

1581
01:16:08,410 --> 01:16:13,555
co nazywa stałą czasową, co oznacza,
krok lub dwa stopnie lub 10 steps--

1582
01:16:13,555 --> 01:16:14,180
nie ma znaczenia.

1583
01:16:14,180 --> 01:16:15,440
Jest to stała liczba.

1584
01:16:15,440 --> 01:16:17,440
To nie ma nic wspólnego z
rozmiar tablicy.

1585
01:16:17,440 --> 01:16:20,130
A powodem tego,
ponownie jest losowego dostępu.

1586
01:16:20,130 --> 01:16:23,180
Komputer może po prostu od razu
przeskoczyć do innej lokalizacji,

1587
01:16:23,180 --> 01:16:27,770
ponieważ są one wszystkie takie same
odległość od wszystkiego innego.

1588
01:16:27,770 --> 01:16:29,112
Nie ma zaangażowany myślenie.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
W porządku.

1591
01:16:32,400 --> 01:16:39,230
Więc jeśli mogę, daj mi spróbować
malować dwa ostatnie zdjęcia.

1592
01:16:39,230 --> 01:16:42,830
Bardzo często jeden znany jako tabeli mieszania.

1593
01:16:42,830 --> 01:16:51,120
Więc motywować tę dyskusję,
pozwól mi myśleć o tym, jak to zrobić.

1594
01:16:51,120 --> 01:16:52,610
>> Tak jak o tym?

1595
01:16:52,610 --> 01:16:55,160
Załóżmy, że problem
chcemy rozwiązać teraz

1596
01:16:55,160 --> 01:16:58,360
wdraża w dictionary--
więc cała masa angielskich słów

1597
01:16:58,360 --> 01:16:59,330
lub cokolwiek.

1598
01:16:59,330 --> 01:17:02,724
A celem jest, aby móc odpowiedzieć
Kwestie postaci jest to słowo?

1599
01:17:02,724 --> 01:17:04,640
Więc chcesz wdrożyć
sprawdzania pisowni, tuż

1600
01:17:04,640 --> 01:17:07,220
jak fizyczny słowniku
że można spojrzeć na rzeczy.

1601
01:17:07,220 --> 01:17:10,490
Załóżmy, że było to zrobić z tablicy.

1602
01:17:10,490 --> 01:17:12,590
Mógłbym to zrobić.

1603
01:17:12,590 --> 01:17:20,756
>> I załóżmy, że słowa są jabłka
banan i kantalupa.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
I nie mogę myśleć o owocach
które zaczynają się d, więc jesteśmy po prostu

1606
01:17:26,465 --> 01:17:27,590
będziemy mieć trzy owoce.

1607
01:17:27,590 --> 01:17:31,510
Więc to jest tablicą, a my jesteśmy
przechowywania wszystkich tych słów

1608
01:17:31,510 --> 01:17:34,200
w tym słowniku jako tablicę.

1609
01:17:34,200 --> 01:17:39,350
Pytanie jest więc, jak inaczej
można przechowywać te informacje?

1610
01:17:39,350 --> 01:17:43,160
>> Cóż, jestem tutaj rodzaj oszukiwania, ponieważ
każda z tych liter w słowie

1611
01:17:43,160 --> 01:17:44,490
jest naprawdę indywidualna bajtów.

1612
01:17:44,490 --> 01:17:46,740
Więc jeśli naprawdę chciałem być
nit-wybredna, powinienem naprawdę

1613
01:17:46,740 --> 01:17:49,600
być podzielenie się do tego znacznie
mniejsze kawałki pamięci,

1614
01:17:49,600 --> 01:17:51,289
i mogliśmy zrobić dokładnie to.

1615
01:17:51,289 --> 01:17:53,580
Ale mamy zamiar uruchomić w
ten sam problem, jak wcześniej.

1616
01:17:53,580 --> 01:17:56,674
Co jeśli, jak Merriam Webster i Oxford
Czy każdy rok-- dodają słowa

1617
01:17:56,674 --> 01:17:59,340
do dictionary-- nie robimy
niekoniecznie chcą się malować

1618
01:17:59,340 --> 01:18:00,780
na rogu z tablicy?

1619
01:18:00,780 --> 01:18:05,710
>> Zamiast więc, może mądrzejsi podejście
jest umieszczenie jabłek we własnym węzłem lub pudełku,

1620
01:18:05,710 --> 01:18:11,190
jak powiedzielibyśmy, banan i
to tutaj mamy kantalupa.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
A my ciąg te rzeczy razem.

1623
01:18:16,790 --> 01:18:19,980
Więc to jest tablica, a
jest to związane lista.

1624
01:18:19,980 --> 01:18:23,300
Jeśli nie można dość zobaczyć, to po prostu
mówi "tablica", a to mówi "listy".

1625
01:18:23,300 --> 01:18:25,780
>> Mamy więc takie same
Dokładne kwestie jak poprzednio,

1626
01:18:25,780 --> 01:18:28,600
przy czym mamy teraz
Dynamizm w naszej połączonej listy.

1627
01:18:28,600 --> 01:18:31,090
Ale mamy dość powolny słownika.

1628
01:18:31,090 --> 01:18:32,870
Załóżmy, że chcę sprawdzić słowo.

1629
01:18:32,870 --> 01:18:35,430
Może to zająć mi Big O n
kroków, ponieważ słowo może

1630
01:18:35,430 --> 01:18:37,840
się, aż na koniec
lista, podobnie jak kantalupa.

1631
01:18:37,840 --> 01:18:40,600
I okazuje się, że
w programowaniu, sortowanie

1632
01:18:40,600 --> 01:18:42,700
świętego Graala danych
struktury, jest czymś

1633
01:18:42,700 --> 01:18:46,620
który daje stałe
Czas jakby tablicy

1634
01:18:46,620 --> 01:18:50,870
ale wciąż daje dynamikę.

1635
01:18:50,870 --> 01:18:52,940
>> Tak więc możemy mieć najlepsze z obu światów?

1636
01:18:52,940 --> 01:18:55,570
I rzeczywiście, jest coś
nazywany tabeli mieszania

1637
01:18:55,570 --> 01:18:59,320
który pozwala dokładnie zrobić
, Które choć w przybliżeniu.

1638
01:18:59,320 --> 01:19:03,140
Tabela mieszania jest hodowcy
Struktura danych, które

1639
01:19:03,140 --> 01:19:06,340
Można pomyśleć, jak
kombinacja array--

1640
01:19:06,340 --> 01:19:12,390
a ja zamierzam go wyciągnąć
jak this-- i połączonych listach

1641
01:19:12,390 --> 01:19:17,310
że będę rysować jak ten tutaj.

1642
01:19:17,310 --> 01:19:19,760
>> A droga ta sprawa
działa, jest następujący.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Jeśli now-- ten hash table--
Jest to moja trzecia struktura danych,

1645
01:19:29,540 --> 01:19:32,590
i chcę się zapisać
słowa tego, nie wiem

1646
01:19:32,590 --> 01:19:35,440
chcę po prostu zapisać wszystkie z
słowa z powrotem do tyłu z powrotem do tyłu.

1647
01:19:35,440 --> 01:19:37,430
Chcę wykorzystać niektóre
kawałek informacji

1648
01:19:37,430 --> 01:19:40,330
o słowach, które pozwolą
mi ją tam, gdzie jest to szybciej.

1649
01:19:40,330 --> 01:19:43,666
>> Tak więc biorąc pod uwagę słowa jabłko
banan i kantalupa,

1650
01:19:43,666 --> 01:19:45,040
Celowo wybraliśmy te słowa.

1651
01:19:45,040 --> 01:19:45,340
Czemu?

1652
01:19:45,340 --> 01:19:47,631
Jaki jest rodzaj gruntu
różni się o trzy?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Co jest oczywiste?

1655
01:19:51,484 --> 01:19:52,900
Zaczynają z różnymi literami.

1656
01:19:52,900 --> 01:19:53,900
>> Więc wiesz co?

1657
01:19:53,900 --> 01:19:57,120
Zamiast umieścić wszystkie moje słowa
to samo wiaderko, że tak powiem,

1658
01:19:57,120 --> 01:20:00,390
jak w jednej wielkiej listy, to dlaczego nie zrobić
Ja przynajmniej spróbować optymalizacji

1659
01:20:00,390 --> 01:20:04,180
i uczynić moje listy 26/01 tak długo.

1660
01:20:04,180 --> 01:20:07,440
Ciekawa optymalizacja
może być, dlaczego nie

1661
01:20:07,440 --> 01:20:10,650
Ja-- podczas wstawiania słowa
do tej struktury danych

1662
01:20:10,650 --> 01:20:14,300
do pamięci komputera, dlatego
Nie mogę umieścić tutaj wszystkie "a" słowa,

1663
01:20:14,300 --> 01:20:17,270
Wszystkie słowa 'B' Tutaj,
i wszystkie słowa, 'C' Tutaj?

1664
01:20:17,270 --> 01:20:24,610
Tak to kończy się wprowadzenie jabłko
tutaj, banan tu kantalupa tutaj

1665
01:20:24,610 --> 01:20:25,730
i tak dalej.

1666
01:20:25,730 --> 01:20:31,700
>> A jeśli mam dodatkowe
Słowo like-- co innego?

1667
01:20:31,700 --> 01:20:36,640
Jabłko, banan, gruszka.

1668
01:20:36,640 --> 01:20:39,370
Każdy myśli o smaku owocowym
zaczynający się a, b lub c?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- doskonały.

1670
01:20:40,570 --> 01:20:43,990
To skończy się tutaj.

1671
01:20:43,990 --> 01:20:47,530
A więc wydaje się, że
minimalnie lepszym rozwiązaniem,

1672
01:20:47,530 --> 01:20:50,820
bo teraz jeśli chcę
aby szukać jabłko, ja

1673
01:20:50,820 --> 01:20:53,200
first-- I nie tylko nurkowanie
w moim struktury danych.

1674
01:20:53,200 --> 01:20:54,850
Nie nurkować w pamięci mojego komputera.

1675
01:20:54,850 --> 01:20:56,530
Po raz pierwszy spojrzeć na pierwszej literze.

1676
01:20:56,530 --> 01:20:58,610
>> I to właśnie z komputera
Naukowiec powie.

1677
01:20:58,610 --> 01:21:00,760
Ty hash do swojej struktury danych.

1678
01:21:00,760 --> 01:21:04,100
Wziąć swój wkład, który w
sprawa ta jest słowem jak jabłko.

1679
01:21:04,100 --> 01:21:07,150
Analizując je, patrząc na
pierwsza litera w tym przypadku,

1680
01:21:07,150 --> 01:21:08,340
sposób mieszania go.

1681
01:21:08,340 --> 01:21:10,950
Hashing to ogólne określenie, zgodnie z którą
wziąć coś jako wejście

1682
01:21:10,950 --> 01:21:12,116
i produkować jakieś wyjście.

1683
01:21:12,116 --> 01:21:15,090
A wyjście na tym, że
Sprawa jest lokalizacja

1684
01:21:15,090 --> 01:21:18,150
chcesz szukać, pierwszy
Położenie drugie położenie, trzecią.

1685
01:21:18,150 --> 01:21:22,160
Więc wejście jest jabłko,
wyjście jest w pierwszej kolejności.

1686
01:21:22,160 --> 01:21:25,054
Wejście jest banan, The
Wyjście powinno być sekundy.

1687
01:21:25,054 --> 01:21:27,220
Wejście jest kantalupa,
wyjście powinno być trzecią.

1688
01:21:27,220 --> 01:21:30,320
Wejście jest borówka, The
Wyjście powinno być ponownie sekund.

1689
01:21:30,320 --> 01:21:34,010
I to właśnie pozwala przejąć
Skróty dzięki swojej pamięci

1690
01:21:34,010 --> 01:21:39,050
w celu uzyskania słów
lub dane bardziej efektywnie.

1691
01:21:39,050 --> 01:21:43,330
>> Teraz ten skraca nasz czas potencjalnie
nawet jako jeden z 26,

1692
01:21:43,330 --> 01:21:45,850
bo jeśli zakładamy, że
mieć tyle "a" słowa jak "z"

1693
01:21:45,850 --> 01:21:48,080
słowa jak "Q" słów, które
nie jest tak naprawdę realistic--

1694
01:21:48,080 --> 01:21:50,830
masz zamiar mieć pochylenie całej
niektóre litery alphabet--

1695
01:21:50,830 --> 01:21:53,204
ale byłoby to przyrostowe
Podejście to nie pozwala

1696
01:21:53,204 --> 01:21:55,930
można dostać się do słów znacznie szybciej.

1697
01:21:55,930 --> 01:21:59,660
A w rzeczywistości, wyrafinowany
programu, Googles świata,

1698
01:21:59,660 --> 01:22:02,180
Facebooks z world--
oni użyć tabeli mieszania

1699
01:22:02,180 --> 01:22:03,740
dla wielu różnych celów.

1700
01:22:03,740 --> 01:22:06,590
Ale nie byłby tak naiwny,
po prostu spojrzeć na pierwszą literę

1701
01:22:06,590 --> 01:22:09,700
w jabłko lub banana lub
gruszkowe lub kantalupa,

1702
01:22:09,700 --> 01:22:13,420
bo jak widać nich
Listy można jeszcze dostać długo.

1703
01:22:13,420 --> 01:22:17,130
>> I tak może to być jeszcze porządek
z linear-- tak jakby powolny,

1704
01:22:17,130 --> 01:22:19,980
jak z Big O n
które omówiono wcześniej.

1705
01:22:19,980 --> 01:22:25,290
Więc co naprawdę dobry tabeli mieszania będzie
do-- będzie miał znacznie większy wachlarz.

1706
01:22:25,290 --> 01:22:28,574
I będzie używać znacznie bardziej
wyrafinowana funkcja skrótu,

1707
01:22:28,574 --> 01:22:30,240
tak, że nie tylko wygląda na "a".

1708
01:22:30,240 --> 01:22:35,480
Może to wygląda na "a-p-p-l-e", a
jakoś konwertuje te pięć liter

1709
01:22:35,480 --> 01:22:38,400
w miejscu, w którym
Apple powinno być przechowywane.

1710
01:22:38,400 --> 01:22:42,660
Jesteśmy po prostu naiwnie pomocą litery "A"
sam, bo to ładne i proste.

1711
01:22:42,660 --> 01:22:44,600
>> Ale tabeli mieszania w
koniec, można myśleć

1712
01:22:44,600 --> 01:22:47,270
jako kombinację
tablicą, z których każda

1713
01:22:47,270 --> 01:22:51,700
ma połączonej listy, które najlepiej
powinien być jak najkrótszy.

1714
01:22:51,700 --> 01:22:54,364
I nie jest to oczywiste rozwiązanie.

1715
01:22:54,364 --> 01:22:57,280
W rzeczywistości, wiele dostrojeniu
co dzieje się pod maską, gdy

1716
01:22:57,280 --> 01:22:59,654
Realizując te rodzaje
wyrafinowane struktury danych

1717
01:22:59,654 --> 01:23:01,640
jest to, co jest właściwe
długość tablicy?

1718
01:23:01,640 --> 01:23:03,250
Jaka jest funkcja hash prawda?

1719
01:23:03,250 --> 01:23:04,830
Jak przechowywać rzeczy w pamięci?

1720
01:23:04,830 --> 01:23:07,249
>> Ale sobie sprawę, jak szybko
tego rodzaju dyskusji

1721
01:23:07,249 --> 01:23:10,540
eskalacja, czy tak daleko, że jest to rodzaj
z nad głową w tym miejscu, które

1722
01:23:10,540 --> 01:23:11,360
jest w porządku.

1723
01:23:11,360 --> 01:23:18,820
Ale zaczęliśmy, wycofanie z prawdziwie
coś na niskim poziomie i elektronicznego.

1724
01:23:18,820 --> 01:23:20,819
I tak to znowu jest to
Tematem abstrakcji,

1725
01:23:20,819 --> 01:23:23,610
gdzie po uruchomieniu do podjęcia przez
przyznane, OK, mam it-- tam

1726
01:23:23,610 --> 01:23:26,680
Pamięć fizyczna, OK, rozumiem, każdy
Fizyczna lokalizacja ma adres,

1727
01:23:26,680 --> 01:23:29,910
OK, rozumiem, mogę reprezentować
te adresy jak arrows--

1728
01:23:29,910 --> 01:23:34,650
można bardzo szybko zaczynają mieć
Bardziej zaawansowane rozmowy, które

1729
01:23:34,650 --> 01:23:38,360
w końcu wydaje się, że pozwala nam
do rozwiązywania problemów, takich jak wyszukiwanie

1730
01:23:38,360 --> 01:23:41,620
i sortowania bardziej efektywnie.

1731
01:23:41,620 --> 01:23:44,190
I mieć pewność, too--
bo myślę, że to

1732
01:23:44,190 --> 01:23:48,700
jest najgłębszym zaszliśmy do niektórych
z tych tematów CS proper-- my ve

1733
01:23:48,700 --> 01:23:51,880
sporządzono w dniu i połowę w tym
wskazać, co można zrobić, zwykle w ciągu

1734
01:23:51,880 --> 01:23:55,520
przebieg ośmiu tygodni w semestrze.

1735
01:23:55,520 --> 01:23:59,670
>> Wszelkie pytania na temat tych?

1736
01:23:59,670 --> 01:24:01,100
Nie?

1737
01:24:01,100 --> 01:24:01,940
W porządku.

1738
01:24:01,940 --> 01:24:05,610
Cóż, dlaczego nie możemy wstrzymać tam,
zacząć obiad kilka minut wcześniej,

1739
01:24:05,610 --> 01:24:07,052
wznowić w ciągu około godziny?

1740
01:24:07,052 --> 01:24:08,760
I będę utrzymywał
nieco z pytaniami.

1741
01:24:08,760 --> 01:24:11,343
Potem będę musiał przejść
potrwać kilka połączeń, jeśli to jest OK.

1742
01:24:11,343 --> 01:24:15,000
Będę włączyć jakąś muzykę w międzyczasie
ale obiad powinien być tuż za rogiem.

1743
01:24:15,000 --> 01:24:17,862