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

2
00:00:00,030 --> 00:00:00,460
>> DAVID Малан: Добре.

3
00:00:00,460 --> 00:00:01,094
Върнахме се.

4
00:00:01,094 --> 00:00:04,260
Така че в този сегмент на програмен какво
Мислех да направя е смесица от неща.

5
00:00:04,260 --> 00:00:06,340
Един, направи малко
на нещо практически,

6
00:00:06,340 --> 00:00:08,690
макар и с помощта на по-закачлив
програмиране environment--

7
00:00:08,690 --> 00:00:11,620
едно, че е демонстративен на
точно вида на идеи

8
00:00:11,620 --> 00:00:14,220
ние сме били говорим за,
но малко по-официално.

9
00:00:14,220 --> 00:00:18,200
Две, да разгледаме някои от
по-техническите начини

10
00:00:18,200 --> 00:00:21,520
че един програмист действително би могла да разреши
проблеми като търсите проблема

11
00:00:21,520 --> 00:00:24,530
че ние погледна преди и
Също така по-фундаментално

12
00:00:24,530 --> 00:00:26,020
интересен проблем на сортиране.

13
00:00:26,020 --> 00:00:28,840
>> Ние просто приема от самото движение
че този телефонен указател се сортират,

14
00:00:28,840 --> 00:00:31,980
но че сам е всъщност един вид
Трудно проблем с много различни начини

15
00:00:31,980 --> 00:00:32,479
да го решим.

16
00:00:32,479 --> 00:00:34,366
Така че ние ще използваме тези като
клас проблеми

17
00:00:34,366 --> 00:00:36,740
представител на неща, които
може да бъде решен като цяло.

18
00:00:36,740 --> 00:00:38,980
И тогава ние ще говорим
за по-подробно какво

19
00:00:38,980 --> 00:00:42,360
се наричат ​​данни structures--
красиви начини, като свързани списъци

20
00:00:42,360 --> 00:00:46,290
и хеш таблици и дървета, които
програмист би действително

21
00:00:46,290 --> 00:00:48,890
използвате и като цяло се използва
върху бяла дъска, за да нарисува

22
00:00:48,890 --> 00:00:51,840
снимка на това, което той или тя
се основава на принципа за прилагане на

23
00:00:51,840 --> 00:00:52,980
някои част от софтуера.

24
00:00:52,980 --> 00:00:55,130
>> Така че нека да се направи на ръце на част първа.

25
00:00:55,130 --> 00:01:00,090
Така че просто си цапаме ръцете с
околната среда, наречени scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Това е инструмент, който ние използваме
в нашия студент клас.

27
00:01:02,636 --> 00:01:04,510
Въпреки, че той е проектиран
за възрасти 12 и нагоре,

28
00:01:04,510 --> 00:01:07,570
ние го използваме за състава
част от които доста малко

29
00:01:07,570 --> 00:01:10,020
тъй като това е приятно, забавно
графичен начин на живот

30
00:01:10,020 --> 00:01:12,160
малко нещо за програмиране.

31
00:01:12,160 --> 00:01:17,600
Така се отправят към този адрес, където можете
трябва да видите страница съвсем като този,

32
00:01:17,600 --> 00:01:23,330
и давай напред и кликнете
Присъединете се към нулата в горния десен ъгъл

33
00:01:23,330 --> 00:01:28,300
и изберете потребителско име и
парола и в крайна сметка се получи себе си

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
Мислех, че ще използва това като
възможност първо да покаже това.

37
00:01:34,665 --> 00:01:39,120
Актуален въпрос изскочи по време на почивката
за това какво код действително прилича.

38
00:01:39,120 --> 00:01:41,315
И ние говорим
По време на почивката за C,

39
00:01:41,315 --> 00:01:45,060
в particular-- особено на
по-ниско ниво в по-стар език.

40
00:01:45,060 --> 00:01:47,750
И аз просто направих един бърз
Google търсене, за да намерите C код

41
00:01:47,750 --> 00:01:51,574
за двоично търсене, алгоритъмът, че ние
използва за търсене, които телефонен указател по-рано.

42
00:01:51,574 --> 00:01:54,240
Този конкретен пример, разбира се,
не търси телефонен указател.

43
00:01:54,240 --> 00:01:57,840
Той просто търси цял куп
номера в паметта на компютъра.

44
00:01:57,840 --> 00:02:01,000
Но ако искате просто да получите визуална
смисъл на това, което действително програмиране

45
00:02:01,000 --> 00:02:05,370
език изглежда, че изглежда
малко нещо като това.

46
00:02:05,370 --> 00:02:09,759
Така че това е около 20-плюс,
30-те реда код,

47
00:02:09,759 --> 00:02:12,640
но разговорът ни
бяха с над почивка

48
00:02:12,640 --> 00:02:16,000
е за това, как това всъщност
получава се превърна в нули и единици

49
00:02:16,000 --> 00:02:19,200
и ако не може просто да се върне, че
обработват и отидете от нули и единици

50
00:02:19,200 --> 00:02:20,210
резервно за код.

51
00:02:20,210 --> 00:02:22,620
>> За съжаление, процесът
е така трансформиращ

52
00:02:22,620 --> 00:02:24,890
че това е много лесно да се каже отколкото да се направи.

53
00:02:24,890 --> 00:02:29,400
Аз отидох напред и действително се обърна
тази програма, Binary Search,

54
00:02:29,400 --> 00:02:32,700
в нули и единици посредством
програма, наречена компилатор, че аз

55
00:02:32,700 --> 00:02:34,400
се случи да има тук точно на моя Mac.

56
00:02:34,400 --> 00:02:37,850
И ако погледнете на екрана
тук, като се фокусира конкретно

57
00:02:37,850 --> 00:02:43,520
на следните средни шест колони само,
ще видите само нули и единици.

58
00:02:43,520 --> 00:02:48,290
И тези, които са нули и тези, които
композирате точно, че търсенето на програма.

59
00:02:48,290 --> 00:02:53,720
>> И така всеки парче от пет бита,
всеки байт от нули и единици тук,

60
00:02:53,720 --> 00:02:57,310
представляват някаква инструкция
Обикновено вътрешността на компютъра.

61
00:02:57,310 --> 00:03:00,730
И в действителност, ако сте чували за
маркетинг лозунг "Intel вътре" - това,

62
00:03:00,730 --> 00:03:04,610
разбира се, просто означава, че имате
Intel CPU или мозъка вътрешността на компютъра.

63
00:03:04,610 --> 00:03:08,000
И това, което означава, че за да бъде един CPU е
че имате набор инструкции,

64
00:03:08,000 --> 00:03:08,840
така да се каже.

65
00:03:08,840 --> 00:03:11,620
>> Всеки процесор в света, много от
тях, направени от Intel тези дни,

66
00:03:11,620 --> 00:03:13,690
разбира ограничен
брой инструкции.

67
00:03:13,690 --> 00:03:18,690
И тези инструкции са толкова ниско ниво
като добавите тези две числа заедно,

68
00:03:18,690 --> 00:03:22,560
умножете тези две числа заедно,
премести тази част от данните от тук

69
00:03:22,560 --> 00:03:27,340
до тук в паметта, освен това
информация от тук до тук, в паметта,

70
00:03:27,340 --> 00:03:32,200
и така forth-- толкова много, много
ниско ниво, почти електронни подробности.

71
00:03:32,200 --> 00:03:34,780
Но с тези математически
операции в съчетание

72
00:03:34,780 --> 00:03:37,410
с това, което ние обсъдихме по-рано,
представяне на данни

73
00:03:37,410 --> 00:03:40,450
като нули и единици, могат
ви изгради всичко

74
00:03:40,450 --> 00:03:44,180
че един компютър може да се направи днес, дали
това е текстова, графична, музикални,

75
00:03:44,180 --> 00:03:45,580
или иначе.

76
00:03:45,580 --> 00:03:49,450
>> Така че това е много лесно да се получи
изгубени в бурените на бързо.

77
00:03:49,450 --> 00:03:52,150
И има много
синтактични предизвикателства

78
00:03:52,150 --> 00:03:56,630
при което, ако се направи най-простите,
тъпото на печатни грешки никой от програмата

79
00:03:56,630 --> 00:03:57,860
ще работи, каквато.

80
00:03:57,860 --> 00:04:00,366
И така, вместо да се използва
език като C тази сутрин,

81
00:04:00,366 --> 00:04:02,240
Мислех, че ще бъде
по-забавно да всъщност правят

82
00:04:02,240 --> 00:04:04,840
нещо повече визуално, които
докато предназначена за деца

83
00:04:04,840 --> 00:04:08,079
е всъщност перфектно проява
на действително програмиране

84
00:04:08,079 --> 00:04:10,370
language-- просто се случва да
използване на снимки, вместо текст

85
00:04:10,370 --> 00:04:11,710
да представляват тези идеи.

86
00:04:11,710 --> 00:04:15,470
>> Така че, след като наистина има
сметка на scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
Кликнете върху бутона Създаване
в горния ляв ъгъл на сайта.

88
00:04:21,070 --> 00:04:24,620
И вие трябва да видите една среда, като
този, аз съм за да се види на екрана си

89
00:04:24,620 --> 00:04:26,310
тук.

90
00:04:26,310 --> 00:04:29,350
И ние ще прекарат малко
малко време да играе тук.

91
00:04:29,350 --> 00:04:34,080
Нека да видим дали не можем да решим всички някои
проблеми заедно по следния начин.

92
00:04:34,080 --> 00:04:39,420
>> Така че това, което ще видите в този
environment-- и всъщност просто нека

93
00:04:39,420 --> 00:04:40,050
ме пауза.

94
00:04:40,050 --> 00:04:42,680
Което не е тук някой?

95
00:04:42,680 --> 00:04:45,070
Не тук?

96
00:04:45,070 --> 00:04:45,800
ДОБРЕ.

97
00:04:45,800 --> 00:04:49,030
Така че нека да се отбележи няколко
характеристики на тази среда.

98
00:04:49,030 --> 00:04:55,024
>> Така че в горния ляв ъгъл на екрана, ние
Трябва етап Scratch е, така да се каже.

99
00:04:55,024 --> 00:04:57,440
Scratch е не само името
на този език за програмиране;

100
00:04:57,440 --> 00:05:00,356
това е и името на котката, че
виждате по подразбиране има в оранжево.

101
00:05:00,356 --> 00:05:02,160
Той е на сцената, така че
много като описах

102
00:05:02,160 --> 00:05:05,770
костенурката по-рано, че е в една
правоъгълна бяла дъска среда.

103
00:05:05,770 --> 00:05:09,800
свят Тази котка се ограничава изцяло
да, че правоъгълник до върха там.

104
00:05:09,800 --> 00:05:12,210
>> Междувременно отдясно
ръката страна тук, това е

105
00:05:12,210 --> 00:05:15,610
само на площ скриптове, а
празен лист, ако щете.

106
00:05:15,610 --> 00:05:18,590
Това е мястото, където отиваме да се напише
нашите програми в един момент.

107
00:05:18,590 --> 00:05:22,935
И градивните елементи, които ние трябва да
използвате, за да напиша тази program-- пъзела

108
00:05:22,935 --> 00:05:25,310
парчета, ако will-- са
тези, точно тук, в центъра,

109
00:05:25,310 --> 00:05:27,500
и те са категоризирани
от функционалност.

110
00:05:27,500 --> 00:05:31,000
Така, например, аз ще отида напред
и да покаже най-малко един от тях.

111
00:05:31,000 --> 00:05:33,690
Отивам да се продължи напред и кликнете
категорията Контрол на върха.

112
00:05:33,690 --> 00:05:35,720
>> Така че това са категориите до върха.

113
00:05:35,720 --> 00:05:39,410
Отивам да кликнете категорията Control.

114
00:05:39,410 --> 00:05:44,020
По-скоро, аз отивам да кликнете на Събитията
категория, най-първата една до върха.

115
00:05:44,020 --> 00:05:47,790
И ако искате да следват заедно дори
като правим това, вие сте доста добре дошли да.

116
00:05:47,790 --> 00:05:52,180
Отивам да щракнете и плъзнете този
Първият, "когато зелен флаг кликнали."

117
00:05:52,180 --> 00:05:58,410
И тогава аз ще го пуснете просто
грубо в горната част на моите празни плочи.

118
00:05:58,410 --> 00:06:01,450
>> И това, което е хубаво за Scratch
е, че този пъзел парче, когато

119
00:06:01,450 --> 00:06:04,560
сключено с друга пъзел
парчета, ще направи буквално

120
00:06:04,560 --> 00:06:06,460
какви са тези пъзел парчета, казват, да се направи.

121
00:06:06,460 --> 00:06:09,710
Така, например, Scratch е прав
сега в средата на неговия свят.

122
00:06:09,710 --> 00:06:14,660
Отивам да вървим напред и да изберете
Сега, нека да кажем, категорията Motion,

123
00:06:14,660 --> 00:06:18,000
ако искате да направите
same-- Предложение категория.

124
00:06:18,000 --> 00:06:20,430
И сега забележи имам цяло
куп пъзел парчета тук

125
00:06:20,430 --> 00:06:23,370
че, отново, вид правя това, което казват.

126
00:06:23,370 --> 00:06:28,110
И аз ще отида напред и да влачите и
изпускайте ход блок право върху тук.

127
00:06:28,110 --> 00:06:31,860
>> И забележете, че веднага щом се получи
в близост до дъното на "зеленото знаме

128
00:06:31,860 --> 00:06:34,580
кликнали "бутон, известие
как се появява бяла линия,

129
00:06:34,580 --> 00:06:36,950
като че ли това е почти
магнитен, тя иска да отиде там.

130
00:06:36,950 --> 00:06:43,070
Само да отида, и той ще щракне
заедно и формите ще съвпадат.

131
00:06:43,070 --> 00:06:46,620
А сега можете може би почти
Предполагам, къде отиваме с това.

132
00:06:46,620 --> 00:06:51,570
>> Ако се вгледате в етапа на Scratch
тук и гледам до върха на това,

133
00:06:51,570 --> 00:06:55,142
ще видите червена светлина, а
знак стоп, и зелен флаг.

134
00:06:55,142 --> 00:06:57,100
И аз ще отида напред
и гледам моите screen--

135
00:06:57,100 --> 00:06:58,460
само за миг, ако можеше.

136
00:06:58,460 --> 00:07:01,960
Отивам да натиснете
зелен флаг точно сега,

137
00:07:01,960 --> 00:07:07,850
и той се премества, което изглежда е 10 стъпки
или 10 пиксела, 10 точки, на екрана.

138
00:07:07,850 --> 00:07:13,390
>> И така, не толкова вълнуващо,
но нека да предложи

139
00:07:13,390 --> 00:07:17,440
без дори да преподава това, просто
използвайки притежавате собствен intuition-- нека

140
00:07:17,440 --> 00:07:22,560
ми предложи, че можете да разбера как да
направи Scratch пеша полето от сцената.

141
00:07:22,560 --> 00:07:28,700
Били го направи път на дясната страна на
на екрана, по целия път от дясно.

142
00:07:28,700 --> 00:07:32,200
Нека ви дам един миг
или така да се боря с това.

143
00:07:32,200 --> 00:07:37,681
Вие може да искате да погледнете
в други категории блокове.

144
00:07:37,681 --> 00:07:38,180
Добре.

145
00:07:38,180 --> 00:07:41,290
Така че просто да обобщим, когато имаме
зеленото знаме кликнали тук

146
00:07:41,290 --> 00:07:44,850
и да се премести на 10 стъпки е
само инструкция, всеки път, когато

147
00:07:44,850 --> 00:07:46,720
кликнете зеленото знаме, което се случва?

148
00:07:46,720 --> 00:07:50,070
Е, това е движение моята програма.

149
00:07:50,070 --> 00:07:52,450
Така че мога да направя това
може би 10 пъти ръчно,

150
00:07:52,450 --> 00:07:55,130
но това се чувства малко
битов hackish, така да се каже,

151
00:07:55,130 --> 00:07:57,480
при което аз не съм наистина
разрешаване на проблема.

152
00:07:57,480 --> 00:08:00,530
Аз просто се опитвам отново и
отново и отново

153
00:08:00,530 --> 00:08:03,180
докато аз някак случайно
постигане на директивата

154
00:08:03,180 --> 00:08:05,560
че съм тръгнал да се постигне по-рано.

155
00:08:05,560 --> 00:08:08,200
>> Но ние знаем от нашата
Псевдокод по-рано, че има

156
00:08:08,200 --> 00:08:11,870
това понятие в програмирането на примка,
правите нещо отново и отново.

157
00:08:11,870 --> 00:08:14,888
И така, аз видях, че един куп вас
достига за какво пъзел парче?

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

159
00:08:17,870 --> 00:08:18,730
Повторете, докато.

160
00:08:18,730 --> 00:08:21,400
Така че можем да направим нещо
като се повтаря, докато.

161
00:08:21,400 --> 00:08:23,760
А ти какво се повтаря, докато по-точно?

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

163
00:08:27,720 --> 00:08:28,540
>> ДОБРЕ.

164
00:08:28,540 --> 00:08:31,974
И нека да продължа с този, който е
малко по-просто само за миг.

165
00:08:31,974 --> 00:08:33,140
Нека да вървим напред и да направим това.

166
00:08:33,140 --> 00:08:35,559
Забележете, че, тъй като може да се наложи
открих под контрол,

167
00:08:35,559 --> 00:08:38,409
има това повторете блок, който
не изглежда като това е толкова голям.

168
00:08:38,409 --> 00:08:41,039
Няма много място в
между тези два жълти линии.

169
00:08:41,039 --> 00:08:43,539
Но тъй като някои от вас може да има
Забелязах, ако плъзнете и капка,

170
00:08:43,539 --> 00:08:45,150
забележите как тя расте, за да запълни формата.

171
00:08:45,150 --> 00:08:46,274
>> И дори може да се тъпча повече.

172
00:08:46,274 --> 00:08:48,670
Тя просто ще продължи да се увеличава, ако
влачите и мишката върху него.

173
00:08:48,670 --> 00:08:51,110
И аз не знам какво е
Най-добрият тук, така че нека

174
00:08:51,110 --> 00:08:54,760
мен най-малко се повтаря пет пъти, за
Например, и след това се върна на сцената

175
00:08:54,760 --> 00:08:56,720
и натиснете зеленото знаме.

176
00:08:56,720 --> 00:08:59,110
И сега забележи това не е съвсем там.

177
00:08:59,110 --> 00:09:02,400
>> Сега някои от вас, предложен, като
Виктория просто се повтаря 10 пъти.

178
00:09:02,400 --> 00:09:05,140
И това обикновено прави
го получите по целия път,

179
00:09:05,140 --> 00:09:10,510
но не би там да е по-стабилна
начин от произволно фигуриращ

180
00:09:10,510 --> 00:09:12,640
колко се движи, за да се направи?

181
00:09:12,640 --> 00:09:17,680
Какво може да бъде по-добър блок
от повторение 10 пъти да са?

182
00:09:17,680 --> 00:09:20,380
>> Да, така че защо да не направим нещо вечно?

183
00:09:20,380 --> 00:09:24,390
А сега нека да се премести този пъзел парче
вътре има и да се отървете от този.

184
00:09:24,390 --> 00:09:28,300
Сега забележите, без значение къде Scratch
започва, той отива до ръба.

185
00:09:28,300 --> 00:09:30,700
И за щастие MIT,
който прави Scratch, просто

186
00:09:30,700 --> 00:09:33,190
прави се, че той никога не
изчезва напълно.

187
00:09:33,190 --> 00:09:35,360
Винаги можете да вземете опашката си.

188
00:09:35,360 --> 00:09:37,680
>> И просто интуитивно,
защо той продължи да се движи?

189
00:09:37,680 --> 00:09:38,892
Какво става тук?

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

191
00:09:41,440 --> 00:09:43,824
Той, изглежда, е спряно, но
След това, ако мога да взема и плъзгане

192
00:09:43,824 --> 00:09:45,240
той продължава да иска да отида там.

193
00:09:45,240 --> 00:09:46,123
Защо така?

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

195
00:09:51,610 --> 00:09:54,360
Наистина, един компютър е буквално
Ще направя това, което го кажа, за да се направи.

196
00:09:54,360 --> 00:09:58,380
Така че, ако ви го каза по-рано направете
следната нещо вечно, се движат от 10 стъпки,

197
00:09:58,380 --> 00:10:01,860
тя ще продължи да функционира и ще
докато не се удари в червен знак стоп

198
00:10:01,860 --> 00:10:04,620
и спре програмата.

199
00:10:04,620 --> 00:10:06,610
>> Така че дори и да не го направи
направите това, как бих могъл да

200
00:10:06,610 --> 00:10:09,510
направи Scratch движат по-бързо
по екрана?

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

202
00:10:12,060 --> 00:10:13,280
Още стъпки, нали?

203
00:10:13,280 --> 00:10:15,710
Така че, вместо да правите 10
в момент, защо не

204
00:10:15,710 --> 00:10:20,100
отидете напред и да го промените to--
какво бихте propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Така че сега аз отивам да кликнете на зелено
флаг, и наистина, той отива много по-бързо.

206
00:10:24,410 --> 00:10:27,180
>> И това, разбира се, е само
проява на анимация.

207
00:10:27,180 --> 00:10:28,060
Какво е анимация?

208
00:10:28,060 --> 00:10:33,090
Това е просто ви показва човешки
куп неподвижни изображения наистина,

209
00:10:33,090 --> 00:10:34,160
Наистина, много по-бързо.

210
00:10:34,160 --> 00:10:36,500
И така, ако ние просто казвам
него да се движат повече стъпки,

211
00:10:36,500 --> 00:10:39,750
ние просто като ефектът е да
промяна, когато той е на екрана

