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

2
00:00:00,030 --> 00:00:00,460
>> DAVID Маланом: Хорошо.

3
00:00:00,460 --> 00:00:01,094
Мы вернулись.

4
00:00:01,094 --> 00:00:04,260
Так что в этом сегменте по программированию, что
Я думал, что мы делаем это сочетание вещей.

5
00:00:04,260 --> 00:00:06,340
Во-первых, сделать немного
о чем-то руки-на,

6
00:00:06,340 --> 00:00:08,690
хотя и с использованием более игривый
программирование environment--

7
00:00:08,690 --> 00:00:11,620
тот, который является показательным из
именно те виды идей

8
00:00:11,620 --> 00:00:14,220
мы говорим о том,
но немного более формально.

9
00:00:14,220 --> 00:00:18,200
Во-вторых, посмотрите на некоторые из
тем более технические способы

10
00:00:18,200 --> 00:00:21,520
что программист будет на самом деле решить
Проблемы, как в поисках проблемы

11
00:00:21,520 --> 00:00:24,530
что мы рассмотрели до и
также более фундаментально

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

13
00:00:26,020 --> 00:00:28,840
>> Мы только предположил, что с самого начала идти
что эта телефонная книга сортировали,

14
00:00:28,840 --> 00:00:31,980
но это само по себе на самом деле добр из
сложная проблема со многими различными способами

15
00:00:31,980 --> 00:00:32,479
чтобы решить эту проблему.

16
00:00:32,479 --> 00:00:34,366
Таким образом, мы будем использовать их как
класс задач

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

18
00:00:36,740 --> 00:00:38,980
И тогда мы будем говорить
о в некоторых деталях, что

19
00:00:38,980 --> 00:00:42,360
называются данные structures--
причудливые способы, как связанные списки

20
00:00:42,360 --> 00:00:46,290
и хэш-таблицы и деревья,
программист будет на самом деле

21
00:00:46,290 --> 00:00:48,890
использовать и как правило, используют
на доске рисовать

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

23
00:00:51,840 --> 00:00:52,980
некоторые части программного обеспечения.

24
00:00:52,980 --> 00:00:55,130
>> Так что давайте делать практический части первой.

25
00:00:55,130 --> 00:01:00,090
Так что просто получить ваши руки грязные с
окружающая среда называется scratch.mit.edu.

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

27
00:01:02,636 --> 00:01:04,510
Несмотря на то, что он предназначен
для лиц до 12 лет и старше,

28
00:01:04,510 --> 00:01:07,570
мы используем его для вверх
часть этого совсем немного

29
00:01:07,570 --> 00:01:10,020
так как это приятно, весело
Графический способ обучения

30
00:01:10,020 --> 00:01:12,160
кое-что о программировании.

31
00:01:12,160 --> 00:01:17,600
Так голова к этому URL, где вы
должны увидеть страницу совсем так,

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

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

34
00:01:28,300 --> 00:01:29,970
account-- scratch.mit.edu.

35
00:01:29,970 --> 00:01:32,165

36
00:01:32,165 --> 00:01:34,665
Я думал, что использовать это как
возможность впервые показать это.

37
00:01:34,665 --> 00:01:39,120
Вопрос подошел во время перерыва
о том, что код на самом деле выглядит.

38
00:01:39,120 --> 00:01:41,315
И мы говорили
во время перерыва о С,

39
00:01:41,315 --> 00:01:45,060
в частности particular--
более низкий уровень в более старом языке.

40
00:01:45,060 --> 00:01:47,750
И я просто сделал быстрый
Google поиск, чтобы найти код C

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

42
00:01:51,574 --> 00:01:54,240
Этот конкретный пример, конечно же,
не ищет телефонную книгу.

43
00:01:54,240 --> 00:01:57,840
Он просто ищет целую кучу
Числа в памяти компьютера.

44
00:01:57,840 --> 00:02:01,000
Но если вы хотите, чтобы просто получить визуальное
ощущение того, что фактическое программирование

45
00:02:01,000 --> 00:02:05,370
язык выглядит, это выглядит
немного что-то вроде этого.

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

47
00:02:09,759 --> 00:02:12,640
но разговор мы
имели более перерыва

48
00:02:12,640 --> 00:02:16,000
был о том, как это на самом деле
получает трансформировалось в нулей и единиц

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

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

51
00:02:20,210 --> 00:02:22,620
>> К сожалению, процесс
настолько преобразовательный

52
00:02:22,620 --> 00:02:24,890
что это намного легче сказать, чем сделать.

53
00:02:24,890 --> 00:02:29,400
Я пошел вперед и на самом деле оказалось
что программа, бинарный поиск,

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

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

56
00:02:34,400 --> 00:02:37,850
И если вы посмотрите на экран
здесь, обратив особое внимание

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

58
00:02:43,520 --> 00:02:48,290
И те нули и единицы, которые
составить именно эту программу поиска.

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

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

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

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

63
00:03:04,610 --> 00:03:08,000
И что это значит быть процессор
что у вас есть набор инструкций,

64
00:03:08,000 --> 00:03:08,840
так сказать.

65
00:03:08,840 --> 00:03:11,620
>> Каждый процессор в мире, многие из
они сделаны Intel в эти дни,

66
00:03:11,620 --> 00:03:13,690
понимает конечное
количество инструкций.

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

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

69
00:03:22,560 --> 00:03:27,340
чтобы здесь, в памяти, сохранить этот
информация отсюда здесь, в памяти,

70
00:03:27,340 --> 00:03:32,200
и так forth-- очень, очень
низкого уровня, почти электронные детали.

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

72
00:03:34,780 --> 00:03:37,410
с тем, что мы обсуждали ранее,
представление данных

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

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

75
00:03:44,180 --> 00:03:45,580
или иным образом.

76
00:03:45,580 --> 00:03:49,450
>> Так что это очень легко получить
потеряли в сорняков быстро.

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

78
00:03:52,150 --> 00:03:56,630
причем, если вы сделаете самый простой,
глупое опечаток никто из программы

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

80
00:03:57,860 --> 00:04:00,366
И поэтому вместо того, чтобы использовать
язык, как C этим утром,

81
00:04:00,366 --> 00:04:02,240
Я думал, что это было бы
больше удовольствия на самом деле делать

82
00:04:02,240 --> 00:04:04,840
нечто большее, визуальное восприятие,
в то время как предназначены для детей

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

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

85
00:04:10,370 --> 00:04:11,710
чтобы представить эти идеи.

86
00:04:11,710 --> 00:04:15,470
>> Поэтому, как только вы на самом деле иметь
счет на scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
нажмите кнопку Создать
в левом верхнем углу сайта.

88
00:04:21,070 --> 00:04:24,620
И вы должны увидеть окружающую среду как
один я собираюсь видеть на моем экране

89
00:04:24,620 --> 00:04:26,310
Вот.

90
00:04:26,310 --> 00:04:29,350
И мы потратим немного
немного времени, играя здесь.

91
00:04:29,350 --> 00:04:34,080
Давайте посмотрим, если мы не можем все решить некоторые
проблемы вместе следующим образом.

92
00:04:34,080 --> 00:04:39,420
>> Так что вы увидите в этом
environment-- и на самом деле просто дайте

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

94
00:04:40,050 --> 00:04:42,680
Кто-нибудь не здесь?

95
00:04:42,680 --> 00:04:45,070
Не здесь?

96
00:04:45,070 --> 00:04:45,800
ОК.

97
00:04:45,800 --> 00:04:49,030
Итак, позвольте мне отметить несколько
Характеристики этой среды.

98
00:04:49,030 --> 00:04:55,024
>> Таким образом, в верхнем левом углу экрана, мы
есть стадия чистого листа, так сказать.

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

100
00:04:57,440 --> 00:05:00,356
это также имя кота,
вы видите, по умолчанию там в оранжевый цвет.

101
00:05:00,356 --> 00:05:02,160
Он находится на сцене, так
так же, как я описал

102
00:05:02,160 --> 00:05:05,770
черепаха ранее как в
прямоугольная белая доска окружающая среда.

103
00:05:05,770 --> 00:05:09,800
Мир этой кошки ограничивается исключительно
на этот прямоугольник наверху там.

104
00:05:09,800 --> 00:05:12,210
>> В то же время, справа
правая часть здесь, это

105
00:05:12,210 --> 00:05:15,610
только область скрипты,
чистого листа, если вы будете.

106
00:05:15,610 --> 00:05:18,590
Именно здесь мы будем писать
наши программы в мгновение.

107
00:05:18,590 --> 00:05:22,935
И строительные блоки, которые мы
использовать, чтобы написать это program-- головоломки

108
00:05:22,935 --> 00:05:25,310
штук, если вы will-- являются
те, прямо здесь, в центре,

109
00:05:25,310 --> 00:05:27,500
и они классифицируются
по функциональности.

110
00:05:27,500 --> 00:05:31,000
Так, например, я собираюсь идти вперед
и продемонстрировать, по крайней мере, один из них.

111
00:05:31,000 --> 00:05:33,690
Я собираюсь идти вперед и нажмите
категория управления наверху.

112
00:05:33,690 --> 00:05:35,720
>> Так что эти категории до вершины.

113
00:05:35,720 --> 00:05:39,410
Я собираюсь нажать категорию управления.

114
00:05:39,410 --> 00:05:44,020
Скорее всего, я буду нажимать на события
категория, самый первый наверху.

115
00:05:44,020 --> 00:05:47,790
И если вы хотите следовать даже
как мы делаем это, вы очень добро пожаловать.

116
00:05:47,790 --> 00:05:52,180
Я собираюсь нажать и перетащить этот
Первый из них, "когда зеленый флаг щелкнул".

117
00:05:52,180 --> 00:05:58,410
А потом я собираюсь бросить его просто
примерно в верхней части моих пустых сланцы.

118
00:05:58,410 --> 00:06:01,450
>> И что приятно о пустом месте
является то, что этот кусок головоломки, когда

119
00:06:01,450 --> 00:06:04,560
взаимосвязанный с другой головоломки
штук, собирается сделать буквально

120
00:06:04,560 --> 00:06:06,460
что эти кусочки головоломки говорят делать.

121
00:06:06,460 --> 00:06:09,710
Так, например, Царапины прав
сейчас в середине своего мира.

122
00:06:09,710 --> 00:06:14,660
Я собираюсь идти вперед и выбрать
Теперь, скажем, категория движения,

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

124
00:06:18,000 --> 00:06:20,430
А теперь обратите внимание у меня есть целый
куча головоломки здесь

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

126
00:06:23,370 --> 00:06:28,110
И я собираюсь идти вперед и перетащить
уронить блок двигаться прямо здесь.

127
00:06:28,110 --> 00:06:31,860
>> И обратите внимание, что, как только вы получите
близко к нижней части "зеленый флаг

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

129
00:06:34,580 --> 00:06:36,950
как будто это почти
магнитные, он хочет поехать туда.

130
00:06:36,950 --> 00:06:43,070
Просто отпустить, и он будет хватать
вместе и формы будут совпадать.

131
00:06:43,070 --> 00:06:46,620
И теперь вы можете, возможно, почти
угадать, где мы собираемся с этим.

132
00:06:46,620 --> 00:06:51,570
>> Если вы посмотрите на сцену Скретч
здесь и смотреть в верхней части его,

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

134
00:06:55,142 --> 00:06:57,100
И я собираюсь идти вперед
и смотреть мои screen--

135
00:06:57,100 --> 00:06:58,460
на мгновение, если бы вы могли.

136
00:06:58,460 --> 00:07:01,960
Я собираюсь нажать
зеленый флаг прямо сейчас,

137
00:07:01,960 --> 00:07:07,850
и он переехал, что, как представляется, 10 шагов
или 10 пикселей, 10 точек, на экране.

138
00:07:07,850 --> 00:07:13,390
>> И так не так интересно,
но позвольте мне предложить

139
00:07:13,390 --> 00:07:17,440
даже не учил этому, просто
используя свой собственный intuition-- пусть

140
00:07:17,440 --> 00:07:22,560
я предлагаю вам выяснить, как
сделать Царапины прогулку прямо со сцены.

141
00:07:22,560 --> 00:07:28,700
Были ли ему сделать путь для правой стороны
экран, весь путь направо.

142
00:07:28,700 --> 00:07:32,200
Позвольте мне дать вам момент
или так, чтобы бороться с этим.

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

144
00:07:37,681 --> 00:07:38,180
Отлично.

145
00:07:38,180 --> 00:07:41,290
Так что просто резюмировать, когда мы имеем
зеленый флаг нажав здесь

146
00:07:41,290 --> 00:07:44,850
и двигаться 10 шагов является
только инструкция, каждый раз, когда я

147
00:07:44,850 --> 00:07:46,720
нажмите зеленый флаг, что происходит?

148
00:07:46,720 --> 00:07:50,070
Ну, это работает моя программа.

149
00:07:50,070 --> 00:07:52,450
Так что я мог бы сделать это
может быть в 10 раз вручную,

150
00:07:52,450 --> 00:07:55,130
но это чувствует себя немного
немного хаком, так сказать,

151
00:07:55,130 --> 00:07:57,480
в результате чего я на самом деле не
решение проблемы.

152
00:07:57,480 --> 00:08:00,530
Я просто пытаюсь снова и
Снова и снова и снова

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

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

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

156
00:08:08,200 --> 00:08:11,870
это понятие в программировании зацикливание,
делать что-то снова и снова.

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

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

159
00:08:17,870 --> 00:08:18,730
Повторяйте до тех пор.

160
00:08:18,730 --> 00:08:21,400
Таким образом, мы могли бы сделать что-то
как повторять до.

161
00:08:21,400 --> 00:08:23,760
И не то, что вы повторить, пока точно?

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

163
00:08:27,720 --> 00:08:28,540
>> ОК.

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

165
00:08:31,974 --> 00:08:33,140
Позвольте мне идти вперед и делать это.

166
00:08:33,140 --> 00:08:35,559
Обратите внимание на то, что, как вы, возможно,
обнаружил под контролем,

167
00:08:35,559 --> 00:08:38,409
есть этот повтор блок, который
не выглядит, как будто это что большой.

168
00:08:38,409 --> 00:08:41,039
Там не так много места в
между этими двумя желтыми линиями.

169
00:08:41,039 --> 00:08:43,539
Но так как некоторые из вас, возможно,
заметили, если вы перетащить,

170
00:08:43,539 --> 00:08:45,150
обратите внимание, как он растет, чтобы заполнить форму.

171
00:08:45,150 --> 00:08:46,274
>> И вы можете даже втиснуть больше.

172
00:08:46,274 --> 00:08:48,670
Это будет просто продолжать расти, если
перетаскивании и парить над ним.

173
00:08:48,670 --> 00:08:51,110
И я не знаю, что это
лучше всего здесь, так что давайте

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

175
00:08:54,760 --> 00:08:56,720
и нажмите на зеленый флаг.

176
00:08:56,720 --> 00:08:59,110
А теперь обратите внимание, что это не совсем там.

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

178
00:09:02,400 --> 00:09:05,140
И что вообще делает
получить его весь путь,

179
00:09:05,140 --> 00:09:10,510
Но разве не было бы более надежным
способ, чем произвольно выяснить,

180
00:09:10,510 --> 00:09:12,640
сколько ходов сделать?

181
00:09:12,640 --> 00:09:17,680
Что может быть лучше блок
чем повторить 10 раз быть?

182
00:09:17,680 --> 00:09:20,380
>> Да, так почему бы не сделать что-то навсегда?

183
00:09:20,380 --> 00:09:24,390
А теперь позвольте мне перенести этот кусок головоломки
внутри там, и избавиться от этого.

184
00:09:24,390 --> 00:09:28,300
Теперь обратите внимание независимо от того, где Царапина
начинается, он идет к краю.

185
00:09:28,300 --> 00:09:30,700
И к счастью MIT,
который делает нуля, просто

186
00:09:30,700 --> 00:09:33,190
не гарантирует, что он никогда
полностью исчезает.

187
00:09:33,190 --> 00:09:35,360
Вы всегда можете схватить его за хвост.

188
00:09:35,360 --> 00:09:37,680
>> И точно так же интуитивно,
Почему он продолжает двигаться?

189
00:09:37,680 --> 00:09:38,892
Что здесь происходит?

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

191
00:09:41,440 --> 00:09:43,824
Он, кажется, остановилось, но
а затем, если я поднимаю и перетащить

192
00:09:43,824 --> 00:09:45,240
он продолжает хотеть идти туда.

193
00:09:45,240 --> 00:09:46,123
Почему это?

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

195
00:09:51,610 --> 00:09:54,360
Действительно, компьютер буквально
собирается делать то, что вы скажете ей сделать.

196
00:09:54,360 --> 00:09:58,380
Так что, если вы сказали это раньше сделать
следующая вещь навсегда, двигаться 10 шагов,

197
00:09:58,380 --> 00:10:01,860
это будет продолжать идти и идти
пока я не ударил красный знак стоп

198
00:10:01,860 --> 00:10:04,620
и остановить программу в целом.

199
00:10:04,620 --> 00:10:06,610
>> Так что даже если вы этого не сделали
сделать это, как я мог

200
00:10:06,610 --> 00:10:09,510
сделать Царапины двигаться быстрее
по экрану?

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

202
00:10:12,060 --> 00:10:13,280
Другие шаги, не так ли?

203
00:10:13,280 --> 00:10:15,710
Таким образом, вместо того, чтобы делать 10
в то время, почему бы нам не

204
00:10:15,710 --> 00:10:20,100
идти вперед и изменить его, целью которых
что бы вы propose-- 50?

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

206
00:10:24,410 --> 00:10:27,180
>> И это, конечно же, это просто
проявление анимации.

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

208
00:10:28,060 --> 00:10:33,090
Это просто показывает вам человека A
целая куча неподвижных изображений на самом деле,

209
00:10:33,090 --> 00:10:34,160
на самом деле, очень быстро.

210
00:10:34,160 --> 00:10:36,500
И поэтому, если мы просто рассказываю
ему двигаться больше шагов,

211
00:10:36,500 --> 00:10:39,750
мы просто имея эффект быть
изменение, где он находится на экране

212
00:10:39,750 --> 00:10:42,900
все более быстро за единицу времени.

213
00:10:42,900 --> 00:10:46,454
>> Теперь следующий вызов, который я предложил
должен был иметь его отскакивают от края.

214
00:10:46,454 --> 00:10:49,120
И не зная, что головоломки
штук exist--, потому что это нормально

215
00:10:49,120 --> 00:10:53,030
если вы не добраться до
этап challenge--, что

216
00:10:53,030 --> 00:10:54,280
вы хотите сделать интуитивно?

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

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

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

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

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

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

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

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

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

226
00:11:23,920 --> 00:11:25,000
или сделать это.

227
00:11:25,000 --> 00:11:27,380
И вы даже можете их гнездо
сделать несколько вещей.

228
00:11:27,380 --> 00:11:34,910
Или, если вы не прошли еще здесь,
идти вперед к категории Sensing

229
00:11:34,910 --> 00:11:39,612
и-- давайте посмотрим, если он здесь.

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

231
00:11:43,050 --> 00:11:52,050
>> Так что блок может быть полезным здесь
чтобы обнаружить, если он со сцены?

232
00:11:52,050 --> 00:11:56,740
Да, обратите внимание, что некоторые из этих блоков
могут быть параметризованы, если можно так выразиться.

233
00:11:56,740 --> 00:12:00,706
Они могут быть настроены рода, а не
В отличие от HTML вчера с атрибутами,

234
00:12:00,706 --> 00:12:03,330
где эти атрибуты рода
настроить поведение тега.

235
00:12:03,330 --> 00:12:08,880
Точно так же здесь, я могу захватить этот трогательный
блок и изменить и задать вопрос,

