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
Так ажно да гэтага URL, дзе вы
павінны ўбачыць старонку зусім так,

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
І мы казалі
падчас перапынку аб З,

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
Я пайшоў наперад і на самай справе аказалася
што праграма, бінарны пошук,

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
І што гэта значыць быць працэсар
што ў вас ёсць набор інструкцый,

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
>> Такім чынам, у верхнім левым куце экрана, мы
існуе ўзровень чыстага ліста, так бы мовіць.

99
00:04:55,024 --> 00:04:57,440
Драпіны не толькі імя
гэтай мовы праграмавання;

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
Я збіраюся націснуць катэгорыю кіравання.

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
>> І што прыемна аб пустым месцы
з'яўляецца тое, што гэты кавалак галаваломкі, калі

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
Так, напрыклад, Драпіны правоў
цяпер у сярэдзіне свайго свету.

122
00:06:09,710 --> 00:06:14,660
Я збіраюся ісці наперад і выбраць
Цяпер, скажам, катэгорыя руху,

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
>> Калі вы паглядзіце на сцэну Скрэтч
тут і глядзець у верхняй часткі яго,

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
я прапаную вам высветліць, як
зрабіць Драпіны шпацыр прама са сцэны.

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
але гэта адчувае сябе крыху
трохі Хакам, так бы мовіць,

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
Зараз звернеце ўвагу незалежна ад таго, дзе драпіна
пачынаецца, ён ідзе да краю.

185
00:09:28,300 --> 00:09:30,700
І на шчасце MIT,
які робіць нуля, проста

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
зрабіць Драпіны рухацца хутчэй
па экране?

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
ісці наперад і змяніць яго, мэтай якіх
што б вы 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
Гэта проста паказвае вам чалавека A
цэлая куча нерухомых малюнкаў на самай справе,

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
як уяўляецца, маюць умоўнымі, так
кажуць, пад катэгорыю кіравання.

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
Ці, калі вы не прайшлі яшчэ тут,
ісці наперад да катэгорыі Sensing

229
00:11:34,910 --> 00:11:39,612
и-- давайце паглядзім, калі ён тут.

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
Так, звярніце ўвагу, што некаторыя з гэтых блокаў
могуць быць параметризованы, калі можна так выказацца.

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
для таго, каб вырашыць праблему наяўнасці
Драпіна рух справа налева направа

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
OK, рухацца крокі.

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
Так то калі.

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
>> Дазвольце мне перацягнуць наскрэбці.

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
>> Motion, 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
Але па большай частцы, вы
ёсць у гэтай мове, на пустым месцы,

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
Любыя пытанні на пустым месцы?

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
пазнаёміць іх з нуля.

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
Цяпер одно-- гэта яшчэ лепш.

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
маюць дадатковую аператыўную памяць, дадатковыя
памяць, таму што, вядома ж,

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
тащась праз кожны раз.

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
Дык колькі крокаў зрабіў я
павінны ўзяць на сябе ў наступны раз?

624
00:29:42,540 --> 00:29:49,970
14, а затым 13, а затым 12, плюс кропка,
кропка, кропка, пакуль я не застанецца толькі адзін.

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
>> Іншымі словамі, калі я падлучу
на мільён, п квадрат

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
Знаходжанне Майк ў тэлефоне
Кніга, якая мае п старонак

690
00:32:50,210 --> 00:32:55,280
можа спатрэбіцца, у самым горшым выпадку,
колькі крокаў па парадку п?

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
Кампутар, як мы ведаем, мае
Аператыўная памяць, або Random Access Memory,

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
Таксама на парадак п квадрата.

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
>> СТУДЭНТЫ: Гэта не паслядоўны.

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
>> СТУДЭНТЫ: Змесціце іх у парадку.

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
>> СТУДЭНЦКАЯ парадку ўзрастання.

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
>> СТУДЭНТЫ: Самы маленькі з
лічбы не ў першым прасторы.

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
>> СТУДЭНТЫ: лікавая паслядоўнасць.

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
>> СТУДЭНТЫ: Плюс адзін.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Малання: Што гэта?

898
00:42:08,750 --> 00:42:09,610
>> СТУДЭНТЫ: Плюс адзін.

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
>> СТУДЭНТЫ: Гэта не месца.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Малання: Што
не ў патрэбным месцы?

908
00:42:25,580 --> 00:42:26,174
>> СТУДЭНТЫ: Чатыры.

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
Я збольшага дасягнуў канца спісу.

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
п раз, таму што вы павінны працягваць ісці
назад, каб праверыць і выправіць патэнцыйна

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
з іх адразу ж інтуітыўна
ад лятучай мышы ад Ben

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
>> Найменшая колькасць,
Я або Бэн выявіў раптам

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
так што гэта крыху руйнаваўся магчыма.

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
І адмыслова для вучняў, якiя не з'яўляюцца
абавязкова візуальнае або матэматычнае,

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, якая на самай справе менш, і, такім чынам,

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
Гэта тое, што называецца "Гном роду."

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 памяці складае

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
адзін гігабайт аператыўнай памяці, адзін гігабайт
памяць, якая, колькі ўсяго байт?

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
Мега млн.

1153
00:54:11,730 --> 00:54:14,570
Гіга гэта мільярд.

1154
00:54:14,570 --> 00:54:15,070
>> Я ляжу?

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
>> Гэта не так складана, як адзін Brattle
Плошчу, Кембрыдж, штат Масачусэтс., 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
яе цэнтральнага працэсара і яго
камплект 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. Гэта значна больш страшным,
Я б сказаў, чым нуля,

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
фактычна становіцца "Printf" з
некаторыя круглыя ​​дужкі і кропка з коскі.

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
>> Але тут ежа на дом, нават
хоць гэта даволі аркан,

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 або something--

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
Калі вы хочаце, каб перайсці да трэцяга элементу,
проста дадайце одно-- наступны элемент, проста

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
>> Цяпер проста, каб быць сапраўды NIT-пераборлівыя,
ёсць скрытыя выдаткі.

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
І я не магу думаць пра садавіну
якія пачынаюцца з D, так што мы проста

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 або Оксфард
робіць кожны год-- яны дадаюць слова

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
Я-- пры ўстаўцы словы
у гэтую структуру дадзеных,

1662
01:20:10,650 --> 01:20:14,300
ў памяць кампутара, чаму
я не аддаў усё 'а' словы тут,

1663
01:20:14,300 --> 01:20:17,270
усе 'Коммерсанта' словы тут,
і ўсё 'C' словы тут?

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
таму што цяпер, калі я хачу
шукаць яблык, я

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
як з вялікім O п
што мы абмяркоўвалі раней.

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
Мы проста па наіўнасці, выкарыстоўваючы літару 'A'
у адзіночку, таму што гэта проста і прыгожа.

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