1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> СПІКЕР 1: Гаразд, так що це
CS50 Це кінець п'ятому тижні.

3
00:00:15,860 --> 00:00:19,220
І нагадаємо, що минулого разу ми
почав шукати в даних любитель

4
00:00:19,220 --> 00:00:22,310
структури, які почали вирішувати
проблеми, які почали вводити

5
00:00:22,310 --> 00:00:25,640
нові проблеми, але ключем до цього
був свого роду різьблення, що ми

6
00:00:25,640 --> 00:00:27,940
почав робити від вузла до вузла.

7
00:00:27,940 --> 00:00:30,085
Так що це, звичайно,
одноразово зв'язаний список.

8
00:00:30,085 --> 00:00:31,960
І односвязанни,
Я маю на увазі є тільки один

9
00:00:31,960 --> 00:00:33,380
нитка між кожним з цих вузлів.

10
00:00:33,380 --> 00:00:35,890
Виявляється, можна зробити любитель
речі, як двічі зв'язані списки

11
00:00:35,890 --> 00:00:38,470
в результаті чого у вас є стрілка
відбувається в обох напрямках, що

12
00:00:38,470 --> 00:00:40,320
може допомогти з деякими ефективності.

13
00:00:40,320 --> 00:00:42,000
Але це вирішити проблему?

14
00:00:42,000 --> 00:00:43,500
Які проблеми це вирішити так?

15
00:00:43,500 --> 00:00:46,620
Чому ми піклуємося в понеділок?

16
00:00:46,620 --> 00:00:49,820
Чому, в теорії, так і ми дбаємо в понеділок?

17
00:00:49,820 --> 00:00:50,630
Що це робить?

18
00:00:50,630 --> 00:00:51,950
>> АУДИТОРІЯ: Ми можемо динамічно змінити її розмір.

19
00:00:51,950 --> 00:00:53,740
>> СПІКЕР 1: Отже, ми можемо
динамічно змінити її розмір.

20
00:00:53,740 --> 00:00:54,710
Молодці вас обох.

21
00:00:54,710 --> 00:00:57,560
Таким чином, ви можете динамічно змінювати розмір цього
Структура даних, у той час як масив,

22
00:00:57,560 --> 00:01:00,760
відгук, ви повинні знати
апріорі, скільки місця ви хочете

23
00:01:00,760 --> 00:01:03,870
і якщо вам потрібно трохи більше
простір, ти ніби не пощастило.

24
00:01:03,870 --> 00:01:05,560
Ви повинні створити абсолютно новий масив.

25
00:01:05,560 --> 00:01:07,893
Ви повинні рухатися всі ваші
дані одного до іншого,

26
00:01:07,893 --> 00:01:10,600
зрештою звільнити старий масив
якщо ви можете, а потім продовжити.

27
00:01:10,600 --> 00:01:13,891
Які тільки відчуває себе дуже дорого і дуже
неефективно, і це дійсно може бути.

28
00:01:13,891 --> 00:01:14,890
Але це ще не все добре.

29
00:01:14,890 --> 00:01:18,180
Ми платимо ціну, що було одним
з більш очевидних цін ми

30
00:01:18,180 --> 00:01:20,550
платити за допомогою пов'язаного списку?

31
00:01:20,550 --> 00:01:22,825
>> АУДИТОРІЯ: Ми повинні використовувати
подвійний простір для кожного з них.

32
00:01:22,825 --> 00:01:25,200
СПІКЕР 1: Так, так що ми повинні
принаймні, в два рази більше простору.

33
00:01:25,200 --> 00:01:27,700
Насправді, я зрозумів, що це з картинки
навіть трохи вводить в оману,

34
00:01:27,700 --> 00:01:32,200
бо на CS50 IDE в багато сучасних
комп'ютери, покажчик або адреса

35
00:01:32,200 --> 00:01:33,700
насправді не чотири байти.

36
00:01:33,700 --> 00:01:36,090
Це дуже часто ці
днів восьмій байт, які

37
00:01:36,090 --> 00:01:38,530
означає самий нижній
прямокутники там в реальності

38
00:01:38,530 --> 00:01:40,900
є свого роду два рази
великий, як те, що я намалював,

39
00:01:40,900 --> 00:01:44,409
що означає, що ви використовуєте в три рази
багато місця, як ми могли б в іншому випадку.

40
00:01:44,409 --> 00:01:46,700
Тепер у той же час, ми
ще говоримо байт, вірно?

41
00:01:46,700 --> 00:01:49,140
Ми не говоримо обов'язково
мегабайтах або гігабайтах,

42
00:01:49,140 --> 00:01:51,000
якщо цих структур даних не отримати великий.

43
00:01:51,000 --> 00:01:54,510
>> І тому сьогодні ми починаємо розглядати
як ми могли б досліджувати дані

44
00:01:54,510 --> 00:01:57,310
більш ефективно, якщо в
факт, що дані стає більше.

45
00:01:57,310 --> 00:02:00,360
Але давайте спробуємо канонізувати
Перші операції

46
00:02:00,360 --> 00:02:02,460
що ви можете зробити на них
види структур даних.

47
00:02:02,460 --> 00:02:04,790
Так щось подібне пов'язано
Список в цілому підтримує

48
00:02:04,790 --> 00:02:07,514
Операції подобається видалити,
вставити, і пошук.

49
00:02:07,514 --> 00:02:08,639
І що я маю на увазі, що?

50
00:02:08,639 --> 00:02:11,222
Це просто означає, що зазвичай
якщо люди використовують зв'язаний список,

51
00:02:11,222 --> 00:02:14,287
вони або хтось ще реалізовані
функції, такі як видалення, вставка,

52
00:02:14,287 --> 00:02:16,120
і пошук, так що ви можете
насправді щось зробити

53
00:02:16,120 --> 00:02:18,030
корисно зі структурою даних.

54
00:02:18,030 --> 00:02:20,760
Отже, давайте поглянемо
на те, як ми могли б реалізувати

55
00:02:20,760 --> 00:02:24,530
деякий код для пов'язаного списку наступним чином.

56
00:02:24,530 --> 00:02:27,885
>> Так що це лише деякі С-код,
навіть не повна програма

57
00:02:27,885 --> 00:02:29,260
що я дійсно швидко спорудив.

58
00:02:29,260 --> 00:02:32,300
Це не онлайн у розподілі
Код, тому що він не буде реально працювати.

59
00:02:32,300 --> 00:02:33,790
Але зверніть увагу, Я тільки
з коментарем сказав,

60
00:02:33,790 --> 00:02:36,130
точка точка точка, є щось
там, точка точка точка, щось там.

61
00:02:36,130 --> 00:02:38,410
І давайте просто подивимося на
те, що соковиті частини.

62
00:02:38,410 --> 00:02:40,790
Так що на третій лінії,
Нагадаємо, що це тепер

63
00:02:40,790 --> 00:02:45,960
Ми запропонували оголосити вузол останній
Час, один з тих прямокутних об'єктів.

64
00:02:45,960 --> 00:02:48,790
Він має Int, що ми назвемо N,
але ми могли б назвати це що-небудь,

65
00:02:48,790 --> 00:02:51,920
а потім структура вузла зірка називається поруч.

66
00:02:51,920 --> 00:02:55,520
І тільки, щоб бути ясним, що в другому
лінія, на шостому рядку, що це таке?

67
00:02:55,520 --> 00:02:57,930
Що він робить для нас?

68
00:02:57,930 --> 00:03:01,044
Тому що, звичайно, виглядає більш
загадковими, ніж наші звичайні змінні.

69
00:03:01,044 --> 00:03:02,740
>> АУДИТОРІЯ: Це змушує його рухатися по одному.

70
00:03:02,740 --> 00:03:04,650
>> СПІКЕР 1: змушує його рухатися по одному.

71
00:03:04,650 --> 00:03:08,580
І якщо бути більш точним,
він буде зберігати адреса

72
00:03:08,580 --> 00:03:11,582
вузла, який призначається, щоб бути
семантично поруч з ним, вірно?

73
00:03:11,582 --> 00:03:13,540
Так що не збирається
обов'язково рухатися нічого.

74
00:03:13,540 --> 00:03:15,290
Це просто буде
зберігати значення, яке

75
00:03:15,290 --> 00:03:17,170
буде адреса
якогось іншого вузла,

76
00:03:17,170 --> 00:03:20,810
і ось чому ми сказали структура
вузол зірка, зірка, що позначає

77
00:03:20,810 --> 00:03:22,370
покажчик або адресу.

78
00:03:22,370 --> 00:03:26,390
ОК, так що тепер якщо припустити, що ми маємо
це N доступні для нас, і давайте

79
00:03:26,390 --> 00:03:29,490
Припустимо, що хтось ще
вставляється цілу купу цілих чисел

80
00:03:29,490 --> 00:03:30,400
у зв'язаному списку.

81
00:03:30,400 --> 00:03:35,640
І, що пов'язано список
вказує якийсь момент

82
00:03:35,640 --> 00:03:39,040
змінна називається список, що це
пройшов тут у якості параметра,

83
00:03:39,040 --> 00:03:43,120
як я можу йти про лінії
14 здійсненні пошуку?

84
00:03:43,120 --> 00:03:45,990
Іншими словами, якщо я реалізую
Функція, мета якого в житті

85
00:03:45,990 --> 00:03:48,889
це прийняти Int і потім
початок пов'язаного списку,

86
00:03:48,889 --> 00:03:50,430
що покажчик на зв'язаний список.

87
00:03:50,430 --> 00:03:52,992
Як перші, хто я думаю, Девід
був наш волонтер в понеділок,

88
00:03:52,992 --> 00:03:54,700
він, вказуючи на
вся зв'язаний список,

89
00:03:54,700 --> 00:03:57,820
Це як якщо б ми передаємо
Девід, як наш аргумент тут.

90
00:03:57,820 --> 00:03:59,990
Як ми можемо йти про проходження цей список?

91
00:03:59,990 --> 00:04:04,640
Що ж, виявляється, що, хоча
покажчики є відносно новими в даний час для нас,

92
00:04:04,640 --> 00:04:07,010
ми можемо зробити це відносно
прямо.

93
00:04:07,010 --> 00:04:09,500
>> Я збираюся йти вперед і
оголосити тимчасову змінну, що

94
00:04:09,500 --> 00:04:12,364
за угодою тільки збирається
щоб назвати покажчик, або PTR,

95
00:04:12,364 --> 00:04:14,030
але ви могли б назвати це все, що ви хочете.

96
00:04:14,030 --> 00:04:16,470
І я збираюся ініціалізації
це на початку списку.

97
00:04:16,470 --> 00:04:20,050
Таким чином, ви можете б думаю це
а мені вчителі днях,

98
00:04:20,050 --> 00:04:23,580
вид, вказуючи на когось
серед наших людей в якості добровольців.

99
00:04:23,580 --> 00:04:26,470
Так що я тимчасову змінну, що це
просто вказуючи на те ж саме

100
00:04:26,470 --> 00:04:31,390
що наш збігом імені
Робота на громадських засадах Давид вказував.

101
00:04:31,390 --> 00:04:35,440
Тепер у той час як покажчик
не нульовий, бо відгук

102
00:04:35,440 --> 00:04:40,350
що нульова деякі особливе значення сторожового
розмежовує кінець списку,

103
00:04:40,350 --> 00:04:44,280
так що поки я не вказуючи на
земля, як наш останній волонтер

104
00:04:44,280 --> 00:04:47,190
було, давайте йти вперед
і виконайте такі дії.

105
00:04:47,190 --> 00:04:51,820
Якщо pointer-- і тепер я як би хочу
робити те, що ми зробили з учнем

106
00:04:51,820 --> 00:04:57,410
structure-- якщо покажчик точка поруч
equals-- швидше, якщо покажчик точка N дорівнює

107
00:04:57,410 --> 00:05:02,290
дорівнює змінна N, то
Аргумент, який був прийнятий в,

108
00:05:02,290 --> 00:05:05,370
то я хочу, щоб йти вперед
і сказати, повернутися правда.

109
00:05:05,370 --> 00:05:11,020
Я знайшов номер N всередині
один з вузлів мого пов'язаного списку.

110
00:05:11,020 --> 00:05:13,500
Але більше крапка не
працює в даному контексті,

111
00:05:13,500 --> 00:05:17,260
бо покажчик, PTR, це
дійсно покажчик, адреса,

112
00:05:17,260 --> 00:05:20,632
ми насправді можемо чудово
використовувати нарешті шматок синтаксису

113
00:05:20,632 --> 00:05:22,590
що вигляд робить
інтуїтивне відчуття, а насправді

114
00:05:22,590 --> 00:05:27,870
використовувати стрілку тут, що означає, йдуть від
що звернення до цілого там в.

115
00:05:27,870 --> 00:05:30,160
Так що це дуже схоже на
дух оператора точка,

116
00:05:30,160 --> 00:05:33,860
а тому, що покажчик не є покажчиком
і сам по собі не фактичний структура,

117
00:05:33,860 --> 00:05:35,380
ми просто використовувати стрілку.

118
00:05:35,380 --> 00:05:40,620
>> Так що, якщо поточний вузол, що Я,
тимчасова змінна, я, вказуючи на

119
00:05:40,620 --> 00:05:43,060
НЕ N, те, що я хочу зробити?

120
00:05:43,060 --> 00:05:45,910
Ну, з моїм добровольцях
що у нас тут днями,

121
00:05:45,910 --> 00:05:49,710
якщо мій перший чоловік не той, який я
хочу, і, можливо, другий людина не

122
00:05:49,710 --> 00:05:52,660
що я хочу, і третій, я
потрібно тримати фізичного переміщення.

123
00:05:52,660 --> 00:05:54,690
Як як я крок через список?

124
00:05:54,690 --> 00:05:57,470
Коли ми були масив, вам
тільки що зробив, як я плюс плюс.

125
00:05:57,470 --> 00:06:03,660
Але в даному випадку, достатньо
зробити покажчик, отримує, покажчик, поруч.

126
00:06:03,660 --> 00:06:07,580
Іншими словами, наступне поле
це, як і всі лівої руки

127
00:06:07,580 --> 00:06:10,880
що наші добровольці в понеділок
використовували, щоб вказати на якийсь інший вузол.

128
00:06:10,880 --> 00:06:12,890
Ті були їхні найближчі сусіди.

129
00:06:12,890 --> 00:06:17,060
>> Так що, якщо я хочу, щоб пройти через цей список,
Я не можу просто зробити я плюс плюс більше,

130
00:06:17,060 --> 00:06:20,120
Я замість цього сказати
Я, покажчик, буде

131
00:06:20,120 --> 00:06:24,650
рівним незалежно від наступного поля,
Наступне поле, наступне поле,

132
00:06:24,650 --> 00:06:28,350
після всіх цих лівої руки
що у нас на сцені, вказуючи

133
00:06:28,350 --> 00:06:30,000
в деяких наступних значень.

134
00:06:30,000 --> 00:06:32,590
І якщо я через
що вся ітерація,

135
00:06:32,590 --> 00:06:39,330
І, нарешті, я вдарив порожній, не маючи
знайшов ще N, я просто повернутися помилковим.

136
00:06:39,330 --> 00:06:44,100
Отже, ще раз, все, що ми робимо тут,
відповідно до картини хвилину тому,

137
00:06:44,100 --> 00:06:47,840
починає, вказуючи на
початку списку імовірно.

138
00:06:47,840 --> 00:06:50,970
І тоді я перевіряю, це значення
Я шукаю дорівнює дев'яти?

139
00:06:50,970 --> 00:06:52,650
Якщо це так, я повертаюся правда, і я зробити.

140
00:06:52,650 --> 00:06:56,450
Якщо ні, то я оновити мою руку,
АКА покажчик, щоб вказати

141
00:06:56,450 --> 00:06:59,540
на місці на наступний стріли, і
те місце в наступному Ерроу,

142
00:06:59,540 --> 00:07:00,480
і в наступному.

