1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[Музыка, играющая]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID Маланом: Это CS50.

5
00:00:14,010 --> 00:00:18,090
И это как начало и
end-- как literally-- почти до конца

6
00:00:18,090 --> 00:00:18,825
из шестой неделе.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> Я думал, я бы поделиться
Немного веселья самом деле.

9
00:00:22,640 --> 00:00:25,370
Я вытащил этот от
установить данные прошлой семестра.

10
00:00:25,370 --> 00:00:29,710
Вы можете вспомнить, что мы просим вас на каждый
р установленной формы, если вы смотрели онлайн

11
00:00:29,710 --> 00:00:31,580
или если вы присутствовали лично.

12
00:00:31,580 --> 00:00:33,020
А вот данные.

13
00:00:33,020 --> 00:00:34,710
Так что сегодня было очень много предсказуемым.

14
00:00:34,710 --> 00:00:37,126
Но мы хотели, чтобы потратить немного
времени с вами, тем не менее.

15
00:00:37,126 --> 00:00:40,599
Кто-нибудь предположить, почему это
График настолько пьяный, вверх вниз, вверх вниз,

16
00:00:40,599 --> 00:00:41,265
так последовательно?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
Что делать каждому из пиков
и желоба представляют?

19
00:00:45,130 --> 00:00:46,005
>> АУДИТОРИЯ: [неразборчиво]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID Маланом: Действительно.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
И еще забавно, не дай бог,
мы проводим одну лекцию в пятницу

24
00:00:55,480 --> 00:00:58,960
в начале семестра,
это то, что мы видим случиться.

25
00:00:58,960 --> 00:01:03,430
Поэтому сегодня, когда мы принимаем в немного
больше о структурах данных.

26
00:01:03,430 --> 00:01:06,660
И, чтобы дать вам более твердого тела
Ментальная модель для задач в пять,

27
00:01:06,660 --> 00:01:07,450
который в настоящее время вне.

28
00:01:07,450 --> 00:01:10,817
Орфографические ошибки, в котором мы будем
вручить вам текстовый файл некоторые 100000

29
00:01:10,817 --> 00:01:12,650
плюс английские слова, и
Вы будете иметь,

30
00:01:12,650 --> 00:01:17,770
чтобы выяснить, как ловко загружать их
в память, в оперативной памяти, используя некоторые данные

31
00:01:17,770 --> 00:01:19,330
Структура вашего выбора.

32
00:01:19,330 --> 00:01:22,470
>> Теперь одна такая структура данных может
быть, но, вероятно, не должно быть,

33
00:01:22,470 --> 00:01:25,630
довольно упрощенно связанный список,
которые мы ввели в прошлый раз.

34
00:01:25,630 --> 00:01:29,220
И связанный список, по крайней мере,
Одно из преимуществ над массивом.

35
00:01:29,220 --> 00:01:32,096
Что одно преимущество
связанный список, возможно?

36
00:01:32,096 --> 00:01:32,950
>> АУДИТОРИЯ: Вставка.

37
00:01:32,950 --> 00:01:33,908
>> DAVID Маланом: Вставка.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
Что вы имеете в виду?

40
00:01:35,196 --> 00:01:37,872
>> АУДИТОРИЯ: Где угодно вместе
Список [неразборчиво].

41
00:01:37,872 --> 00:01:38,770
>> DAVID Маланом: Хорошо.

42
00:01:38,770 --> 00:01:42,090
Таким образом, вы можете вставить элемент там, где это
Вы хотите в середине списка

43
00:01:42,090 --> 00:01:45,490
без перетасовать ничего,
которые мы заключили, в нашем сортировки

44
00:01:45,490 --> 00:01:47,630
дискуссии, не
обязательно хорошо,

45
00:01:47,630 --> 00:01:51,200
потому что это занимает время, чтобы действительно двигаться
все эти человека влево или вправо.

46
00:01:51,200 --> 00:01:55,540
И так со связанным списком, вы можете
просто выделить с таНос, новый узел,

47
00:01:55,540 --> 00:01:58,385
а затем обновить пару
pointers-- два, три операции max--

48
00:01:58,385 --> 00:02:01,480
и мы в состоянии слот кого
в любом месте в списке.

49
00:02:01,480 --> 00:02:03,550
>> Что еще было выгодно
о связанном списке?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
Да?

52
00:02:05,659 --> 00:02:06,534
>> АУДИТОРИЯ: [неразборчиво]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID Маланом: Прекрасно.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
Идеальный.

57
00:02:11,090 --> 00:02:12,070
Это действительно динамичным.

58
00:02:12,070 --> 00:02:15,100
И что вы не совершает,
заранее, до некоторой фиксированного размера

59
00:02:15,100 --> 00:02:18,750
участок памяти, как вам придется
чтобы с массивом, вверх из которых

60
00:02:18,750 --> 00:02:22,455
является то, что вы можете выделить узлы только на
Спрос, таким образом, используя только столько места

61
00:02:22,455 --> 00:02:23,330
как вы на самом деле нужно.

62
00:02:23,330 --> 00:02:26,830
В отличие от массива, вы могли бы
случайно выделить слишком мало.

63
00:02:26,830 --> 00:02:28,871
А потом он просто будет
быть боль в шее

64
00:02:28,871 --> 00:02:32,440
перераспределить новый больший массив, копировать
все более, освободить старый массив,

65
00:02:32,440 --> 00:02:33,990
а затем перейти о вашем бизнесе.

66
00:02:33,990 --> 00:02:37,479
Или еще хуже, вы можете выделить путь
больше памяти, чем вы на самом деле нужно,

67
00:02:37,479 --> 00:02:40,520
и таким образом, вы будете иметь очень
малонаселенной массив, так сказать.

68
00:02:40,520 --> 00:02:44,350
>> Так связанный список дает эти
Преимущества динамизм и гибкость

69
00:02:44,350 --> 00:02:46,080
с вставки и удаления.

70
00:02:46,080 --> 00:02:48,000
Но, безусловно, должна быть цена, заплаченная.

71
00:02:48,000 --> 00:02:50,000
На самом деле, одна из тем,
исследовали на викторине нулевой

72
00:02:50,000 --> 00:02:52,430
было пару компромиссов
мы видели до сих пор.

73
00:02:52,430 --> 00:02:56,161
Так что цена, заплаченная или
Недостатком связанного списка?

74
00:02:56,161 --> 00:02:56,660
Да.

75
00:02:56,660 --> 00:02:57,560
>> АУДИТОРИЯ: Нет произвольного доступа.

76
00:02:57,560 --> 00:02:58,809
>> DAVID Маланом: Нет произвольного доступа.

77
00:02:58,809 --> 00:02:59,540
Но кого это волнует?

78
00:02:59,540 --> 00:03:01,546
Произвольный доступ звучит не убедительно.

79
00:03:01,546 --> 00:03:02,421
>> АУДИТОРИЯ: [неразборчиво]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID Маланом: Совершенно верно.

82
00:03:05,740 --> 00:03:07,580
Если вы хотите иметь
определенная algorithm--

83
00:03:07,580 --> 00:03:10,170
и позвольте мне на самом деле предлагают
бинарный поиск, в частности, что

84
00:03:10,170 --> 00:03:12,600
является одним мы использовали довольно bit--
если у вас нет случайного доступа,

85
00:03:12,600 --> 00:03:15,516
Вы не можете сделать что простую арифметику
найти как средний элемент

86
00:03:15,516 --> 00:03:16,530
и прыгает прямо к нему.

87
00:03:16,530 --> 00:03:20,239
Вы вместо этого начать в первый
элемент и линейно поиск слева

88
00:03:20,239 --> 00:03:22,780
направо, если вы хотите найти
средний или любой другой элемент.

89
00:03:22,780 --> 00:03:24,410
>> АУДИТОРИЯ: Это, вероятно, займет больше памяти.

90
00:03:24,410 --> 00:03:25,040
>> DAVID Маланом: займет больше памяти.

91
00:03:25,040 --> 00:03:27,464
Где, что дополнительный
Стоимость прибывающий из памяти?

92
00:03:27,464 --> 00:03:28,339
>> АУДИТОРИЯ: [неразборчиво]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID Маланом: Совершенно верно.

95
00:03:33,440 --> 00:03:35,679
В этом случае здесь, у нас были
связанный список для целых чисел,

96
00:03:35,679 --> 00:03:37,470
и еще мы удваиваем
объем памяти

97
00:03:37,470 --> 00:03:39,680
мы должны также путем хранения эти указатели.

98
00:03:39,680 --> 00:03:42,090
Теперь менее крупной сделки, как
Ваши Структуры получить больше

99
00:03:42,090 --> 00:03:45,320
и вы храните не ряд, но
может быть, студент или какой-то другой объект.

100
00:03:45,320 --> 00:03:46,880
Но дело, конечно, остается.

101
00:03:46,880 --> 00:03:49,421
И так число операций
на связанных списках назывались

102
00:03:49,421 --> 00:03:50,570
были большими вывода N-- линейной.

103
00:03:50,570 --> 00:03:54,730
Такие вещи, как вставки или поиска
или удаление в случае элемента

104
00:03:54,730 --> 00:03:57,720
оказался в самом конце
Список будь то сортируются или нет.

105
00:03:57,720 --> 00:04:01,167
>> Иногда может повезти и в
так нижние границы этих операций

106
00:04:01,167 --> 00:04:04,250
также может быть постоянной времени, если вы
всегда смотрит на первом элементе,

107
00:04:04,250 --> 00:04:05,070
например.

108
00:04:05,070 --> 00:04:09,360
Но, в конечном счете, мы обещали
для достижения Святой Грааль

109
00:04:09,360 --> 00:04:12,630
структур данных, или
некоторые приближение их,

110
00:04:12,630 --> 00:04:14,290
путем постоянной времени.

111
00:04:14,290 --> 00:04:17,579
Можем ли мы найти элементы или добавлять элементы
или удалять элементы из списка?

112
00:04:17,579 --> 00:04:19,059
Мы увидим совсем скоро.

113
00:04:19,059 --> 00:04:21,100
И получается, что один
механизмов мы

114
00:04:21,100 --> 00:04:23,464
собирается начать использовать сегодня,
Годовое потребление в р установлено пять,

115
00:04:23,464 --> 00:04:24,630
на самом деле довольно знакомым.

116
00:04:24,630 --> 00:04:27,430
Например, если это связка
экзаменационные книг, каждая из которых

117
00:04:27,430 --> 00:04:29,660
имеет студент сначала
имя и фамилия на ней,

118
00:04:29,660 --> 00:04:31,820
и я забрать их из
в конце экзамена,

119
00:04:31,820 --> 00:04:33,746
и все они довольно
много в случайном порядке,

120
00:04:33,746 --> 00:04:36,370
и мы хотим идти о сортировке
эти экзамены, так что, как только оцениваются

121
00:04:36,370 --> 00:04:38,661
это просто намного легче и
быстрее сдать их обратно

