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 відеовідтворення]