212
00:10:39,750 --> 00:10:42,900
още по-бързо за единица време.

213
00:10:42,900 --> 00:10:46,454
>> Сега следващото предизвикателство, което аз предложих
е да има го скача от ръба.

214
00:10:46,454 --> 00:10:49,120
И без да знаят какво пъзел
парчета exist--, защото това е добре

215
00:10:49,120 --> 00:10:53,030
ако не се стигне до
етап на challenge-- какво

216
00:10:53,030 --> 00:10:54,280
искаш да направиш интуитивно?

217
00:10:54,280 --> 00:10:58,030
Как ще имаме му скача назад и
напред, между ляво и дясно?

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

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

220
00:11:03,810 --> 00:11:05,680
Така че ние се нуждаем от някакъв вид
на състояние, и

221
00:11:05,680 --> 00:11:09,710
изглежда да има условни, така че да
говоря, в категорията Control.

222
00:11:09,710 --> 00:11:14,110
Коя от тези блокове
имаме вероятно искате?

223
00:11:14,110 --> 00:11:15,200
Да, може би ", ако, след това."

224
00:11:15,200 --> 00:11:18,780
Така че забележите, че сред жълтите блокове
имаме тук, там е това "ако"

225
00:11:18,780 --> 00:11:23,920
или това "ако, иначе" блок, който ще
ни позволи да се вземе решение да се направи това

226
00:11:23,920 --> 00:11:25,000
или да направи това.

227
00:11:25,000 --> 00:11:27,380
дори и можете да ги гнездо
да направим няколко неща.

228
00:11:27,380 --> 00:11:34,910
Или, ако все още не сте преминали тук,
давай напред към категорията на засичане

229
00:11:34,910 --> 00:11:39,612
and-- нека да видим дали това е тук.

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

231
00:11:43,050 --> 00:11:52,050
>> И така, какво блок може да бъде полезно тук
да се открие, ако той е от сцената?

232
00:11:52,050 --> 00:11:56,740
Да, забележите, че някои от тези блокове
може да се parametrized, така да се каже.

233
00:11:56,740 --> 00:12:00,706
Те могат да бъдат подредени на персонализирани, не
за разлика от HTML вчера с атрибути,

234
00:12:00,706 --> 00:12:03,330
когато тези атрибути вид
персонализирате поведението на маркер.

235
00:12:03,330 --> 00:12:08,880
По същия начин тук, мога да вземете тази трогателна
блок и промяна и да зададем въпроса,

236
00:12:08,880 --> 00:12:11,500
са ви докосва мишката
показалка като курсора

237
00:12:11,500 --> 00:12:13,250
или са ви докосва ръба?

238
00:12:13,250 --> 00:12:15,210
>> Така че нека да ида и да направите това.

239
00:12:15,210 --> 00:12:18,130
Отивам да се отдалечите за миг.

240
00:12:18,130 --> 00:12:21,320
Нека да вземете този пъзел парче
тук, на този пъзел парче това,

241
00:12:21,320 --> 00:12:24,570
и аз ще неуредица
ги нагоре само за миг.

242
00:12:24,570 --> 00:12:27,620
Отивам да се движи този,
промените това да докосва ръба,

243
00:12:27,620 --> 00:12:38,590
и аз ще движение направите това.

244
00:12:38,590 --> 00:12:40,490
Така че тук са някои съставки.

245
00:12:40,490 --> 00:12:42,570
Мисля, че имам всичко, което искам.

246
00:12:42,570 --> 00:12:47,710
>> Някой би ли искал да предложи как съм
може да се свърже това може би горе до долу

247
00:12:47,710 --> 00:12:52,020
, за да се реши проблема с имащ
Scratch ход дясно на ляво на дясно, за да

248
00:12:52,020 --> 00:12:57,020
от ляво на дясно на ляво, всеки
време само подскачащи на разстояние от стената?

249
00:12:57,020 --> 00:12:58,050
Какво искам да направя?

250
00:12:58,050 --> 00:13:01,097
Кои блок трябва да се свърже с
"Когато зелен флаг кликнали на първо място"?

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

252
00:13:04,060 --> 00:13:06,200
>> ОК, така че нека да започнем с "завинаги".

253
00:13:06,200 --> 00:13:07,170
Какво става вътре в следващата?

254
00:13:07,170 --> 00:13:10,290
Някой друг.

255
00:13:10,290 --> 00:13:11,850
ОК, се движат стъпки.

256
00:13:11,850 --> 00:13:12,350
Добре.

257
00:13:12,350 --> 00:13:14,470
Тогава какво?

258
00:13:14,470 --> 00:13:15,120
Така че тогава IF.

259
00:13:15,120 --> 00:13:17,720
И забележи, макар и да изглежда
притисната плътно заедно,

260
00:13:17,720 --> 00:13:19,500
той просто ще нарасне до запълване.

261
00:13:19,500 --> 00:13:21,500
Тя просто ще скочи в мястото, където го искате.

262
00:13:21,500 --> 00:13:25,920
>> И това, което мога да прехвърля между
на дали и за тогава?

263
00:13:25,920 --> 00:13:27,180
Вероятно ", ако докосва ръба."

264
00:13:27,180 --> 00:13:31,800
И известие, отново, това е твърде голям
за това, но то ще расте, за да запълни.

265
00:13:31,800 --> 00:13:35,002
И след това завъртете на 15 градуса?

266
00:13:35,002 --> 00:13:35,710
Колко градуса?

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

268
00:13:38,800 --> 00:13:41,196
Да, така 180 ще се завърти
ми целия път наоколо.

269
00:13:41,196 --> 00:13:42,570
Така че нека да видим дали имам това право.

270
00:13:42,570 --> 00:13:43,930
Нека да го намалите.

271
00:13:43,930 --> 00:13:45,130
>> Нека да плъзнете Scratch нагоре.

272
00:13:45,130 --> 00:13:50,030
Така че той е малко изкривен
сега, но това е добре.

273
00:13:50,030 --> 00:13:52,231
Как мога да го възстановите лесно?

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

275
00:13:59,879 --> 00:14:01,045
Отивам да мамят леко.

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

277
00:14:04,074 --> 00:14:05,990
Така че аз съм добавяне на друг
блок, само за да бъде ясно.

278
00:14:05,990 --> 00:14:08,424
Искам да отбележа 90 градуса
надясно по подразбиране,

279
00:14:08,424 --> 00:14:10,840
така че аз съм просто ще му кажа
да направи това програмно.

280
00:14:10,840 --> 00:14:11,632
И тук отиваме.

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

282
00:14:14,740 --> 00:14:15,740
Ние като че ли са го направили.

283
00:14:15,740 --> 00:14:19,980
Това е малко странно, защото
той ходи с главата надолу.

284
00:14:19,980 --> 00:14:21,250
Нека да наречем, че е грешка.

285
00:14:21,250 --> 00:14:22,120
Това е грешка.

286
00:14:22,120 --> 00:14:27,320
Бъг е грешка в програмата, а
логическа грешка, че аз, човекът, направил.

287
00:14:27,320 --> 00:14:28,985
Защо се случва с главата надолу?

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

289
00:14:33,560 --> 00:14:35,250
Знаете MIT притеснявам или нали?

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

291
00:14:38,840 --> 00:14:42,550
>> Да, искам да кажа, че не е в MIT
вина. Те ми дадоха един пъзел парче

292
00:14:42,550 --> 00:14:44,970
която казва превърне някои броят на градуса.

293
00:14:44,970 --> 00:14:47,672
И по предложение на Виктория,
Аз съм се обърна на 180 градуса,

294
00:14:47,672 --> 00:14:48,880
което е правилният интуиция.

295
00:14:48,880 --> 00:14:53,700
Но превръщането на 180 градуса буквално
означава завъртане на 180 градуса,

296
00:14:53,700 --> 00:14:55,860
и това не е наистина
това, което искам, очевидно.

297
00:14:55,860 --> 00:14:58,026
Тъй като най-малко той е в
този двуизмерен свят,

298
00:14:58,026 --> 00:15:00,740
така повратна наистина се случва
да го обърне с главата надолу.

299
00:15:00,740 --> 00:15:04,030
>> Аз може би искате да използвате това, което блок
Вместо това, на базата на това, което виждате тук?

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

301
00:15:11,890 --> 00:15:14,790
Как бихме могли да поправя това?

302
00:15:14,790 --> 00:15:18,380
Да, за да можем да посоча
в обратна посока.

303
00:15:18,380 --> 00:15:22,300
И всъщност дори, че е
няма да бъде достатъчно,

304
00:15:22,300 --> 00:15:26,410
защото можем само трудно код
да сочи наляво или надясно.

305
00:15:26,410 --> 00:15:27,920
>> Знаеш ли какво можем да направим?

306
00:15:27,920 --> 00:15:30,160
Тя изглежда като имаме
удобство блок тук.

307
00:15:30,160 --> 00:15:32,987
Ако увеличите, виж
нещо ни харесва тук?

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

309
00:15:36,120 --> 00:15:40,020
Така че тя изглежда като MIT има
абстракция построена през тук.

310
00:15:40,020 --> 00:15:45,440
Този блок изглежда да е равностоен
за които други блокове, в множествено число?

311
00:15:45,440 --> 00:15:49,510
>> Това един блок изглежда да е равностоен
за цялото това трио на блокове

312
00:15:49,510 --> 00:15:50,880
че имаме тук.

313
00:15:50,880 --> 00:15:54,670
Така се оказва, че може да се опрости ми
програма, отървавайки се от всичко това

314
00:15:54,670 --> 00:15:58,270
и просто сложи това в тук.

315
00:15:58,270 --> 00:16:01,620
И сега той е все още малко
бъги, и това е добре за сега.

316
00:16:01,620 --> 00:16:03,370
Ще оставим, че да.

317
00:16:03,370 --> 00:16:06,000
Но моята програма е дори
-просто, и това също

318
00:16:06,000 --> 00:16:09,060
ще бъде представител
на гол в programming--

319
00:16:09,060 --> 00:16:13,430
е да идеално направи своя код, както е
проста, като компактен, колкото е възможно,

320
00:16:13,430 --> 00:16:15,650
докато все още е като
четим, колкото е възможно.

321
00:16:15,650 --> 00:16:20,310
Вие не искате да се направи така, накратко
че е трудно да се разбере.

322
00:16:20,310 --> 00:16:22,826
>> Но забележете съм заменя
три блока с един,

323
00:16:22,826 --> 00:16:24,200
и това е може би нещо добро.

324
00:16:24,200 --> 00:16:27,280
Аз бях абстрахира понятието
на проверка дали сте

325
00:16:27,280 --> 00:16:29,120
на ръба само с един блок.

326
00:16:29,120 --> 00:16:31,520
Сега можем да се забавляваме с това, в действителност.

327
00:16:31,520 --> 00:16:35,790
Това не променя толкова много
интелектуална стойност, но игриво стойност.

328
00:16:35,790 --> 00:16:39,730
Отивам да се продължи напред
и вземете този звук тук.

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

330
00:16:42,900 --> 00:16:46,420
Така че нека да вървим напред, и ме пусна
спрете програмата за миг.

331
00:16:46,420 --> 00:16:52,070
Отивам да се запише следното,
позволяваща достъп до микрофона ми.

332
00:16:52,070 --> 00:16:53,181
>> Ето ни.

333
00:16:53,181 --> 00:16:53,680
Ох.

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

335
00:16:58,710 --> 00:17:01,140
Нека да опитаме отново.

336
00:17:01,140 --> 00:17:02,279
Ето ни.

337
00:17:02,279 --> 00:17:03,570
ОК, аз записва нещо погрешно.

338
00:17:03,570 --> 00:17:04,580
Ето ни.

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

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

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

342
00:17:08,800 --> 00:17:09,300
Добре.

343
00:17:09,300 --> 00:17:10,791
Сега трябва да се отървете от това.

344
00:17:10,791 --> 00:17:11,290
Добре.

345
00:17:11,290 --> 00:17:13,950
>> Така че сега имам
записване на просто "ох".

346
00:17:13,950 --> 00:17:18,040
Така че сега аз ще отида
напред и да наричаме това "ох".

347
00:17:18,040 --> 00:17:20,270
Отивам да се върна
да ми скриптове, и сега

348
00:17:20,270 --> 00:17:25,460
известие има този блок, който се нарича
играе звук "мяу" или играе звук "ох".

349
00:17:25,460 --> 00:17:28,920
Отивам да плъзнете това, и където
трябва да сложа този за комичен ефект?

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

351
00:17:31,740 --> 00:17:37,860
Да, така че сега това е вид
бъги, защото сега това block--

352
00:17:37,860 --> 00:17:42,050
Забележете как това "ако на ръба,
скача "е вид автономен.

353
00:17:42,050 --> 00:17:43,704
Така че аз трябва да се определи това.

354
00:17:43,704 --> 00:17:44,870
Нека да вървим напред и да направим това.

355
00:17:44,870 --> 00:17:48,630
Нека да се отървете от този и да се върна
в нашия оригинален, по-съзнателно

356
00:17:48,630 --> 00:17:49,870
функционалност.

357
00:17:49,870 --> 00:18:01,080
Така че "ако докосва ръба, след това" Искам
за да включите, като Виктория, предложен,

358
00:18:01,080 --> 00:18:02,480
180 градуса.

359
00:18:02,480 --> 00:18:05,497
И искам да играя
звукът "ох" там?

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

361
00:18:11,800 --> 00:18:15,580
>> Да, забележи, че е извън
че жълт блок.

362
00:18:15,580 --> 00:18:17,680
Така че това също би било
бъг, но аз съм го забелязал.

363
00:18:17,680 --> 00:18:21,290
Така че аз ще го плъзнете до тук,
и известие сега е вътре в ", ако".

364
00:18:21,290 --> 00:18:24,250
Така че, "ако" е този вид
на подобно ръка-като петно

365
00:18:24,250 --> 00:18:26,260
че се случва само да
направи това, което е вътре в него.

366
00:18:26,260 --> 00:18:30,216
Така че сега, ако аз отдалечаване на
риска от annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> КОМПЮТЪР: Ох, ох, ох.

369
00:18:36,470 --> 00:18:39,910
>> DAVID Малан: И това
просто ще продължи вечно.

370
00:18:39,910 --> 00:18:44,160
Сега, само за да се ускори нещата
тук, нека да вървим напред и да се отворят,

371
00:18:44,160 --> 00:18:50,460
нека say-- ме пусна до известна
на мои неща от класа.

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

373
00:18:53,000 --> 00:19:00,220
И нека да се отворят, да речем, това
една, направена от един от нашите учебни събратя

374
00:19:00,220 --> 00:19:01,500
преди няколко години.

375
00:19:01,500 --> 00:19:04,732
Така че някои от вас може да се припомни,
тази игра от недалечното минало,

376
00:19:04,732 --> 00:19:05,940
и това е всъщност забележителна.

377
00:19:05,940 --> 00:19:08,190
Въпреки, че ние сме направили на
простият на програми в момента,

378
00:19:08,190 --> 00:19:09,980
нека да разгледаме какво е това
всъщност прилича.

379
00:19:09,980 --> 00:19:10,650
Нека ме удари игра.

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

381
00:19:14,210 --> 00:19:18,980
>> Така че в тази игра, ние имаме
жаба, и с помощта на стрелката keys--

382
00:19:18,980 --> 00:19:23,340
той поема по-големи стъпки, отколкото аз remember--
Аз имам контрол над тази жаба.

383
00:19:23,340 --> 00:19:29,630
И целта е да се получи през натоварения
път, без да поема в колите.

384
00:19:29,630 --> 00:19:34,735
И нека see-- ако отида до тук, аз
Трябва да се изчака за дневник, за да преминете от.

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

386
00:19:38,130 --> 00:19:39,274
Това се чувства като буболечка.

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

388
00:19:42,240 --> 00:19:43,495
Това е един вид грешка.

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

390
00:19:45,980 --> 00:19:46,480
Добре.

391
00:19:46,480 --> 00:19:51,550
Аз съм на това тук,
там, и след това да поддържате

392
00:19:51,550 --> 00:19:54,100
Ще докато не получите всички
жабите към лилия подложки.

393
00:19:54,100 --> 00:19:55,920
Сега това може да изглежда
всички по-сложни,

394
00:19:55,920 --> 00:19:57,840
но нека се опитаме да се прекъсне
това надолу психически

395
00:19:57,840 --> 00:20:00,040
и устно на съставните си блокове.

396
00:20:00,040 --> 00:20:03,910
Така че вероятно има един пъзел
парче, което не сме виждали още

397
00:20:03,910 --> 00:20:07,440
но това е в отговор на клавиши,
за неща, които удари на клавиатурата.

398
00:20:07,440 --> 00:20:11,660
>> Така че вероятно има някакъв вид
блок, който казва, ако ключовата равнява,

399
00:20:11,660 --> 00:20:15,965
След това направи нещо с Scratch--
Може би това се движат 10 стъпки по този начин.

400
00:20:15,965 --> 00:20:20,240
Ако се натисне надолу ключ, се движат 10 стъпки
по този начин, или левия клавиш, се движат 10 стъпки

401
00:20:20,240 --> 00:20:21,710
този начин, 10 стъпки, които.

402
00:20:21,710 --> 00:20:23,644
Аз ясно превърна котката в жаба.

403
00:20:23,644 --> 00:20:26,060
Така че това е точно там, където
костюм, като скреч разговори it-- ние

404
00:20:26,060 --> 00:20:28,440
просто внесени снимка на жаба.

405
00:20:28,440 --> 00:20:29,570
>> Но какво друго се случва?

406
00:20:29,570 --> 00:20:32,794
Какви други реда код,
какви други парчета от пъзел

407
00:20:32,794 --> 00:20:35,460
Направих Блейк, нашето учение колега,
използва в тази програма, очевидно?

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

409
00:20:38,320 --> 00:20:42,730
Какво се прави всичко move--
какво програмиране изгради?

410
00:20:42,730 --> 00:20:44,950
>> Предложение, sure-- така че
преместите блок, със сигурност.

411
00:20:44,950 --> 00:20:49,330
И това, което е, че ход блок
вътре, най-вероятно?

412
00:20:49,330 --> 00:20:52,850
Да, някакъв вид цикъл, може би
завинаги блокира, може би повторение block--

413
00:20:52,850 --> 00:20:54,070
повтаря, докато блок.

414
00:20:54,070 --> 00:20:57,330
И това е това, което се прави на дървени трупи, и
лилия подложки и всичко останало ход

415
00:20:57,330 --> 00:20:57,990
напред и назад.

416
00:20:57,990 --> 00:21:00,270
Това е просто става безкрайно.

417
00:21:00,270 --> 00:21:03,180
>> Защо някои от колите
движи по-бързо от другите?

418
00:21:03,180 --> 00:21:06,607
Какво е различното в тези програми?

419
00:21:06,607 --> 00:21:09,690
Да, може би някои от тях са като
повече стъпки наведнъж и някои от тях

420
00:21:09,690 --> 00:21:10,690
по-малко стъпки наведнъж.

421
00:21:10,690 --> 00:21:14,670
И визуален ефект
е бързо в сравнение с бавно.

422
00:21:14,670 --> 00:21:16,030
>> Какво мислите се случи?

423
00:21:16,030 --> 00:21:19,700
Когато имам моята жаба целия път
другата страна на улицата и реката

424
00:21:19,700 --> 00:21:23,560
върху лилия, нещо,
Забележително е случило.

425
00:21:23,560 --> 00:21:26,540
Какво се случи, след като се направи това?

426
00:21:26,540 --> 00:21:27,210
Тя спря.

427
00:21:27,210 --> 00:21:29,680
Това жаба спря, и
Имам втори жаба.

428
00:21:29,680 --> 00:21:33,155
Така че това, което конструкция трябва да бъде
използва там, какво функция?

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

430
00:21:36,020 --> 00:21:38,660
>> Да, така че има някакъв вид
"Ако" състоянието там, също.

431
00:21:38,660 --> 00:21:41,909
И се оказва out-- не видяхме this--
но има други блокове в там, че

432
00:21:41,909 --> 00:21:45,300
Може да се каже, ако се допират
Друго нещо, което на екрана,

433
00:21:45,300 --> 00:21:47,720
ако се докосва лилия тампон, "след това."

434
00:21:47,720 --> 00:21:50,810
И след това е, когато ние
да се появи втората жаба.

435
00:21:50,810 --> 00:21:54,969
Така че, въпреки че тази игра е със сигурност
много от, въпреки че на пръв поглед

436
00:21:54,969 --> 00:21:58,010
има толкова много ще on-- и Блейк
не привличам това до две минути,

437
00:21:58,010 --> 00:22:00,390
то вероятно си взе няколко
часа, за да се създаде тази игра

438
00:22:00,390 --> 00:22:03,850
въз основа на паметта или видеоклипове му
на версия на това недалечното минало е.

439
00:22:03,850 --> 00:22:07,940
Но всички тези малки неща
става на екрана в изолация

440
00:22:07,940 --> 00:22:11,550
се свеждат до това много проста
constructs-- движения или изявления

441
00:22:11,550 --> 00:22:15,519
като говорихме, примки и
условия, и това е за него.

442
00:22:15,519 --> 00:22:17,060
Има няколко други красиви черти.

443
00:22:17,060 --> 00:22:19,130
Някои от тях са чисто
естетически или акустична,

444
00:22:19,130 --> 00:22:20,964
като звуците аз просто играе с.

445
00:22:20,964 --> 00:22:23,380
Но в по-голямата си част, вие
има в този език, Scratch,

446
00:22:23,380 --> 00:22:25,350
всички от основните
градивни елементи, които можете