122
00:04:38,661 --> 00:04:40,030
для студентов по алфавиту.

123
00:04:40,030 --> 00:04:42,770
Что бы ваши инстинкты быть
для кучи экзаменов, как это?

124
00:04:42,770 --> 00:04:45,019
>> Ну, если вы, как я, вы
могли бы видеть, что это м,

125
00:04:45,019 --> 00:04:48,505
так что я собираюсь рода поставить это в,
если это мой стол или мой этаж, где

126
00:04:48,505 --> 00:04:50,650
Я распространении вещи
out-- или мой массив really--

127
00:04:50,650 --> 00:04:52,210
Я мог бы поставить все Ms там.

128
00:04:52,210 --> 00:04:52,710
О.

129
00:04:52,710 --> 00:04:55,020
Вот А. Таким образом, я мог бы
положить As здесь.

130
00:04:55,020 --> 00:04:55,520
О.

131
00:04:55,520 --> 00:04:57,980
Вот еще А. Я собираюсь
положить, что здесь.

132
00:04:57,980 --> 00:05:02,490
Вот З. Вот еще М. И так
Я мог бы начать делать сваи, как это.

133
00:05:02,490 --> 00:05:06,620
И тогда, возможно, я бы в дальнейшем
и своего рода очень nitpicky-лы рода

134
00:05:06,620 --> 00:05:07,710
отдельные сваи.

135
00:05:07,710 --> 00:05:11,300
Но дело в том, я хотел бы посмотреть
на входе, что я руками

136
00:05:11,300 --> 00:05:14,016
и я хотел бы сделать некоторые рассчитывается
Решение основано на этом входе.

137
00:05:14,016 --> 00:05:15,640
Если он начинается с, положил его там.

138
00:05:15,640 --> 00:05:18,980
Если он начинается с Z, поставить его на
там, и все между ними.

139
00:05:18,980 --> 00:05:22,730
>> Так что это техника, это
как правило, известны как hashing-- Н-A-S-Н-

140
00:05:22,730 --> 00:05:26,550
Обычно это означает, взяв в качестве
вход и с помощью этого вход для расчета

141
00:05:26,550 --> 00:05:30,940
Значение, как правило, количество, и что
число является индексом в хранении

142
00:05:30,940 --> 00:05:32,260
Контейнер, как массив.

143
00:05:32,260 --> 00:05:35,490
Итак, другими словами, я мог бы
Хэш функция, как и я, в моей голове,

144
00:05:35,490 --> 00:05:37,940
что, если я вижу кого-то это
Название, кто начинает с А,

145
00:05:37,940 --> 00:05:40,190
Я собираюсь карту, что
к нулю в моей голове.

146
00:05:40,190 --> 00:05:44,160
И если я вижу кого-то, с Z, я
собирается карту, что до 25 у меня в голове

147
00:05:44,160 --> 00:05:46,220
а затем положить, что в
последний наиболее куча.

148
00:05:46,220 --> 00:05:50,990
>> Теперь, если вы думаете о не мой мозг
но программа C, какие номера могли

149
00:05:50,990 --> 00:05:53,170
Вы полагаетесь на для достижения этой же результат?

150
00:05:53,170 --> 00:05:55,594
Другими словами, если вас
имел ASCII символов A,

151
00:05:55,594 --> 00:05:57,510
как вы определяете,
что ведро положить его в?

152
00:05:57,510 --> 00:05:59,801
Вы, наверное, не хотите, чтобы
положить его в ведро 65, который

153
00:05:59,801 --> 00:06:01,840
будет, как там
без уважительной причины.

154
00:06:01,840 --> 00:06:04,320
Где вы хотите поставить
с точки зрения его стоимости ASCII?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
Где вы хотите сделать его ASCII
Значение придумать умнее ведра

157
00:06:08,920 --> 00:06:09,480
поставить его в?

158
00:06:09,480 --> 00:06:10,206
>> АУДИТОРИЯ: Минус А.

159
00:06:10,206 --> 00:06:10,956
>> DAVID Маланом: Да.

160
00:06:10,956 --> 00:06:13,190
Так минус-минус
специально 65, если это

161
00:06:13,190 --> 00:06:18,240
Столица А. Или 98, если
это строчная.

162
00:06:18,240 --> 00:06:21,300
И так, что позволит нам, очень
просто и очень арифметически,

163
00:06:21,300 --> 00:06:23,260
положить что-то в ведро, как, что.

164
00:06:23,260 --> 00:06:26,010
Вот и получается, что мы на самом деле
это также еще с викторины.

165
00:06:26,010 --> 00:06:29,051
>> Таким образом, вы, возможно, помните, вы кружил ваш
Название преподавательского стипендиата на обложке.

166
00:06:29,051 --> 00:06:32,270
И имена ТФ были организованы
в этих колонках по алфавиту,

167
00:06:32,270 --> 00:06:34,400
хорошо, верить этому или нет,
когда все 80 плюс из нас

168
00:06:34,400 --> 00:06:37,800
собрались в тот вечер в классе,
Последний шаг в нашем процессе аттестации

169
00:06:37,800 --> 00:06:41,830
является хэш викторины в большой
пространство пола в [неразборчиво]

170
00:06:41,830 --> 00:06:45,110
и заложить викторины всеобщие из
точно соблюдать порядок их TF-х

171
00:06:45,110 --> 00:06:47,700
Имена на обложке, потому что
то это намного легче для нас

172
00:06:47,700 --> 00:06:51,290
искать в этом с помощью линейных
поиск или какой-то хитрости

173
00:06:51,290 --> 00:06:54,050
для TF найти его или
викторины ней студентов.

174
00:06:54,050 --> 00:06:56,060
>> Так эта идея хеширования
что вы увидите это

175
00:06:56,060 --> 00:07:00,520
довольно мощный на самом деле довольно
обычным и очень интуитивным,

176
00:07:00,520 --> 00:07:03,000
так же, как, возможно, разделить и
захват был нулевой неделе.

177
00:07:03,000 --> 00:07:05,250
Я перенесемся в Hackathon
Пару лет назад.

178
00:07:05,250 --> 00:07:08,040
Это было Zamyla и пару
Другие студенты персонал поздравительные

179
00:07:08,040 --> 00:07:09,030
как они вошли.

180
00:07:09,030 --> 00:07:12,680
И у нас был целый букет складывания
столы там с бейджи.

181
00:07:12,680 --> 00:07:15,380
И мы теги имен организован
с как как над там

182
00:07:15,380 --> 00:07:16,690
и Zs там.

183
00:07:16,690 --> 00:07:20,350
И поэтому один из ТФ очень умно
написал это как инструкции

184
00:07:20,350 --> 00:07:21,030
в течение дня.

185
00:07:21,030 --> 00:07:24,480
И в 12-й неделе семестра этом
все имело смысл, и все

186
00:07:24,480 --> 00:07:25,310
знал, что делать.

187
00:07:25,310 --> 00:07:27,900
Но в любое время вы имеете
очередь таким же образом,

188
00:07:27,900 --> 00:07:30,272
вы реализуете
же понятие хэш.

189
00:07:30,272 --> 00:07:31,730
Так что давайте формализовать это немного.

190
00:07:31,730 --> 00:07:32,890
Вот это массив.

191
00:07:32,890 --> 00:07:36,820
Это обращается, чтобы быть немного
Широкий просто изобразить, визуально,

192
00:07:36,820 --> 00:07:38,920
что мы могли бы поставить струны
в чем-то вроде этого.

193
00:07:38,920 --> 00:07:41,970
И этот массив
явно размер 26 всего.

194
00:07:41,970 --> 00:07:43,935
И дело называется
Таблица произвольно.

195
00:07:43,935 --> 00:07:48,930
Но это всего лишь исполнение художника
того, что может быть хэш-таблицу.

196
00:07:48,930 --> 00:07:52,799
>> Так хэш-таблицу теперь собирается
быть выше, структура данных уровня.

197
00:07:52,799 --> 00:07:54,840
В конце дня
мы собираемся, чтобы увидеть, что вас

198
00:07:54,840 --> 00:07:58,700
может реализовать хэш-таблицу, которая
это так же, как регистрация в линии

199
00:07:58,700 --> 00:08:02,059
на Hackathon так же, как это
Таблица используется для сортировки экзаменационные книги.

200
00:08:02,059 --> 00:08:03,850
Но таблица хэш
рода этом высоком уровне

201
00:08:03,850 --> 00:08:08,250
Концепция, которая может использовать массив
под капот, чтобы реализовать его,

202
00:08:08,250 --> 00:08:11,890
или это может использовать список длины, или даже
возможно, некоторые другие структуры данных.

203
00:08:11,890 --> 00:08:15,590
А теперь вот theme-- взятие
некоторые из этих фундаментальных ингредиентов

204
00:08:15,590 --> 00:08:18,310
как массив и этого здания
блокировать сейчас из списка длины

205
00:08:18,310 --> 00:08:21,740
и, увидев, что еще мы можем построить
поверх тех, как ингредиенты

206
00:08:21,740 --> 00:08:26,550
в рецепте, что делает все более и более
интересные и полезные окончательные результаты.

207
00:08:26,550 --> 00:08:28,680
>> Так с хэш-таблицы
мы могли бы реализовать его

208
00:08:28,680 --> 00:08:32,540
в памяти наглядно, как это, но
как может он на самом деле быть закодированы до?

209
00:08:32,540 --> 00:08:33,789
Ну, может быть, как просто это.

210
00:08:33,789 --> 00:08:38,270
Если ПОТЕНЦИАЛ заглавными буквами, это просто
некоторые constant-- например 26,

211
00:08:38,270 --> 00:08:42,030
для 26 букв alphabet--
Я мог бы назвать свою таблицу переменных,

212
00:08:42,030 --> 00:08:45,630
и я мог бы утверждать, что я собираюсь
положить текстовые звезды в там, или строки.

213
00:08:45,630 --> 00:08:49,880
Так что это так просто, как это, если вы
хотите реализовать хэш-таблицу.

214
00:08:49,880 --> 00:08:51,490
И все же, это действительно просто массив.

215
00:08:51,490 --> 00:08:53,198
Но, опять же, хэш
Таблица теперь то, что мы будем

216
00:08:53,198 --> 00:08:57,470
называют абстрактный тип данных, это только
рода концептуальной слоев сверху

217
00:08:57,470 --> 00:09:00,780
о чем-то более мирской
Теперь хотелось массив.

218
00:09:00,780 --> 00:09:02,960
>> Теперь, как мы идем
о решении проблем?

219
00:09:02,960 --> 00:09:06,980
Ну, раньше я была роскошь
иметь достаточно места таблицы здесь

220
00:09:06,980 --> 00:09:09,460
так что я мог бы поставить
викторины где угодно, я хотел.

221
00:09:09,460 --> 00:09:10,620
Так, как может идти здесь.

222
00:09:10,620 --> 00:09:12,100
Zs может идти здесь.