236
00:12:08,880 --> 00:12:11,500
вы касаясь мышью
указатель, как курсор

237
00:12:11,500 --> 00:12:13,250
или вы прикоснувшись к краю?

238
00:12:13,250 --> 00:12:15,210
>> Итак, позвольте мне пойти и сделать это.

239
00:12:15,210 --> 00:12:18,130
Я собираюсь уменьшить на мгновение.

240
00:12:18,130 --> 00:12:21,320
Позвольте мне захватить этот кусок головоломки
здесь, это кусок головоломки это,

241
00:12:21,320 --> 00:12:24,570
и я собираюсь перемешивать
они на мгновение.

242
00:12:24,570 --> 00:12:27,620
Я буду двигаться в этом,
изменить это трогательной край,

243
00:12:27,620 --> 00:12:38,590
и я собираюсь сделать это движение.

244
00:12:38,590 --> 00:12:40,490
Так вот некоторые ингредиенты.

245
00:12:40,490 --> 00:12:42,570
Я думаю, что у меня есть все, что захочу.

246
00:12:42,570 --> 00:12:47,710
>> кто-то хотел бы предложить, как я
может соединить их, может быть, сверху вниз

247
00:12:47,710 --> 00:12:52,020
для того, чтобы решить проблему наличия
Царапина движение справа налево направо

248
00:12:52,020 --> 00:12:57,020
слева направо, налево, каждый
Время как раз отражаясь от стены?

249
00:12:57,020 --> 00:12:58,050
Что я хочу сделать?

250
00:12:58,050 --> 00:13:01,097
Какой блок я должен подключиться к
"Когда зеленый флаг щелкнул первый"?

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

252
00:13:04,060 --> 00:13:06,200
>> ОК, так что давайте начнем с «навсегда».

253
00:13:06,200 --> 00:13:07,170
То, что происходит внутри дальше?

254
00:13:07,170 --> 00:13:10,290
Кто-нибудь другой.

255
00:13:10,290 --> 00:13:11,850
OK, двигаться шаги.

256
00:13:11,850 --> 00:13:12,350
Отлично.

257
00:13:12,350 --> 00:13:14,470
И что?

258
00:13:14,470 --> 00:13:15,120
Так то если.

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

260
00:13:17,720 --> 00:13:19,500
он просто будет расти, чтобы заполнить.

261
00:13:19,500 --> 00:13:21,500
Это будет просто прыгать в том, где я хочу.

262
00:13:21,500 --> 00:13:25,920
>> И что же я ставлю между
ИФ и тогда?

263
00:13:25,920 --> 00:13:27,180
Возможно ", если вы прикасаетесь край».

264
00:13:27,180 --> 00:13:31,800
И заметьте, опять же, это слишком большой
для нее, но она будет расти, чтобы заполнить.

265
00:13:31,800 --> 00:13:35,002
А затем повернуть на 15 градусов?

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

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

268
00:13:38,800 --> 00:13:41,196
Да, так что 180 будет вращаться
меня все наоборот.

269
00:13:41,196 --> 00:13:42,570
Итак, давайте посмотрим, если я получил это право.

270
00:13:42,570 --> 00:13:43,930
Позвольте мне уменьшить изображение.

271
00:13:43,930 --> 00:13:45,130
>> Позвольте мне перетащить наскрести.

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

273
00:13:50,030 --> 00:13:52,231
Как я могу сбросить его легко?

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

275
00:13:59,879 --> 00:14:01,045
Я собираюсь немного обмануть.

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

277
00:14:04,074 --> 00:14:05,990
Таким образом, я добавил еще один
блок, просто чтобы быть ясным.

278
00:14:05,990 --> 00:14:08,424
Я хочу, чтобы он указывает на 90 градусов
вправо по умолчанию,

279
00:14:08,424 --> 00:14:10,840
так что я просто хочу, чтобы сказать ему,
сделать это программно.

280
00:14:10,840 --> 00:14:11,632
И здесь мы идем.

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

282
00:14:14,740 --> 00:14:15,740
Мы, кажется, сделали это.

283
00:14:15,740 --> 00:14:19,980
Это немного странно, потому что
он идет с ног на голову.

284
00:14:19,980 --> 00:14:21,250
Давайте назовем, что ошибка.

285
00:14:21,250 --> 00:14:22,120
Это ошибка.

286
00:14:22,120 --> 00:14:27,320
Исправлена ​​ошибка, ошибка в программе, а
логическая ошибка, что я, человек, сделал.

287
00:14:27,320 --> 00:14:28,985
Почему он собирается с ног на голову?

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

289
00:14:33,560 --> 00:14:35,250
Оказалась MIT завинтить или я?

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

291
00:14:38,840 --> 00:14:42,550
>> Да, я имею в виду, это не в MIT
неисправность. Они дали мне кусок головоломки

292
00:14:42,550 --> 00:14:44,970
что говорит повернуть некоторое количество градусов.

293
00:14:44,970 --> 00:14:47,672
И по предложению Виктории,
Я превращаюсь на 180 градусов,

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

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

296
00:14:53,700 --> 00:14:55,860
и это на самом деле не
что я хочу, по-видимому.

297
00:14:55,860 --> 00:14:58,026
Потому что, по крайней мере, он в
это двумерная мир,

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

299
00:15:00,740 --> 00:15:04,030
>> Я, вероятно, хотите, чтобы использовать то, что блок
вместо того, чтобы, основываясь на то, что вы видите здесь?

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

301
00:15:11,890 --> 00:15:14,790
Как мы можем это исправить?

302
00:15:14,790 --> 00:15:18,380
Да, таким образом, мы могли бы указать
в противоположном направлении.

303
00:15:18,380 --> 00:15:22,300
И на самом деле даже это
не будет достаточно,

304
00:15:22,300 --> 00:15:26,410
потому что мы можем только жесткий код
чтобы указывать влево или вправо.

305
00:15:26,410 --> 00:15:27,920
>> Вы знаете, что мы можем сделать?

306
00:15:27,920 --> 00:15:30,160
Похоже, что у нас есть
удобный блок здесь.

307
00:15:30,160 --> 00:15:32,987
Если я приближать см
то, что мы, как здесь?

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

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

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

311
00:15:45,440 --> 00:15:49,510
>> Этот блок представляется эквивалентным
ко всей этой тройке блоков

312
00:15:49,510 --> 00:15:50,880
что мы имеем здесь.

313
00:15:50,880 --> 00:15:54,670
Так получается, что я могу упростить свою
Программа, избавившись от всего этого

314
00:15:54,670 --> 00:15:58,270
и просто поставить это здесь.

315
00:15:58,270 --> 00:16:01,620
А теперь он еще немного
глючит, и это нормально сейчас.

316
00:16:01,620 --> 00:16:03,370
Мы оставим это будет.

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

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

319
00:16:09,060 --> 00:16:13,430
это в идеале сделать свой код,
просто, как можно более компактным,

320
00:16:13,430 --> 00:16:15,650
в то же время, как
читаемым, насколько это возможно.

321
00:16:15,650 --> 00:16:20,310
Вы не хотите, чтобы сделать это так лаконичен
что это трудно понять.

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

323
00:16:22,826 --> 00:16:24,200
и это, возможно, хорошая вещь.

324
00:16:24,200 --> 00:16:27,280
Я абстрагируются понятие
проверки, являетесь ли Вы

325
00:16:27,280 --> 00:16:29,120
на краю с помощью только одного блока.

326
00:16:29,120 --> 00:16:31,520
Теперь мы можем получать удовольствие с этим, на самом деле.

327
00:16:31,520 --> 00:16:35,790
Это не добавляет столько
интеллектуальные ценности, но игривая значение.

328
00:16:35,790 --> 00:16:39,730
Я собираюсь идти вперед
и захватить этот звук здесь.

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

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

331
00:16:46,420 --> 00:16:52,070
Я собираюсь записать следующее,
обеспечивая доступ к моему микрофону.

332
00:16:52,070 --> 00:16:53,181
>> Вот так.

333
00:16:53,181 --> 00:16:53,680
Уч.

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

335
00:16:58,710 --> 00:17:01,140
Давайте попробуем это снова.

336
00:17:01,140 --> 00:17:02,279
Вот так.

337
00:17:02,279 --> 00:17:03,570
ОК, я записал неправильные вещи.

338
00:17:03,570 --> 00:17:04,580
Вот так.

339
00:17:04,580 --> 00:17:05,080
Уч.

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

341
00:17:07,910 --> 00:17:08,800
Уч.

342
00:17:08,800 --> 00:17:09,300
Отлично.

343
00:17:09,300 --> 00:17:10,791
Теперь мне нужно, чтобы избавиться от этого.

344
00:17:10,791 --> 00:17:11,290
Отлично.

345
00:17:11,290 --> 00:17:13,950
>> Так что теперь у меня есть
Запись только "Ой".

346
00:17:13,950 --> 00:17:18,040
Так что теперь я собираюсь пойти
вперед и называем это "Уч."

347
00:17:18,040 --> 00:17:20,270
Я собираюсь вернуться
для моих сценариев, и теперь

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

349
00:17:25,460 --> 00:17:28,920
Я собираюсь тащить это, и где
я должен поставить это на комический эффект?

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

351
00:17:31,740 --> 00:17:37,860
Да, так что теперь это своего рода
глючит, потому что теперь это block--

352
00:17:37,860 --> 00:17:42,050
обратите внимание, как это ", если на краю,
отскока "является своего рода самодостаточным.

353
00:17:42,050 --> 00:17:43,704
Поэтому мне нужно, чтобы исправить это.

354
00:17:43,704 --> 00:17:44,870
Позвольте мне идти вперед и делать это.

355
00:17:44,870 --> 00:17:48,630
Позвольте мне избавиться от этого и вернуться
к нашему первоначальному, более преднамеренным

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

357
00:17:49,870 --> 00:18:01,080
Так что "если вы прикасаетесь край, а затем" Я хочу
повернуть, как это было предложено Виктория,

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

359
00:18:02,480 --> 00:18:05,497
И я хочу, чтобы играть
звук "Уч" есть?

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

361
00:18:11,800 --> 00:18:15,580
>> Да, обратите внимание, что это за пределами
что желтый блок.

362
00:18:15,580 --> 00:18:17,680
Так что это тоже было бы
ошибка, но я заметил это.

363
00:18:17,680 --> 00:18:21,290
Так что я собираюсь тащить его сюда,
и заметьте, теперь это внутри «если».

364
00:18:21,290 --> 00:18:24,250
Так что "если" это своего рода
одноименных руки, как блоттинга

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

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

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

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

369
00:18:36,470 --> 00:18:39,910
>> DAVID Маланом: И
будет просто продолжаться вечно.

370
00:18:39,910 --> 00:18:44,160
Теперь просто ускорить вещи
здесь, позвольте мне идти вперед и открыть,

371
00:18:44,160 --> 00:18:50,460
давайте say-- отпустить меня в какой-то
моего собственного материала от класса.

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

373
00:18:53,000 --> 00:19:00,220
И позвольте мне открыть, скажем, это
один сделанный одним из наших обучающих товарищей

374
00:19:00,220 --> 00:19:01,500
Несколько лет назад.

375
00:19:01,500 --> 00:19:04,732
Так что некоторые из вас могут вспомнить
эта игра от прошлых лет,

376
00:19:04,732 --> 00:19:05,940
и это на самом деле замечательно.

377
00:19:05,940 --> 00:19:08,190
Несмотря на то, что мы сделали
Простейшим программ прямо сейчас,

378
00:19:08,190 --> 00:19:09,980
давайте рассмотрим, что это
на самом деле выглядит.

379
00:19:09,980 --> 00:19:10,650
Позвольте мне ударил играть.

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

381
00:19:14,210 --> 00:19:18,980
>> Так что в этой игре, у нас есть
лягушки, и с помощью стрелки keys--

382
00:19:18,980 --> 00:19:23,340
он принимает большие шаги, чем я remember--
У меня есть контроль над этой лягушки.

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

384
00:19:29,630 --> 00:19:34,735
И давайте see--, если я иду здесь, я
придется ждать, пока журнал для прокрутки по.

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

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

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

388
00:19:42,240 --> 00:19:43,495
Это своего рода ошибка.

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

390
00:19:45,980 --> 00:19:46,480
Отлично.

391
00:19:46,480 --> 00:19:51,550
Я на это здесь,
там, а затем вы держите

392
00:19:51,550 --> 00:19:54,100
идти, пока не получите все
лягушки в кувшинок.

393
00:19:54,100 --> 00:19:55,920
Теперь это может выглядеть
все более сложными,

394
00:19:55,920 --> 00:19:57,840
но давайте попробуем разбить
это вниз мысленно

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

396
00:20:00,040 --> 00:20:03,910
Так что, вероятно, головоломка
часть, которую мы еще не видели

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

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

399
00:20:11,660 --> 00:20:15,965
затем сделать что-то с Scratch--
возможно переместить его 10 шагов таким образом.

400
00:20:15,965 --> 00:20:20,240
Если вниз клавиша нажата, двигаться 10 шагов
таким образом, или левая клавиша, двигаться 10 шагов

401
00:20:20,240 --> 00:20:21,710
Таким образом, 10 шагов, которые.

402
00:20:21,710 --> 00:20:23,644
Я четко повернул кошку в лягушку.

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

404
00:20:26,060 --> 00:20:28,440
только что импортировали картину лягушки.

405
00:20:28,440 --> 00:20:29,570
>> Но что еще происходит?

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

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

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

409
00:20:38,320 --> 00:20:42,730
Что делает все move--
то, что программирование построить?

410
00:20:42,730 --> 00:20:44,950
>> Motion, sure-- так
переместить блок, наверняка.

411
00:20:44,950 --> 00:20:49,330
И то, что этот шаг блок
внутри, скорее всего?

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

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

414
00:20:54,070 --> 00:20:57,330
И вот что делает журналы и
кувшинок и все остальное движение

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

416
00:20:57,990 --> 00:21:00,270
Это просто происходит бесконечно.

417
00:21:00,270 --> 00:21:03,180
>> Почему некоторые из автомобилей
двигаться быстрее, чем другие?

418
00:21:03,180 --> 00:21:06,607
Что отличает этих программ?

419
00:21:06,607 --> 00:21:09,690
Да, вероятно, некоторые из них принимают
больше шагов сразу и некоторые из них

420
00:21:09,690 --> 00:21:10,690
меньше шагов сразу.

421
00:21:10,690 --> 00:21:14,670
И визуальный эффект
очень быстро по сравнению с медленным.

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

423
00:21:16,030 --> 00:21:19,700
Когда я получил мою лягушку весь путь
через дорогу и реку

424
00:21:19,700 --> 00:21:23,560
на лилии площадку, что-то
Примечательно, произошло.

425
00:21:23,560 --> 00:21:26,540
То, что произошло, как только я сделал это?

426
00:21:26,540 --> 00:21:27,210
Она остановилась.

427
00:21:27,210 --> 00:21:29,680
Эта лягушка остановилась, и
Я получил вторую лягушку.

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

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

430
00:21:36,020 --> 00:21:38,660
>> Да, так что есть какая-то
"Если" состояние там, тоже.

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

432
00:21:41,909 --> 00:21:45,300
Можно сказать, если вы прикасаетесь
Другое дело, на экране,

433
00:21:45,300 --> 00:21:47,720
если вы прикасаясь к кувшинки ", а затем".

434
00:21:47,720 --> 00:21:50,810
И тогда, когда мы
сделать второй лягушки появляются.

435
00:21:50,810 --> 00:21:54,969
Так что, хотя эта игра, безусловно,
очень устарели, хотя на первый взгляд

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

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

438
00:22:00,390 --> 00:22:03,850
основанный на его памяти или видео
версии вчерашнего дня о нем.

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

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

441
00:22:11,550 --> 00:22:15,519
как мы уже обсуждали, петли и
условия, и именно об этом.

442
00:22:15,519 --> 00:22:17,060
Там в несколько других особенностей любитель.

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

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

445
00:22:20,964 --> 00:22:23,380
Но по большей части, вы
есть в этом языке, на пустом месте,

446
00:22:23,380 --> 00:22:25,350
все фундаментальные
строительные блоки, которые вам

447
00:22:25,350 --> 00:22:29,280
есть в C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
и любое количество других языков.

449
00:22:32,960 --> 00:22:36,720
Любые вопросы на пустом месте?

450
00:22:36,720 --> 00:22:37,220
Отлично.

451
00:22:37,220 --> 00:22:40,303
Поэтому мы не будем погружаться глубже поцарапать,
хотя вы всегда можете в эти выходные,

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

453
00:22:42,860 --> 00:22:44,220
познакомить их с нуля.

454
00:22:44,220 --> 00:22:47,960
Это на самом деле удивительно игривый
среда с, как говорят его авторы,

455
00:22:47,960 --> 00:22:49,120
очень высокие потолки.

456
00:22:49,120 --> 00:22:51,670
Несмотря на то, что мы начали с
очень низкоуровневых деталей,

457
00:22:51,670 --> 00:22:54,890
вы действительно можете сделать совсем немного
с ним, и это, пожалуй,

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

459
00:22:57,360 --> 00:23:02,920
>> Но давайте теперь перейти к некоторым более
сложные проблемы, если вы будете,

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

461
00:23:05,870 --> 00:23:09,500
У нас была эта телефонная книга earlier-- здесь
еще один раз для discussion--

462
00:23:09,500 --> 00:23:13,460
что мы смогли найти
более эффективно, потому что

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

464
00:23:15,270 --> 00:23:17,655
И просто быть понятно, что
Предполагалось, что делает я

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

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

467
00:23:23,342 --> 00:23:25,300
Это Майк Смит был в
телефонная книга, хотя я

468
00:23:25,300 --> 00:23:27,410
будет иметь возможность обрабатывать
сценарий без него

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

470
00:23:30,720 --> 00:23:31,806
Книга в алфавитном порядке.

471
00:23:31,806 --> 00:23:33,930
И это очень щедрый
предположение, потому что

472
00:23:33,930 --> 00:23:36,580
означает someone-- Я вроде
резки угол,

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

474
00:23:40,580 --> 00:23:43,120
>> Но что, если телефон
Книга была НЕСОРТИРОВАННАЯ?

475
00:23:43,120 --> 00:23:47,050
Может быть, Verizon стал ленивым, просто бросил
имена и номера каждого в там

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

477
00:23:50,120 --> 00:23:54,570
А сколько времени занимает меня
чтобы найти кого-то вроде Майка Смита?

478
00:23:54,570 --> 00:23:58,160
1000 страница телефон book-- сколько
страницы я должен просмотреть?

479
00:23:58,160 --> 00:23:58,905
>> Все они.

480
00:23:58,905 --> 00:24:00,030
Ты вроде не повезло.

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

482
00:24:03,420 --> 00:24:04,450
случайным образом сортируются.

483
00:24:04,450 --> 00:24:06,910
Вы можете получить повезло и найти Mike
на самой первой странице, потому что он

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

485
00:24:08,826 --> 00:24:10,760
Но он, возможно, был последним, тоже.

486
00:24:10,760 --> 00:24:12,500
>> Так в случайном порядке не хорошо.

487
00:24:12,500 --> 00:24:16,750
Поэтому предположим, что мы должны сортировать
Телефонная книга или в общих данных сортировки

488
00:24:16,750 --> 00:24:18,520
что мы дали.

489
00:24:18,520 --> 00:24:19,440
Как мы можем сделать это?

490
00:24:19,440 --> 00:24:21,360
>> Что ж, позвольте мне попробовать
простой пример здесь.

491
00:24:21,360 --> 00:24:24,290
Позвольте мне идти вперед и бросить
Несколько номеров на доске.