447
00:22:25,350 --> 00:22:29,280
има в C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
и всякакъв брой други езици.

449
00:22:32,960 --> 00:22:36,720
Всякакви въпроси за Scratch?

450
00:22:36,720 --> 00:22:37,220
Добре.

451
00:22:37,220 --> 00:22:40,303
Така че ние няма да се потопите в дълбок до нулата,
въпреки че сте добре дошли този уикенд,

452
00:22:40,303 --> 00:22:42,860
особено ако имате деца или
племенници и такива,

453
00:22:42,860 --> 00:22:44,220
да ги запознае с Scratch.

454
00:22:44,220 --> 00:22:47,960
Това всъщност е чудесно игриво
среда с, както казват неговите автори,

455
00:22:47,960 --> 00:22:49,120
много високи тавани.

456
00:22:49,120 --> 00:22:51,670
Въпреки, че ние започнахме с
Самите детайли от ниско ниво,

457
00:22:51,670 --> 00:22:54,890
Вие наистина може да направи доста малко
с него, и това е може би

458
00:22:54,890 --> 00:22:57,360
демонстрация на точно това.

459
00:22:57,360 --> 00:23:02,920
>> Но нека сега преминете към някои по-
сложни проблеми, ако щете,

460
00:23:02,920 --> 00:23:05,870
известен като "търсене" и
"Сортиране", по-общо.

461
00:23:05,870 --> 00:23:09,500
Имахме този телефонен указател earlier-- ето
друг само за discussion--

462
00:23:09,500 --> 00:23:13,460
че ние бяхме в състояние да търсите
по-ефективно, защото

463
00:23:13,460 --> 00:23:15,270
на значителен предположение.

464
00:23:15,270 --> 00:23:17,655
И само за да бъде ясно, какво
предположение беше, че вземането

465
00:23:17,655 --> 00:23:19,280
когато се търси чрез този телефонен указател?

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

467
00:23:23,342 --> 00:23:25,300
Това Майк Смит е в
телефонния указател, макар че

468
00:23:25,300 --> 00:23:27,410
ще бъде в състояние да се справят
сценария без него

469
00:23:27,410 --> 00:23:30,720
там, ако аз просто спря преждевременно.

470
00:23:30,720 --> 00:23:31,806
Книгата е азбучен.

471
00:23:31,806 --> 00:23:33,930
И това е много щедър
предположение, защото това

472
00:23:33,930 --> 00:23:36,580
означава someone-- Аз съм един вид
на рязане на корнер,

473
00:23:36,580 --> 00:23:40,580
като аз съм по-бързо, защото някой
друго е много упорита работа за мен.

474
00:23:40,580 --> 00:23:43,120
>> Но какво, ако телефонът
книга бяха несортирани?

475
00:23:43,120 --> 00:23:47,050
Може би Verizon имам мързелив, просто хвърли
имена и номера на всички там

476
00:23:47,050 --> 00:23:50,120
може би в реда, в който те
регистрирали за телефонни услуги.

477
00:23:50,120 --> 00:23:54,570
И колко време отнема мен
да се намери някой като Майк Смит?

478
00:23:54,570 --> 00:23:58,160
1000 страница телефон book-- колко
страници Трябва ли да погледнете през?

479
00:23:58,160 --> 00:23:58,905
>> Всички тях.

480
00:23:58,905 --> 00:24:00,030
Ти си нещо на късмет.

481
00:24:00,030 --> 00:24:03,420
Вие буквално трябва да разгледаме всеки
страница, ако телефонния указател е просто

482
00:24:03,420 --> 00:24:04,450
произволно подредени.

483
00:24:04,450 --> 00:24:06,910
Можете да получите късмет и да намерят Mike
още на първата страница, защото той

484
00:24:06,910 --> 00:24:08,826
беше първият клиент
по поръчка на телефонни услуги.

485
00:24:08,826 --> 00:24:10,760
Но той може да е бил последният, също.

486
00:24:10,760 --> 00:24:12,500
>> Така произволен ред, не е добро.

487
00:24:12,500 --> 00:24:16,750
Така че предполагам, че трябва да се справи със
телефонен указател или като цяло данните сортиране

488
00:24:16,750 --> 00:24:18,520
че ние сме били дадени.

489
00:24:18,520 --> 00:24:19,440
Как можем да направим това?

490
00:24:19,440 --> 00:24:21,360
>> Е, нека просто опитайте
Един прост пример тук.

491
00:24:21,360 --> 00:24:24,290
Нека да вървим напред и да хвърля
Няколко номера на дъската.

492
00:24:24,290 --> 00:24:35,480
Да предположим, че цифрите, които имаме, са,
да речем, четири, две, едно, а три.

493
00:24:35,480 --> 00:24:38,390
И, Бен, сортирате тези номера за нас.

494
00:24:38,390 --> 00:24:39,017
>> Добре.

495
00:24:39,017 --> 00:24:39,850
Как го направи това?

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

497
00:24:42,731 --> 00:24:43,230
Добре.

498
00:24:43,230 --> 00:24:44,710
Така че започнете с най-малките
стойност и най-високата,

499
00:24:44,710 --> 00:24:46,084
и това е наистина добра интуиция.

500
00:24:46,084 --> 00:24:48,080
И осъзнавам, че ние
хората са всъщност доста

501
00:24:48,080 --> 00:24:49,913
добри в решаването на проблеми
по този начин, най-малко

502
00:24:49,913 --> 00:24:51,810
когато данните са сравнително малко.

503
00:24:51,810 --> 00:24:54,860
Веднага след като започнете да има стотици
на номера, хиляди номера,

504
00:24:54,860 --> 00:24:58,440
милиони номера, Бен вероятно
не може да го направи доста, че бързо,

505
00:24:58,440 --> 00:25:00,620
се предполага, че има
пропуски по отношение на номера.

506
00:25:00,620 --> 00:25:03,450
Доста лесно да брои до милион
в противен случай, просто отнема време.

507
00:25:03,450 --> 00:25:07,150
>> Така че алгоритъмът звучи
като Бен използва само сега

508
00:25:07,150 --> 00:25:08,930
Беше търсене за най-малък брой.

509
00:25:08,930 --> 00:25:12,900
Така че, въпреки че ние, хората могат да се
в много информация визуално,

510
00:25:12,900 --> 00:25:14,830
компютър е всъщност
малко по-ограничен.

511
00:25:14,830 --> 00:25:17,560
Компютърът може само
Посетете един байт в даден момент

512
00:25:17,560 --> 00:25:20,770
или може би четири байта в един time--
тези дни може би 8 байта в един time--

513
00:25:20,770 --> 00:25:24,450
но много малък брой
байтове в даден момент.

514
00:25:24,450 --> 00:25:28,480
>> Така че при положение, че ние наистина трябва
четири отделни стойности here--

515
00:25:28,480 --> 00:25:32,440
и можете да мислите за Бен като имащи
наочници за ако той беше на компютър, като

516
00:25:32,440 --> 00:25:36,450
че той не може да види нищо друго
от един номер на time--

517
00:25:36,450 --> 00:25:39,720
така че ние като цяло ще приемем, като в
Английски, ще се чете от дясно на ляво.

518
00:25:39,720 --> 00:25:42,870
Така че първото число Бен вероятно изглеждаше
при Беше четири и след това много бързо

519
00:25:42,870 --> 00:25:44,770
осъзнах, че е доста голям
number-- нека продължим да търсим.

520
00:25:44,770 --> 00:25:45,357
>> Има две.

521
00:25:45,357 --> 00:25:45,940
Чакай малко.

522
00:25:45,940 --> 00:25:47,070
Две е по-малък от четири.

523
00:25:47,070 --> 00:25:47,986
Отивам да си спомня.

524
00:25:47,986 --> 00:25:49,070
Две сега е най-малката.

525
00:25:49,070 --> 00:25:50,417
Сега one--, че е дори по-добре.

526
00:25:50,417 --> 00:25:51,250
Това е още по-малък.

527
00:25:51,250 --> 00:25:54,000
Отивам да забрави за двама
и просто не забравяйте едно сега.

528
00:25:54,000 --> 00:25:56,550
>> И можеше да спре да търси?

529
00:25:56,550 --> 00:25:58,360
Е, той може да се основава
на тази информация,

530
00:25:58,360 --> 00:26:00,477
но той е по-добре за търсене
останалата част от списъка.

531
00:26:00,477 --> 00:26:02,060
Защото това, което, ако нулата бяха в списъка?

532
00:26:02,060 --> 00:26:03,643
Какво става, ако отрицателен бяха в списъка?

533
00:26:03,643 --> 00:26:07,720
Той знае само, че неговият отговор
е правилно, ако той е изчерпателно

534
00:26:07,720 --> 00:26:08,729
проверява целия списък.

535
00:26:08,729 --> 00:26:10,020
Така че ние гледаме на останалата част на този.

536
00:26:10,020 --> 00:26:11,394
Three--, че е загуба на време.

537
00:26:11,394 --> 00:26:13,540
Имаш късмет, но бях
все още правилно да се направи това.

538
00:26:13,540 --> 00:26:17,857
И така, сега той вероятно
избран най-малкият брой

539
00:26:17,857 --> 00:26:20,440
и просто да го постави в началото
от списъка, тъй като аз ще направя тук.

540
00:26:20,440 --> 00:26:23,480
Сега какво направи следващата, въпреки че
ти не мислиш за него почти

541
00:26:23,480 --> 00:26:25,962
в този смисъл?

542
00:26:25,962 --> 00:26:27,670
Повторете процеса,
така някаква линия.

543
00:26:27,670 --> 00:26:28,920
Има една позната идея.

544
00:26:28,920 --> 00:26:30,860
Така че тук е четири.

545
00:26:30,860 --> 00:26:32,110
Това е в момента най-малките.

546
00:26:32,110 --> 00:26:33,220
Това е кандидат.

547
00:26:33,220 --> 00:26:33,900
Вече не.

548
00:26:33,900 --> 00:26:34,770
Сега аз съм виждал две.

549
00:26:34,770 --> 00:26:36,630
Това е следващата по-малка елемент.

550
00:26:36,630 --> 00:26:40,800
Three--, че не е по-малък, така че
Сега Бен може да се извади от двете.

551
00:26:40,800 --> 00:26:44,510
>> И сега ние повторете процеса, както и
Разбира три получава извади следващия.

552
00:26:44,510 --> 00:26:45,420
Повторете този процес.

553
00:26:45,420 --> 00:26:46,990
Четири получава извади.

554
00:26:46,990 --> 00:26:50,140
И сега ние сме изложени на номера,
така в списъка трябва да бъдат сортирани.

555
00:26:50,140 --> 00:26:51,960
>> И наистина, това е формален алгоритъм.

556
00:26:51,960 --> 00:26:56,610
Компютърен учен би
наричаме това "избор на сортиране,"

557
00:26:56,610 --> 00:27:00,880
като идеята е сортиране на
изброят iteratively-- отново

558
00:27:00,880 --> 00:27:03,807
и отново избиране
най-малък брой.

559
00:27:03,807 --> 00:27:06,140
И това, което е хубаво за него е
това е просто толкова дяволски интуитивен.

560
00:27:06,140 --> 00:27:07,470
Това е толкова просто.

561
00:27:07,470 --> 00:27:11,100
И вие може да се повтаря един и същ
работа отново и отново.

562
00:27:11,100 --> 00:27:12,150
Просто е.

563
00:27:12,150 --> 00:27:17,170
>> В този случай това е бързо, но
колко време всъщност взема?

564
00:27:17,170 --> 00:27:19,880
Нека да изглежда и
се чувствам малко по-досаден.

565
00:27:19,880 --> 00:27:24,150
Така че едно, две, три, четири, пет и шест,
седем, осем, девет, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- произволен брой.

567
00:27:26,160 --> 00:27:28,780
Аз просто исках повече това
време, отколкото само четиримата.

568
00:27:28,780 --> 00:27:30,780
Така че, ако аз имам едно цяло
куп номера го now--

569
00:27:30,780 --> 00:27:32,420
дори не значение
това, което те are-- нека

570
00:27:32,420 --> 00:27:34,380
мисля за това, този
алгоритъм наистина е като.

571
00:27:34,380 --> 00:27:35,857
>> Да предположим, че има номера там.

572
00:27:35,857 --> 00:27:38,190
Отново, няма значение какво
те са, но те са случайни.

573
00:27:38,190 --> 00:27:39,679
Кандидатствам алгоритъм на Бен.

574
00:27:39,679 --> 00:27:41,220
Трябва да изберете най-малкият брой.

575
00:27:41,220 --> 00:27:41,761
Какво да правя?

576
00:27:41,761 --> 00:27:44,240
И аз ще се физически
го направя този път да го изиграят.

577
00:27:44,240 --> 00:27:46,099
Търси, грижа,
търси, търси, търси.

578
00:27:46,099 --> 00:27:48,140
Само от време съм се да
В края на списъка може да

579
00:27:48,140 --> 00:27:51,230
Давам си сметка, най-малките
брой е два и този път.

580
00:27:51,230 --> 00:27:52,720
Човек не е в списъка.

581
00:27:52,720 --> 00:27:54,400
Така че остави две.

582
00:27:54,400 --> 00:27:55,590
>> Какво да правя сега?

583
00:27:55,590 --> 00:27:58,600
Търси, грижа, грижа, грижа.

584
00:27:58,600 --> 00:28:02,250
Сега разбрах, числото седем, защото
има пропуски в тези numbers--

585
00:28:02,250 --> 00:28:03,300
но просто произволно.

586
00:28:03,300 --> 00:28:03,800
Добре.

587
00:28:03,800 --> 00:28:06,030
Така че сега мога да остави седем.

588
00:28:06,030 --> 00:28:08,860
Търси гледам, да търсим.

589
00:28:08,860 --> 00:28:11,030
>> Сега аз съм се предположи, на
Разбира се, че Бен не

590
00:28:11,030 --> 00:28:14,780
има допълнително RAM, допълнително
памет, защото, разбира се,

591
00:28:14,780 --> 00:28:16,080
Търся в същия брой.

592
00:28:16,080 --> 00:28:18,246
Със сигурност бих могъл да си спомни
Всички тези номера,

593
00:28:18,246 --> 00:28:19,930
и това е абсолютно вярно.

594
00:28:19,930 --> 00:28:22,610
Но ако Бен помни всичко
на номерата, което е видял,

595
00:28:22,610 --> 00:28:24,430
той не е наистина
фундаментален напредък

596
00:28:24,430 --> 00:28:26,170
защото той вече има
възможността за търсене

597
00:28:26,170 --> 00:28:27,540
чрез числата на дъската.

598
00:28:27,540 --> 00:28:29,373
Помня всичко на
номера не помогнат,

599
00:28:29,373 --> 00:28:32,490
защото той все още може като компютър
само погледнете, казахме, един брой

600
00:28:32,490 --> 00:28:33,080
на време.

601
00:28:33,080 --> 00:28:35,760
Така че няма някаква измама
там, че можете да използвате.

602
00:28:35,760 --> 00:28:39,170
>> Така че в действителност, тъй като аз
продължавам да търся в списъка,

603
00:28:39,170 --> 00:28:44,200
Аз буквално трябва да се запази просто ще
назад и напред през него, скубане навън

604
00:28:44,200 --> 00:28:45,710
следващата най-малкият брой.

605
00:28:45,710 --> 00:28:48,810
И както можете да вид заключим
от моите глупави движения,

606
00:28:48,810 --> 00:28:50,860
това също ще стане много
досаден много бързо,

607
00:28:50,860 --> 00:28:54,850
и аз като че ли да се връщаме и
напред, назад и напред, доста малко.

608
00:28:54,850 --> 00:29:03,220
Сега, за да бъдем честни, аз не трябва да отида
толкова, добре, нека да see-- да бъде справедлив,

609
00:29:03,220 --> 00:29:06,310
Аз не трябва да ходят доста
толкова стъпки, всеки път.

610
00:29:06,310 --> 00:29:09,200
Защото, разбира се, както аз
изберете номера от списъка,

611
00:29:09,200 --> 00:29:11,860
останалата част от списъка става все по-кратък.

612
00:29:11,860 --> 00:29:14,240
>> И така, нека да мислим за
колко стъпки аз съм всъщност

613
00:29:14,240 --> 00:29:16,010
traipsing през всяко време.

614
00:29:16,010 --> 00:29:18,950
В първата ситуация
имахме 16 номера,

615
00:29:18,950 --> 00:29:22,210
и така maximally-- му нека просто
направите това за discussion--

616
00:29:22,210 --> 00:29:25,640
Аз трябваше да погледне през 16
номера, за да намерят най-малките.

617
00:29:25,640 --> 00:29:28,420
Но след като аз изтръгната
най-малък брой, как

618
00:29:28,420 --> 00:29:30,590
отдавна е останалата част от списъка, разбира се?

619
00:29:30,590 --> 00:29:31,420
Само 15.

620
00:29:31,420 --> 00:29:34,670
Така че колко числа направиха Бен или имам
да погледнете през втория път?

621
00:29:34,670 --> 00:29:36,832
15, само за да отидат и да намерят най-малките.

622
00:29:36,832 --> 00:29:39,540
Но сега, разбира се, в списъка е,
също по-малки, отколкото преди.

623
00:29:39,540 --> 00:29:42,540
Така че колко стъпки направиха I
Трябва да се вземе следващия път?

624
00:29:42,540 --> 00:29:49,970
14 и след 13 и след 12, плюс точка,
точка, DOT, докато аз съм оставил само с един.

625
00:29:49,970 --> 00:29:53,146
Така че сега е компютърен специалист би
попитам, добре, това, което прави, че всички сме равни?

626
00:29:53,146 --> 00:29:55,770
То всъщност се равнява на някои бетон
брой, че ние със сигурност може да

627
00:29:55,770 --> 00:30:00,490
направя аритметично, но ние искаме да говорим
за ефективността на алгоритми

628
00:30:00,490 --> 00:30:04,940
малко повече formulaically,
независимо от това колко дълго списъка е.

629
00:30:04,940 --> 00:30:06,240
>> И така, знаете ли какво?

630
00:30:06,240 --> 00:30:09,860
Това е 16, но както казах и преди,
нека просто се обадете на размера на проблема

631
00:30:09,860 --> 00:30:10,970
п, където п е известно номер.

632
00:30:10,970 --> 00:30:13,220
Може би това е 16, може би това е
три, може би това е един милион.

633
00:30:13,220 --> 00:30:13,761
Не знам.

634
00:30:13,761 --> 00:30:14,390
Не ме интересува.

635
00:30:14,390 --> 00:30:16,520
Това, което наистина искам, е
формула, която мога

636
00:30:16,520 --> 00:30:19,420
използвате, за да сравни този алгоритъм
срещу други алгоритми

637
00:30:19,420 --> 00:30:22,350
че някой може да претендира
са по-добре или по-лошо.

638
00:30:22,350 --> 00:30:25,430
>> Така се оказва, и само аз
Знам това от началното училище,

639
00:30:25,430 --> 00:30:34,790
че това всъщност работи до същите
нещо като п над п плюс една над два.

640
00:30:34,790 --> 00:30:40,020
И това се случи, за да бъде равна, на
Разбира се, п квадрат плюс п над два.

641
00:30:40,020 --> 00:30:43,250
Така че, ако аз исках формула
за колко стъпки

642
00:30:43,250 --> 00:30:46,330
са участвали в разглеждане на всички
на тези числа отново и отново

643
00:30:46,330 --> 00:30:52,681
и отново, и отново, бих казал,
това е п квадрат плюс п над два.

644
00:30:52,681 --> 00:30:53,430
Но знаете ли какво?

645
00:30:53,430 --> 00:30:54,500
Това просто изглежда разхвърлян.

646
00:30:54,500 --> 00:30:56,470
Аз просто наистина искате
общ смисъл на нещата.

647
00:30:56,470 --> 00:30:58,810
И вие може да си припомни от
гимназията, че има

648
00:30:58,810 --> 00:31:00,660
е идеята на най-високо термин ред.

649
00:31:00,660 --> 00:31:05,300
Коя от тези условия, н
квадрат, п, или на половина,

650
00:31:05,300 --> 00:31:07,550
има най-голямо влияние с течение на времето?

651
00:31:07,550 --> 00:31:11,920
Колкото по-голяма п получава, които
на тези въпроси най-много?

652
00:31:11,920 --> 00:31:15,560
>> С други думи, ако включа
на милион, N квадрат

653
00:31:15,560 --> 00:31:17,900
ще бъде най-вероятно
факторът доминиращ,

654
00:31:17,900 --> 00:31:21,670
защото един милион пъти
себе си е много по-голям

655
00:31:21,670 --> 00:31:23,682
от плюс една допълнителна млн.

656
00:31:23,682 --> 00:31:24,390
Така ли какво?

657
00:31:24,390 --> 00:31:27,305
Това е толкова дяволски голяма
номер, ако квадрат редица.

658
00:31:27,305 --> 00:31:28,430
Това няма значение.

659
00:31:28,430 --> 00:31:30,596
Ние просто ще кръст, който
навън и да забравите за нея.

660
00:31:30,596 --> 00:31:34,250
И така компютърен учен ще каже
че ефективността на този алгоритъм

661
00:31:34,250 --> 00:31:37,850
е от порядъка на п squared--
Искам да кажа, наистина приближение.

662
00:31:37,850 --> 00:31:40,810
Това е нещо като грубо н квадрат.

663
00:31:40,810 --> 00:31:44,130
С течение на времето, толкова по-голям
и по-голяма п получава, това

664
00:31:44,130 --> 00:31:47,610
е добра оценка Понеже това, което
ефективност или липса на ефективност

665
00:31:47,610 --> 00:31:49,400
на този алгоритъм всъщност е.