223
00:09:12,100 --> 00:09:13,230
Г-жа может идти здесь.

224
00:09:13,230 --> 00:09:14,740
А потом у меня было некоторое дополнительное пространство.

225
00:09:14,740 --> 00:09:18,740
Но это что-то вроде обмана права
Теперь из-за этого стола, если я действительно

226
00:09:18,740 --> 00:09:22,720
думал об этом как массив, просто
будет какого-либо фиксированного размера.

227
00:09:22,720 --> 00:09:25,380
>> Технически, если я тяну
до викторины другого студента

228
00:09:25,380 --> 00:09:28,490
и увидеть, о, это человек-х
Имя начинается с А также,

229
00:09:28,490 --> 00:09:30,980
Я вроде хочу поставить его там.

230
00:09:30,980 --> 00:09:34,740
Но как только я положил его туда, если
эта таблица действительно представляет собой массив,

231
00:09:34,740 --> 00:09:37,840
Я собираюсь быть переопределение или удалив
кто викторина этот студент является.

232
00:09:37,840 --> 00:09:38,340
Не так ли?

233
00:09:38,340 --> 00:09:41,972
Если это массив, только одна вещь может
перейти в каждой из этих клеток или элементов.

234
00:09:41,972 --> 00:09:43,680
И так я вроде есть
выбирать.

235
00:09:43,680 --> 00:09:45,735
>> Теперь ранее я вроде
обманули и сделали это, или я

236
00:09:45,735 --> 00:09:47,526
только отчасти укладываются
их друг над другом.

237
00:09:47,526 --> 00:09:49,170
Но что не собирается лететь в коде.

238
00:09:49,170 --> 00:09:52,260
Так где я мог бы поставить
Второй студент, чье имя

239
00:09:52,260 --> 00:09:54,964
это если все, что я имел это
доступны табличного пространства?

240
00:09:54,964 --> 00:09:57,880
И я использовал три слота и его
Похоже, есть только несколько других.

241
00:09:57,880 --> 00:09:58,959
Что вы могли бы сделать?

242
00:09:58,959 --> 00:09:59,834
АУДИТОРИЯ: [неразборчиво]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID Маланом: Да.

245
00:10:01,315 --> 00:10:02,370
Может быть, давайте просто держать его просто.

246
00:10:02,370 --> 00:10:02,660
Не так ли?

247
00:10:02,660 --> 00:10:04,243
Это не укладывается, где я хочу поставить его.

248
00:10:04,243 --> 00:10:07,450
Так что я собираюсь поставить его
технически, где B пойдет.

249
00:10:07,450 --> 00:10:09,932
Теперь, конечно, я начинаю
рисовать себя в угол.

250
00:10:09,932 --> 00:10:11,890
Если я доберусь до студента
чье имя на самом деле B,

251
00:10:11,890 --> 00:10:14,840
Теперь B собирается быть немного сдвинулся
вперед, как может случиться, да,

252
00:10:14,840 --> 00:10:17,530
если это B, теперь он должен пройти здесь.

253
00:10:17,530 --> 00:10:20,180
>> И так это очень быстро
может стать проблематичным,

254
00:10:20,180 --> 00:10:23,850
но это техника, которая на самом деле
упоминается как линейная зондирования,

255
00:10:23,850 --> 00:10:26,650
в котором вы просто оценить уровень своих
Массив быть вдоль линии.

256
00:10:26,650 --> 00:10:29,680
И вы только отчасти зонд или
проверять каждый доступный элемент

257
00:10:29,680 --> 00:10:31,360
поиск свободного места.

258
00:10:31,360 --> 00:10:34,010
И как только вы найдете
один, вы поместите его в там.

259
00:10:34,010 --> 00:10:38,390
>> Теперь, цена уделяется сейчас
для этого решения является то, что?

260
00:10:38,390 --> 00:10:41,300
У нас есть массив фиксированного размера,
и когда я вставляю имена

261
00:10:41,300 --> 00:10:44,059
в нее, по крайней мере, на начальном этапе, что
время работы вставки

262
00:10:44,059 --> 00:10:46,350
для сдачи студентов
викторины в правильных ведра?

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
Big O чего?

265
00:10:50,002 --> 00:10:51,147
>> АУДИТОРИЯ: н.

266
00:10:51,147 --> 00:10:52,480
DAVID Маланом: Я слышал, большой O п.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
Это не так.

269
00:10:54,300 --> 00:10:56,490
Но мы будем дразнить друг от друга
почему через минуту.

270
00:10:56,490 --> 00:10:57,702
Что еще это может быть?

271
00:10:57,702 --> 00:10:58,755
>> АУДИТОРИЯ: [неразборчиво]

272
00:10:58,755 --> 00:11:00,380
DAVID Маланом: И позвольте мне сделать это визуально.

273
00:11:00,380 --> 00:11:04,720
Так, предположим, это буква S.

274
00:11:04,720 --> 00:11:05,604
>> АУДИТОРИЯ: Это один.

275
00:11:05,604 --> 00:11:06,520
DAVID Маланом: Это один.

276
00:11:06,520 --> 00:11:06,710
Не так ли?

277
00:11:06,710 --> 00:11:08,950
Это массив, который
значит у нас есть произвольный доступ.

278
00:11:08,950 --> 00:11:11,790
И если мы думаем, что это
как ноль и это как 25,

279
00:11:11,790 --> 00:11:13,800
и мы понимаем, что,
ой, вот мой вклад S,

280
00:11:13,800 --> 00:11:16,350
Я могу, конечно, конвертировать
S, ASCII символов,

281
00:11:16,350 --> 00:11:18,540
на соответствующий номер
между нулем и 25

282
00:11:18,540 --> 00:11:20,910
, а затем немедленно
положить его где она принадлежит.

283
00:11:20,910 --> 00:11:26,120
>> Но, конечно, как только я доберусь до
Второй человек, который зовут А или В или С

284
00:11:26,120 --> 00:11:29,300
в конце концов, если я использовал
линейный зондирования в качестве моего решения,

285
00:11:29,300 --> 00:11:31,360
время работы
вставки в худшем случае

286
00:11:31,360 --> 00:11:33,120
на самом деле происходит, чтобы превратится в чем?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
И я слышу его здесь
Правильно рано.

289
00:11:36,045 --> 00:11:36,920
АУДИТОРИЯ: [неразборчиво]

290
00:11:36,920 --> 00:11:41,620
DAVID Маланом: Так это н действительно когда-то
у вас есть достаточно большой набор данных.

291
00:11:41,620 --> 00:11:44,410
Так, с одной стороны, если
ваш массив достаточно велик

292
00:11:44,410 --> 00:11:48,287
и ваши данные достаточно редки, вы
получить эту красивую постоянное время.

293
00:11:48,287 --> 00:11:50,620
Но как только вы начинаете
все больше и больше элементов,

294
00:11:50,620 --> 00:11:53,200
и только статистически Вы получаете
больше людей с буквой

295
00:11:53,200 --> 00:11:56,030
Как их имя или письмо
B, это может потенциально

296
00:11:56,030 --> 00:11:57,900
переходит во что-то более линейными.

297
00:11:57,900 --> 00:11:59,640
Так что не совсем идеально.

298
00:11:59,640 --> 00:12:00,690
Так мы могли сделать лучше?

299
00:12:00,690 --> 00:12:03,210
>> Ну, то, что было нашим
Решение раньше, когда мы

300
00:12:03,210 --> 00:12:06,820
хотят иметь больший динамизм, чем
что-то вроде массива разрешено?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
АУДИТОРИЯ: [неразборчиво]

303
00:12:08,960 --> 00:12:10,030
DAVID Маланом: Что мы вводим?

304
00:12:10,030 --> 00:12:10,530
Да.

305
00:12:10,530 --> 00:12:11,430
Так связанный список.

306
00:12:11,430 --> 00:12:14,430
Ну, давайте посмотрим, что связано
Список может сделать для нас, а не.

307
00:12:14,430 --> 00:12:17,630
Ну, позвольте мне предложить, что мы
рисовать картину следующим образом.

308
00:12:17,630 --> 00:12:19,620
Теперь это уже другая
картинка из примера

309
00:12:19,620 --> 00:12:24,750
с другой текст, на самом деле, что
на самом деле, используя массив размером 31.

310
00:12:24,750 --> 00:12:28,220
И этот автор просто
решил хэш строки

311
00:12:28,220 --> 00:12:32,430
не на основе имен этого лица,
но на основе их даты рождения.

312
00:12:32,430 --> 00:12:35,680
Независимо от месяца, они полагали,
если вы родились с первого месяца

313
00:12:35,680 --> 00:12:39,580
или 31-е число месяца, автор
будет хэш на основе этого значения,

314
00:12:39,580 --> 00:12:44,154
с тем, чтобы распространить имена из немного
больше, чем просто 26 пятна могут позволить.

315
00:12:44,154 --> 00:12:47,320
И, возможно, это немного более равномерное
чем идти с букв алфавита,

316
00:12:47,320 --> 00:12:50,236
потому что, конечно, есть, вероятно,
Чем больше людей в мире с именами

317
00:12:50,236 --> 00:12:54,020
что начало с чем, конечно,
некоторые другие буквы алфавита.

318
00:12:54,020 --> 00:12:56,380
Так, может быть, это немного
более равномерное, предполагая

319
00:12:56,380 --> 00:12:58,640
Равномерное распределение
младенцев через месяц.

320
00:12:58,640 --> 00:12:59,990
>> Но, конечно, это все еще несовершенны.

321
00:12:59,990 --> 00:13:00,370
Не так ли?

322
00:13:00,370 --> 00:13:01,370
Мы с коллизии.

323
00:13:01,370 --> 00:13:04,680
Несколько человек в это
Структура данных по-прежнему

324
00:13:04,680 --> 00:13:08,432
имеющий ту же дату рождения, по крайней мере
Вы, независимо от месяца.

325
00:13:08,432 --> 00:13:09,640
Но то, что автор сделал?

326
00:13:09,640 --> 00:13:13,427
Ну, похоже, что мы имеем массив
на левой стороне, проведенной вертикально,

327
00:13:13,427 --> 00:13:15,010
но вот только исполнение художника.

328
00:13:15,010 --> 00:13:18,009
Это не имеет значения, в каком направлении вам
обратить массив, это все-таки массив.

329
00:13:18,009 --> 00:13:20,225
Что это массив, по-видимому?

330
00:13:20,225 --> 00:13:21,500
>> АУДИТОРИЯ: связанный список.

331
00:13:21,500 --> 00:13:21,650
>> DAVID Маланом: Да.

332
00:13:21,650 --> 00:13:23,490
Похоже, что это
Массив связанного списка.

333
00:13:23,490 --> 00:13:26,490
Итак, еще раз, на этот момент рода
использования этих структур данных сейчас

334
00:13:26,490 --> 00:13:28,550
в качестве ингредиентов в более
интересные решения,