492
00:24:24,290 --> 00:24:35,480
Пусть числа у нас есть есть,
скажем, четыре, два, один и три.

493
00:24:35,480 --> 00:24:38,390
И, Бен, сортировать эти цифры для нас.

494
00:24:38,390 --> 00:24:39,017
>> Хорошо.

495
00:24:39,017 --> 00:24:39,850
Как ты это сделал?

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

497
00:24:42,731 --> 00:24:43,230
Отлично.

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

499
00:24:44,710 --> 00:24:46,084
и это действительно хорошая интуиция.

500
00:24:46,084 --> 00:24:48,080
И понимаем, что мы
люди на самом деле довольно

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

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

503
00:24:51,810 --> 00:24:54,860
Как только вы начинаете иметь сотни
чисел, тысячи чисел,

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

505
00:24:58,440 --> 00:25:00,620
если предположить, что существуют
пробелы в цифрах.

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

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

508
00:25:07,150 --> 00:25:08,930
был поиск наименьшего числа.

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

510
00:25:12,900 --> 00:25:14,830
компьютер на самом деле
чуть более ограниченным.

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

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

513
00:25:20,770 --> 00:25:24,450
но очень небольшое число
байтов в данный момент времени.

514
00:25:24,450 --> 00:25:28,480
>> Поэтому, учитывая, что мы действительно имеем
четыре отдельные значения here--

515
00:25:28,480 --> 00:25:32,440
и вы можете думать о Бен как имеющий
шоры, если бы он был компьютер типа

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

517
00:25:36,450 --> 00:25:39,720
поэтому мы обычно будем считать, как и в
Английский, мы будем читать справа налево.

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

519
00:25:42,870 --> 00:25:44,770
понял, что это довольно большой
number-- позвольте мне продолжать поиски.

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

521
00:25:45,357 --> 00:25:45,940
Подожди минуту.

522
00:25:45,940 --> 00:25:47,070
Два меньше четырех.

523
00:25:47,070 --> 00:25:47,986
Я буду помнить.

524
00:25:47,986 --> 00:25:49,070
Два в настоящее время является наименьшим.

525
00:25:49,070 --> 00:25:50,417
Теперь одно-- это еще лучше.

526
00:25:50,417 --> 00:25:51,250
Это даже меньше.

527
00:25:51,250 --> 00:25:54,000
Я собираюсь забыть о двух
и просто вспомнить его сейчас.

528
00:25:54,000 --> 00:25:56,550
>> И он мог перестать смотреть?

529
00:25:56,550 --> 00:25:58,360
Ну, он мог на основе
на этой информации,

530
00:25:58,360 --> 00:26:00,477
но он лучше бы поиск
остальная часть списка.

531
00:26:00,477 --> 00:26:02,060
Потому что, если ноль были в списке?

532
00:26:02,060 --> 00:26:03,643
Что делать, если отрицательный были в списке?

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

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

535
00:26:08,729 --> 00:26:10,020
Таким образом, мы смотрим на остальной части этого.

536
00:26:10,020 --> 00:26:11,394
Three--, что это пустая трата времени.

537
00:26:11,394 --> 00:26:13,540
Не повезло, но я был
до сих пор правильно сделать это.

538
00:26:13,540 --> 00:26:17,857
И вот теперь он, вероятно,
выбирается наименьшее число

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

540
00:26:20,440 --> 00:26:23,480
Теперь то, что вы делали дальше, несмотря на то,
Вы не думали об этом почти

541
00:26:23,480 --> 00:26:25,962
до такой степени?

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

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

544
00:26:28,920 --> 00:26:30,860
Так вот четыре.

545
00:26:30,860 --> 00:26:32,110
Это в настоящее время самый маленький.

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

547
00:26:33,220 --> 00:26:33,900
Уже нет.

548
00:26:33,900 --> 00:26:34,770
Теперь я видел два.

549
00:26:34,770 --> 00:26:36,630
Это следующий наименьший элемент.

550
00:26:36,630 --> 00:26:40,800
Three--, что не меньше, так
Теперь Бен может вырывать два.

551
00:26:40,800 --> 00:26:44,510
>> И теперь мы повторяем процесс, а
конечно три получает вытащил следующий.

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

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

554
00:26:46,990 --> 00:26:50,140
А теперь мы из чисел,
так что список должен быть отсортирован.

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

556
00:26:51,960 --> 00:26:56,610
Компьютер ученый будет
называем это "выбор рода"

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

558
00:27:00,880 --> 00:27:03,807
и снова и снова выбор
наименьшее число.

559
00:27:03,807 --> 00:27:06,140
И что приятно о нем
это просто так чертовски интуитивным.

560
00:27:06,140 --> 00:27:07,470
Это так просто.

561
00:27:07,470 --> 00:27:11,100
И вы можете повторить то же самое
операция снова и снова.

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

563
00:27:12,150 --> 00:27:17,170
>> В этом случае это было быстро, но
как долго это на самом деле взять?

564
00:27:17,170 --> 00:27:19,880
Давайте сделаем это, кажется, и
чувствовать себя немного более утомительным.

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

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

567
00:27:26,160 --> 00:27:28,780
Я просто хотел больше этого
Время, чем просто четыре.

568
00:27:28,780 --> 00:27:30,780
Так что, если у меня есть целое
связка чисел now-- его

569
00:27:30,780 --> 00:27:32,420
даже не имеет значения
что они are-- давайте

570
00:27:32,420 --> 00:27:34,380
думать о том, что это
Алгоритм очень похож.

571
00:27:34,380 --> 00:27:35,857
>> Предположим, что существуют числа там.

572
00:27:35,857 --> 00:27:38,190
Опять же, не имеет значения, что
они есть, но они случайным образом.

573
00:27:38,190 --> 00:27:39,679
Я применяю алгоритм Бен.

574
00:27:39,679 --> 00:27:41,220
Мне нужно, чтобы выбрать наименьшее число.

575
00:27:41,220 --> 00:27:41,761
Что я делаю?

576
00:27:41,761 --> 00:27:44,240
И я собираюсь физически
сделать это на этот раз, чтобы действовать его.

577
00:27:44,240 --> 00:27:46,099
Глядя, глядя,
глядя, глядя, глядя.

578
00:27:46,099 --> 00:27:48,140
Только к тому времени я получаю
конец списка может

579
00:27:48,140 --> 00:27:51,230
Я понимаю, что самый маленький
число было два на этот раз.

580
00:27:51,230 --> 00:27:52,720
Один не в списке.

581
00:27:52,720 --> 00:27:54,400
Так что я положил два.

582
00:27:54,400 --> 00:27:55,590
>> Что делать дальше?

583
00:27:55,590 --> 00:27:58,600
Глядя, глядя, глядя, глядя.

584
00:27:58,600 --> 00:28:02,250
Теперь я нашел номер семь, потому что
есть пробелы в этих numbers--

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

586
00:28:03,300 --> 00:28:03,800
Отлично.

587
00:28:03,800 --> 00:28:06,030
Так что теперь я могу положить вниз семь.

588
00:28:06,030 --> 00:28:08,860
Глядя глядя, глядя.

589
00:28:08,860 --> 00:28:11,030
>> Теперь я предполагаю, из
Конечно же, что Бен не

590
00:28:11,030 --> 00:28:14,780
имеют дополнительную оперативную память, дополнительные
память, потому что, конечно же,

591
00:28:14,780 --> 00:28:16,080
Я смотрю на тот же номер.

592
00:28:16,080 --> 00:28:18,246
Конечно, я мог бы помнить,
все эти цифры,

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

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

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

596
00:28:24,430 --> 00:28:26,170
потому что у него уже есть
возможность поиска

597
00:28:26,170 --> 00:28:27,540
по номерам на доске.

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

599
00:28:29,373 --> 00:28:32,490
потому что он все еще может как компьютер
только смотреть, мы уже говорили, один номер

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

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

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

603
00:28:39,170 --> 00:28:44,200
Я буквально должен просто продолжать идти
взад и вперед через нее, выщипывания

604
00:28:44,200 --> 00:28:45,710
следующий наименьшее число.

605
00:28:45,710 --> 00:28:48,810
И, как вы можете отчасти сделать вывод
от моих глупых движений,

606
00:28:48,810 --> 00:28:50,860
это просто становится очень
утомительно очень быстро,

607
00:28:50,860 --> 00:28:54,850
и я, кажется, идет назад и
вперед, взад и вперед, совсем немного.

608
00:28:54,850 --> 00:29:03,220
Теперь, чтобы быть справедливым, я не должен идти
совсем как, ну, давайте see-- быть справедливым,

609
00:29:03,220 --> 00:29:06,310
Я не придется ходить довольно
столько шагов, каждый раз.

610
00:29:06,310 --> 00:29:09,200
Потому что, конечно же, как я
выбрать номера из списка,

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

612
00:29:11,860 --> 00:29:14,240
>> Так что давайте думать о
сколько шагов я на самом деле

613
00:29:14,240 --> 00:29:16,010
тащась через каждый раз.

614
00:29:16,010 --> 00:29:18,950
В первой ситуации
у нас было 16 номеров,

615
00:29:18,950 --> 00:29:22,210
и так maximally-- давайте просто
сделать это для discussion--

616
00:29:22,210 --> 00:29:25,640
Я должен был смотреть через 16 лет
номера, чтобы найти самый маленький.

617
00:29:25,640 --> 00:29:28,420
Но как только я исторгли
наименьшее число, как

618
00:29:28,420 --> 00:29:30,590
долгое время был оставшийся список, конечно?

619
00:29:30,590 --> 00:29:31,420
Только 15.

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

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

622
00:29:36,832 --> 00:29:39,540
Но теперь, конечно, список,
тоже меньше, чем это было раньше.

623
00:29:39,540 --> 00:29:42,540
Так сколько шагов сделал я
должны взять на себя в следующий раз?

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

625
00:29:49,970 --> 00:29:53,146
Так что теперь компьютерный ученый будет
спросите, ну, что же, что все равны?

626
00:29:53,146 --> 00:29:55,770
Это на самом деле равно некоторые конкретные
число, которое мы могли бы, конечно,

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

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

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

630
00:30:06,240 --> 00:30:09,860
Это 16, но как я уже сказал раньше,
давайте просто назвать размер проблемы

631
00:30:09,860 --> 00:30:10,970
п, где п некоторое число.

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

633
00:30:13,220 --> 00:30:13,761
Я не знаю.

634
00:30:13,761 --> 00:30:14,390
Я не забочусь.

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

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

637
00:30:19,420 --> 00:30:22,350
что кто-то может претендовать
лучше или хуже.

638
00:30:22,350 --> 00:30:25,430
>> Так что получается, и я только
знаю, что это из начальной школы,

639
00:30:25,430 --> 00:30:34,790
что это на самом деле работает, к тому же
вещь, как п по п плюс один больше двух.

640
00:30:34,790 --> 00:30:40,020
И это происходит в равных условиях,
Конечно же, п квадрат плюс п над ними.

641
00:30:40,020 --> 00:30:43,250
Так что, если я хотел формулу
На сколько шагов

642
00:30:43,250 --> 00:30:46,330
были вовлечены в глядя на все
о снова и снова эти цифры

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

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

645
00:30:53,430 --> 00:30:54,500
Это просто выглядит неаккуратно.

646
00:30:54,500 --> 00:30:56,470
Я просто очень хочу
Общий смысл вещей.

647
00:30:56,470 --> 00:30:58,810
И вы можете вспомнить из
средней школы, что там

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

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

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

651
00:31:07,550 --> 00:31:11,920
Чем больше п получает, что
из этих вопросов больше всего?

652
00:31:11,920 --> 00:31:15,560
>> Другими словами, если я подключу
на миллион, п квадрат

653
00:31:15,560 --> 00:31:17,900
будет, скорее всего,
доминирующим фактором,

654
00:31:17,900 --> 00:31:21,670
потому что в миллион раз
сама по себе намного больше

655
00:31:21,670 --> 00:31:23,682
чем плюс один дополнительный миллион.

656
00:31:23,682 --> 00:31:24,390
Таким образом, вы знаете, что?

657
00:31:24,390 --> 00:31:27,305
Это такая большая штопка
номер, если вы квадратуры номер.

658
00:31:27,305 --> 00:31:28,430
Это не имеет никакого значения.

659
00:31:28,430 --> 00:31:30,596
Мы просто крест,
, и забыть об этом.

660
00:31:30,596 --> 00:31:34,250
И поэтому ученый сказал бы
что эффективность этого алгоритма

661
00:31:34,250 --> 00:31:37,850
составляет порядка п squared--
Я имею в виду действительно приближение.

662
00:31:37,850 --> 00:31:40,810
Это своего рода грубо п в квадрате.

663
00:31:40,810 --> 00:31:44,130
С течением времени, тем больше
и больше п получает, это

664
00:31:44,130 --> 00:31:47,610
является хорошей оценкой для того, что
эффективность или отсутствие эффективности

665
00:31:47,610 --> 00:31:49,400
этого алгоритма на самом деле.

666
00:31:49,400 --> 00:31:52,040
И я получить, что, конечно же,
от фактически делает математику.

667
00:31:52,040 --> 00:31:54,040
Но теперь я просто махал
мои руки, потому что я просто

668
00:31:54,040 --> 00:31:55,790
хотите общий смысл этого алгоритма.

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

670
00:31:58,850 --> 00:32:01,162
мы уже рассмотрели at-- линейный поиск.

671
00:32:01,162 --> 00:32:02,870
Когда я искал
для телефона book--

672
00:32:02,870 --> 00:32:05,980
не сортировать ее, поиск
через телефонную book--

673
00:32:05,980 --> 00:32:09,197
мы продолжали говорить, что это было
1000 шагов или 500 шагов.

674
00:32:09,197 --> 00:32:10,280
Но давайте обобщим это.

675
00:32:10,280 --> 00:32:12,860
Если есть п страниц
телефонная книга, что

676
00:32:12,860 --> 00:32:17,250
бегущая время или
эффективность линейного поиска?

677
00:32:17,250 --> 00:32:19,750
Это на порядок
сколько шагов, чтобы найти

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

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

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

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

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

683
00:32:38,380 --> 00:32:38,990
Как и 1000.

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

685
00:32:39,830 --> 00:32:41,790
Это худший из возможных ситуаций.

686
00:32:41,790 --> 00:32:44,410
Но опять же, мы удаляясь
из числа, как 1000 сейчас.

687
00:32:44,410 --> 00:32:45,730
Это просто п.

688
00:32:45,730 --> 00:32:47,470
>> Так что же логический вывод?

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

690
00:32:50,210 --> 00:32:55,280
может потребоваться, в самом худшем случае,
сколько шагов по порядку п?

691
00:32:55,280 --> 00:32:58,110
И в самом деле компьютер
ученый сказал бы

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

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

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

695
00:33:10,010 --> 00:33:13,170
как я только что сделал на второй
Алгоритм мы имели с телефонной книгой,

696
00:33:13,170 --> 00:33:16,040
куда мы пошли две страницы одновременно.

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

698
00:33:20,120 --> 00:33:21,910
если мы загнуть немного.

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

700
00:33:26,590 --> 00:33:28,900
это примерно то, что?

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

702
00:33:33,190 --> 00:33:38,490
Но я сделал требовать
минуту назад, что п над two--

703
00:33:38,490 --> 00:33:41,060
это своего рода такой же, как только п.

704
00:33:41,060 --> 00:33:44,050
Это просто постоянный множитель,
компьютерные ученые сказали бы.

705
00:33:44,050 --> 00:33:45,970
Давайте акцентировать внимание только на
переменные, really--

706
00:33:45,970 --> 00:33:47,780
самые большие переменные в уравнении.

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

708
00:33:52,530 --> 00:33:54,810
является своего рода принципиально то же самое.

709
00:33:54,810 --> 00:33:56,880
Это по-прежнему порядка п.

710
00:33:56,880 --> 00:34:01,930
Но я утверждал с моим изображением ранее
что третий алгоритм не был

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

712
00:34:02,480 --> 00:34:03,605
Это была не прямая линия.

713
00:34:03,605 --> 00:34:08,659
Это было то, что изогнутые линии, и
алгебраическая формула была что?

714
00:34:08,659 --> 00:34:11,812
Журнал так войти N-, основание два п.

715
00:34:11,812 --> 00:34:14,520
И мы не должны вдаваться в
много деталей на логарифмов сегодня,

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

717
00:34:17,394 --> 00:34:20,639
Потому что это все просто
постоянными факторами, так сказать,

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

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

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

721
00:34:33,949 --> 00:34:36,889
на самом деле утверждая, который
Алгоритм они будут использовать

722
00:34:36,889 --> 00:34:39,500
или то, что коэффициент полезного действия
из их алгоритм.

723
00:34:39,500 --> 00:34:42,960
>> И это не обязательно что-то
вы будете обсуждать в любом деталях,

724
00:34:42,960 --> 00:34:47,889
но хороший программист кто-то
который имеет солидный, формальный фон.

725
00:34:47,889 --> 00:34:50,120
Он в состоянии говорить
Вы в этом виде пути

726
00:34:50,120 --> 00:34:53,350
и на самом деле сделать
качественные аргументы,

727
00:34:53,350 --> 00:34:56,870
почему один алгоритм или
одна часть программного обеспечения

728
00:34:56,870 --> 00:35:00,165
превосходит в какой-то мере к другому.

729
00:35:00,165 --> 00:35:02,540
Потому что вы могли бы, конечно,
просто запустить программу одного человека

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

731
00:35:04,980 --> 00:35:06,710
и вы можете запустить некоторые
программа другого человека

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

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

734
00:35:12,840 --> 00:35:15,520
если вы будете, как раз на
бумага или просто в устной форме.

735
00:35:15,520 --> 00:35:18,430
Даже не запустить его без
даже пробовать входы выборки,

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

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

738
00:35:24,670 --> 00:35:28,460
почему их алгоритм, их секрет
соус для поиска миллиарды

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

740
00:35:30,580 --> 00:35:33,302
являются виды аргументов, которые они
в идеале должны быть в состоянии сделать.

741
00:35:33,302 --> 00:35:35,010
Или, по крайней мере, это
виды вещей

742
00:35:35,010 --> 00:35:40,211
что бы прийти в дискуссии на
хотя бы в очень формальной дискуссии.

743
00:35:40,211 --> 00:35:40,710
Отлично.

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

745
00:35:44,400 --> 00:35:48,200
Но я собираюсь предложить, что есть
другие способы сделать это, тоже.

746
00:35:48,200 --> 00:35:50,400
То, что я не очень нравится
об алгоритме Бен

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

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

749
00:35:56,930 --> 00:36:04,130
Что делать, если вместо того, чтобы я должен был сделать
что-то вроде этих чисел здесь

750
00:36:04,130 --> 00:36:08,200
и я должен был просто иметь дело с каждым
номер, в свою очередь, как я дал ему?

751
00:36:08,200 --> 00:36:10,780
>> Другими словами, здесь
мой список номеров.

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

753
00:36:12,944 --> 00:36:14,360
И я собираюсь сделать следующее.

754
00:36:14,360 --> 00:36:17,230
Я собираюсь вставить цифры
где они принадлежат скорее

755
00:36:17,230 --> 00:36:18,980
чем выбирая их по одному за раз.

756
00:36:18,980 --> 00:36:20,820
Другими словами, вот номер четыре.

757
00:36:20,820 --> 00:36:22,430
>> Вот мой первоначальный список.

758
00:36:22,430 --> 00:36:25,290
И я буду поддерживать
по существу, новый список здесь.

759
00:36:25,290 --> 00:36:26,710
Так что это старый список.

760
00:36:26,710 --> 00:36:28,560
Это новый список.

761
00:36:28,560 --> 00:36:30,220
Я вижу номер четыре в первую очередь.