666
00:31:49,400 --> 00:31:52,040
И аз се извлече, че, разбира се,
от всъщност прави по математика.

667
00:31:52,040 --> 00:31:54,040
Но сега аз съм просто къдрене
ръцете ми, защото аз просто

668
00:31:54,040 --> 00:31:55,790
Искам най-общ смисъл на този алгоритъм.

669
00:31:55,790 --> 00:31:58,850
>> Така че, използвайки същата логика, междувременно,
нека разгледаме друг алгоритъм

670
00:31:58,850 --> 00:32:01,162
ние вече изглеждаше at-- линейно търсене.

671
00:32:01,162 --> 00:32:02,870
Когато бях на търсенето
за телефон book--

672
00:32:02,870 --> 00:32:05,980
не го сортиране, търсене
чрез телефон book--

673
00:32:05,980 --> 00:32:09,197
ние непрекъснато повтаряше, че е
1000 стъпки, или 500 стъпки.

674
00:32:09,197 --> 00:32:10,280
Но нека да обобщим, че.

675
00:32:10,280 --> 00:32:12,860
Ако има н страници в
телефонния указател, това, което е

676
00:32:12,860 --> 00:32:17,250
времето на работа или на
ефективност на линеен търсене?

677
00:32:17,250 --> 00:32:19,750
Това е от порядъка на
колко стъпки, за да се намери

678
00:32:19,750 --> 00:32:24,210
Майк Смит се използва линейна търсене,
първият алгоритъм, или дори на втория?

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

680
00:32:27,240 --> 00:32:31,710
>> В най-лошия случай, Майк
е в края на книгата.

681
00:32:31,710 --> 00:32:35,590
Така че, ако телефонния указател има 1000 страници,
казахме последно време, в най-лошия случай,

682
00:32:35,590 --> 00:32:38,380
той може да отнеме приблизително колко
много страници, за да намерят Майк?

683
00:32:38,380 --> 00:32:38,990
Подобно на 1000.

684
00:32:38,990 --> 00:32:39,830
Това е горната граница.

685
00:32:39,830 --> 00:32:41,790
Това е възможно най-лошата ситуация.

686
00:32:41,790 --> 00:32:44,410
Но отново, ние сме се отдалечава
от номера като 1000 сега.

687
00:32:44,410 --> 00:32:45,730
Това е просто п.

688
00:32:45,730 --> 00:32:47,470
>> Така че това, което е най-логичното заключение?

689
00:32:47,470 --> 00:32:50,210
Намирането Mike в телефона
книга, която има п страници

690
00:32:50,210 --> 00:32:55,280
може да вземе, в много лошия случай,
колко стъпки от порядъка на N?

691
00:32:55,280 --> 00:32:58,110
И наистина компютър
учен ще каже

692
00:32:58,110 --> 00:33:02,340
че времето на работа, или
изпълнение или ефикасността

693
00:33:02,340 --> 00:33:07,470
или неефективност, на алгоритъм, като
линейно търсене е от порядъка на п.

694
00:33:07,470 --> 00:33:10,010
И ние можем да се прилагат едни и същи
логика на пресичане нещо

695
00:33:10,010 --> 00:33:13,170
като Току-що е за втората
алгоритъм имахме с телефонния указател,

696
00:33:13,170 --> 00:33:16,040
където отидохме две страници наведнъж.

697
00:33:16,040 --> 00:33:20,120
>> Така че 1000 страница телефон книга може
предприеме ни 500 страници завои, плюс един

698
00:33:20,120 --> 00:33:21,910
ако ние се удвои малко назад.

699
00:33:21,910 --> 00:33:26,590
Така че, ако един телефонен указател има п страници, но
правим две страници в даден момент,

700
00:33:26,590 --> 00:33:28,900
това е грубо какво?

701
00:33:28,900 --> 00:33:33,190
N над две, така че е като п над два.

702
00:33:33,190 --> 00:33:38,490
Но аз направих за да претендира за
Преди миг, че п над two--

703
00:33:38,490 --> 00:33:41,060
това е почти същото като просто п.

704
00:33:41,060 --> 00:33:44,050
Това е просто един постоянен фактор,
компютърни специалисти ще кажат.

705
00:33:44,050 --> 00:33:45,970
Нека да се съсредоточи само върху
променливите, really--

706
00:33:45,970 --> 00:33:47,780
най-големите променливи в уравнението.

707
00:33:47,780 --> 00:33:52,530
>> Така линеен търсене, независимо дали се направи един
страница в даден момент или две страници наведнъж,

708
00:33:52,530 --> 00:33:54,810
е нещо фундаментално еднакви.

709
00:33:54,810 --> 00:33:56,880
Тя все още е от порядъка на п.

710
00:33:56,880 --> 00:34:01,930
Но аз доминираха с моя снимка по-рано
че третата алгоритъм не е

711
00:34:01,930 --> 00:34:02,480
линейна.

712
00:34:02,480 --> 00:34:03,605
Това не беше по права линия.

713
00:34:03,605 --> 00:34:08,659
Това беше, че крива линия, и
алгебрична формула имаше какво?

714
00:34:08,659 --> 00:34:11,812
Вход на, N- така влезте база двама от п.

715
00:34:11,812 --> 00:34:14,520
И ние не трябва да отиде в твърде
много подробности относно логаритми днес,

716
00:34:14,520 --> 00:34:17,394
но повечето компютърни учени не би
дори да ви кажа това, което е в основата.

717
00:34:17,394 --> 00:34:20,639
Защото всичко е просто
постоянни фактори, така да се каже,

718
00:34:20,639 --> 00:34:22,659
само незначителни числови разлики.

719
00:34:22,659 --> 00:34:31,179
И така, това би било много чести
начин за особено официално компютър

720
00:34:31,179 --> 00:34:33,949
учени в борда или
програмисти в бяла дъска

721
00:34:33,949 --> 00:34:36,889
всъщност спорят които
алгоритъм, че биха използвали

722
00:34:36,889 --> 00:34:39,500
или това, което ефективността
на тяхната алгоритъм е.

723
00:34:39,500 --> 00:34:42,960
>> И това не е непременно нещо
обсъждате в някоя големи подробности,

724
00:34:42,960 --> 00:34:47,889
но добър програмист е някой,
който има солидна, официално фон.

725
00:34:47,889 --> 00:34:50,120
Той е в състояние да говори, за да
ви в този вид начин

726
00:34:50,120 --> 00:34:53,350
и всъщност правят
качествени аргументи като

727
00:34:53,350 --> 00:34:56,870
защо един алгоритъм или
една част от софтуера

728
00:34:56,870 --> 00:35:00,165
превъзхожда по някакъв начин към друг.

729
00:35:00,165 --> 00:35:02,540
Защото вие със сигурност може да
просто стартирате програмата на един човек

730
00:35:02,540 --> 00:35:04,980
и да отчита броя на секунди
е необходимо, за да се справи някои цифри,

731
00:35:04,980 --> 00:35:06,710
и можете да изпълните някои
програма на друго лице

732
00:35:06,710 --> 00:35:08,418
и се преброят
на секунди, необходимо.

733
00:35:08,418 --> 00:35:12,840
Но това е по-общ начин, че
можете да използвате, за да се анализира алгоритми,

734
00:35:12,840 --> 00:35:15,520
ако щете, само на
хартия или просто устно.

735
00:35:15,520 --> 00:35:18,430
Без дори да го използвате, без да се
дори се опитва примерни входове,

736
00:35:18,430 --> 00:35:20,180
може просто да се разсъждава през него.

737
00:35:20,180 --> 00:35:24,670
И така, с наемането на разработчика или ако
като него или нея нещо спори с вас

738
00:35:24,670 --> 00:35:28,460
защо им алгоритъм, тяхната тайна
сос за търсене милиарди

739
00:35:28,460 --> 00:35:30,580
на уеб страници за вашия
компанията е по-добре, те

740
00:35:30,580 --> 00:35:33,302
са видовете аргументи те
в идеалния случай трябва да бъде в състояние да направи.

741
00:35:33,302 --> 00:35:35,010
Или поне това са
вида на нещата

742
00:35:35,010 --> 00:35:40,211
че ще излезе в дискусия, в
поне в един много формално обсъждане.

743
00:35:40,211 --> 00:35:40,710
Добре.

744
00:35:40,710 --> 00:35:44,400
Така Бен предложи нещо
наречен избор на сортиране.

745
00:35:44,400 --> 00:35:48,200
Но аз ще се предложи, че има
други начини за това, също.

746
00:35:48,200 --> 00:35:50,400
Това, което аз наистина не харесвам
за алгоритъм на Бен

747
00:35:50,400 --> 00:35:54,400
е, че той продължи да върви, или
като ми върви, назад и напред

748
00:35:54,400 --> 00:35:56,930
и назад и напред и назад и напред.

749
00:35:56,930 --> 00:36:04,130
Ами ако вместо аз да направя
нещо като тези номера тук

750
00:36:04,130 --> 00:36:08,200
и аз да се справя само с всеки
номер на свой ред, както аз съм го дал?

751
00:36:08,200 --> 00:36:10,780
>> С други думи, тук е
моя списък от номера.

752
00:36:10,780 --> 00:36:12,944
Четири, едно, три, две.

753
00:36:12,944 --> 00:36:14,360
И аз ще направя следното.

754
00:36:14,360 --> 00:36:17,230
Отивам да въведете номера
където им е мястото, а

755
00:36:17,230 --> 00:36:18,980
отколкото ги изберете един по един.

756
00:36:18,980 --> 00:36:20,820
С други думи, тук е номер четири.

757
00:36:20,820 --> 00:36:22,430
>> Ето първоначалното ми списък.

758
00:36:22,430 --> 00:36:25,290
И аз ще се запази
същество нов списък тук.

759
00:36:25,290 --> 00:36:26,710
Така че това е най-старата списъка.

760
00:36:26,710 --> 00:36:28,560
Това е нов списък.

761
00:36:28,560 --> 00:36:30,220
Виждам броят четири първи.

762
00:36:30,220 --> 00:36:34,500
Моят нов списък е първоначално празен,
така че е тривиално случая

763
00:36:34,500 --> 00:36:36,410
че четири сега е асорти списък.

764
00:36:36,410 --> 00:36:39,560
Аз съм просто като броят аз съм дал,
и аз съм го поставя в моя нов списък.

765
00:36:39,560 --> 00:36:41,460
>> Се сортира този нов списък?

766
00:36:41,460 --> 00:36:41,990
Да.

767
00:36:41,990 --> 00:36:45,090
Това е глупаво, защото има само един
елемент, но това е абсолютно подредени.

768
00:36:45,090 --> 00:36:46,390
Няма нищо не на място.

769
00:36:46,390 --> 00:36:49,290
Това е по-интересно, този алгоритъм,
когато се премине към следващата стъпка.

770
00:36:49,290 --> 00:36:50,550
>> Сега имам един.

771
00:36:50,550 --> 00:36:55,430
Така един, разбира се, принадлежи в
началото или края на този нов списък?

772
00:36:55,430 --> 00:36:56,360
Началото.

773
00:36:56,360 --> 00:36:58,530
Така че трябва да се направят някои работи сега.

774
00:36:58,530 --> 00:37:01,410
Аз бях като някаква
свободи с моя маркер

775
00:37:01,410 --> 00:37:03,120
само с изготвянето неща
където аз ги искам,

776
00:37:03,120 --> 00:37:05,320
но това не е наистина
точно в компютър.

777
00:37:05,320 --> 00:37:08,530
Компютър, както знаем, има
RAM, или памет с произволен достъп,

778
00:37:08,530 --> 00:37:12,411
и това е един байт и
друг байт и друг байт.

779
00:37:12,411 --> 00:37:14,910
И ако имате гигабайт
RAM, имате един милиард байта,

780
00:37:14,910 --> 00:37:16,680
но те са физически на едно място.

781
00:37:16,680 --> 00:37:19,540
Не може просто да се движат нещата около
от съставянето на дъската

782
00:37:19,540 --> 00:37:20,750
където поискаш.

783
00:37:20,750 --> 00:37:24,090
Така че, ако моят нов списък има
четири точки в паметта,

784
00:37:24,090 --> 00:37:27,480
за съжаление четиримата е
вече на грешното място.

785
00:37:27,480 --> 00:37:30,410
>> Така че, за да въведете номера един
Не мога просто да го направи тук.

786
00:37:30,410 --> 00:37:31,901
Това място в паметта не съществува.

787
00:37:31,901 --> 00:37:35,150
Това би било измама, и аз съм бил
изневерява картинно за няколко минути

788
00:37:35,150 --> 00:37:35,800
тук.

789
00:37:35,800 --> 00:37:40,950
Така че наистина, ако искам да се сложи един тук,
Аз трябва да временно да копирате четиримата

790
00:37:40,950 --> 00:37:43,030
и след това пуснати на един там.

791
00:37:43,030 --> 00:37:45,500
>> Това е добре, това е вярно,
това е технически възможно,

792
00:37:45,500 --> 00:37:48,410
но осъзнават, че това е допълнителна работа.

793
00:37:48,410 --> 00:37:50,460
Аз не съм сложил на броя на мястото.

794
00:37:50,460 --> 00:37:53,026
Аз първо трябваше да се движат по-
номер, след това го постави на място,

795
00:37:53,026 --> 00:37:54,650
така че аз вид удвои ми количество работа.

796
00:37:54,650 --> 00:37:55,660
Така че имайте това предвид.

797
00:37:55,660 --> 00:37:57,120
>> Но аз сега съм направил с този елемент.

798
00:37:57,120 --> 00:37:59,056
Сега искам да вземеш числото три.

799
00:37:59,056 --> 00:38:00,430
Когато, разбира се, няма да принадлежи?

800
00:38:00,430 --> 00:38:01,480
Между.

801
00:38:01,480 --> 00:38:03,650
Не мога да изневеряват повече
и просто да го постави там,

802
00:38:03,650 --> 00:38:06,770
защото, отново, тази памет
е в физически места.

803
00:38:06,770 --> 00:38:10,900
Така че трябва да копирате четиримата
и вкара тройка тук.

804
00:38:10,900 --> 00:38:11,550
Не е голяма работа.

805
00:38:11,550 --> 00:38:14,610
Това е просто една допълнителна стъпка
again-- чувства много евтин.

806
00:38:14,610 --> 00:38:16,445
>> Но сега да преминем към двамата.

807
00:38:16,445 --> 00:38:17,820
Двамата, разбира се, принадлежи тук.

808
00:38:17,820 --> 00:38:20,990
Сега можете да започнете да се види как
работата може да се трупат.

809
00:38:20,990 --> 00:38:23,520
Сега какво трябва да направя?

810
00:38:23,520 --> 00:38:28,570
Да, трябва да се движи на четири,
След това трябва да копирате тримата,

811
00:38:28,570 --> 00:38:31,200
и сега мога да поставите двете.

812
00:38:31,200 --> 00:38:34,460
И уловката с този
алгоритъм, достатъчно интересно,

813
00:38:34,460 --> 00:38:41,050
е, че предполагам, че ние имаме по-екстремен
случай, когато това е да кажем, осем, седем,

814
00:38:41,050 --> 00:38:45,150
шест, пет, четири, три, две, едно.

815
00:38:45,150 --> 00:38:49,450
Това е, в много контексти,
най-лошият сценарий,

816
00:38:49,450 --> 00:38:51,570
защото дяволски нещо
е буквално назад.

817
00:38:51,570 --> 00:38:53,670
>> Не може да кажем,
повлияе алгоритъм на Бен,

818
00:38:53,670 --> 00:38:55,940
защото при избора на Бен
подреди той ще се запази

819
00:38:55,940 --> 00:38:58,359
връщане назад и напред през списъка.

820
00:38:58,359 --> 00:39:01,150
И тъй като той е бил винаги търси
през цялата останала списъка

821
00:39:01,150 --> 00:39:02,858
няма значение
когато елементите са.

822
00:39:02,858 --> 00:39:05,630
Но в този случай с моя вмъкване
approach-- нека се опитаме това.

823
00:39:05,630 --> 00:39:08,616
>> Така че едно, две, три, четири,
пет, шест, седем, осем.

824
00:39:08,616 --> 00:39:11,630
Едно две три четири,
пет, шест, седем, осем.

825
00:39:11,630 --> 00:39:14,320
Отивам да взема осем,
и къде мога да го сложите?

826
00:39:14,320 --> 00:39:17,260
Е, в началото на моя списък,
защото този нов списък е сортиран.

827
00:39:17,260 --> 00:39:18,760
И аз го зачеркнете.

828
00:39:18,760 --> 00:39:20,551
>> Къде да поставя седмината?

829
00:39:20,551 --> 00:39:21,050
Дяволски го.

830
00:39:21,050 --> 00:39:23,174
Тя трябва да отиде там, така че
Аз трябва да се направят някои копиране.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
И сега седемте отива тук.

833
00:39:28,480 --> 00:39:29,860
Сега преминете към шест.

834
00:39:29,860 --> 00:39:30,980
Сега е още повече работа.

835
00:39:30,980 --> 00:39:32,570
>> Осем трябва да отидете тук.

836
00:39:32,570 --> 00:39:33,920
Седем трябва да отидете тук.

837
00:39:33,920 --> 00:39:35,450
Сега шестимата да отидете тук.

838
00:39:35,450 --> 00:39:37,950
Сега вземете пет.

839
00:39:37,950 --> 00:39:40,560
Сега осемте трябва да си отиде
тук, седем трябва да отидете тук,

840
00:39:40,560 --> 00:39:43,650
шест трябва да отидете тук, и
Сега петимата и повторете.

841
00:39:43,650 --> 00:39:46,610
И аз съм доста много
тя се движи постоянно.

842
00:39:46,610 --> 00:39:52,950
>> Така че в края, това algorithm-- ние ще
го наричат ​​вмъкване sort-- всъщност

843
00:39:52,950 --> 00:39:55,020
има много работа, прекалено.

844
00:39:55,020 --> 00:39:56,970
Това е просто различен
вид работа, отколкото на Бен.

845
00:39:56,970 --> 00:40:00,090
работа Бен трябваше да ми става
напред и назад през цялото време,

846
00:40:00,090 --> 00:40:03,510
избиране на следващата по-малка
елемент отново и отново.

847
00:40:03,510 --> 00:40:06,660
Така беше и този много визуален вид работа.

848
00:40:06,660 --> 00:40:10,600
>> Това друг алгоритъм, който е все още
correct-- това ще отида на работа done--

849
00:40:10,600 --> 00:40:12,800
Просто се променя обема на работата.

850
00:40:12,800 --> 00:40:15,420
Тя изглежда като първоначално сте
спестяване, защото ти си просто

851
00:40:15,420 --> 00:40:19,190
занимаващи се с всеки елемент
отпред, без да ходят всички

852
00:40:19,190 --> 00:40:20,930
Между другото през списъка като Бен беше.

853
00:40:20,930 --> 00:40:25,300
Но проблемът е, особено в тези
луди случаите, когато това е всичко назад,

854
00:40:25,300 --> 00:40:27,830
ти си просто вид
отлагане на усилената работа

855
00:40:27,830 --> 00:40:30,360
докато не се наложи да поправите грешките си.

856
00:40:30,360 --> 00:40:33,919
>> И така, ако можете да си представите това
осем и седем и шест и пет

857
00:40:33,919 --> 00:40:36,710
и по-късно четири и три и две
преместване пътя си през списъка,

858
00:40:36,710 --> 00:40:39,060
ние току-що сте променили
тип на работа, което правим.

859
00:40:39,060 --> 00:40:42,340
Вместо да го прави в
началото на моето итерация,

860
00:40:42,340 --> 00:40:45,250
Аз съм просто го прави най-
край на всяка итерация.

861
00:40:45,250 --> 00:40:50,550
Така се оказва, че този алгоритъм,
също, обикновено се нарича поставяне на сортиране,

862
00:40:50,550 --> 00:40:52,190
е от порядъка на N квадрат.

863
00:40:52,190 --> 00:40:56,480
Това всъщност не е по-добре,
няма по-добро на всички.

864
00:40:56,480 --> 00:41:00,810
>> Въпреки това, има и трети подход
Аз ще ни накара да помислят,

865
00:41:00,810 --> 00:41:02,970
който е това.

866
00:41:02,970 --> 00:41:07,850
Така че предполагам, че моят списък, за простота
отново, е четири, едно, три,

867
00:41:07,850 --> 00:41:11,080
two-- само четири числа.

868
00:41:11,080 --> 00:41:13,300
Бен имаше добра интуиция,
добър човешката интуиция

869
00:41:13,300 --> 00:41:16,340
преди, чрез което определено цяло
изброят eventually-- сортиране чрез вмъкване.

870
00:41:16,340 --> 00:41:18,020
Аз ни придума заедно.

871
00:41:18,020 --> 00:41:22,530
Но нека да се разгледа
простият начин за решаване на този списък.

872
00:41:22,530 --> 00:41:24,110
>> Този списък не е сортиран.

873
00:41:24,110 --> 00:41:26,130
Защо?

874
00:41:26,130 --> 00:41:31,920
На английски език, обясни защо
това не е всъщност сортирани.

875
00:41:31,920 --> 00:41:33,400
Какво означава това, не трябва да бъдат подредени?

876
00:41:33,400 --> 00:41:34,220
>> STUDENT: Това не е последователно.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Малан: Не е последователен.

878
00:41:34,990 --> 00:41:35,822
Дайте ми пример.

879
00:41:35,822 --> 00:41:37,180
>> STUDENT: Сложете ги в ред.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Малан: OK.

881
00:41:37,440 --> 00:41:38,790
Дай ми по-конкретен пример.

882
00:41:38,790 --> 00:41:39,832
>> STUDENT: възходящ ред.