335
00:13:28,550 --> 00:13:30,862
Вы можете абсолютно взять
фундаментальная, как массив,

336
00:13:30,862 --> 00:13:33,320
а затем взять что-то больше
Интересно, как связанный список

337
00:13:33,320 --> 00:13:36,660
и даже объединить их в еще
более интересным структура данных.

338
00:13:36,660 --> 00:13:39,630
И в самом деле, это тоже будет
назвать хэш-таблицу,

339
00:13:39,630 --> 00:13:42,610
в результате чего массив
действительно хеш-таблица,

340
00:13:42,610 --> 00:13:45,600
но, что хеш-таблица имеет
цепи, так сказать,

341
00:13:45,600 --> 00:13:50,220
что может расти или уменьшаться на основе
Количество элементов вы хотите вставить.

342
00:13:50,220 --> 00:13:52,990
>> Теперь, соответственно, что
время работы в настоящее время?

343
00:13:52,990 --> 00:13:58,030
Если я хочу, чтобы вставить кого-
чей день рождения 31 октября

344
00:13:58,030 --> 00:13:59,040
где он или она?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
Хорошо.

347
00:14:01,030 --> 00:14:02,819
В самом низу, где он говорит 31.

348
00:14:02,819 --> 00:14:03,610
И это прекрасно.

349
00:14:03,610 --> 00:14:05,060
Это было постоянное время.

350
00:14:05,060 --> 00:14:08,760
Но что, если мы находим кого-то другого
чей день рождения, давайте посмотрим,

351
00:14:08,760 --> 00:14:10,950
Октябрь, ноябрь 31 декабря?

352
00:14:10,950 --> 00:14:12,790
Где он собирается идти?

353
00:14:12,790 --> 00:14:13,290
То же самое.

354
00:14:13,290 --> 00:14:13,970
Двухступенчатая же.

355
00:14:13,970 --> 00:14:15,303
Это постоянная, хотя не так ли?

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
Хорошо.

358
00:14:16,860 --> 00:14:17,840
На данный момент он является.

359
00:14:17,840 --> 00:14:20,570
Но в общем случае,
чем больше людей мы добавляем,

360
00:14:20,570 --> 00:14:23,790
вероятностно, мы собираемся
чтобы получить больше и больше столкновений.

361
00:14:23,790 --> 00:14:26,820
>> Теперь это немного
лучше, потому что технически

362
00:14:26,820 --> 00:14:34,580
Теперь мои цепи может быть в
в худшем случае, как долго?

363
00:14:34,580 --> 00:14:38,890
Если я вставляю русский народ в это более
сложная структура данных, русский народ,

364
00:14:38,890 --> 00:14:41,080
в худшем случае это будет н.

365
00:14:41,080 --> 00:14:41,815
Почему?

366
00:14:41,815 --> 00:14:43,332
>> АУДИТОРИЯ: Потому что, если все
имеет тот же день рождения,

367
00:14:43,332 --> 00:14:44,545
они собираются быть одна линия.

368
00:14:44,545 --> 00:14:45,420
DAVID Маланом: Прекрасно.

369
00:14:45,420 --> 00:14:47,480
Это может быть немного надуманный,
но действительно, в худшем случае,

370
00:14:47,480 --> 00:14:50,117
если каждый человек имеет тот же день рождения,
учитывая входы у вас есть,

371
00:14:50,117 --> 00:14:51,950
Вы будете иметь,
массово длинная цепочка.

372
00:14:51,950 --> 00:14:54,241
И так, вы могли бы назвать это
хэш-таблицу, но на самом деле это

373
00:14:54,241 --> 00:14:56,810
просто массивный связанный список с
в целом много неиспользуемого пространства.

374
00:14:56,810 --> 00:15:00,460
Но в целом, если считать, что
по крайней мере, дни рождения uniform--

375
00:15:00,460 --> 00:15:01,750
и это, вероятно, нет.

376
00:15:01,750 --> 00:15:02,587
Я делаю это.

377
00:15:02,587 --> 00:15:04,420
Но если предположить, для
ради обсуждения

378
00:15:04,420 --> 00:15:07,717
что они, то в теории, если
Это вертикальное представление

379
00:15:07,717 --> 00:15:11,050
из массива, а затем, надеюсь, вы
собирается получить цепей, которые являются, вы знаете,

380
00:15:11,050 --> 00:15:15,880
примерно такой же длины, где каждый из
это представляет собой день месяца.

381
00:15:15,880 --> 00:15:19,930
>> Теперь, если есть 31 дней в месяц,
что означает мое время работы действительно

382
00:15:19,930 --> 00:15:25,230
большой вывода п над 31, которые
чувствует себя лучше, чем линейный.

383
00:15:25,230 --> 00:15:27,950
Но то, что было одним из наших
Обязательства пару недель

384
00:15:27,950 --> 00:15:31,145
назад, когда он пришел к выражению
время работы алгоритма?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
Просто только посмотрите на высоком срок заказа.

387
00:15:35,190 --> 00:15:35,690
Не так ли?

388
00:15:35,690 --> 00:15:37,400
31, безусловно, полезно.

389
00:15:37,400 --> 00:15:39,610
Но это по-прежнему большой O п.

390
00:15:39,610 --> 00:15:41,730
Но одна из тем,
из проблем установить пять

391
00:15:41,730 --> 00:15:43,950
будет в
признать, что абсолютно,

392
00:15:43,950 --> 00:15:47,320
асимптотически, теоретически
Эта структура данных

393
00:15:47,320 --> 00:15:50,470
нет лучше, чем просто
один массивный связанный список.

394
00:15:50,470 --> 00:15:53,550
И в самом деле, в худшем случае, это
хеш-таблицы может превратится в что.

395
00:15:53,550 --> 00:15:57,620
>> Но в реальном мире, с нами люди
что собственных компьютерах Mac или ПК или что

396
00:15:57,620 --> 00:16:01,240
и работаете реальный мир
Программное обеспечение на реальных данных,

397
00:16:01,240 --> 00:16:03,260
какой алгоритм вы собираетесь предпочитаете?

398
00:16:03,260 --> 00:16:09,180
Тот, который принимает конечные шаги или
тот, который берет н делится на 31 шагов

399
00:16:09,180 --> 00:16:12,900
найти какой-то фрагмент данных или
искать некоторую информацию?

400
00:16:12,900 --> 00:16:16,580
Я имею в виду, абсолютно те 31 марок
Разница в реальном мире.

401
00:16:16,580 --> 00:16:18,540
Это в 31 раз быстрее.

402
00:16:18,540 --> 00:16:20,880
И мы, люди, конечно,
понравится, что.

403
00:16:20,880 --> 00:16:23,004
>> Так понимаю, дихотомию
там между фактически

404
00:16:23,004 --> 00:16:25,920
говорить о том, теоретически
и асимптотически которые определенно

405
00:16:25,920 --> 00:16:28,760
имеет значение, как мы видели,
но в реальном мире,

406
00:16:28,760 --> 00:16:32,930
если вы заботитесь о просто сделать
человек счастлив по общим входам,

407
00:16:32,930 --> 00:16:36,010
Вы могли бы очень хорошо хотят принимать
Дело в том, что, да, это линейная,

408
00:16:36,010 --> 00:16:38,360
но это в 31 раз быстрее
чем линейная может быть.

409
00:16:38,360 --> 00:16:41,610
А еще лучше, мы не просто должны
сделать что-то произвольное, как дата рождения,

410
00:16:41,610 --> 00:16:44,030
мы могли бы потратить немного
Чем больше времени и ум

411
00:16:44,030 --> 00:16:47,140
и думаю о том, что мы могли бы сделать,
имя человека и, может быть,

412
00:16:47,140 --> 00:16:50,130
их дата рождения объединить тех,
ингредиенты, чтобы выяснить что-то

413
00:16:50,130 --> 00:16:52,720
что это действительно больше,
равномерное и менее пьяный,

414
00:16:52,720 --> 00:16:56,250
так сказать, чем этой картине
В настоящее время предполагает, что это могло бы быть.

415
00:16:56,250 --> 00:16:57,750
Как мы могли реализовать это в коде?

416
00:16:57,750 --> 00:17:00,280
Ну, позвольте мне предложить, что мы
просто одолжить синтаксис мы

417
00:17:00,280 --> 00:17:01,799
использовать пару раз до сих пор.

418
00:17:01,799 --> 00:17:03,590
И я собираюсь определить
Узел, который снова

419
00:17:03,590 --> 00:17:06,812
это общий термин для только некоторые
Контейнер по какой структуре данных.

420
00:17:06,812 --> 00:17:09,020
Я собираюсь предложить, чтобы
строка будет там.

421
00:17:09,020 --> 00:17:11,369
Но мы собираемся начать принимать
те, обучение колес от теперь.

422
00:17:11,369 --> 00:17:13,230
>> Нет больше CS50 библиотека
действительно, если вы не хотите

423
00:17:13,230 --> 00:17:15,230
использовать его для вашего финале
Проект, который прекрасен,

424
00:17:15,230 --> 00:17:18,569
но сейчас мы собираемся отступать
занавес и говорят, что это всего лишь символ звезды.

425
00:17:18,569 --> 00:17:22,069
Так слова там будет
имя человека в вопросе.

426
00:17:22,069 --> 00:17:25,079
И теперь у меня есть связь
Здесь к следующему узлу

427
00:17:25,079 --> 00:17:28,170
так, что они представляют
каждый из узлов

428
00:17:28,170 --> 00:17:30,950
в цепи, потенциально,
из связанного списка.

429
00:17:30,950 --> 00:17:34,090
>> А теперь, как я заявляю,
саму таблицу?

430
00:17:34,090 --> 00:17:36,660
Как объявить всю эту структуру?

431
00:17:36,660 --> 00:17:40,960
Ну, на самом деле, так же, как я использовал указатель
чтобы только первый элемент списка

432
00:17:40,960 --> 00:17:44,510
до, так же я могу только сказать,
Мне просто нужно кучу указателей

433
00:17:44,510 --> 00:17:46,270
осуществить весь этот хэш-таблицу.

434
00:17:46,270 --> 00:17:49,484
Я собираюсь есть массив
называется таблица для хэш-таблицы.

435
00:17:49,484 --> 00:17:50,900
Это собирается быть емкости размера.

436
00:17:50,900 --> 00:17:52,525
Вот сколько элементов может поместиться в него.

437
00:17:52,525 --> 00:17:56,180
И каждый из этих элементов в этом
Массив будет узел звезда.

438
00:17:56,180 --> 00:17:56,810
Почему?

439
00:17:56,810 --> 00:18:00,160
Ну, за эту картину, то, что я
реализации хэш-таблицу в качестве

440
00:18:00,160 --> 00:18:04,330
эффективно в начало всего
это массив, который мы нарисовали вертикально,

441
00:18:04,330 --> 00:18:06,820
каждый из которых квадратов
представляет собой указатель.

442
00:18:06,820 --> 00:18:09,170
Это те, которые имеют косую черту
через них просто нулевым.

