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

2
00:00:00,500 --> 00:00:03,340
[MUZYKA GRY]

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

4
00:00:11,020 --> 00:00:14,010
>> DAVID MALAN: To CS50.

5
00:00:14,010 --> 00:00:18,090
I to zarówno początek i
end-- jak literally-- prawie koniec

6
00:00:18,090 --> 00:00:18,825
od sześciu tygodni.

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

8
00:00:20,030 --> 00:00:22,640
>> Pomyślałem, że podzielę
Trochę zabawy rzeczywistości.

9
00:00:22,640 --> 00:00:25,370
Mam wyciągnął z tego się
zbiór danych minionego semestru.

10
00:00:25,370 --> 00:00:29,710
Można przypomnieć, że poprosi o co
str forma zestaw jeśli Widziałem w Internecie

11
00:00:29,710 --> 00:00:31,580
lub jeśli już udział osobiście.

12
00:00:31,580 --> 00:00:33,020
A oto dane.

13
00:00:33,020 --> 00:00:34,710
Więc dzisiaj był bardzo przewidywalny.

14
00:00:34,710 --> 00:00:37,126
Ale chcieliśmy spędzić trochę
czasu z tobą jednak.

15
00:00:37,126 --> 00:00:40,599
Czy ktoś chciałby się domyślić, dlaczego
Wykres jest tak chropawy, w górę w dół, w górę w dół,

16
00:00:40,599 --> 00:00:41,265
tak konsekwentnie?

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

18
00:00:42,980 --> 00:00:45,130
Co każdy z wierzchołków
i koryta reprezentacji?

19
00:00:45,130 --> 00:00:46,005
>> PUBLICZNOŚCI: [niesłyszalne]

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

21
00:00:47,002 --> 00:00:47,835
DAVID MALAN: Rzeczywiście.

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

23
00:00:50,900 --> 00:00:55,480
I bardziej zabawnie, nie daj Boże,
posiadamy jeden wykład w piątek

24
00:00:55,480 --> 00:00:58,960
na początku semestru,
że to, co widzimy, dzieje.

25
00:00:58,960 --> 00:01:03,430
Więc dzisiaj, uczestniczymy w nieco
więcej o strukturach danych.

26
00:01:03,430 --> 00:01:06,660
I dać więcej stałe
Model mentalny problemów w pięciu,

27
00:01:06,660 --> 00:01:07,450
co jest teraz na zewnątrz.

28
00:01:07,450 --> 00:01:10,817
Błędy ortograficzne, w którym, będziemy
wręczyć ci plik tekstowy 100,000

29
00:01:10,817 --> 00:01:12,650
oraz angielskie słowa i
będziesz mieć

30
00:01:12,650 --> 00:01:17,770
aby dowiedzieć się, jak sprytnie je załadować
do pamięci do pamięci RAM, używając pewnych danych

31
00:01:17,770 --> 00:01:19,330
Struktura wyboru.

32
00:01:19,330 --> 00:01:22,470
>> Teraz jedna taka struktura danych może
być, ale prawdopodobnie nie powinien być

33
00:01:22,470 --> 00:01:25,630
dość uproszczona lista powiązana,
które wprowadziliśmy ostatnio.

34
00:01:25,630 --> 00:01:29,220
I powiązana lista miał co najmniej
jedną przewagę nad tablicą.

35
00:01:29,220 --> 00:01:32,096
Co jest jedną z zalet
powiązane lista zapewne?

36
00:01:32,096 --> 00:01:32,950
>> Publiczność: Insertion.

37
00:01:32,950 --> 00:01:33,908
>> DAVID MALAN: Insertion.

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

39
00:01:34,155 --> 00:01:35,196
Co masz na myśli?

40
00:01:35,196 --> 00:01:37,872
>> Publiczność: Wszędzie razem
Lista [niesłyszalne].

41
00:01:37,872 --> 00:01:38,770
>> DAVID MALAN: Dobra.

42
00:01:38,770 --> 00:01:42,090
Więc można wstawić element w miarę
chcesz w środku listy

43
00:01:42,090 --> 00:01:45,490
bez shuffle niczego,
które zawarliśmy w naszym sortowania

44
00:01:45,490 --> 00:01:47,630
dyskusje, nie jest
zawsze dobra rzecz,

45
00:01:47,630 --> 00:01:51,200
bo na to potrzeba czasu, aby rzeczywiście przenieść
wszystkich tych ludzi w lewo lub w prawo.

46
00:01:51,200 --> 00:01:55,540
I tak z połączonej listy, można
po prostu przeznaczyć z malloc, nowy węzeł,

47
00:01:55,540 --> 00:01:58,385
a następnie zaktualizować kilka
pointers-- dwa, trzy operacje max--

48
00:01:58,385 --> 00:02:01,480
i jesteśmy w stanie rozciąć kogoś
w dowolnym miejscu na liście.

49
00:02:01,480 --> 00:02:03,550
>> Co jeszcze było korzystne
o połączonej listy?

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

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

52
00:02:05,659 --> 00:02:06,534
>> PUBLICZNOŚCI: [niesłyszalne]

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

54
00:02:07,538 --> 00:02:08,413
DAVID MALAN: Idealny.

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

56
00:02:10,590 --> 00:02:11,090
Doskonały.

57
00:02:11,090 --> 00:02:12,070
To bardzo dynamiczna.

58
00:02:12,070 --> 00:02:15,100
I że nie jesteś popełnienia,
z góry, do pewnego stałego rozmiaru

59
00:02:15,100 --> 00:02:18,750
kawałek pamięci, jak trzeba
się z tablicy, w której pozytywnie

60
00:02:18,750 --> 00:02:22,455
jest to, że można przeznaczyć tylko na węzłach
Popyt ten sposób przy użyciu tylko tyle miejsca

61
00:02:22,455 --> 00:02:23,330
jak rzeczywiście trzeba.

62
00:02:23,330 --> 00:02:26,830
W przeciwieństwie do tablicy, to polubisz
przypadkowo przeznaczyć zbyt mało.

63
00:02:26,830 --> 00:02:28,871
A potem to tylko będzie
się ból w szyi

64
00:02:28,871 --> 00:02:32,440
realokacji nowy większy wachlarz, kopiowanie
wszystko skończy, uwolnić starą tablicę,

65
00:02:32,440 --> 00:02:33,990
a następnie przenieść na temat swojej działalności.

66
00:02:33,990 --> 00:02:37,479
Albo, co gorsza, może przeznaczyć sposób
więcej pamięci, niż faktycznie potrzebujemy,

67
00:02:37,479 --> 00:02:40,520
i tak będziesz mieć bardzo
słabo zaludnionych tablicy, że tak powiem.

68
00:02:40,520 --> 00:02:44,350
>> Tak powiązana lista daje te
Korzyści z dynamiką i elastycznością

69
00:02:44,350 --> 00:02:46,080
z wstawkami i skreśleń.

70
00:02:46,080 --> 00:02:48,000
Ale na pewno nie może być zapłacona cena.

71
00:02:48,000 --> 00:02:50,000
W istocie, jednym z motywów
zbadane w quizie zera

72
00:02:50,000 --> 00:02:52,430
było kilka kompromisy
widzieliśmy do tej pory.

73
00:02:52,430 --> 00:02:56,161
Więc co jest cena zapłacona lub
Minusem połączonej listy?

74
00:02:56,161 --> 00:02:56,660
Tak.

75
00:02:56,660 --> 00:02:57,560
>> Publiczność: Nie o dostępie swobodnym.

76
00:02:57,560 --> 00:02:58,809
>> DAVID MALAN: Nie o dostępie swobodnym.

77
00:02:58,809 --> 00:02:59,540
Ale kogo to obchodzi?

78
00:02:59,540 --> 00:03:01,546
O dostępie swobodnym nie brzmi atrakcyjnie.

79
00:03:01,546 --> 00:03:02,421
>> PUBLICZNOŚCI: [niesłyszalne]

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

81
00:03:04,865 --> 00:03:05,740
DAVID MALAN: Dokładnie.

82
00:03:05,740 --> 00:03:07,580
Jeśli chcesz mieć
pewne algorithm--

83
00:03:07,580 --> 00:03:10,170
i pozwól mi faktycznie proponują
przeszukiwanie binarne w szczególności, co

84
00:03:10,170 --> 00:03:12,600
jest jednym używaliśmy dość bit--
jeśli nie ma swobodnego dostępu,

85
00:03:12,600 --> 00:03:15,516
nie można zrobić, że prostych działań arytmetycznych
znalezienia jak elementu środkowego

86
00:03:15,516 --> 00:03:16,530
i skoki do niego prawo.

87
00:03:16,530 --> 00:03:20,239
Zamiast tego zacząć w pierwszym
elementem i liniowo od lewej wyszukiwania

88
00:03:20,239 --> 00:03:22,780
do prawej, jeśli chcesz znaleźć
średniej lub jakikolwiek inny element.

89
00:03:22,780 --> 00:03:24,410
>> Publiczność: Prawdopodobnie ma więcej pamięci.

90
00:03:24,410 --> 00:03:25,040
>> DAVID MALAN: zajmuje więcej pamięci.

91
00:03:25,040 --> 00:03:27,464
Gdzie jest, że dodatkowe
kosztować pochodzących z pamięci?

92
00:03:27,464 --> 00:03:28,339
>> PUBLICZNOŚCI: [niesłyszalne]

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

94
00:03:32,566 --> 00:03:33,440
DAVID MALAN: Dokładnie.

95
00:03:33,440 --> 00:03:35,679
W tym przypadku tutaj, mieliśmy
powiązane lista dla liczb całkowitych,

96
00:03:35,679 --> 00:03:37,470
i jeszcze mamy podwojenie
Ilość pamięci

97
00:03:37,470 --> 00:03:39,680
musimy również poprzez przechowywanie tych wskazówek.

98
00:03:39,680 --> 00:03:42,090
Teraz mniej wielkiego jak
Twoje structury się większe

99
00:03:42,090 --> 00:03:45,320
a ty przechowywania, ale nie wiele
Może student lub inny obiekt.

100
00:03:45,320 --> 00:03:46,880
Ale chodzi oczywiście pozostaje.

101
00:03:46,880 --> 00:03:49,421
A więc liczba operacji
na list nazywano powiązanych

102
00:03:49,421 --> 00:03:50,570
były duże O z n-- liniowych.

103
00:03:50,570 --> 00:03:54,730
Rzeczy takie jak wkładanie i wyszukiwania
lub usunięcie w przypadku elementu

104
00:03:54,730 --> 00:03:57,720
stało się na samym końcu
lista czy to sortowane, czy nie.

105
00:03:57,720 --> 00:04:01,167
>> Czasami może będziesz miał szczęście i
tak dolne granice tych operacji

106
00:04:01,167 --> 00:04:04,250
może być również stała czasowa, jeśli jesteś
Zawsze patrząc na pierwszy element,

107
00:04:04,250 --> 00:04:05,070
na przykład.

108
00:04:05,070 --> 00:04:09,360
Ale ostatecznie, obiecaliśmy
do osiągnięcia Świętego Graala

109
00:04:09,360 --> 00:04:12,630
struktur danych, lub
niektóre ich przybliżenie,

110
00:04:12,630 --> 00:04:14,290
na zasadzie stałym czasie.

111
00:04:14,290 --> 00:04:17,579
Możemy znaleźć elementy lub dodać elementy
lub usunąć elementy z listy?

112
00:04:17,579 --> 00:04:19,059
Przekonamy się już wkrótce.

113
00:04:19,059 --> 00:04:21,100
I okazuje się, że jeden
mechanizmów których jesteśmy

114
00:04:21,100 --> 00:04:23,464
zamiar zacząć korzystać z dzisiaj,
roczne zużycie w punkcie ustawić pięć,

115
00:04:23,464 --> 00:04:24,630
jest rzeczywiście bardzo znajomo.

116
00:04:24,630 --> 00:04:27,430
Na przykład, jeśli jest to kilka
książek egzaminacyjnych, z których każda