883
00:41:39,832 --> 00:41:41,206
DAVID Малан: Не възходящ ред.

884
00:41:41,206 --> 00:41:42,100
Бъдем по-точни.

885
00:41:42,100 --> 00:41:45,190
Аз не знам какво искаш да кажеш с възходящ.

886
00:41:45,190 --> 00:41:47,150
Какво има?

887
00:41:47,150 --> 00:41:49,930
>> STUDENT: най-малката от
номера не е на първо място.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Малан: Най-малък брой на
не на първо място.

889
00:41:51,140 --> 00:41:52,120
Бъдете по-специфичен.

890
00:41:52,120 --> 00:41:55,000
Аз съм се започне да се закачат.

891
00:41:55,000 --> 00:41:59,470
Ние разчитаме, но
това, което е в ред тук?

892
00:41:59,470 --> 00:42:00,707
>> STUDENT: номериране.

893
00:42:00,707 --> 00:42:02,040
DAVID Малан: номериране.

894
00:42:02,040 --> 00:42:04,248
вид водене на всеки човек
тя here-- много високо ниво.

895
00:42:04,248 --> 00:42:07,450
Просто буквално да ми каже какво е
погрешно като пет-годишен мощ.

896
00:42:07,450 --> 00:42:08,310
>> STUDENT: Плюс един.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Малан: Какво е това?

898
00:42:08,750 --> 00:42:09,610
>> STUDENT: Плюс един.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Малан: Какво искаш да кажеш, плюс едно?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Дай ми различен пет-годишен.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Какво не е наред, мамо?

904
00:42:18,330 --> 00:42:19,940
Какво не е наред, татко?

905
00:42:19,940 --> 00:42:22,808
Какво искаш да кажеш това не е сортиран?

906
00:42:22,808 --> 00:42:24,370
>> STUDENT: Това не е на правилното място.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Малан: Какво е
не на мястото си?

908
00:42:25,580 --> 00:42:26,174
>> STUDENT: Four.

909
00:42:26,174 --> 00:42:27,090
DAVID Малан: Добре, добре.

910
00:42:27,090 --> 00:42:29,110
Така че четири не е мястото, където трябва да бъде.

911
00:42:29,110 --> 00:42:30,590
По-специално, е това право?

912
00:42:30,590 --> 00:42:33,000
Четири и един, първият
две числа, които виждам.

913
00:42:33,000 --> 00:42:34,930
Това вярно ли е?

914
00:42:34,930 --> 00:42:36,427
Не, те не са на ред, нали?

915
00:42:36,427 --> 00:42:38,135
Всъщност, мисля, че сега
за компютър, също.

916
00:42:38,135 --> 00:42:40,824
Тя може да гледа само може би един,
може би две неща once--

917
00:42:40,824 --> 00:42:43,240
и всъщност само едно нещо
в даден момент, но може поне

918
00:42:43,240 --> 00:42:45,790
Посетете едно нещо тогавашния на
Следващо нещо, в непосредствена близост до него.

919
00:42:45,790 --> 00:42:47,380
>> Така са тези, с цел?

920
00:42:47,380 --> 00:42:48,032
Разбира се, че не.

921
00:42:48,032 --> 00:42:48,740
Така ли какво?

922
00:42:48,740 --> 00:42:51,020
Защо не вземем бебе
стъпки, определящи този проблем

923
00:42:51,020 --> 00:42:53,410
вместо да правиш тези фантазия
алгоритми като Бен, където

924
00:42:53,410 --> 00:42:56,440
той е нещо като това определяне от
примка през списъка

925
00:42:56,440 --> 00:42:59,670
вместо да правиш това, което направих, когато
Аз просто един вид го фиксира като отидем?

926
00:42:59,670 --> 00:43:03,650
Нека просто буквално съборят
понятие за order-- ред на номерата,

927
00:43:03,650 --> 00:43:06,990
го наричат ​​каквото и да want--
в тези двойки сравнения.

928
00:43:06,990 --> 00:43:07,590
>> Четири и един.

929
00:43:07,590 --> 00:43:09,970
Дали това е правилния ред?

930
00:43:09,970 --> 00:43:11,310
Така че нека да поправи това.

931
00:43:11,310 --> 00:43:14,700
Един и четири, и след това
ние просто ще копира това.

932
00:43:14,700 --> 00:43:15,560
Добре, добре.

933
00:43:15,560 --> 00:43:17,022
Оправих едно и четири.

934
00:43:17,022 --> 00:43:18,320
Три и две?

935
00:43:18,320 --> 00:43:18,820
Не.

936
00:43:18,820 --> 00:43:21,690
Нека думите ми съвпадат пръстите ми.

937
00:43:21,690 --> 00:43:23,695
Четири и три?

938
00:43:23,695 --> 00:43:27,930
>> Това не е в ред, така че аз ще
да се направи един, три, четири, две.

939
00:43:27,930 --> 00:43:28,680
Добре.

940
00:43:28,680 --> 00:43:32,310
Сега четири и две?

941
00:43:32,310 --> 00:43:33,370
Ние трябва да се определи това, също.

942
00:43:33,370 --> 00:43:36,700
Така един, три, две, четири.

943
00:43:36,700 --> 00:43:39,820
Така е то подредени?

944
00:43:39,820 --> 00:43:43,170
Не, но е по-близо до сортирани?

945
00:43:43,170 --> 00:43:48,930
>> Това е, защото тази фиксирана
грешка, ние фиксирана тази грешка,

946
00:43:48,930 --> 00:43:50,370
и ние фиксирана тази грешка.

947
00:43:50,370 --> 00:43:52,420
Така че ние фиксирана три грешки безспорно.

948
00:43:52,420 --> 00:43:58,100
Все още не е наистина изглежда сортиран, но
е обективно по-близо до сортиран

949
00:43:58,100 --> 00:44:00,080
защото фиксирана някои от тези грешки.

950
00:44:00,080 --> 00:44:02,047
>> Сега какво да правя след това?

951
00:44:02,047 --> 00:44:03,630
I вид достигнал края на списъка.

952
00:44:03,630 --> 00:44:05,680
Аз като че ли са фиксирани
всички грешки, но не.

953
00:44:05,680 --> 00:44:08,510
Тъй като в този случай, някои цифри
може да са на мехурчета по-близо

954
00:44:08,510 --> 00:44:10,410
към други номера, които
все още са в ред.

955
00:44:10,410 --> 00:44:12,951
Така че нека да го направя отново, и аз ще
просто го направи на място този път.

956
00:44:12,951 --> 00:44:14,170
Един и три?

957
00:44:14,170 --> 00:44:14,720
Всичко е наред.

958
00:44:14,720 --> 00:44:16,070
Три и две?

959
00:44:16,070 --> 00:44:17,560
Разбира се, не, така че нека да промени това.

960
00:44:17,560 --> 00:44:19,160
Така две, три.

961
00:44:19,160 --> 00:44:21,340
Три и четири?

962
00:44:21,340 --> 00:44:24,370
А сега нека просто да бъде
особено педантичен тук.

963
00:44:24,370 --> 00:44:26,350
Е то подредени?

964
00:44:26,350 --> 00:44:29,280
Вие хора знаят, че е сортиран.

965
00:44:29,280 --> 00:44:30,400
>> Аз трябва да се опита отново.

966
00:44:30,400 --> 00:44:31,900
Така че Оливия предлага опитам отново.

967
00:44:31,900 --> 00:44:32,530
Защо?

968
00:44:32,530 --> 00:44:35,810
Защото един компютър няма
лукса на нашите човешки очи

969
00:44:35,810 --> 00:44:38,080
на само поглеждайки back-- ОК, аз съм направил.

970
00:44:38,080 --> 00:44:41,610
Как компютърът определи
че списъкът сега се сортира?

971
00:44:41,610 --> 00:44:44,590
Механично.

972
00:44:44,590 --> 00:44:47,650
>> Аз трябва да мине през
още веднъж, и то само ако съм

973
00:44:47,650 --> 00:44:51,190
не правят / намери грешки мога
След това се заключи, както на компютъра, да,

974
00:44:51,190 --> 00:44:51,980
ние сме добре да тръгвам.

975
00:44:51,980 --> 00:44:54,850
Така че едно и две, две и
три, три и четири.

976
00:44:54,850 --> 00:44:58,030
Сега мога да кажа категорично това е
подредени, защото съм направил никакви промени.

977
00:44:58,030 --> 00:45:01,940
Сега би било грешка и просто
глупави, ако аз, компютъра,

978
00:45:01,940 --> 00:45:05,640
попита същите тези въпроси отново
очакваш различни отговори.

979
00:45:05,640 --> 00:45:07,110
Не трябва да се случи.

980
00:45:07,110 --> 00:45:08,600
>> И така, сега списъкът се сортира.

981
00:45:08,600 --> 00:45:12,630
За съжаление, времето за работа на
този алгоритъм е също N квадрат.

982
00:45:12,630 --> 00:45:13,130
Защо?

983
00:45:13,130 --> 00:45:19,520
Защото имате н номера, и в
най-лошия случай ще трябва да се движат н номера

984
00:45:19,520 --> 00:45:23,637
N пъти, защото трябва да продължи да функционира
обратно да се провери и евентуално да определи

985
00:45:23,637 --> 00:45:24,220
тези номера.

986
00:45:24,220 --> 00:45:26,280
И ние можем да направим повече
формален анализ, също.

987
00:45:26,280 --> 00:45:29,530
>> Така че всичко това е да се каже, ние сме направили
три различни подхода, един

988
00:45:29,530 --> 00:45:32,210
от тях веднага интуитивно
разстояние бухалката от Бен

989
00:45:32,210 --> 00:45:35,170
с предложените ми вмъкване
сортиране на тази една

990
00:45:35,170 --> 00:45:38,540
където можете вид губи от поглед
гората за дърветата в началото.

991
00:45:38,540 --> 00:45:41,760
Но след това, ако се върнем назад,
готово, ние сме фиксирани за сортиране понятието.

992
00:45:41,760 --> 00:45:43,824
Така че това е, смея да кажа,
по-ниско ниво може би

993
00:45:43,824 --> 00:45:45,740
от някои от тези други
алгоритми, но нека

994
00:45:45,740 --> 00:45:48,550
да видим дали не можем да се визуализира
тези чрез това.

995
00:45:48,550 --> 00:45:51,450
>> Така че това е някой хубав
софтуер, който някой

996
00:45:51,450 --> 00:45:56,110
пише с помощта на цветни ленти, които е
Ще направя следното за нас.

997
00:45:56,110 --> 00:45:57,736
Всеки един от тези барове представлява номер.

998
00:45:57,736 --> 00:46:00,026
Taller бара, толкова по-голям
броя, по-малък от гредата,

999
00:46:00,026 --> 00:46:00,990
толкова по-малък номер.

1000
00:46:00,990 --> 00:46:05,880
Така че в идеалния случай ние искаме хубава пирамида
където тя започва малък и получава голяма,

1001
00:46:05,880 --> 00:46:08,330
и това би означавало, че
тези барове са сортирани.

1002
00:46:08,330 --> 00:46:11,200
Така че аз ще отида напред и да изберете,
например, алгоритъм на Бен

1003
00:46:11,200 --> 00:46:13,990
first-- избор на сортиране.

1004
00:46:13,990 --> 00:46:16,220
>> И забележи това, което прави.

1005
00:46:16,220 --> 00:46:18,670
Начинът, по който те са избрали да
визуализира този алгоритъм

1006
00:46:18,670 --> 00:46:22,090
е, че, точно както бях
ходене през моя списък,

1007
00:46:22,090 --> 00:46:24,710
тази програма е ходене
чрез своя списък с номера,

1008
00:46:24,710 --> 00:46:28,160
подчертаване на всеки розов
номер, който го търси при.

1009
00:46:28,160 --> 00:46:32,360
И това, което е на път да се случи точно сега?

1010
00:46:32,360 --> 00:46:35,154
>> Най-малкият брой че
I или Бен намери изведнъж

1011
00:46:35,154 --> 00:46:36,820
получава се премества в началото на списъка.

1012
00:46:36,820 --> 00:46:40,037
И забележи те направиха изгони
номера, който беше там,

1013
00:46:40,037 --> 00:46:41,120
и това е съвършено глоба.

1014
00:46:41,120 --> 00:46:42,600
Аз не се получи в това ниво на детайлност.

1015
00:46:42,600 --> 00:46:44,308
Но ние трябва да се постави
този номер някъде,

1016
00:46:44,308 --> 00:46:47,775
така че ние просто го премества в
отворено място, че е бил създаден.

1017
00:46:47,775 --> 00:46:49,900
Така че аз отивам да се ускори този
нагоре, защото в противен случай

1018
00:46:49,900 --> 00:46:51,871
става много досадно бързо.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Анимация speed-- там отиваме.

1021
00:46:58,600 --> 00:47:01,850
Така че сега същия принцип
Аз се прилагат, но ви

1022
00:47:01,850 --> 00:47:06,540
може да започнете да се чувствате по алгоритъм, ако
ще, или да го видите малко по-ясно.

1023
00:47:06,540 --> 00:47:13,190
И този алгоритъм има ефекта на
избиране на следващата по-малка елемент,

1024
00:47:13,190 --> 00:47:16,422
така че ще започнем да
виж го повиши в ляво.

1025
00:47:16,422 --> 00:47:19,130
И на всяка итерация, както аз
предложен, го прави по-малко работа.

1026
00:47:19,130 --> 00:47:21,921
То не трябва да отидем по целия път
обратно към левия край на списъка,

1027
00:47:21,921 --> 00:47:23,900
защото вече
знае тези са подредени.

1028
00:47:23,900 --> 00:47:28,129
Така че това нещо се чувства като това е
ускоряване, въпреки че всяка стъпка е

1029
00:47:28,129 --> 00:47:29,420
довеждайки същия период от време.

1030
00:47:29,420 --> 00:47:31,600
Има само малко стъпки останалите.

1031
00:47:31,600 --> 00:47:35,240
А сега можете да вид усещане за
алгоритъм почистване в края на това,

1032
00:47:35,240 --> 00:47:37,040
и наистина сега се сортират.

1033
00:47:37,040 --> 00:47:41,620
>> Така сортиране чрез вмъкване е всичко направено.

1034
00:47:41,620 --> 00:47:43,600
Аз трябва отново случайност масива.

1035
00:47:43,600 --> 00:47:45,940
И забележи, че мога просто
да го рандомизиране,

1036
00:47:45,940 --> 00:47:50,630
и ние ще се сближаване на
същия подход, сортиране чрез вмъкване.

1037
00:47:50,630 --> 00:47:55,050
Нека да го забави до тук.

1038
00:47:55,050 --> 00:47:56,915
Нека започнем, че свърши.

1039
00:47:56,915 --> 00:47:57,414
Спри се.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Нека да пропусне четири.

1042
00:48:02,410 --> 00:48:03,200
Ето.

1043
00:48:03,200 --> 00:48:04,190
Случаен те масив.

1044
00:48:04,190 --> 00:48:05,555
И тук ние go-- сортиране чрез вмъкване.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Играя.

1047
00:48:12,800 --> 00:48:17,280
Забележете, че това е работа с всеки
елемент, който срещне веднага,

1048
00:48:17,280 --> 00:48:20,282
но ако тя принадлежи в
обявлението за грешното място

1049
00:48:20,282 --> 00:48:21,740
всички от работата, която трябва да се случи.

1050
00:48:21,740 --> 00:48:24,700
Ние трябва да продължим да измества повече
и повече елементи, за да направи място

1051
00:48:24,700 --> 00:48:27,340
за този, който искаме да се въведе.

1052
00:48:27,340 --> 00:48:30,740
>> Така че ние сме с акцент върху
левия край на само на списъка.

1053
00:48:30,740 --> 00:48:34,460
Забележете, ние дори не са изглеждали at-- ние
не са подчертани в розово нещо

1054
00:48:34,460 --> 00:48:35,610
надясно.

1055
00:48:35,610 --> 00:48:38,180
Ние просто се занимават с
проблемите, както и да отидем,

1056
00:48:38,180 --> 00:48:40,430
но ние създаваме много
работят за себе си все още.

1057
00:48:40,430 --> 00:48:44,410
И така, ако ние се ускори този нагоре
Сега, за да преминете към приключване,

1058
00:48:44,410 --> 00:48:46,210
тя има различно усещане за това, наистина.

1059
00:48:46,210 --> 00:48:50,150
Това е просто фокусира върху левия край, но
това малко повече работа, като needed--

1060
00:48:50,150 --> 00:48:53,230
вид изглаждане неща
над, фиксиране неща,

1061
00:48:53,230 --> 00:48:58,350
но се занимават в крайна сметка с
всеки елемент по една

1062
00:48:58,350 --> 00:49:07,740
докато стигнем до the-- добре, ние
Всички знаем как това ще свърши,

1063
00:49:07,740 --> 00:49:09,700
така че е малко underwhelming може би.

1064
00:49:09,700 --> 00:49:12,830
>> Но списъка в end--
spoiler-- ще бъдат сортирани.

1065
00:49:12,830 --> 00:49:15,300
Така че нека да разгледаме един последен един.

1066
00:49:15,300 --> 00:49:16,840
Не можем просто да пропуснете сега.

1067
00:49:16,840 --> 00:49:18,000
Ние сме почти там.

1068
00:49:18,000 --> 00:49:19,980
Двама да отида, един да отиде.

1069
00:49:19,980 --> 00:49:22,680
И готово.

1070
00:49:22,680 --> 00:49:23,450
Отличен.

1071
00:49:23,450 --> 00:49:27,220
>> Така че сега нека да направим един последен един,
отново рандомизиране с балон подреди.

1072
00:49:27,220 --> 00:49:31,690
И забележи тук, особено ако тя се забави
надолу, това не пази спуска през.

1073
00:49:31,690 --> 00:49:36,830
Но забележете, че просто прави по двойки
comparisons-- сортиране на решения на местно ниво.

1074
00:49:36,830 --> 00:49:39,050
Но веднага след като стигнем до
В края на списъка в розово,

1075
00:49:39,050 --> 00:49:40,690
какво ще се наложи да се случи отново?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Да, той ще трябва да се
започнем отначало, защото тя само

1078
00:49:46,830 --> 00:49:49,870
фиксирани двойки грешки.

1079
00:49:49,870 --> 00:49:53,120
И това може да разкрива още други.

1080
00:49:53,120 --> 00:49:58,950
И така, ако ускоряването на този процес, ще
виждаме, че, колкото подсказва името,

1081
00:49:58,950 --> 00:50:01,870
по-малката elements-- или по-скоро,
по-големите elements-- започват

1082
00:50:01,870 --> 00:50:03,740
да се балон до върха, ако щете.

1083
00:50:03,740 --> 00:50:07,380
И по-малки елементи са
като се започне да се балон надолу в ляво.

1084
00:50:07,380 --> 00:50:10,780
И наистина, това е вид
визуален ефект, както добре.

1085
00:50:10,780 --> 00:50:17,150
И така, това в крайна сметка ще завърши
по много подобен начин, твърде.

1086
00:50:17,150 --> 00:50:19,160
>> Ние не трябва да се живее
на този един.

1087
00:50:19,160 --> 00:50:21,010
Нека да се отвори тази сега, твърде.

1088
00:50:21,010 --> 00:50:24,040
Има няколко други алгоритми за сортиране
в света, някои от които

1089
00:50:24,040 --> 00:50:25,580
се включват тук.

1090
00:50:25,580 --> 00:50:29,960
И най-вече за учащи, които не са
непременно визуален или математически,

1091
00:50:29,960 --> 00:50:31,930
както направихме преди, можем
също така да направите това audially

1092
00:50:31,930 --> 00:50:34,210
ако ние свързваме звук с това.

1093
00:50:34,210 --> 00:50:36,990
И просто за забавление, тук е
няколко различни алгоритми,

1094
00:50:36,990 --> 00:50:40,950
и един от тях по-специално, че сте
Ще забележите, се нарича "сортиране чрез сливане."

1095
00:50:40,950 --> 00:50:43,250
>> Всъщност, това е фундаментално
по-добре алгоритъм,

1096
00:50:43,250 --> 00:50:45,860
такава, че сортиране чрез сливане, един от
тези, които сте на път да се види,

1097
00:50:45,860 --> 00:50:49,170
не е цел на п квадрат.

1098
00:50:49,170 --> 00:50:57,280
Това е от порядъка на N пъти вляза на
N, който всъщност е по-малка и по този начин

1099
00:50:57,280 --> 00:50:58,940
по-бързо от другите три.

1100
00:50:58,940 --> 00:51:00,670
А има и няколко други
глупави хора, които ще видим.

1101
00:51:00,670 --> 00:51:01,933
>> Така че тук ние отивам с някакъв звук.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Това е вмъкване на сортиране, така че отново
това е просто работа с елементите

1104
00:51:10,490 --> 00:51:13,420
тъй като те идват.

1105
00:51:13,420 --> 00:51:17,180
Това е метод на мехурчето, така че е
разглеждането им двойки в даден момент.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
И отново, най-големите елементи
се надига към върха.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Следващият избор на сортиране.

1110
00:51:41,710 --> 00:51:45,420
Това е алгоритъм Бен, където
отново той е избор на итеративно

1111
00:51:45,420 --> 00:51:46,843
следващата по-малка елемент.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
И отново, сега наистина може да чуете, че
това е ускоряване но само дотолкова, доколкото

1114
00:51:53,900 --> 00:51:58,230
като го прави по-малко и по-малко
работят на всяка итерация.

1115
00:51:58,230 --> 00:52:04,170
Това е по-бързо този, сортиране чрез сливане,
който е сортиране клъстери на номера

1116
00:52:04,170 --> 00:52:05,971
заедно и след това ги обединява.