443
00:18:09,170 --> 00:18:11,410
И те, которые имеют
Стрелки, идущие справа

444
00:18:11,410 --> 00:18:16,140
фактические указатели на фактические узлов,
Ergo начало связанного списка.

445
00:18:16,140 --> 00:18:19,050
>> Так вот, то, как мы могли бы
реализации хэш-таблицу, что

446
00:18:19,050 --> 00:18:21,580
реализует отдельный цепочки.

447
00:18:21,580 --> 00:18:22,840
Теперь мы можем сделать лучше?

448
00:18:22,840 --> 00:18:25,632
Ладно, я обещал в прошлый раз, что
мы могли бы добиться постоянного времени.

449
00:18:25,632 --> 00:18:27,381
И я как бы дал вам
постоянная времени здесь,

450
00:18:27,381 --> 00:18:29,850
но тогда не сказал на самом деле
Постоянная времени, потому что это все-таки

451
00:18:29,850 --> 00:18:31,890
зависит от общего
Количество элементов

452
00:18:31,890 --> 00:18:34,500
Вы ввода в
Структура данных.

453
00:18:34,500 --> 00:18:35,980
Но предположим, что мы сделали это.

454
00:18:35,980 --> 00:18:39,550
Позвольте мне вернуться к экрану здесь.

455
00:18:39,550 --> 00:18:44,520
Позвольте мне также проецировать это здесь, очевидно,
экран, и предположим, что я сделал это.

456
00:18:44,520 --> 00:18:49,300
Предположим, что я хотел, чтобы вставить имя
Daven в в моей структуре данных.

457
00:18:49,300 --> 00:18:52,100
>> Поэтому я хочу, чтобы вставить строку
Daven в структуре данных.

458
00:18:52,100 --> 00:18:54,370
Что делать, если я не использую
хэш-таблицы, но я использую

459
00:18:54,370 --> 00:18:56,980
что-то, что больше древовидная
как родословной, где

460
00:18:56,980 --> 00:18:59,670
у вас есть корень в
Верхняя и затем узлы и листья

461
00:18:59,670 --> 00:19:01,440
что идти вниз и наружу.

462
00:19:01,440 --> 00:19:04,450
Предположим, то, что я
хотите вставить Daven-х

463
00:19:04,450 --> 00:19:06,430
в то, что в настоящее время пустой список.

464
00:19:06,430 --> 00:19:09,780
Я собираюсь сделать следующее: я
собирается создать узел в этой семье

465
00:19:09,780 --> 00:19:15,170
древовидная структура данных, которая выглядит
немного как это, каждый из которых

466
00:19:15,170 --> 00:19:19,640
прямоугольники уже, скажем,
а пока 26 элементов в нем.

467
00:19:19,640 --> 00:19:21,650
И каждый из клеток
в этом массиве будет

468
00:19:21,650 --> 00:19:23,470
представлять букву алфавита.

469
00:19:23,470 --> 00:19:28,190
>> В частности, я собираюсь лечить
это, то В, то С, затем D,

470
00:19:28,190 --> 00:19:29,310
этот здесь.

471
00:19:29,310 --> 00:19:32,940
Так это будет эффективно
представляют букву D.

472
00:19:32,940 --> 00:19:36,040
Но, чтобы вставить все Daven-х
назвать мне нужно сделать немного больше.

473
00:19:36,040 --> 00:19:37,840
Так что я сначала буду хэш, так сказать.

474
00:19:37,840 --> 00:19:41,049
Я собираюсь посмотреть на первую букву
в Daven, который, очевидно, является D,

475
00:19:41,049 --> 00:19:42,840
и я собираюсь выделить
узел, который выглядит

476
00:19:42,840 --> 00:19:45,570
как this-- большой прямоугольник большой
достаточно, чтобы соответствовать весь алфавит.

477
00:19:45,570 --> 00:19:47,140
>> Теперь D делается.

478
00:19:47,140 --> 00:19:49,720
Теперь А. Д-А-В-Е-Н и является целью.

479
00:19:49,720 --> 00:19:51,220
Так что теперь я собираюсь сделать это.

480
00:19:51,220 --> 00:19:54,027
Как только я начал D уведомление
нет указателя там.

481
00:19:54,027 --> 00:19:56,860
Это ценности мусора на данный момент,
или я мог бы инициализировать его до нуля.

482
00:19:56,860 --> 00:19:59,630
Но позвольте мне продолжать идти с
эта идея построения дерева.

483
00:19:59,630 --> 00:20:04,260
Позвольте мне выделить еще один из них
узлы, которые имеет 26 элементов в нем.

484
00:20:04,260 --> 00:20:05,150
>> И знаете что?

485
00:20:05,150 --> 00:20:09,130
Если это всего лишь узел в памяти, что
Я создал с таНос, используя-структуру

486
00:20:09,130 --> 00:20:11,240
как мы скоро увидим,
Я собираюсь сделать this--

487
00:20:11,240 --> 00:20:14,450
Я собираюсь нарисовать стрелку от
вещь, которая представлена ​​D вниз

488
00:20:14,450 --> 00:20:15,860
в этом новом узле.

489
00:20:15,860 --> 00:20:19,240
А теперь, во-первых рядом
Письмо на имя Daven в,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- я собираюсь идти вперед
и сделать еще один узел, как это,

491
00:20:24,150 --> 00:20:30,150
в результате чего, в V элементы здесь, которые
мы будем рисовать для instance-- возгласами.

492
00:20:30,150 --> 00:20:31,020
Мы не будем рисовать там.

493
00:20:31,020 --> 00:20:31,936
Это собирается идти сюда.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> Тогда мы идем к
считают, что это В.

496
00:20:35,712 --> 00:20:44,920
А потом сюда мы собираемся индекса
по сравнению с V в то, что мы будем рассматривать E.

497
00:20:44,920 --> 00:20:50,100
А потом отсюда мы собираемся
пойти иметь один из этих узлов здесь.

498
00:20:50,100 --> 00:20:52,930
И теперь у нас есть вопрос, чтобы ответить.

499
00:20:52,930 --> 00:20:57,840
Мне нужно как-то указать, что
мы в конце строки Daven.

500
00:20:57,840 --> 00:20:59,490
Так что я мог просто оставить его пустым.

501
00:20:59,490 --> 00:21:02,670
>> Но что делать, если у нас есть Daven-х
ФИО также, что

502
00:21:02,670 --> 00:21:04,280
это, как мы уже говорили, Дэвенпорт?

503
00:21:04,280 --> 00:21:06,970
Так что, если Daven является
фактически подстрока,

504
00:21:06,970 --> 00:21:08,960
префиксом гораздо более длинной строки?

505
00:21:08,960 --> 00:21:11,450
Мы не можем просто постоянно
сказать ничего не происходит

506
00:21:11,450 --> 00:21:14,410
туда, потому что мы могли
никогда не вставить слово, как Давенпорт

507
00:21:14,410 --> 00:21:15,840
в этой структуре данных

508
00:21:15,840 --> 00:21:19,560
>> Так что мы можем сделать, а не является
лечения каждого из этих элементов

509
00:21:19,560 --> 00:21:22,170
как может быть, имея два
элементы внутри них.

510
00:21:22,170 --> 00:21:24,810
Одним из них является указателем, в самом деле,
как я делал.

511
00:21:24,810 --> 00:21:27,100
Таким образом, каждый из этих ящиков
это не просто одна клетка.

512
00:21:27,100 --> 00:21:29,855
Но что делать, если верхняя
одно-- нижний-х

513
00:21:29,855 --> 00:21:32,230
будет нулевым, потому что
нет Дэвенпорт только пока.

514
00:21:32,230 --> 00:21:34,197
Что делать, если верхний
это какая-то особая ценность?

515
00:21:34,197 --> 00:21:36,530
И это будет немного
трудно сделать это этот размер.

516
00:21:36,530 --> 00:21:38,130
Но предполагаю, что это просто галочка.

517
00:21:38,130 --> 00:21:38,920
Проверьте.

518
00:21:38,920 --> 00:21:44,230
Д-А-В-Е-Н представляет собой строку
В этой структуры данных.

519
00:21:44,230 --> 00:21:48,350
>> Между тем, если бы я имел больше места
здесь, что я мог сделать P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
и я мог бы поставить проверку в узле
что есть буква Т в самом конце.

521
00:21:52,650 --> 00:21:55,460
Так что это массово
Комплекс вид структуры данных.

522
00:21:55,460 --> 00:21:57,210
И мой почерк
конечно, не поможет.

523
00:21:57,210 --> 00:22:00,043
Но если бы я хотел, чтобы вставить что-то
еще, подумайте, что мы будем делать.

524
00:22:00,043 --> 00:22:03,370
Если бы мы хотели поставить Давида в,
мы следовать той же логике, D-A-V,

525
00:22:03,370 --> 00:22:08,802
но сейчас я хотел бы отметить в следующем
Элемент не от Е, но от I до D.

526
00:22:08,802 --> 00:22:10,760
Так что это будет
больше узлов в этом дереве.

527
00:22:10,760 --> 00:22:12,325
Мы собираемся иметь вызова таНос более.

528
00:22:12,325 --> 00:22:14,700
Но я не хочу, чтобы сделать
полный беспорядок изображения.

529
00:22:14,700 --> 00:22:17,710
Итак, давайте вместо этого смотреть в одном
который был предварительно сформулированы

530
00:22:17,710 --> 00:22:21,810
как это с не точка, точка,
точки, но только сокращенные массивы.

531
00:22:21,810 --> 00:22:23,950
Но каждый из узлов
в этом дереве здесь

532
00:22:23,950 --> 00:22:26,700
представляет тот же thing--
Массив Луч размера 26.

533
00:22:26,700 --> 00:22:28,860
>> Или, если мы хотим быть
действительно правильное сейчас, что

534
00:22:28,860 --> 00:22:30,790
если кто-то имя, как
апостроф, давайте

535
00:22:30,790 --> 00:22:35,560
Предположим, что каждый узел имеет фактически
как 27 индексов в этом, а не только 26.

536
00:22:35,560 --> 00:22:42,020
Так что это теперь будет данных
Структура называется trie-- T-R-I-Е.

537
00:22:42,020 --> 00:22:46,120
Trie, который, предположительно,
исторически умный имя для дерева

538
00:22:46,120 --> 00:22:49,040
который оптимизирован для
поиск, который конечно же,

539
00:22:49,040 --> 00:22:50,870
пишется с I-Е так это Trie.

540
00:22:50,870 --> 00:22:52,710
Но это история синтаксического дерева.

541
00:22:52,710 --> 00:22:55,860
>> Так Trie это древовидная данных
Структура как родословной

542
00:22:55,860 --> 00:22:57,510
что в конечном счете ведет себя так.

543
00:22:57,510 --> 00:23:00,890
А вот еще один пример
целая куча имен других людей.

544
00:23:00,890 --> 00:23:03,540
Но вопрос сейчас
под рукой то, что есть