117
00:04:27,430 --> 00:04:29,660
ma pierwszy studenta
Imię i nazwisko na nim,

118
00:04:29,660 --> 00:04:31,820
a ja je odebrać ze
Na koniec egzaminu,

119
00:04:31,820 --> 00:04:33,746
i wszystkie są dość
wiele w kolejności losowej

120
00:04:33,746 --> 00:04:36,370
i chcemy go o sortowaniu
Egzaminy te klasyfikowane tak, że raz

121
00:04:36,370 --> 00:04:38,661
to jest po prostu o wiele łatwiej i
szybciej oddać je z powrotem

122
00:04:38,661 --> 00:04:40,030
studentów alfabetycznie.

123
00:04:40,030 --> 00:04:42,770
Co by twoje instynkty się
na stos egzaminów takich jak ten?

124
00:04:42,770 --> 00:04:45,019
>> Cóż, jeśli jesteś podobny do mnie,
można zobaczyć, że jest to m,

125
00:04:45,019 --> 00:04:48,505
więc mam zamiar jakby umieścić to pod,
jeśli to jest mój stół lub podłoga, gdzie mój

126
00:04:48,505 --> 00:04:50,650
Jestem rozprzestrzeniania rzeczy
out-- lub moja tablica really--

127
00:04:50,650 --> 00:04:52,210
Mogę umieścić wszystkie Ms tam.

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

129
00:04:52,710 --> 00:04:55,020
Oto A. Więc mógłbym
umieścić jako tutaj.

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

131
00:04:55,520 --> 00:04:57,980
Oto kolejny A. Zamierzam
umieścić to tutaj.

132
00:04:57,980 --> 00:05:02,490
Oto Z. Oto kolejny M. I tak
Mógłbym zacząć pali jak ten.

133
00:05:02,490 --> 00:05:06,620
A potem może pójdę na później
i rodzaj bardzo nitpicky-ly sortowania

134
00:05:06,620 --> 00:05:07,710
poszczególne pale.

135
00:05:07,710 --> 00:05:11,300
Ale chodzi o to, będę szukać
na wejściu, że jestem ręką

136
00:05:11,300 --> 00:05:14,016
i chciałbym, aby niektóre obliczane
Decyzja opiera się na tym wejściu.

137
00:05:14,016 --> 00:05:15,640
Jeśli zaczyna się, umieścić go tam.

138
00:05:15,640 --> 00:05:18,980
Jeżeli zaczyna się na Z, umieścić go na
nie, i wszystko pomiędzy.

139
00:05:18,980 --> 00:05:22,730
>> Więc jest to technika, która jest
ogólnie znane jako hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
co generalnie oznacza, przyjmując jako
wejściowy i za pomocą tego wejścia do obliczenia

141
00:05:26,550 --> 00:05:30,940
wartości, na ogół ilość, i że
liczba to indeks do przechowywania

142
00:05:30,940 --> 00:05:32,260
pojemnik, jak tablicy.

143
00:05:32,260 --> 00:05:35,490
Więc innymi słowy, może mam
funkcja skrótu, tak jak ja w mojej głowie,

144
00:05:35,490 --> 00:05:37,940
Widzę, że jeśli ktoś jest
Nazwa, która zaczyna się od A,

145
00:05:37,940 --> 00:05:40,190
Idę do map, które
do zera w mojej głowie.

146
00:05:40,190 --> 00:05:44,160
A jeśli widzę kogoś z Z, jestem
map, które będą do 25 w mojej głowie

147
00:05:44,160 --> 00:05:46,220
a następnie umieścić, że w
ostatnia najbardziej stos.

148
00:05:46,220 --> 00:05:50,990
>> Teraz, jeśli myślisz o mój mózg nie
ale program C, jakie numery mógł

149
00:05:50,990 --> 00:05:53,170
można liczyć na osiągnięcie tego samego rezultatu?

150
00:05:53,170 --> 00:05:55,594
Innymi słowy, jeśli
miał ASCII charakterem,

151
00:05:55,594 --> 00:05:57,510
jak można określić,
co wiadro, aby umieścić go w?

152
00:05:57,510 --> 00:05:59,801
Prawdopodobnie nie chcesz
umieścić go w wiadrze 65, które

153
00:05:59,801 --> 00:06:01,840
będzie jak tam
bez powodu.

154
00:06:01,840 --> 00:06:04,320
Gdzie chcesz umieścić
pod względem jego wartości ASCII?

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

156
00:06:05,600 --> 00:06:08,920
W przypadku, gdy chcesz zrobić na jego ASCII
Wartość wymyślić sprytniejszy wiadra

157
00:06:08,920 --> 00:06:09,480
umieścić go w?

158
00:06:09,480 --> 00:06:10,206
>> Publiczność: Minus A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID MALAN: Tak.

160
00:06:10,956 --> 00:06:13,190
Więc minus lub minus
szczególnie jeśli jest to 65

161
00:06:13,190 --> 00:06:18,240
A. Kapitał Albo 98, jeśli
to małe.

162
00:06:18,240 --> 00:06:21,300
I tak, że pozwoli nam, bardzo
po prostu i bardzo arytmetycznie,

163
00:06:21,300 --> 00:06:23,260
umieścić coś do wiadra takiego.

164
00:06:23,260 --> 00:06:26,010
Tak więc okazuje się, że faktycznie
to jak dobrze nawet z quizów.

165
00:06:26,010 --> 00:06:29,051
>> Więc może przypomnieć ci okrążył swoje
Nazwa ucząc znajduje się na okładce.

166
00:06:29,051 --> 00:06:32,270
I nazwy TF zostały zorganizowane
w tych kolumnach alfabetycznie

167
00:06:32,270 --> 00:06:34,400
dobrze, wierzcie lub nie,
kiedy wszystko nas 80 plus

168
00:06:34,400 --> 00:06:37,800
zebrali nocy do klasy,
ostatni krok w naszym procesie klasyfikacji

169
00:06:37,800 --> 00:06:41,830
jest do mieszania quizy na duże
przestrzeń na podłodze [niesłyszalne]

170
00:06:41,830 --> 00:06:45,110
quizy i położyć się każdego z nas
dokładnie w kolejności ich TF tych

171
00:06:45,110 --> 00:06:47,700
nazwiska na okładce, ponieważ
to jest to o wiele łatwiejsze dla nas

172
00:06:47,700 --> 00:06:51,290
przeszukiwać tego przy użyciu liniowych
wyszukiwania lub jakiś spryt

173
00:06:51,290 --> 00:06:54,050
dla TF znaleźć jego lub
quizy jej uczniów.

174
00:06:54,050 --> 00:06:56,060
>> Więc ten pomysł mieszania
że zobaczysz to

175
00:06:56,060 --> 00:07:00,520
bardzo mocny jest rzeczywiście bardzo
powszechne i bardzo intuicyjne,

176
00:07:00,520 --> 00:07:03,000
podobnie jak może dzielić i
przejęcie było w tygodniu zerowym.

177
00:07:03,000 --> 00:07:05,250
I do przodu na hackathon
Kilka lat temu.

178
00:07:05,250 --> 00:07:08,040
To był Zamyla i kilka
Pracownicy z życzeniami innych studentów

179
00:07:08,040 --> 00:07:09,030
jak przyszedł.

180
00:07:09,030 --> 00:07:12,680
I mieliśmy całą masę składania
stoły tam z plakietkami.

181
00:07:12,680 --> 00:07:15,380
I mieliśmy organizowane tagów nazw
z jak As tam

182
00:07:15,380 --> 00:07:16,690
i Zs tam.

183
00:07:16,690 --> 00:07:20,350
I tak jeden z TF bardzo sprytnie
Napisałem to w instrukcji

184
00:07:20,350 --> 00:07:21,030
na dzień.

185
00:07:21,030 --> 00:07:24,480
A w 12 tygodniu semestru tego
wszystko ma sens i wszyscy

186
00:07:24,480 --> 00:07:25,310
wiedział, co robić.

187
00:07:25,310 --> 00:07:27,900
Ale w każdej chwili masz
kolejkowane w taki sam sposób,

188
00:07:27,900 --> 00:07:30,272
ty realizacji
samo pojęcie mieszania.

189
00:07:30,272 --> 00:07:31,730
Więc sformalizować to trochę.

190
00:07:31,730 --> 00:07:32,890
Oto tablica.

191
00:07:32,890 --> 00:07:36,820
Jest sporządzony za mało
Szeroki tylko dla zobrazowania, wizualnie,

192
00:07:36,820 --> 00:07:38,920
że możemy umieścić ciągów
w czymś takim.

193
00:07:38,920 --> 00:07:41,970
I ta tablica jest
wyraźnie od rozmiaru 26 w sumie.

194
00:07:41,970 --> 00:07:43,935
A co jest nazywane
Tabela arbitralnie.

195
00:07:43,935 --> 00:07:48,930
Ale to tylko interpretacja artysty
tego, co może być tabeli mieszania.

196
00:07:48,930 --> 00:07:52,799
>> Więc tabeli mieszania będzie teraz
być wyższa struktura danych poziom.

197
00:07:52,799 --> 00:07:54,840
Na koniec dnia
jesteśmy by zobaczyć, że Ciebie

198
00:07:54,840 --> 00:07:58,700
można wdrożyć tabeli mieszania, który
jest bardzo podobny do check-in online

199
00:07:58,700 --> 00:08:02,059
na hackathon dużo jak ten
stół używany do sortowania książek egzaminacyjnych.

200
00:08:02,059 --> 00:08:03,850
Ale tabeli mieszania jest
rodzaj wysokiego poziomu

201
00:08:03,850 --> 00:08:08,250
pojęcie, które może wykorzystać tablicę
Pod maską do jego realizacji,

202
00:08:08,250 --> 00:08:11,890
lub może skorzystać z listy długości, a nawet
być może niektóre inne struktury danych.

203
00:08:11,890 --> 00:08:15,590
A teraz to theme-- podejmowanie
niektóre z tych podstawowych składników

204
00:08:15,590 --> 00:08:18,310
jak tablicy i budynku
blokować teraz listy długość

205
00:08:18,310 --> 00:08:21,740
i zobaczyć, co jeszcze możemy budować
na wierzchu tych, jak składniki

206
00:08:21,740 --> 00:08:26,550
w recepturze, co coraz
interesujące i użyteczne wyniki końcowe.

207
00:08:26,550 --> 00:08:28,680
>> Więc z tabeli mieszania
możemy go wdrożyć

208
00:08:28,680 --> 00:08:32,540
w pamięci, tak obrazowo, ale
jak to może być rzeczywiście zakodowane się?

209
00:08:32,540 --> 00:08:33,789
Cóż, może tak po prostu jest to.

210
00:08:33,789 --> 00:08:38,270
Jeśli we wszystkich czapki WYDAJNOŚĆ, jest tylko
niektóre constant-- na przykład 26,

211
00:08:38,270 --> 00:08:42,030
dla 26 liter alphabet--
Mogę zadzwonić do mojego tabeli zmiennych,

212
00:08:42,030 --> 00:08:45,630
i mogę twierdzić, że mam zamiar
umieścić tam gwiazdy char lub string.

213
00:08:45,630 --> 00:08:49,880
Więc to jest tak proste, jak to w przypadku
chcą wprowadzić tabeli mieszania.

214
00:08:49,880 --> 00:08:51,490
A jednak, jest to naprawdę tylko tablica.

215
00:08:51,490 --> 00:08:53,198
Ale znowu, hash
Stół jest teraz to, co my będziemy

216
00:08:53,198 --> 00:08:57,470
nazywamy abstrakcyjne typu danych, który jest po prostu
rodzaj pojęciowej warstw na górze

217
00:08:57,470 --> 00:09:00,780
coś bardziej przyziemnego
teraz jak tablicę.

218
00:09:00,780 --> 00:09:02,960
>> Teraz, jak mamy iść
o rozwiązywaniu problemów?