1117
00:52:05,971 --> 00:52:07,720
Така look-- ляво
половината вече е сортиран.

1118
00:52:07,720 --> 00:52:14,165
>> Сега е сортиране на дясната половина, и
Сега то се случва да ги комбинира в едно.

1119
00:52:14,165 --> 00:52:19,160
Това е нещо, наречено "Gnome сортиране."

1120
00:52:19,160 --> 00:52:23,460
И вие можете да вид се види, че
то се случва напред и назад,

1121
00:52:23,460 --> 00:52:27,950
определяне работа малко тук и
там, преди да пристъпи към нова работа.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
И това е.

1124
00:52:33,692 --> 00:52:36,400
Има друг вид, който е
наистина само за академични цели,

1125
00:52:36,400 --> 00:52:40,980
наречен "глупав сортиране," който взема
Вашите данни, сортира на случаен принцип,

1126
00:52:40,980 --> 00:52:43,350
и след това се проверява дали е сортирани.

1127
00:52:43,350 --> 00:52:47,880
И ако това не е, то отново сортира го
на случаен принцип, проверява дали е сортирана,

1128
00:52:47,880 --> 00:52:49,440
и ако не се повтаря.

1129
00:52:49,440 --> 00:52:52,660
И на теория, вероятностно
това ще завърши,

1130
00:52:52,660 --> 00:52:54,140
но след доста време.

1131
00:52:54,140 --> 00:52:56,930
Това не е най-
ефективно на алгоритми.

1132
00:52:56,930 --> 00:53:02,550
Така че всяка интересува за тези,
конкретните алгоритми или нищо

1133
00:53:02,550 --> 00:53:04,720
свързани там, прекалено?

1134
00:53:04,720 --> 00:53:09,430
>> Е, нека сега дразни, освен това, което всички
тези линии са, че съм бил рисуване

1135
00:53:09,430 --> 00:53:15,090
и това, което аз съм се предположи компютъра
може да се направи под предния капак.

1136
00:53:15,090 --> 00:53:18,650
Бих казал, че всички тези номера
Държа drawing-- те се нуждаят, за да получите

1137
00:53:18,650 --> 00:53:21,330
съхраняват някъде в паметта.

1138
00:53:21,330 --> 00:53:24,130
Ние ще се отървете от този човек сега, твърде.

1139
00:53:24,130 --> 00:53:30,110
>> Така че едно парче на памет в
computer-- толкова RAM DIMM е

1140
00:53:30,110 --> 00:53:35,480
това, което търсихме вчера, двойна
инлайн памет module-- изглежда по този начин.

1141
00:53:35,480 --> 00:53:39,370
И всеки един от тези малки черни чипове
някои брой байтове, обикновено.

1142
00:53:39,370 --> 00:53:44,380
И тогава златните игли са подобни на
кабели, които го свързват с компютъра,

1143
00:53:44,380 --> 00:53:47,521
и зелен силициев борда е просто
това, което държи всичко заедно.

1144
00:53:47,521 --> 00:53:48,770
Е, какво значи това наистина означава?

1145
00:53:48,770 --> 00:53:53,180
Ако аз вид привлече същия тази картина,
да предположим за простота

1146
00:53:53,180 --> 00:53:55,280
че това DIMM, двойна
инлайн модул с памет,

1147
00:53:55,280 --> 00:54:00,530
е един гигабайт RAM, един гигабайт
памет, която е колко общо байта?

1148
00:54:00,530 --> 00:54:02,100
Един гигабайт е колко байта?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Повече от това.

1151
00:54:06,030 --> 00:54:09,960
1124 е килограм, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega е милион.

1153
00:54:11,730 --> 00:54:14,570
Giga е един милиард.

1154
00:54:14,570 --> 00:54:15,070
>> Am I лъже?

1155
00:54:15,070 --> 00:54:16,670
Можем дори да чете етикета?

1156
00:54:16,670 --> 00:54:19,920
Това е всъщност 128
гигабайта, така че е повече.

1157
00:54:19,920 --> 00:54:22,130
Но ние ще се преструвам, този
е само един гигабайт.

1158
00:54:22,130 --> 00:54:25,640
Така че това означава, че има един милиард
байта памет на разположение за мен

1159
00:54:25,640 --> 00:54:29,770
или 8 милиарда бита, но ние отиваме
да говоря от гледна точка на байта сега,

1160
00:54:29,770 --> 00:54:30,750
движа се напред.

1161
00:54:30,750 --> 00:54:36,330
>> И така, какво означава това е, това е
един байт, това е един байт,

1162
00:54:36,330 --> 00:54:38,680
това е друг байт,
и ако ние наистина искахме

1163
00:54:38,680 --> 00:54:43,280
да бъдат конкретни, ние ще трябва да
изготвят един милиард малките квадрати.

1164
00:54:43,280 --> 00:54:44,320
Но какво означава това?

1165
00:54:44,320 --> 00:54:46,420
Е, нека просто да я увеличите
в тази картина.

1166
00:54:46,420 --> 00:54:50,900
Ако имам нещо, което изглежда
като този сега, това е четири байта.

1167
00:54:50,900 --> 00:54:53,710
>> И така, аз може да постави четири номера тук.

1168
00:54:53,710 --> 00:54:54,990
Едно две три четири.

1169
00:54:54,990 --> 00:55:00,170
Или мога да сложи четири букви или символи.

1170
00:55:00,170 --> 00:55:02,620
"Хей!" може да отиде точно там,
тъй като всяка от буквите,

1171
00:55:02,620 --> 00:55:04,370
ние обсъдихме по-рано,
могат да бъдат представени

1172
00:55:04,370 --> 00:55:06,650
с осем бита или ASCII или един байт.

1173
00:55:06,650 --> 00:55:09,370
Така че, с други думи, можете да
сложи 8 милиарда неща вътре

1174
00:55:09,370 --> 00:55:11,137
на този един стик на паметта.

1175
00:55:11,137 --> 00:55:14,345
Сега какво означава да постави нещата назад
за да се върна обратно в паметта като този?

1176
00:55:14,345 --> 00:55:17,330
Това е, което един програмист
ще се обади на "масив."

1177
00:55:17,330 --> 00:55:21,250
В една компютърна програма, вие не мислите
за основния хардуер, само по себе си.

1178
00:55:21,250 --> 00:55:24,427
Просто мисля за себе си като имащи
достъп до общия един милиард байта,

1179
00:55:24,427 --> 00:55:26,010
и можете да всичко, което искате с него.

1180
00:55:26,010 --> 00:55:27,880
Но за удобство
това е обикновено полезно

1181
00:55:27,880 --> 00:55:31,202
да си прав памет
един до друг по този начин.

1182
00:55:31,202 --> 00:55:33,660
Така че, ако аз се фокусирам върху this--
защото ние със сигурност няма да ходиш

1183
00:55:33,660 --> 00:55:39,310
да се направи един милиард малки squares--
да предположим, че този съвет представлява

1184
00:55:39,310 --> 00:55:40,610
че стик памет сега.

1185
00:55:40,610 --> 00:55:43,800
И аз просто ще направи толкова, колкото ми
маркер завършва давайки ми тук.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Така че сега ние имаме една пръчка
на паметта на дъската

1188
00:55:52,300 --> 00:55:56,400
че има един, два, три, четири, пет,
шест, едно, две, три, четири, пет, шест,

1189
00:55:56,400 --> 00:56:01,130
seven-- така 42 байта
памет общия брой на екран.

1190
00:56:01,130 --> 00:56:01,630
Благодаря.

1191
00:56:01,630 --> 00:56:02,838
Да, направих моя аритметика полето.

1192
00:56:02,838 --> 00:56:05,120
Така 42 байта памет тук.

1193
00:56:05,120 --> 00:56:06,660
И така, какво означава това всъщност означава?

1194
00:56:06,660 --> 00:56:09,830
Е, компютърен програмист
всъщност ще обикновено

1195
00:56:09,830 --> 00:56:12,450
мисля, че на тази памет като адресат.

1196
00:56:12,450 --> 00:56:16,630
С други думи, всеки един от тях
местоположения в паметта, в хардуер,

1197
00:56:16,630 --> 00:56:18,030
има уникален адрес.

1198
00:56:18,030 --> 00:56:22,020
>> Това не е толкова сложна, колкото Един Братъл
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Вместо това, той е просто един номер.

1200
00:56:23,830 --> 00:56:27,930
Това е байт номер нула, това е
един, това е два, е три,

1201
00:56:27,930 --> 00:56:30,327
и това е 41.

1202
00:56:30,327 --> 00:56:30,910
Чакай малко.

1203
00:56:30,910 --> 00:56:32,510
Мислех, че каза 42 преди малко.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Започнах да броим на нула,
така че това е всъщност правилна.

1206
00:56:37,772 --> 00:56:40,980
Сега ние не трябва да всъщност го направи
като решетка, и ако го направи като решетка

1207
00:56:40,980 --> 00:56:43,520
Мисля, че нещата в действителност
получите малко подвеждащо.

1208
00:56:43,520 --> 00:56:46,650
Какво програмист би,
в собствената си ум,

1209
00:56:46,650 --> 00:56:50,310
като цяло мисля, че на този
памет, както е точно като на лента,

1210
00:56:50,310 --> 00:56:53,340
като парче хартиено тиксо
че просто продължава и върху завинаги

1211
00:56:53,340 --> 00:56:54,980
или докато не изтече на паметта.

1212
00:56:54,980 --> 00:56:59,200
Така че по-общ начин да се привлече
и просто мисля за памет

1213
00:56:59,200 --> 00:57:03,710
ще бъде, че това е байт нула, едно,
две, три, а след това с точка, точка, точка.

1214
00:57:03,710 --> 00:57:07,650
И вие имате общо 42 такива байта, дори
въпреки че физически той може в действителност

1215
00:57:07,650 --> 00:57:09,480
да е нещо по-така.

1216
00:57:09,480 --> 00:57:12,850
>> Така че, ако сега мислите за вашия
памет, тъй като това, точно като на лента,

1217
00:57:12,850 --> 00:57:17,640
това е, което един програмист отново
ще се обади масив от паметта.

1218
00:57:17,640 --> 00:57:20,660
А когато искате да всъщност се съхранява
нещо в паметта на компютъра,

1219
00:57:20,660 --> 00:57:23,290
Вие обикновено се съхранява неща
гръб с гръб до гръб до гръб.

1220
00:57:23,290 --> 00:57:25,010
Така че ние сме били говорим за цифри.

1221
00:57:25,010 --> 00:57:30,880
И когато аз исках да реши проблемите
като четири, едно, три, две,

1222
00:57:30,880 --> 00:57:33,820
въпреки че аз бях просто рисунка
само четирите номера, едно, три,

1223
00:57:33,820 --> 00:57:39,490
две на дъската, на компютъра, ще
наистина имат тази настройка в паметта.

1224
00:57:39,490 --> 00:57:43,347
>> И какво ще бъде следващото към
две в паметта на компютъра?

1225
00:57:43,347 --> 00:57:44,680
Е, няма отговор на това.

1226
00:57:44,680 --> 00:57:45,770
Ние наистина не знам.

1227
00:57:45,770 --> 00:57:48,200
И така, докато
компютър няма нужда от нея,

1228
00:57:48,200 --> 00:57:51,440
тя не трябва да се интересува какво е следващата
на номерата за да го е грижа за.

1229
00:57:51,440 --> 00:57:55,130
И когато казах по-рано, че един компютър
може да гледа само един адрес в даден момент,

1230
00:57:55,130 --> 00:57:56,170
това е вид защо.

1231
00:57:56,170 --> 00:57:59,490
>> Не е за разлика от рекордните
плейър и четяща глава,

1232
00:57:59,490 --> 00:58:03,030
само е в състояние да погледнем в определен
бразда във физическа рекорд от старата школа

1233
00:58:03,030 --> 00:58:06,500
по време, подобно
може един компютър благодарение

1234
00:58:06,500 --> 00:58:09,810
да му CPU и неговото
Intel набор инструкции,

1235
00:58:09,810 --> 00:58:12,480
сред чиито инструкция
се чете от паметта

1236
00:58:12,480 --> 00:58:15,590
или запишете на memory-- на
компютър може да изглежда само

1237
00:58:15,590 --> 00:58:19,210
на едно място в time--
понякога комбинация от тях,

1238
00:58:19,210 --> 00:58:21,770
но наистина само едно място в даден момент.

1239
00:58:21,770 --> 00:58:24,770
Така че, когато ние правехме
тези различни алгоритми,

1240
00:58:24,770 --> 00:58:28,110
Аз не съм просто писане в
vacuum-- четири, едно, три, две.

1241
00:58:28,110 --> 00:58:30,849
Тези числа всъщност принадлежат
някъде физическа памет.

1242
00:58:30,849 --> 00:58:32,890
Така че има мъничък
транзистори или някакъв вид

1243
00:58:32,890 --> 00:58:35,840
на електрониката под
качулка съхраняване на тези стойности.

1244
00:58:35,840 --> 00:58:40,460
>> И в общия, колко бита са
замесен в момента, само за да бъде ясно?

1245
00:58:40,460 --> 00:58:45,580
Така че това е четири байта, или
Сега тя е 32 бита общо.

1246
00:58:45,580 --> 00:58:49,280
Така че там са всъщност 32 нули и
такива, съставящи тези четири неща.

1247
00:58:49,280 --> 00:58:52,070
Има дори още тук, но
отново не ни пука за това.

1248
00:58:52,070 --> 00:58:55,120
>> Така че сега нека да поиска от друга
въпрос с помощта на паметта,

1249
00:58:55,120 --> 00:58:57,519
защото в края
на деня е в противоречие.

1250
00:58:57,519 --> 00:59:00,310
Без значение какво можем да направим с
компютъра, в края на деня

1251
00:59:00,310 --> 00:59:02,560
хардуерът е все още на
същото под предния капак.

1252
00:59:02,560 --> 00:59:04,670
Как бих се съхранява дума тук?

1253
00:59:04,670 --> 00:59:09,710
Е, една дума на един компютър като
"Хей!" ще се съхраняват само по този начин.

1254
00:59:09,710 --> 00:59:12,300
И ако искате по-дълго
дума, можете просто

1255
00:59:12,300 --> 00:59:19,120
презаписване, че и да кажа нещо
като "здравей" и магазин, който тук.

1256
00:59:19,120 --> 00:59:23,930
>> И така, тук също, това contiguousness
всъщност е предимство,

1257
00:59:23,930 --> 00:59:26,530
защото един компютър може просто
чете от дясно на ляво.

1258
00:59:26,530 --> 00:59:28,680
Но тук е въпрос.

1259
00:59:28,680 --> 00:59:33,480
В контекста на тази дума,
з-д-л-л-о, удивителен знак,

1260
00:59:33,480 --> 00:59:38,740
как може компютърът знае къде е
Думата започва и където думата завършва?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
В контекста на номера,
как компютъра

1263
00:59:43,800 --> 00:59:48,396
знам колко дълго последователността на
номера е или където тя започва?

1264
00:59:48,396 --> 00:59:50,270
Е, оказва out--
и ние няма да отидат твърде много

1265
00:59:50,270 --> 00:59:54,970
в това ниво на detail--
компютри се движат нещата около в памет

1266
00:59:54,970 --> 00:59:57,800
буквално по пътя на тези адреси.

1267
00:59:57,800 --> 01:00:02,080
Така че в един компютър, ако сте
писането код за съхраняване на неща

1268
01:00:02,080 --> 01:00:05,800
като думи, това, което сте
наистина прави пише

1269
01:00:05,800 --> 01:00:11,320
изрази, които си спомнят, където в
памет на компютъра тези думи са.

1270
01:00:11,320 --> 01:00:14,370
Така че нека да се направи много,
много прост пример.

1271
01:00:14,370 --> 01:00:18,260
>> Отивам да се продължи напред и
отвори една проста програма, текст,

1272
01:00:18,260 --> 01:00:20,330
и аз отивам да се създаде
файл, наречен hello.c.

1273
01:00:20,330 --> 01:00:22,849
Повечето от тази информация ние
Няма да навлизам в по-големи подробности,

1274
01:00:22,849 --> 01:00:25,140
но аз ще напише
програма в същия този език,

1275
01:00:25,140 --> 01:00:31,140
C. Това е далеч по-смущаваща,
Бих казал, отколкото Scratch,

1276
01:00:31,140 --> 01:00:32,490
но това е много подобен по дух.

1277
01:00:32,490 --> 01:00:34,364
В действителност, тези къдрава
braces-- можете вид

1278
01:00:34,364 --> 01:00:37,820
мисля за това, което току-що е направил, тъй като това.

1279
01:00:37,820 --> 01:00:39,240
>> Нека да направим това, всъщност.

1280
01:00:39,240 --> 01:00:45,100
Когато зелен флаг кликнали,
направете следното.

1281
01:00:45,100 --> 01:00:50,210
Искам да отпечатате "здравей".

1282
01:00:50,210 --> 01:00:51,500
Така че сега това е Псевдокод.

1283
01:00:51,500 --> 01:00:53,000
Аз съм нещо като замъгляване на линиите.

1284
01:00:53,000 --> 01:00:56,750
В C, този език говоря
за тази линия печат здравей

1285
01:00:56,750 --> 01:01:01,940
всъщност става "ФОРМАТ" с
някои скоби и точка и запетая.

1286
01:01:01,940 --> 01:01:03,480
>> Но това е точно същата идея.

1287
01:01:03,480 --> 01:01:06,730
И това много лесен за употреба
"Когато зелен флаг кликнали" става

1288
01:01:06,730 --> 01:01:10,182
на много по-тайнствена "INT главната празнотата."

1289
01:01:10,182 --> 01:01:12,890
И това наистина не е картографиране,
така че аз съм просто ще игнорира това.

1290
01:01:12,890 --> 01:01:17,210
Но фигурните скоби са подобни на
извити пъзел парчета, като това.

1291
01:01:17,210 --> 01:01:18,700
>> Така че можете да вид предполагам.

1292
01:01:18,700 --> 01:01:22,357
Дори ако никога не сте програмирани преди,
какво прави тази програма вероятно правя?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Вероятно отпечатва здравей
с удивителен знак.

1295
01:01:28,000 --> 01:01:29,150
>> Така че нека се опитаме това.

1296
01:01:29,150 --> 01:01:30,800
Отивам да го спаси.

1297
01:01:30,800 --> 01:01:34,000
И това е, отново, много
стара училищна среда.

1298
01:01:34,000 --> 01:01:35,420
Не мога да кликнете, аз не мога да плъзнете.

1299
01:01:35,420 --> 01:01:36,910
Трябва да въведете команди.

1300
01:01:36,910 --> 01:01:41,320
Така че аз искам да тече моята програма, така че
Аз може да направи това, като hello.c.

1301
01:01:41,320 --> 01:01:42,292
Това е файла, който изтича.

1302
01:01:42,292 --> 01:01:43,500
Но чакайте, аз съм липсва една стъпка.

1303
01:01:43,500 --> 01:01:46,470
Какво направихме ние казваме, е необходимо
стъпка за език като C?

1304
01:01:46,470 --> 01:01:49,470
Току-що написан източник
код, но това, което ми е необходимо?

1305
01:01:49,470 --> 01:01:50,670
Да, имам нужда от компилатор.

1306
01:01:50,670 --> 01:01:57,670
Така че на моя Mac тук, имам
програма, наречена GCC, GNU C компилатор,

1307
01:01:57,670 --> 01:02:03,990
което ми позволява да правя this-- завой
ми изходния код в, ние ще го наричаме,

1308
01:02:03,990 --> 01:02:04,930
машинен код.

1309
01:02:04,930 --> 01:02:10,180
>> И мога да видя, че,
Отново, както следва, тези

1310
01:02:10,180 --> 01:02:14,090
са нули и тези, които аз просто
създаден от моя изходния код,

1311
01:02:14,090 --> 01:02:15,730
всички нули и единици.

1312
01:02:15,730 --> 01:02:17,770
И ако искам да тече
ми program-- това се случва

1313
01:02:17,770 --> 01:02:23,010
да се нарече a.out за
исторически reasons-- "здравей".

1314
01:02:23,010 --> 01:02:24,070
Мога да го стартирате отново.

1315
01:02:24,070 --> 01:02:25,690
Здравей Здравей Здравей.

1316
01:02:25,690 --> 01:02:27,430
И това изглежда да се работи.

1317
01:02:27,430 --> 01:02:31,000
>> Но това означава, че някъде в моята
памет на компютъра са думите

1318
01:02:31,000 --> 01:02:35,279
з-д-л-л-о, удивителен знак.

1319
01:02:35,279 --> 01:02:38,070
И се оказва, просто като настрана,
какво компютър обикновено би

1320
01:02:38,070 --> 01:02:40,550
направи така, че да не знае къде
нещата започват и end-- това е

1321
01:02:40,550 --> 01:02:42,460
ще постави специален символ тук.

1322
01:02:42,460 --> 01:02:46,064
И Конвенцията е да се постави
номер нула в края на думата

1323
01:02:46,064 --> 01:02:48,230
така че вие ​​къде го знам
фактически завършва, така че да

1324
01:02:48,230 --> 01:02:52,750
Да не се съхранява отпечатване все повече и повече
символи, отколкото всъщност имат намерение.

1325
01:02:52,750 --> 01:02:55,400
>> Но Takeaway тук, дори
въпреки че това е доста тайнствена,

1326
01:02:55,400 --> 01:02:58,140
е, че това е в крайна сметка
сравнително проста.

1327
01:02:58,140 --> 01:03:04,550
Ти беше даден вид на лента, празен
пространство, на която можете да пишете писма.

1328
01:03:04,550 --> 01:03:07,150
Ти просто трябва да има
специален символ, като произволно