545
00:23:03,540 --> 00:23:08,070
мы получили путем введения возможно более
сложной структурой данных, и один,

546
00:23:08,070 --> 00:23:09,870
честно говоря, что использует много памяти.

547
00:23:09,870 --> 00:23:11,703
>> Потому что даже при том, что,
на данный момент, я только

548
00:23:11,703 --> 00:23:15,050
с помощью указателя Д и
И V и Es и Ns,

549
00:23:15,050 --> 00:23:16,700
Я тратить чертовски много памяти.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
Но где я провожу один ресурс,
Я, как правило, ничего получить назад другой.

552
00:23:22,660 --> 00:23:26,020
Так что, если я трачу больше места,
что, вероятно, надежда?

553
00:23:26,020 --> 00:23:27,407
Это я трачу меньше чем?

554
00:23:27,407 --> 00:23:28,240
АУДИТОРИЯ: Меньше времени.

555
00:23:28,240 --> 00:23:28,990
DAVID Маланом: Время.

556
00:23:28,990 --> 00:23:30,320
Теперь, почему это может быть?

557
00:23:30,320 --> 00:23:33,880
Ну, то, что является вставка
время, с точки зрения большой O теперь,

558
00:23:33,880 --> 00:23:37,660
имени, как Daven
или Дэвенпорт или Дэвид?

559
00:23:37,660 --> 00:23:39,340
Ну, Daven было пять шагов.

560
00:23:39,340 --> 00:23:42,350
Дэвенпорт будет девять шагов,
так что было бы несколько шагов.

561
00:23:42,350 --> 00:23:44,250
Дэвид будет пять шагов, а также.

562
00:23:44,250 --> 00:23:47,230
Так что те, конкретны
номера, но, безусловно, есть

563
00:23:47,230 --> 00:23:49,550
верхняя граница
Длина чье-то имя.

564
00:23:49,550 --> 00:23:52,240
И действительно, в задаче
наборы пяти спецификации,

565
00:23:52,240 --> 00:23:54,050
мы собираемся предложить
что это что-то

566
00:23:54,050 --> 00:23:55,470
это 40-некоторые с лишним персонажей.

567
00:23:55,470 --> 00:23:58,180
>> Реально, никто не имеет
бесконечно длинное имя,

568
00:23:58,180 --> 00:24:01,542
который должен сказать, что длина
назвать или длина строки мы могли бы

569
00:24:01,542 --> 00:24:03,750
есть определенная состояние
Структура, возможно, что?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
Это постоянная.

572
00:24:06,250 --> 00:24:06,430
Не так ли?

573
00:24:06,430 --> 00:24:09,310
Это может быть большой постоянной, как
40-то, но это константа.

574
00:24:09,310 --> 00:24:13,752
И это не имеет никакого зависимость от того, сколько
другие названия являются в этой структуре данных.

575
00:24:13,752 --> 00:24:15,460
Другими словами, если I
хотел сейчас вставить

576
00:24:15,460 --> 00:24:20,540
Колтон или Габриэль или Роб или Zamyla или
Элисон или Белинда или любые другие имена

577
00:24:20,540 --> 00:24:23,940
от персонала в этих данных
Структура, является время работы

578
00:24:23,940 --> 00:24:26,750
вставки и другие названия
будет вообще влияние

579
00:24:26,750 --> 00:24:30,220
по тому, как и многие другие элементы являются
в структуре данных, уже?

580
00:24:30,220 --> 00:24:31,040
Это не так.

581
00:24:31,040 --> 00:24:31,540
Не так ли?

582
00:24:31,540 --> 00:24:36,150
Потому что мы эффективно использовать
это многослойная хеш-таблицы.

583
00:24:36,150 --> 00:24:38,280
И время работы
любой из этих операций

584
00:24:38,280 --> 00:24:41,510
зависит не от количества
элементы, которые в структуре данных

585
00:24:41,510 --> 00:24:43,090
или что в конечном итоге происходит
чтобы быть в структуре данных,

586
00:24:43,090 --> 00:24:44,714
но по длине, что конкретно?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> Строка быть
вставлен, который делает

589
00:24:49,200 --> 00:24:52,580
это асимптотически постоянным
time-- большой O одного.

590
00:24:52,580 --> 00:24:54,720
И, честно говоря, просто в
реальный мир, это

591
00:24:54,720 --> 00:24:58,380
означает вставки название Daven берет
как пять шагов, или Дэвенпорт девять

592
00:24:58,380 --> 00:25:00,100
шаги, или Дэвид пять шагов.

593
00:25:00,100 --> 00:25:03,071
Это чертовски маленькие раз ходовые.

594
00:25:03,071 --> 00:25:05,320
И, действительно, это очень
хорошая вещь, особенно когда

595
00:25:05,320 --> 00:25:08,126
это не зависит от общей
Количество элементов в там.

596
00:25:08,126 --> 00:25:10,500
Так как мы можем это реализовать
Такая структура в коде?

597
00:25:10,500 --> 00:25:12,900
Это немного больше,
Комплекс, но все-таки это

598
00:25:12,900 --> 00:25:15,050
только применение
основные строительные блоки.

599
00:25:15,050 --> 00:25:17,830
Я собираюсь пересмотреть
нам узел следующим образом:

600
00:25:17,830 --> 00:25:21,100
Ьоо называется word-- и это
можно было бы назвать что-нибудь.

601
00:25:21,100 --> 00:25:23,970
Но Ьоо представляет
то, что я обратил как галочкой.

602
00:25:23,970 --> 00:25:24,490
Да.

603
00:25:24,490 --> 00:25:26,720
Это конец строки
В этой структуры данных.

604
00:25:26,720 --> 00:25:30,702
>> И, конечно, узел звезда
там имеет в виду детей.

605
00:25:30,702 --> 00:25:32,410
И, в самом деле, так же, как
генеалогическое дерево, вы

606
00:25:32,410 --> 00:25:34,370
рассмотрит узлы
что висят от

607
00:25:34,370 --> 00:25:36,920
из нижней части какой-то из родителей
Элемент быть дети.

608
00:25:36,920 --> 00:25:40,510
И поэтому дети собирается
быть массивом 27, 27 один

609
00:25:40,510 --> 00:25:41,680
просто быть для апострофа.

610
00:25:41,680 --> 00:25:43,390
Мы собираемся, чтобы разобраться
Особый случай этого.

611
00:25:43,390 --> 00:25:45,400
Таким образом, вы можете иметь определенный
Имена участников апострофы.

612
00:25:45,400 --> 00:25:47,399
Может быть, даже дефис должны
идти туда, но вы будете

613
00:25:47,399 --> 00:25:50,330
см в р наборе 5 мы только ухода
о письмах и апострофы.

614
00:25:50,330 --> 00:25:52,990
>> А потом, как вы представляете
сама структура данных?

615
00:25:52,990 --> 00:25:56,454
Как вы представляете корень
этого синтаксического дерева, так сказать?

616
00:25:56,454 --> 00:25:59,620
Ну, точно так же как с связанного списка, вы
нужен указатель на первый элемент.

617
00:25:59,620 --> 00:26:04,270
С синтаксического дерева нужно просто один
указатель на корень этого синтаксического дерева.

618
00:26:04,270 --> 00:26:07,290
И оттуда вы можете хэш
Ваш путь вниз все глубже и глубже

619
00:26:07,290 --> 00:26:10,460
для каждого другого узла в структуре.

620
00:26:10,460 --> 00:26:13,440
Так просто с этой банкой
мы представляем, что-структуру.

621
00:26:13,440 --> 00:26:15,877
>> Теперь Meanwhile-- О, вопрос.

622
00:26:15,877 --> 00:26:17,220
>> АУДИТОРИЯ: Что Ьоо слово?

623
00:26:17,220 --> 00:26:20,490
>> DAVID Маланом: Bool слово
просто это C воплощение

624
00:26:20,490 --> 00:26:22,920
из того, что я описал
в этом поле здесь, когда

625
00:26:22,920 --> 00:26:26,000
Я начал разделения каждой из
элементы массива на две части.

626
00:26:26,000 --> 00:26:27,600
Одним из них является указателем на следующий узел.

627
00:26:27,600 --> 00:26:30,280
Другой должен быть
что-то вроде флажка

628
00:26:30,280 --> 00:26:33,770
сказать да, есть
Слово Daven что здесь заканчивается,

629
00:26:33,770 --> 00:26:35,610
потому что мы не хотим,
на данный момент, Дэйв.

630
00:26:35,610 --> 00:26:39,320
>> Даже при том, что Дэйв будет
законным слово, что он не в синтаксического дерева

631
00:26:39,320 --> 00:26:39,830
еще.

632
00:26:39,830 --> 00:26:40,950
И D нет ни слова.

633
00:26:40,950 --> 00:26:42,770
И D-это не то слово или имя.

634
00:26:42,770 --> 00:26:45,020
Так галочкой
указывает только один раз вас

635
00:26:45,020 --> 00:26:48,190
ударил этот узел
предыдущая путь персонажей

636
00:26:48,190 --> 00:26:50,700
на самом деле это строка, как вы вставили.

637
00:26:50,700 --> 00:26:53,660
Так что все Ьоо
там делает для нас.

638
00:26:53,660 --> 00:26:55,500
>> Любые другие вопросы о попытках?

639
00:26:55,500 --> 00:26:56,215
Да.

640
00:26:56,215 --> 00:26:58,035
>> АУДИТОРИЯ: Что такое перекрытие?

641
00:26:58,035 --> 00:26:59,945
Что делать, если у вас есть Дэйва и Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID Маланом: Прекрасно.

643
00:27:00,820 --> 00:27:02,580
Что делать, если у вас есть Дэйва и Daven?

644
00:27:02,580 --> 00:27:06,240
Так что, если мы вставляем, говорят прозвище,
для David-- Dave-- D-A-V-E?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
На самом деле это супер просто.

647
00:27:08,700 --> 00:27:10,325
Таким образом, мы только собираемся предпринять четыре шага.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
Д-А-В-Е. И то, что мне нужно
сделать, как только я ударил, что четвертый узел?

650
00:27:15,847 --> 00:27:16,680
Просто собираюсь проверить.

651
00:27:16,680 --> 00:27:18,000
Мы уже хорошо идти.

652
00:27:18,000 --> 00:27:18,840
Готово.

653
00:27:18,840 --> 00:27:19,750
Четыре шага.

654
00:27:19,750 --> 00:27:21,590
Постоянное время асимптотически.

655
00:27:21,590 --> 00:27:26,300
И теперь мы показали, что оба Dave
и Daven являются строками в структуре.

656
00:27:26,300 --> 00:27:27,710
Так не проблема.

657
00:27:27,710 --> 00:27:30,200
И обратите внимание, как присутствие
из Daven не сделать это

658
00:27:30,200 --> 00:27:34,750
взять больше времени или меньше
Время для Дэйва, и наоборот.