762
00:36:30,220 --> 00:36:34,500
Мой новый список изначально пуст,
поэтому тривиальным случай

763
00:36:34,500 --> 00:36:36,410
что четыре теперь сортировали список.

764
00:36:36,410 --> 00:36:39,560
Я просто принимая число я дал,
и я ставлю его в своем новом списке.

765
00:36:39,560 --> 00:36:41,460
>> рассортированные этот новый список?

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

767
00:36:41,990 --> 00:36:45,090
Это глупо, потому что есть только один
элемент, но это абсолютно отсортирован.

768
00:36:45,090 --> 00:36:46,390
Там нет ничего, неуместны.

769
00:36:46,390 --> 00:36:49,290
Это более интересно, этот алгоритм,
когда я перехожу к следующему шагу.

770
00:36:49,290 --> 00:36:50,550
>> Теперь у меня есть один.

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

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

773
00:36:56,360 --> 00:36:58,530
Так что я должен сделать некоторые работы в настоящее время.

774
00:36:58,530 --> 00:37:01,410
Я принимаю некоторые
вольности с моим маркером

775
00:37:01,410 --> 00:37:03,120
на просто рисунок вещей
где я хочу их,

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

777
00:37:05,320 --> 00:37:08,530
Компьютер, как мы знаем, имеет
Оперативная память, или Random Access Memory,

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

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

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

781
00:37:16,680 --> 00:37:19,540
Вы не можете просто перемещать вещи вокруг
нарисовав ее на доске

782
00:37:19,540 --> 00:37:20,750
где угодно.

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

784
00:37:24,090 --> 00:37:27,480
к сожалению, четыре является
уже в неправильном месте.

785
00:37:27,480 --> 00:37:30,410
>> Таким образом, чтобы вставить номер один
Я не могу просто сделать это здесь.

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

787
00:37:31,901 --> 00:37:35,150
Это было бы обман, и я был
Измены изобразительно в течение нескольких минут

788
00:37:35,150 --> 00:37:35,800
Вот.

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

790
00:37:40,950 --> 00:37:43,030
а затем положить один там.

791
00:37:43,030 --> 00:37:45,500
>> Это хорошо, это правильно,
что это технически возможно,

792
00:37:45,500 --> 00:37:48,410
но понимаю, что это дополнительная работа.

793
00:37:48,410 --> 00:37:50,460
Я не просто поставить номер на месте.

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

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

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

797
00:37:55,660 --> 00:37:57,120
>> Но сейчас я сделал с этим элементом.

798
00:37:57,120 --> 00:37:59,056
Теперь я хочу, чтобы захватить номер три.

799
00:37:59,056 --> 00:38:00,430
Там, где, конечно же, оно принадлежит?

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

801
00:38:01,480 --> 00:38:03,650
Я не могу обмануть больше
и просто поставить его там,

802
00:38:03,650 --> 00:38:06,770
потому что, опять же, эта память
в физических местах.

803
00:38:06,770 --> 00:38:10,900
Так что я должен скопировать четыре
и поставить три здесь.

804
00:38:10,900 --> 00:38:11,550
Не ахти какое дело.

805
00:38:11,550 --> 00:38:14,610
Это всего лишь один дополнительный шаг
again-- чувствует себя очень недорого.

806
00:38:14,610 --> 00:38:16,445
>> Но теперь я перехожу к двум.

807
00:38:16,445 --> 00:38:17,820
Два, конечно же, принадлежит здесь.

808
00:38:17,820 --> 00:38:20,990
Теперь вы начинаете видеть, как
работа может накапливаться.

809
00:38:20,990 --> 00:38:23,520
Теперь то, что я должен делать?

810
00:38:23,520 --> 00:38:28,570
Да, я должен переместить четыре,
Затем я должен скопировать три,

811
00:38:28,570 --> 00:38:31,200
и теперь я могу вставить два.

812
00:38:31,200 --> 00:38:34,460
И улов с этим
Алгоритм, достаточно интересно,

813
00:38:34,460 --> 00:38:41,050
является то, что предположим, у нас есть более экстремальный
случай, когда это, скажем, восемь, семь,

814
00:38:41,050 --> 00:38:45,150
шесть, пять, четыре, три, два, один.

815
00:38:45,150 --> 00:38:49,450
Это, во многих контекстах,
в худшем случае,

816
00:38:49,450 --> 00:38:51,570
потому что штопать вещь
буквально в обратном направлении.

817
00:38:51,570 --> 00:38:53,670
>> Это действительно не имеет
влияет на алгоритм Бен,

818
00:38:53,670 --> 00:38:55,940
потому что в отборе Бен
своего рода он собирается держать

819
00:38:55,940 --> 00:38:58,359
ходит взад и вперед по списку.

820
00:38:58,359 --> 00:39:01,150
И потому, что он всегда искал
через весь оставшийся список,

821
00:39:01,150 --> 00:39:02,858
неважно
где элементы.

822
00:39:02,858 --> 00:39:05,630
Но в этом случае с моей вставки
approach-- давайте попробуем это.

823
00:39:05,630 --> 00:39:08,616
>> Так один, два, три, четыре,
пять, шесть, семь, восемь.

824
00:39:08,616 --> 00:39:11,630
Один два три четыре,
пять, шесть, семь, восемь.

825
00:39:11,630 --> 00:39:14,320
Я собираюсь взять восемь,
и где я могу это сказать?

826
00:39:14,320 --> 00:39:17,260
Ну, в самом начале моего списка,
потому что этот новый список отсортирован.

827
00:39:17,260 --> 00:39:18,760
И я пересекаю его.

828
00:39:18,760 --> 00:39:20,551
>> Где я поставил семь?

829
00:39:20,551 --> 00:39:21,050
Слей это.

830
00:39:21,050 --> 00:39:23,174
Он должен идти туда, так
Я должен сделать некоторые копирования.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
А теперь семь идет здесь.

833
00:39:28,480 --> 00:39:29,860
Теперь я перехожу к шести.

834
00:39:29,860 --> 00:39:30,980
Теперь стало еще больше работы.

835
00:39:30,980 --> 00:39:32,570
>> Восемь должен идти здесь.

836
00:39:32,570 --> 00:39:33,920
Семь должен идти сюда.

837
00:39:33,920 --> 00:39:35,450
Теперь шесть может пойти сюда.

838
00:39:35,450 --> 00:39:37,950
Теперь я захватить пять.

839
00:39:37,950 --> 00:39:40,560
Теперь восемь должен идти
здесь, семь приходится идти сюда,

840
00:39:40,560 --> 00:39:43,650
шесть должен идти здесь, и
Теперь пять и повторите.

841
00:39:43,650 --> 00:39:46,610
И я довольно много
перемещая его постоянно.

842
00:39:46,610 --> 00:39:52,950
>> Таким образом, в конце концов, это algorithm-- мы будем
назвать его вставки sort-- на самом деле

843
00:39:52,950 --> 00:39:55,020
имеет много работы, тоже.

844
00:39:55,020 --> 00:39:56,970
Это просто разные
вид работы, чем Бен.

845
00:39:56,970 --> 00:40:00,090
Работа Бен заставил меня идти
назад и вперед все время,

846
00:40:00,090 --> 00:40:03,510
выбирая следующий наименьший
элемент снова и снова.

847
00:40:03,510 --> 00:40:06,660
Так что это было очень визуальный вид работы.

848
00:40:06,660 --> 00:40:10,600
>> Этот другой алгоритм, который по-прежнему
correct-- он получит работу done--

849
00:40:10,600 --> 00:40:12,800
просто изменяет объем работы.

850
00:40:12,800 --> 00:40:15,420
Похоже, что изначально вы
экономии, потому что вы просто

851
00:40:15,420 --> 00:40:19,190
имеем дело с каждым элементом
фронт без ходить все

852
00:40:19,190 --> 00:40:20,930
путь через список, как Бен.

853
00:40:20,930 --> 00:40:25,300
Но проблема в том, особенно в эти
сумасшедшие случаи, когда это все в обратном направлении,

854
00:40:25,300 --> 00:40:27,830
вы просто вид
откладывая тяжелую работу

855
00:40:27,830 --> 00:40:30,360
пока вы не должны исправить свои ошибки.

856
00:40:30,360 --> 00:40:33,919
>> И так, если вы можете себе это
восемь и семь и шесть и пять

857
00:40:33,919 --> 00:40:36,710
а затем четыре и три и два
перемещая их путь через список,

858
00:40:36,710 --> 00:40:39,060
мы только что изменили
тип работы, которую мы делаем.

859
00:40:39,060 --> 00:40:42,340
Вместо того, чтобы делать это на
начало моей итерации,

860
00:40:42,340 --> 00:40:45,250
Я просто делаю это на
конец каждой итерации.

861
00:40:45,250 --> 00:40:50,550
Так получается, что этот алгоритм,
тоже, как правило, называется сортировка вставкой,

862
00:40:50,550 --> 00:40:52,190
Также на порядок п квадрата.

863
00:40:52,190 --> 00:40:56,480
Это не на самом деле не лучше,
не лучше вообще.

864
00:40:56,480 --> 00:41:00,810
>> Тем не менее, есть и третий подход
Я хотел бы призвать нас к рассмотрению,

865
00:41:00,810 --> 00:41:02,970
что это.

866
00:41:02,970 --> 00:41:07,850
Итак, пусть мой список, для простоты
опять же, четыре, один, три,

867
00:41:07,850 --> 00:41:11,080
two-- всего четыре номера.

868
00:41:11,080 --> 00:41:13,300
Бен имел хорошую интуицию,
хорошая человеческая интуиция

869
00:41:13,300 --> 00:41:16,340
до того, с помощью которого мы фиксировали весь
список eventually-- вставки сортировки.

870
00:41:16,340 --> 00:41:18,020
Я уговорил нас вперед.

871
00:41:18,020 --> 00:41:22,530
Но давайте рассмотрим
Простейший способ исправить этот список.

872
00:41:22,530 --> 00:41:24,110
>> Этот список не отсортирован.

873
00:41:24,110 --> 00:41:26,130
Зачем?

874
00:41:26,130 --> 00:41:31,920
В английском языке объяснить, почему
это на самом деле не сортируется.

875
00:41:31,920 --> 00:41:33,400
Что это значит не быть отсортированы?

876
00:41:33,400 --> 00:41:34,220
>> СТУДЕНТ: Это не последовательный.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Маланом: Не последовательный.

878
00:41:34,990 --> 00:41:35,822
Дайте мне пример.

879
00:41:35,822 --> 00:41:37,180
>> СТУДЕНТ: Поместите их в порядке.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Маланом: OK.

881
00:41:37,440 --> 00:41:38,790
Дайте мне более конкретный пример.

882
00:41:38,790 --> 00:41:39,832
>> СТУДЕНТ порядке возрастания.

883
00:41:39,832 --> 00:41:41,206
DAVID Маланом: Не в порядке возрастания.

884
00:41:41,206 --> 00:41:42,100
Быть более точным.

885
00:41:42,100 --> 00:41:45,190
Я не знаю, что вы имеете в виду по возрастанию.

886
00:41:45,190 --> 00:41:47,150
Что не так?

887
00:41:47,150 --> 00:41:49,930
>> СТУДЕНТ: Самый маленький из
цифры не в первом пространстве.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Маланом: Наименьший номера модели
не в первом пространстве.

889
00:41:51,140 --> 00:41:52,120
Более конкретно.

890
00:41:52,120 --> 00:41:55,000
Я начинаю ловить на.

891
00:41:55,000 --> 00:41:59,470
Мы рассчитываем, но
что из строя здесь?

892
00:41:59,470 --> 00:42:00,707
>> СТУДЕНТ: числовая последовательность.

893
00:42:00,707 --> 00:42:02,040
DAVID Маланом: числовая последовательность.

894
00:42:02,040 --> 00:42:04,248
вид каждого человека удерживания
она here-- очень высокий уровень.

895
00:42:04,248 --> 00:42:07,450
Просто буквально сказать мне, что
не так, как пять-летней мощи.

896
00:42:07,450 --> 00:42:08,310
>> СТУДЕНТ: Плюс один.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Маланом: Что это?

898
00:42:08,750 --> 00:42:09,610
>> СТУДЕНТ: Плюс один.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Маланом: Что вы имеете в виду плюс один?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Дайте мне другой пять лет.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Что случилось, мама?

904
00:42:18,330 --> 00:42:19,940
Что случилось, папа?

905
00:42:19,940 --> 00:42:22,808
Что вы имеете в виду это не отсортирован?

906
00:42:22,808 --> 00:42:24,370
>> СТУДЕНТ: Это не место.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Маланом: Что
не в нужном месте?

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

909
00:42:26,174 --> 00:42:27,090
DAVID Маланом: Хорошо, хорошо.

910
00:42:27,090 --> 00:42:29,110
Так четыре не там, где она должна быть.

911
00:42:29,110 --> 00:42:30,590
В частности, это верно?

912
00:42:30,590 --> 00:42:33,000
Четыре и один, первый
два числа, которые я вижу.

913
00:42:33,000 --> 00:42:34,930
Это правильно?

914
00:42:34,930 --> 00:42:36,427
Нет, они не в порядке, не так ли?

915
00:42:36,427 --> 00:42:38,135
На самом деле, думаю, что сейчас
о компьютере, тоже.

916
00:42:38,135 --> 00:42:40,824
Он может смотреть только на одну, может быть,
может быть, две вещи в once--

917
00:42:40,824 --> 00:42:43,240
а на самом деле только одна вещь,
в то время, но он может по крайней мере,

918
00:42:43,240 --> 00:42:45,790
посмотреть на одну вещь, то
Следующее, что прямо рядом с ним.

919
00:42:45,790 --> 00:42:47,380
>> Так же эти в порядке?

920
00:42:47,380 --> 00:42:48,032
Конечно нет.

921
00:42:48,032 --> 00:42:48,740
Таким образом, вы знаете, что?

922
00:42:48,740 --> 00:42:51,020
Почему бы нам не взять ребенка
шаги устранить эту проблему

923
00:42:51,020 --> 00:42:53,410
вместо того, чтобы делать эти фантазии
алгоритмы, такие как Бен, где

924
00:42:53,410 --> 00:42:56,440
он вроде фиксируя его
пробегаем по списку

925
00:42:56,440 --> 00:42:59,670
вместо того, чтобы делать то, что я сделал, где
Я только отчасти установил его, как мы идем?

926
00:42:59,670 --> 00:43:03,650
Давайте просто буквально сломать
Понятие order-- числового порядка,

927
00:43:03,650 --> 00:43:06,990
назвать это все, что вы want--
в этих парных сравнений.

928
00:43:06,990 --> 00:43:07,590
>> Четыре и один.

929
00:43:07,590 --> 00:43:09,970
Является ли это правильный порядок?

930
00:43:09,970 --> 00:43:11,310
Итак, давайте исправим это.

931
00:43:11,310 --> 00:43:14,700
Один и четыре, а затем
мы просто скопировать это.

932
00:43:14,700 --> 00:43:15,560
Хорошо, хорошо.

933
00:43:15,560 --> 00:43:17,022
Я установил один и четыре.

934
00:43:17,022 --> 00:43:18,320
Три и два?

935
00:43:18,320 --> 00:43:18,820
Нет.

936
00:43:18,820 --> 00:43:21,690
Пусть мои слова совпадают мои пальцы.

937
00:43:21,690 --> 00:43:23,695
Четыре и три?

938
00:43:23,695 --> 00:43:27,930
>> Это не в порядке, так что я собираюсь
чтобы сделать один, три, четыре, два.

939
00:43:27,930 --> 00:43:28,680
Хорошо.

940
00:43:28,680 --> 00:43:32,310
Теперь четыре и два?

941
00:43:32,310 --> 00:43:33,370
Нам нужно, чтобы исправить это, тоже.

942
00:43:33,370 --> 00:43:36,700
Так один, три, два, четыре.

943
00:43:36,700 --> 00:43:39,820
Так это сортируется?

944
00:43:39,820 --> 00:43:43,170
Нет, но это ближе к отсортирован?

945
00:43:43,170 --> 00:43:48,930
>> Это, потому что мы это исправил
ошибка, мы исправили эту ошибку,

946
00:43:48,930 --> 00:43:50,370
и мы исправили эту ошибку.

947
00:43:50,370 --> 00:43:52,420
Таким образом, мы зафиксировали три ошибки, возможно.

948
00:43:52,420 --> 00:43:58,100
Тем не менее не выглядит отсортированный, но
она объективно ближе к отсортированный

949
00:43:58,100 --> 00:44:00,080
потому что мы зафиксировали некоторые из этих ошибок.

950
00:44:00,080 --> 00:44:02,047
>> Теперь то, что мне делать дальше?

951
00:44:02,047 --> 00:44:03,630
Я отчасти достиг конца списка.

952
00:44:03,630 --> 00:44:05,680
Я, казалось, закрепилась
все ошибки, но нет.

953
00:44:05,680 --> 00:44:08,510
Потому что в этом случае, некоторые номера
возможно, пузырились ближе

954
00:44:08,510 --> 00:44:10,410
на другие номера, которые
по-прежнему не в порядке.

955
00:44:10,410 --> 00:44:12,951
Так что давайте делать это снова, и я буду
просто сделать это на месте на этот раз.

956
00:44:12,951 --> 00:44:14,170
Один и три?

957
00:44:14,170 --> 00:44:14,720
Все нормально.

958
00:44:14,720 --> 00:44:16,070
Три и два?

959
00:44:16,070 --> 00:44:17,560
Конечно, нет, так что давайте изменить эту ситуацию.

960
00:44:17,560 --> 00:44:19,160
Так два, три.

961
00:44:19,160 --> 00:44:21,340
Три и четыре?

962
00:44:21,340 --> 00:44:24,370
А теперь давайте просто
особенно педантичным здесь.

963
00:44:24,370 --> 00:44:26,350
сортируется ли это?

964
00:44:26,350 --> 00:44:29,280
Вы, люди знают, что это сортируется.

965
00:44:29,280 --> 00:44:30,400
>> Я должен попробовать еще раз.

966
00:44:30,400 --> 00:44:31,900
Так что Оливия предлагает мне попробовать еще раз.

967
00:44:31,900 --> 00:44:32,530
Зачем?

968
00:44:32,530 --> 00:44:35,810
Поскольку компьютер не имеет
роскошь наших человеческих глаз

969
00:44:35,810 --> 00:44:38,080
просто взглянув back-- ОК, я сделал.

970
00:44:38,080 --> 00:44:41,610
Как компьютер определяет
что список теперь отсортирован?

971
00:44:41,610 --> 00:44:44,590
Механически.

972
00:44:44,590 --> 00:44:47,650
>> Я должен пройти через
еще раз, и только тогда, когда я

973
00:44:47,650 --> 00:44:51,190
не делают / найти какие-либо ошибки, я могу
затем сделать вывод, как компьютер, да,

974
00:44:51,190 --> 00:44:51,980
мы хорошо идти.

975
00:44:51,980 --> 00:44:54,850
Так один и два, два и
три, три и четыре.

976
00:44:54,850 --> 00:44:58,030
Теперь я могу окончательно сказать, что это
сортируют, потому что я не сделал никаких изменений.

977
00:44:58,030 --> 00:45:01,940
Теперь это будет ошибка и просто
глупо, если я, компьютер,

978
00:45:01,940 --> 00:45:05,640
снова спросил те же вопросы
ожидая разные ответы.

979
00:45:05,640 --> 00:45:07,110
Не должно произойти.

980
00:45:07,110 --> 00:45:08,600
>> И вот теперь список отсортирован.

981
00:45:08,600 --> 00:45:12,630
К сожалению, бег времени
этот алгоритм также N в квадрате.