219
00:09:02,960 --> 00:09:06,980
Cóż, wcześniej miałem luksus
posiadania wystarczająco dużo miejsca tabeli tutaj

220
00:09:06,980 --> 00:09:09,460
tak, że mogę umieścić
quizy wszędzie chciałem.

221
00:09:09,460 --> 00:09:10,620
Więc jak może przejść tutaj.

222
00:09:10,620 --> 00:09:12,100
Zs może przejść tutaj.

223
00:09:12,100 --> 00:09:13,230
Pani może przejść tutaj.

224
00:09:13,230 --> 00:09:14,740
A potem miałem trochę więcej przestrzeni.

225
00:09:14,740 --> 00:09:18,740
Ale to jest trochę oszukiwać prawo
teraz, bo tej tabeli, jeśli naprawdę

226
00:09:18,740 --> 00:09:22,720
myślałem o tym jako tablica, jest tylko
dzieje się z pewnej ustalonej wielkości.

227
00:09:22,720 --> 00:09:25,380
>> Więc technicznie, jeśli ciągnąć
się quizie innego studenta

228
00:09:25,380 --> 00:09:28,490
i zobaczyć, och, to osoby
Nazwa zaczyna się od A także,

229
00:09:28,490 --> 00:09:30,980
I niby chcą ją tam umieścić.

230
00:09:30,980 --> 00:09:34,740
Ale jak tylko umieścić go tam, jeśli
tabela ta rzeczywiście reprezentuje tablicę,

231
00:09:34,740 --> 00:09:37,840
Mam zamiar być nadrzędne lub przebijania
kto tego quizu studenta jest.

232
00:09:37,840 --> 00:09:38,340
Prawda?

233
00:09:38,340 --> 00:09:41,972
Jeśli jest to tablica, tylko jedna rzecz może
przejść w każdej z tych komórek lub elementów.

234
00:09:41,972 --> 00:09:43,680
I tak niby mają
wybierać.

235
00:09:43,680 --> 00:09:45,735
>> Teraz wcześniej I rodzaju
oszukany i to zrobił lub I

236
00:09:45,735 --> 00:09:47,526
tylko rodzaj ułożone
ich jeden nad drugim.

237
00:09:47,526 --> 00:09:49,170
Ale to nie będzie latać w kodzie.

238
00:09:49,170 --> 00:09:52,260
Więc gdzie mogę umieścić
Drugi uczeń, którego nazwa

239
00:09:52,260 --> 00:09:54,964
jeśli wszystko jest to miałem
wolnego miejsca na stół?

240
00:09:54,964 --> 00:09:57,880
I użyłem go trzy sloty i
Wygląda na to, że tylko kilka innych.

241
00:09:57,880 --> 00:09:58,959
Co można zrobić?

242
00:09:58,959 --> 00:09:59,834
PUBLICZNOŚCI: [niesłyszalne]

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

244
00:10:00,565 --> 00:10:01,315
DAVID MALAN: Tak.

245
00:10:01,315 --> 00:10:02,370
Może niech po prostu keep it simple.

246
00:10:02,370 --> 00:10:02,660
Prawda?

247
00:10:02,660 --> 00:10:04,243
To nie pasuje gdzie chcę go umieścić.

248
00:10:04,243 --> 00:10:07,450
Więc mam zamiar umieścić go
technicznie, gdzie B pójdzie.

249
00:10:07,450 --> 00:10:09,932
Teraz, oczywiście, zaczynam
malować się w kąt.

250
00:10:09,932 --> 00:10:11,890
Jeśli dostanę się do studenta
którego nazwa jest w rzeczywistości B,

251
00:10:11,890 --> 00:10:14,840
teraz B zostanie przeniesiona mało
do przodu, a może się zdarzyć, yep,

252
00:10:14,840 --> 00:10:17,530
czy to jest B, teraz ma iść tutaj.

253
00:10:17,530 --> 00:10:20,180
>> I tak to się bardzo szybko
może stać się problematyczne,

254
00:10:20,180 --> 00:10:23,850
ale jest to technika, która rzeczywiście
jest określany jako liniowy próbkowania,

255
00:10:23,850 --> 00:10:26,650
w którym po prostu rozważyć swoje
Tablica będzie wzdłuż linii.

256
00:10:26,650 --> 00:10:29,680
I po prostu rodzaj sondy lub
zbadać każdy dostępny element,

257
00:10:29,680 --> 00:10:31,360
szukam wolnego miejsca.

258
00:10:31,360 --> 00:10:34,010
I jak najszybciej znaleźć
jeden, można upuścić go tam.

259
00:10:34,010 --> 00:10:38,390
>> Teraz, teraz ceny płacone
dla tego rozwiązania jest to, co?

260
00:10:38,390 --> 00:10:41,300
Mamy stałą tablicę rozmiar,
i podczas wkładania imion

261
00:10:41,300 --> 00:10:44,059
do niego, przynajmniej na początku, co jest
czas pracy wstawiania

262
00:10:44,059 --> 00:10:46,350
za wprowadzenie studentów "
quizy w odpowiednich wiadra?

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

264
00:10:48,710 --> 00:10:50,002
Big O co?

265
00:10:50,002 --> 00:10:51,147
>> PUBLICZNOŚCI: brak.

266
00:10:51,147 --> 00:10:52,480
DAVID MALAN: Słyszałem Big O n.

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

268
00:10:53,530 --> 00:10:54,300
Nie prawda.

269
00:10:54,300 --> 00:10:56,490
Ale my odciąć
dlaczego za chwilę.

270
00:10:56,490 --> 00:10:57,702
Co jeszcze może być?

271
00:10:57,702 --> 00:10:58,755
>> PUBLICZNOŚCI: [niesłyszalne]

272
00:10:58,755 --> 00:11:00,380
DAVID MALAN: I pozwól mi zrobić wizualnie.

273
00:11:00,380 --> 00:11:04,720
Więc przypuszczam, że tego jest literą S.

274
00:11:04,720 --> 00:11:05,604
>> Publiczność: To jedna.

275
00:11:05,604 --> 00:11:06,520
DAVID MALAN: To jedna.

276
00:11:06,520 --> 00:11:06,710
Prawda?

277
00:11:06,710 --> 00:11:08,950
Jest to tablica, która
oznacza, że ​​mamy swobodny dostęp.

278
00:11:08,950 --> 00:11:11,790
A jeśli myślimy o tym
jako zero i to jako 25,

279
00:11:11,790 --> 00:11:13,800
i zdajemy sobie sprawę, że,
oh, tu jest mój wkład S

280
00:11:13,800 --> 00:11:16,350
Pewnością mogę przekonwertować
S, ASCII,

281
00:11:16,350 --> 00:11:18,540
z odpowiednim numerem
między zero a 25

282
00:11:18,540 --> 00:11:20,910
a następnie natychmiast
umieścić go tam, gdzie należy.

283
00:11:20,910 --> 00:11:26,120
>> Ale oczywiście, jak tylko mogę
Druga osoba, która to nazwa jest A lub B lub C

284
00:11:26,120 --> 00:11:29,300
w końcu, jeśli użyłem
liniowy sondowania jak mój rozwiązania,

285
00:11:29,300 --> 00:11:31,360
czas pracy
wstawiania w najgorszym przypadku

286
00:11:31,360 --> 00:11:33,120
faktycznie się przechodzą do czego?

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

288
00:11:34,270 --> 00:11:36,045
A ja słyszałam go tutaj
poprawnie wcześnie.

289
00:11:36,045 --> 00:11:36,920
PUBLICZNOŚCI: [niesłyszalne]

290
00:11:36,920 --> 00:11:41,620
DAVID MALAN: Tak jest rzeczywiście, gdy n
mieć wystarczająco duży zestaw danych.

291
00:11:41,620 --> 00:11:44,410
Tak więc z jednej strony, jeśli
Twoja tablica jest na tyle duże,

292
00:11:44,410 --> 00:11:48,287
i dane są na tyle rzadkie, można
stały się ten piękny czas.

293
00:11:48,287 --> 00:11:50,620
Ale jak tylko zaczniesz
coraz więcej i więcej elementów,

294
00:11:50,620 --> 00:11:53,200
i po prostu masz statystycznie
więcej osób z literą

295
00:11:53,200 --> 00:11:56,030
Jak ich nazwa lub list
B, to może potencjalnie

296
00:11:56,030 --> 00:11:57,900
przechodzą w coś bardziej liniowy.

297
00:11:57,900 --> 00:11:59,640
Więc nie dość doskonałe.

298
00:11:59,640 --> 00:12:00,690
Tak więc możemy zrobić lepiej?

299
00:12:00,690 --> 00:12:03,210
>> Cóż, to, co było naszym
Przed gdy rozwiązanie

300
00:12:03,210 --> 00:12:06,820
chcą mieć więcej dynamiki niż
coś w stylu tablicy dozwolone?

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

302
00:12:08,085 --> 00:12:08,960
PUBLICZNOŚCI: [niesłyszalne]

303
00:12:08,960 --> 00:12:10,030
DAVID MALAN: Co możemy wprowadzić?

304
00:12:10,030 --> 00:12:10,530
Tak.

305
00:12:10,530 --> 00:12:11,430
Tak powiązana lista.

306
00:12:11,430 --> 00:12:14,430
Cóż, zobaczymy, co związane
Lista może zrobić dla nas, a nie.

307
00:12:14,430 --> 00:12:17,630
Cóż, pozwól mi zaproponować, że
narysować obrazek poniżej.

308
00:12:17,630 --> 00:12:19,620
Teraz jest inaczej
obraz z przykładu

309
00:12:19,620 --> 00:12:24,750
od innego tekstu, właściwie, że
w rzeczywistości za pomocą tablicy wielkości 31.

310
00:12:24,750 --> 00:12:28,220
A to po prostu autor
ciągi postanowiła hash

311
00:12:28,220 --> 00:12:32,430
nie na podstawie nazwy danej osoby,
lecz na podstawie ich daty urodzin.

312
00:12:32,430 --> 00:12:35,680
Niezależnie od miesiąca, ale zorientowali
jeśli urodził się po raz pierwszy od miesiąca

313
00:12:35,680 --> 00:12:39,580
lub 31 w miesiącu, autor
będzie hash na podstawie tej wartości,

314
00:12:39,580 --> 00:12:44,154
tak, aby rozprzestrzeniać się nazwiska z odrobiną
więcej niż 26 miejsc może pozwolić.

315
00:12:44,154 --> 00:12:47,320
I być może jest to trochę bardziej jednolite
niż dzieje się z liter alfabetu,

316
00:12:47,320 --> 00:12:50,236
bo oczywiście nie ma chyba
więcej ludzi na świecie, z nazwami

317
00:12:50,236 --> 00:12:54,020
że początek z pewnością nie
inne litery alfabetu.

318
00:12:54,020 --> 00:12:56,380
Więc może to jest trochę
bardziej jednolity, zakładając

319
00:12:56,380 --> 00:12:58,640
jednorodny rozkład
niemowląt w całym miesiącu.

320
00:12:58,640 --> 00:12:59,990
>> Ale, oczywiście, to jest wciąż niedoskonała.

321
00:12:59,990 --> 00:13:00,370
Prawda?

322
00:13:00,370 --> 00:13:01,370
Jesteśmy o kolizji.

323
00:13:01,370 --> 00:13:04,680
Wiele osób, w tym
struktura danych są nadal

324
00:13:04,680 --> 00:13:08,432
mające co najmniej taką samą datę urodzenia
jesteś, niezależnie od miesiąca.

325
00:13:08,432 --> 00:13:09,640
Ale co autor uczynił?

326
00:13:09,640 --> 00:13:13,427
Cóż, wygląda na to, że mamy tablicę
po lewej stronie sporządzonej pionowo

327
00:13:13,427 --> 00:13:15,010
ale to tylko interpretacja artysty.

328
00:13:15,010 --> 00:13:18,009
Nie ma znaczenia, jaki kierunek Cię
zwrócić tablicę, to jeszcze tablica.

329
00:13:18,009 --> 00:13:20,225
Co to jest tablica z pozoru?

