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
Действие.