1329
01:03:07,150 --> 01:03:10,316
числото нула, за да сложи в края на
Вашите думи така, че компютърът ми е свидетел,

1330
01:03:10,316 --> 01:03:13,410
О, аз трябва да спре да печата, след
Виждам удивителен знак.

1331
01:03:13,410 --> 01:03:16,090
Защото следващото нещо, което има
е ASCII стойност, равна на нула,

1332
01:03:16,090 --> 01:03:19,125
или нулевата характер като
някой ще го наречем.

1333
01:03:19,125 --> 01:03:21,500
Но има и нещо като проблем
тук, и нека да се върне обратно

1334
01:03:21,500 --> 01:03:23,320
до номера за миг.

1335
01:03:23,320 --> 01:03:28,720
Да предположим, че аз правя, всъщност,
имаме масив от числа,

1336
01:03:28,720 --> 01:03:30,730
и предполагам, че
програма Пиша е

1337
01:03:30,730 --> 01:03:34,680
като клас книга за учителя
и учители класната стая.

1338
01:03:34,680 --> 01:03:38,720
И тази програма него или нея позволява
да въведете в десетки техните ученици

1339
01:03:38,720 --> 01:03:39,960
на викторини.

1340
01:03:39,960 --> 01:03:43,750
И предполагам, че студентът получава
100 за първия си тест, може би

1341
01:03:43,750 --> 01:03:49,920
като 80 на следващия, а след това
75, след това 90 на четвърти теста.

1342
01:03:49,920 --> 01:03:54,150
>> Така че в този момент в историята,
масива е с размери четири.

1343
01:03:54,150 --> 01:03:58,470
Няма абсолютно повече памет в
компютър, но на масива, така да се каже,

1344
01:03:58,470 --> 01:04:00,350
е с размери четири.

1345
01:04:00,350 --> 01:04:06,060
Да предположим сега, че учителят иска
да възложи една пета викторина към класа.

1346
01:04:06,060 --> 01:04:08,510
Е, едно от нещата, които той
или тя ще трябва да направите,

1347
01:04:08,510 --> 01:04:10,650
сега се съхранява допълнителна стойност тук.

1348
01:04:10,650 --> 01:04:15,490
Но ако масива учителят има
създаден в тази програма е с размер за,

1349
01:04:15,490 --> 01:04:22,440
един от проблема с множество е, че
не може просто да поддържа добавянето на памет.

1350
01:04:22,440 --> 01:04:26,470
Защото това, което, ако друга част от
програма има думата "хей" точно там?

1351
01:04:26,470 --> 01:04:29,650
>> С други думи, паметта ми може да бъде
използвана за нещо в една програма.

1352
01:04:29,650 --> 01:04:33,250
И ако по-рано написах, хей,
Искам да вход четири теста резултати,

1353
01:04:33,250 --> 01:04:34,784
те биха могли да отидете тук и тук.

1354
01:04:34,784 --> 01:04:37,700
И ако изведнъж промени мнението си
по-късно и да кажа, че искам една пета викторина

1355
01:04:37,700 --> 01:04:40,872
Оценката, не може просто да
Казано където искате,

1356
01:04:40,872 --> 01:04:42,580
защото какво, ако това
памет се използва

1357
01:04:42,580 --> 01:04:45,990
за нещо else-- някоя друга програма
или някаква друга особеност на програмата

1358
01:04:45,990 --> 01:04:46,910
че сте стартирали?

1359
01:04:46,910 --> 01:04:50,650
Така че ще трябва да се мисли предварително
как искате да съхранявате данните си,

1360
01:04:50,650 --> 01:04:54,480
защото сега сте боядисани
себе си в цифров ъгъл.

1361
01:04:54,480 --> 01:04:57,280
>> Така учителят може вместо
се каже, когато пишете програма

1362
01:04:57,280 --> 01:04:59,360
за съхраняване на неговия или нейния
степени, знаете ли какво?

1363
01:04:59,360 --> 01:05:04,180
Аз отивам да поиска,
при писане на моята програма,

1364
01:05:04,180 --> 01:05:12,070
че искам нула, едно, две, три,
четири, пет, шест, осем степени общо.

1365
01:05:12,070 --> 01:05:15,320
Така че едно, две, три, четири,
пет, шест, седем, осем.

1366
01:05:15,320 --> 01:05:18,612
Учителят може да сантиметри-отпусне
памет при писане на неговата или нейната програма

1367
01:05:18,612 --> 01:05:19,570
и да кажа, знаеш ли какво?

1368
01:05:19,570 --> 01:05:22,236
Аз никога няма да се възложи по-
от осем викторини в един семестър.

1369
01:05:22,236 --> 01:05:23,130
Това е просто луд.

1370
01:05:23,130 --> 01:05:24,470
Аз никога няма да се разпределят, че.

1371
01:05:24,470 --> 01:05:28,270
Така че по този начин той или тя има
гъвкавост на магазин студентски резултати,

1372
01:05:28,270 --> 01:05:33,010
като 75, 90, а може би и едно допълнително, където
студентът получи допълнително кредит, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Но ако никога учителя
използва тези три помещения,

1374
01:05:36,130 --> 01:05:38,860
има интуитивен храна за вкъщи тук.

1375
01:05:38,860 --> 01:05:41,410
Той или тя е просто загуба на пространство.

1376
01:05:41,410 --> 01:05:44,790
Така че, с други думи, там е това
общ компромис в програмирането

1377
01:05:44,790 --> 01:05:48,241
където можете да разпредели
точно толкова памет, колкото искате,

1378
01:05:48,241 --> 01:05:51,490
В посока нагоре, от които е, че вие ​​сте супер
efficient-- ви не се разточително

1379
01:05:51,490 --> 01:05:54,640
при all-- но недостатъкът на които
е това, което, ако промените мнението си, когато

1380
01:05:54,640 --> 01:05:58,780
с помощта на програмата, която искате да съхраните
повече данни, отколкото първоначално сте предназначени.

1381
01:05:58,780 --> 01:06:03,030
>> Така че може би решението е, след това,
напишете вашите програми по такъв начин,

1382
01:06:03,030 --> 01:06:05,605
че те използват повече памет
отколкото те действително се нуждаят.

1383
01:06:05,605 --> 01:06:07,730
По този начин вие няма
да тичам в този проблем,

1384
01:06:07,730 --> 01:06:09,730
но ти е разточително.

1385
01:06:09,730 --> 01:06:12,960
И колкото по-паметта си програма използва,
като обсъдихме вчера, толкова по-малко

1386
01:06:12,960 --> 01:06:15,410
памет, която е на разположение
за други програми,

1387
01:06:15,410 --> 01:06:18,790
колкото по-бързо вашия компютър може да се забави
надолу, защото на виртуалната памет.

1388
01:06:18,790 --> 01:06:22,670
И така идеалното решение би могло да бъде това, което?

1389
01:06:22,670 --> 01:06:24,610
>> По-алокиране изглежда лошо.

1390
01:06:24,610 --> 01:06:27,030
Над алокиране изглежда лошо.

1391
01:06:27,030 --> 01:06:31,120
Така че това, което може да е по-добро решение?

1392
01:06:31,120 --> 01:06:32,390
Преразпределяне.

1393
01:06:32,390 --> 01:06:33,590
Бъдете по-динамичен.

1394
01:06:33,590 --> 01:06:37,520
Не насилвайте себе си да изберем
априори, в началото, това, което искам.

1395
01:06:37,520 --> 01:06:41,370
И със сигурност не над-отпусне,
да не би да бъде разточително.

1396
01:06:41,370 --> 01:06:45,770
>> И така, за да се постигне тази цел, ние
Трябва да хвърлят тази структура от данни,

1397
01:06:45,770 --> 01:06:48,100
така да се каже, далеч.

1398
01:06:48,100 --> 01:06:51,080
И така, какво програмист
обикновено ще използва

1399
01:06:51,080 --> 01:06:55,940
е нещо, което не е наречено
масив, но свързан списък.

1400
01:06:55,940 --> 01:07:00,860
С други думи, той или тя ще
започне да се мисли за тяхната памет

1401
01:07:00,860 --> 01:07:05,280
като вид форма, която те
може да се направи по следния начин.

1402
01:07:05,280 --> 01:07:08,520
Ако искам да се съхранява един номер в
а program-- така че е септември

1403
01:07:08,520 --> 01:07:12,600
Дадох моите студенти тест; аз искам
за съхраняване на първия тест на студентите,

1404
01:07:12,600 --> 01:07:16,220
и те имам 100 на it-- I
отивам да попитам моя компютър,

1405
01:07:16,220 --> 01:07:19,540
по пътя на програмата съм
писмено, за една парче от паметта.

1406
01:07:19,540 --> 01:07:22,570
И аз отивам, за да съхраните
номер 100 в нея, и това е всичко.

1407
01:07:22,570 --> 01:07:24,820
>> След няколко седмици по-късно
когато получа моят втори тест,

1408
01:07:24,820 --> 01:07:27,890
и че е време да въведете
в която 90%, аз отивам

1409
01:07:27,890 --> 01:07:32,129
да поиска от компютъра, хей, компютър,
мога да имам друг парче от паметта?

1410
01:07:32,129 --> 01:07:34,170
Това ще ми даде тази
празно парче от паметта.

1411
01:07:34,170 --> 01:07:39,370
Отивам да се постави в брой 90,
но в моята програма по някакъв начин или other--

1412
01:07:39,370 --> 01:07:42,100
и ние няма да се тревожи за
синтаксиса за this-- ми трябва

1413
01:07:42,100 --> 01:07:44,430
по някакъв начин да прикове тези неща заедно.

1414
01:07:44,430 --> 01:07:47,430
И аз ще ги прикове заедно с
това, което изглежда като стрела тук.

1415
01:07:47,430 --> 01:07:50,050
>> Третият тест, който идва,
Отивам да се каже, хей, компютър,

1416
01:07:50,050 --> 01:07:51,680
дай ми още една буца памет.

1417
01:07:51,680 --> 01:07:54,660
И аз отивам да потушат
каквото и да е, като 75,

1418
01:07:54,660 --> 01:07:56,920
и аз трябва да верига тази
заедно сега някак си.

1419
01:07:56,920 --> 01:08:00,290
Четвърто викторина идва заедно, а може би и
това е към края на семестъра.

1420
01:08:00,290 --> 01:08:03,140
И от този момент моята програма
може да бъде използване на паметта

1421
01:08:03,140 --> 01:08:05,540
навсякъде, по целия физически.

1422
01:08:05,540 --> 01:08:08,170
И така, само за ритници, аз съм
Ще се направи това напред

1423
01:08:08,170 --> 01:08:11,260
quiz-- да забравя какво е било; аз
че може би на 80 противниците или нещо друго

1424
01:08:11,260 --> 01:08:12,500
начин тук.

1425
01:08:12,500 --> 01:08:15,920
>> Но това е добре, защото картинно
Отивам да се направи тази линия.

1426
01:08:15,920 --> 01:08:19,063
С други думи, в действителност,
в хардуера на компютъра,

1427
01:08:19,063 --> 01:08:20,979
първата оценка мощ
в крайна сметка тук, защото това е

1428
01:08:20,979 --> 01:08:22,529
полето в началото на семестъра.

1429
01:08:22,529 --> 01:08:25,810
Следващият може да свърши тук
защото малко време е минало

1430
01:08:25,810 --> 01:08:27,210
и програмата продължава да работи.

1431
01:08:27,210 --> 01:08:30,060
Следващата оценка, което е
75, може да бъде тук.

1432
01:08:30,060 --> 01:08:33,420
И последната оценка може да бъде
80, който е тук.

1433
01:08:33,420 --> 01:08:38,729
>> Така че в действителност, физически, това може да бъде
какво паметта на компютъра си прилича.

1434
01:08:38,729 --> 01:08:41,569
Но това не е полезен психичното
парадигма за компютърен програмист.

1435
01:08:41,569 --> 01:08:44,649
Защо трябва да се грижи, когато е на
чесало ви данни е завършил?

1436
01:08:44,649 --> 01:08:46,200
Вие просто искате да съхранява данни.

1437
01:08:46,200 --> 01:08:49,390
>> Това е нещо като нашата дискусия
по-рано от изготвянето на куба.

1438
01:08:49,390 --> 01:08:52,200
Защо ви интересува какво
ъгълът е на куба

1439
01:08:52,200 --> 01:08:53,740
и как трябва да се обърнат към него се направи?

1440
01:08:53,740 --> 01:08:54,950
Вие просто искате куб.

1441
01:08:54,950 --> 01:08:57,359
По същия начин тук,
Просто искам да клас книга.

1442
01:08:57,359 --> 01:08:59,559
Вие просто искате да се мисли за
това като списък от номера.

1443
01:08:59,559 --> 01:09:01,350
На кой му пука как е
приложени в хардуер?

1444
01:09:01,350 --> 01:09:05,180
>> Така черпене сега
е тази снимка тук.

1445
01:09:05,180 --> 01:09:07,580
Това е свързан списък, тъй като
програмист ще го наричаме,

1446
01:09:07,580 --> 01:09:10,640
доколкото имате
списък, очевидно на номера.

1447
01:09:10,640 --> 01:09:14,990
Но това е свързано картинно
по пътя на тези стрелки,

1448
01:09:14,990 --> 01:09:18,510
и всички тези стрели are-- отдолу
качулката, ако сте любопитни,

1449
01:09:18,510 --> 01:09:23,210
Припомняме, че нашата физическа хардуерна има
адреси нула, едно, две, три, четири.

1450
01:09:23,210 --> 01:09:28,465
Всички тези стрели са е като карта
или направления, в които, ако 90 is-- сега

1451
01:09:28,465 --> 01:09:29,090
Трябва да се брои.

1452
01:09:29,090 --> 01:09:31,750
>> Нула, едно, две, три,
четири, пет, шест, седем.

1453
01:09:31,750 --> 01:09:35,640
Тя изглежда като 90 е най-
памет адрес номер седем.

1454
01:09:35,640 --> 01:09:38,460
Всички тези стрели са се
като малко парче хартия

1455
01:09:38,460 --> 01:09:42,439
че да даде указания на
програма, която казва, следват тази карта

1456
01:09:42,439 --> 01:09:43,880
да стигнем до място седем.

1457
01:09:43,880 --> 01:09:46,680
И там ще намерите най-
втори тест на полувремето студент.

1458
01:09:46,680 --> 01:09:52,100
Междувременно, 75-- ако продължи това,
това е седем, осем, девет, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Тази друга стрела точно представлява
карта на място в паметта 15.

1461
01:09:59,080 --> 01:10:02,550
Но отново, програмист обикновено прави
не се грижи за това ниво на детайлност.

1462
01:10:02,550 --> 01:10:05,530
И в най-всеки програмиране
език днес, програмист

1463
01:10:05,530 --> 01:10:10,490
дори няма да знаят къде в паметта
тези числа всъщност са.

1464
01:10:10,490 --> 01:10:14,830
Всичко, което той или тя трябва да се грижи за е
че те са по някакъв начин свързани заедно

1465
01:10:14,830 --> 01:10:18,390
в структурата на данните по този начин.

1466
01:10:18,390 --> 01:10:21,580
>> Но се оказва, не
за да получите твърде технически.

1467
01:10:21,580 --> 01:10:27,430
Но само защото ние може би ще
позволят да имат тази дискусия тук,

1468
01:10:27,430 --> 01:10:33,630
Предполагам, че ние отново
този въпрос тук от масив.

1469
01:10:33,630 --> 01:10:35,780
Да видим дали съжаляваме става тук.

1470
01:10:35,780 --> 01:10:42,950
Това е 100, 90, 75 и 80.

1471
01:10:42,950 --> 01:10:44,980
>> Нека накратко да това твърдение.

1472
01:10:44,980 --> 01:10:48,980
Това е масив, и отново, за
изявена характеристика на масив

1473
01:10:48,980 --> 01:10:52,400
е, че всичките ви данни е обратно
успоредно в memory-- буквално

1474
01:10:52,400 --> 01:10:56,830
един байт или може би четири байта,
някои фиксиран брой байтове далеч.

1475
01:10:56,830 --> 01:11:00,710
В свързан списък, който бихме могли да изготвят
по този начин, под предния капак, който

1476
01:11:00,710 --> 01:11:02,000
знае къде тези неща е?

1477
01:11:02,000 --> 01:11:03,630
Той дори не е необходимо да тече по този начин.

1478
01:11:03,630 --> 01:11:06,050
Някои от данните може да бъде
обратно наляво там.

1479
01:11:06,050 --> 01:11:07,530
Ти дори не знаеш.

1480
01:11:07,530 --> 01:11:15,430
>> И така с масив, че имате
функция, известна като произволен достъп.

1481
01:11:15,430 --> 01:11:20,570
И какво означава произволен достъп е
че компютърът може да скочи мигновено

1482
01:11:20,570 --> 01:11:22,730
за всяко място в масив.

1483
01:11:22,730 --> 01:11:23,580
Защо?

1484
01:11:23,580 --> 01:11:26,000
Тъй компютъра знае
че първото място е

1485
01:11:26,000 --> 01:11:29,540
нула, едно, две, три.

1486
01:11:29,540 --> 01:11:33,890
>> И така, ако искате да се премине от
този елемент на следващия елемент,

1487
01:11:33,890 --> 01:11:36,099
Вие буквално, в
съзнанието на компютъра, просто добавете една.

1488
01:11:36,099 --> 01:11:39,140
Ако искате да отидете на третия елемент,
Просто добавете one-- следващия елемент, просто

1489
01:11:39,140 --> 01:11:40,290
добавете една.

1490
01:11:40,290 --> 01:11:42,980
Въпреки това, в тази версия
на историята, да предположим,

1491
01:11:42,980 --> 01:11:46,080
компютърът е в момента търси
при или занимаващи се с номера 100.

1492
01:11:46,080 --> 01:11:49,770
Как да стигнем до следващото
клас в клас книгата?

1493
01:11:49,770 --> 01:11:52,560
>> Трябва да се вземат седем
стъпки, което е произволно.

1494
01:11:52,560 --> 01:11:58,120
За да стигнете до следващото, което трябва да
отнеме още осем стъпки, за да стигнем до 15.

1495
01:11:58,120 --> 01:12:02,250
С други думи, това не е
постоянна разлика между цифрите,

1496
01:12:02,250 --> 01:12:04,857
и така тя просто е на
компютър повече време е най-важното.

1497
01:12:04,857 --> 01:12:06,940
Компютърът трябва да търси
чрез памет, за

1498
01:12:06,940 --> 01:12:08,990
за да намерите това, което търсите.

1499
01:12:08,990 --> 01:12:14,260
>> Така че масив има тенденция да бъде
structure-- бързо данни, защото

1500
01:12:14,260 --> 01:12:17,610
може буквално направи проста аритметика
и стигнеш там, където искате чрез добавяне на един,

1501
01:12:17,610 --> 01:12:21,300
за instance-- свързан списък,
жертваш тази функция.

1502
01:12:21,300 --> 01:12:24,020
Не може просто да отида от първия
до втора до трета до четвърта.

1503
01:12:24,020 --> 01:12:25,240
Трябва да се следват карта.

1504
01:12:25,240 --> 01:12:28,160
Трябва да се вземат повече стъпки
за да стигнем до тези стойности, които

1505
01:12:28,160 --> 01:12:30,230
изглежда е добавянето на разходите.

1506
01:12:30,230 --> 01:12:35,910
Така че ние плащаме цената, но това, което беше
функцията, която Дан се търси тук?

1507
01:12:35,910 --> 01:12:38,110
Какво прави един свързан списък
очевидно ни позволи да направим,

1508
01:12:38,110 --> 01:12:40,240
който е произхода на
тази конкретна история?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Точно.

1511
01:12:43,830 --> 01:12:46,220
Един динамичен размер до него.

1512
01:12:46,220 --> 01:12:48,040
Ние можем да добавите към този списък.

1513
01:12:48,040 --> 01:12:51,430
Ние дори може да се свие в списъка, така че
че ние сме само с помощта на повече памет

1514
01:12:51,430 --> 01:12:55,560
както всъщност искаме и така
ние никога не сме прекалено тяхното разпределяне.

1515
01:12:55,560 --> 01:12:58,470
>> Сега, само за да бъде наистина гнида-придирчиви,
има скрити разходи.

1516
01:12:58,470 --> 01:13:01,980
Така че не трябва просто да ме убедят
ви, че това е убедителна компромис.

1517
01:13:01,980 --> 01:13:04,190
Има и друг скрит разход тук.

1518
01:13:04,190 --> 01:13:06,550
Ползата, за да бъде ясно,
е, че ние се динамика.

1519
01:13:06,550 --> 01:13:10,359
Ако искам още един елемент, мога просто
изготвят го и постави редица там.

1520
01:13:10,359 --> 01:13:12,150
И тогава мога да го свържете
със снимка тук,

1521
01:13:12,150 --> 01:13:14,970
като има предвид тук, отново, ако съм
себе си боядисани в един ъгъл,

1522
01:13:14,970 --> 01:13:19,410
ако нещо друго вече е с помощта
спомена тук, аз съм на късмет.

1523
01:13:19,410 --> 01:13:21,700
Аз съм се боядисани в ъгъла.

1524
01:13:21,700 --> 01:13:24,390
>> Но това, което е най-скритите
струва в тази картина?

1525
01:13:24,390 --> 01:13:27,690
Това не е просто сумата
на време, необходимо

1526
01:13:27,690 --> 01:13:29,870
да минат оттук към тук,
което е седем стъпки, тогава

1527
01:13:29,870 --> 01:13:32,820
осем стъпала, което е повече от един.

1528
01:13:32,820 --> 01:13:34,830
Какво друго скрити разходи?

