1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
ДАГ Lloyd: Так в CS50, мы рассмотрели
много различных структур данных,

3
00:00:08,300 --> 00:00:09,180
правильно?

4
00:00:09,180 --> 00:00:11,420
Мы видели массивы, и связано
списки, хэш-таблицы и,

5
00:00:11,420 --> 00:00:15,210
и пытается, стеки и очереди.

6
00:00:15,210 --> 00:00:17,579
Мы также узнаем немного
о деревьях и кучи,

7
00:00:17,579 --> 00:00:20,120
но на самом деле это всего лишь конец
тем, что вариации на тему.

8
00:00:20,120 --> 00:00:22,840
Там на самом деле это
вид из четырех основных идей

9
00:00:22,840 --> 00:00:25,190
что все еще может сводиться к.

10
00:00:25,190 --> 00:00:28,150
Массивы, связанные списки,
хэш-таблицы, и пытается.

11
00:00:28,150 --> 00:00:30,720
И, как я уже сказал,
вариации на них,

12
00:00:30,720 --> 00:00:32,720
но это довольно
много происходит обобщить

13
00:00:32,720 --> 00:00:38,140
все, что мы будем говорить
о в этом классе с точки зрения С.

14
00:00:38,140 --> 00:00:40,140
>> Но как сделать это все мерой, верно?

15
00:00:40,140 --> 00:00:44,265
Мы говорили о плюсах и минусах
каждого из них в отдельных видео на них,

16
00:00:44,265 --> 00:00:46,390
но есть много цифр
получать бросил вокруг.

17
00:00:46,390 --> 00:00:48,723
Там очень много общего
мысли получать разбросаны.

18
00:00:48,723 --> 00:00:51,950
Давайте попробуем и консолидации
это в одном месте.

19
00:00:51,950 --> 00:00:55,507
Давайте взвешивать плюсы от
минусы, и рассмотреть

20
00:00:55,507 --> 00:00:57,340
в состав которого данные
может быть правильным данных

21
00:00:57,340 --> 00:01:01,440
структура вашей конкретной ситуации,
независимо от вида данных, которые вы хранения.

22
00:01:01,440 --> 00:01:06,625
Вам не обязательно всегда должны
использовать сверхбыструю вставки, удаления,

23
00:01:06,625 --> 00:01:10,761
и поиск из синтаксического дерева, если вы действительно
не заботятся о вставки и удаления

24
00:01:10,761 --> 00:01:11,260
слишком.

25
00:01:11,260 --> 00:01:13,968
Если вам нужно просто быстро случайных
доступа, может быть, массив, тем лучше.

26
00:01:13,968 --> 00:01:15,340
Итак, давайте перегонять, что.

27
00:01:15,340 --> 00:01:18,530
Давайте поговорим о каждом из четырех
основных вида структур данных

28
00:01:18,530 --> 00:01:21,720
что мы говорили, и
просто видеть, когда они могли бы быть хорошо,

29
00:01:21,720 --> 00:01:23,340
и когда они не могут быть так хорошо.

30
00:01:23,340 --> 00:01:24,610
Итак, давайте начнем с массивами.

31
00:01:24,610 --> 00:01:27,300
Так вставки, это своего рода плохо.

32
00:01:27,300 --> 00:01:31,350
>> Вносимые в конце массива в порядке,
если мы строим массив, как мы идем.

33
00:01:31,350 --> 00:01:33,570
Но если нам нужно вставить
элементы в середине,

34
00:01:33,570 --> 00:01:35,550
вспомните вставки
сортировать, есть много

35
00:01:35,550 --> 00:01:37,510
сдвига, чтобы соответствовать элемент там.

36
00:01:37,510 --> 00:01:41,170
И поэтому, если мы собираемся, чтобы вставить
где угодно, но в конце массива,

37
00:01:41,170 --> 00:01:43,590
это, наверное, не так уж велика.

38
00:01:43,590 --> 00:01:46,710
>> Аналогично, удаление, если мы не
удаление с конца массива,

39
00:01:46,710 --> 00:01:49,810
это, вероятно, также не так здорово, если
мы не хотим, чтобы оставить пустые пробелы,

40
00:01:49,810 --> 00:01:50,790
которые обычно мы не делаем.

