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