1529
01:13:34,830 --> 01:13:35,440
Не само времето.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Допълнителна информация е
необходимото за постигане на тази снимка.

1532
01:13:49,940 --> 01:13:53,210
>> Да, това картата, тези малки парченца
хартия, като пазя ги като.

1533
01:13:53,210 --> 01:13:55,650
Те arrows-- тези, които не са свободни.

1534
01:13:55,650 --> 01:13:57,660
А computer-- ли, че
какъв компютър има.

1535
01:13:57,660 --> 01:13:58,790
Той има нули и единици.

1536
01:13:58,790 --> 01:14:03,170
Ако искате да представлява стрелка или
карта или номер, имате нужда от памет.

1537
01:14:03,170 --> 01:14:05,950
Така че, от друга цената, която
плати за свързан списък,

1538
01:14:05,950 --> 01:14:09,070
обща компютърни науки
ресурс, също място.

1539
01:14:09,070 --> 01:14:11,710
>> И наистина е така, толкова често,
сред алтернативите

1540
01:14:11,710 --> 01:14:15,580
при проектирането на софтуерно инженерство
системи е време и space--

1541
01:14:15,580 --> 01:14:18,596
са две от вашите съставки, две
на вашите най-скъпи съставки.

1542
01:14:18,596 --> 01:14:21,220
Това е ми струва повече време
защото трябва да следват тази карта,

1543
01:14:21,220 --> 01:14:25,730
но тя също ми струва повече пространство
защото трябва да се запази тази карта наоколо.

1544
01:14:25,730 --> 01:14:28,730
Така надеждата, тъй като ние сме вид
обсъдено над вчера и днес,

1545
01:14:28,730 --> 01:14:31,720
е, че ползите
ще надхвърлят разходите.

1546
01:14:31,720 --> 01:14:33,870
>> Но няма очевидно решение тук.

1547
01:14:33,870 --> 01:14:35,870
Може би това е better--
а-ла-бърз и мръсен,

1548
01:14:35,870 --> 01:14:38,660
като Карим предложен earlier--
да хвърлят памет на проблема.

1549
01:14:38,660 --> 01:14:42,520
Просто купуват повече памет, мисля, че по-малко
трудно за решаване на проблема,

1550
01:14:42,520 --> 01:14:44,595
и го решим в по-лесен начин.

1551
01:14:44,595 --> 01:14:46,720
И наистина по-рано, когато
ние говорихме за компромиси,

1552
01:14:46,720 --> 01:14:49,190
не е пространство
компютъра и времето.

1553
01:14:49,190 --> 01:14:51,810
Беше време разработчик, който
е още един ресурс.

1554
01:14:51,810 --> 01:14:54,829
>> Така че отново, това е този балансиращ акт
опитвайки се да реши кои от тези неща,

1555
01:14:54,829 --> 01:14:55,870
склонни да харчат сте?

1556
01:14:55,870 --> 01:14:57,380
Коя е най-евтиният?

1557
01:14:57,380 --> 01:15:01,040
Което води до получаване на по-добри резултати?

1558
01:15:01,040 --> 01:15:01,540
Да?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Наистина.

1561
01:15:12,580 --> 01:15:15,970
В този случай, ако сте
представляваща номера в maps--

1562
01:15:15,970 --> 01:15:18,820
те се наричат ​​в много езици
"указатели" или "адреси" -

1563
01:15:18,820 --> 01:15:20,390
това е двойно пространството.

1564
01:15:20,390 --> 01:15:24,390
Това не трябва да бъде толкова лошо, колкото двойно, ако
точно сега ние просто съхраняване на номера.

1565
01:15:24,390 --> 01:15:27,410
Да предположим, че сме били съхраняване
досиета на пациентите в hospital--

1566
01:15:27,410 --> 01:15:30,870
така имена Пиърсън е, телефонни номера,
номера на социални осигуровки, лекар

1567
01:15:30,870 --> 01:15:31,540
история.

1568
01:15:31,540 --> 01:15:34,160
Тази клетка може да бъде много,
много по-голям, като в този случай

1569
01:15:34,160 --> 01:15:38,000
мъничък показалеца, на адреса на
следващата element-- това не е голяма работа.

1570
01:15:38,000 --> 01:15:40,620
Това е толкова ресни
струва, че няма значение.

1571
01:15:40,620 --> 01:15:43,210
Но в този случай, да, това е удвояване.

1572
01:15:43,210 --> 01:15:45,290
Добър въпрос.

1573
01:15:45,290 --> 01:15:47,900
>> Нека поговорим за времето на
малко по-конкретно.

1574
01:15:47,900 --> 01:15:50,380
Какво е времето за работа на
на търсене този списък?

1575
01:15:50,380 --> 01:15:53,640
Да предположим, че аз исках да търсите
през всички степени на учениците,

1576
01:15:53,640 --> 01:15:55,980
и има н степени
в тази структура на данните.

1577
01:15:55,980 --> 01:15:58,830
Тук също можем да заеме
речника на по-рано.

1578
01:15:58,830 --> 01:16:00,890
Това е линейна структура на данните.

1579
01:16:00,890 --> 01:16:04,570
>> Big O на п е какво се изисква, за да се получи
в края на тази структура данни,

1580
01:16:04,570 --> 01:16:08,410
whereas-- и не сме виждали
това before-- масив дава

1581
01:16:08,410 --> 01:16:13,555
това, което се нарича константно време, което означава,
една стъпка или две стъпки или 10 steps--

1582
01:16:13,555 --> 01:16:14,180
Няма значение.

1583
01:16:14,180 --> 01:16:15,440
Това е един фиксиран номер.

1584
01:16:15,440 --> 01:16:17,440
Това няма нищо общо с
размера на масива.

1585
01:16:17,440 --> 01:16:20,130
И причината за това,
отново, е произволен достъп.

1586
01:16:20,130 --> 01:16:23,180
Компютърът може просто веднага
скочи на друго място,

1587
01:16:23,180 --> 01:16:27,770
защото те всички са еднакви
разстояние от всичко останало.

1588
01:16:27,770 --> 01:16:29,112
Не е мислене участват.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Добре.

1591
01:16:32,400 --> 01:16:39,230
Така че, ако мога, нека се опитаме да
нарисува две финални снимки.

1592
01:16:39,230 --> 01:16:42,830
А много често един известен като таблица хашиш.

1593
01:16:42,830 --> 01:16:51,120
Така че, за да мотивира тази дискусия,
позволете ми да мисля за това как да направите това.

1594
01:16:51,120 --> 01:16:52,610
>> Така че какво ще кажеш за това?

1595
01:16:52,610 --> 01:16:55,160
Да предположим, че проблемът
ние искаме да решим сега

1596
01:16:55,160 --> 01:16:58,360
изпълнява в dictionary--
така цял куп английски думи

1597
01:16:58,360 --> 01:16:59,330
или каквото.

1598
01:16:59,330 --> 01:17:02,724
И целта е да бъде в състояние да отговори на
въпроси на формата е тази дума?

1599
01:17:02,724 --> 01:17:04,640
Така че ако искате да се приложат
една проверка на правописа, просто

1600
01:17:04,640 --> 01:17:07,220
като физическо речника
че можете да погледнете нещата вътре.

1601
01:17:07,220 --> 01:17:10,490
Да предположим, че аз трябваше да направя това с масив.

1602
01:17:10,490 --> 01:17:12,590
Мога да направя това.

1603
01:17:12,590 --> 01:17:20,756
>> И предполагам, че думите са ябълка
и банан и пъпеш.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
И не мога да мисля за плодове
които започват с г, така че ние сме просто

1606
01:17:26,465 --> 01:17:27,590
ще има три плодове.

1607
01:17:27,590 --> 01:17:31,510
Така че това е масив, и ние сме
съхраняване на всички тези думи

1608
01:17:31,510 --> 01:17:34,200
в този речник като масив.

1609
01:17:34,200 --> 01:17:39,350
Въпросът тогава е как друг
може ли да се съхранява тази информация?

1610
01:17:39,350 --> 01:17:43,160
>> Е, аз съм един вид измама тук, защото
всеки един от тези буквите в думата

1611
01:17:43,160 --> 01:17:44,490
е наистина индивидуално байт.

1612
01:17:44,490 --> 01:17:46,740
Така че, ако аз наистина исках да бъда
гнида-придирчиви, че трябва наистина

1613
01:17:46,740 --> 01:17:49,600
да се раздели този нагоре в много
по-малки парчета от паметта,

1614
01:17:49,600 --> 01:17:51,289
и можем да направим точно това.

1615
01:17:51,289 --> 01:17:53,580
Но ние ще се сблъскате
същия проблем, както преди.

1616
01:17:53,580 --> 01:17:56,674
Ами ако, като Merriam Webster или Оксфорд
прави всеки year-- те добавят думи

1617
01:17:56,674 --> 01:17:59,340
до dictionary-- не го правим
непременно искаме да се нарисува

1618
01:17:59,340 --> 01:18:00,780
в един ъгъл с масив?

1619
01:18:00,780 --> 01:18:05,710
>> Така че, вместо да, може би по-интелигентен подход
е да се сложи ябълка в своя собствен възел или кутия,

1620
01:18:05,710 --> 01:18:11,190
както бихме казали, банан, и
След това тук имаме пъпеш.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
И ние низ тези неща заедно.

1623
01:18:16,790 --> 01:18:19,980
Така че това е масива, и
това е свързан списък.

1624
01:18:19,980 --> 01:18:23,300
Ако не можете да доста видим, тя просто
казва "масив", и това казва "списък."

1625
01:18:23,300 --> 01:18:25,780
>> Така че ние имаме едни и същи
точните въпроси, както и преди,

1626
01:18:25,780 --> 01:18:28,600
при което имаме сега
динамика в нашия списък свързан.

1627
01:18:28,600 --> 01:18:31,090
Но ние имаме доста бавен речника.

1628
01:18:31,090 --> 01:18:32,870
Да предположим, че искате да погледнете нагоре и дума.

1629
01:18:32,870 --> 01:18:35,430
Тя може да ми отнеме голяма O на п
стъпки, защото думата мощ

1630
01:18:35,430 --> 01:18:37,840
е чак в края на
списъка, като пъпеш.

1631
01:18:37,840 --> 01:18:40,600
И се оказва, че
в програмирането, сортиране

1632
01:18:40,600 --> 01:18:42,700
на Светия Граал на данни
структури, е нещо,

1633
01:18:42,700 --> 01:18:46,620
който ви дава постоянна
време като масив

1634
01:18:46,620 --> 01:18:50,870
но това все още дава динамика.

1635
01:18:50,870 --> 01:18:52,940
>> Така че може да имаме най-доброто от двата свята?

1636
01:18:52,940 --> 01:18:55,570
И наистина, има нещо
наречена хеш таблица

1637
01:18:55,570 --> 01:18:59,320
който ви позволява да направите точно
че, макар и приблизително.

1638
01:18:59,320 --> 01:19:03,140
А маса хеш е любител
структурата на данните, че

1639
01:19:03,140 --> 01:19:06,340
да мислим като за
комбинация от array--

1640
01:19:06,340 --> 01:19:12,390
и аз ще го направи
като this-- и свързани списъци

1641
01:19:12,390 --> 01:19:17,310
че аз ще се направи като този тук.

1642
01:19:17,310 --> 01:19:19,760
>> И начина, по това нещо
дела е както следва.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Ако това now-- хеш table--
е третото ми структура на данните,

1645
01:19:29,540 --> 01:19:32,590
и аз искам да се съхранява
думи от това, аз не правя

1646
01:19:32,590 --> 01:19:35,440
искате да съхранявате просто всичко на
думи обратно към гръб с гръб към гръб.

1647
01:19:35,440 --> 01:19:37,430
Искам да се наберат някои
част от информацията

1648
01:19:37,430 --> 01:19:40,330
за думите, които ще ви позволи
ми го получи, когато това е по-бързо.

1649
01:19:40,330 --> 01:19:43,666
>> Така че като се има предвид думи ябълка
и банан и пъпеш,

1650
01:19:43,666 --> 01:19:45,040
Аз съзнателно са избрали тези думи.

1651
01:19:45,040 --> 01:19:45,340
Защо?

1652
01:19:45,340 --> 01:19:47,631
Какво е нещо фундаментално
различен за трите?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Какво е най-очевидното?

1655
01:19:51,484 --> 01:19:52,900
Те започват с различни букви.

1656
01:19:52,900 --> 01:19:53,900
>> Така ли какво?

1657
01:19:53,900 --> 01:19:57,120
Вместо да постави всички мои думи в
същата кофа, така да се каже,

1658
01:19:57,120 --> 01:20:00,390
като в един голям списък, защо не го правят
Аз поне се опита оптимизация

1659
01:20:00,390 --> 01:20:04,180
и да ми списъци 1/26 толкова дълго.

1660
01:20:04,180 --> 01:20:07,440
А непреодолими оптимизация
може да е защо не го правят

1661
01:20:07,440 --> 01:20:10,650
I-- при поставянето на думата
в тази структура от данни,

1662
01:20:10,650 --> 01:20:14,300
в паметта на компютъра, защо
не сложих всички "А" думите тук,

1663
01:20:14,300 --> 01:20:17,270
всичко думите "б" тук,
и всички "С" думи тук?

1664
01:20:17,270 --> 01:20:24,610
Така че това в крайна сметка сложи ябълка
тук, банан тук, пъпеш тук,

1665
01:20:24,610 --> 01:20:25,730
и т.н.

1666
01:20:25,730 --> 01:20:31,700
>> И ако имам допълнителен
Думата like-- това, което е още един?

1667
01:20:31,700 --> 01:20:36,640
Ябълка, банан, круша.

1668
01:20:36,640 --> 01:20:39,370
Всеки, който се мисли за плодове
който започва с А, В, или С?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- перфектно.

1670
01:20:40,570 --> 01:20:43,990
Това се случва, за да се свърши тук.

1671
01:20:43,990 --> 01:20:47,530
И така, ние като че ли да има
незначително по-добро решение,

1672
01:20:47,530 --> 01:20:50,820
защото сега, ако искам
за търсене на ябълка, I

1673
01:20:50,820 --> 01:20:53,200
first-- аз не просто гмуркане
в моята структура на данните.

1674
01:20:53,200 --> 01:20:54,850
Аз не се потопите в памет на моя компютър.

1675
01:20:54,850 --> 01:20:56,530
Аз първо разгледаме първата буква.

1676
01:20:56,530 --> 01:20:58,610
>> И това е, което един компютър
учен ще каже.

1677
01:20:58,610 --> 01:21:00,760
Можете хеш във вашата структура на данните.

1678
01:21:00,760 --> 01:21:04,100
Можете да си вход, което в
този случай е дума, като ябълка.

1679
01:21:04,100 --> 01:21:07,150
Можете да го анализираме, гледайки
първата буква в този случай,

1680
01:21:07,150 --> 01:21:08,340
като по този начин го хеширане.

1681
01:21:08,340 --> 01:21:10,950
Хеширане е общ термин, с което
вземете нещо като вход

1682
01:21:10,950 --> 01:21:12,116
и ви се произвеждат някои изход.

1683
01:21:12,116 --> 01:21:15,090
И изхода с това, че
случай е мястото

1684
01:21:15,090 --> 01:21:18,150
искате да търсите, първият
място, второ място, на трето място.

1685
01:21:18,150 --> 01:21:22,160
Така че входът е ябълка,
изхода е на първо място.

1686
01:21:22,160 --> 01:21:25,054
Входът е банан г.
изход трябва да бъде втори.

1687
01:21:25,054 --> 01:21:27,220
Входът е пъпеш,
на изхода трябва да е трета.

1688
01:21:27,220 --> 01:21:30,320
Входът е боровинка г.
изход трябва отново да бъде на второ място.

1689
01:21:30,320 --> 01:21:34,010
И това е, което ви помага да се вземат
команди за бърз достъп чрез паметта си

1690
01:21:34,010 --> 01:21:39,050
за да се стигне до думи
или данни по-ефективно.

1691
01:21:39,050 --> 01:21:43,330
>> Сега това съкращава времето ни потенциално
с толкова, колкото един на 26,

1692
01:21:43,330 --> 01:21:45,850
защото, ако приемем, че сте
имат най-много "А" думи като "Z"

1693
01:21:45,850 --> 01:21:48,080
думи като думи "Q", които
Не е наистина realistic--

1694
01:21:48,080 --> 01:21:50,830
започваш да имат кос през
някои букви от alphabet--

1695
01:21:50,830 --> 01:21:53,204
но това ще бъде постепенен
подход, който позволява

1696
01:21:53,204 --> 01:21:55,930
можете да получите на думи много по-бързо.

1697
01:21:55,930 --> 01:21:59,660
И в действителност, изискан
програма, на Googles на света,

1698
01:21:59,660 --> 01:22:02,180
на Facebooks на world--
те ще се използва хеш-таблица

1699
01:22:02,180 --> 01:22:03,740
за много различни цели.

1700
01:22:03,740 --> 01:22:06,590
Но те не биха били толкова наивен като
да изглежда точно по първата буква

1701
01:22:06,590 --> 01:22:09,700
в ябълка или банан или
круша или пъпеш,

1702
01:22:09,700 --> 01:22:13,420
защото, както можете да видите тези
списъци все още може да получи дълго.

1703
01:22:13,420 --> 01:22:17,130
>> И така, това все още може да бъде нещо като
на linear-- така някак бавно,

1704
01:22:17,130 --> 01:22:19,980
като с голям О от п
че ние обсъдихме по-рано.

1705
01:22:19,980 --> 01:22:25,290
Така че това, което истински добър хеш таблица ще
do-- тя ще има много по-голям масив.

1706
01:22:25,290 --> 01:22:28,574
И тя ще се използва много по-
усъвършенствана функция за хеширане,

1707
01:22:28,574 --> 01:22:30,240
така че да не просто погледнете в "А".

1708
01:22:30,240 --> 01:22:35,480
Може би изглежда на "а-р-р-л-д" и
някак конвертира тези пет букви

1709
01:22:35,480 --> 01:22:38,400
в мястото, където
ябълка трябва да се съхранява.

1710
01:22:38,400 --> 01:22:42,660
Ние просто наивно помощта на буквата "А"
сам, защото това е хубаво и просто.

1711
01:22:42,660 --> 01:22:44,600
>> Но хеш таблица, в
края, можеш да се сетиш

1712
01:22:44,600 --> 01:22:47,270
на като комбинация от
масив, всеки от които

1713
01:22:47,270 --> 01:22:51,700
има свързан списък, че в идеалния случай
трябва да бъде възможно най-кратък.

1714
01:22:51,700 --> 01:22:54,364
И това не е очевидно решение.

1715
01:22:54,364 --> 01:22:57,280
В действителност, много от фина настройка
че отива под капака, когато

1716
01:22:57,280 --> 01:22:59,654
прилагането на тези видове
сложни структури от данни

1717
01:22:59,654 --> 01:23:01,640
е това, което е право
дължина на масива?

1718
01:23:01,640 --> 01:23:03,250
Какъв е правилният хеш функция?

1719
01:23:03,250 --> 01:23:04,830
Как да съхранявате неща в паметта?

1720
01:23:04,830 --> 01:23:07,249
>> Но осъзнават колко бързо
този вид на дискусия

1721
01:23:07,249 --> 01:23:10,540
ескалира, както досега, че това е вид
на над главата в този момент, който

1722
01:23:10,540 --> 01:23:11,360
е наред.

1723
01:23:11,360 --> 01:23:18,820
Но ние започнахме, изземване, с наистина
нещо на ниско ниво и на електронен носител.

1724
01:23:18,820 --> 01:23:20,819
И така, това отново е това
Темата на абстракция,

1725
01:23:20,819 --> 01:23:23,610
където след като започнете да се вземат за
отпусната, ОК, аз съм it-- попаднал там е

1726
01:23:23,610 --> 01:23:26,680
физическата памет, Добре, разбрах, всеки
физическо място има адрес,

1727
01:23:26,680 --> 01:23:29,910
ОК, аз го имам, мога да представляват
тези адреси като arrows--

1728
01:23:29,910 --> 01:23:34,650
можете да много бързо да започне да има
по-сложни разговори, които

1729
01:23:34,650 --> 01:23:38,360
в края на краищата изглежда да ни позволи
за решаване на проблеми, като търсите

1730
01:23:38,360 --> 01:23:41,620
и сортиране по-ефективно.

1731
01:23:41,620 --> 01:23:44,190
И бъдете сигурни, too--
защото мисля, че това

1732
01:23:44,190 --> 01:23:48,700
е най-дълбокото сме отишли ​​в някои
на тези CS теми proper-- ние сме

1733
01:23:48,700 --> 01:23:51,880
направи в един ден и половина в този
посоча това, което може обикновено правя над

1734
01:23:51,880 --> 01:23:55,520
В продължение на осем седмици в семестър.

1735
01:23:55,520 --> 01:23:59,670
>> Всички въпроси, свързани с тях?

1736
01:23:59,670 --> 01:24:01,100
Не?

1737
01:24:01,100 --> 01:24:01,940
Добре.

1738
01:24:01,940 --> 01:24:05,610
Е, защо не спрете там,
започне обяд няколко минути по-рано,

1739
01:24:05,610 --> 01:24:07,052
възобнови само около един час?

1740
01:24:07,052 --> 01:24:08,760
И аз ще се задържи за
малко с въпроса.

1741
01:24:08,760 --> 01:24:11,343
Тогава аз ще трябва да отида
отнеме няколко повиквания, ако това е ОК.

1742
01:24:11,343 --> 01:24:15,000
Ще включа малко музика в същото време,
но обяд трябва да е зад ъгъла.

1743
01:24:15,000 --> 01:24:17,862