982
00:45:12,630 --> 00:45:13,130
Зачем?

983
00:45:13,130 --> 00:45:19,520
Поскольку у вас есть п числа, а в
худшем случае вы должны двигаться п чисел

984
00:45:19,520 --> 00:45:23,637
п раз, потому что вы должны продолжать идти
назад, чтобы проверить и исправить потенциально

985
00:45:23,637 --> 00:45:24,220
эти цифры.

986
00:45:24,220 --> 00:45:26,280
И мы можем сделать более
формальный анализ тоже.

987
00:45:26,280 --> 00:45:29,530
>> Так что это все, чтобы сказать, что мы сделали
три различных подхода, один

988
00:45:29,530 --> 00:45:32,210
из них сразу же интуитивно
от летучей мыши от Ben

989
00:45:32,210 --> 00:45:35,170
к моему предлагаемого включения
сортировать к этому

990
00:45:35,170 --> 00:45:38,540
где вы вроде упускать из виду
лес за деревьями на начальном этапе.

991
00:45:38,540 --> 00:45:41,760
Но тогда, если вы сделать шаг назад,
вуаля, мы исправили сортировочный понятие.

992
00:45:41,760 --> 00:45:43,824
Так что это, осмелюсь сказать,
более низкий уровень, возможно,

993
00:45:43,824 --> 00:45:45,740
чем некоторые из тех других
алгоритмы, но давайте

994
00:45:45,740 --> 00:45:48,550
увидеть, если мы не можем представить себе
они через это.

995
00:45:48,550 --> 00:45:51,450
>> Так что это какой-то хороший
программное обеспечение, которое кто-то

996
00:45:51,450 --> 00:45:56,110
написал, используя красочные бары, что это
собирается сделать следующее для нас.

997
00:45:56,110 --> 00:45:57,736
Каждый из этих стержней представляет собой число.

998
00:45:57,736 --> 00:46:00,026
Taller столбик, тем больше
число, меньше бар,

999
00:46:00,026 --> 00:46:00,990
тем меньше число.

1000
00:46:00,990 --> 00:46:05,880
Так что в идеале мы хотим хорошую пирамиду
где она начинается с малого и становится большой,

1001
00:46:05,880 --> 00:46:08,330
и это будет означать, что
эти бары сортируются.

1002
00:46:08,330 --> 00:46:11,200
Так что я собираюсь идти вперед и выбирать,
например, алгоритм Бен

1003
00:46:11,200 --> 00:46:13,990
first-- выбор сортировки.

1004
00:46:13,990 --> 00:46:16,220
>> И заметьте, что он делает.

1005
00:46:16,220 --> 00:46:18,670
То, как они выбрали
визуализировать этот алгоритм

1006
00:46:18,670 --> 00:46:22,090
в том, что, так же, как я был
ходить через мой список,

1007
00:46:22,090 --> 00:46:24,710
эта программа идет
через свой список номеров,

1008
00:46:24,710 --> 00:46:28,160
выделяя в розовый цвет каждого
число, которое он смотрит.

1009
00:46:28,160 --> 00:46:32,360
А что должно произойти прямо сейчас?

1010
00:46:32,360 --> 00:46:35,154
>> Наименьшее число,
Я или Бен обнаружил вдруг

1011
00:46:35,154 --> 00:46:36,820
получает перемещается в начало списка.

1012
00:46:36,820 --> 00:46:40,037
И обратите внимание, что они сделали выселить
номер, который был там,

1013
00:46:40,037 --> 00:46:41,120
и это прекрасно.

1014
00:46:41,120 --> 00:46:42,600
Я не попал в этот уровень детализации.

1015
00:46:42,600 --> 00:46:44,308
Но нам нужно поставить
что число где-то,

1016
00:46:44,308 --> 00:46:47,775
так что мы просто переместил его к
открытое место, которое было создано.

1017
00:46:47,775 --> 00:46:49,900
Так что я собираюсь ускорить этот процесс
вверх, потому что в противном случае он

1018
00:46:49,900 --> 00:46:51,871
становится очень утомительным быстро.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Анимация speed-- там мы идем.

1021
00:46:58,600 --> 00:47:01,850
Так что теперь же принцип
Я применяла, но вы

1022
00:47:01,850 --> 00:47:06,540
может начать чувствовать себя алгоритм, если вы
будет, или увидеть его немного более четко.

1023
00:47:06,540 --> 00:47:13,190
И этот алгоритм имеет эффект
выбирая следующий наименьший элемент,

1024
00:47:13,190 --> 00:47:16,422
так что вы собираетесь начать
он поднимется на левой стороне.

1025
00:47:16,422 --> 00:47:19,130
И на каждой итерации, как я
предложил, он делает немного меньше работы.

1026
00:47:19,130 --> 00:47:21,921
Он не должен пройти весь путь
обратно к левому концу списка,

1027
00:47:21,921 --> 00:47:23,900
потому что это уже
знает тех, сортируются.

1028
00:47:23,900 --> 00:47:28,129
Так что это своего рода чувствует, как это
ускорения, хотя каждый шаг

1029
00:47:28,129 --> 00:47:29,420
принимая такое же количество времени.

1030
00:47:29,420 --> 00:47:31,600
Там в оставшиеся всего меньше шагов.

1031
00:47:31,600 --> 00:47:35,240
И теперь вы можете отчасти чувствую
Алгоритм очистки в конце его,

1032
00:47:35,240 --> 00:47:37,040
и в самом деле теперь это сортируется.

1033
00:47:37,040 --> 00:47:41,620
>> Таким образом, сортировка вставкой все это делается.

1034
00:47:41,620 --> 00:47:43,600
Мне нужно повторно рандомизации массив.

1035
00:47:43,600 --> 00:47:45,940
И заметьте, я могу просто
держать его рандомизации,

1036
00:47:45,940 --> 00:47:50,630
и мы получим приближение
тот же подход, сортировка вставкой.

1037
00:47:50,630 --> 00:47:55,050
Позвольте мне замедлить его сюда.

1038
00:47:55,050 --> 00:47:56,915
Давайте начнем, что более.

1039
00:47:56,915 --> 00:47:57,414
Стоп.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Давайте пропустить четыре.

1042
00:48:02,410 --> 00:48:03,200
Там мы идем.

1043
00:48:03,200 --> 00:48:04,190
Перемешайте их массив.

1044
00:48:04,190 --> 00:48:05,555
И здесь мы go-- вставки рода.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Играть.

1047
00:48:12,800 --> 00:48:17,280
Обратите внимание на то, что он имеет дело с каждым
элемент он встречает сразу же,

1048
00:48:17,280 --> 00:48:20,282
но если она принадлежит
неправильное место уведомление

1049
00:48:20,282 --> 00:48:21,740
все работы, что должно произойти.

1050
00:48:21,740 --> 00:48:24,700
Мы должны продолжать переход более
и более элементов, чтобы освободить место

1051
00:48:24,700 --> 00:48:27,340
для того, что мы хотим, чтобы поставить на место.

1052
00:48:27,340 --> 00:48:30,740
>> Таким образом, мы сосредотачиваемся на
левый конец только список.

1053
00:48:30,740 --> 00:48:34,460
Заметьте, что мы даже не смотрели at-- мы
не выделены розовым цветом что-нибудь

1054
00:48:34,460 --> 00:48:35,610
направо.

1055
00:48:35,610 --> 00:48:38,180
Мы просто имеем дело с
проблемы, как мы идем,

1056
00:48:38,180 --> 00:48:40,430
но мы создаем много
работать для себя до сих пор.

1057
00:48:40,430 --> 00:48:44,410
И поэтому, если мы ускорить этот процесс
Теперь, чтобы перейти к завершению,

1058
00:48:44,410 --> 00:48:46,210
она имеет другое чувство к нему на самом деле.

1059
00:48:46,210 --> 00:48:50,150
Это просто сосредоточиться на левом конце, но
делать немного больше работы, как needed--

1060
00:48:50,150 --> 00:48:53,230
вид сглаживающих вещей
более, фиксируя вещи,

1061
00:48:53,230 --> 00:48:58,350
но дело в конечном счете, с
каждый элемент по одному за раз

1062
00:48:58,350 --> 00:49:07,740
пока мы не получим хорошо the--, мы
все знают, как это собирается закончиться,

1063
00:49:07,740 --> 00:49:09,700
так что это немного сокрушающей возможно.

1064
00:49:09,700 --> 00:49:12,830
>> Но список в end--
spoiler-- собирается быть отсортированы.

1065
00:49:12,830 --> 00:49:15,300
Итак, давайте рассмотрим один последний.

1066
00:49:15,300 --> 00:49:16,840
Мы не можем просто пропустить этот.

1067
00:49:16,840 --> 00:49:18,000
Мы почти там.

1068
00:49:18,000 --> 00:49:19,980
Два идти, один идти.

1069
00:49:19,980 --> 00:49:22,680
И вуаля.

1070
00:49:22,680 --> 00:49:23,450
Отлично.

1071
00:49:23,450 --> 00:49:27,220
>> Так что теперь давайте сделаем одну последнюю,
повторно рандомизации с пузырьковой сортировки.

1072
00:49:27,220 --> 00:49:31,690
И заметьте здесь, особенно если я замедлить его
вниз, это держать парящий до конца.

1073
00:49:31,690 --> 00:49:36,830
Но обратите внимание, это только делает парно
comparisons-- рода локальных решений.

1074
00:49:36,830 --> 00:49:39,050
Но как только мы получаем
конец списка в розовый,

1075
00:49:39,050 --> 00:49:40,690
что придется случиться снова?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Да, это придется
начать все сначала, потому что это только

1078
00:49:46,830 --> 00:49:49,870
Неподвижные попарные ошибки.

1079
00:49:49,870 --> 00:49:53,120
И это, возможно, выявили еще другие.

1080
00:49:53,120 --> 00:49:58,950
И поэтому, если вы ускорить этот процесс, вы будете
видим, что, подобно тому как следует из названия,

1081
00:49:58,950 --> 00:50:01,870
тем меньше elements-- или, вернее,
большие elements-- начинают

1082
00:50:01,870 --> 00:50:03,740
пузыриться до самого верха, если вы будете.

1083
00:50:03,740 --> 00:50:07,380
А более мелкие элементы
начиная пузыриться вниз влево.

1084
00:50:07,380 --> 00:50:10,780
И в самом деле, это своего рода
визуальный эффект, а также.

1085
00:50:10,780 --> 00:50:17,150
И таким образом это будет в конечном итоге отделка
в очень похожим образом, тоже.

1086
00:50:17,150 --> 00:50:19,160
>> Мы не должны останавливаться
по этому конкретному одному.

1087
00:50:19,160 --> 00:50:21,010
Позвольте мне открыть это сейчас, тоже.

1088
00:50:21,010 --> 00:50:24,040
Там в несколько других алгоритмов сортировки
в мире, некоторые из которых

1089
00:50:24,040 --> 00:50:25,580
захватываются здесь.

1090
00:50:25,580 --> 00:50:29,960
И специально для учащихся, которые не являются
обязательно визуальное или математическое,

1091
00:50:29,960 --> 00:50:31,930
как мы делали раньше, мы можем
также сделать это audially

1092
00:50:31,930 --> 00:50:34,210
если ассоциировать звук с этим.

1093
00:50:34,210 --> 00:50:36,990
И просто для удовольствия, вот
несколько различных алгоритмов,

1094
00:50:36,990 --> 00:50:40,950
и один из них, в частности, вы
заметит, называется "сортировка слиянием."

1095
00:50:40,950 --> 00:50:43,250
>> Это на самом деле принципиально
лучше алгоритм,

1096
00:50:43,250 --> 00:50:45,860
таким образом, что сортировка слиянием, один из
те, с которыми вы хотите видеть,

1097
00:50:45,860 --> 00:50:49,170
не порядок п в квадрате.

1098
00:50:49,170 --> 00:50:57,280
Это о порядке п раз Логарифм
N, которая на самом деле меньше, и, таким образом,

1099
00:50:57,280 --> 00:50:58,940
быстрее, чем остальные три.

1100
00:50:58,940 --> 00:51:00,670
И есть пара другой
глупые те, что мы будем видеть.

1101
00:51:00,670 --> 00:51:01,933
>> Так что здесь мы идем с некоторым звуком.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Это сортировка вставкой, так что опять
это просто дело с элементами

1104
00:51:10,490 --> 00:51:13,420
как они приходят.

1105
00:51:13,420 --> 00:51:17,180
Это своего рода пузырь, так что
считая их пары одновременно.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
И опять же, самые большие элементы
прорывается до самого верха.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Далее выбор сортировки.

1110
00:51:41,710 --> 00:51:45,420
Это алгоритм Бен, где
снова он итеративно выбора

1111
00:51:45,420 --> 00:51:46,843
следующий наименьший элемент.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
И опять же, теперь вы можете действительно услышать, что
это ускорение, но только в той степени,

1114
00:51:53,900 --> 00:51:58,230
как это делает все меньше и меньше
работать на каждой итерации.

1115
00:51:58,230 --> 00:52:04,170
Это более быстрое, сортировка слиянием,
который сортирует кластеры чисел

1116
00:52:04,170 --> 00:52:05,971
вместе, а затем объединяя их.

1117
00:52:05,971 --> 00:52:07,720
Так look-- левый
половина уже отсортированы.

1118
00:52:07,720 --> 00:52:14,165
>> Теперь это сортировка правую половину, и
Теперь он собирается объединить их в одно целое.

1119
00:52:14,165 --> 00:52:19,160
Это то, что называется "Гном рода."

1120
00:52:19,160 --> 00:52:23,460
И вы можете отчасти видеть, что
он ходит взад и вперед,

1121
00:52:23,460 --> 00:52:27,950
фиксируя работу немного здесь и
там, прежде чем он приступает к новой работе.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Вот и все.

1124
00:52:33,692 --> 00:52:36,400
Там в другой вид, который
действительно только для академических целей,

1125
00:52:36,400 --> 00:52:40,980
называется "глупым рода", который принимает
Ваши данные, сортирует его в случайном порядке,

1126
00:52:40,980 --> 00:52:43,350
а затем проверяет, является ли она сортируется.

1127
00:52:43,350 --> 00:52:47,880
И если это не так, то вновь сортирует его
случайным образом, проверяет, является ли она сортируется,

1128
00:52:47,880 --> 00:52:49,440
и если не повторяется.

1129
00:52:49,440 --> 00:52:52,660
И в теории, вероятностно
это будет завершено,

1130
00:52:52,660 --> 00:52:54,140
но после того, как совсем немного времени.

1131
00:52:54,140 --> 00:52:56,930
Это не самый
эффективность алгоритмов.

1132
00:52:56,930 --> 00:53:02,550
Так что любые вопросы о тех,
конкретные алгоритмы или что-нибудь

1133
00:53:02,550 --> 00:53:04,720
связанных там тоже?

1134
00:53:04,720 --> 00:53:09,430
>> Что ж, давайте теперь дразнят друг от друга, что все
эти линии, которые я рисую

1135
00:53:09,430 --> 00:53:15,090
и то, что я предполагаю, что компьютер
может сделать под капотом.

1136
00:53:15,090 --> 00:53:18,650
Я считаю, что все эти цифры
Я держу drawing-- они должны получить

1137
00:53:18,650 --> 00:53:21,330
хранится где-то в памяти.

1138
00:53:21,330 --> 00:53:24,130
Мы избавиться от этого парня сейчас тоже.

1139
00:53:24,130 --> 00:53:30,110
>> Таким образом, часть памяти в
computer-- так RAM памяти составляет

1140
00:53:30,110 --> 00:53:35,480
то, что мы искали вчера, двойной
встроенная память module-- выглядит следующим образом.

1141
00:53:35,480 --> 00:53:39,370
И каждый из этих маленьких черных фишек
некоторое количество байтов, как правило.

1142
00:53:39,370 --> 00:53:44,380
А потом золотые булавки подобны
провода, которые подключаются к компьютеру,

1143
00:53:44,380 --> 00:53:47,521
и зеленая доска кремния просто
что держит все вместе.

1144
00:53:47,521 --> 00:53:48,770
Так что же это на самом деле означает?

1145
00:53:48,770 --> 00:53:53,180
Если я как бы сделать такой же картину,
давайте предположим для простоты

1146
00:53:53,180 --> 00:53:55,280
что этот модуль DIMM, двойной
встроенный модуль памяти,

1147
00:53:55,280 --> 00:54:00,530
один гигабайт оперативной памяти, один гигабайт
память, которая, сколько всего байт?

1148
00:54:00,530 --> 00:54:02,100
Один гигабайт это сколько байт?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Больше чем это.

1151
00:54:06,030 --> 00:54:09,960
1124 является килограмм, 1000.

1152
00:54:09,960 --> 00:54:11,730
Мега млн.

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

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

1155
00:54:15,070 --> 00:54:16,670
Можем ли мы даже читать этикетку?

1156
00:54:16,670 --> 00:54:19,920
Это на самом деле 128
гигабайты, так что это больше.

1157
00:54:19,920 --> 00:54:22,130
Но мы будем делать вид, это
это только один гигабайт.

1158
00:54:22,130 --> 00:54:25,640
Так что означает, что есть миллиард
байт памяти, доступной для меня

1159
00:54:25,640 --> 00:54:29,770
или 8 миллиардов бит, но мы собираемся
говорить в терминах байтов в настоящее время,

1160
00:54:29,770 --> 00:54:30,750
Движение вперед.

1161
00:54:30,750 --> 00:54:36,330
>> Так что это значит, это
один байт, это еще один байт,

1162
00:54:36,330 --> 00:54:38,680
это еще один байт,
и если мы действительно хотели

1163
00:54:38,680 --> 00:54:43,280
чтобы быть конкретным, мы бы
привлечь миллиард маленьких квадратов.

1164
00:54:43,280 --> 00:54:44,320
Но что это значит?

1165
00:54:44,320 --> 00:54:46,420
Что ж, позвольте мне просто увеличить
в этой фотографии.

1166
00:54:46,420 --> 00:54:50,900
Если у меня есть что-то, что выглядит
как это сейчас, это четыре байта.

1167
00:54:50,900 --> 00:54:53,710
>> И таким образом я мог бы поставить четыре числа здесь.

1168
00:54:53,710 --> 00:54:54,990
Один два три четыре.

1169
00:54:54,990 --> 00:55:00,170
Или я мог бы поставить четыре буквы или символы.

1170
00:55:00,170 --> 00:55:02,620
"Привет!" может пойти прямо там,
потому что каждая из букв,

1171
00:55:02,620 --> 00:55:04,370
мы обсуждали ранее,
может быть представлена

1172
00:55:04,370 --> 00:55:06,650
с восемью битами или ASCII или байт.

1173
00:55:06,650 --> 00:55:09,370
Итак, другими словами, вы можете
поставил 8 миллиардов вещи внутри

1174
00:55:09,370 --> 00:55:11,137
этой одной палки памяти.

1175
00:55:11,137 --> 00:55:14,345
Теперь то, что это значит, чтобы положить вещи обратно
чтобы спина к спине в памяти, как это?

1176
00:55:14,345 --> 00:55:17,330
Это то, что программист
могли бы назвать "массив".

1177
00:55:17,330 --> 00:55:21,250
В компьютерной программе, вы не думаете,
об основных аппаратных средств, само по себе.

1178
00:55:21,250 --> 00:55:24,427
Вы просто думаете о себе как имеющие
доступ к общей сложности в миллиард байтов,

1179
00:55:24,427 --> 00:55:26,010
и вы можете все, что вы хотите с ним.

1180
00:55:26,010 --> 00:55:27,880
Но для удобства
это вообще полезно

1181
00:55:27,880 --> 00:55:31,202
чтобы сохранить свое право памяти
рядом друг с другом, как это.