659
00:27:34,750 --> 00:27:36,000
>> Так что еще мы можем сейчас сделать?

660
00:27:36,000 --> 00:27:40,680
Мы использовали эту метафору до
лотков, представляющий что-то.

661
00:27:40,680 --> 00:27:43,380
Но оказывается, что
стопка лотков на самом деле

662
00:27:43,380 --> 00:27:47,187
демонстративное другого абстрактного данных
type-- более высокую структуру данных уровня

663
00:27:47,187 --> 00:27:49,770
что в конце дня это просто
как массив или связанный список

664
00:27:49,770 --> 00:27:50,970
или что-то более приземленным.

665
00:27:50,970 --> 00:27:53,270
Но это более интересно
концептуальное понятие.

666
00:27:53,270 --> 00:27:56,440
Стек, как это
Лотки здесь в Мазер,

667
00:27:56,440 --> 00:27:58,750
как правило, называют
просто that-- стек.

668
00:27:58,750 --> 00:28:02,540
>> И в этом типе структуры данных
у вас есть два operations--

669
00:28:02,540 --> 00:28:05,880
у вас есть один под названием толчок для
добавляя что-то в стек,

670
00:28:05,880 --> 00:28:08,320
как положить еще один лоток
Вернувшись на вершине стека.

671
00:28:08,320 --> 00:28:11,350
И тогда поп, который означает, что вы
взять верхний офф лотка.

672
00:28:11,350 --> 00:28:16,210
Но то, что ключ о стека является то, что
он получил эту любопытную характеристику.

673
00:28:16,210 --> 00:28:19,560
Как столовой персонала
переставляя лотки для следующего приема пищи,

674
00:28:19,560 --> 00:28:21,380
что будет
правда о том, как студенты

675
00:28:21,380 --> 00:28:22,856
взаимодействовать с этой структурой данных?

676
00:28:22,856 --> 00:28:24,480
АУДИТОРИЯ: Они собираются поп прочь.

677
00:28:24,480 --> 00:28:26,550
DAVID Маланом: Они собираются
поп прочь, мы надеемся на вершину.

678
00:28:26,550 --> 00:28:28,910
В противном случае это просто какая-то глупая
чтобы пройти весь путь до дна.

679
00:28:28,910 --> 00:28:29,070
Не так ли?

680
00:28:29,070 --> 00:28:31,620
Структура данных на самом деле не позволяют
Вы, чтобы захватить нижнюю лоток, по крайней мере

681
00:28:31,620 --> 00:28:32,520
легко.

682
00:28:32,520 --> 00:28:35,040
Так что это любопытно
Свойство к стеку

683
00:28:35,040 --> 00:28:39,730
что последний элемент в это
будет первым из.

684
00:28:39,730 --> 00:28:43,400
И компьютерные ученые называют
это LIFO-- последним пришел, первым вышел.

685
00:28:43,400 --> 00:28:45,540
И это на самом деле есть
интересные приложения.

686
00:28:45,540 --> 00:28:50,090
Это не обязательно так очевидно, как некоторые
и другие, но он может, конечно, быть полезным,

687
00:28:50,090 --> 00:28:54,040
и оно может, в самом деле, быть реализованы
через пару-разному.

688
00:28:54,040 --> 00:28:58,550
>> Так что, и на самом деле, пусть
мне не нырять в том, что.

689
00:28:58,550 --> 00:28:59,860
Давайте сделаем это вместо этого.

690
00:28:59,860 --> 00:29:03,700
Давайте посмотрим на тот, который почти
Та же идея, но это немного более справедливым.

691
00:29:03,700 --> 00:29:04,200
Не так ли?

692
00:29:04,200 --> 00:29:07,560
Если вы один из этих мальчиков вентиляторов или
девочки, что действительно любит продукты компании Apple

693
00:29:07,560 --> 00:29:10,130
и вы проснулись в 3:00
выстраиваться в какой-то магазин

694
00:29:10,130 --> 00:29:14,150
чтобы получить самую последнюю iPhone, вы
возможно, в очереди, как это.

695
00:29:14,150 --> 00:29:15,800
>> Теперь очередь очень сознательно назвал.

696
00:29:15,800 --> 00:29:18,190
Это линия, потому что есть
некоторые справедливость к нему.

697
00:29:18,190 --> 00:29:18,690
Не так ли?

698
00:29:18,690 --> 00:29:21,690
Было бы вид сосал если у вас есть
получил там первый в Apple Store

699
00:29:21,690 --> 00:29:25,700
но вы эффективно нижний
Лоток, потому что сотрудники Apple, затем

700
00:29:25,700 --> 00:29:28,189
поп последний человек, который
на самом деле попал в линию.

701
00:29:28,189 --> 00:29:31,230
Так стеков и очередей, хотя
функционально они вроде в same--

702
00:29:31,230 --> 00:29:33,105
это просто эта коллекция
ресурсов, что это

703
00:29:33,105 --> 00:29:36,210
будет расти и shrink-- там
Этот аспект справедливости к нему,

704
00:29:36,210 --> 00:29:39,634
по крайней мере, в реальном мире,
где операции вы тренируетесь

705
00:29:39,634 --> 00:29:40,800
принципиально отличаются.

706
00:29:40,800 --> 00:29:43,360
Stack-- очереди
rather--, как говорят,

707
00:29:43,360 --> 00:29:45,320
две операции: очереди н и очередей d.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
Или вы можете позвонить им
любое количество вещей.

710
00:29:48,090 --> 00:29:50,770
Но вы просто хотите, чтобы захватить
понятие, что человек добавления

711
00:29:50,770 --> 00:29:53,230
и, в конечном счете один вычитания.

712
00:29:53,230 --> 00:29:58,840
>> Теперь под капотом, как стек
и очередь может быть реализован как?

713
00:29:58,840 --> 00:30:01,390
Мы не будем вдаваться в коде
это потому, что чем выше уровень

714
00:30:01,390 --> 00:30:03,387
Идея является своего рода более очевидным.

715
00:30:03,387 --> 00:30:04,470
Я имею в виду, что ты это делают люди?

716
00:30:04,470 --> 00:30:07,030
Если я первый человек в компании Apple
Храните и это входная дверь,

717
00:30:07,030 --> 00:30:08,130
Вы знаете, что я собираюсь стоять здесь.

718
00:30:08,130 --> 00:30:09,750
И следующий человек
собираюсь стоять здесь.

719
00:30:09,750 --> 00:30:11,500
И следующий человек
собираюсь стоять здесь.

720
00:30:11,500 --> 00:30:13,792
Так что структура данных
поддается очереди?

721
00:30:13,792 --> 00:30:14,542
>> АУДИТОРИЯ: Очередь.

722
00:30:14,542 --> 00:30:15,667
DAVID Маланом: Ну, очереди.

723
00:30:15,667 --> 00:30:16,390
Конечно.

724
00:30:16,390 --> 00:30:16,920
Что еще?

725
00:30:16,920 --> 00:30:17,600
>> АУДИТОРИЯ: связанный список.

726
00:30:17,600 --> 00:30:18,990
>> DAVID Маланом: связаны
список можно реализовать.

727
00:30:18,990 --> 00:30:22,500
И связанный список хорошо, потому что тогда
она может расти сколь угодно долго, в отличие

728
00:30:22,500 --> 00:30:24,880
к тому, некоторое фиксированное число
людей в магазине.

729
00:30:24,880 --> 00:30:27,030
Но, может быть, фиксированное число
мест является законным.

730
00:30:27,030 --> 00:30:30,350
Потому что, если у них только есть, как 20
IPhones в первый день, может быть,

731
00:30:30,350 --> 00:30:33,930
они должны только массив размера
20 чтобы представить эту очередь, которая

732
00:30:33,930 --> 00:30:37,070
только сказать сейчас, как только мы начинаем говорить
об этих высоких задач на уровне,

733
00:30:37,070 --> 00:30:38,890
Вы можете реализовать его
в любом числе путей.

734
00:30:38,890 --> 00:30:42,030
И там, наверное, только собираюсь
быть компромисс в пространстве и времени

735
00:30:42,030 --> 00:30:43,950
или просто в собственном сложности кода.

736
00:30:43,950 --> 00:30:45,380
>> А как насчет стека?

737
00:30:45,380 --> 00:30:48,190
Ну, стек, мы видели слишком
может быть просто эти лотки.

738
00:30:48,190 --> 00:30:50,007
И вы могли бы реализовать этот массив.

739
00:30:50,007 --> 00:30:53,090
Но в какой-то момент, если вы используете массив,
что произойдет с лотков

740
00:30:53,090 --> 00:30:54,173
Вы пытаетесь подавить?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
Хорошо.

743
00:30:55,670 --> 00:30:57,490
Вы только собираетесь
быть в состоянии пойти так высоко.

744
00:30:57,490 --> 00:31:00,156
И я думаю, что в Mather они
фактически встраиваемые в это отверстие.

745
00:31:00,156 --> 00:31:01,950
Так на самом деле, это почти
как Mather использует

746
00:31:01,950 --> 00:31:03,783
массив фиксированного размера,
потому что вы можете только

747
00:31:03,783 --> 00:31:08,302
подходят так много лотков в этом открытии в
стена внизу колени людей.

748
00:31:08,302 --> 00:31:10,010
И так, что может быть
говорят, массив,

749
00:31:10,010 --> 00:31:14,300
но мы, безусловно, может реализовать, что
в более общем с связанного списка.

750
00:31:14,300 --> 00:31:16,390
>> Ну, то, что о другой структуре данных?

751
00:31:16,390 --> 00:31:18,760
Позвольте мне подтянуть один другой визуальный здесь.

752
00:31:18,760 --> 00:31:24,710
Что-то вроде, как об этом один здесь?

753
00:31:24,710 --> 00:31:28,920
Почему это может быть полезно иметь не
что-то фантазии, как синтаксического дерева, которое

754
00:31:28,920 --> 00:31:32,370
мы видели бы эти очень широкие узлы,
каждый из которых находится в массиве?

755
00:31:32,370 --> 00:31:35,740
Но что, если мы делаем что-то более
просто, как старый школьный родословной,

756
00:31:35,740 --> 00:31:38,110
каждый из которых узлы здесь
только сохранении номера.

757
00:31:38,110 --> 00:31:42,180
Вместо имени или потомка
просто сохранении номера вроде этого.

758
00:31:42,180 --> 00:31:45,250
>> Ну, жаргон мы используем в
структуры данных является обе попытки

759
00:31:45,250 --> 00:31:49,510
и деревья, где Trie, опять же,
только один, узлы которого являются массивы,

760
00:31:49,510 --> 00:31:51,680
еще, что вы могли бы
использовать из начальной школы

761
00:31:51,680 --> 00:31:53,860
когда вы сделали семью
tree-- листья и корень

762
00:31:53,860 --> 00:31:57,250
из дерева и детей
родитель и их братья и сестры.