143
00:07:00,480 --> 00:07:03,770
Я просто йшов через цей масив.

144
00:07:03,770 --> 00:07:06,010
>> Отже, ще раз, хто піклується?

145
00:07:06,010 --> 00:07:07,861
Подобається те, що це інгредієнт для?

146
00:07:07,861 --> 00:07:10,360
Ну, пам'ятаєте, що ми ввели
поняття стека, який

147
00:07:10,360 --> 00:07:15,400
це ввести абстрактний дані, оскільки це
не є С, що, це не CS50 річ,

148
00:07:15,400 --> 00:07:19,430
це абстрактна ідея, це ідея
укладка речей на верхній частині один з одним

149
00:07:19,430 --> 00:07:21,820
, Які можуть бути реалізовані в
пучки різними способами.

150
00:07:21,820 --> 00:07:25,600
І один із способів ми запропонували була з
масив, або зі зв'язаним списком.

151
00:07:25,600 --> 00:07:29,570
І виходить, що канонічно, А
Стек підтримує, щонайменше дві операції.

152
00:07:29,570 --> 00:07:32,320
І Buzz слова поштовх, щоб
натиснути щось в стек,

153
00:07:32,320 --> 00:07:34,770
як новий лоток в
їдальня, або поп,

154
00:07:34,770 --> 00:07:39,000
це означає, щоб видалити верхній
лоток з стека в їдальні

155
00:07:39,000 --> 00:07:41,500
зал, а потім, можливо, деякі
інші операції, а також.

156
00:07:41,500 --> 00:07:45,770
Так як ми могли б визначити структуру
що ми зараз виклику стек?

157
00:07:45,770 --> 00:07:50,020
>> Ну, у нас є все необхідне умова
Синтаксис в нашому розпорядженні в С. я кажу,

158
00:07:50,020 --> 00:07:53,830
дати мені визначення типу в
на структуру всередині стопки,

159
00:07:53,830 --> 00:07:58,030
Я хочу сказати, це масив, в А
ціла купа цифр, а потім розмір.

160
00:07:58,030 --> 00:08:00,930
Отже, іншими словами, якщо я хочу
здійснити це в коді,

161
00:08:00,930 --> 00:08:03,830
дозвольте мені піти і просто вид
малювати те, що це говорить.

162
00:08:03,830 --> 00:08:06,317
Таким чином, це говорить, дайте мені
Структура, що є масив,

163
00:08:06,317 --> 00:08:09,400
і я не знаю, що потужність,
це мабуть деяка константа, що я

164
00:08:09,400 --> 00:08:10,858
визначаються в іншому місці, і це нормально.

165
00:08:10,858 --> 00:08:15,260
Але припустимо, це всього лише один,
два, три, чотири, п'ять.

166
00:08:15,260 --> 00:08:16,700
Так потужність 5.

167
00:08:16,700 --> 00:08:21,730
Цей елемент всередині мого
Структура буде називатися число.

168
00:08:21,730 --> 00:08:24,020
А потім мені потрібен
мабуть, іншої змінної

169
00:08:24,020 --> 00:08:27,814
називається розмір, який спочатку я збираюся
обумовлювати встановлюється на нуль.

170
00:08:27,814 --> 00:08:29,730
Якщо немає нічого
стек, розмір дорівнює нулю,

171
00:08:29,730 --> 00:08:31,420
і це значення сміття в цифрах.

172
00:08:31,420 --> 00:08:33,450
Я поняття не маю, що там просто немає.

173
00:08:33,450 --> 00:08:36,059
>> Так що, якщо я хочу, щоб підштовхнути
то в стек,

174
00:08:36,059 --> 00:08:40,780
Вважаю, я викликати функцію поштовх, і
Я говорю натиснути 50, як і число 50,

175
00:08:40,780 --> 00:08:44,090
де ви могли б запропонувати
Я малюю його в цьому масиві?

176
00:08:44,090 --> 00:08:47,124
Там в п'ять різних можливих відповідей.

177
00:08:47,124 --> 00:08:48,790
Де ви хочете, щоб підштовхнути число 50?

178
00:08:48,790 --> 00:08:51,899
Якщо мета тут, знову ж таки, називаємо
Функція поштовх, проходять у якості аргументу

179
00:08:51,899 --> 00:08:52,940
50, де я поклав його?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
П'ять possible-- 20% шанс
гадати правильно.

182
00:08:59,052 --> 00:08:59,896
Так?

183
00:08:59,896 --> 00:09:00,740
>> АУДИТОРІЯ: Далекий право.

184
00:09:00,740 --> 00:09:01,990
>> СПІКЕР 1: Далекий право.

185
00:09:01,990 --> 00:09:08,359
Існує в даний час 25% шанс
гадати правильно.

186
00:09:08,359 --> 00:09:09,650
Так що буде насправді буде в порядку.

187
00:09:09,650 --> 00:09:12,770
За угодою, я скажу з масивом,
ми, як правило, починають з лівої,

188
00:09:12,770 --> 00:09:14,519
але ми, безумовно, може
почати з правої.

189
00:09:14,519 --> 00:09:17,478
Таким чином, спойлер тут буде я
ймовірно, збирається залучити його ліворуч,

190
00:09:17,478 --> 00:09:20,060
Як і в звичайному масиві де
Я почати рухатися зліва направо.

191
00:09:20,060 --> 00:09:21,780
Але якщо ви можете привернути
арифметичне, відмінно.

192
00:09:21,780 --> 00:09:23,060
Це просто не звичайний.

193
00:09:23,060 --> 00:09:24,880
ОК, мені потрібно, щоб зробити один
більше змін, хоча.

194
00:09:24,880 --> 00:09:27,710
Тепер, коли я штовхнув щось
стек, що далі?

195
00:09:27,710 --> 00:09:29,400
>> Гаразд, у мене є, щоб збільшити розмір.

196
00:09:29,400 --> 00:09:32,600
Отже, дозвольте мені йти вперед і просто
оновити це, який дорівнював нулю.

197
00:09:32,600 --> 00:09:35,950
І замість того, в даний час, я йду
покласти в вартості одного.

198
00:09:35,950 --> 00:09:39,460
А тепер припустимо, я натискаю іншу
Кількість в стек, як 51.

199
00:09:39,460 --> 00:09:42,680
Ну, я повинен зробити ще один
зміна, яка до розміру двох.

200
00:09:42,680 --> 00:09:46,100
А потім думаю, я натискаю ще один
Кількість в стек, як 61,

201
00:09:46,100 --> 00:09:52,530
Тепер мені потрібно, щоб оновити ще один розмір
час і отримати значення 3 в якості розміру.

202
00:09:52,530 --> 00:09:54,690
І тепер, я називаю поп-музики.

203
00:09:54,690 --> 00:09:57,250
Тепер поп, за угодою,
не брати аргумент.

204
00:09:57,250 --> 00:10:00,430
Зі стеком, вся
точка метафори лоток

205
00:10:00,430 --> 00:10:03,450
є те, що ви не на свій розсуд
піти отримати цей лоток, все можна зробити

206
00:10:03,450 --> 00:10:06,330
поп верхній один з
стек, тільки тому, що.

207
00:10:06,330 --> 00:10:08,010
Це те, що ця структура даних робить.

208
00:10:08,010 --> 00:10:12,250
>> Отже, за цією логікою, якщо я
кажуть поп, те, що приходить від?

209
00:10:12,250 --> 00:10:13,080
Так 61.

210
00:10:13,080 --> 00:10:15,402
Так що насправді комп'ютер
збираємося робити в пам'яті?

211
00:10:15,402 --> 00:10:16,610
Що мій код потрібно зробити?

212
00:10:16,610 --> 00:10:20,330
Що ви могли б запропонувати
ми міняємо на екрані?

213
00:10:20,330 --> 00:10:23,410
Що має змінитися?

214
00:10:23,410 --> 00:10:24,960
На жаль?

215
00:10:24,960 --> 00:10:26,334
Так ми позбудемося 61.

216
00:10:26,334 --> 00:10:27,500
Так що я можу впевнено зробити.

217
00:10:27,500 --> 00:10:28,640
І я можу позбутися від 61.

218
00:10:28,640 --> 00:10:30,980
І тоді те, що інші
зміна має статися?

219
00:10:30,980 --> 00:10:33,160
Розмір, ймовірно, має повернутися до двох.

220
00:10:33,160 --> 00:10:34,210
І так, що все в порядку.

221
00:10:34,210 --> 00:10:36,690
Але зачекайте хвилину, розмір
Хвилину тому було три.

222
00:10:36,690 --> 00:10:38,240
Давайте просто зробити швидку перевірку осудності.

223
00:10:38,240 --> 00:10:41,810
Як ми знаємо, що ми
хотів, щоб позбутися від 61?

224
00:10:41,810 --> 00:10:42,760
Тому що ми з'являтися.

225
00:10:42,760 --> 00:10:46,450
І тому в мене є цей другий розмір власності.

226
00:10:46,450 --> 00:10:48,470
>> Почекай, я
згадуючи другого тижня

227
00:10:48,470 --> 00:10:51,660
коли ми почали говорити про
масиви, де це місце нульовий,

228
00:10:51,660 --> 00:10:55,920
це було місце одне, це було місце
два, це розташування три, чотири,

229
00:10:55,920 --> 00:10:58,460
це виглядає як
взаємозв'язок між розміром

230
00:10:58,460 --> 00:11:02,780
і елемент, який я хочу, щоб видалити
з масиву, здається, просто що?

231
00:11:02,780 --> 00:11:05,120
Розмір мінус один.

232
00:11:05,120 --> 00:11:07,786
І ось як, як люди
ми знаємо, 61 на першому місці.

233
00:11:07,786 --> 00:11:09,160
Як це комп'ютер буде знати?

234
00:11:09,160 --> 00:11:11,701
Коли ваш код, де ви, ймовірно
хочу зробити розмір мінус один,

235
00:11:11,701 --> 00:11:14,950
так трьох мінус один дорівнює двом, і що
означає, що ми хочемо, щоб позбутися від 61.

236
00:11:14,950 --> 00:11:18,000
І тоді ми дійсно можемо оновити
розмір так, щоб розмір в даний час

237
00:11:18,000 --> 00:11:20,300
йде від трьох до двох.

238
00:11:20,300 --> 00:11:24,520
І тільки, щоб бути педантичним, я збираюся
припустити, що я зробив, вірно?

239
00:11:24,520 --> 00:11:27,660
Ви інтуїтивно запропонував
правильно я повинен позбутися 61.

240
00:11:27,660 --> 00:11:30,700
Але не я начебто
начебто позбулися 61?

241
00:11:30,700 --> 00:11:33,790
Я забув ефективно
що це насправді є.

242
00:11:33,790 --> 00:11:37,680
І згадайте PSET4, якщо ви читали
стаття про судово-медичної експертизи, то у форматі PDF

243
00:11:37,680 --> 00:11:40,780
що у нас, ви, хлопці читати, або ви
читатиме на цьому тижні PSET4.

244
00:11:40,780 --> 00:11:44,300
Нагадаємо, що це насправді доречні для
вся ідея комп'ютерної експертизи.

245
00:11:44,300 --> 00:11:47,820
Що комп'ютер взагалі робить це
він просто забуває, де щось,

246
00:11:47,820 --> 00:11:51,300
але це не пішли і, як
спробувати подряпати його або перевизначення

247
00:11:51,300 --> 00:11:54,560
ці біти з нулів і одиниць
або деякий інший випадковим чином

248
00:11:54,560 --> 00:11:56,690
якщо ви самі не роблять це свідомо.

249
00:11:56,690 --> 00:11:58,930
Так ваша інтуїція була
Добре, давайте позбутися 61.

250
00:11:58,930 --> 00:12:00,650
Але насправді, ми не повинні турбуватися.

251
00:12:00,650 --> 00:12:04,040
Нам просто потрібно забувати, що
це там, змінивши наш розмір.

252
00:12:04,040 --> 00:12:05,662
>> Тепер є проблема з цим стеком.

253
00:12:05,662 --> 00:12:07,620
Якщо я штовхати речі
стек, що

254
00:12:07,620 --> 00:12:11,167
Очевидно, відбудеться
За кілька моментів часу?

255
00:12:11,167 --> 00:12:12,500
Ми збираємося запустити з космосу.

256
00:12:12,500 --> 00:12:13,580
І що нам робити?

257
00:12:13,580 --> 00:12:14,680
Ми начебто болтах.

258
00:12:14,680 --> 00:12:19,000
Ця реалізація не дозволяє
нам розмір масиву, тому що за допомогою

259
00:12:19,000 --> 00:12:21,240
цей синтаксис, якщо ви
згадайте другого тижня,

260
00:12:21,240 --> 00:12:23,520
коли ви оголосили
розмір масиву,

261
00:12:23,520 --> 00:12:26,780
ми не бачили механізм ще десь
Ви можете змінити розмір масиву.

262
00:12:26,780 --> 00:12:29,020
І справді С не мають цю функцію.

263
00:12:29,020 --> 00:12:32,524
Якщо ви говорите, дайте мені п'ять
Nths, називають їх число,

264
00:12:32,524 --> 00:12:33,940
це все, що ви збираєтеся отримати.

265
00:12:33,940 --> 00:12:38,790
Таким чином, ми тепер робити, як понеділок, є
здатність виражати рішення

266
00:12:38,790 --> 00:12:42,480
хоча, ми просто потрібно налаштувати
визначення нашої стека

267
00:12:42,480 --> 00:12:46,840
щоб не бути деяких жорстко масив,
а просто зберігати адреси.

268
00:12:46,840 --> 00:12:47,890
>> Тепер, чому це?

269
00:12:47,890 --> 00:12:51,690
Тепер ми просто повинні бути комфортно з
той факт, що, коли працює мій програми,

270
00:12:51,690 --> 00:12:53,730
Я, ймовірно, збирається
повинні запитати людину,

271
00:12:53,730 --> 00:12:55,110
скільки номерів ви хочете зберегти?

272
00:12:55,110 --> 00:12:56,776
Таким чином, вхід повинен звідкись.

273
00:12:56,776 --> 00:12:59,140
Але як тільки я знаю, що
число, то я можу тільки

274
00:12:59,140 --> 00:13:02,470
використовувати те, що працювати, щоб дати
мені шматок пам'яті?

275
00:13:02,470 --> 00:13:03,580
Я можу використовувати Танос.

276
00:13:03,580 --> 00:13:06,710
І я можу сказати, будь-яку кількість
байт я хочу повернутися на ці Nths.

277
00:13:06,710 --> 00:13:10,910
І все, що потрібно зберігати в цифрах
Мінлива тут всередині цієї структури

278
00:13:10,910 --> 00:13:13,480
повинно бути що?

279
00:13:13,480 --> 00:13:18,440
Що насправді відбувається в
Цифри в цьому випадку?

280
00:13:18,440 --> 00:13:21,300
Так, це покажчик на перший
байт цього шматка пам'яті,

281
00:13:21,300 --> 00:13:24,940
або, більш конкретно, адреса
з перших з цих байт.

282
00:13:24,940 --> 00:13:27,300
Не має значення, якщо це один
байт або байт, млрд

283
00:13:27,300 --> 00:13:28,890
Мені просто потрібно, щоб піклуватися про першу.

284
00:13:28,890 --> 00:13:31,530
Тому що те, що Танос гарантії і
мої операційної системи гарантій,

285
00:13:31,530 --> 00:13:34,170
є те, що шматок пам'яті I
отримати, він збирається бути суміжними.

286
00:13:34,170 --> 00:13:35,378
Там не буде прогалин.

287
00:13:35,378 --> 00:13:38,576
Так що, якщо я попросив 50
байт або 1000 байт,

288
00:13:38,576 --> 00:13:40,450
вони все буде
спина до спини до спини.

289
00:13:40,450 --> 00:13:44,500
І так довго, як я пам'ятаю, як великий, як
багато я попросив, все мені потрібно знати

290
00:13:44,500 --> 00:13:46,230
перший такий адресу.