330
00:13:20,225 --> 00:13:21,500
>> Publiczność: Związany lista.

331
00:13:21,500 --> 00:13:21,650
>> DAVID MALAN: Tak.

332
00:13:21,650 --> 00:13:23,490
Wygląda na to, że to
Tablica połączonej listy.

333
00:13:23,490 --> 00:13:26,490
Więc jeszcze raz, do tego punktu rodzaju
korzystania z tych struktur danych teraz

334
00:13:26,490 --> 00:13:28,550
jako składników do więcej
ciekawe rozwiązania,

335
00:13:28,550 --> 00:13:30,862
można absolutnie brać
podstawowym, jak tablica,

336
00:13:30,862 --> 00:13:33,320
a następnie podjąć się czegoś więcej
ciekawe jak połączonej listy

337
00:13:33,320 --> 00:13:36,660
a nawet połączyć je nawet
bardziej interesujące struktury danych.

338
00:13:36,660 --> 00:13:39,630
I rzeczywiście, to też będzie
nazwać tabeli mieszania,

339
00:13:39,630 --> 00:13:42,610
przy czym tablica jest
naprawdę tabeli mieszania,

340
00:13:42,610 --> 00:13:45,600
ale, że tabeli mieszania ma
łańcuchy, by tak rzec,

341
00:13:45,600 --> 00:13:50,220
które mogą rosnąć lub kurczyć w oparciu o
liczba elementów chcesz wstawić.

342
00:13:50,220 --> 00:13:52,990
>> Się, odpowiednio, co
czas pracy teraz?

343
00:13:52,990 --> 00:13:58,030
Jeśli chcę wstawić kogoś
którego urodziny 31 października,

344
00:13:58,030 --> 00:13:59,040
gdzie ma on iść?

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

346
00:14:00,530 --> 00:14:01,030
Dobrze.

347
00:14:01,030 --> 00:14:02,819
Na samym dole, gdzie jest napisane 31.

348
00:14:02,819 --> 00:14:03,610
I to jest doskonały.

349
00:14:03,610 --> 00:14:05,060
To był stały czas.

350
00:14:05,060 --> 00:14:08,760
Ale co, jeśli znajdziemy kogoś innego
którego urodziny, zobaczmy,

351
00:14:08,760 --> 00:14:10,950
Październik, listopad, 31 grudnia?

352
00:14:10,950 --> 00:14:12,790
W przypadku, gdy jest on pójdzie?

353
00:14:12,790 --> 00:14:13,290
Samo.

354
00:14:13,290 --> 00:14:13,970
Dwuetapowym chociaż.

355
00:14:13,970 --> 00:14:15,303
To jest stała, choć nie jest?

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

357
00:14:16,360 --> 00:14:16,860
Dobrze.

358
00:14:16,860 --> 00:14:17,840
W tej chwili jest.

359
00:14:17,840 --> 00:14:20,570
Jednak w przypadku ogólnym
im więcej ludzi możemy dodać,

360
00:14:20,570 --> 00:14:23,790
probabilistycznie, jedziemy
aby uzyskać więcej i więcej kolizji.

361
00:14:23,790 --> 00:14:26,820
>> Teraz to jest trochę
lepiej, bo technicznie

362
00:14:26,820 --> 00:14:34,580
teraz moje łańcuchy może być w
w najgorszym przypadku, jak długo?

363
00:14:34,580 --> 00:14:38,890
Jeśli wstawić n tym więcej ludzi do
wyrafinowane struktury danych, brak ludzi,

364
00:14:38,890 --> 00:14:41,080
w najgorszym przypadku to będzie n.

365
00:14:41,080 --> 00:14:41,815
Dlaczego?

366
00:14:41,815 --> 00:14:43,332
>> Publiczność: Bo jeśli wszyscy
ma urodziny tego samego dnia,

367
00:14:43,332 --> 00:14:44,545
że będziemy mieć jedną linię.

368
00:14:44,545 --> 00:14:45,420
DAVID MALAN: Idealny.

369
00:14:45,420 --> 00:14:47,480
To może być trochę wydumane,
ale naprawdę, w najgorszym przypadku,

370
00:14:47,480 --> 00:14:50,117
jeśli każdy z nas ma urodziny tego samego dnia,
biorąc pod uwagę trzeba wejść,

371
00:14:50,117 --> 00:14:51,950
będziesz mieć
masowo długi łańcuch.

372
00:14:51,950 --> 00:14:54,241
I tak, można to nazwać
Tablica mieszająca, ale tak naprawdę to

373
00:14:54,241 --> 00:14:56,810
tylko ogromny lista związana z
dużo niewykorzystanego miejsca.

374
00:14:56,810 --> 00:15:00,460
Ogólnie jednak, jeżeli założymy, że
przynajmniej są uniform-- urodzin

375
00:15:00,460 --> 00:15:01,750
i to chyba nie jest.

376
00:15:01,750 --> 00:15:02,587
Robię to w górę.

377
00:15:02,587 --> 00:15:04,420
Ale jeśli założymy, dla
sake dyskusji

378
00:15:04,420 --> 00:15:07,717
że są one, to w teorii, czy
jest pionowa reprezentacja

379
00:15:07,717 --> 00:15:11,050
tablicy, a potem mam nadzieję, że jesteś
dostanie łańcuchy, które są, wiesz,

380
00:15:11,050 --> 00:15:15,880
mniej więcej takiej samej długości, gdzie każdy z
nich reprezentuje dzień miesiąca.

381
00:15:15,880 --> 00:15:19,930
>> Teraz, czy jest +31 dni w miesiącu,
co oznacza, że ​​tak naprawdę mój czas pracy

382
00:15:19,930 --> 00:15:25,230
jest duże O n ponad 31, które
czuje się lepiej niż liniowy.

383
00:15:25,230 --> 00:15:27,950
Ale to, co było jednym z naszych
Zobowiązania kilka tygodni

384
00:15:27,950 --> 00:15:31,145
temu, kiedy doszło do wyrażania
czas działania algorytmu?

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

386
00:15:33,450 --> 00:15:35,190
Wystarczy spojrzeć tylko na wysokim terminu zamówienia.

387
00:15:35,190 --> 00:15:35,690
Prawda?

388
00:15:35,690 --> 00:15:37,400
31 jest na pewno pomocne.

389
00:15:37,400 --> 00:15:39,610
Ale to wciąż wielki O n.

390
00:15:39,610 --> 00:15:41,730
Ale jeden z tematów
zestaw pięciu z problemem

391
00:15:41,730 --> 00:15:43,950
będzie do
przyznać, że absolutnie,

392
00:15:43,950 --> 00:15:47,320
asymptotycznie, teoretycznie
to struktura danych

393
00:15:47,320 --> 00:15:50,470
nie jest lepsza niż tylko
jeden ogromny lista powiązane.

394
00:15:50,470 --> 00:15:53,550
I rzeczywiście, w najgorszym przypadku, ten
Tablica mieszająca może przechodzą do tego.

395
00:15:53,550 --> 00:15:57,620
>> Ale w realnym świecie, o nas ludzie
że własnych komputerach Mac lub PC lub cokolwiek

396
00:15:57,620 --> 00:16:01,240
i działa prawdziwy świat
Oprogramowanie na danych rzeczywistych światowej,

397
00:16:01,240 --> 00:16:03,260
który algorytm idziesz do woli?

398
00:16:03,260 --> 00:16:09,180
Który podejmuje kroki końcowych lub
który trwa n dzieli się przez 31 kroków

399
00:16:09,180 --> 00:16:12,900
znaleźć jakiś kawałek danych lub
aby wyszukać informacje?

400
00:16:12,900 --> 00:16:16,580
To znaczy, absolutnie 31 marek
Różnica w realnym świecie.

401
00:16:16,580 --> 00:16:18,540
Jest to 31 razy szybciej.

402
00:16:18,540 --> 00:16:20,880
A my, ludzie są z pewnością
będzie wdzięczny.

403
00:16:20,880 --> 00:16:23,004
>> Tak sobie dychotomię
rzeczywiście istnieje między

404
00:16:23,004 --> 00:16:25,920
mówić o rzeczach teoretycznie
a co zdecydowanie asymptotycznie

405
00:16:25,920 --> 00:16:28,760
ma wartość jak widzieliśmy,
ale w realnym świecie,

406
00:16:28,760 --> 00:16:32,930
jeśli zależy Ci tylko co
ludzka szczęśliwy dla wejść ogólnych,

407
00:16:32,930 --> 00:16:36,010
można bardzo dobrze się na przyjęcie
Fakt, że tak, to jest liniowy,

408
00:16:36,010 --> 00:16:38,360
ale to jest 31 razy szybciej
niż liniowy może być.

409
00:16:38,360 --> 00:16:41,610
A jeszcze lepiej, że nie wystarczy
coś zrobić dowolny jak data urodzenia,

410
00:16:41,610 --> 00:16:44,030
mogliśmy spędzić trochę
więcej czasu i spryt

411
00:16:44,030 --> 00:16:47,140
i zastanowić się, co możemy zrobić,
imię, a może czyjeś

412
00:16:47,140 --> 00:16:50,130
ich data urodzenia połączyć te
składniki, aby dowiedzieć się czegoś

413
00:16:50,130 --> 00:16:52,720
że jest naprawdę więcej
jednolita i mniej chropawy,

414
00:16:52,720 --> 00:16:56,250
że tak powiem, niż tego obrazu
Obecnie sugeruje to może być.

415
00:16:56,250 --> 00:16:57,750
Jak moglibyśmy wdrożyć to w kodzie?

416
00:16:57,750 --> 00:17:00,280
Cóż, pozwól mi zaproponować, że
tylko pożyczyć trochę składni mamy

417
00:17:00,280 --> 00:17:01,799
używane kilka razy do tej pory.

418
00:17:01,799 --> 00:17:03,590
I mam zamiar zdefiniować
Węzeł, który ponownie

419
00:17:03,590 --> 00:17:06,812
to ogólne określenie dla tylko niektóre
Pojemnik na pewnej struktury danych.

420
00:17:06,812 --> 00:17:09,020
Mam zamiar zaproponować,
Ciąg będzie tam.

421
00:17:09,020 --> 00:17:11,369
Ale mamy zamiar rozpocząć przyjmowanie
te koła się teraz trenuje.

422
00:17:11,369 --> 00:17:13,230
>> Biblioteka nie więcej CS50
naprawdę, jeśli nie chcesz

423
00:17:13,230 --> 00:17:15,230
używać go do finału
Projekt, który jest w porządku,

424
00:17:15,230 --> 00:17:18,569
ale teraz zamierzamy wycofać
kurtyny i powiedzieć, że to po prostu gwiazda char.

425
00:17:18,569 --> 00:17:22,069
Tak więc słowa nie będzie
nazwisko osoby, o którym mowa.

426
00:17:22,069 --> 00:17:25,079
I teraz mam link
stąd do następnego węzła

427
00:17:25,079 --> 00:17:28,170
tak, że stanowią one
każdy z węzłów

428
00:17:28,170 --> 00:17:30,950
w łańcuchu potencjalnie
z połączonej listy.

429
00:17:30,950 --> 00:17:34,090
>> A teraz jak mam zadeklarować
Sam tabeli mieszania?

430
00:17:34,090 --> 00:17:36,660
Jak mogę zadeklarować całą tę konstrukcję?

431
00:17:36,660 --> 00:17:40,960
Cóż, tak naprawdę, tak jak kiedyś wskaźnik
się tylko do pierwszego elementu listy

432
00:17:40,960 --> 00:17:44,510
wcześniej, podobnie mogę tylko powiedzieć,
Muszę tylko kilka wskazówek

433
00:17:44,510 --> 00:17:46,270
do realizacji tego całego tabeli mieszania.

434
00:17:46,270 --> 00:17:49,484
Zamierzam tablicę
zwany stół do tabeli mieszania.

435
00:17:49,484 --> 00:17:50,900
To będzie zdolności wielkości.