1182
00:55:31,202 --> 00:55:33,660
Так что если я увеличить на this--
потому что мы, конечно, не собирается

1183
00:55:33,660 --> 00:55:39,310
привлечь миллиард маленьких squares--
давайте предположим, что эта плата представляет

1184
00:55:39,310 --> 00:55:40,610
что палка памяти в настоящее время.

1185
00:55:40,610 --> 00:55:43,800
И я просто сделать так много, как мой
Маркер заканчивается тем, что дал мне здесь.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Так что теперь у нас есть палка
памяти на борту

1188
00:55:52,300 --> 00:55:56,400
что есть один, два, три, четыре, пять,
шесть, один, два, три, четыре, пять, шесть,

1189
00:55:56,400 --> 00:56:01,130
seven-- около того 42 байта
Память на общей экрана.

1190
00:56:01,130 --> 00:56:01,630
Спасибо.

1191
00:56:01,630 --> 00:56:02,838
Да, сделал мой арифметика правильно.

1192
00:56:02,838 --> 00:56:05,120
Так 42 байт памяти здесь.

1193
00:56:05,120 --> 00:56:06,660
Так что же это на самом деле означает?

1194
00:56:06,660 --> 00:56:09,830
Ну, компьютерный программист
будет на самом деле, как правило

1195
00:56:09,830 --> 00:56:12,450
думать об этой памяти как адресно.

1196
00:56:12,450 --> 00:56:16,630
Другими словами, каждый из них
места в памяти, в аппаратных средствах,

1197
00:56:16,630 --> 00:56:18,030
имеет уникальный адрес.

1198
00:56:18,030 --> 00:56:22,020
>> Это не так сложно, как один Brattle
Площадь, Кембридж, штат Массачусетс., 02138.

1199
00:56:22,020 --> 00:56:23,830
Вместо этого, это просто число.

1200
00:56:23,830 --> 00:56:27,930
Это байт с номером ноль, это
Во-первых, это два, это три,

1201
00:56:27,930 --> 00:56:30,327
и это 41.

1202
00:56:30,327 --> 00:56:30,910
Подожди минуту.

1203
00:56:30,910 --> 00:56:32,510
Я думал, что я сказал, 42 минуту назад.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Я начал отсчет с нуля,
так что это на самом деле правильно.

1206
00:56:37,772 --> 00:56:40,980
Теперь мы не должны фактически сделать его
в виде сетки, и если вы рисуете его в виде сетки

1207
00:56:40,980 --> 00:56:43,520
Я думаю, что вещи на самом деле
получить немного вводит в заблуждение.

1208
00:56:43,520 --> 00:56:46,650
Какой программист,
в своем собственном уме,

1209
00:56:46,650 --> 00:56:50,310
как правило, думают об этом
памяти, как это так же, как ленты,

1210
00:56:50,310 --> 00:56:53,340
как кусок липкой лентой
что просто идет дальше и дальше навсегда

1211
00:56:53,340 --> 00:56:54,980
или пока не кончатся памяти.

1212
00:56:54,980 --> 00:56:59,200
Таким образом, более распространенным способом привлечь
и думать только о памяти

1213
00:56:59,200 --> 00:57:03,710
было бы, что это байта ноль, один,
два, три, а затем точка, точка, точка.

1214
00:57:03,710 --> 00:57:07,650
И у вас есть всего 42 таких байтов, даже
хотя физически он может на самом деле

1215
00:57:07,650 --> 00:57:09,480
быть чем-то больше, как это.

1216
00:57:09,480 --> 00:57:12,850
>> Так что если вы сейчас думаете о вашей
памяти, так как это, так же, как ленты,

1217
00:57:12,850 --> 00:57:17,640
это то, что программист снова
назвали бы массив памяти.

1218
00:57:17,640 --> 00:57:20,660
И когда вы действительно хотите сохранить
что-то в памяти компьютера,

1219
00:57:20,660 --> 00:57:23,290
Вы вообще делаете хранения вещей
спина к спине спина к спине.

1220
00:57:23,290 --> 00:57:25,010
Таким образом, мы говорим о цифрах.

1221
00:57:25,010 --> 00:57:30,880
И когда я хотел, чтобы решить проблемы
как четыре, один, три, два,

1222
00:57:30,880 --> 00:57:33,820
хотя я был просто рисунок
только цифры четыре, один, три,

1223
00:57:33,820 --> 00:57:39,490
два на борту, компьютер
действительно эту установку в памяти.

1224
00:57:39,490 --> 00:57:43,347
>> А что было бы рядом с
два в памяти компьютера?

1225
00:57:43,347 --> 00:57:44,680
Ну, нет никакого ответа на это.

1226
00:57:44,680 --> 00:57:45,770
Мы действительно не знаем.

1227
00:57:45,770 --> 00:57:48,200
И до тех пор пока
компьютер не нужен,

1228
00:57:48,200 --> 00:57:51,440
он не должен заботиться, что будет дальше
к числам это действительно заботится о.

1229
00:57:51,440 --> 00:57:55,130
И когда я уже говорил ранее, что компьютер
можно смотреть только по одному адресу в то время,

1230
00:57:55,130 --> 00:57:56,170
это своего рода почему.

1231
00:57:56,170 --> 00:57:59,490
>> Не в отличие от записи
плеер и считывающая головка

1232
00:57:59,490 --> 00:58:03,030
только будучи в состоянии смотреть на определенный
канавка в физической записи старой школы

1233
00:58:03,030 --> 00:58:06,500
в то время, аналогичным образом
может компьютер благодаря

1234
00:58:06,500 --> 00:58:09,810
ее центрального процессора и его
комплект Intel инструкция,

1235
00:58:09,810 --> 00:58:12,480
среди которых инструкции
считывается из памяти

1236
00:58:12,480 --> 00:58:15,590
или сохранить memory--
компьютер может только смотреть

1237
00:58:15,590 --> 00:58:19,210
в одном месте при time--
иногда их сочетание,

1238
00:58:19,210 --> 00:58:21,770
но на самом деле только в одном месте в то время.

1239
00:58:21,770 --> 00:58:24,770
Поэтому, когда мы делаем
эти различные алгоритмы,

1240
00:58:24,770 --> 00:58:28,110
Я не просто писать в
vacuum-- четыре, один, три, два.

1241
00:58:28,110 --> 00:58:30,849
Эти цифры на самом деле принадлежат
где-то физической памяти.

1242
00:58:30,849 --> 00:58:32,890
Так что есть крошечное
транзисторов или какой-то

1243
00:58:32,890 --> 00:58:35,840
электроники под
капот хранения этих значений.

1244
00:58:35,840 --> 00:58:40,460
>> А в общей сложности, сколько бит
участие прямо сейчас, чтобы быть ясно?

1245
00:58:40,460 --> 00:58:45,580
Так что это четыре байта, или
теперь это всего 32 бита.

1246
00:58:45,580 --> 00:58:49,280
Так что есть на самом деле 32 нулей и
те составляющие эти четыре вещи.

1247
00:58:49,280 --> 00:58:52,070
Там даже больше здесь, но
снова мы не заботимся об этом.

1248
00:58:52,070 --> 00:58:55,120
>> Так что теперь давайте зададим другой
Вопрос использования памяти,

1249
00:58:55,120 --> 00:58:57,519
потому что это в конце
дня в дисперсии.

1250
00:58:57,519 --> 00:59:00,310
Независимо от того, что мы могли бы сделать с
компьютер, в конце дня

1251
00:59:00,310 --> 00:59:02,560
аппаратные средства по-прежнему
то же самое под капотом.

1252
00:59:02,560 --> 00:59:04,670
Как бы я хранить слово здесь?

1253
00:59:04,670 --> 00:59:09,710
Ну, слово в компьютере, как
"Привет!" будет храниться так же, как это.

1254
00:59:09,710 --> 00:59:12,300
И если вы хотели больше
слово, вы можете просто

1255
00:59:12,300 --> 00:59:19,120
перезаписать, что и сказать что-то
как "привет" и магазин, который здесь.

1256
00:59:19,120 --> 00:59:23,930
>> И вот здесь тоже, это contiguousness
на самом деле является преимуществом,

1257
00:59:23,930 --> 00:59:26,530
потому что компьютер может просто
читать справа налево.

1258
00:59:26,530 --> 00:59:28,680
Но вот вопрос.

1259
00:59:28,680 --> 00:59:33,480
В контексте этого слова,
ч-е-л-л-о, восклицательного знака,

1260
00:59:33,480 --> 00:59:38,740
как, возможно, компьютер знает, где
слово начинается и где кончается слово?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
В контексте чисел,
как делает компьютер

1263
00:59:43,800 --> 00:59:48,396
знаю, как долго последовательность
номера или где она начинается?

1264
00:59:48,396 --> 00:59:50,270
Что ж, оказывается out--
и мы не будем слишком много

1265
00:59:50,270 --> 00:59:54,970
в этот уровень detail--
компьютеры перемещать вещи вокруг в памяти

1266
00:59:54,970 --> 00:59:57,800
буквально через эти адреса.

1267
00:59:57,800 --> 01:00:02,080
Таким образом, в компьютере, если вы
написание кода для хранения вещей

1268
01:00:02,080 --> 01:00:05,800
как и слова, что вы
на самом деле делает печатает

1269
01:00:05,800 --> 01:00:11,320
Выражения, которые помнят, где в
память компьютера эти слова.

1270
01:00:11,320 --> 01:00:14,370
Итак, позвольте мне сделать очень,
очень простой пример.

1271
01:00:14,370 --> 01:00:18,260
>> Я собираюсь идти вперед и
открыть простую текстовую программу,

1272
01:00:18,260 --> 01:00:20,330
и я собираюсь создать
файл с именем hello.c.

1273
01:00:20,330 --> 01:00:22,849
Большая часть этой информации мы
Не буду вдаваться в очень подробно,

1274
01:00:22,849 --> 01:00:25,140
но я собираюсь написать
Программа в том же самом языке,

1275
01:00:25,140 --> 01:00:31,140
C. Это гораздо более пугающим,
Я бы сказал, чем нуля,

1276
01:00:31,140 --> 01:00:32,490
но это очень похоже по духу.

1277
01:00:32,490 --> 01:00:34,364
На самом деле, эти фигурная
braces-- вы можете вид

1278
01:00:34,364 --> 01:00:37,820
думаю о том, что я только что сделал, как это.

1279
01:00:37,820 --> 01:00:39,240
>> Давайте сделаем это, на самом деле.

1280
01:00:39,240 --> 01:00:45,100
Когда зеленый флаг щелкнул,
выполните следующие действия.

1281
01:00:45,100 --> 01:00:50,210
Я хочу, чтобы распечатать "привет".

1282
01:00:50,210 --> 01:00:51,500
Так что теперь это псевдокод.

1283
01:00:51,500 --> 01:00:53,000
Я отчасти размывая границы.

1284
01:00:53,000 --> 01:00:56,750
В C, этот язык я говорю
О, эта линия печати привет

1285
01:00:56,750 --> 01:01:01,940
фактически становится "Printf" с
некоторые круглые скобки и точка с запятой.

1286
01:01:01,940 --> 01:01:03,480
>> Но это точно такая же идея.

1287
01:01:03,480 --> 01:01:06,730
И это очень удобно
"Когда зеленый флаг щелкнул" становится

1288
01:01:06,730 --> 01:01:10,182
гораздо более аркан "INT главный недействительным."

1289
01:01:10,182 --> 01:01:12,890
И это на самом деле не имеет никакого отображения,
так что я буду просто игнорировать это.

1290
01:01:12,890 --> 01:01:17,210
Но фигурные скобки подобны
изогнутые части головоломки, как это.

1291
01:01:17,210 --> 01:01:18,700
>> Так что вы можете угадать вид.

1292
01:01:18,700 --> 01:01:22,357
Даже если вы никогда не программировали ранее,
что делает эта программа, вероятно, делать?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Возможно печатает привет
с восклицательным знаком.

1295
01:01:28,000 --> 01:01:29,150
>> Так давайте попробуем это.

1296
01:01:29,150 --> 01:01:30,800
Я собираюсь сохранить его.

1297
01:01:30,800 --> 01:01:34,000
И это, опять же, очень
старая школьная среда.

1298
01:01:34,000 --> 01:01:35,420
Я не могу нажать, я не могу перетащить.

1299
01:01:35,420 --> 01:01:36,910
Я должен вводить команды.

1300
01:01:36,910 --> 01:01:41,320
Поэтому я хочу, чтобы запустить свою программу, так что
Я мог бы сделать это, как hello.c.

1301
01:01:41,320 --> 01:01:42,292
Это файл я побежал.

1302
01:01:42,292 --> 01:01:43,500
Но подождите, я пропускаю шаг.

1303
01:01:43,500 --> 01:01:46,470
Что мы говорим, является необходимым
шаг для языка как C?

1304
01:01:46,470 --> 01:01:49,470
Я только что написал источник
код, но что мне нужно сделать?

1305
01:01:49,470 --> 01:01:50,670
Да, мне нужен компилятор.

1306
01:01:50,670 --> 01:01:57,670
Так что на моем Mac здесь, у меня есть
Программа под названием GCC, GNU C компилятор,

1307
01:01:57,670 --> 01:02:03,990
которая позволяет мне делать this-- поворот
мой исходный код в, мы будем называть его,

1308
01:02:03,990 --> 01:02:04,930
Машинный код.

1309
01:02:04,930 --> 01:02:10,180
>> И я вижу, что,
еще раз, как показано ниже, эти

1310
01:02:10,180 --> 01:02:14,090
являются нули и единицы я просто
созданный из моего исходного кода,

1311
01:02:14,090 --> 01:02:15,730
все нули и единицы.

1312
01:02:15,730 --> 01:02:17,770
И если я хочу работать
мой program-- это происходит

1313
01:02:17,770 --> 01:02:23,010
называться a.out для
исторические reasons-- "привет".

1314
01:02:23,010 --> 01:02:24,070
Я могу запустить его снова.

1315
01:02:24,070 --> 01:02:25,690
Привет привет привет.

1316
01:02:25,690 --> 01:02:27,430
И это, кажется, работает.

1317
01:02:27,430 --> 01:02:31,000
>> Но это означает, что где-то в моем
память компьютера слова

1318
01:02:31,000 --> 01:02:35,279
ч-е-л-л-о, восклицательным знаком.

1319
01:02:35,279 --> 01:02:38,070
И оказывается, так же, как и в сторону,
что такое компьютер, как правило,

1320
01:02:38,070 --> 01:02:40,550
сделать так, что он знает, где
вещи начинают и end-- это

1321
01:02:40,550 --> 01:02:42,460
собирается поставить специальный символ здесь.

1322
01:02:42,460 --> 01:02:46,064
И конвенция должна поставить
номер ноль в конце слова

1323
01:02:46,064 --> 01:02:48,230
так что вы знаете, где это
на самом деле заканчивается, так что вы

1324
01:02:48,230 --> 01:02:52,750
не продолжать печатать больше и больше
символов, чем вы на самом деле намерены.

1325
01:02:52,750 --> 01:02:55,400
>> Но здесь еда на дом, даже
хотя это довольно аркан,

1326
01:02:55,400 --> 01:02:58,140
является то, что это в конечном счете
относительно просто.

1327
01:02:58,140 --> 01:03:04,550
Вы получили вид ленты, заготовки
пространство, на котором можно писать письма.

1328
01:03:04,550 --> 01:03:07,150
Вы просто должны иметь
специальный символ, как угодно

1329
01:03:07,150 --> 01:03:10,316
число ноль, чтобы положить в конце
ваши слова так, что компьютер знает,

1330
01:03:10,316 --> 01:03:13,410
ой, я должен остановить печать после того, как
Я вижу восклицательный знак.

1331
01:03:13,410 --> 01:03:16,090
Потому что следующая вещь там
это значение ASCII нуля,

1332
01:03:16,090 --> 01:03:19,125
или нулевой символ, как
кто-то назовет его.

1333
01:03:19,125 --> 01:03:21,500
Но есть своего рода проблемы
здесь, и давайте вернуться

1334
01:03:21,500 --> 01:03:23,320
числам на минуту.

1335
01:03:23,320 --> 01:03:28,720
Предположим, что я, на самом деле,
есть массив чисел,

1336
01:03:28,720 --> 01:03:30,730
и предположим, что
Программа Я пишу это

1337
01:03:30,730 --> 01:03:34,680
как класс книга для учителя
и учителей классе.

1338
01:03:34,680 --> 01:03:38,720
И эта программа позволяет ему или ей
чтобы набрать баллы своих учеников

1339
01:03:38,720 --> 01:03:39,960
на викторинах.

1340
01:03:39,960 --> 01:03:43,750
И предположим, что студент получает
100 на их первой викторины, может быть,

1341
01:03:43,750 --> 01:03:49,920
как 80 на следующий, то
75, а затем 90 на четвертой викторины.

1342
01:03:49,920 --> 01:03:54,150
>> Таким образом, в этот момент в истории,
массив имеет размер четыре.

1343
01:03:54,150 --> 01:03:58,470
Там абсолютно больше памяти в
компьютер, но массив, так сказать,

1344
01:03:58,470 --> 01:04:00,350
имеет размер четыре.

1345
01:04:00,350 --> 01:04:06,060
Предположим теперь, что учитель хочет
назначить пятый тест на класс.

1346
01:04:06,060 --> 01:04:08,510
Ну, одна из вещей, которые он
или она будет иметь, чтобы сделать

1347
01:04:08,510 --> 01:04:10,650
теперь хранить дополнительную ценность здесь.

1348
01:04:10,650 --> 01:04:15,490
Но если массив учитель имеет
Созданный в этой программе имеет размер для,

1349
01:04:15,490 --> 01:04:22,440
одна из проблем с массивом является то, что
Вы не можете просто продолжать добавлять к памяти.

1350
01:04:22,440 --> 01:04:26,470
Потому что, если другая часть
Программа имеет слово "эй" прямо там?

1351
01:04:26,470 --> 01:04:29,650
>> Другими словами, память может быть
используется для чего-нибудь в программе.

1352
01:04:29,650 --> 01:04:33,250
А если заранее я напечатал, эй,
Я хочу, чтобы ввод четырех баллов викторины,

1353
01:04:33,250 --> 01:04:34,784
они могли бы пойти здесь и здесь.

1354
01:04:34,784 --> 01:04:37,700
И если вы вдруг передумаете
позже и сказать, что я хочу пятый викторины

1355
01:04:37,700 --> 01:04:40,872
счет, вы не можете просто
положить его туда, куда вы хотите,

1356
01:04:40,872 --> 01:04:42,580
потому что, если это
памяти используется

1357
01:04:42,580 --> 01:04:45,990
для чего-то else-- другую программу
или какой-либо другой особенностью программы

1358
01:04:45,990 --> 01:04:46,910
что вы работаете?

1359
01:04:46,910 --> 01:04:50,650
Таким образом, вы должны думать заранее
как вы хотите хранить ваши данные,

1360
01:04:50,650 --> 01:04:54,480
потому что теперь вы покрашены
себя в цифровой угол.

1361
01:04:54,480 --> 01:04:57,280
>> Таким образом, вместо того, чтобы учитель мог бы
говорят, при написании программы

1362
01:04:57,280 --> 01:04:59,360
хранить его или ее
классов, вы знаете, что?

1363
01:04:59,360 --> 01:05:04,180
Я буду просить,
при написании моей программы,

1364
01:05:04,180 --> 01:05:12,070
что я хочу, ноль, один, два, три,
четыре, пять, шесть, восемь классов в общей сложности.

1365
01:05:12,070 --> 01:05:15,320
Так один, два, три, четыре,
пять, шесть, семь, восемь.