291
00:13:46,230 --> 00:13:48,660
>> Так що тепер у нас є можливість в коді.

292
00:13:48,660 --> 00:13:51,280
Хоча і він збирається взяти нас
більше часу, щоб написати цю гру,

293
00:13:51,280 --> 00:13:55,900
ми могли тепер перерозподілити цю пам'ять
просто зберігати різні адреси є

294
00:13:55,900 --> 00:13:59,060
якщо ми хочемо, щоб більше або навіть
менше шматок пам'яті.

295
00:13:59,060 --> 00:14:00,170
Так от, щоб компроміс.

296
00:14:00,170 --> 00:14:01,360
Тепер ми отримуємо динаміку.

297
00:14:01,360 --> 00:14:03,350
У нас ще є
contiguousness я стверджуючи.

298
00:14:03,350 --> 00:14:05,881
Тому Танос дасть нам
безперервний шматок пам'яті.

299
00:14:05,881 --> 00:14:08,630
Але це буде біль у
шия для нас, програміст,

300
00:14:08,630 --> 00:14:09,770
насправді код до.

301
00:14:09,770 --> 00:14:10,730
Це просто більше роботи.

302
00:14:10,730 --> 00:14:13,930
Ми повинні код схоже на те, що я був
стукати з усього мить тому.

303
00:14:13,930 --> 00:14:16,120
Дуже здійснимо, але це додає складності.

304
00:14:16,120 --> 00:14:19,520
І так разів розробник, програміст
Час ще один ресурс

305
00:14:19,520 --> 00:14:22,520
що ми могли б потрібно витрачати
деякий час, щоб отримати нові можливості.

306
00:14:22,520 --> 00:14:24,020
І тоді, звичайно, є черги.

307
00:14:24,020 --> 00:14:26,227
Ми не будемо зупинятися на цьому
одним дуже докладно.

308
00:14:26,227 --> 00:14:27,560
Але це дуже схоже за духом.

309
00:14:27,560 --> 00:14:31,220
Я міг би реалізувати чергу, і
його відповідні операції,

310
00:14:31,220 --> 00:14:35,660
Ставити або черги, як додати або видалити,
це просто любитель спосіб сказати це,

311
00:14:35,660 --> 00:14:38,100
Ставити або черги, як слід.

312
00:14:38,100 --> 00:14:41,170
Я можу тільки дати собі-структуру
що знову є масив ряду, в

313
00:14:41,170 --> 00:14:44,000
що знову має розмір,
але чому зараз мені потрібно

314
00:14:44,000 --> 00:14:46,940
відслідковувати передньої черзі?

315
00:14:46,940 --> 00:14:50,630
Я не знаю, потрібно
передня мого стека.

316
00:14:50,630 --> 00:14:53,570
Ну, якщо я знову для
queue-- давайте просто важко

317
00:14:53,570 --> 00:14:57,870
його код як мають, як п'ять
цілі числа в тут потенційно.

318
00:14:57,870 --> 00:15:00,940
Таким чином, це нуль, один, два, три, чотири.

319
00:15:00,940 --> 00:15:03,430
Це буде
звані знову номера.

320
00:15:03,430 --> 00:15:06,940
І це буде називатися розмір.

321
00:15:06,940 --> 00:15:10,056
>> Чому це не достатньо
мати тільки розмір?

322
00:15:10,056 --> 00:15:11,680
Ну, давайте штовхати ці ж цифри на.

323
00:15:11,680 --> 00:15:14,220
Так що я pushed-- я в чергу, або штовхнув.

324
00:15:14,220 --> 00:15:20,150
Тепер я в чергу 50, а потім
51, а потім 61, і крапка точка точка.

325
00:15:20,150 --> 00:15:21,070
Так от поставити в чергу.

326
00:15:21,070 --> 00:15:23,176
Я в черзі 50, то 51, то 61.

327
00:15:23,176 --> 00:15:25,050
І, що виглядає ідентично
в стек досі,

328
00:15:25,050 --> 00:15:27,190
крім мені потрібно зробити одна зміна.

329
00:15:27,190 --> 00:15:33,680
Мені потрібно, щоб оновити цей розмір, так що я йду
від нуля до одиниці до двох-трьох Тепер.

330
00:15:33,680 --> 00:15:35,760
Як з черги?

331
00:15:35,760 --> 00:15:36,890
Що відбувається з DEQUEUE?

332
00:15:36,890 --> 00:15:41,950
Хто повинен прийти з цього списку в першу чергу
якщо це лінія на Apple Store?

333
00:15:41,950 --> 00:15:42,780
Так 50.

334
00:15:42,780 --> 00:15:44,700
Так що це свого роду складніше цього разу.

335
00:15:44,700 --> 00:15:47,880
У той час як останній раз це було супер
просто, щоб просто робити розмір мінус один,

336
00:15:47,880 --> 00:15:51,440
Я до кінця мого масиву ефективно
де цифри, це знімає 61.

337
00:15:51,440 --> 00:15:52,920
Але я не хочу, щоб видалити 61.

338
00:15:52,920 --> 00:15:55,030
Я хочу взяти 50, які
був там в 5:00

339
00:15:55,030 --> 00:15:56,790
вибудовуватися для
Новий iPhone або ще багато чого.

340
00:15:56,790 --> 00:16:01,200
І так, щоб позбутися від 50, я
не можете просто зробити це, чи не так?

341
00:16:01,200 --> 00:16:02,547
Я можу викреслити 50.

342
00:16:02,547 --> 00:16:04,380
Але ми тільки що сказали, ми
не повинні бути настільки анальний

343
00:16:04,380 --> 00:16:06,330
щоб видряпати або приховати дані.

344
00:16:06,330 --> 00:16:08,090
Ми можемо просто забути, де вона є.

345
00:16:08,090 --> 00:16:12,330
>> Але якщо я можу змінити мій розмір тепер
два, це достатньо інформації

346
00:16:12,330 --> 00:16:15,711
щоб знати, що відбувається в моєму черзі?

347
00:16:15,711 --> 00:16:16,680
Не зовсім.

348
00:16:16,680 --> 00:16:19,830
Як мій розмір в два, але
де ж черзі починають,

349
00:16:19,830 --> 00:16:22,980
особливо якщо я досі
ті ж номери в пам'яті.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Тому мені потрібно пам'ятати,
Тепер, коли фронт.

352
00:16:27,090 --> 00:16:29,630
І таким чином, я запропонував до
там, ми тільки що називається

353
00:16:29,630 --> 00:16:33,729
N-й фронт, чий початковий
Значення має бути що?

354
00:16:33,729 --> 00:16:35,270
Нуль, тільки початок списку.

355
00:16:35,270 --> 00:16:40,876
Але тепер на додаток до зменшуючи
розмір, ми просто збільшуємо фронт.

356
00:16:40,876 --> 00:16:42,000
Тепер ось інша проблема.

357
00:16:42,000 --> 00:16:43,030
Тому, як тільки я весь час.

358
00:16:43,030 --> 00:16:47,520
Припустимо, що це число
як 121, 124, а потім, чорт візьми,

359
00:16:47,520 --> 00:16:48,610
Я з космосу.

360
00:16:48,610 --> 00:16:50,390
Але зачекайте хвилину, я не є.

361
00:16:50,390 --> 00:16:55,630
Таким чином, на даний момент в історії,
Припустимо, що розмір одного, двох,

362
00:16:55,630 --> 00:17:00,370
три, чотири, так що припустимо, що
розмір чотирьох, передня одна,

363
00:17:00,370 --> 00:17:01,621
так 51 на фронті.

364
00:17:01,621 --> 00:17:04,329
Я хочу поставити ще один номер тут,
але, чорт візьми, я з космосу.

365
00:17:04,329 --> 00:17:06,710
Але я не дуже, чи не так?

366
00:17:06,710 --> 00:17:11,192
Де я можу поставити деякі
додаткова вартість, як 171?

367
00:17:11,192 --> 00:17:13,400
Так, я міг тільки частково
повернутися туди, вірно?

368
00:17:13,400 --> 00:17:18,161
А потім закреслити 50, або
просто переписати його з 171.

369
00:17:18,161 --> 00:17:20,410
І якщо вам цікаво, чому
наші номери отримав так випадково,

370
00:17:20,410 --> 00:17:24,150
вони зазвичай прийнято комп'ютер
наука курси в Гарварді після CS50.

371
00:17:24,150 --> 00:17:27,510
Але це був хороший оптимізація,
тому що тепер я не витрачати простір.

372
00:17:27,510 --> 00:17:30,750
Я досі повинні пам'ятати,
наскільки велика ця річ спільна.

373
00:17:30,750 --> 00:17:31,500
Це п'ять всього.

374
00:17:31,500 --> 00:17:33,375
Тому що я не хочу, щоб
почати перезапис 51.

375
00:17:33,375 --> 00:17:36,260
Так що тепер я як і раніше з космосу,
так само проблема, що й раніше.

376
00:17:36,260 --> 00:17:39,140
Але ви можете побачити, як в даний час
в коді, ви, ймовірно,

377
00:17:39,140 --> 00:17:41,910
потрібно написати трохи більше
Складність, щоб це відбулося.

378
00:17:41,910 --> 00:17:44,510
І справді, те, що оператор
в С, ймовірно, дозволяє

379
00:17:44,510 --> 00:17:48,110
Ви чарівним зробити це округлість?

380
00:17:48,110 --> 00:17:50,160
Та оператор по модулю,
знак відсотка.

381
00:17:50,160 --> 00:17:53,160
Так що круто про черги,
хоча ми зберегти малюнок масиви

382
00:17:53,160 --> 00:17:56,520
як ці, як прямих, якщо ви
вид думаю про це, як вигину

383
00:17:56,520 --> 00:18:00,341
навколо, як коло, то просто
інтуїтивно вид роботи розумово

384
00:18:00,341 --> 00:18:01,590
Я думаю, що трохи чистішим.

385
00:18:01,590 --> 00:18:05,190
Ви все одно доведеться здійснювати
що ментальна модель в коді.

386
00:18:05,190 --> 00:18:07,550
Так що не так уже й важко,
в кінцевому рахунку, реалізації,

387
00:18:07,550 --> 00:18:12,430
але ми як і раніше втрачають размер-- скоріше,
Можливість змінювати розмір, якщо ми не зробимо це.

388
00:18:12,430 --> 00:18:15,310
>> Ми повинні позбутися від масиву, ми
замінити його з одного покажчика,

389
00:18:15,310 --> 00:18:20,010
а потім десь в моєму коді я отримав
подзвоніть, які функції насправді створити

390
00:18:20,010 --> 00:18:23,720
масив звані цифри?

391
00:18:23,720 --> 00:18:26,190
Маллок, або інші подібні
Функція, точно.

392
00:18:26,190 --> 00:18:30,481
Будь-які питання по стеків або черг.

393
00:18:30,481 --> 00:18:30,980
Так?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Гарне питання.

396
00:18:34,240 --> 00:18:35,830
Що б ви модулю використовувати тут.

397
00:18:35,830 --> 00:18:38,520
Так як правило, при використанні
мод, ви могли б зробити це

398
00:18:38,520 --> 00:18:40,620
з розміром
Вся структура даних.

399
00:18:40,620 --> 00:18:44,120
Так щось на зразок п'яти або ємність, якщо
це постійна, ймовірно участь.