41
00:01:50,790 --> 00:01:54,700
Мы хотим, чтобы удалить элемент, и
потом вроде сделать это уютно снова.

42
00:01:54,700 --> 00:01:57,670
И так удаления элементов из
массив, а также не столь велика.

43
00:01:57,670 --> 00:01:58,820
>> Поиск, однако, это здорово.

44
00:01:58,820 --> 00:02:00,920
У нас есть произвольный доступ,
постоянная времени поиска.

45
00:02:00,920 --> 00:02:03,800
Мы просто скажем, семь, и мы идем
массиву переселения семь.

46
00:02:03,800 --> 00:02:05,907
Мы говорим 20, с ходу в
Массив переселение 20.

47
00:02:05,907 --> 00:02:07,240
Мы не должны повторять через.

48
00:02:07,240 --> 00:02:08,630
Это очень хорошо.

49
00:02:08,630 --> 00:02:11,020
>> Массивы также относительно легко сортировать.

50
00:02:11,020 --> 00:02:14,040
Каждый раз, когда мы говорили о сортировке
Алгоритм, таких как выбор вида,

51
00:02:14,040 --> 00:02:18,820
сортировка вставками, пузырьковая сортировка, слияние
сортировать, мы всегда использовали массивы, чтобы сделать это,

52
00:02:18,820 --> 00:02:21,860
потому что массивы довольно легко
рода, по отношению к структурам данных

53
00:02:21,860 --> 00:02:22,970
мы видели до сих пор.

54
00:02:22,970 --> 00:02:24,320
>> Они также относительно невелик.

55
00:02:24,320 --> 00:02:25,695
Там не так много дополнительного пространства.

56
00:02:25,695 --> 00:02:29,210
Вы просто отложите ровно столько
как вам нужно, чтобы держать ваши данные,

57
00:02:29,210 --> 00:02:30,320
и это довольно много его.

58
00:02:30,320 --> 00:02:33,180
Так они довольно малы
и эффективной таким образом.

59
00:02:33,180 --> 00:02:36,000
Но другой недостаток, хотя,
является то, что они не будут устранены в размере.

60
00:02:36,000 --> 00:02:38,630
Мы должны объявить, как именно
большой, мы хотим наш массив, чтобы быть,

61
00:02:38,630 --> 00:02:39,940
и мы только один выстрел на него.

62
00:02:39,940 --> 00:02:41,280
Мы не можем расти и сжать его.

63
00:02:41,280 --> 00:02:44,582
>> Если мы должны расти или сжать его, мы
нужно объявить совершенно новый массив,

64
00:02:44,582 --> 00:02:47,750
скопировать все элементы
Первый массив во второй массив.

65
00:02:47,750 --> 00:02:51,410
И если мы просчитались, что
раз мы должны сделать это снова.

66
00:02:51,410 --> 00:02:52,760
Не так здорово.

67
00:02:52,760 --> 00:02:58,750
Так массивы не дают нам гибкость
чтобы иметь переменное количество элементов.

68
00:02:58,750 --> 00:03:01,320
>> С связанного списка,
вставка довольно легко.

69
00:03:01,320 --> 00:03:03,290
Мы просто лавировать на фронте.

70
00:03:03,290 --> 00:03:04,892
Удаление также довольно легко.

71
00:03:04,892 --> 00:03:06,100
Мы должны найти элементы.

72
00:03:06,100 --> 00:03:07,270
Это включает некоторый поиск.

73
00:03:07,270 --> 00:03:10,270
>> Но как только вы нашли элемент
Вы ищете, все, что вам нужно сделать,

74
00:03:10,270 --> 00:03:12,830
это изменить указатель,
возможно два, если у вас есть

75
00:03:12,830 --> 00:03:15,151
связанный list-- вдвойне
Связанный список, rather--

76
00:03:15,151 --> 00:03:16,650
и тогда вы можете просто освободить узел.

77
00:03:16,650 --> 00:03:18,399
Вы не должны перекладывать
все вокруг.

78
00:03:18,399 --> 00:03:22,090
Вы просто изменить два указателя,
так что это довольно быстро.

79
00:03:22,090 --> 00:03:23,470
>> Поиск плохо, верно?

80
00:03:23,470 --> 00:03:26,280
Для того, чтобы нам найти
элемент связанного списка,