436
00:17:50,900 --> 00:17:52,525
To, jak wiele elementów można w nim zmieścić.

437
00:17:52,525 --> 00:17:56,180
I każdy z tych elementów w tym
Tablica będzie gwiazdą węzeł.

438
00:17:56,180 --> 00:17:56,810
Dlaczego?

439
00:17:56,810 --> 00:18:00,160
Cóż, na tym zdjęciu, co mam
wdrażania tabeli mieszania jako

440
00:18:00,160 --> 00:18:04,330
skutecznie na początku jest tylko
Tablica ta, że ​​mamy wyciągnąć pionowo,

441
00:18:04,330 --> 00:18:06,820
każdy z których kwadraty
reprezentuje wskaźnik.

442
00:18:06,820 --> 00:18:09,170
To te, które mają ukośniki
z nich są po prostu puste.

443
00:18:09,170 --> 00:18:11,410
I te, które mają
strzałkami w prawo

444
00:18:11,410 --> 00:18:16,140
są rzeczywistymi wskaźnikami do rzeczywistych węzłów,
ergo rozpoczęcia połączonej listy.

445
00:18:16,140 --> 00:18:19,050
>> Więc tutaj, a następnie, w jaki sposób moglibyśmy
wdrożyć tabeli mieszania, które

446
00:18:19,050 --> 00:18:21,580
realizuje oddzielny łańcuchowym.

447
00:18:21,580 --> 00:18:22,840
Teraz możemy zrobić lepiej?

448
00:18:22,840 --> 00:18:25,632
Dobrze Obiecałem, że po raz ostatni
możemy osiągnąć stały czas.

449
00:18:25,632 --> 00:18:27,381
I dał ci trochę
Stała czasowa tutaj,

450
00:18:27,381 --> 00:18:29,850
ale to naprawdę nie powiedział
Stała czasowa, bo to wciąż

451
00:18:29,850 --> 00:18:31,890
uzależniona od sumy
Liczba elementów

452
00:18:31,890 --> 00:18:34,500
jesteś wprowadzania do
Struktura danych.

453
00:18:34,500 --> 00:18:35,980
Ale załóżmy, że to zrobił.

454
00:18:35,980 --> 00:18:39,550
Pozwól mi wrócić do ekranu tutaj.

455
00:18:39,550 --> 00:18:44,520
Pozwól, że Projekt ten również się tutaj, jasne
ekran, i przypuszczam, że to zrobił.

456
00:18:44,520 --> 00:18:49,300
Załóżmy, że chcę, aby wstawić nazwę
Daven się do mojego struktury danych.

457
00:18:49,300 --> 00:18:52,100
>> Więc chcę wstawić ciąg
Daven do struktury danych.

458
00:18:52,100 --> 00:18:54,370
Co zrobić, jeśli nie używam
Tablica mieszająca, ale używam

459
00:18:54,370 --> 00:18:56,980
coś, co jest bardziej podobny do drzewa
jak drzewo genealogiczne, gdzie

460
00:18:56,980 --> 00:18:59,670
masz jakieś korzenie w
Ulubione, a następnie węzły i liście

461
00:18:59,670 --> 00:19:01,440
że go w dół i na zewnątrz.

462
00:19:01,440 --> 00:19:04,450
Załóżmy więc, że ja
chcesz wstawić Daven na

463
00:19:04,450 --> 00:19:06,430
do tego, co jest obecnie pusta lista.

464
00:19:06,430 --> 00:19:09,780
Zamierzam wykonać następujące czynności: Jestem
W celu utworzenia węzła w tej rodziny

465
00:19:09,780 --> 00:19:15,170
jak drzewa, które wygląda struktura danych
trochę tak, z których każda

466
00:19:15,170 --> 00:19:19,640
prostokątów jest, powiedzmy,
na razie 26 elementów w nim.

467
00:19:19,640 --> 00:19:21,650
I każda z komórek
w tej tablicy będzie

468
00:19:21,650 --> 00:19:23,470
reprezentuje literę alfabetu.

469
00:19:23,470 --> 00:19:28,190
>> W szczególności mam zamiar leczyć
to jest, to B, a następnie C, następnie D,

470
00:19:28,190 --> 00:19:29,310
ten tutaj.

471
00:19:29,310 --> 00:19:32,940
Więc to będzie skutecznie
reprezentuje literę D.

472
00:19:32,940 --> 00:19:36,040
Ale, aby wstawić na wszystkie Daven
wymienić muszę zrobić nieco więcej.

473
00:19:36,040 --> 00:19:37,840
Więc jestem pierwszy będzie hash, że tak powiem.

474
00:19:37,840 --> 00:19:41,049
Zamierzam przyjrzeć się pierwszej litery
w Daven, która jest oczywiście D

475
00:19:41,049 --> 00:19:42,840
i mam zamiar przeznaczyć
Węzeł, który wygląda

476
00:19:42,840 --> 00:19:45,570
jak this-- duży prostokąt duży
wystarczy, aby zmieścić cały alfabet.

477
00:19:45,570 --> 00:19:47,140
>> Teraz D odbywa.

478
00:19:47,140 --> 00:19:49,720
Teraz A. D-V-E-N jest celem.

479
00:19:49,720 --> 00:19:51,220
Więc teraz, co mam zamiar zrobić, to ten.

480
00:19:51,220 --> 00:19:54,027
Jak tylko zacząłem zawiadomienie D
tam nie ma wskaźnika.

481
00:19:54,027 --> 00:19:56,860
To wartości śmieci w tej chwili,
lub może zainicjować go na null.

482
00:19:56,860 --> 00:19:59,630
Ale pozwól mi iść dalej z
idea budowania drzewa.

483
00:19:59,630 --> 00:20:04,260
Pozwól mi przydzielić inny jeden z nich
Węzły, które posiada 26 elementów w nim.

484
00:20:04,260 --> 00:20:05,150
>> I wiesz co?

485
00:20:05,150 --> 00:20:09,130
Jeśli jest to tylko w pamięci, że węzeł
Stworzyłem z malloc, za pomocą struct

486
00:20:09,130 --> 00:20:11,240
jak to już wkrótce,
Mam zamiar zrobić this--

487
00:20:11,240 --> 00:20:14,450
Mam zamiar wyciągnąć strzałę z
rzeczą, która reprezentowana D w dół

488
00:20:14,450 --> 00:20:15,860
do tego nowego węzła.

489
00:20:15,860 --> 00:20:19,240
A teraz, po raz pierwszy obok
litera w nazwie Daven, w

490
00:20:19,240 --> 00:20:24,150
V-- D-V-- mam zamiar iść do przodu
i wyciągnąć inny węzeł tak,

491
00:20:24,150 --> 00:20:30,150
przy czym elementy, które tutaj V
będziemy rysować na instance-- whoops.

492
00:20:30,150 --> 00:20:31,020
Nie będziemy tam rysować.

493
00:20:31,020 --> 00:20:31,936
To będzie tutaj.

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

495
00:20:32,890 --> 00:20:35,712
>> Następnie jedziemy do
uznają to za V.

496
00:20:35,712 --> 00:20:44,920
A potem tu będziemy indeksu
dół od V do tego, co będziemy rozważać E.

497
00:20:44,920 --> 00:20:50,100
A potem tutaj będziemy
go jeden z tych węzłów tutaj.

498
00:20:50,100 --> 00:20:52,930
I teraz mamy pytanie.

499
00:20:52,930 --> 00:20:57,840
Muszę w jakiś sposób wskazują, że
jesteśmy na końcu łańcucha Daven.

500
00:20:57,840 --> 00:20:59,490
Więc może po prostu pozostawić puste.

501
00:20:59,490 --> 00:21:02,670
>> Ale co, jeśli mamy Daven na
pełna nazwa również, które

502
00:21:02,670 --> 00:21:04,280
jest, jak już powiedzieliśmy, Davenport?

503
00:21:04,280 --> 00:21:06,970
Więc co, jeśli Daven jest
faktycznie podciąg,

504
00:21:06,970 --> 00:21:08,960
prefiks znacznie dłuższy ciąg?

505
00:21:08,960 --> 00:21:11,450
Nie możemy po prostu stałe
powiedzieć nic się nie dzieje

506
00:21:11,450 --> 00:21:14,410
tam, bo mogliśmy
nigdy wstawić słowo jak Davenport

507
00:21:14,410 --> 00:21:15,840
w tej strukturze danych

508
00:21:15,840 --> 00:21:19,560
>> Więc co możemy zrobić, a nie jest
traktować każdego z tych elementów

509
00:21:19,560 --> 00:21:22,170
a może o dwa
elementy wewnątrz nich.

510
00:21:22,170 --> 00:21:24,810
Jednym z nich jest wskaźnik, rzeczywiście,
jak robiłem.

511
00:21:24,810 --> 00:21:27,100
Tak więc każdy z tych pól
Nie jest tylko jedna komórka.

512
00:21:27,100 --> 00:21:29,855
Ale co, jeśli górna
jedno- dolny na

513
00:21:29,855 --> 00:21:32,230
będzie pusty, ponieważ
nie ma Davenport jeszcze.

514
00:21:32,230 --> 00:21:34,197
Co zrobić, jeśli górna
jest jakaś specjalna wartość?

515
00:21:34,197 --> 00:21:36,530
I to będzie trochę
trudno jest to rozmiar rysować.

516
00:21:36,530 --> 00:21:38,130
Ale załóżmy, że jest to po prostu znak wyboru.

517
00:21:38,130 --> 00:21:38,920
Sprawdź.

518
00:21:38,920 --> 00:21:44,230
D-V-E-N jest ciągiem
w tej strukturze danych.

519
00:21:44,230 --> 00:21:48,350
>> Tymczasem, gdybym miał więcej miejsca
tutaj, mogłem zrobić P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
i może umieścić czek w węźle
że ma literę T na samym końcu.

521
00:21:52,650 --> 00:21:55,460
Jest to więc masowo
Kompleks wyglądające struktury danych.

522
00:21:55,460 --> 00:21:57,210
A mój charakter pisma
na pewno nie pomaga.

523
00:21:57,210 --> 00:22:00,043
Ale gdybym chciał włożyć coś
jeszcze, za co będziemy robić.

524
00:22:00,043 --> 00:22:03,370
Gdybyśmy chcieli umieścić Dawid,
że będziemy postępować zgodnie z tą samą logiką, D-A-V,

525
00:22:03,370 --> 00:22:08,802
ale teraz chciałbym zwrócić się obok
element nie z E, ale od I do D.

526
00:22:08,802 --> 00:22:10,760
Więc nie będzie
więcej węzłów w tym drzewie.

527
00:22:10,760 --> 00:22:12,325
Mamy zamiar mieć połączenia malloc więcej.

528
00:22:12,325 --> 00:22:14,700
Ale ja nie chcę, aby
kompletny bałagan z tym obrazem.

529
00:22:14,700 --> 00:22:17,710
Więc zamiast patrzeć na jednego
, co zostało sformułowane wcześniej

530
00:22:17,710 --> 00:22:21,810
tak ze nie kropka, kropka,
kropki, ale tylko skrócone tablice.

531
00:22:21,810 --> 00:22:23,950
A każdy z węzłów
w tym drzewa tutaj

532
00:22:23,950 --> 00:22:26,700
oznacza to samo thing--
Tablica Ray rozmiaru 26.

533
00:22:26,700 --> 00:22:28,860
>> Lub jeśli chcemy być
Teraz naprawdę właściwa, co

534
00:22:28,860 --> 00:22:30,790
jeśli czyjeś imię, jak
apostrof, niech

535
00:22:30,790 --> 00:22:35,560
Zakładamy, że każdy węzeł ma rzeczywiście
jak 27 indeksów w nim, a nie tylko 26.

536
00:22:35,560 --> 00:22:42,020
Tak to teraz będzie dane
struktura nazywana trie-- R-T I-E.

537
00:22:42,020 --> 00:22:46,120
Trie, która jest podobno
historycznie mądra nazwa drzewa