1366
01:05:15,320 --> 01:05:18,612
Преподаватель может просто чрезмерно выделять
памяти при написании свою программу

1367
01:05:18,612 --> 01:05:19,570
и сказать, вы знаете, что?

1368
01:05:19,570 --> 01:05:22,236
Я никогда не буду назначать более
чем через восемь викторин в течение семестра.

1369
01:05:22,236 --> 01:05:23,130
Это просто безумие.

1370
01:05:23,130 --> 01:05:24,470
Я никогда не буду выделять это.

1371
01:05:24,470 --> 01:05:28,270
Так что таким образом он или она имеет
гибкость для хранения студенческих баллов,

1372
01:05:28,270 --> 01:05:33,010
как 75, 90, и, возможно, один дополнительный, где
студент получил дополнительный кредит, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Но если учитель никогда
использует эти три пространства,

1374
01:05:36,130 --> 01:05:38,860
есть интуитивное навынос здесь.

1375
01:05:38,860 --> 01:05:41,410
Он или она просто тратить пространство.

1376
01:05:41,410 --> 01:05:44,790
Итак, другими словами, есть этот
общий компромисс в программировании

1377
01:05:44,790 --> 01:05:48,241
где вы можете либо выделить
ровно столько памяти, сколько вы хотите,

1378
01:05:48,241 --> 01:05:51,490
потенциал роста которого является то, что ты супер
efficient-- вы не быть расточительным

1379
01:05:51,490 --> 01:05:54,640
на all-- но нижняя сторона которого
является то, что если вы измените свое мнение, когда

1380
01:05:54,640 --> 01:05:58,780
с помощью программы, которую вы хотите сохранить
больше данных, чем первоначально предполагалось.

1381
01:05:58,780 --> 01:06:03,030
>> Поэтому, возможно, это решение, то,
писать свои программы таким образом,

1382
01:06:03,030 --> 01:06:05,605
что они используют больше памяти
чем они на самом деле нужно.

1383
01:06:05,605 --> 01:06:07,730
Таким образом, вы не собираетесь
нарваться на эту проблему,

1384
01:06:07,730 --> 01:06:09,730
но вы быть расточительным.

1385
01:06:09,730 --> 01:06:12,960
И чем больше памяти ваша программа использует,
как мы обсуждали вчера, тем меньше

1386
01:06:12,960 --> 01:06:15,410
память, которая доступна
для других программ,

1387
01:06:15,410 --> 01:06:18,790
тем быстрее ваш компьютер может замедлить
вниз из-за виртуальной памяти.

1388
01:06:18,790 --> 01:06:22,670
И поэтому идеальным решением может быть то, что?

1389
01:06:22,670 --> 01:06:24,610
>> Под-выделяющих кажется плохим.

1390
01:06:24,610 --> 01:06:27,030
Чрезмерная кажется плохо Выделение.

1391
01:06:27,030 --> 01:06:31,120
Так что может быть лучшим решением?

1392
01:06:31,120 --> 01:06:32,390
Перераспределение.

1393
01:06:32,390 --> 01:06:33,590
Будьте более динамичным.

1394
01:06:33,590 --> 01:06:37,520
Не заставлять себя выбрать
априори, в самом начале, что вы хотите.

1395
01:06:37,520 --> 01:06:41,370
И, конечно, не чрезмерно выделять,
чтобы не быть расточительным.

1396
01:06:41,370 --> 01:06:45,770
>> И так, чтобы достичь этой цели, мы
нужно бросить эту структуру данных,

1397
01:06:45,770 --> 01:06:48,100
так сказать, прочь.

1398
01:06:48,100 --> 01:06:51,080
И так, что программист
как правило, используют

1399
01:06:51,080 --> 01:06:55,940
что-то не называется
массив, но связанный список.

1400
01:06:55,940 --> 01:07:00,860
Другими словами, он или она будет
начинают думать о своей памяти

1401
01:07:00,860 --> 01:07:05,280
как являющийся своего рода форму, что они
можно сделать следующим образом.

1402
01:07:05,280 --> 01:07:08,520
Если я хочу, чтобы сохранить номер в
program-- поэтому сентября

1403
01:07:08,520 --> 01:07:12,600
Я дал моим студентам викторины; я хочу
для хранения первой викторины студентов,

1404
01:07:12,600 --> 01:07:16,220
и они получили 100 на it-- I
задам мой компьютер,

1405
01:07:16,220 --> 01:07:19,540
путем программы я
написано, для одного куска памяти.

1406
01:07:19,540 --> 01:07:22,570
И я буду хранить
номер 100 в нем, и это все.

1407
01:07:22,570 --> 01:07:24,820
>> Затем несколько недель спустя
когда я получу свой второй викторины,

1408
01:07:24,820 --> 01:07:27,890
и настало время, чтобы набрать
в том, что 90%, я собираюсь

1409
01:07:27,890 --> 01:07:32,129
чтобы спросить компьютер, эй, компьютер,
может у меня есть еще один кусок памяти?

1410
01:07:32,129 --> 01:07:34,170
Это собирается дать мне это
пустой кусок памяти.

1411
01:07:34,170 --> 01:07:39,370
Я собираюсь поставить в число 90,
но в моей программе как-то или other--

1412
01:07:39,370 --> 01:07:42,100
и мы не будем беспокоиться о
Синтаксис this-- мне нужно

1413
01:07:42,100 --> 01:07:44,430
как-то цепь эти вещи вместе.

1414
01:07:44,430 --> 01:07:47,430
И я приковать их вместе с
что выглядит как стрела здесь.

1415
01:07:47,430 --> 01:07:50,050
>> Третий тест, который приходит,
Я собираюсь сказать, эй, компьютер,

1416
01:07:50,050 --> 01:07:51,680
дайте мне еще один кусок памяти.

1417
01:07:51,680 --> 01:07:54,660
И я собираюсь положить вниз
Как бы то ни было, как 75,

1418
01:07:54,660 --> 01:07:56,920
и я должен цепи этой
вместе сейчас как-то.

1419
01:07:56,920 --> 01:08:00,290
Четвертый викторины приходит вместе, и, возможно,
что это ближе к концу семестра.

1420
01:08:00,290 --> 01:08:03,140
И к тому моменту моя программа
может быть с использованием памяти

1421
01:08:03,140 --> 01:08:05,540
повсюду, во всем физически.

1422
01:08:05,540 --> 01:08:08,170
И вот как раз для пинков, я
собирается сделать это вперед

1423
01:08:08,170 --> 01:08:11,260
quiz-- я забыл, что это было; я
думаю, может быть, 80 или something--

1424
01:08:11,260 --> 01:08:12,500
путь здесь.

1425
01:08:12,500 --> 01:08:15,920
>> Но это нормально, потому что изобразительно
Я собираюсь нарисовать эту линию.

1426
01:08:15,920 --> 01:08:19,063
Другими словами, в действительности,
в аппаратном обеспечении вашего компьютера,

1427
01:08:19,063 --> 01:08:20,979
первый счет может
в конечном итоге здесь, потому что это

1428
01:08:20,979 --> 01:08:22,529
прямо в начале семестра.

1429
01:08:22,529 --> 01:08:25,810
Следующим может в конечном итоге здесь
потому что немного времени прошло

1430
01:08:25,810 --> 01:08:27,210
и программа продолжает работать.

1431
01:08:27,210 --> 01:08:30,060
Следующий показатель, который был
75, может быть здесь.

1432
01:08:30,060 --> 01:08:33,420
И последняя оценка может быть
80, который находится здесь.

1433
01:08:33,420 --> 01:08:38,729
>> Таким образом, в действительности, физически, это может быть
какая память компьютера выглядит следующим образом.

1434
01:08:38,729 --> 01:08:41,569
Но это не является полезным психического
парадигма для программиста.

1435
01:08:41,569 --> 01:08:44,649
Почему вы должны заботиться, где
щеколда ваши данные в конечном итоге?

1436
01:08:44,649 --> 01:08:46,200
Вы просто хотите сохранить данные.

1437
01:08:46,200 --> 01:08:49,390
>> Это вроде как нашей дискуссии
ранее рисования куба.

1438
01:08:49,390 --> 01:08:52,200
Почему вы все равно, что
угол куба

1439
01:08:52,200 --> 01:08:53,740
и как нужно повернуть, чтобы привлечь его?

1440
01:08:53,740 --> 01:08:54,950
Вы просто хотите куб.

1441
01:08:54,950 --> 01:08:57,359
Точно так же здесь, вы
просто хочу, чтобы класс книги.

1442
01:08:57,359 --> 01:08:59,559
Вы просто хотите, чтобы думать о
это как список номеров.

1443
01:08:59,559 --> 01:09:01,350
Кто заботится, как это
реализованы в аппаратных средствах?

1444
01:09:01,350 --> 01:09:05,180
>> Таким образом, абстракция в настоящее время
эта картина здесь.

1445
01:09:05,180 --> 01:09:07,580
Это связано список, как и
программист назвал бы это,

1446
01:09:07,580 --> 01:09:10,640
поскольку у вас есть
список, очевидно чисел.

1447
01:09:10,640 --> 01:09:14,990
Но это связано изобразительно
посредством этих стрелок,

1448
01:09:14,990 --> 01:09:18,510
и все эти стрелки are-- под
капот, если вам интересно,

1449
01:09:18,510 --> 01:09:23,210
Напомним, что наше физическое оборудование имеет
адреса ноль, один, два, три, четыре.

1450
01:09:23,210 --> 01:09:28,465
Все эти стрелы как карта
или направления, где, если 90 is-- прямо сейчас

1451
01:09:28,465 --> 01:09:29,090
Я должен рассчитывать.

1452
01:09:29,090 --> 01:09:31,750
>> Ноль, один, два, три,
четыре, пять, шесть, семь.

1453
01:09:31,750 --> 01:09:35,640
Похоже, что 90 находится
память адрес номер семь.

1454
01:09:35,640 --> 01:09:38,460
Все эти стрелы является
как маленький клочок бумаги

1455
01:09:38,460 --> 01:09:42,439
который дает направлениях к
программа, которая говорит, что следовать этой карте

1456
01:09:42,439 --> 01:09:43,880
чтобы добраться до места семь.

1457
01:09:43,880 --> 01:09:46,680
И там вы найдете
второй студенческий викторины счет.

1458
01:09:46,680 --> 01:09:52,100
Между тем, 75-- если я буду продолжать это,
это семь, восемь, девять, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Эта другая стрелка просто представляет
карта памяти на место 15.

1461
01:09:59,080 --> 01:10:02,550
Но опять же, как правило, программист делает
не заботятся об этом уровне детализации.

1462
01:10:02,550 --> 01:10:05,530
И в большинстве каждого программирования
язык сегодня, программист

1463
01:10:05,530 --> 01:10:10,490
даже не будет знать, где в памяти
эти цифры на самом деле.

1464
01:10:10,490 --> 01:10:14,830
Все, что он или она должен заботиться о том,
что они каким-то образом связаны друг с другом

1465
01:10:14,830 --> 01:10:18,390
в структуре данных, как это.

1466
01:10:18,390 --> 01:10:21,580
>> Но оказывается, не
чтобы получить слишком технический.

1467
01:10:21,580 --> 01:10:27,430
Но только потому, что мы можем, возможно,
позволить себе иметь эту дискуссию здесь,

1468
01:10:27,430 --> 01:10:33,630
Предположим, что мы вновь
этот вопрос здесь массива.

1469
01:10:33,630 --> 01:10:35,780
Давайте посмотрим, если мы собираемся здесь сожалеют.

1470
01:10:35,780 --> 01:10:42,950
Это 100, 90, 75, и 80.

1471
01:10:42,950 --> 01:10:44,980
>> Позвольте мне кратко сделать это заявление.

1472
01:10:44,980 --> 01:10:48,980
Это массив, и снова,
характерным признаком которых массива

1473
01:10:48,980 --> 01:10:52,400
является то, что все ваши данные обратно
спина к спине в memory-- буквально

1474
01:10:52,400 --> 01:10:56,830
один байт или, может быть четыре байта,
некоторое фиксированное число байтов прочь.

1475
01:10:56,830 --> 01:11:00,710
В связанном списке, который мы могли бы сделать
как это, под капотом, который

1476
01:11:00,710 --> 01:11:02,000
знает где, что материал?

1477
01:11:02,000 --> 01:11:03,630
Он даже не нужно поступать так.

1478
01:11:03,630 --> 01:11:06,050
Некоторые данные могут быть
обратно влево там.

1479
01:11:06,050 --> 01:11:07,530
Вы даже не знаете.

1480
01:11:07,530 --> 01:11:15,430
>> И так с массивом, у вас есть
особенность известна как случайного доступа.

1481
01:11:15,430 --> 01:11:20,570
А какие средства произвольного доступа
что компьютер может прыгать мгновенно

1482
01:11:20,570 --> 01:11:22,730
в любое место в массиве.

1483
01:11:22,730 --> 01:11:23,580
Зачем?

1484
01:11:23,580 --> 01:11:26,000
Поскольку компьютер знает
что первое местоположение

1485
01:11:26,000 --> 01:11:29,540
ноль, один, два, и три.

1486
01:11:29,540 --> 01:11:33,890
>> И поэтому, если вы хотите, чтобы перейти от
этот элемент к следующему элементу,

1487
01:11:33,890 --> 01:11:36,099
вы в буквальном смысле, в
ум компьютера, просто добавьте один.

1488
01:11:36,099 --> 01:11:39,140
Если вы хотите, чтобы перейти к третьему элементу,
просто добавьте одно-- следующий элемент, просто

1489
01:11:39,140 --> 01:11:40,290
добавить один.

1490
01:11:40,290 --> 01:11:42,980
Тем не менее, в этой версии
истории, предположим,

1491
01:11:42,980 --> 01:11:46,080
компьютер в настоящее время ищет
на или имеем дело с номером 100.

1492
01:11:46,080 --> 01:11:49,770
Как вы получаете к следующему
класс в классе книги?

1493
01:11:49,770 --> 01:11:52,560
>> Вы должны принять семь
шаги, которые произвольно.

1494
01:11:52,560 --> 01:11:58,120
Для того, чтобы добраться до следующей, вы должны
принять еще восемь шагов, чтобы добраться до 15.

1495
01:11:58,120 --> 01:12:02,250
Другими словами, это не
постоянный зазор между числами,

1496
01:12:02,250 --> 01:12:04,857
и поэтому он просто берет
Компьютер больше времени точка.

1497
01:12:04,857 --> 01:12:06,940
Компьютер должен искать
через память в порядке

1498
01:12:06,940 --> 01:12:08,990
чтобы найти то, что вы ищете.

1499
01:12:08,990 --> 01:12:14,260
>> Таким образом, в то время как массив имеет тенденцию быть
быстро данные structure-- потому что вы

1500
01:12:14,260 --> 01:12:17,610
может буквально сделать простую арифметику
и попасть туда, куда вы хотите, добавив к нему один,

1501
01:12:17,610 --> 01:12:21,300
для instance-- связанный список,
вы жертвуете эту функцию.

1502
01:12:21,300 --> 01:12:24,020
Вы не можете просто идти от первой
на второй третий четвертый.

1503
01:12:24,020 --> 01:12:25,240
Вы должны следовать карте.

1504
01:12:25,240 --> 01:12:28,160
Вы должны предпринять дополнительные шаги,
чтобы добраться до тех значений, которые

1505
01:12:28,160 --> 01:12:30,230
Казалось бы, добавление стоимости.

1506
01:12:30,230 --> 01:12:35,910
Таким образом, мы платим цену, но то, что было
особенность, что Дэн искал здесь?

1507
01:12:35,910 --> 01:12:38,110
Что делает связанный список
по-видимому, позволяют нам делать,

1508
01:12:38,110 --> 01:12:40,240
который был происхождение
эта конкретная история?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> В точку.

1511
01:12:43,830 --> 01:12:46,220
Динамический размер для него.

1512
01:12:46,220 --> 01:12:48,040
Мы можем добавить к этому списку.

1513
01:12:48,040 --> 01:12:51,430
Мы можем даже сократить список, так
что мы только используя столько памяти

1514
01:12:51,430 --> 01:12:55,560
как мы на самом деле хотим и так
мы никогда не чрезмерно расПредеЛение.

1515
01:12:55,560 --> 01:12:58,470
>> Теперь просто, чтобы быть действительно NIT-разборчивы,
есть скрытые расходы.

1516
01:12:58,470 --> 01:13:01,980
Таким образом, вы не должны просто дайте мне убедить
вы, что это является убедительным компромиссом.

1517
01:13:01,980 --> 01:13:04,190
Там другая скрытая стоимость здесь.

1518
01:13:04,190 --> 01:13:06,550
Преимущество, чтобы быть ясно,
является то, что мы получаем динамичность.

1519
01:13:06,550 --> 01:13:10,359
Если я хочу еще один элемент, я могу просто
нарисовать его и поставить ряд там.

1520
01:13:10,359 --> 01:13:12,150
И тогда я могу связать его
с изображением здесь,

1521
01:13:12,150 --> 01:13:14,970
в то время как здесь, опять же, если я
окрашены себя в угол,

1522
01:13:14,970 --> 01:13:19,410
если что-то еще уже использует
память здесь, я не повезло.

1523
01:13:19,410 --> 01:13:21,700
Я нарисовал себя в угол.

1524
01:13:21,700 --> 01:13:24,390
>> Но то, что скрытый
стоит в этой картине?

1525
01:13:24,390 --> 01:13:27,690
Это не просто сумма
времени, которое требуется

1526
01:13:27,690 --> 01:13:29,870
идти отсюда здесь,
который семь шагов, а затем

1527
01:13:29,870 --> 01:13:32,820
восемь шагов, что более чем один.

1528
01:13:32,820 --> 01:13:34,830
Что еще одна скрытая стоимость?

1529
01:13:34,830 --> 01:13:35,440
Не только время.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Дополнительная информация
необходимо для достижения этой фотографии.

1532
01:13:49,940 --> 01:13:53,210
>> Да, эта карта, эти маленькие клочки
бумаги, как я продолжаю описывать их как.

1533
01:13:53,210 --> 01:13:55,650
Эти arrows-- те не являются свободными.

1534
01:13:55,650 --> 01:13:57,660
Computer-- вы знаете,
то, что компьютер имеет.

1535
01:13:57,660 --> 01:13:58,790
Он имеет нули и единицы.

1536
01:13:58,790 --> 01:14:03,170
Если вы хотите, чтобы представлять стрелу или А
карту или номер, вам нужно некоторое количество памяти.

1537
01:14:03,170 --> 01:14:05,950
Так что с другой ценой, которую вы
платить за связанного списка,

1538
01:14:05,950 --> 01:14:09,070
общая информатика
ресурс, также пространство.

1539
01:14:09,070 --> 01:14:11,710
>> И в самом деле так, так часто,
среди компромиссах

1540
01:14:11,710 --> 01:14:15,580
в разработке программной инженерии
системы время и space--

1541
01:14:15,580 --> 01:14:18,596
два из ваших ингредиентов, два
из ваших самых дорогостоящих ингредиентов.

1542
01:14:18,596 --> 01:14:21,220
Это стоило мне больше времени
потому что я должен следовать этой карте,

1543
01:14:21,220 --> 01:14:25,730
но это также стоит мне больше места
потому что я должен держать эту карту вокруг.

1544
01:14:25,730 --> 01:14:28,730
Таким образом, надежда, как мы своего рода
обсуждался в течение вчерашнего дня и сегодня,

1545
01:14:28,730 --> 01:14:31,720
в том, что выгоды
перевесят издержки.

1546
01:14:31,720 --> 01:14:33,870
>> Но нет никакого очевидного решения здесь.

1547
01:14:33,870 --> 01:14:35,870
Может быть, это better--
а-ля быстрый и грязный,