81
00:03:26,280 --> 00:03:29,154
ли по отдельности или двойной связью,
мы должны искать его линейным.

82
00:03:29,154 --> 00:03:32,320
Мы должны начать с самого начала и
переместить конец, или начать в конце хода

83
00:03:32,320 --> 00:03:33,860
к началу.

84
00:03:33,860 --> 00:03:35,474
Мы не имеем произвольный доступ больше.

85
00:03:35,474 --> 00:03:37,265
Так что, если мы делаем
Много поиска, может быть,

86
00:03:37,265 --> 00:03:39,830
связанный список не является
совсем так хорошо для нас.

87
00:03:39,830 --> 00:03:43,750
>> Они также очень
трудно разобраться, не так ли?

88
00:03:43,750 --> 00:03:45,666
Единственный способ вы можете
действительно сортировки связанного списка

89
00:03:45,666 --> 00:03:47,870
для сортировки его, как вы построить его.

90
00:03:47,870 --> 00:03:50,497
Но если вы сортировать его, как вы
не построить его, вы больше не

91
00:03:50,497 --> 00:03:51,830
принятия быстрых вставок больше.

92
00:03:51,830 --> 00:03:53,746
Вы не просто лавировать
вещи на фронт.

93
00:03:53,746 --> 00:03:55,710
Вы должны найти
правильное место, чтобы положить его,

94
00:03:55,710 --> 00:03:57,820
и тогда ваш вставки
становится почти так же плохо

95
00:03:57,820 --> 00:03:59,390
как вставка в массив.

96
00:03:59,390 --> 00:04:03,130
Так связанные списки не
так здорово для сортировки данных.

97
00:04:03,130 --> 00:04:05,830
>> Они также довольно небольшой, размер-мудрый.

98
00:04:05,830 --> 00:04:08,496
Двунаправленный список немного
больше, чем по отдельности, связанных списков,

99
00:04:08,496 --> 00:04:10,620
который немного больше
по сравнению с массивами, но это не

100
00:04:10,620 --> 00:04:13,330
огромное количество неиспользуемого пространства.

101
00:04:13,330 --> 00:04:18,730
Так что, если пространство в большом почете, но
не очень интенсивным премиум,

102
00:04:18,730 --> 00:04:22,180
это может быть правильный путь.

103
00:04:22,180 --> 00:04:23,330
>> Хэш-таблицы.

104
00:04:23,330 --> 00:04:25,850
Вносимые в хэш-таблице
довольно проста.

105
00:04:25,850 --> 00:04:26,980
Это двухступенчатый процесс.

106
00:04:26,980 --> 00:04:30,700
Во-первых, мы должны запустить наши данные через
хэш-функция, чтобы получить хэш-код,

107
00:04:30,700 --> 00:04:37,550
а затем вставляем элемент в
хеш-таблица в этой хэш-код расположения.

108
00:04:37,550 --> 00:04:40,879
>> Удаление, подобно связанного списка,
легко, как только вы найдете элемент.

109
00:04:40,879 --> 00:04:43,170
Вы должны найти его первым,
но потом, когда вы удалите его,

110
00:04:43,170 --> 00:04:45,128
вам просто нужно обменять
пару указателей,

111
00:04:45,128 --> 00:04:47,250
если вы используете отдельный цепочки.

112
00:04:47,250 --> 00:04:49,942
Если вы используете зондирования,
или если вы не

113
00:04:49,942 --> 00:04:51,650
с помощью цепочки на всех
в хеш-таблицы,

114
00:04:51,650 --> 00:04:53,040
удаление на самом деле очень просто.

115
00:04:53,040 --> 00:04:57,134
Все, что вам нужно сделать, это хеш
Данные, а затем перейти к этому месту.

116
00:04:57,134 --> 00:04:58,925
И если вы не
есть какие-либо столкновений,

117
00:04:58,925 --> 00:05:01,650
Вы сможете удалить очень быстро.

118
00:05:01,650 --> 00:05:04,930
>> Теперь, поиск, где вещи
получить немного сложнее.

119
00:05:04,930 --> 00:05:06,910
Это в среднем лучше,
чем связанные списки.

120
00:05:06,910 --> 00:05:09,560
Если вы используете цепочки,
Вы все еще есть связанный список,

