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
І спеціально для учнів, які не є
обов'язково візуальне або математичне,

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