538
00:22:46,120 --> 00:22:49,040
, który jest zoptymalizowany do
odzyskiwanie, co oczywiście

539
00:22:49,040 --> 00:22:50,870
pisze się z I-E więc trie.

540
00:22:50,870 --> 00:22:52,710
Ale to jest historia trie.

541
00:22:52,710 --> 00:22:55,860
>> Więc trie jest to drzewo, jak dane
Struktura jak drzewo genealogiczne

542
00:22:55,860 --> 00:22:57,510
że ostatecznie zachowuje się tak.

543
00:22:57,510 --> 00:23:00,890
I tu jest właśnie kolejny przykład
cała masa imion innych ludzi.

544
00:23:00,890 --> 00:23:03,540
Ale pytanie teraz
pod ręką to, co mają

545
00:23:03,540 --> 00:23:08,070
zdobyliśmy wprowadzając zapewne więcej
skomplikowana struktura danych oraz jednym,

546
00:23:08,070 --> 00:23:09,870
mówiąc, że używa dużo pamięci.

547
00:23:09,870 --> 00:23:11,703
>> Bo chociaż,
w tej chwili, jestem tylko

548
00:23:11,703 --> 00:23:15,050
za pomocą wskaźnika i D's
I V i Es i Ns,

549
00:23:15,050 --> 00:23:16,700
Tracę kawał dużo pamięci.

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

551
00:23:18,030 --> 00:23:22,660
Ale gdzie spędzić jednego zasobu,
Staram się nie uzyskać z powrotem innego.

552
00:23:22,660 --> 00:23:26,020
Więc jeśli mam spędzać więcej miejsca,
co prawdopodobnie nadzieja?

553
00:23:26,020 --> 00:23:27,407
Że spędzam mniej co?

554
00:23:27,407 --> 00:23:28,240
Publiczność: Mniej czasu.

555
00:23:28,240 --> 00:23:28,990
DAVID MALAN: Czas.

556
00:23:28,990 --> 00:23:30,320
Teraz, dlaczego może to być?

557
00:23:30,320 --> 00:23:33,880
Cóż, to, co jest wstawiania
Czas, w kategoriach wielkiej O teraz,

558
00:23:33,880 --> 00:23:37,660
nazwy jak Daven
lub Davenport czy Dawid?

559
00:23:37,660 --> 00:23:39,340
Cóż, Daven było pięć kroków.

560
00:23:39,340 --> 00:23:42,350
Davenport będzie dziewięć kroków,
więc byłoby kilka kroków.

561
00:23:42,350 --> 00:23:44,250
David będzie pięć kroków, jak również.

562
00:23:44,250 --> 00:23:47,230
To są konkretne
numery, ale na pewno nie ma

563
00:23:47,230 --> 00:23:49,550
górną granicę
długość czyjegoś imienia.

564
00:23:49,550 --> 00:23:52,240
I rzeczywiście, w tym problemu
zestawy pięciu specyfikacji

565
00:23:52,240 --> 00:23:54,050
mamy zamiar zaproponować
że to coś

566
00:23:54,050 --> 00:23:55,470
to znaki 40-pewne-nieparzyste.

567
00:23:55,470 --> 00:23:58,180
>> Realistycznie, nikt nie ma
nieskończenie długa nazwa,

568
00:23:58,180 --> 00:24:01,542
to znaczy, że długość
nazwisko lub długość łańcucha moglibyśmy

569
00:24:01,542 --> 00:24:03,750
mają pewien stan
Struktura jest chyba co?

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

571
00:24:05,550 --> 00:24:06,250
Jest to stała.

572
00:24:06,250 --> 00:24:06,430
Prawda?

573
00:24:06,430 --> 00:24:09,310
To może być wielki jak stały
40 coś, ale stała.

574
00:24:09,310 --> 00:24:13,752
I nie ma uzależnienia od ilu
inne nazwy są w tej strukturze danych.

575
00:24:13,752 --> 00:24:15,460
Innymi słowy, jeśli I
chce teraz włożyć

576
00:24:15,460 --> 00:24:20,540
Colton lub Gabriel lub Rob lub Zamyla lub
Alison i Belinda lub wszelkie inne nazwy

577
00:24:20,540 --> 00:24:23,940
z pracowników w tym danych
struktura, jest czas pracy

578
00:24:23,940 --> 00:24:26,750
wstawiania inne nazwy
będzie w wpłynęły

579
00:24:26,750 --> 00:24:30,220
od tego, jak wiele innych elementów są
w już struktury danych?

580
00:24:30,220 --> 00:24:31,040
To nie jest.

581
00:24:31,040 --> 00:24:31,540
Prawda?

582
00:24:31,540 --> 00:24:36,150
Ponieważ jesteśmy skutecznie za pomocą
to wielowarstwowa tabeli mieszania.

583
00:24:36,150 --> 00:24:38,280
I czas pracy
każda z tych operacji

584
00:24:38,280 --> 00:24:41,510
nie jest zależna od liczby
Elementy, które mają w strukturze danych

585
00:24:41,510 --> 00:24:43,090
lub które są w końcu dzieje
się w strukturze danych,

586
00:24:43,090 --> 00:24:44,714
lecz na długości co konkretnie?

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

588
00:24:46,500 --> 00:24:49,200
>> Ciąg jest
włożona, co robi

589
00:24:49,200 --> 00:24:52,580
Stała to asymptotycznie
time-- duże O jednego.

590
00:24:52,580 --> 00:24:54,720
I szczerze mówiąc, tylko w
prawdziwy świat, to

591
00:24:54,720 --> 00:24:58,380
oznacza wstawienie rozgrywa nazwa Daven
jak pięć kroków, czy Davenport dziewięć

592
00:24:58,380 --> 00:25:00,100
kroki, lub David pięć kroków.

593
00:25:00,100 --> 00:25:03,071
To cholernie małe czasy jazdy.

594
00:25:03,071 --> 00:25:05,320
I rzeczywiście, to bardzo
dobra rzecz, zwłaszcza gdy

595
00:25:05,320 --> 00:25:08,126
to nie zależy od łącznej
liczba elementów w tam.

596
00:25:08,126 --> 00:25:10,500
Więc jak możemy wdrożyć to
rodzaju struktury w kodzie?

597
00:25:10,500 --> 00:25:12,900
To trochę więcej
skomplikowane, ale nadal jest to

598
00:25:12,900 --> 00:25:15,050
tylko zastosowanie
podstawowe cegiełki.

599
00:25:15,050 --> 00:25:17,830
Idę do przedefiniowania
węzeł nas w następujący sposób:

600
00:25:17,830 --> 00:25:21,100
bool i to nazywa word--
można nazwać niczego.

601
00:25:21,100 --> 00:25:23,970
Ale bool reprezentuje
co narysowałem jako znak wyboru.

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

603
00:25:24,490 --> 00:25:26,720
To jest koniec łańcucha
w tej strukturze danych.

604
00:25:26,720 --> 00:25:30,702
>> I, oczywiście, gwiazda węzeł
nie odnosi się do dzieci.

605
00:25:30,702 --> 00:25:32,410
I rzeczywiście, tak jak
drzewo genealogiczne, to

606
00:25:32,410 --> 00:25:34,370
uznałby węzły
które są zawieszony

607
00:25:34,370 --> 00:25:36,920
na dnie pewnego nadrzędnego
Element się dzieci.

608
00:25:36,920 --> 00:25:40,510
I tak będzie do dzieci
być tablicą 27, 27 jeden

609
00:25:40,510 --> 00:25:41,680
po prostu do apostrofu.

610
00:25:41,680 --> 00:25:43,390
Jedziemy do sortowania
w szczególnym przypadku tego.

611
00:25:43,390 --> 00:25:45,400
Więc można mieć pewność,
Nazwy z apostrofami.

612
00:25:45,400 --> 00:25:47,399
Może nawet łącznik powinien
idź tam, ale będziesz

613
00:25:47,399 --> 00:25:50,330
zobacz w zestawie 5 p opieki tylko
o listach i apostrofów.

614
00:25:50,330 --> 00:25:52,990
>> A potem jak można reprezentować
Struktura danych sama?

615
00:25:52,990 --> 00:25:56,454
Jak Pan reprezentuje korzeń
tego trie, że tak powiem?

616
00:25:56,454 --> 00:25:59,620
Cóż, tak jak z połączonej listy, to
potrzebuje wskaźnik do pierwszego elementu.

617
00:25:59,620 --> 00:26:04,270
Z trie wystarczy jeden
wskaźnik do korzenia tego trie.

618
00:26:04,270 --> 00:26:07,290
I stamtąd można hash
Twój sposób coraz głębiej w dół

619
00:26:07,290 --> 00:26:10,460
każdy inny węzeł w konstrukcji.

620
00:26:10,460 --> 00:26:13,440
Tak po prostu z tym puszki
Oświadczamy, że struct.

621
00:26:13,440 --> 00:26:15,877
>> Teraz Meanwhile-- Och, pytanie.

622
00:26:15,877 --> 00:26:17,220
>> Publiczność: Co bool słowo?

623
00:26:17,220 --> 00:26:20,490
>> DAVID MALAN: Bool słowo
tylko ten C wcielenie

624
00:26:20,490 --> 00:26:22,920
z tego, co opisałem
w tym oknie tutaj, kiedy

625
00:26:22,920 --> 00:26:26,000
Zacząłem podziału każdej z
elementy na dwie części Array.

626
00:26:26,000 --> 00:26:27,600
Jednym z nich jest wskaźnik do następnego węzła.

627
00:26:27,600 --> 00:26:30,280
Druga ma być
coś jak pole wyboru

628
00:26:30,280 --> 00:26:33,770
powiedzieć tak, nie
Słowo Daven, że kończy się tutaj,

629
00:26:33,770 --> 00:26:35,610
dlatego, że nie chcemy,
w momencie, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Mimo, że Dave będzie
uzasadnione słowo, że nie jest w trie

631
00:26:39,320 --> 00:26:39,830
jeszcze.

632
00:26:39,830 --> 00:26:40,950
I D nie jest słowo.

633
00:26:40,950 --> 00:26:42,770
I D-nie jest to słowo lub nazwa.

634
00:26:42,770 --> 00:26:45,020
Więc z haczykiem
wskazuje tylko raz Ciebie

635
00:26:45,020 --> 00:26:48,190
uderzył węzeł jest
poprzednia ścieżka znaków

636
00:26:48,190 --> 00:26:50,700
rzeczywiście ciąg wstawienie.

637
00:26:50,700 --> 00:26:53,660
Więc to wszystko bool
nie robi dla nas.

638
00:26:53,660 --> 00:26:55,500
>> Wszelkie inne pytania na próbach?

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

640
00:26:56,215 --> 00:26:58,035
>> Publiczność: Co to jest nakładanie?

641
00:26:58,035 --> 00:26:59,945
Co zrobić, jeśli masz Dave i Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID MALAN: Idealny.

643
00:27:00,820 --> 00:27:02,580
Co zrobić, jeśli masz Dave i Daven?

644
00:27:02,580 --> 00:27:06,240
Jeśli więc włożyć, powiedzmy pseudonim,
dla David-- Dave-- D-A-V-E?

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

646
00:27:07,370 --> 00:27:08,700
To jest rzeczywiście bardzo prosty.

647
00:27:08,700 --> 00:27:10,325
Więc jedziemy tylko wziąć cztery kroki.

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

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. I co mam
zrobić raz trafiłem że czwarty węzeł?

650
00:27:15,847 --> 00:27:16,680
Po prostu się sprawdzić.

651
00:27:16,680 --> 00:27:18,000
Jesteśmy już dobrze iść.

652
00:27:18,000 --> 00:27:18,840
Gotowe.

653
00:27:18,840 --> 00:27:19,750
Cztery kroki.

654
00:27:19,750 --> 00:27:21,590
Stała czasowa asymptotycznie.

655
00:27:21,590 --> 00:27:26,300
A teraz mamy wykazały, że zarówno Dave
i Daven są struny w strukturze.