400
00:18:44,120 --> 00:18:47,100
Але тільки робити по модулю п`ять
ймовірно, не є достатнім,

401
00:18:47,100 --> 00:18:51,380
тому що ми повинні знати, робити ми
обернути навколо тут або тут або тут.

402
00:18:51,380 --> 00:18:54,160
Таким чином, ви, ймовірно, також
захоче залучити

403
00:18:54,160 --> 00:18:57,220
розмір речі або
передня змінна, а також.

404
00:18:57,220 --> 00:19:00,140
Так що це просто це відносно
просте арифметичне вираз,

405
00:19:00,140 --> 00:19:02,000
але по модулю буде ключовим елементом.

406
00:19:02,000 --> 00:19:03,330
>> Так короткий фільм, якщо ви будете.

407
00:19:03,330 --> 00:19:05,780
Анімація, що деякі
Люди в іншому університеті

408
00:19:05,780 --> 00:19:08,060
зібрати, що ми
пристосовані для цієї дискусії.

409
00:19:08,060 --> 00:19:12,630
Вона включає в себе Джек навчання
Факти про черг та статистики.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> ФІЛЬМ: Давним-давно,
був хлопець на ім'я Джек.

412
00:19:21,890 --> 00:19:25,330
Коли справа дійшла до прийняття друзями,
Джек не мають вправності.

413
00:19:25,330 --> 00:19:28,220
Так Джек пішов поговорити з
Найбільш популярний хлопець знав.

414
00:19:28,220 --> 00:19:30,920
Він пішов до Лу і запитала, що мені робити?

415
00:19:30,920 --> 00:19:33,400
Лу побачив, що його друг
був дійсно засмучений.

416
00:19:33,400 --> 00:19:36,050
Ну, він почав, тільки
подивіться, як ви одягнені.

417
00:19:36,050 --> 00:19:38,680
Чи немає у вас які-небудь одяг
з іншого вид?

418
00:19:38,680 --> 00:19:39,660
Так, сказав Джек.

419
00:19:39,660 --> 00:19:40,840
Я впевнений, що робити.

420
00:19:40,840 --> 00:19:43,320
Приходьте в мій будинок і
Я покажу їх вам.

421
00:19:43,320 --> 00:19:44,550
Таким чином, вони вирушили в Джека.

422
00:19:44,550 --> 00:19:47,520
І Джек показав Лу вікно
де він зберігав всі свої сорочки,

423
00:19:47,520 --> 00:19:49,260
і штани, і шкарпетки.

424
00:19:49,260 --> 00:19:52,290
Лу сказав, я бачу, у вас є
всі ваші одягу в купу.

425
00:19:52,290 --> 00:19:54,870
Чому б вам не носити деякі
інші раз в деякий час?

426
00:19:54,870 --> 00:19:58,020
>> Джек сказав, добре, коли я
видалити одяг і шкарпетки,

427
00:19:58,020 --> 00:20:00,780
Я мити їх і покласти
їм далеко в поле.

428
00:20:00,780 --> 00:20:03,210
Потім настає наступний
вранці, і до я стрибаю.

429
00:20:03,210 --> 00:20:06,380
Я йду в поле й отримати
мій одяг з верхньої.

430
00:20:06,380 --> 00:20:09,070
Лу швидко зрозумів,
проблема з Джеком.

431
00:20:09,070 --> 00:20:12,080
Він продовжував одяг, CD,
і книги в стеку.

432
00:20:12,080 --> 00:20:14,420
Коли він потягнувся за
то читати або носити,

433
00:20:14,420 --> 00:20:17,100
він вибрати верхню книгу або нижню білизну.

434
00:20:17,100 --> 00:20:19,500
Потім, коли він був зроблений, він
буде покласти його назад.

435
00:20:19,500 --> 00:20:21,970
Повернутися вона буде йти на вершині стека.

436
00:20:21,970 --> 00:20:24,460
Я знаю, що рішення,
сказав торжествуючий Голосно.

437
00:20:24,460 --> 00:20:27,090
Ви повинні навчитися
почати використовувати черги.

438
00:20:27,090 --> 00:20:29,870
Лу взяв одяг Джека і
повісив у шафу.

439
00:20:29,870 --> 00:20:32,710
І коли він спустошив
коробка, він просто кинув її.

440
00:20:32,710 --> 00:20:36,500
>> Тоді він сказав, тепер Джек, наприкінці
день, покласти одяг зліва

441
00:20:36,500 --> 00:20:37,990
коли ви кладете їх.

442
00:20:37,990 --> 00:20:41,300
Тоді завтра вранці, коли вам
см сонцем, отримати одяг

443
00:20:41,300 --> 00:20:43,440
на право, з кінця рядка.

444
00:20:43,440 --> 00:20:44,880
Хіба ви не бачите? сказав Лу.

445
00:20:44,880 --> 00:20:46,370
Це буде так приємно.

446
00:20:46,370 --> 00:20:49,770
Ви будете носити все відразу
перш ніж ви носите щось в два рази.

447
00:20:49,770 --> 00:20:52,670
І з усім в чергах
в шафі і шельфу,

448
00:20:52,670 --> 00:20:55,160
Джек почав відчувати
досить впевнений у собі.

449
00:20:55,160 --> 00:20:59,720
Все завдяки Лу і
його чудовий черги.

450
00:20:59,720 --> 00:21:01,220
СПІКЕР 1: Гаразд, це чудово.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Так що було насправді відбувається
на під капотом тепер?

453
00:21:10,080 --> 00:21:12,370
Що ми маємо покажчики,
що у нас є Танос,

454
00:21:12,370 --> 00:21:15,680
що у нас є можливість створити
шматки пам'яті для себе

455
00:21:15,680 --> 00:21:16,344
динамічно.

456
00:21:16,344 --> 00:21:18,510
Так що це картина, яку ми
побачив лише днями.

457
00:21:18,510 --> 00:21:21,180
Ми дійсно не зупинятися
на ньому, але ця картина

458
00:21:21,180 --> 00:21:24,180
має вже на під
капот вже кілька тижнів.

459
00:21:24,180 --> 00:21:27,050
І так це представляє, просто
прямокутник, який ми намалювали,

460
00:21:27,050 --> 00:21:28,180
пам'яті комп'ютера.

461
00:21:28,180 --> 00:21:31,850
І, можливо, ваш комп'ютер або CS50
ID, має гігабайт оперативної пам'яті або пам'яті

462
00:21:31,850 --> 00:21:33,050
або два гігабайти або чотири.

463
00:21:33,050 --> 00:21:34,450
Це дійсно не має значення.

464
00:21:34,450 --> 00:21:37,240
Ваша операційна система
Вікна або Mac OS або Linux,

465
00:21:37,240 --> 00:21:41,120
по суті дозволяє вашої програми
думати, що він має доступ

466
00:21:41,120 --> 00:21:42,982
до всієї
пам'яті комп'ютера,

467
00:21:42,982 --> 00:21:45,440
навіть якщо ви могли б бути запущений
кілька програм відразу.

468
00:21:45,440 --> 00:21:46,990
Таким чином, насправді, що насправді не працює.

469
00:21:46,990 --> 00:21:49,448
Але це свого роду ілюзія
враховуючи всі ваші програми.

470
00:21:49,448 --> 00:21:53,110
Так що, якщо у вас є два гігабайтами оперативної пам'яті, це
як комп'ютер може думати про це.

471
00:21:53,110 --> 00:21:57,110
>> Тепер за збігом, один з них
речі, один з цих сегментів пам'яті,

472
00:21:57,110 --> 00:21:58,350
називається стек.

473
00:21:58,350 --> 00:22:01,680
І справді в будь-який час
досі в написанні коду

474
00:22:01,680 --> 00:22:05,900
що ви назвали
Функція, наприклад, магістралі.

475
00:22:05,900 --> 00:22:08,410
Нагадаємо, що в будь-який час я маю
Намальовані пам'яті комп'ютера,

476
00:22:08,410 --> 00:22:10,640
Я завжди привертають роду
половина прямокутника тут

477
00:22:10,640 --> 00:22:12,520
і не турбувати говорити
про те, що це вище.

478
00:22:12,520 --> 00:22:15,980
Тому що, коли головний називається, я стверджую,
що ви отримаєте це шматочок пам'яті

479
00:22:15,980 --> 00:22:16,970
що йде сюди.

480
00:22:16,970 --> 00:22:20,650
І якщо основна функція називається
як своп, а своп йде тут.

481
00:22:20,650 --> 00:22:23,720
І виявляється, що це
де він в кінцевому підсумку.

482
00:22:23,720 --> 00:22:26,277
На те, що називається стеком
всередині пам'яті комп'ютера.

483
00:22:26,277 --> 00:22:28,360
Тепер в кінці дня,
це просто звертається.

484
00:22:28,360 --> 00:22:30,680
Це як нульовим байтом,
байт одним, байт 2 млрд.

485
00:22:30,680 --> 00:22:33,130
Але якщо ви думаєте про це
як це прямокутний об'єкт,

486
00:22:33,130 --> 00:22:35,130
все, що ми робимо кожен
Час ми називаємо функція

487
00:22:35,130 --> 00:22:37,180
відводками новий шматочок пам'яті.

488
00:22:37,180 --> 00:22:41,700
Ми даємо цю функцію шматочок
його власної пам'яті, щоб працювати с.

489
00:22:41,700 --> 00:22:44,490
>> І зараз згадати, що це важливо.

490
00:22:44,490 --> 00:22:46,400
Тому що, якщо у нас є
щось на зразок обміну

491
00:22:46,400 --> 00:22:51,610
і дві локальні змінні, такі як А і В і
ми змінюємо ці значення з одного і двох

492
00:22:51,610 --> 00:22:55,130
до двох і однієї, нагадаємо
що коли підкачки повертається,

493
00:22:55,130 --> 00:22:58,330
Це як якщо б цього шматочка
з пам'яті щойно.

494
00:22:58,330 --> 00:23:00,080
У дійсності, вона як і раніше
є криміналістично.

495
00:23:00,080 --> 00:23:01,940
І щось ще насправді є.

496
00:23:01,940 --> 00:23:05,410
Але концептуально, це, як
хоча це повністю зникли.

497
00:23:05,410 --> 00:23:10,910
І так основний не знаю ні про роботу
що було зроблено в цій функції підкачки,

498
00:23:10,910 --> 00:23:14,890
якщо це не насправді пройшло в тих
Аргументи за вказівником або за посиланням.

499
00:23:14,890 --> 00:23:17,790
Тепер, фундаментальне рішення
до цієї проблеми з своп

500
00:23:17,790 --> 00:23:19,970
Проходить речі в за адресою.

501
00:23:19,970 --> 00:23:23,250
Але, виявляється, теж що
вже на вище тієї частини

502
00:23:23,250 --> 00:23:26,330
прямокутника весь цей час
поки є більше пам'яті там.

503
00:23:26,330 --> 00:23:28,790
І коли ви динамічно
виділити пам'ять,

504
00:23:28,790 --> 00:23:32,020
будь то всередині GetString, який
ми робили для вас в CS50

505
00:23:32,020 --> 00:23:34,710
бібліотека, або якщо ви, хлопці,
зателефонувати і запитати Танос

506
00:23:34,710 --> 00:23:37,950
операційна система шматок
пам'яті, він не приходить з стека.

507
00:23:37,950 --> 00:23:40,960
Він поставляється з іншого місця
в пам'яті комп'ютера

508
00:23:40,960 --> 00:23:42,220
що називається купою.

509
00:23:42,220 --> 00:23:43,430
І це нічим не відрізняється.

510
00:23:43,430 --> 00:23:44,285
Це те ж саме ОЗУ.

511
00:23:44,285 --> 00:23:45,160
Це ж пам'ять.

512
00:23:45,160 --> 00:23:49,080
Це просто ОЗУ це до
там замість тут.

513
00:23:49,080 --> 00:23:50,750
>> І так що ж це означає?

514
00:23:50,750 --> 00:23:53,650
Ну, якщо ваш комп'ютер має
кінцеве кількість пам'яті

515
00:23:53,650 --> 00:23:57,450
і стек росте вгору, так
говорити, і купа, по

516
00:23:57,450 --> 00:23:59,349
в цьому стрілки, зростає вниз.

517
00:23:59,349 --> 00:24:01,140
Іншими словами, кожен
виклику Танос,

518
00:24:01,140 --> 00:24:03,430
Ви приділяється шматочок
пам'яті зверху,

519
00:24:03,430 --> 00:24:06,630
то, можливо, трохи нижче, то трохи
нижче, кожен раз, коли ви телефонуєте Танос,

520
00:24:06,630 --> 00:24:10,100
купа, його використання,
є свого роду зростає,

521
00:24:10,100 --> 00:24:11,950
росте ближче і ближче до чого?

522
00:24:11,950 --> 00:24:13,382
Стек.

523
00:24:13,382 --> 00:24:14,840
Так що це, здається, як хороша ідея?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Я маю на увазі, де це не зовсім ясно
що ще можна зробити, якщо тільки ви

526
00:24:22,140 --> 00:24:23,910
є кінцеве кількість пам'яті.

527
00:24:23,910 --> 00:24:25,200
Але це, безумовно, погано.

528
00:24:25,200 --> 00:24:27,920
Ці два стріли на
Інтенсивний курс для одного.

529
00:24:27,920 --> 00:24:31,930
>> І виходить, що поганий хлопець, люди, які
особливо добре з програмуванням,

530
00:24:31,930 --> 00:24:36,140
і намагається зламати комп'ютери,
можуть використовувати цю реальність.

531
00:24:36,140 --> 00:24:38,290
Справді, давайте розглянемо
трохи фрагмент.

532
00:24:38,290 --> 00:24:41,350
Таким чином, це є прикладом ви можете прочитати
про більш докладно у Вікіпедії.

533
00:24:41,350 --> 00:24:43,100
Ми вкажу вам на
Стаття якщо цікаво.

534
00:24:43,100 --> 00:24:45,650
Але є напад в цілому
відомий як переповнення буфера, що

535
00:24:45,650 --> 00:24:49,570
існує до тих пір, як люди
мали можливість маніпулювати

536
00:24:49,570 --> 00:24:53,120
пам'яті комп'ютера, особливо на C.
Так що це дуже довільна програма,

537
00:24:53,120 --> 00:24:55,130
але давайте читати знизу вгору.

538
00:24:55,130 --> 00:24:57,650
Головна в ARGC символ зірки ARGV.

539
00:24:57,650 --> 00:24:59,830
Так що це програма, яка приймає
Аргументи командного рядка.

540
00:24:59,830 --> 00:25:03,620
І все ж головна, мабуть, виклик
функція, назвемо його для простоти F.

541
00:25:03,620 --> 00:25:04,610
І це проходить в чому?

542
00:25:04,610 --> 00:25:05,490
ARGV одного.

543
00:25:05,490 --> 00:25:09,320
Так вона переходить в F всі
слово те, що користувач ввів

544
00:25:09,320 --> 00:25:11,500
в рядку після того,
Назва програми взагалі.

545
00:25:11,500 --> 00:25:15,730
Так само, як Цезар або Vigenere, який
Ви могли б пригадати, робить з ARGV.

546
00:25:15,730 --> 00:25:16,680
>> Так що F?

547
00:25:16,680 --> 00:25:19,760
F подає в рядку
в якості єдиного аргументу,

548
00:25:19,760 --> 00:25:22,100
АКА напівкоксу зірка, ж
річ, як рядок.

549
00:25:22,100 --> 00:25:24,920
І це називається як завгодно
бар в цьому прикладі.

550
00:25:24,920 --> 00:25:27,710
І тоді символ з 12
тільки з точки зору непрофесіонала,

551
00:25:27,710 --> 00:25:31,750
що символ з дужка 12 робить для нас?

552
00:25:31,750 --> 00:25:33,440
Що він робить?

553
00:25:33,440 --> 00:25:36,490
Виділення пам'яті, спеціально
12 байта для 12 символів.

554
00:25:36,490 --> 00:25:36,990
Точно.

555
00:25:36,990 --> 00:25:40,000
І тоді останній рядок, перемішати і
копія, ви, ймовірно, не бачив.

556
00:25:40,000 --> 00:25:43,360
Це рядок копія
Функція, мета якого в житті

557
00:25:43,360 --> 00:25:48,160
це скопіювати його другий аргумент
в якості першого аргументу,

558
00:25:48,160 --> 00:25:51,190
але тільки до
Певна кількість байтів.

559
00:25:51,190 --> 00:25:53,860
Таким чином, третій аргумент говорить,
скільки байт необхідно скопіювати?

560
00:25:53,860 --> 00:25:56,720
Довжина панелі,
всі користувач вводить в.

561
00:25:56,720 --> 00:25:59,320
І зміст
бар, цей рядок, є

562
00:25:59,320 --> 00:26:02,330
скопійовані в пам'ять вказав на точці С.

563
00:26:02,330 --> 00:26:04,060
>> Так що це, здається, свого роду нерозумно, і це.

564
00:26:04,060 --> 00:26:06,300
Це надуманий приклад,
але це представник

565
00:26:06,300 --> 00:26:10,100
класу векторів атаки,
спосіб нападу на програму.

566
00:26:10,100 --> 00:26:15,050
Все добре і чудово, якщо користувач
типи в слова, що це 11 символів

567
00:26:15,050 --> 00:26:18,040
або менше, плюс зворотний слеш нулю.

568
00:26:18,040 --> 00:26:22,830
Що робити, якщо користувач в більш ніж
11 або 12 або 20 або 50 символів?

569
00:26:22,830 --> 00:26:25,090
Що ця програма буде робити?

570
00:26:25,090 --> 00:26:29,360
Потенційно SEG вина. Це відбувається
сліпо копіювати все в барі до

571
00:26:29,360 --> 00:26:31,750
його довжині, яка
буквально все в барі,

572
00:26:31,750 --> 00:26:36,307
на адресу вказав на С. Але З
тільки превентивно дається як 12 байт.

573
00:26:36,307 --> 00:26:37,640
Але немає додаткової перевірки.

574
00:26:37,640 --> 00:26:38,700
Там, якщо умовах це немає.

575
00:26:38,700 --> 00:26:40,580
Там немає перевірки помилок тут.

576
00:26:40,580 --> 00:26:43,270
>> І так, що ця програма
збираюся зробити, це просто сліпо

577
00:26:43,270 --> 00:26:45,750
скопіювати одне до іншого.

578
00:26:45,750 --> 00:26:47,880
І тому, якщо ми це зробити
як картинка, ось

579
00:26:47,880 --> 00:26:49,860
просто шматочок простору пам'яті.

580
00:26:49,860 --> 00:26:53,470
Так помітити на дні, ми
є локальна змінна бар.

581
00:26:53,470 --> 00:26:57,330
Так, що покажчик, який збирається store--
а цієї локальної аргументу, що це

582
00:26:57,330 --> 00:26:58,672
збираєтеся зберігати рядок бар.

583
00:26:58,672 --> 00:27:00,380
І зверніть увагу на те якраз
вище, в стеку,

584
00:27:00,380 --> 00:27:02,505
тому що кожного разу ви просите
на пам'ять в стеку,

585
00:27:02,505 --> 00:27:04,310
вона йде трохи
над ним наочно,

586
00:27:04,310 --> 00:27:06,270
Зверніть увагу, що у нас є 12 байт там.

587
00:27:06,270 --> 00:27:10,690
Верхній лівий одна кронштейн З нуля і
нижній правий одна кронштейн З 11.

588
00:27:10,690 --> 00:27:12,870
От тільки, як комп'ютери
збирається закласти його.

589
00:27:12,870 --> 00:27:18,300
Так що просто інтуїтивно, якщо бар має більш
ніж 12 символів в загальній складності, в тому числі

590
00:27:18,300 --> 00:27:25,790
зворотний слеш нуль, де знаходиться
12 або З 12 кронштейн збирається йти?

591
00:27:25,790 --> 00:27:28,440
Або, скоріше, де 12-й
символ або 13 символів,

592
00:27:28,440 --> 00:27:30,900
соті персонаж збирається
в кінцевому підсумку на картинці?

593
00:27:30,900 --> 00:27:33,400
Вище або нижче?

594
00:27:33,400 --> 00:27:36,300
>> Правильно, тому що, хоча
сам стек росте вгору,

595
00:27:36,300 --> 00:27:39,590
як тільки ви покласти речі в
це, вона за конструктивними причин,

596
00:27:39,590 --> 00:27:41,294
ставить пам'ять зверху до низу.

597
00:27:41,294 --> 00:27:44,460
Так що, якщо у вас є більше, ніж 12 байт,
Ви збираєтеся почати перезапис бар.

598
00:27:44,460 --> 00:27:47,280
Тепер це помилка, але це
насправді не має великого значення.

599
00:27:47,280 --> 00:27:51,130
Але це велика справа, тому що є
більше речей відбувається в пам'яті.

600
00:27:51,130 --> 00:27:53,074
Так от, як ми могли б
поклав привіт, щоб бути ясно.

601
00:27:53,074 --> 00:27:54,490
Якщо я набрав в привіт в командному рядку.

602
00:27:54,490 --> 00:27:59,330
Н-Е-Л-Л-О зворотний слеш нуль, закінчується в
ці 12 байт, і ми супер безпечно.

603
00:27:59,330 --> 00:28:00,330
Все добре.

604
00:28:00,330 --> 00:28:03,020
Але якщо я щось типу
більше, потенційно це

605
00:28:03,020 --> 00:28:05,860
збирається повзати в бар просторі.

606
00:28:05,860 --> 00:28:08,405
Але ще гірше, виявляється
з усього цього часу,

607
00:28:08,405 --> 00:28:11,530
хоча ми ніколи не говорили про
це, стек використовується для інших речей.

608
00:28:11,530 --> 00:28:13,560
Це не тільки локальні змінні.

609
00:28:13,560 --> 00:28:15,100
>> З мовою дуже низький рівень.

610
00:28:15,100 --> 00:28:17,810
І це свого роду таємно
використовує стек також

611
00:28:17,810 --> 00:28:21,260
пам'ятати, коли
Функція називається те, що

612
00:28:21,260 --> 00:28:26,040
адреса є попередньої функції,
так що він може перейти назад до цієї функції.

613
00:28:26,040 --> 00:28:29,980
Тому, коли основні виклики поміняти, серед
речі в стек

614
00:28:29,980 --> 00:28:34,380
не тільки змінює локальні змінні,
або його аргументи, також таємно штовхнув

615
00:28:34,380 --> 00:28:37,510
стек, як представлено
червоним скибочкою тут,

616
00:28:37,510 --> 00:28:40,520
це адресу головної фізично
в пам'яті комп'ютера,

617
00:28:40,520 --> 00:28:44,180
так що, коли своп буде зроблено, комп'ютер
знає, що я повинен повернутися на головну

618
00:28:44,180 --> 00:28:46,760
і закінчити виконання основної функції.

619
00:28:46,760 --> 00:28:51,960
Так що це небезпечно зараз, тому що, якщо
користувач вводить в добре більш ніж привіт,

620
00:28:51,960 --> 00:28:57,030
таким чином, що введення користувача перевизначає
або переписує, що червоний розділ,

621
00:28:57,030 --> 00:28:59,820
логічно, якщо комп'ютера
просто хочу, щоб сліпо припустити,

622
00:28:59,820 --> 00:29:03,830
що байт в цій червоній скибочку є
адреса, за якою він повинен повернути,

623
00:29:03,830 --> 00:29:09,020
що, якщо противник досить розумний, або
пощастило поставити послідовність байт

624
00:29:09,020 --> 00:29:13,450
там виглядає як адреса,
але це адреса коду

625
00:29:13,450 --> 00:29:18,730
що він або вона хоче комп'ютер
виконати замість головної?

626
00:29:18,730 --> 00:29:21,670
>> Іншими словами, якщо те,
Користувач друкує в командному рядку,

627
00:29:21,670 --> 00:29:23,850
це не тільки те,
безневинно, як привіт,

628
00:29:23,850 --> 00:29:28,210
але насправді це код, який еквівалентно
видалити всі файли цього користувача?

629
00:29:28,210 --> 00:29:30,060
Або напишіть свій пароль мені?

630
00:29:30,060 --> 00:29:31,940
Або почати запис їх
натиснення клавіш, вірно?

631
00:29:31,940 --> 00:29:34,920
Існує спосіб, давайте передбачають сьогодні,
що вони могли б запровадити не лише в привіт

632
00:29:34,920 --> 00:29:36,711
світ або їх назву,
вони могли істотно

633
00:29:36,711 --> 00:29:39,570
перейти в код, нулів і
ті, що комп'ютер

634
00:29:39,570 --> 00:29:43,450
помилки для коду та адреси.

635
00:29:43,450 --> 00:29:48,950
Так нехай і дещо абстрактно, якщо
користувач в досить змагальності коду

636
00:29:48,950 --> 00:29:52,330
що ми будемо узагальнювати тут
А. А напад чи супротивники.

637
00:29:52,330 --> 00:29:53,140
Так що погані речі.

638
00:29:53,140 --> 00:29:55,306
Ми не дбаємо про
номера або нулі чи одиниці

639
00:29:55,306 --> 00:29:59,470
сьогодні, наприклад, що ви в кінцевому підсумку
перезапису, що червоний розділ,

640
00:29:59,470 --> 00:30:01,580
зауважити, що послідовність байт.

641
00:30:01,580 --> 00:30:05,020
Про 835 З нуля восьмій нулів.

642
00:30:05,020 --> 00:30:08,960
А тепер, як стаття Вікіпедії тут
запропонував, якщо ви зараз насправді почати

643
00:30:08,960 --> 00:30:12,460
маркування байти в комп'ютері років
пам'яті, що стаття Вікіпедії

644
00:30:12,460 --> 00:30:19,060
пропоную, що, те, що, якщо адреса
цієї верхньому лівому байта 80 С 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Іншими словами, якщо поганий хлопець
досить розумний, з його або її код

646
00:30:22,200 --> 00:30:26,650
насправді поставити номер тут, що
відповідає адресі коду

647
00:30:26,650 --> 00:30:29,180
він або вона вводять
в комп'ютер, ви

648
00:30:29,180 --> 00:30:31,050
може обдурити комп'ютер
в роблячи нічого.

649
00:30:31,050 --> 00:30:34,140
Видалення файлів, електронної пошти
речі, нюхати трафіку,

650
00:30:34,140 --> 00:30:36,710
буквально нічого може бути
вводили в комп'ютер.

651
00:30:36,710 --> 00:30:39,220
І так переповнення буфера
атака за своєю суттю

652
00:30:39,220 --> 00:30:43,530
це просто нерозумно, нерозумно
найважливіша з масиву,

653
00:30:43,530 --> 00:30:45,840
не мають його межі перевіряється.

654
00:30:45,840 --> 00:30:48,850
І це те, що це супер небезпечно
і одночасно супер потужний

655
00:30:48,850 --> 00:30:52,560
в С, що ми дійсно повинні
доступ в будь-яку точку в пам'яті.

656
00:30:52,560 --> 00:30:55,320
Це до нас, програмістів,
хто пише вихідний код

657
00:30:55,320 --> 00:30:59,330
для перевірки довжини прокляту будь-якого
масиви, які ми маніпулювання.

658
00:30:59,330 --> 00:31:00,750
Таким чином, щоб було ясно, що виправлення?

659
00:31:00,750 --> 00:31:03,190
Якщо ми повернутися до цього
Код, я не повинен просто

660
00:31:03,190 --> 00:31:08,000
змінити довжину панелі, те, що
ще я повинен перевіряти?

661
00:31:08,000 --> 00:31:10,620
Що ще я повинен робити, щоб
запобігти цьому напад повністю?

662
00:31:10,620 --> 00:31:14,110
Я не хочу, щоб просто сліпо сказати
що ви повинні скопіювати стільки байт,

663
00:31:14,110 --> 00:31:16,140
а довжина панелі.

664
00:31:16,140 --> 00:31:18,910
Я хочу сказати, скопіюйте в
кількість байт в рядку

665
00:31:18,910 --> 00:31:24,090
до виділена
пам'яті, або 12 максимально.

666
00:31:24,090 --> 00:31:27,450
Так що я потрібен якийсь, якщо умова
що робить перевірити довжину панелі,

667
00:31:27,450 --> 00:31:32,800
але якщо він перевищує 12, ми просто жорсткий код
12 як максимально можливу відстань.

668
00:31:32,800 --> 00:31:35,910
В іншому випадку так званого буфера
Переповнення напад може статися.

669
00:31:35,910 --> 00:31:38,451
У нижній частині цих слайдів,
якщо вам цікаво дізнатися більше

670
00:31:38,451 --> 00:31:41,200
фактична оригінальна стаття
якщо ви хочете, щоб поглянути.

671
00:31:41,200 --> 00:31:44,550
>> Але тепер, серед цін
заплатив тут був неефективність.

672
00:31:44,550 --> 00:31:46,680
Так, щоб було швидко
низький рівень погляд на те, що

673
00:31:46,680 --> 00:31:49,709
можуть виникнути проблеми в даний час, що ми
мати доступ до пам'яті комп'ютера.

674
00:31:49,709 --> 00:31:51,750
Але інша проблема, ми
вже натрапив на понеділок

675
00:31:51,750 --> 00:31:53,800
просто неефективність
із зв'язаного списку.

676
00:31:53,800 --> 00:31:56,019
Ми повернулися до лінійного часу.

677
00:31:56,019 --> 00:31:57,560
Ми більше не мають безперервний спектр.

678
00:31:57,560 --> 00:31:58,980
Ми не маємо довільний доступ.

679
00:31:58,980 --> 00:32:00,710
Ми не можемо використовувати квадратний позначення кронштейна.

680
00:32:00,710 --> 00:32:04,590
Ми буквально повинні використовувати той час як цикл
як один я написав якийсь час назад.

681
00:32:04,590 --> 00:32:09,740
Але в понеділок, ми стверджували, що ми можемо
повзти назад у царство ефективності

682
00:32:09,740 --> 00:32:13,040
досягнення те, що це
логарифмічна може бути, або ще краще,

683
00:32:13,040 --> 00:32:16,120
може бути, навіть щось, що це
Так званий постійної часу.

684
00:32:16,120 --> 00:32:19,840
Так, як ми можемо зробити це за допомогою цих нових
інструменти, ці адреси, ці покажчики,

685
00:32:19,840 --> 00:32:22,210
і різьблення речі наш власний?

686
00:32:22,210 --> 00:32:23,960
Ну, припустимо, що
тут, це купа

687
00:32:23,960 --> 00:32:27,170
чисел, які ми хочемо зберегти
Структура даних і пошук ефективно.

688
00:32:27,170 --> 00:32:30,960
Ми можемо абсолютно перемотати тижні
два, кинути їх в масив,

689
00:32:30,960 --> 00:32:33,150
і шукати їх за допомогою бінарного пошуку.

690
00:32:33,150 --> 00:32:34,040
Розділяй і володарюй.

691
00:32:34,040 --> 00:32:37,720
І насправді ви написали
бінарний пошук в PSET3,

692
00:32:37,720 --> 00:32:40,100
де ви реалізували програму знайти.

693
00:32:40,100 --> 00:32:40,890
Але ви знаєте, що.

694
00:32:40,890 --> 00:32:45,060
Там начебто більш
розумний спосіб зробити це.

695
00:32:45,060 --> 00:32:47,390
Це трохи більше,
складні і, можливо,

696
00:32:47,390 --> 00:32:50,830
дозволяє нам зрозуміти, чому двійкова
Пошук набагато швидше.

697
00:32:50,830 --> 00:32:52,980
По-перше, давайте познайомимося
поняття дерева.

698
00:32:52,980 --> 00:32:54,730
Який, хоча в
реальність дерева роду

699
00:32:54,730 --> 00:32:57,730
рости, як це, у світі комп'ютер
наука вони начебто ростуть вниз

700
00:32:57,730 --> 00:33:00,830
як родоводу, де у вас є
Ваші дідусі та бабусі або прадіди

701
00:33:00,830 --> 00:33:04,580
або ще багато чого у верхній, патріарха і
матриарх сім'ї, тільки один

702
00:33:04,580 --> 00:33:07,930
так званий корінь, вузол, нижче
які є її діти,

703
00:33:07,930 --> 00:33:11,442
нижче якого є його діти, або
його нащадки в цілому.

704
00:33:11,442 --> 00:33:13,400
І хто висить
нижня частина родини

705
00:33:13,400 --> 00:33:16,070
Дерево, крім того, що
молодший в сім'ї,

706
00:33:16,070 --> 00:33:19,520
Також можна просто в загальному
називається листя дерева.

707
00:33:19,520 --> 00:33:21,800
>> Так що це просто купа
слів і визначень

708
00:33:21,800 --> 00:33:25,790
щось називається дерево в комп'ютері
наука, так само, як родоводу.

709
00:33:25,790 --> 00:33:28,770
Але є більш вигадливі втілення
дерев, одне з яких

710
00:33:28,770 --> 00:33:30,780
називається бінарне дерево пошуку.

711
00:33:30,780 --> 00:33:34,380
І ви можете роду дражнити
крім того, що ця річ робить.

712
00:33:34,380 --> 00:33:37,180
Ну, це двійковий, в якому сенсі?

713
00:33:37,180 --> 00:33:41,455
Де двійковий приходять звідси?

714
00:33:41,455 --> 00:33:41,955
На жаль?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Це не стільки або.

717
00:33:47,210 --> 00:33:52,000
Це більше, що кожен з вузлів має не
більше двох дітей, як ми бачимо тут.

718
00:33:52,000 --> 00:33:54,990
Загалом, в tree-- і
Ваші батьки та бабусі

719
00:33:54,990 --> 00:33:57,640
може мати стільки дітей або
онуки, як вони насправді хочуть,

720
00:33:57,640 --> 00:34:00,820
і так, наприклад там у нас є три
дітей з цією правом вузлі,

721
00:34:00,820 --> 00:34:05,480
але в бінарному дереві, вузол має
нуль, один або двоє дітей. Максимально

722
00:34:05,480 --> 00:34:08,496
І це приємно власності,
тому що, якщо він обмежений двома,

723
00:34:08,496 --> 00:34:10,620
ми збираємося, щоб мати можливість
отримати трохи журналу бази двох

724
00:34:10,620 --> 00:34:11,975
Дія відбувається тут, в кінцевому рахунку.

725
00:34:11,975 --> 00:34:13,350
Отже, ми маємо щось логарифмічна.

726
00:34:13,350 --> 00:34:14,558
Але про це трохи пізніше.

727
00:34:14,558 --> 00:34:19,810
Пошук дерево означає, що номери
розташовані таким чином, що ліва дитини

728
00:34:19,810 --> 00:34:22,429
значення більше кореня.

729
00:34:22,429 --> 00:34:26,010
І його право дитина
більше, ніж в корені.

730
00:34:26,010 --> 00:34:29,290
Іншими словами, якщо ви берете будь-який з
вузли, кола в цій картині,

731
00:34:29,290 --> 00:34:31,840
і дивиться на його лівій
Дитина та її права дитини,

732
00:34:31,840 --> 00:34:34,739
перше має бути менше,
друга повинна бути більше, ніж.

733
00:34:34,739 --> 00:34:36,159
Так розсудливість перевірити 55.

734
00:34:36,159 --> 00:34:37,780
Це залишилося дитини 33.

735
00:34:37,780 --> 00:34:38,620
Це менше, ніж.

736
00:34:38,620 --> 00:34:40,929
55, його право дитина 77.

737
00:34:40,929 --> 00:34:41,783
Це більше, ніж.

738
00:34:41,783 --> 00:34:43,199
І це рекурсивне визначення.

739
00:34:43,199 --> 00:34:46,480
Ми могли б перевірити кожен з тих,
вузли і та ж картина буде проводити.

740
00:34:46,480 --> 00:34:49,389
>> Так що приємно в
бінарне дерево пошуку, це

741
00:34:49,389 --> 00:34:52,204
що один, ми можемо реалізувати його
з структури, як це.

742
00:34:52,204 --> 00:34:54,620
І хоча ми кидали
багато структур, у вашому

743
00:34:54,620 --> 00:34:56,560
вони дещо
Тепер, сподіваюся, інтуїтивно.

744
00:34:56,560 --> 00:35:00,570
Синтаксис ще таємницею напевно,
але вміст вузла в цьому

745
00:35:00,570 --> 00:35:02,786
context--, і ми продовжуємо
використовуючи слово вузол,

746
00:35:02,786 --> 00:35:04,910
чи є це прямокутник
на екрані або круга,

747
00:35:04,910 --> 00:35:08,970
це лише деякі загальні контейнер,
У цьому випадку дерева, як той,

748
00:35:08,970 --> 00:35:11,780
ми бачили, ми повинні ціле
в кожному з вузлів

749
00:35:11,780 --> 00:35:15,460
а потім мені потрібно дві покажчики, що вказують
на лівому дитини і правої дитини,

750
00:35:15,460 --> 00:35:16,590
відповідно.

751
00:35:16,590 --> 00:35:20,730
Так от, як ми могли б
здійснити, що в структури.

752
00:35:20,730 --> 00:35:22,315
І як я міг би реалізувати це в коді?

753
00:35:22,315 --> 00:35:26,730
Ну, давайте швидко
подивитися на цьому крихітному наприклад.

754
00:35:26,730 --> 00:35:29,820
Це не працює, але я
скопіювати і вставити цю структуру.

755
00:35:29,820 --> 00:35:33,510
І якщо моя функція для бінарних
Пошук дерево називається пошук,

756
00:35:33,510 --> 00:35:36,980
і це приймає два аргументи,
ціле число N і покажчик

757
00:35:36,980 --> 00:35:41,400
до вузла, так що покажчик на дерево
або покажчик на корінь дерева,

758
00:35:41,400 --> 00:35:43,482
як я можу йти про пошук N?

759
00:35:43,482 --> 00:35:45,440
Ну, по-перше, тому, що я
справу з покажчиками,

760
00:35:45,440 --> 00:35:46,750
Я збираюся зробити перевірку осудності.

761
00:35:46,750 --> 00:35:54,279
Якщо дерево одно дорівнює нулю, є N
в цьому дереві чи ні в цьому дереві?

762
00:35:54,279 --> 00:35:55,070
Це не може бути, чи не так?

763
00:35:55,070 --> 00:35:56,870
Якщо я повз нуль,
немає нічого.

764
00:35:56,870 --> 00:35:59,230
Я міг би також просто
сліпо сказати повернутися помилковим.

765
00:35:59,230 --> 00:36:04,050
Якщо ви не дають мені нічого, я, звичайно, не можу
знайти число N. Так що ще я міг би

766
00:36:04,050 --> 00:36:04,750
Перевір зараз?

767
00:36:04,750 --> 00:36:12,830
Я хочу сказати, добре ще, якщо п
менше, ніж те, що знаходиться у вузлі дерева

768
00:36:12,830 --> 00:36:16,300
що я був переданий значення N.

769
00:36:16,300 --> 00:36:20,270
Іншими словами, якщо число Я
шукаєте, N, менше, ніж вузол

770
00:36:20,270 --> 00:36:21,340
що я дивлюся на.

771
00:36:21,340 --> 00:36:23,190
І вузол Я шукаю
в називається дерево,

772
00:36:23,190 --> 00:36:26,370
і згадати з попереднього прикладу
щоб дістатися до значення в покажчик,

773
00:36:26,370 --> 00:36:28,310
Я використовую позначення зі стрілкою.

774
00:36:28,310 --> 00:36:35,960
Так що, якщо N менше, ніж дерево стрілки
N, я хочу, щоб концептуально йдіть наліво.

775
00:36:35,960 --> 00:36:38,590
Як я висловлюю пошуку залишилося?

776
00:36:38,590 --> 00:36:41,560
Щоб було ясно, якщо це
картина в питанні,

777
00:36:41,560 --> 00:36:44,612
і я був прийнятий, що верхній
стрілка, який спрямований вниз.

778
00:36:44,612 --> 00:36:45,570
Це моя покажчик дерево.

779
00:36:45,570 --> 00:36:48,060
Я вказую на корені дерева.

780
00:36:48,060 --> 00:36:52,100
І я з нетерпінням скажімо,
число 44, довільно.

781
00:36:52,100 --> 00:36:55,300
44 менше або
більше, ніж 55, очевидно?

782
00:36:55,300 --> 00:36:56,360
Так це менше, ніж.

783
00:36:56,360 --> 00:36:58,760
І так це, якщо умова поширюється.

784
00:36:58,760 --> 00:37:03,981
Так концептуально, те, що я хочу, щоб
пошук в наступному, якщо я шукаю 44?

785
00:37:03,981 --> 00:37:04,480
Так?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Точно, я хочу
пошук ліву дитини,

788
00:37:11,100 --> 00:37:12,789
або вліво суб-дерево цієї картини.

789
00:37:12,789 --> 00:37:14,830
І справді, хай мене через
картина тут

790
00:37:14,830 --> 00:37:17,770
на мить, так як
Я не можу подряпати це.

791
00:37:17,770 --> 00:37:21,150
Якщо я почну тут в 55, і
Я знаю, що значення 44

792
00:37:21,150 --> 00:37:23,180
Я шукаю, щоб
ліва, це свого роду

793
00:37:23,180 --> 00:37:26,010
з, як розриваючи телефонну книгу в
половина або розриваючи дерево навпіл.

794
00:37:26,010 --> 00:37:29,660
Я більше не доведеться піклуватися про
весь цей половина дерева.

795
00:37:29,660 --> 00:37:33,270
І все ж, як не дивно, в термінах
Структура, ця річ тут, що

796
00:37:33,270 --> 00:37:36,682
починається з 33, що саме по собі
це бінарне дерево пошуку.

797
00:37:36,682 --> 00:37:39,890
Я сказав слово рекурсивний раніше, тому що
Дійсно, це структура даних,

798
00:37:39,890 --> 00:37:41,707
за визначенням є рекурсивним.

799
00:37:41,707 --> 00:37:44,540
Ви, можливо, дерево, в цьому
великий, але кожен з його дітей

800
00:37:44,540 --> 00:37:46,870
являє собою дерево просто трохи менше.

801
00:37:46,870 --> 00:37:50,910
Замість цього бути дідуся
чи бабуся, тепер це просто мама

802
00:37:50,910 --> 00:37:54,300
ілі-- я не можу say-- не мама
або тато, що було б дивно.

803
00:37:54,300 --> 00:37:59,000
Замість двоє дітей там
буде як брат і брат.

804
00:37:59,000 --> 00:38:01,120
Нове покоління в родоводу.

805
00:38:01,120 --> 00:38:02,900
Але структурно, це та ж сама ідея.

806
00:38:02,900 --> 00:38:06,790
А то виходить, у мене є функція
з якою я можу шукати бінарний пошук

807
00:38:06,790 --> 00:38:07,290
дерево.

808
00:38:07,290 --> 00:38:08,680
Це називається пошук.

809
00:38:08,680 --> 00:38:17,870
Я шукаю N в дереві зліва стрілки
інше, якщо п більше, ніж значення

810
00:38:17,870 --> 00:38:18,870
що я в даний час.

811
00:38:18,870 --> 00:38:20,800
55 в історії момент тому.

812
00:38:20,800 --> 00:38:23,780
У мене є функція під назвою
Пошук, що я можу просто

813
00:38:23,780 --> 00:38:29,660
пройти N це і рекурсивний пошук
суб-дерево і просто повернення

814
00:38:29,660 --> 00:38:30,620
все, що відповіддю.

815
00:38:30,620 --> 00:38:33,530
Інакше я отримав деякі підсумковий базовий випадок тут.

816
00:38:33,530 --> 00:38:35,310
>> Яка кінцева справа?

817
00:38:35,310 --> 00:38:36,570
Дерево або нульовим.

818
00:38:36,570 --> 00:38:39,980
Значення я або шукаю є
менше, ніж це чи більше, що

819
00:38:39,980 --> 00:38:42,610
або дорівнює їй.

820
00:38:42,610 --> 00:38:44,750
І я можу сказати, дорівнюють
рівні, але логічно це

821
00:38:44,750 --> 00:38:46,500
еквівалентно просто говорю ще тут.

822
00:38:46,500 --> 00:38:49,150
Так правда, як я знайти щось.

823
00:38:49,150 --> 00:38:51,710
Так, ми сподіваємося це
ще більш переконливим прикладом

824
00:38:51,710 --> 00:38:54,900
ніж дурною функції сигма
Ми зробили кілька лекцій назад,

825
00:38:54,900 --> 00:38:58,360
де це було так само легко використовувати цикл
підрахувати всі цифри від одного

826
00:38:58,360 --> 00:39:02,390
до N. Тут зі структурою даних
що сама рекурсивно

827
00:39:02,390 --> 00:39:07,050
визначені і рекурсивно звертається, тепер ми
мають можливість виразити себе, щоб

828
00:39:07,050 --> 00:39:09,780
в коді, який сам по собі є рекурсивним.

829
00:39:09,780 --> 00:39:12,580
Так що це точно такий же код тут.

830
00:39:12,580 --> 00:39:14,400
>> Так що інші проблеми ми можемо вирішити?

831
00:39:14,400 --> 00:39:18,160
Таким чином, швидким кроком від
дерева на мить.

832
00:39:18,160 --> 00:39:20,130
Ось, скажімо, німецький прапор.

833
00:39:20,130 --> 00:39:22,020
І є явно
шаблон для цього прапора.

834
00:39:22,020 --> 00:39:23,811
І є багато
прапори у світі,

835
00:39:23,811 --> 00:39:27,560
так просто, як це з погляду
їх кольори і візерунки.

836
00:39:27,560 --> 00:39:31,930
Але припустимо, що це зберігається як
.GIF Або JPEG, або растровий, або пінг,

837
00:39:31,930 --> 00:39:34,240
будь-який графічний формат файлу
з якою ви знайомі,

838
00:39:34,240 --> 00:39:36,460
деякі з яких ми
грати з в PSET4.

839
00:39:36,460 --> 00:39:41,550
Це, здається, не варто зберігати
чорний піксель, чорний піксель, чорний піксель,

840
00:39:41,550 --> 00:39:44,790
крапка, крапка, крапка, ціла купа
чорні пікселі для першого рядка розгортки,

841
00:39:44,790 --> 00:39:47,430
або рядок, то ціла купа
те ж саме, то ціла купа

842
00:39:47,430 --> 00:39:49,530
того ж самого, а потім
Весь букет червоних пікселів,

843
00:39:49,530 --> 00:39:53,020
червоний пікселів, червоні пікселі, то в цілому
Букет з жовтих точок, жовтий, вірно?

844
00:39:53,020 --> 00:39:55,050
>> Там така неефективність тут.

845
00:39:55,050 --> 00:39:59,040
Як би ви інтуїтивно
стискати німецький прапор

846
00:39:59,040 --> 00:40:01,320
якщо її реалізації у вигляді файлу?

847
00:40:01,320 --> 00:40:04,940
Подобається те, що інформація ми не можемо
турбувати зберігання на диску для того,

848
00:40:04,940 --> 00:40:08,040
щоб зменшити нашу розмір файлу з, як
мегабайт в кілобайт, то

849
00:40:08,040 --> 00:40:09,430
менше?

850
00:40:09,430 --> 00:40:13,130
У чому полягає надмірність
тут, щоб бути зрозуміло?

851
00:40:13,130 --> 00:40:13,880
Що ви могли б зробити?

852
00:40:13,880 --> 00:40:14,380
Так?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Точно.

855
00:40:21,970 --> 00:40:24,550
Чому б не згадати, чим
колір кожного пікселя штопати

856
00:40:24,550 --> 00:40:28,200
так само, як ви робите в PSET4
с Формат графічного файлу,

857
00:40:28,200 --> 00:40:32,060
чому б вам просто не уявляють
ліва колонка пікселів, наприклад

858
00:40:32,060 --> 00:40:35,370
купа чорних пікселів, купа
червоний, і купа жовтий,

859
00:40:35,370 --> 00:40:39,210
а потім просто якимось чином кодувати
Ідея повторити цей 100 раз

860
00:40:39,210 --> 00:40:41,020
або повторити це в 1000 разів?

861
00:40:41,020 --> 00:40:43,430
Де 100 або 1000 є
просто ціле число, так що ви

862
00:40:43,430 --> 00:40:47,290
може зійти з рук тільки один номер
замість сотень або тисяч

863
00:40:47,290 --> 00:40:48,270
додаткових пікселів.

864
00:40:48,270 --> 00:40:50,990
І справді, ось як ми
може стискати німецький прапор.

865
00:40:50,990 --> 00:40:51,490
І

866
00:40:51,490 --> 00:40:53,470
Тепер те, що про французьким прапором?

867
00:40:53,470 --> 00:40:58,930
І трохи свого роду
розумовий вправу, що прапор

868
00:40:58,930 --> 00:41:01,040
можуть бути стислі більш на диску?

869
00:41:01,040 --> 00:41:05,720
Німецький прапор або французький
Прапор, якщо ми візьмемо такий підхід?

870
00:41:05,720 --> 00:41:08,490
Німецький прапор, тому що є
більш горизонтального резервування.

871
00:41:08,490 --> 00:41:12,190
І по дизайну, багато графічний файл
Формати дійсно працювати, як сканування ліній

872
00:41:12,190 --> 00:41:12,830
горизонталі.

873
00:41:12,830 --> 00:41:14,674
Вони могли б працювати
вертикально, просто людство

874
00:41:14,674 --> 00:41:17,090
вирішили років тому, що ми будемо
як правило, думати про речі, ряд

875
00:41:17,090 --> 00:41:18,880
по рядках, а не по стовпцях.

876
00:41:18,880 --> 00:41:20,820
Так, якщо б ви були
подивитися на файл

877
00:41:20,820 --> 00:41:24,670
розмір німецьким прапором та французькою мовами
Прапор, поки дозвіл

878
00:41:24,670 --> 00:41:27,530
те ж саме, такої ж ширини
і висота, на цей раз

879
00:41:27,530 --> 00:41:31,580
тут буде більше, тому що ви
доведеться повторити себе три рази.

880
00:41:31,580 --> 00:41:35,570
Ви повинні вказати, повторення синій
самостійно, білий, повторюватися, червоний,

881
00:41:35,570 --> 00:41:36,740
повторюватися.

882
00:41:36,740 --> 00:41:39,000
Ви не можете просто піти всі
шлях до правої.

883
00:41:39,000 --> 00:41:41,200
І, як в сторону, щоб зробити
очистити стиск

884
00:41:41,200 --> 00:41:43,910
скрізь, якщо це
чотири кадри з video-- ви

885
00:41:43,910 --> 00:41:45,890
Нагадаю, що фільм
або відео, як правило,

886
00:41:45,890 --> 00:41:47,286
як 29 або 30 кадрів в секунду.

887
00:41:47,286 --> 00:41:50,410
Це як маленький фліп книги, де вас
просто побачити зображення, зображення, зображення, зображення,

888
00:41:50,410 --> 00:41:54,410
Зображення просто супер швидко, так що, схоже,
актори на екрані рухаються.

889
00:41:54,410 --> 00:41:57,130
Ось джміль на
Верх букетом квітів.

890
00:41:57,130 --> 00:41:59,790
І хоча це може бути вид
важко зрозуміти, на перший погляд,

891
00:41:59,790 --> 00:42:04,020
єдине рух в
цей фільм бджола.

892
00:42:04,020 --> 00:42:06,880
>> Що є німим про зберігання
відео в стислому?

893
00:42:06,880 --> 00:42:11,420
Це свого роду відходів для зберігання відео
, як чотири майже ідентичних зображень,

894
00:42:11,420 --> 00:42:13,670
відрізняються лише остільки, оскільки, коли бджола.

895
00:42:13,670 --> 00:42:16,280
Ви можете викинути найбільш
цієї інформації

896
00:42:16,280 --> 00:42:20,190
і пам'ятати тільки, наприклад,
перший кадр і останній кадр,

897
00:42:20,190 --> 00:42:22,180
ключові кадри, якщо ви
коли-небудь чули слово,

898
00:42:22,180 --> 00:42:24,337
і просто зберігати в
середнього, де бджола.

899
00:42:24,337 --> 00:42:26,170
І ви не повинні
зберігати всі рожевому,

900
00:42:26,170 --> 00:42:28,330
і синій, і
зелені значення, а також.

901
00:42:28,330 --> 00:42:31,200
Так що це тільки сказати, що
стиснення в усьому світі.

902
00:42:31,200 --> 00:42:34,900
Це техніка, яку ми часто використовують
або приймати як належне в ці дні.

903
00:42:34,900 --> 00:42:38,750
>> Але як ви стиснути текст?

904
00:42:38,750 --> 00:42:40,450
Як ви йти про стиснення тексту?

905
00:42:40,450 --> 00:42:45,410
Ну, кожен з персонажів
Ascii один байт, чи вісім біт.

906
00:42:45,410 --> 00:42:47,360
І це свого роду німий, чи не так?

907
00:42:47,360 --> 00:42:51,160
Тому що ви, ймовірно, введіть A
і Е, я і виводу і U багато

908
00:42:51,160 --> 00:42:55,270
частіше, ніж, як W або Q або Z,
залежно від мови, якою

909
00:42:55,270 --> 00:42:56,610
Ви пишете, звичайно ,.

910
00:42:56,610 --> 00:42:59,600
І так, чому ми за допомогою
восьмій бітів для кожного листа,

911
00:42:59,600 --> 00:43:02,040
в тому числі не менше
популярні букви, вірно?

912
00:43:02,040 --> 00:43:05,300
Чому б не використовувати меншу кількість біт для
супер популярні літери,

913
00:43:05,300 --> 00:43:07,760
як Е, то, думаю, ви
перший в Колесо Фортуни,

914
00:43:07,760 --> 00:43:10,450
і використовувати більше бітів для
менш популярні літери?

915
00:43:10,450 --> 00:43:10,950
Чому?

916
00:43:10,950 --> 00:43:13,130
Тому що ми тільки збираємося
використовувати їх рідше.

917
00:43:13,130 --> 00:43:15,838
>> Ну, виявляється, що там є
робилися спроби зробити це.

918
00:43:15,838 --> 00:43:18,630
І якщо ви пам'ятаєте з класу
школа чи ВНЗ, код Морзе.

919
00:43:18,630 --> 00:43:20,400
Азбука Морзе має точки
і тире, які можуть бути

920
00:43:20,400 --> 00:43:24,270
передаються по дроту як
звуки або сигнали якийсь.

921
00:43:24,270 --> 00:43:25,930
Але код Морзе є супер чистий.

922
00:43:25,930 --> 00:43:29,010
Це свого роду подвійної системи в
що у вас є точки або рисочки.

923
00:43:29,010 --> 00:43:30,977
Але якщо ви бачите, наприклад, дві точки.

924
00:43:30,977 --> 00:43:33,810
Або, якщо ви думаєте, назад оператору
хто йде, як звуковий сигнал, біп, біп,

925
00:43:33,810 --> 00:43:36,760
звуковий сигнал, потрапивши трохи курок
що передає сигнал,

926
00:43:36,760 --> 00:43:40,360
якщо ви, одержувач отримує два
точки, те, що повідомлення ви отримали?

927
00:43:40,360 --> 00:43:43,490
Повністю довільно.

928
00:43:43,490 --> 00:43:44,450
>> Я?

929
00:43:44,450 --> 00:43:45,060
Я?

930
00:43:45,060 --> 00:43:47,500
Або те, що about-- чи я?

931
00:43:47,500 --> 00:43:49,570
Може бути, це було всього лише два прямо Е?

932
00:43:49,570 --> 00:43:52,480
Так що ця проблема
з декодіруемой з Морзе

933
00:43:52,480 --> 00:43:54,890
Код, в результаті чого, якщо тільки
людина, який посилає вам повідомлення

934
00:43:54,890 --> 00:43:59,510
насправді робить паузу, щоб ви могли сортувати
бачити або чути пропуски між буквами,

935
00:43:59,510 --> 00:44:02,990
це не досить просто
відправити потік нулів і одиниць,

936
00:44:02,990 --> 00:44:05,610
або точки і тире,
бо є двозначність.

937
00:44:05,610 --> 00:44:08,640
Е є одна точка, так що якщо вам
побачити дві точки або почути дві точки,

938
00:44:08,640 --> 00:44:11,254
може бути, це два E-то або, може бути, це один І.

939
00:44:11,254 --> 00:44:13,670
Так що ми повинні систему, що це
трохи розумніші, ніж це.

940
00:44:13,670 --> 00:44:16,851
Таким чином, людина на ім'я Хаффмана років
тому вигадав саме це.

941
00:44:16,851 --> 00:44:18,600
Таким чином, ми просто збираємося
взяти швидкий погляд

942
00:44:18,600 --> 00:44:20,114
на те, як дерева доречні для цього.

943
00:44:20,114 --> 00:44:22,530
Припустимо, що це який-
нерозумно повідомлення ви хочете відправити,

944
00:44:22,530 --> 00:44:26,342
складається тільки з A, B, C в D's і Е х,
але є багато надмірності тут.

945
00:44:26,342 --> 00:44:27,550
Це не означало, щоб бути англійська.

946
00:44:27,550 --> 00:44:28,341
Це не шифрується.

947
00:44:28,341 --> 00:44:30,540
Це просто нерозумно повідомлення
з великою кількістю повторень.

948
00:44:30,540 --> 00:44:34,010
Так що, якщо ви насправді відраховувати всі
А-х, Б, С-х, D's, і E-х, ось

949
00:44:34,010 --> 00:44:34,890
частота.

950
00:44:34,890 --> 00:44:37,800
20% з букв
А-х, 45% з букв

951
00:44:37,800 --> 00:44:39,660
є E, і три інші частоти.

952
00:44:39,660 --> 00:44:41,960
Ми нарахували там вручну
і просто зробив математику.

953
00:44:41,960 --> 00:44:44,579
>> Так що виходить, що
Хаффман, якийсь час назад,

954
00:44:44,579 --> 00:44:46,620
зрозумів, що, ви знаєте,
те, що, якщо я почну будівля

955
00:44:46,620 --> 00:44:51,172
дерево, чи ліс дерев, якщо хочете,
як слід, я можу зробити наступне.

956
00:44:51,172 --> 00:44:53,880
Я збираюся дати вузол друг
з листів, які я піклуються про

957
00:44:53,880 --> 00:44:55,530
і я збираюся зберігати
всередині цього вузла

958
00:44:55,530 --> 00:44:58,610
частоти, як плаваючою точкою
значення, або ви могли б використовувати його п теж

959
00:44:58,610 --> 00:45:00,210
але ми будемо використовувати тільки поплавок тут.

960
00:45:00,210 --> 00:45:03,100
І алгоритм, який
він запропонував, що ви

961
00:45:03,100 --> 00:45:07,210
прийняти цей ліс одному вузлі
дерева, так супер короткі дерева,

962
00:45:07,210 --> 00:45:11,920
і ви починаєте з'єднання їх з
нові групи, нові батьки, якщо ви будете.

963
00:45:11,920 --> 00:45:16,150
І це можна зробити, вибравши
два маленьких частоти одночасно.

964
00:45:16,150 --> 00:45:18,110
Так що я взяв 10% і 10%.

965
00:45:18,110 --> 00:45:19,090
Створити новий вузол.

966
00:45:19,090 --> 00:45:20,910
І я закликаю новий вузол 20%.

967
00:45:20,910 --> 00:45:22,750
>> Які два вузли я комбінувати далі?

968
00:45:22,750 --> 00:45:23,810
Це трохи неоднозначним.

969
00:45:23,810 --> 00:45:26,643
Так є деякі випадки, в кутові
розглянути, але тримати речі досить,

970
00:45:26,643 --> 00:45:29,300
Я збираюся вибрати 20% -
Тепер я ігнорувати дітей.

971
00:45:29,300 --> 00:45:33,640
Я збираюся вибрати 20%, а
15% і намалюйте два нові ребра.

972
00:45:33,640 --> 00:45:35,624
А тепер які два вузли
я логічно об'єднати?

973
00:45:35,624 --> 00:45:38,540
Ігнорувати всі діти, все
онуки, просто подивіться на коріння

974
00:45:38,540 --> 00:45:39,070
Тепер.

975
00:45:39,070 --> 00:45:42,220
Які два вузли я зв'язати разом?

976
00:45:42,220 --> 00:45:44,530
Другий пункт і 0,35.

977
00:45:44,530 --> 00:45:45,890
Отже, дозвольте мені зробити два нових ребер.

978
00:45:45,890 --> 00:45:47,570
І потім, я тільки отримав один залишився.

979
00:45:47,570 --> 00:45:48,650
Так от дерево.

980
00:45:48,650 --> 00:45:51,160
І це було звернено навмисно
дивитися вигляд досить,

981
00:45:51,160 --> 00:45:55,870
але зауважив, що ребра мають
Також були помічені нуля і один.

982
00:45:55,870 --> 00:45:59,510
Таким чином, всі з лівого країв дорівнюють нулю
довільно, але послідовно.

983
00:45:59,510 --> 00:46:01,170
Усі праві краю є ті.

984
00:46:01,170 --> 00:46:05,070
>> І так, що Хоффман запропонував є,
якщо ви хочете, щоб представляти B,

985
00:46:05,070 --> 00:46:10,080
а не являють собою кількість, як 66
ASCII, котрий вісім цілі біт,

986
00:46:10,080 --> 00:46:13,360
ви знаєте, що тільки магазин
зразок нуль, нуль, нуль,

987
00:46:13,360 --> 00:46:17,030
нулю, тому що це шлях
від мого дерева, дерево Хаффмана г,

988
00:46:17,030 --> 00:46:18,600
до аркуша від кореня.

989
00:46:18,600 --> 00:46:20,970
Якщо ви хочете зберегти
Е, навпаки, не

990
00:46:20,970 --> 00:46:26,290
відправити восьмій біт, які представляють Е.
Замість цього, відправити який набір бітів?

991
00:46:26,290 --> 00:46:26,890
Один.

992
00:46:26,890 --> 00:46:30,410
І, що приємно про це є
що Е є найпопулярнішим лист,

993
00:46:30,410 --> 00:46:32,340
і ви за допомогою
короткий код для нього.

994
00:46:32,340 --> 00:46:34,090
Наступним найбільш популярним
Лист виглядає вона

995
00:46:34,090 --> 00:46:37,380
був А. І так, скільки біт
він пропонується використовувати для цього?

996
00:46:37,380 --> 00:46:38,270
Нуль, один.

997
00:46:38,270 --> 00:46:41,060
>> І тому, що він реалізований
як це дерево, в даний час

998
00:46:41,060 --> 00:46:43,350
дозвольте мені передбачають є
немає неоднозначності, як в Морзе

999
00:46:43,350 --> 00:46:46,090
Код, бо всі з
Листи ви дбаєте про

1000
00:46:46,090 --> 00:46:48,780
в кінці цих країв.

1001
00:46:48,780 --> 00:46:50,580
Так це тільки один
Застосування дерева.

1002
00:46:50,580 --> 00:46:52,538
Це is-- і я хвиля
моя рука на це, як ви

1003
00:46:52,538 --> 00:46:55,570
може здійснити це в C структури.

1004
00:46:55,570 --> 00:46:58,260
Ми просто повинні об'єднати
символ, як гольця,

1005
00:46:58,260 --> 00:46:59,910
і частота в лівий і правий.

1006
00:46:59,910 --> 00:47:02,510
Але давайте подивимося на два
Остаточні приклади, які ви

1007
00:47:02,510 --> 00:47:06,070
отримати добре знайомі з після
Тест нулю в проблемі встановити п'ять.

1008
00:47:06,070 --> 00:47:09,210
>> Так що є структура даних
відомий як хеш-таблицю.

1009
00:47:09,210 --> 00:47:12,247
І хеш-таблиця є своєрідною
охолонути в тому, що він має відра.

1010
00:47:12,247 --> 00:47:14,830
І нехай там чотири відра
тут всього чотири прогалини.

1011
00:47:14,830 --> 00:47:20,830
Ось колода карт, і тут
клуб, лопата, клуб, алмази, клуб,

1012
00:47:20,830 --> 00:47:25,960
діаманти, алмази клуб ,,
clubs-- так що це випадкова.

1013
00:47:25,960 --> 00:47:30,330
Серця, hearts-- тому я
bucketizing всі входи тут.

1014
00:47:30,330 --> 00:47:32,430
І А потреби хеш-таблицю
поглянути на свій вхід,

1015
00:47:32,430 --> 00:47:34,850
а потім покласти його в певний
розмістити основі того, що ви бачите.

1016
00:47:34,850 --> 00:47:35,600
Це алгоритм.

1017
00:47:35,600 --> 00:47:37,980
І я був за допомогою супер
простий візуальний алгоритм.

1018
00:47:37,980 --> 00:47:40,030
Найважча частина з яких була
пам'ятаючи, що фотографії були.

1019
00:47:40,030 --> 00:47:41,590
А тут ще всього чотири речі.

1020
00:47:41,590 --> 00:47:45,440
>> Тепер стеки були зростає, що
навмисне дизайн річ тут.

1021
00:47:45,440 --> 00:47:46,540
Але що ще я міг би зробити?

1022
00:47:46,540 --> 00:47:49,080
Тому насправді тут ми маємо
купа старих книг школи іспит.

1023
00:47:49,080 --> 00:47:51,240
Припустимо, що купу
студенти імена тут.

1024
00:47:51,240 --> 00:47:52,570
Ось більше хеш-таблиці.

1025
00:47:52,570 --> 00:47:54,867
Замість чотирьох відер,
Я, скажімо, 26.

1026
00:47:54,867 --> 00:47:57,950
І ми не хочемо йти займати 26
речі з поза [? Анненберг?], Так що

1027
00:47:57,950 --> 00:48:00,289
ось п'ять, які представляють
А до Z. І якщо я

1028
00:48:00,289 --> 00:48:03,580
см студента, чиє ім'я починається з А,
Я збираюся поставити його або її вікторини там.

1029
00:48:03,580 --> 00:48:08,850
Якщо хтось починає з C, там,
A-- насправді, не хочуть, щоб зробити це.

1030
00:48:08,850 --> 00:48:10,060
У іде сюди.

1031
00:48:10,060 --> 00:48:13,390
Так що я отримав А і В і С. А
Тепер ось ще студент.

1032
00:48:13,390 --> 00:48:16,212
Але якщо це хеш-таблиці
реалізовані з масивом,

1033
00:48:16,212 --> 00:48:17,920
Я начебто угвинчується
на даний момент, чи не так?

1034
00:48:17,920 --> 00:48:19,510
Я начебто повинні покласти це десь.

1035
00:48:19,510 --> 00:48:24,380
>> Так один спосіб я можу вирішити це, все
право, зайнятий, зайнятий В, С зайнятий.

1036
00:48:24,380 --> 00:48:28,880
Я збираюся поставити його в D. Таким чином, в
Спочатку я є випадкове миттєвий доступ

1037
00:48:28,880 --> 00:48:31,064
до кожного з ковшів для студентів.

1038
00:48:31,064 --> 00:48:33,230
Але тепер це начебто передані
у щось лінійних,

1039
00:48:33,230 --> 00:48:36,750
тому що, якщо я хочу, щоб шукати кого-
чиє ім'я починається з А, я перевіряю тут.

1040
00:48:36,750 --> 00:48:38,854
Але якщо це не А
студент Я шукаю,

1041
00:48:38,854 --> 00:48:41,520
Я начебто повинні почати перевірку
відра, тому що те, що я зробив

1042
00:48:41,520 --> 00:48:44,530
був свого роду лінійно
досліджувати структуру даних.

1043
00:48:44,530 --> 00:48:47,710
Дурний спосіб сказати просто подивитися
для першої доступною відкриття,

1044
00:48:47,710 --> 00:48:51,850
і поставити в план Б, так би мовити,
або план розробки в цьому випадку, значення

1045
00:48:51,850 --> 00:48:53,340
в цьому місці замість цього.

1046
00:48:53,340 --> 00:48:56,470
Це просто так, що якщо ви
отримав 26 місця і не студенти

1047
00:48:56,470 --> 00:49:00,600
з ім'ям Q або Z, або щось на зразок
що, принаймні, ви використовуєте простір.

1048
00:49:00,600 --> 00:49:03,140
>> Але ми вже бачили більш
розумні рішення тут, вірно?

1049
00:49:03,140 --> 00:49:04,870
Що б ви зробили, замість
якщо у вас є зіткнення?

1050
00:49:04,870 --> 00:49:06,670
Якщо дві людини мають
назву А, що б

1051
00:49:06,670 --> 00:49:09,160
були розумнішими або
інтуїтивне рішення, ніж просто

1052
00:49:09,160 --> 00:49:12,840
Приміщення, де D, як передбачається, буде?

1053
00:49:12,840 --> 00:49:14,810
Чому я не можу просто піти
поза [? Анненберг?],

1054
00:49:14,810 --> 00:49:19,960
як Танос, інший вузол, поставити його
тут, а потім покласти, що студент тут.

1055
00:49:19,960 --> 00:49:22,120
Так що я по суті є
яка з масиву,

1056
00:49:22,120 --> 00:49:25,590
або, може бути, більш елегантно, як ми
починаємо бачити зв'язаний список.

1057
00:49:25,590 --> 00:49:29,520
>> І так хеш-таблиця структура
що може виглядати так само, як це,

1058
00:49:29,520 --> 00:49:33,900
але розумніші, ви щось називається
окремий ланцюжки, в результаті чого хеш-таблицю

1059
00:49:33,900 --> 00:49:38,340
досить просто являє собою масив, кожен з
елементи якого не є числом,

1060
00:49:38,340 --> 00:49:40,470
саме по собі є зв'язаний список.

1061
00:49:40,470 --> 00:49:45,080
Так що ви отримаєте супер швидкий доступ
вирішити, де в хеш вашу цінність для.

1062
00:49:45,080 --> 00:49:48,059
Багато чого, як у прикладі карт,
Я зробив супер швидкі рішення.

1063
00:49:48,059 --> 00:49:49,600
Серця йде тут, алмази йде тут.

1064
00:49:49,600 --> 00:49:52,180
Те ж саме тут, А тут йде,
Д йде тут, В тут йде.

1065
00:49:52,180 --> 00:49:55,740
Так супер швидкий погляд вікна, і якщо
Ви випадково запустити у разі

1066
00:49:55,740 --> 00:49:59,429
де ви отримали зіткнення, два
люди з таким же ім'ям, ну а потім

1067
00:49:59,429 --> 00:50:00,970
Ви просто почати, пов'язуючи їх разом.

1068
00:50:00,970 --> 00:50:03,900
І, може бути, ви тримаєте їх упорядковано
в алфавітному порядку, може бути, ви цього не роблять.

1069
00:50:03,900 --> 00:50:05,900
Але принаймні тепер у нас є динамізм.

1070
00:50:05,900 --> 00:50:10,250
Отже, з одного боку, ми маємо дуже швидко
постійна часу, і вигляд лінійного часу

1071
00:50:10,250 --> 00:50:14,110
участь, якщо ці зв'язані списки
починають отримувати трохи довго.

1072
00:50:14,110 --> 00:50:16,880
>> Так що це свого роду дурні,
зухвалим жарти років тому.

1073
00:50:16,880 --> 00:50:19,590
У CS50 рубати-а-марафон,
коли студенти перевірити в,

1074
00:50:19,590 --> 00:50:22,040
деякі TF або Каліфорнія щороку
думає, що це смішно, миритися

1075
00:50:22,040 --> 00:50:27,772
знак, як це, де це тільки
означає, що якщо ваше ім'я починається з А,

1076
00:50:27,772 --> 00:50:28,870
йти по цьому шляху.

1077
00:50:28,870 --> 00:50:31,110
Якщо починається ваше ім'я
з В, перейти this-- ОК,

1078
00:50:31,110 --> 00:50:33,290
це смішно, може бути, пізніше в семестр.

1079
00:50:33,290 --> 00:50:36,420
Але є ще один
спосіб зробити це, теж.

1080
00:50:36,420 --> 00:50:37,410
Вернись до цього.

1081
00:50:37,410 --> 00:50:38,600
>> Так що ця структура.

1082
00:50:38,600 --> 00:50:40,420
І це наша остання
Структура на сьогоднішній день,

1083
00:50:40,420 --> 00:50:42,400
щось називається Trie.

1084
00:50:42,400 --> 00:50:47,140
Т-Р-И-Е, який чомусь не вистачає
для пошуку, але це називається Trie.

1085
00:50:47,140 --> 00:50:51,389
Так Trie ще один цікавий
амальгама багато цих ідей.

1086
00:50:51,389 --> 00:50:52,930
Це дерево, яке ми бачили раніше.

1087
00:50:52,930 --> 00:50:54,180
Це не бінарне дерево пошуку.

1088
00:50:54,180 --> 00:50:58,410
Це дерево з будь-якою кількістю дітей,
але кожен з дітей у синтаксичного дерева

1089
00:50:58,410 --> 00:51:00,090
є масивом.

1090
00:51:00,090 --> 00:51:04,790
Масив розміром, припустимо, 26 або, може бути 27
якщо ви хочете, щоб підтримати дефіс імена

1091
00:51:04,790 --> 00:51:06,790
або апострофи в іменах людей.

1092
00:51:06,790 --> 00:51:08,280
>> І так це структури даних.

1093
00:51:08,280 --> 00:51:10,290
І якщо ви подивитеся зверху
вниз, як якби вас

1094
00:51:10,290 --> 00:51:13,710
подивіться на верхній вузол там, М,
вказуючи на крайню ліву речі там,

1095
00:51:13,710 --> 00:51:17,665
який потім A, X, W, E, L, L. Це
просто структура даних, яка довільно

1096
00:51:17,665 --> 00:51:19,120
є збереження імен людей.

1097
00:51:19,120 --> 00:51:25,720
І Максвелл зберігається тільки після
це шлях масиву масиву на масив.

1098
00:51:25,720 --> 00:51:30,050
Але що дивно близько Trie є
що, в той час як зв'язаний список, і навіть

1099
00:51:30,050 --> 00:51:34,520
масив, найкраще, що ми коли-небудь отримували це
лінійний час або логарифмічне час шукаєте

1100
00:51:34,520 --> 00:51:35,600
хто до.

1101
00:51:35,600 --> 00:51:40,530
У цьому структури даних синтаксичного дерева, якщо
мій структура даних має один ім'я в ньому

1102
00:51:40,530 --> 00:51:43,720
і Я шукаю Максвелла, я
збираюся знайти його досить швидко.

1103
00:51:43,720 --> 00:51:47,910
Я просто дивлюся на М-А-Х-W-E-L-L. Якщо
Ця структура даних, навпаки,

1104
00:51:47,910 --> 00:51:51,830
Якщо N є млн, якщо є
мільйон імена в цій структурі даних,

1105
00:51:51,830 --> 00:51:57,100
Максвелл ще буде
виявити вже через М-А-Х-Ш-Е-Л-Ь

1106
00:51:57,100 --> 00:51:58,090
кроки.

1107
00:51:58,090 --> 00:52:01,276
І David-- Д-А-В-Я-D кроки.

1108
00:52:01,276 --> 00:52:03,400
Іншими словами, шляхом створення
структура даних, що це

1109
00:52:03,400 --> 00:52:07,240
отримав всі ці масивів, кожен з яких
Самі підтримувати довільний доступ,

1110
00:52:07,240 --> 00:52:11,090
Я можу почати дивлячись народних
назвати, використовуючи кількість часу, що'S

1111
00:52:11,090 --> 00:52:14,340
пропорційна не кількості
речей в структурі даних,

1112
00:52:14,340 --> 00:52:16,330
як мільйон існуючі імена.

1113
00:52:16,330 --> 00:52:20,135
Кількість часу, який потрібен, щоб знайти мене
М-А-Х-Ш-Е-Л-Л в цій структурі даних є

1114
00:52:20,135 --> 00:52:22,260
пропорційна НЕ
Розмір структури даних,

1115
00:52:22,260 --> 00:52:25,930
але з довжиною імені.

1116
00:52:25,930 --> 00:52:28,440
І реалістично
Імена ми дивлячись

1117
00:52:28,440 --> 00:52:29,970
ніколи не буде з розуму довго.

1118
00:52:29,970 --> 00:52:32,600
Можливо, хтось має 10 характер
ім'я, ім'я персонажа 20.

1119
00:52:32,600 --> 00:52:33,900
Це, звичайно, звичайно, не так?

1120
00:52:33,900 --> 00:52:37,110
Існує людини на Землі, який
має максимально можливий ім'я,

1121
00:52:37,110 --> 00:52:39,920
але це ім'я є константою
значення довжини, вірно?

1122
00:52:39,920 --> 00:52:41,980
Це не змінюється в будь-якому сенсі.

1123
00:52:41,980 --> 00:52:45,090
Таким чином, в цьому випадку, ми
досягнуті структурою даних

1124
00:52:45,090 --> 00:52:47,800
що постійна часу погляд вгору.

1125
00:52:47,800 --> 00:52:50,670
Це займе кілька кроків
в залежності від довжини входу,

1126
00:52:50,670 --> 00:52:54,250
але не число імені
в структурі даних.

1127
00:52:54,250 --> 00:52:58,700
Так що, якщо ми подвоїмо кількість імен
в наступному році з мільярда до двох мільярдів,

1128
00:52:58,700 --> 00:53:03,720
висновок Максвелла збирається взяти
точно такий же кількість сім кроків

1129
00:53:03,720 --> 00:53:04,650
щоб знайти його.

1130
00:53:04,650 --> 00:53:08,810
І таким чином, ми, здається, досягли
наш святий Грааль час роботи.

1131
00:53:08,810 --> 00:53:10,860
>> Таким чином, пара швидких оголошень.

1132
00:53:10,860 --> 00:53:11,850
Вікторина нуль вигадувати.

1133
00:53:11,850 --> 00:53:14,600
Докладніше про те, що на веб-сайті Курсу
протягом найближчих декількох днів.

1134
00:53:14,600 --> 00:53:17,120
Понеділок lecture-- Це свято
тут в Гарварді в понеділок.

1135
00:53:17,120 --> 00:53:18,850
Це не в Нью-Хейвені,
таким чином, ми беремо клас

1136
00:53:18,850 --> 00:53:20,310
в Нью-Гейвен для лекції в понеділок.

1137
00:53:20,310 --> 00:53:22,550
Все буде знятий
і транслюватиметься в прямому ефірі, як звичайно,

1138
00:53:22,550 --> 00:53:24,900
але давайте в кінцевому сьогодні
з другим затиском 30

1139
00:53:24,900 --> 00:53:26,910
звані "глибокі думки"
по Daven Фарн, який

1140
00:53:26,910 --> 00:53:30,850
був натхненний торік у суботу
"Думки" Deep Night Live в

1141
00:53:30,850 --> 00:53:35,700
Джек Хенді, який
Тепер слід розібратися.

1142
00:53:35,700 --> 00:53:38,810
>> ФІЛЬМ: А тепер, "Глибоке
Думки "по Daven Фарн.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Хеш-таблиці.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> СПІКЕР 1: Гаразд, що вона в даний час.

1147
00:53:47,660 --> 00:53:48,805
Ми будемо бачити Вас на наступному тижні.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> Даг: Для того щоб побачити його в дії.

1150
00:53:56,680 --> 00:53:58,304
Отже, давайте поглянемо на це прямо зараз.

1151
00:53:58,304 --> 00:53:59,890
Так от, у нас є несортоване масив.

1152
00:53:59,890 --> 00:54:04,860
>> УПА: Дуг, ви можете йти вперед і перезапуск
це всього лише за одну секунду, будь ласка.

1153
00:54:04,860 --> 00:54:08,562
Гаразд, камери працюють, так що
дії всякий раз, коли ви будете готові, Дуг, ОК?

1154
00:54:08,562 --> 00:54:11,020
Даг: Гаразд, так що ми
Тобто тут несортоване масив.

1155
00:54:11,020 --> 00:54:13,960
І я всі кольорові елементи
червоним кольором, що, по суті,

1156
00:54:13,960 --> 00:54:14,460
несортоване.

1157
00:54:14,460 --> 00:54:17,960
Так нагадати, що перше, що ми робимо
це ми сортуємо ліву половину масиву.

1158
00:54:17,960 --> 00:54:20,630
Потім ми сортуємо право
половина масиву.

1159
00:54:20,630 --> 00:54:22,830
І я-так, я-так, я-так,
ми їх зливаються.

1160
00:54:22,830 --> 00:54:24,520
І у нас є повністю відсортований масив.

1161
00:54:24,520 --> 00:54:25,360
Так от, як об'єднати роду робіт.

1162
00:54:25,360 --> 00:54:27,109
>> УПА: Гей, гей, гей,
вирізати, вирізати, вирізати, вирізати.

1163
00:54:27,109 --> 00:54:30,130
Дуг, ти не можеш просто я-так, я-так,
я-так, ваш шлях через сортування злиттям.

1164
00:54:30,130 --> 00:54:31,970
>> Даг: Я тільки що зробив.

1165
00:54:31,970 --> 00:54:32,832
Все добре.

1166
00:54:32,832 --> 00:54:33,540
Ми добре йти.

1167
00:54:33,540 --> 00:54:34,760
Давайте просто тримати прокатки.

1168
00:54:34,760 --> 00:54:35,380
Так чи інакше,

1169
00:54:35,380 --> 00:54:37,800
>> УПА: Ви повинні пояснити
це більш повно, ніж це.

1170
00:54:37,800 --> 00:54:39,999
Ось тільки не вистачає.

1171
00:54:39,999 --> 00:54:41,790
Даг: Ян, ми не
потрібно повернутися до одного.

1172
00:54:41,790 --> 00:54:42,350
Все добре.

1173
00:54:42,350 --> 00:54:45,690
Так чи інакше, якщо ми будемо продовжувати з merge--
Ян, ми знаходимося в середині зйомок.

1174
00:54:45,690 --> 00:54:46,612
>> УПА: Я знаю.

1175
00:54:46,612 --> 00:54:49,320
І ми не можемо просто я-так, я-так,
я-так, через весь процес.

1176
00:54:49,320 --> 00:54:52,200
Ви повинні пояснити, як
Сторони зливаються разом.

1177
00:54:52,200 --> 00:54:53,570
>> ДАГ: Але ми вже
пояснив, як два sides--

1178
00:54:53,570 --> 00:54:55,321
>> УПА: Ви тільки що показали
їх масив злиття.

1179
00:54:55,321 --> 00:54:56,486
Даг: Вони знають процес.

1180
00:54:56,486 --> 00:54:57,172
Вони в порядку.

1181
00:54:57,172 --> 00:54:58,380
Ми пішли на нього в десять разів.

1182
00:54:58,380 --> 00:55:00,330
>> УПА: Ви тільки що пропустив прямо над нею.

1183
00:55:00,330 --> 00:55:03,360
Ми повертаємося до одного, ви
ви не можете я-так, я-так над ним.

1184
00:55:03,360 --> 00:55:05,480
Гаразд, до одного.

1185
00:55:05,480 --> 00:55:07,833
>> Даг: Я повинен повернутися
через всі слайди?

1186
00:55:07,833 --> 00:55:08,332
Боже.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Це як в шостий раз, Ian.

1189
00:55:13,004 --> 00:55:13,940
Все добре.

1190
00:55:13,940 --> 00:55:15,200
>> УПА: Гаразд.

1191
00:55:15,200 --> 00:55:16,590
Ви готові?

1192
00:55:16,590 --> 00:55:17,400
Відмінно.

1193
00:55:17,400 --> 00:55:18,950
Дія.