121
00:05:09,560 --> 00:05:13,170
который означает, что вы по-прежнему имеют
Поиск ущерб связанный список.

122
00:05:13,170 --> 00:05:18,390
Но потому, что вы принимать ваши связано
Перечень и разделения его на 100 или 1000

123
00:05:18,390 --> 00:05:25,380
или п элементов в вашей хэш-таблицы, вы
связанные списки все одно п-размера.

124
00:05:25,380 --> 00:05:27,650
Они все значительно меньше.

125
00:05:27,650 --> 00:05:32,080
Вы н связанные списки вместо
одного связанного списка размера п.

126
00:05:32,080 --> 00:05:34,960
>> И так постоянная этот реальный
фактор, который мы обычно

127
00:05:34,960 --> 00:05:39,730
не говорить о сложности времени, его
действительно фактически сделать разницу здесь.

128
00:05:39,730 --> 00:05:43,020
Так поиск по-прежнему линейный
поиск, если вы используете цепочки,

129
00:05:43,020 --> 00:05:46,780
но длина списка
Вы ищете через

130
00:05:46,780 --> 00:05:50,080
очень, очень короткий в сравнении.

131
00:05:50,080 --> 00:05:52,995
Опять же, если это ваши сортировка
Цель здесь, хэш таблицы

132
00:05:52,995 --> 00:05:54,370
вероятно, не правильный путь.

133
00:05:54,370 --> 00:05:56,830
Просто используйте массив, если сортировка
это действительно важно для вас.

134
00:05:56,830 --> 00:05:58,590
>> И они могут запустить гамму размеров.

135
00:05:58,590 --> 00:06:01,640
Трудно сказать, является ли
хеш-таблица является маленький или большой,

136
00:06:01,640 --> 00:06:04,110
потому что это действительно зависит от
насколько велик ваш хэш таблицы.

137
00:06:04,110 --> 00:06:07,340
Если вы только собираетесь быть хранения
пять элементов в вашем хэш-таблицы,

138
00:06:07,340 --> 00:06:10,620
и у вас есть хэш-таблицу
10000 элементов в нем,

139
00:06:10,620 --> 00:06:12,614
вы, вероятно, тратить много места.

140
00:06:12,614 --> 00:06:15,030
Контраст быть Вы также можете
есть очень компактные хэш-таблицы,

141
00:06:15,030 --> 00:06:18,720
но меньше ваша хэш-таблица получает,
чем больше каждый из этих связанных списков

142
00:06:18,720 --> 00:06:19,220
получает.

143
00:06:19,220 --> 00:06:22,607
И поэтому на самом деле нет способа определить
точно размер хеш-таблицы,

144
00:06:22,607 --> 00:06:24,440
но это, вероятно, безопасно
сказать это вообще

145
00:06:24,440 --> 00:06:27,990
будет больше, чем связанный
Список хранения те же данные,

146
00:06:27,990 --> 00:06:30,400
но меньше, чем синтаксического дерева.

147
00:06:30,400 --> 00:06:32,720
>> И пытается это четвертый
из этих структур

148
00:06:32,720 --> 00:06:34,070
что мы говорим о.

149
00:06:34,070 --> 00:06:36,450
Вставка в синтаксического дерева является сложным.

150
00:06:36,450 --> 00:06:38,400
Там очень много динамических
выделение памяти,

151
00:06:38,400 --> 00:06:40,780
особенно в начале,
а вы начинаете строить.

152
00:06:40,780 --> 00:06:43,700
Но это постоянная времени.

153
00:06:43,700 --> 00:06:47,690
Это только человеческий фактор
вот что делает его сложным.

154
00:06:47,690 --> 00:06:53,250
Имея столкнуться нулевой указатель, таНос
пространство, туда, возможно, таНос пространство

155
00:06:53,250 --> 00:06:54,490
оттуда снова.

156
00:06:54,490 --> 00:06:58,880
Своего рода запугивания фактор
указатели в динамическом распределении памяти

157
00:06:58,880 --> 00:07:00,130
является препятствием, чтобы очистить.

158
00:07:00,130 --> 00:07:04,550
Но как только вы очистили его, вставка
на самом деле происходит довольно просто,

159
00:07:04,550 --> 00:07:06,810
и это, конечно, постоянная времени.