656
00:27:26,300 --> 00:27:27,710
Tak więc nie jest to problem.

657
00:27:27,710 --> 00:27:30,200
I zauważyć, jak obecność
z Daven nie udało się

658
00:27:30,200 --> 00:27:34,750
podjęcia wszelkich mniej lub więcej czasu
Czas na Dave'a i odwrotnie.

659
00:27:34,750 --> 00:27:36,000
>> Co jeszcze możemy zrobić?

660
00:27:36,000 --> 00:27:40,680
Użyliśmy tej metafory przed
tac reprezentujących coś.

661
00:27:40,680 --> 00:27:43,380
Ale okazuje się, że
stos tac jest rzeczywiście

662
00:27:43,380 --> 00:27:47,187
poglądowe innego abstrakcyjnego danych
type-- wyższy poziom struktury danych

663
00:27:47,187 --> 00:27:49,770
który na koniec dnia jest po prostu
jak tablica lub połączonej listy

664
00:27:49,770 --> 00:27:50,970
lub coś bardziej przyziemne.

665
00:27:50,970 --> 00:27:53,270
Ale to jest bardziej interesujące
koncepcyjne koncepcja.

666
00:27:53,270 --> 00:27:56,440
Stos, jak te
podajników tutaj w Mather,

667
00:27:56,440 --> 00:27:58,750
nazywane są ogólnie
tylko that-- stos.

668
00:27:58,750 --> 00:28:02,540
>> Oraz w strukturze tego typu danych
masz dwa operations--

669
00:28:02,540 --> 00:28:05,880
trzeba dążyć do jednej nazwie
dodawania co do stosu

670
00:28:05,880 --> 00:28:08,320
jak wprowadzenie innego podajnika
tyłu na górze stosu.

671
00:28:08,320 --> 00:28:11,350
A następnie pop, co oznacza, że
przyjąć najwyższą tacy off.

672
00:28:11,350 --> 00:28:16,210
Ale co jest kluczem o to, że stos
to musi to ciekawe cechy.

673
00:28:16,210 --> 00:28:19,560
Jako pracownicy jadalni są
rozmieszczanie tace do następnego posiłku,

674
00:28:19,560 --> 00:28:21,380
co będzie
prawda o tym, jak studenci

675
00:28:21,380 --> 00:28:22,856
interakcji z tej struktury danych?

676
00:28:22,856 --> 00:28:24,480
Publiczność: Zamierzają pop jednorazowe.

677
00:28:24,480 --> 00:28:26,550
DAVID MALAN: Zamierzają
pop-One, mam nadzieję, że szczyt.

678
00:28:26,550 --> 00:28:28,910
W przeciwnym razie jest to tylko głupie
aby przejść całą drogę w dół.

679
00:28:28,910 --> 00:28:29,070
Prawda?

680
00:28:29,070 --> 00:28:31,620
Struktura danych naprawdę nie pozwala
można chwycić dolną tacę co najmniej

681
00:28:31,620 --> 00:28:32,520
łatwo.

682
00:28:32,520 --> 00:28:35,040
Więc jest to ciekawy
nieruchomości na stosie

683
00:28:35,040 --> 00:28:39,730
że ostatni element jest
będzie pierwszy na zewnątrz.

684
00:28:39,730 --> 00:28:43,400
I informatycy nazywają
to LIFO-- trwać, pierwsze wyszło.

685
00:28:43,400 --> 00:28:45,540
I to rzeczywiście ma
ciekawe aplikacje.

686
00:28:45,540 --> 00:28:50,090
To nie koniecznie tak oczywiste, jak niektóre
Inne, ale może w istocie być użyteczne

687
00:28:50,090 --> 00:28:54,040
i może, w rzeczywistości, być stosowane
w kilka różnych sposobów.

688
00:28:54,040 --> 00:28:58,550
>> Tak jeden, i rzeczywiście, niech
mnie nie do nurkowania w tym.

689
00:28:58,550 --> 00:28:59,860
Zróbmy to zamiast.

690
00:28:59,860 --> 00:29:03,700
Spójrzmy na taki, który jest prawie
sam pomysł, ale jest to trochę bardziej sprawiedliwy.

691
00:29:03,700 --> 00:29:04,200
Prawda?

692
00:29:04,200 --> 00:29:07,560
Jeśli jesteś jednym z tych chłopców wentylatorów lub
dziewczyny, które naprawdę lubi produktów Apple

693
00:29:07,560 --> 00:29:10,130
i obudził się o 3:00
w kolejce w jakimś sklepie

694
00:29:10,130 --> 00:29:14,150
aby uzyskać najnowsze iPhone, ty
mógł w kolejce tak.

695
00:29:14,150 --> 00:29:15,800
>> Teraz kolejka jest bardzo celowo nazwane.

696
00:29:15,800 --> 00:29:18,190
To dlatego, że nie ma linii
niektóre sprawiedliwości do niego.

697
00:29:18,190 --> 00:29:18,690
Prawda?

698
00:29:18,690 --> 00:29:21,690
To będzie rodzaj dupy, jeśli masz
tam pierwszy w Apple Store

699
00:29:21,690 --> 00:29:25,700
ale są skutecznie najniżej
Pracownicy tacy, bo wtedy firmy Apple

700
00:29:25,700 --> 00:29:28,189
pop ostatnią osobę, która
rzeczywiście dostał w kolejce.

701
00:29:28,189 --> 00:29:31,230
Więc stosów i kolejek, nawet jeśli między
funkcjonalnie są niby same--

702
00:29:31,230 --> 00:29:33,105
to tylko ta kolekcja
zasobów to

703
00:29:33,105 --> 00:29:36,210
będzie się rozwijać i shrink-- istnieje
ten aspekt jej uczciwość,

704
00:29:36,210 --> 00:29:39,634
przynajmniej w świecie rzeczywistym,
gdzie można wykonywać operacje

705
00:29:39,634 --> 00:29:40,800
różnią się zasadniczo.

706
00:29:40,800 --> 00:29:43,360
Stack-- kolejka
rather-- mówi się, że

707
00:29:43,360 --> 00:29:45,320
dwie operacje: brak kolejek i d kolejce.

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

709
00:29:46,341 --> 00:29:48,090
Czy można je nazwać
dowolną ilość rzeczy.

710
00:29:48,090 --> 00:29:50,770
Ale po prostu chcesz zrobić
Pogląd, że jeden jest dodanie

711
00:29:50,770 --> 00:29:53,230
i jeden jest ostatecznie odjęcie.

712
00:29:53,230 --> 00:29:58,840
>> Teraz pod maską, zarówno w stos
i kolejki mogą być realizowane w jaki sposób?

713
00:29:58,840 --> 00:30:01,390
Nie pójdziemy do kodu
dlatego, że wyższy poziom

714
00:30:01,390 --> 00:30:03,387
Chodzi o to, jakby bardziej oczywista.

715
00:30:03,387 --> 00:30:04,470
Chodzi mi o to, co ludzie robią?

716
00:30:04,470 --> 00:30:07,030
Jeśli jestem pierwszą osobą w Apple
Przechowywać i to przednie drzwi,

717
00:30:07,030 --> 00:30:08,130
wiesz, mam zamiar tu stać.

718
00:30:08,130 --> 00:30:09,750
A obok osoby
będziemy tu stać.

719
00:30:09,750 --> 00:30:11,500
A obok osoby
będziemy tu stać.

720
00:30:11,500 --> 00:30:13,792
Więc co struktura danych
nadaje się do kolejki?

721
00:30:13,792 --> 00:30:14,542
>> Publiczność: kolejka.

722
00:30:14,542 --> 00:30:15,667
DAVID MALAN: Cóż, kolejka.

723
00:30:15,667 --> 00:30:16,390
Jasne.

724
00:30:16,390 --> 00:30:16,920
Co jeszcze?

725
00:30:16,920 --> 00:30:17,600
>> Odbiorcy: związane lista.

726
00:30:17,600 --> 00:30:18,990
>> DAVID MALAN: związane
listy można wdrożyć.

727
00:30:18,990 --> 00:30:22,500
I związane lista jest dobre, bo to
może rosnąć dowolnie długo, w przeciwieństwie

728
00:30:22,500 --> 00:30:24,880
się o jakąś stałą liczbę
ludzi w sklepie.

729
00:30:24,880 --> 00:30:27,030
Ale być może stała liczba
miejsc jest zgodny z prawem.

730
00:30:27,030 --> 00:30:30,350
Bo jeśli mają tylko jak 20
iPhone w pierwszym dniu, a może

731
00:30:30,350 --> 00:30:33,930
muszą tylko tablicę rozmiarów
20 do reprezentowania kolejkę, która

732
00:30:33,930 --> 00:30:37,070
tylko powiedzieć, teraz gdy już zacznie mówić
o tych problemach na wyższym poziomie,

733
00:30:37,070 --> 00:30:38,890
można go wdrożyć
w dowolnej liczbie sposobów.

734
00:30:38,890 --> 00:30:42,030
I nie ma chyba po prostu będzie
być kompromis w czasie i przestrzeni

735
00:30:42,030 --> 00:30:43,950
czy tylko w swoim własnym kodzie złożoności.

736
00:30:43,950 --> 00:30:45,380
>> Co stosie?

737
00:30:45,380 --> 00:30:48,190
Cóż, stos, widzieliśmy też
może być tylko te tace.

738
00:30:48,190 --> 00:30:50,007
I można zaimplementować to tablica.

739
00:30:50,007 --> 00:30:53,090
Ale w pewnym momencie, jeśli używać tablicy,
co się wydarzy do podajników

740
00:30:53,090 --> 00:30:54,173
starasz się odłożyć?

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

742
00:30:55,170 --> 00:30:55,670
Dobrze.

743
00:30:55,670 --> 00:30:57,490
Będziesz tylko
być w stanie iść tak wysoko.

744
00:30:57,490 --> 00:31:00,156
I myślę, że oni są w Mather
rzeczywiście wpuszczone w tym otwarciu.

745
00:31:00,156 --> 00:31:01,950
Tak naprawdę, to prawie
jak Mather korzysta

746
00:31:01,950 --> 00:31:03,783
Tablica stałej wielkości,
bo tylko to możliwe

747
00:31:03,783 --> 00:31:08,302
zmieścić tak wiele tac w tym otworze
ściana w dół poniżej kolana ludzi.

748
00:31:08,302 --> 00:31:10,010
I tak, że może być
Mówi się, że tablica,

749
00:31:10,010 --> 00:31:14,300
ale możemy z pewnością, że wdrożenie
ogólnie z połączonej listy.

750
00:31:14,300 --> 00:31:16,390
>> Cóż, co innego struktury danych?

751
00:31:16,390 --> 00:31:18,760
Pozwól mi wyciągnąć jeden inny wizualny tutaj.

752
00:31:18,760 --> 00:31:24,710
Coś takiego, jak o tym tutaj?

753
00:31:24,710 --> 00:31:28,920
Dlaczego to może być przydatne, aby nie mieć
coś tak wyjątkowego jak trie, która

754
00:31:28,920 --> 00:31:32,370
widzieliśmy miał te bardzo szerokie węzłów,
z których każdy jest w tablicy?

755
00:31:32,370 --> 00:31:35,740
Ale co, jeśli robimy coś więcej
po prostu, jak stare drzewo genealogiczne w szkole,

756
00:31:35,740 --> 00:31:38,110
u których węzły tutaj
jest po prostu zapisywania numeru.

757
00:31:38,110 --> 00:31:42,180
Zamiast nazwy lub potomka
jest po prostu zapisywania numeru takiego.

758
00:31:42,180 --> 00:31:45,250
>> Cóż, w żargonu używamy
struktury danych jest zarówno stara

759
00:31:45,250 --> 00:31:49,510
i drzewa, gdzie trie, ponownie, jest
tylko jeden, którego węzły są tablice,

760
00:31:49,510 --> 00:31:51,680
jest jeszcze to, co mogłoby
korzystać z podstawówki