763
00:31:57,250 --> 00:32:03,670
И мы могли бы реализовать дерево,
Например, как просто, как это.

764
00:32:03,670 --> 00:32:07,420
Дерево, если он в виде узла, один из
эти круги, что имеет ряд,

765
00:32:07,420 --> 00:32:09,947
это не будет иметь
один указатель, а два.

766
00:32:09,947 --> 00:32:11,780
И как только вы добавляете
Второй указатель, вы

767
00:32:11,780 --> 00:32:13,905
может на самом деле сейчас сделать вид
двумерного данных

768
00:32:13,905 --> 00:32:14,780
структуры в памяти.

769
00:32:14,780 --> 00:32:16,660
Многое, как двумерный
Массив, вы можете

770
00:32:16,660 --> 00:32:18,904
есть вид двумерных
связанные списки, но те,

771
00:32:18,904 --> 00:32:20,820
что следуют образцу
где нет никаких циклов.

772
00:32:20,820 --> 00:32:24,487
Это действительно дерево с одним
прародитель путь сюда, а затем

773
00:32:24,487 --> 00:32:27,320
некоторые родители и дети, и
внуки и правнуки.

774
00:32:27,320 --> 00:32:28,370
и так далее.

775
00:32:28,370 --> 00:32:32,390
>> Но то, что действительно опрятно об этом тоже,
просто чтобы подразнить вас с немного кода,

776
00:32:32,390 --> 00:32:35,370
Напомним рекурсия от
некоторое время назад, в результате чего

777
00:32:35,370 --> 00:32:38,220
Вы пишете функцию, которая называет себя.

778
00:32:38,220 --> 00:32:41,140
Это красивая возможность
осуществить то,

779
00:32:41,140 --> 00:32:42,920
как рекурсии, потому что считаю это.

780
00:32:42,920 --> 00:32:43,860
>> Это дерево.

781
00:32:43,860 --> 00:32:48,040
И я был немного анальный с тем, как
Я положил целые числа на улицу.

782
00:32:48,040 --> 00:32:51,020
Настолько, что она имеет специальный
name-- дерево двоичного поиска.

783
00:32:51,020 --> 00:32:53,460
Теперь мы слышали о двоичный
поиск, но вы можете

784
00:32:53,460 --> 00:32:55,180
работать в обратном направлении от имени Эта вещь?

785
00:32:55,180 --> 00:32:59,280
Что такое шаблон, как я
вставляется целые числа в этом дереве?

786
00:32:59,280 --> 00:33:00,696
Это не произвольная.

787
00:33:00,696 --> 00:33:01,570
Там какая-то картина.

788
00:33:01,570 --> 00:33:02,090
Да.

789
00:33:02,090 --> 00:33:03,370
>> АУДИТОРИЯ: Небольшие те, что слева.

790
00:33:03,370 --> 00:33:03,690
>> DAVID Маланом: Да.

791
00:33:03,690 --> 00:33:05,062
Меньшие из них слева.

792
00:33:05,062 --> 00:33:06,270
Большие из них по праву.

793
00:33:06,270 --> 00:33:12,940
Такой, что истинное утверждение является
родитель превышает его левой ребенка,

794
00:33:12,940 --> 00:33:14,850
но меньше, чем его правой ребенка.

795
00:33:14,850 --> 00:33:17,750
И что в одиночку даже
рекурсивный словесное определение

796
00:33:17,750 --> 00:33:20,500
потому что вы можете применить, что
Та же самая логика для каждого узла

797
00:33:20,500 --> 00:33:23,080
И это только днища
вне, базовый вариант, если вам

798
00:33:23,080 --> 00:33:25,740
будет, когда вы нажмете одну из
листья, так сказать,

799
00:33:25,740 --> 00:33:28,580
где отпуск не имеет детей дальше.

800
00:33:28,580 --> 00:33:30,614
>> Теперь, как вы могли бы найти номер 44?

801
00:33:30,614 --> 00:33:32,280
Вы бы начать в корне и сказать, хм.

802
00:33:32,280 --> 00:33:35,690
55 не 44 Так что я хочу пойти
правильно или я хочу пойти налево?

803
00:33:35,690 --> 00:33:37,190
Ну, очевидно, вы хотите пойти налево.

804
00:33:37,190 --> 00:33:40,060
И так это просто, как телефон
Пример книга в бинарного поиска

805
00:33:40,060 --> 00:33:41,099
в целом.

806
00:33:41,099 --> 00:33:43,390
Но мы его реализации
Теперь немного более динамично

807
00:33:43,390 --> 00:33:45,339
чем массив может позволить.

808
00:33:45,339 --> 00:33:48,130
И в самом деле, если вы хотите посмотреть
на код, на первый взгляд, что.

809
00:33:48,130 --> 00:33:49,671
Похоже, целой кучей линий.

810
00:33:49,671 --> 00:33:51,220
Но это красиво просто.

811
00:33:51,220 --> 00:33:54,490
Если вы хотите реализовать функцию
называется поиск, цель которого в жизни

812
00:33:54,490 --> 00:33:57,290
является поиск значения
как п, целое число,

813
00:33:57,290 --> 00:34:01,756
и вы прошли в одной pointer--
указатель на узел корней,

814
00:34:01,756 --> 00:34:04,380
скорее, из этого дерева, из которого
Вы можете получить доступ все остальное,

815
00:34:04,380 --> 00:34:08,850
обратите внимание, как прямо
Вы можете реализовать логику.

816
00:34:08,850 --> 00:34:10,880
Если дерево является пустым,
Очевидно, что это не есть.

817
00:34:10,880 --> 00:34:11,880
Давайте просто вернуться ложным.

818
00:34:11,880 --> 00:34:12,000
Не так ли?

819
00:34:12,000 --> 00:34:14,040
Если вы не передать ему ничего,
там ничего нет.

820
00:34:14,040 --> 00:34:17,900
>> В противном случае, если п меньше
Дерево стрелки N-- теперь стрелка н,

821
00:34:17,900 --> 00:34:20,670
Напомним, мы ввели супер
кратко на днях,

822
00:34:20,670 --> 00:34:25,100
и это просто означает, де-ссылку на
указатель и посмотреть на месте, называемом н.

823
00:34:25,100 --> 00:34:27,690
Так это значит, пойти туда и
посмотреть на поле под названием п.

824
00:34:27,690 --> 00:34:33,810
Так что, если п, значение вы дали, меньше
чем значение в целое число деревьев,

825
00:34:33,810 --> 00:34:35,449
где вы хотите пойти?

826
00:34:35,449 --> 00:34:36,389
Налево.

827
00:34:36,389 --> 00:34:37,780
>> Так заметить рекурсию.

828
00:34:37,780 --> 00:34:39,860
Я returning-- не верно.

829
00:34:39,860 --> 00:34:40,989
Не ложь.

830
00:34:40,989 --> 00:34:45,670
Я возвращаюсь независимо ответ
от звонка в себя, проходя

831
00:34:45,670 --> 00:34:50,100
п снова, который является избыточным,
но то, что немного отличается теперь?

832
00:34:50,100 --> 00:34:51,989
Как я делаю проблему меньше?

833
00:34:51,989 --> 00:34:54,920
Я передаю в качестве второго
Аргумент, не корень дерева,

834
00:34:54,920 --> 00:34:59,616
но левая ребенок в этом случае.

835
00:34:59,616 --> 00:35:00,990
Так я передаю в левом ребенка.

836
00:35:00,990 --> 00:35:04,720
>> Между тем, если п больше, чем
узел В настоящее время я, глядя на,

837
00:35:04,720 --> 00:35:06,690
Я поиск правую сторону.

838
00:35:06,690 --> 00:35:10,880
В противном случае, если дерево не является нулевым, и
если элемент не влево

839
00:35:10,880 --> 00:35:13,240
и это не право,
что удивительно дело?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Мы фактически обнаружили узел в
Вопрос, а так мы возвращаемся верно.

842
00:35:18,440 --> 00:35:21,490
>> Так мы только поцарапали поверхность
Теперь некоторые из этих структур данных.

843
00:35:21,490 --> 00:35:24,370
В проблема установить пять вы будете
исследовать эти еще дальше,

844
00:35:24,370 --> 00:35:27,250
и вам будет предоставлена ​​ваш дизайн
Выбор, как идти об этом.

845
00:35:27,250 --> 00:35:30,250
То, что я хотел бы завершить на
это просто второй тизер 30

846
00:35:30,250 --> 00:35:32,080
о том, что ждет на следующей неделе, и за его пределами.

847
00:35:32,080 --> 00:35:35,390
>> Как мы begin-- счастью вы могли бы
think-- наш переход медленно

848
00:35:35,390 --> 00:35:38,680
из мира C и ниже
Детали реализации уровня,

849
00:35:38,680 --> 00:35:42,090
в мире, в котором мы можем взять для
разумеющимся, что кто-то наконец-

850
00:35:42,090 --> 00:35:44,010
реализованы эти данные
сооружения для нас,

851
00:35:44,010 --> 00:35:47,570
и мы начнем понимать,
Реальный мир означает реализации

852
00:35:47,570 --> 00:35:50,560
программы веб-основе и
сайты в более общем

853
00:35:50,560 --> 00:35:52,910
а также очень безопасности
Последствия, которые мы только

854
00:35:52,910 --> 00:35:54,850
начали царапать поверхность.

855
00:35:54,850 --> 00:35:57,320
Вот что нас ждет
в ближайшие дни.

856
00:35:57,320 --> 00:36:00,480
>> [ВИДЕОВОСПРОИЗВЕДЕНИЕ]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -Он Пришел с сообщением,
с протоколом все свое.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Он пришел в мир жесток
брандмауэры, незаботливым маршрутизаторы,

861
00:36:30,894 --> 00:36:33,368
и опасности гораздо хуже, чем смерть.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Он быстро.

864
00:36:36,236 --> 00:36:37,980
Он сильный.

865
00:36:37,980 --> 00:36:42,830
Он TCP / IP, и у него есть свой адрес.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
«Воины Сети".

868
00:36:48,074 --> 00:36:49,660
[END ВИДЕОВОСПРОИЗВЕДЕНИЕ]

869
00:36:49,660 --> 00:36:50,910
DAVID Маланом: Coming следующей неделе.

870
00:36:50,910 --> 00:36:51,880
Мы будем видеть вас тогда.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[ВИДЕОВОСПРОИЗВЕДЕНИЕ]

873
00:36:56,060 --> 00:36:59,240
-А Теперь, "Глубокие мысли"
по Daven Фарнэме.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
Дэвид всегда начинается
лекции с "Хорошо".

876
00:37:05,820 --> 00:37:08,750
Почему не "Вот решение
на этой неделе проблемы набора "

877
00:37:08,750 --> 00:37:12,180
или "Мы даем все вы?"

878
00:37:12,180 --> 00:37:13,380
[Смеется]

879
00:37:13,380 --> 00:37:15,530
[END ВИДЕОВОСПРОИЗВЕДЕНИЕ]