160
00:07:06,810 --> 00:07:07,680
>> Удаление легко.

161
00:07:07,680 --> 00:07:11,330
Все, что вам нужно сделать, это перейти вниз
пара указателей и бесплатным узла,

162
00:07:11,330 --> 00:07:12,420
так что это довольно хорошо.

163
00:07:12,420 --> 00:07:13,930
Поиск также довольно быстро.

164
00:07:13,930 --> 00:07:16,780
Это только на основе
длина ваших данных.

165
00:07:16,780 --> 00:07:19,924
Так что, если все ваши данные в
пять символов строки,

166
00:07:19,924 --> 00:07:22,590
Например, вы храните пять
символьные строки в Вашей синтаксического дерева,

167
00:07:22,590 --> 00:07:25,439
это займет всего пять шагов к
найти то, что вы ищете.

168
00:07:25,439 --> 00:07:28,480
Пять просто постоянным фактором, так
снова, вставка, удаление, поиск и

169
00:07:28,480 --> 00:07:31,670
здесь все время постоянной, эффективно.

170
00:07:31,670 --> 00:07:34,880
>> Другое дело, что ваш Trie является
на самом деле вид уже отсортированы, верно?

171
00:07:34,880 --> 00:07:36,800
В силу того, как мы
вставка элементов,

172
00:07:36,800 --> 00:07:40,060
перейдя по буквам из
Ключ, или цифра за цифрой ключа,

173
00:07:40,060 --> 00:07:45,084
обычно, на ваш Trie заканчивается время
вид сортируются, как вы строите его.

174
00:07:45,084 --> 00:07:47,250
Это на самом деле не делает
смысл подумать о сортировке

175
00:07:47,250 --> 00:07:49,874
таким же образом, мы думаем о
это с массивами, или связанные списки,

176
00:07:49,874 --> 00:07:51,070
или хэш-таблицы.

177
00:07:51,070 --> 00:07:54,780
Но в каком-то смысле, ваш
Trie сортируется, как вы идете.

178
00:07:54,780 --> 00:07:58,630
>> Недостатком, конечно, является то, что
Trie быстро становится огромным.

179
00:07:58,630 --> 00:08:02,970
Из каждой точки перехода, вы можете
have-- если ваш ключ состоит из цифр,

180
00:08:02,970 --> 00:08:04,880
у вас есть 10 других
места, которые вы можете пойти, что

181
00:08:04,880 --> 00:08:07,490
означает, что каждый узел
содержит информацию

182
00:08:07,490 --> 00:08:11,440
о данных, которые вы хотите сохранить
в этом узле, плюс 10 указателей.

183
00:08:11,440 --> 00:08:14,430
Что, по CS50 IDE, 80 байт.

184
00:08:14,430 --> 00:08:17,220
Так что, по крайней мере 80 байта для
каждый узел, который вы создаете,

185
00:08:17,220 --> 00:08:19,240
и это даже не считая данных.

186
00:08:19,240 --> 00:08:24,950
И если ваши узлы
письма вместо цифр,

187
00:08:24,950 --> 00:08:27,825
теперь у вас есть 26 указателей
от каждого места.

188
00:08:27,825 --> 00:08:32,007
И 26 раз 8, вероятно, 200
байт, или что-то подобное.

189
00:08:32,007 --> 00:08:33,840
А у вас есть капитал
и lowercase-- вы можете

190
00:08:33,840 --> 00:08:35,381
увидеть, где я собираюсь с этим, верно?

191
00:08:35,381 --> 00:08:37,500
Ваши узлы могут получить действительно
большой, и поэтому Trie

192
00:08:37,500 --> 00:08:40,470
Сам, в целом, может
получить действительно большой, слишком.

193
00:08:40,470 --> 00:08:42,630
Так что, если пространство на высоком
премия по вашей системе,

194
00:08:42,630 --> 00:08:45,830
Trie не может быть правильным способом
идти, даже если другие его преимущества

195
00:08:45,830 --> 00:08:47,780
вступают в игру.

196
00:08:47,780 --> 00:08:48,710
Я Дуг Ллойд.

197
00:08:48,710 --> 00:08:50,740
Это CS50.

198
00:08:50,740 --> 00:08:52,316