761
00:31:51,680 --> 00:31:53,860
kiedy się rodzinę
tree-- liście i korzeń

762
00:31:53,860 --> 00:31:57,250
drzewa i dzieci
rodzic i jego rodzeństwo.

763
00:31:57,250 --> 00:32:03,670
I moglibyśmy zaimplementować drzewo,
Na przykład, jak po prostu, jak to.

764
00:32:03,670 --> 00:32:07,420
Drzewa, czy to jako węzła, jeden z
te koła, które ma wiele,

765
00:32:07,420 --> 00:32:09,947
to nie będzie mieć
jeden wskaźnik, ale dwa.

766
00:32:09,947 --> 00:32:11,780
I jak tylko dodać
Drugi wskaźnik, można

767
00:32:11,780 --> 00:32:13,905
rzeczywiście mogą teraz sortowania
danych dwuwymiarowych

768
00:32:13,905 --> 00:32:14,780
struktury w pamięci.

769
00:32:14,780 --> 00:32:16,660
Podobnie jak dwuwymiarowy
tablica, można

770
00:32:16,660 --> 00:32:18,904
mieć rodzaj z dwuwymiarowym
listy, ale te związane

771
00:32:18,904 --> 00:32:20,820
że zgodne z wzorcem
gdzie nie ma cykli.

772
00:32:20,820 --> 00:32:24,487
To naprawdę jeden z drzewa
dziadkowie aż tutaj, a następnie

773
00:32:24,487 --> 00:32:27,320
niektórzy rodzice i dzieci oraz
wnuki i prawnuki.

774
00:32:27,320 --> 00:32:28,370
i tak dalej.

775
00:32:28,370 --> 00:32:32,390
>> Ale to, co naprawdę o tym zbyt schludny,
tylko dokuczać Ci trochę kodu,

776
00:32:32,390 --> 00:32:35,370
wycofanie z rekurencji
jakiś czas temu, przy czym

777
00:32:35,370 --> 00:32:38,220
można napisać funkcję, która nazywa siebie.

778
00:32:38,220 --> 00:32:41,140
To jest piękne okazja
zaimplementować coś

779
00:32:41,140 --> 00:32:42,920
jak rekursji, ponieważ uważają to.

780
00:32:42,920 --> 00:32:43,860
>> To jest drzewo.

781
00:32:43,860 --> 00:32:48,040
I byłem trochę jak z odbytu
Włożyłem liczby całkowite na ulicę.

782
00:32:48,040 --> 00:32:51,020
Tak bardzo, że ma specjalny
name-- poszukiwania binarnego drzewa.

783
00:32:51,020 --> 00:32:53,460
Teraz słyszałem o binarny
szukać, ale można

784
00:32:53,460 --> 00:32:55,180
działa wstecz od nazwy tego stwora?

785
00:32:55,180 --> 00:32:59,280
Co to jest wzór jak ja
wstawione liczby całkowite do tego drzewa?

786
00:32:59,280 --> 00:33:00,696
To nie jest przypadkowe.

787
00:33:00,696 --> 00:33:01,570
Jest jakiś wzór.

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

789
00:33:02,090 --> 00:33:03,370
>> Publiczność: Mniejsze po lewej stronie.

790
00:33:03,370 --> 00:33:03,690
>> DAVID MALAN: Tak.

791
00:33:03,690 --> 00:33:05,062
Mniejsze są po lewej stronie.

792
00:33:05,062 --> 00:33:06,270
Większe z nich są po prawej stronie.

793
00:33:06,270 --> 00:33:12,940
Takie, że stwierdzenie jest prawdziwe
rodzic jest większa niż jego lewej dziecka,

794
00:33:12,940 --> 00:33:14,850
ale mniej niż prawo dziecka.

795
00:33:14,850 --> 00:33:17,750
I że sam jest jeszcze
rekurencyjna definicja słowna

796
00:33:17,750 --> 00:33:20,500
dlatego, że można zastosować
sama logika dla każdego węzła

797
00:33:20,500 --> 00:33:23,080
i to tylko dna
się, wariant podstawowy, jeśli Ciebie

798
00:33:23,080 --> 00:33:25,740
będzie, po trafieniu jednego z
liście, że tak powiem,

799
00:33:25,740 --> 00:33:28,580
Urlop gdzie dzieci nie ma dalej.

800
00:33:28,580 --> 00:33:30,614
>> Teraz, jak można znaleźć numer 44?

801
00:33:30,614 --> 00:33:32,280
Można by zacząć od korzeni i powiedzieć, hm.

802
00:33:32,280 --> 00:33:35,690
55 nie jest 44 Więc nie chcę iść
prawo czy chcę iść w lewo?

803
00:33:35,690 --> 00:33:37,190
Cóż, oczywiście chcesz iść w lewo.

804
00:33:37,190 --> 00:33:40,060
I tak to jest jak telefon
przykład książki w poszukiwaniu binarnym

805
00:33:40,060 --> 00:33:41,099
bardziej ogólnie.

806
00:33:41,099 --> 00:33:43,390
Ale my jej realizacji
teraz trochę bardziej dynamicznie

807
00:33:43,390 --> 00:33:45,339
niż tablica może pozwolić.

808
00:33:45,339 --> 00:33:48,130
I faktycznie, jeśli chcesz wyglądać
w kodzie, na pierwszy rzut oka na pewno.

809
00:33:48,130 --> 00:33:49,671
Wygląda na to cała masa linii.

810
00:33:49,671 --> 00:33:51,220
Ale to pięknie proste.

811
00:33:51,220 --> 00:33:54,490
Jeśli chcesz zaimplementować funkcję
Wyszukiwarka nazywany w życiu, którego celem

812
00:33:54,490 --> 00:33:57,290
jest poszukiwanie wartości
jak n, liczba całkowita,

813
00:33:57,290 --> 00:34:01,756
a ty przeszedł w jednej pointer--
wskaźnik do węzła korzeni

814
00:34:01,756 --> 00:34:04,380
raczej z tego drzewa, z którego,
można uzyskać dostęp do wszystkiego innego,

815
00:34:04,380 --> 00:34:08,850
zauważyć, jak w prosty sposób
można zaimplementować logikę.

816
00:34:08,850 --> 00:34:10,880
Jeśli drzewo jest null,
oczywiście, że nie ma.

817
00:34:10,880 --> 00:34:11,880
Miejmy tylko return false.

818
00:34:11,880 --> 00:34:12,000
Prawda?

819
00:34:12,000 --> 00:34:14,040
Jeśli strony to nic,
nic tam nie ma.

820
00:34:14,040 --> 00:34:17,900
>> Inaczej, gdy n jest mniejsze niż
drzewo strzałka strzałka n-- teraz n

821
00:34:17,900 --> 00:34:20,670
Przypomnijmy wprowadziliśmy Super
krótko drugi dzień,

822
00:34:20,670 --> 00:34:25,100
i że po prostu oznacza de odniesienie do
wskaźnik i spojrzeć na polu o nazwie n.

823
00:34:25,100 --> 00:34:27,690
Więc oznacza to, że tam i
popatrz na pole o nazwie n.

824
00:34:27,690 --> 00:34:33,810
Więc jeśli n, wartość dostaniemy, jest mniej
od wartości na drzewach całkowitej,

825
00:34:33,810 --> 00:34:35,449
gdzie chcesz iść?

826
00:34:35,449 --> 00:34:36,389
Proszę skręcić w lewo.

827
00:34:36,389 --> 00:34:37,780
>> Więc zauważyć rekurencji.

828
00:34:37,780 --> 00:34:39,860
Jestem returning-- nieprawda.

829
00:34:39,860 --> 00:34:40,989
Nie fałszywe.

830
00:34:40,989 --> 00:34:45,670
Wracam niezależnie odpowiedź
jest z wezwaniem do siebie, przechodząc

831
00:34:45,670 --> 00:34:50,100
ponownie n, który jest zbędny,
ale to, co teraz jest nieco inaczej?

832
00:34:50,100 --> 00:34:51,989
Jak mam co problem mniejsze?

833
00:34:51,989 --> 00:34:54,920
Jestem przekazując jako drugi
Argument, nie korzeniem drzewa,

834
00:34:54,920 --> 00:34:59,616
ale lewa dziecko w tym przypadku.

835
00:34:59,616 --> 00:35:00,990
Więc jestem przechodząc w lewym dziecka.

836
00:35:00,990 --> 00:35:04,720
>> Tymczasem, jeżeli n jest większe niż
węzeł Jestem obecnie patrząc na,

837
00:35:04,720 --> 00:35:06,690
Szukam prawą stronę.

838
00:35:06,690 --> 00:35:10,880
Indziej, jeśli drzewo nie jest null, a
Jeśli element nie jest na lewo

839
00:35:10,880 --> 00:35:13,240
i to nie jest w prawo,
co jest cudownie przypadek?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Mamy rzeczywiście znaleźć węzeł w
pytanie, i tak wracamy prawda.

842
00:35:18,440 --> 00:35:21,490
>> Więc mamy tylko powierzchownie
teraz niektóre z tych struktur danych.

843
00:35:21,490 --> 00:35:24,370
W problemem ustawić pięć będziesz
zbadać te jeszcze dalej,

844
00:35:24,370 --> 00:35:27,250
i będziesz mieć twój projekt
Wybór, jak go o to.

845
00:35:27,250 --> 00:35:30,250
Co chciałbym zawrzeć na
jest tylko 30 sekund zwiastun

846
00:35:30,250 --> 00:35:32,080
tego, co czeka w przyszłym tygodniu i poza nią.

847
00:35:32,080 --> 00:35:35,390
>> Jak begin-- szczęście może po
think-- nasze przejście powoli

848
00:35:35,390 --> 00:35:38,680
ze świata C i niższej
Poziom, szczegóły realizacji

849
00:35:38,680 --> 00:35:42,090
do świata, w którym możemy wziąć na
pewnik, że w końcu ktoś inny ma

850
00:35:42,090 --> 00:35:44,010
realizowane te dane
konstrukcje dla nas,

851
00:35:44,010 --> 00:35:47,570
i zaczniemy rozumieć
Prawdziwy świat środki realizacji

852
00:35:47,570 --> 00:35:50,560
programów opartych na sieci Web i
strony internetowe bardziej ogólnie

853
00:35:50,560 --> 00:35:52,910
a także bardzo bezpieczeństwa
Implikacje, że mamy tylko

854
00:35:52,910 --> 00:35:54,850
zaczęły zarysować powierzchnię.

855
00:35:54,850 --> 00:35:57,320
Oto, co nas czeka
w najbliższych dniach.

856
00:35:57,320 --> 00:36:00,480
>> [ODTWARZANIE]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -On Przyszedł z wiadomością,
z protokołem wszystkim jego własne.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Przyszedł na świat okrutny
firewalle, routery niedbały,

861
00:36:30,894 --> 00:36:33,368
i zagrożenia znacznie gorsze niż śmierć.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Jest szybki.

864
00:36:36,236 --> 00:36:37,980
On jest silny.

865
00:36:37,980 --> 00:36:42,830
On jest protokół TCP / IP, a on ma swój adres.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Warriors of the Net".

868
00:36:48,074 --> 00:36:49,660
[KONIEC ODTWARZANIE]

869
00:36:49,660 --> 00:36:50,910
DAVID MALAN: Już w przyszłym tygodniu.

870
00:36:50,910 --> 00:36:51,880
Mamy zobaczysz wtedy.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[ODTWARZANIE]

873
00:36:56,060 --> 00:36:59,240
-A Teraz, "głębokich myśli"
przez Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Zawsze zaczyna
wykłady z "dobrze."

876
00:37:05,820 --> 00:37:08,750
Dlaczego nie "Oto rozwiązanie
do problemu w tym tygodniu zestaw "

877
00:37:08,750 --> 00:37:12,180
lub "Dajemy wam wszystkim?"

878
00:37:12,180 --> 00:37:13,380
[ROZEŚMIANY]

879
00:37:13,380 --> 00:37:15,530
[KONIEC ODTWARZANIE]