1548
01:14:35,870 --> 01:14:38,660
а Карим предложил earlier--
бросить память на проблему.

1549
01:14:38,660 --> 01:14:42,520
Просто купите больше памяти, меньше думать
трудно о решении проблемы,

1550
01:14:42,520 --> 01:14:44,595
и решить ее в более простой способ.

1551
01:14:44,595 --> 01:14:46,720
И действительно раньше, когда
мы говорили о компромиссах,

1552
01:14:46,720 --> 01:14:49,190
оно не было места в
компьютер и время.

1553
01:14:49,190 --> 01:14:51,810
Это было время, разработчик, который
это еще один ресурс.

1554
01:14:51,810 --> 01:14:54,829
>> Итак, еще раз, именно это уравновешивание
пытаясь решить, какой из этих вещей

1555
01:14:54,829 --> 01:14:55,870
вы готовы потратить?

1556
01:14:55,870 --> 01:14:57,380
Который является наименее дорогим?

1557
01:14:57,380 --> 01:15:01,040
Что дает лучшие результаты?

1558
01:15:01,040 --> 01:15:01,540
Да?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> В самом деле.

1561
01:15:12,580 --> 01:15:15,970
В этом случае, если вы
представления чисел в maps--

1562
01:15:15,970 --> 01:15:18,820
их называют на многих языках
"указатели" или "адреса" -

1563
01:15:18,820 --> 01:15:20,390
это двойное пространство.

1564
01:15:20,390 --> 01:15:24,390
Это не должно быть так плохо, как двойной, если
Прямо сейчас мы просто хранения чисел.

1565
01:15:24,390 --> 01:15:27,410
Предположим, что мы хранили
записи пациента в hospital--

1566
01:15:27,410 --> 01:15:30,870
так называет Пирсона, номера телефонов,
номера социального страхования, доктор

1567
01:15:30,870 --> 01:15:31,540
история.

1568
01:15:31,540 --> 01:15:34,160
Это поле может быть много,
гораздо больше, и в этом случае

1569
01:15:34,160 --> 01:15:38,000
крошечная указатель, адрес
следующая element-- это не имеет большого значения.

1570
01:15:38,000 --> 01:15:40,620
Это такая бахрома
стоимость не имеет значения.

1571
01:15:40,620 --> 01:15:43,210
Но в этом случае, да, это удвоение.

1572
01:15:43,210 --> 01:15:45,290
Хороший вопрос.

1573
01:15:45,290 --> 01:15:47,900
>> Давайте поговорим о том времени, а
чуть более конкретно.

1574
01:15:47,900 --> 01:15:50,380
Что время работы
поиска этот список?

1575
01:15:50,380 --> 01:15:53,640
Предположим, что я хотел искать
через все классы студентов,

1576
01:15:53,640 --> 01:15:55,980
и есть п классов
в этой структуре данных.

1577
01:15:55,980 --> 01:15:58,830
Здесь, также, мы можем заимствовать
словарный запас ранее.

1578
01:15:58,830 --> 01:16:00,890
Это линейная структура данных.

1579
01:16:00,890 --> 01:16:04,570
>> Big O п является то, что требуется, чтобы получить
к концу этой структуры данных,

1580
01:16:04,570 --> 01:16:08,410
whereas-- и мы не видели
это before-- массив дает вам

1581
01:16:08,410 --> 01:16:13,555
что называется постоянной времени, что означает,
один шаг или два шага или 10 steps--

1582
01:16:13,555 --> 01:16:14,180
не имеет значения.

1583
01:16:14,180 --> 01:16:15,440
Это фиксированное число.

1584
01:16:15,440 --> 01:16:17,440
Она не имеет ничего общего с
размер массива.

1585
01:16:17,440 --> 01:16:20,130
И причина этого,
опять же, с произвольным доступом.

1586
01:16:20,130 --> 01:16:23,180
Компьютер может просто немедленно
перейти на другое место,

1587
01:16:23,180 --> 01:16:27,770
потому что они все равно
расстояние от всего остального.

1588
01:16:27,770 --> 01:16:29,112
Там нет мышления участвует.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Отлично.

1591
01:16:32,400 --> 01:16:39,230
Так что, если я могу, я попытаюсь
нарисовать два финальных изображений.

1592
01:16:39,230 --> 01:16:42,830
Очень часто один известный как хэш-таблицу.

1593
01:16:42,830 --> 01:16:51,120
Таким образом, чтобы мотивировать эту дискуссию,
дайте мне подумать о том, как это сделать.

1594
01:16:51,120 --> 01:16:52,610
>> Так как насчет этого?

1595
01:16:52,610 --> 01:16:55,160
Предположим, что задача
мы хотим решить прямо сейчас

1596
01:16:55,160 --> 01:16:58,360
осуществляет в dictionary--
так целая куча английских слов

1597
01:16:58,360 --> 01:16:59,330
или любой другой.

1598
01:16:59,330 --> 01:17:02,724
И цель состоит в том, чтобы быть в состоянии ответить
вопросы форме это слово?

1599
01:17:02,724 --> 01:17:04,640
Так что вы хотите реализовать
программа проверки орфографии, просто

1600
01:17:04,640 --> 01:17:07,220
как физический словарь
что вы можете посмотреть вещи в.

1601
01:17:07,220 --> 01:17:10,490
Предположим, я сделать это с помощью массива.

1602
01:17:10,490 --> 01:17:12,590
Я мог бы сделать это.

1603
01:17:12,590 --> 01:17:20,756
>> И предположим, что слова яблоко
и банан и дыня.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
И я не могу думать о фруктах
которые начинаются с D, так что мы просто

1606
01:17:26,465 --> 01:17:27,590
будет иметь три фруктов.

1607
01:17:27,590 --> 01:17:31,510
Так что это массив, и мы
хранить все эти слова

1608
01:17:31,510 --> 01:17:34,200
в этом словаре как массив.

1609
01:17:34,200 --> 01:17:39,350
Вопрос, тогда, как еще
Вы могли бы хранить эту информацию?

1610
01:17:39,350 --> 01:17:43,160
>> Ну, я своего рода обман здесь, потому что
каждая из этих букв в слове

1611
01:17:43,160 --> 01:17:44,490
действительно индивидуальный байт.

1612
01:17:44,490 --> 01:17:46,740
Так что, если я действительно хотел быть
нит-разборчивы, я должен действительно

1613
01:17:46,740 --> 01:17:49,600
быть разделив это вверх в гораздо
меньшие куски памяти,

1614
01:17:49,600 --> 01:17:51,289
и мы могли бы сделать именно это.

1615
01:17:51,289 --> 01:17:53,580
Но мы будем работать в
та же проблема, как и раньше.

1616
01:17:53,580 --> 01:17:56,674
Что если, как Merriam Webster или Оксфорд
делает каждый год-- они добавляют слова

1617
01:17:56,674 --> 01:17:59,340
к dictionary-- мы не делаем
обязательно хотят рисовать себя

1618
01:17:59,340 --> 01:18:00,780
в угол с массивом?

1619
01:18:00,780 --> 01:18:05,710
>> Так что вместо того, чтобы, может быть, умнее подход
это положить яблоко в своем собственном узле или коробке,

1620
01:18:05,710 --> 01:18:11,190
как бы мы сказали, банан, и
то здесь мы имеем дыню.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
И мы струна эти вещи вместе.

1623
01:18:16,790 --> 01:18:19,980
Так что это массив,
это связанный список.

1624
01:18:19,980 --> 01:18:23,300
Если вы не можете достаточно видеть, это просто
говорит "массив", и это говорит, что "список."

1625
01:18:23,300 --> 01:18:25,780
>> Таким образом, мы имеем то же самое
точные вопросы, как и прежде,

1626
01:18:25,780 --> 01:18:28,600
в результате чего мы теперь имеем
динамизм в нашем связанном списке.

1627
01:18:28,600 --> 01:18:31,090
Но у нас есть довольно медленный словарь.

1628
01:18:31,090 --> 01:18:32,870
Предположим, я хочу, чтобы искать слово.

1629
01:18:32,870 --> 01:18:35,430
Это может занять мне большую O п
шаги, потому что слово может

1630
01:18:35,430 --> 01:18:37,840
быть весь путь в конце
список, как дыня.

1631
01:18:37,840 --> 01:18:40,600
И получается, что
в программировании, сортировать

1632
01:18:40,600 --> 01:18:42,700
Грааля данных
структуры, что-то

1633
01:18:42,700 --> 01:18:46,620
что дает вам постоянное
время как массив

1634
01:18:46,620 --> 01:18:50,870
но это по-прежнему дает вам динамизм.

1635
01:18:50,870 --> 01:18:52,940
>> Так что мы можем иметь лучшее из обоих миров?

1636
01:18:52,940 --> 01:18:55,570
И в самом деле, есть что-то
называется хэш-таблицу

1637
01:18:55,570 --> 01:18:59,320
что позволяет делать именно
что, хотя и приблизительно.

1638
01:18:59,320 --> 01:19:03,140
Хэш-таблица представляет собой искуснее
Структура данных, которые мы

1639
01:19:03,140 --> 01:19:06,340
может думать, как
сочетание array--

1640
01:19:06,340 --> 01:19:12,390
и я собираюсь нарисовать его
как this-- и связанные списки

1641
01:19:12,390 --> 01:19:17,310
что я буду рисовать, как это здесь.

1642
01:19:17,310 --> 01:19:19,760
>> И то, как эта вещь
работает следующим образом.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Если этот now-- хэш table--
моя третья структура данных,

1645
01:19:29,540 --> 01:19:32,590
и я хочу, чтобы сохранить
Слова в этом, я не

1646
01:19:32,590 --> 01:19:35,440
хочу просто хранить все
слова спина к спине, чтобы спина к спине.

1647
01:19:35,440 --> 01:19:37,430
Я хочу использовать некоторые
часть информации

1648
01:19:37,430 --> 01:19:40,330
о словах, которые позволят
мне получить его там, где это быстрее.

1649
01:19:40,330 --> 01:19:43,666
>> Так что, учитывая слова яблоко
и бананы и дыня,

1650
01:19:43,666 --> 01:19:45,040
Я намеренно выбрал эти слова.

1651
01:19:45,040 --> 01:19:45,340
Зачем?

1652
01:19:45,340 --> 01:19:47,631
Что-то принципиально
отличается о трех?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Что очевидно?

1655
01:19:51,484 --> 01:19:52,900
Они начинаются с разных букв.

1656
01:19:52,900 --> 01:19:53,900
>> Таким образом, вы знаете, что?

1657
01:19:53,900 --> 01:19:57,120
Вместо того, чтобы поместить все мои слова в
то же ведро, так сказать,

1658
01:19:57,120 --> 01:20:00,390
как в одном большом списке, почему не
Я по крайней мере попробовать оптимизацию

1659
01:20:00,390 --> 01:20:04,180
и сделать мои списки 1/26 до тех пор.

1660
01:20:04,180 --> 01:20:07,440
Убедительный оптимизация
может быть, почему не

1661
01:20:07,440 --> 01:20:10,650
Я-- при вставке слова
в эту структуру данных,

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

1663
01:20:14,300 --> 01:20:17,270
все 'Ъ' слова здесь,
и все 'C' слова здесь?

1664
01:20:17,270 --> 01:20:24,610
Так что это в конечном итоге положить яблоко
здесь, банан здесь, дыню здесь,

1665
01:20:24,610 --> 01:20:25,730
и так далее.

1666
01:20:25,730 --> 01:20:31,700
>> И если у меня есть дополнительный
Слово like-- что другое?

1667
01:20:31,700 --> 01:20:36,640
Яблоко, банан, груша.

1668
01:20:36,640 --> 01:20:39,370
Любой думаю плода
которая начинается с А, В или С?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- совершенным.

1670
01:20:40,570 --> 01:20:43,990
Это будет в конечном итоге здесь.

1671
01:20:43,990 --> 01:20:47,530
И поэтому мы, кажется, есть
незначительно лучшее решение,

1672
01:20:47,530 --> 01:20:50,820
потому что теперь, если я хочу
искать яблоко, я

1673
01:20:50,820 --> 01:20:53,200
first-- Я не просто погружение
в моей структуре данных.

1674
01:20:53,200 --> 01:20:54,850
Я не погружайтесь в память моего компьютера.

1675
01:20:54,850 --> 01:20:56,530
Я первый взгляд на первую букву.

1676
01:20:56,530 --> 01:20:58,610
>> И это то, что компьютер
ученый сказал бы.

1677
01:20:58,610 --> 01:21:00,760
Вы хэш в вашей структуре данных.

1678
01:21:00,760 --> 01:21:04,100
Вы берете свой вклад, который в
этот случай является слово, как яблоко.

1679
01:21:04,100 --> 01:21:07,150
Вы анализируете его, глядя на
первая буква в этом случае,

1680
01:21:07,150 --> 01:21:08,340
тем самым хэширования.

1681
01:21:08,340 --> 01:21:10,950
Хэш представляет собой общий термин, в результате чего
вы берете что-то в качестве входных данных

1682
01:21:10,950 --> 01:21:12,116
и вы производите некоторый вывод.

1683
01:21:12,116 --> 01:21:15,090
И выход в том,
случай расположение

1684
01:21:15,090 --> 01:21:18,150
Вы хотите найти, первый
место, второе место, третье место.

1685
01:21:18,150 --> 01:21:22,160
Таким образом, вход яблоко,
выход первого.

1686
01:21:22,160 --> 01:21:25,054
Вход банан,
Вывод должен быть вторым.

1687
01:21:25,054 --> 01:21:27,220
Вход дыня,
вывод должен быть третьим.

1688
01:21:27,220 --> 01:21:30,320
Вход черника,
Вывод должен снова быть вторым.

1689
01:21:30,320 --> 01:21:34,010
И это то, что поможет вам принять
ярлыки через вашу память

1690
01:21:34,010 --> 01:21:39,050
для того, чтобы добраться до слов
или данные более эффективно.

1691
01:21:39,050 --> 01:21:43,330
>> Теперь это сокращает наше время потенциально
по столько, сколько один из 26,

1692
01:21:43,330 --> 01:21:45,850
потому что если предположить, что вы
иметь столько «а» слова, как "Z"

1693
01:21:45,850 --> 01:21:48,080
слова, как "Q" слов, которые
на самом деле не realistic--

1694
01:21:48,080 --> 01:21:50,830
вы будете иметь перекос по
некоторые буквы alphabet--

1695
01:21:50,830 --> 01:21:53,204
но это было бы инкрементный
Подход, который действительно позволяет

1696
01:21:53,204 --> 01:21:55,930
вы, чтобы добраться до слов гораздо быстрее.

1697
01:21:55,930 --> 01:21:59,660
И в самом деле, сложный
программа, то Googles мира,

1698
01:21:59,660 --> 01:22:02,180
Facebooks из world--
они будут использовать хэш-таблицу

1699
01:22:02,180 --> 01:22:03,740
для многих различных целей.

1700
01:22:03,740 --> 01:22:06,590
Но они не были бы настолько наивен,
чтобы просто посмотреть на первую букву

1701
01:22:06,590 --> 01:22:09,700
в яблоко или банан или
груша или дыня,

1702
01:22:09,700 --> 01:22:13,420
потому что, как вы можете видеть эти
списки могут получить еще долго.

1703
01:22:13,420 --> 01:22:17,130
>> И так что это еще может быть своего рода
из linear-- так вроде медленно,

1704
01:22:17,130 --> 01:22:19,980
как с большим O п
что мы обсуждали ранее.

1705
01:22:19,980 --> 01:22:25,290
Так что реальная хорошая хеш-таблица будет
do-- он будет иметь гораздо больший массив.

1706
01:22:25,290 --> 01:22:28,574
И это будет использовать гораздо больше
сложные функции хеширования,

1707
01:22:28,574 --> 01:22:30,240
так что это не просто смотреть на «а».

1708
01:22:30,240 --> 01:22:35,480
Может быть, он смотрит на "а-р-р-л-е" и
каким-то образом преобразует эти пять букв

1709
01:22:35,480 --> 01:22:38,400
в том месте, где
яблоко должно быть сохранено.

1710
01:22:38,400 --> 01:22:42,660
Мы просто по наивности, используя букву 'A'
в одиночку, потому что это просто и красиво.

1711
01:22:42,660 --> 01:22:44,600
>> Но хэш-таблицу, в
конец, вы можете думать

1712
01:22:44,600 --> 01:22:47,270
в виде комбинации
массив, каждый из которых

1713
01:22:47,270 --> 01:22:51,700
имеет связанный список, что в идеале
должно быть как можно короче.

1714
01:22:51,700 --> 01:22:54,364
И это не является очевидным решением.

1715
01:22:54,364 --> 01:22:57,280
На самом деле, большая часть тонкой настройки
что происходит под капот, когда

1716
01:22:57,280 --> 01:22:59,654
осуществление этих видов
сложные структуры данных

1717
01:22:59,654 --> 01:23:01,640
это то, что является правильным
длина массива?

1718
01:23:01,640 --> 01:23:03,250
Что такое правильный хэш-функция?

1719
01:23:03,250 --> 01:23:04,830
Как вы храните вещи в памяти?

1720
01:23:04,830 --> 01:23:07,249
>> Но понять, насколько быстро
такого рода дискуссии

1721
01:23:07,249 --> 01:23:10,540
возрастали, либо до сих пор, что это своего рода
из над головой в этот момент, который

1722
01:23:10,540 --> 01:23:11,360
Это хорошо.

1723
01:23:11,360 --> 01:23:18,820
Но мы начали, напомним, с истинно
что-то низкого уровня и электронные.

1724
01:23:18,820 --> 01:23:20,819
И так это опять-таки это
тема абстракции,

1725
01:23:20,819 --> 01:23:23,610
где, как только вы начнете принимать для
как должное, в порядке, у меня есть it--

1726
01:23:23,610 --> 01:23:26,680
физической памяти, ОК, получил его, каждый
физическое расположение имеет адрес,

1727
01:23:26,680 --> 01:23:29,910
ОК, я получил его, я могу представить
эти адреса как arrows--

1728
01:23:29,910 --> 01:23:34,650
Вы можете очень быстро начать иметь
более сложные разговоры о том,

1729
01:23:34,650 --> 01:23:38,360
в конце концов, кажется, что позволяет нам
решать проблемы, такие как поиск

1730
01:23:38,360 --> 01:23:41,620
и сортировки более эффективно.

1731
01:23:41,620 --> 01:23:44,190
И будьте уверены, too--
потому что я думаю, что это

1732
01:23:44,190 --> 01:23:48,700
является самым глубоким мы пошли в некоторые
из этих тем CS proper-- мы

1733
01:23:48,700 --> 01:23:51,880
сделано в полтора дня на это
указать, что вы, возможно, как правило, делают более

1734
01:23:51,880 --> 01:23:55,520
течение восьми недель в течение семестра.

1735
01:23:55,520 --> 01:23:59,670
>> Любые вопросы по этим?

1736
01:23:59,670 --> 01:24:01,100
Нет?

1737
01:24:01,100 --> 01:24:01,940
Отлично.

1738
01:24:01,940 --> 01:24:05,610
Ну, почему бы нам не сделать паузу там,
начать обед на несколько минут раньше,

1739
01:24:05,610 --> 01:24:07,052
резюме всего около часа?

1740
01:24:07,052 --> 01:24:08,760
И я буду задерживаться
немного с вопросами.

1741
01:24:08,760 --> 01:24:11,343
Тогда я буду должен идти
взять пару звонков, если это нормально.

1742
01:24:11,343 --> 01:24:15,000
Я включу музыку в то же время,
но обед должен быть за углом.

1743
01:24:15,000 --> 01:24:17,862