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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Więc w CS50, omówiliśmy
wiele różnych struktur danych,

3
00:00:08,300 --> 00:00:09,180
dobrze?

4
00:00:09,180 --> 00:00:11,420
Widzieliśmy tablic i związane
Wykazy i tabele mieszania,

5
00:00:11,420 --> 00:00:15,210
i stara, stosy i kolejki.

6
00:00:15,210 --> 00:00:17,579
Będziemy również dowiedzieć się trochę
o drzewach i hałd,

7
00:00:17,579 --> 00:00:20,120
ale tak naprawdę to wszystko po prostu skończyć
się jako wariacje na temat.

8
00:00:20,120 --> 00:00:22,840
Tam naprawdę są te
rodzaj czterech podstawowych idei

9
00:00:22,840 --> 00:00:25,190
że wszystko jeszcze może sprowadzać się do.

10
00:00:25,190 --> 00:00:28,150
Tablice, związane listy,
hash tabele i próbuje.

11
00:00:28,150 --> 00:00:30,720
I tak jak powiedziałem,
są wariacje na ich temat,

12
00:00:30,720 --> 00:00:32,720
ale jest to dość
dużo się dzieje na podsumowanie

13
00:00:32,720 --> 00:00:38,140
wszystko, co mamy zamiar rozmawiać
o w tej klasie pod względem C

14
00:00:38,140 --> 00:00:40,140
>> Ale jak to wszystko miarą się, prawda?

15
00:00:40,140 --> 00:00:44,265
Mówiliśmy o plusy i minusy
każdego w oddzielnych filmy z nimi,

16
00:00:44,265 --> 00:00:46,390
ale jest wiele numerów
wyrzucenie wokół.

17
00:00:46,390 --> 00:00:48,723
Istnieje wiele ogólnie
myśli wyrzucenie wokół.

18
00:00:48,723 --> 00:00:51,950
Spróbujmy i konsolidacji
to w jednym miejscu.

19
00:00:51,950 --> 00:00:55,507
Miejmy ważyć argumenty przeciwko
minusy, i rozważyć

20
00:00:55,507 --> 00:00:57,340
których struktura danych
może być właściwym danych

21
00:00:57,340 --> 00:01:01,440
Struktura dla danej sytuacji,
niezależnie od rodzaju danych, które przechowujemy.

22
00:01:01,440 --> 00:01:06,625
Nie koniecznie zawsze trzeba
korzystać z super szybkie wstawienie, usunięcie,

23
00:01:06,625 --> 00:01:10,761
i wyszukiwanie z trie Jeśli naprawdę
nie dbają o wstawianie i usuwanie

24
00:01:10,761 --> 00:01:11,260
za dużo.

25
00:01:11,260 --> 00:01:13,968
Jeśli musisz po prostu szybko losowo
dostęp, może tablica jest lepiej.

26
00:01:13,968 --> 00:01:15,340
Więc destylować, że.

27
00:01:15,340 --> 00:01:18,530
Porozmawiajmy o każdym z czterech
główne rodzaje struktur danych

28
00:01:18,530 --> 00:01:21,720
że rozmawialiśmy o, i
po prostu zobaczyć, kiedy mogą być dobre,

29
00:01:21,720 --> 00:01:23,340
a gdy nie mogą one być tak dobrze.

30
00:01:23,340 --> 00:01:24,610
Więc zacznijmy z tablicami.

31
00:01:24,610 --> 00:01:27,300
Więc wstawiania, że ​​trochę źle.

32
00:01:27,300 --> 00:01:31,350
>> Wstawiania na końcu tablicy jest OK,
jeśli budujemy tablicę jak idziemy.

33
00:01:31,350 --> 00:01:33,570
Ale jeśli trzeba wstawić
elementów w środku,

34
00:01:33,570 --> 00:01:35,550
że powrót do wstawienia
sortowanie, jest wiele

35
00:01:35,550 --> 00:01:37,510
przesunięcia, aby dopasować element tam.

36
00:01:37,510 --> 00:01:41,170
I tak, jeśli chcemy, aby wstawić
wszędzie, ale do końca tablicy,

37
00:01:41,170 --> 00:01:43,590
to chyba nie tak wielki.

38
00:01:43,590 --> 00:01:46,710
>> Podobnie, usunięcie, jeśli nie jesteśmy
usunięcie z końca tablicy,

39
00:01:46,710 --> 00:01:49,810
Prawdopodobnie również nie tak wielki, jeśli
nie chcemy zostawić puste luki,

40
00:01:49,810 --> 00:01:50,790
które zwykle nie mamy.

41
00:01:50,790 --> 00:01:54,700
Chcemy, aby usunąć element, a
to rodzaj zrobić to ponownie przyjemny.

42
00:01:54,700 --> 00:01:57,670
I tak usuwanie elementów z
tablica, również nie jest tak wielka.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, choć, jest wielki.

44
00:01:58,820 --> 00:02:00,920
Mamy swobodny dostęp,
Stała czasu wyszukiwania.

45
00:02:00,920 --> 00:02:03,800
My po prostu powiedzieć, siedem, i idziemy
do tablicy relokacji siedem.

46
00:02:03,800 --> 00:02:05,907
Mówimy, 20, z podróży do
Tablica przeniesienie 20.

47
00:02:05,907 --> 00:02:07,240
Nie mamy do iteracji po drugiej.

48
00:02:07,240 --> 00:02:08,630
To dość dobre.

49
00:02:08,630 --> 00:02:11,020
>> Tablice są stosunkowo łatwe do sortowania.

50
00:02:11,020 --> 00:02:14,040
Za każdym razem, rozmawialiśmy o sortowaniu
Algorytm, takie jak wybór rodzaju,

51
00:02:14,040 --> 00:02:18,820
Sortowanie przez wstawianie, sortowanie bąbelkowe, scalanie
rodzaju, zawsze stosowane tablice to zrobić,

52
00:02:18,820 --> 00:02:21,860
bo tablice są dość łatwe do
sortowania, w porównaniu do struktury danych

53
00:02:21,860 --> 00:02:22,970
widzieliśmy do tej pory.

54
00:02:22,970 --> 00:02:24,320
>> Są także stosunkowo niewielka.

55
00:02:24,320 --> 00:02:25,695
Nie ma dużo dodatkowej przestrzeni.

56
00:02:25,695 --> 00:02:29,210
Po prostu uchylenie dokładnie tyle
jak trzeba trzymać swoje dane,

57
00:02:29,210 --> 00:02:30,320
i to dość dużo.

58
00:02:30,320 --> 00:02:33,180
Więc oni są bardzo małe
i skuteczne w ten sposób.

59
00:02:33,180 --> 00:02:36,000
Ale inny minusem, choć,
jest to, że są one ustalone rozmiary.

60
00:02:36,000 --> 00:02:38,630
Musimy zadeklarować dokładnie jak
duża chcemy, aby nasza tablica będzie,

61
00:02:38,630 --> 00:02:39,940
a my tylko jeden strzał na niego.

62
00:02:39,940 --> 00:02:41,280
Nie możemy rosną i kurczą się.

63
00:02:41,280 --> 00:02:44,582
>> Jeśli musimy powiększać lub zmniejszać go, że
trzeba zadeklarować zupełnie nową tablicę,

64
00:02:44,582 --> 00:02:47,750
skopiować wszystkie elementy z
pierwsza tablica w drugiej tablicy.

65
00:02:47,750 --> 00:02:51,410
A jeśli przeliczył, że
czas, musimy zrobić to ponownie.

66
00:02:51,410 --> 00:02:52,760
Nie tak świetne.

67
00:02:52,760 --> 00:02:58,750
Więc tablice nie dają nam elastyczność
mieć zmienną liczbę elementów.

68
00:02:58,750 --> 00:03:01,320
>> Z połączonej listy,
wstawiania jest całkiem proste.

69
00:03:01,320 --> 00:03:03,290
My po prostu przykleić na przednią.

70
00:03:03,290 --> 00:03:04,892
Skreślenie jest również bardzo proste.

71
00:03:04,892 --> 00:03:06,100
Musimy znaleźć elementy.

72
00:03:06,100 --> 00:03:07,270
Które wiążą się wyszukiwanie.

73
00:03:07,270 --> 00:03:10,270
>> Ale po znalezieniu elementu
szukasz, wszystko co musisz zrobić,

74
00:03:10,270 --> 00:03:12,830
to zmienić wskaźnik,
ewentualnie dwa, jeśli masz

75
00:03:12,830 --> 00:03:15,151
związane list-- podwójnie
związane lista, rather--

76
00:03:15,151 --> 00:03:16,650
a następnie można po prostu zwolnić węzeł.

77
00:03:16,650 --> 00:03:18,399
Nie musisz się zmieniać
wszystko wokół.

78
00:03:18,399 --> 00:03:22,090
Po prostu zmienić dwa wskaźniki,
więc to dość szybko.

79
00:03:22,090 --> 00:03:23,470
>> Lookup jest złe, choć, tak?

80
00:03:23,470 --> 00:03:26,280
Aby nas znaleźć
elementem w połączonej listy,

81
00:03:26,280 --> 00:03:29,154
pojedynczo lub podwójnie związany,
musimy szukać go liniowym.

82
00:03:29,154 --> 00:03:32,320
Musimy zacząć od początku i
przenieść się do końca, albo zaczynają się od ruchu końcowego

83
00:03:32,320 --> 00:03:33,860
na początku.

84
00:03:33,860 --> 00:03:35,474
Nie mamy już swobodny dostęp.

85
00:03:35,474 --> 00:03:37,265
Więc jeśli robimy
wiele poszukiwań, może

86
00:03:37,265 --> 00:03:39,830
połączonej listy nie jest
aż tak dobre dla nas.

87
00:03:39,830 --> 00:03:43,750
>> Są również bardzo
trudne do sortowania, prawda?

88
00:03:43,750 --> 00:03:45,666
Tylko w ten sposób można
Naprawdę sortować połączonej listy

89
00:03:45,666 --> 00:03:47,870
znajduje się rozwiązać to jak skonstruować go.

90
00:03:47,870 --> 00:03:50,497
Ale jeśli rozwiązać to jak ty
skonstruowanie go, nie jesteś już

91
00:03:50,497 --> 00:03:51,830
co więcej szybkich wstawki.

92
00:03:51,830 --> 00:03:53,746
Nie jesteś tylko sklejaniu
rzeczy na froncie.

93
00:03:53,746 --> 00:03:55,710
Musisz znaleźć
właściwym miejscu, aby umieścić go,

94
00:03:55,710 --> 00:03:57,820
i wówczas wstawiania
staje się niemal tak źle

95
00:03:57,820 --> 00:03:59,390
jak wstawianie do tablicy.

96
00:03:59,390 --> 00:04:03,130
Więc związane listy nie są
tak wielka, do sortowania danych.

97
00:04:03,130 --> 00:04:05,830
>> Są także bardzo mały, rozmiar mądry.

98
00:04:05,830 --> 00:04:08,496
Podwójnie związany nieco listy
większe niż pojedynczo związane listy,

99
00:04:08,496 --> 00:04:10,620
które są nieco większe
niż tablic, ale to nie jest

100
00:04:10,620 --> 00:04:13,330
ogromna ilość niewykorzystanego miejsca.

101
00:04:13,330 --> 00:04:18,730
Więc jeśli przestrzeń jest na wagę złota, ale
Nie bardzo intensywne premii,

102
00:04:18,730 --> 00:04:22,180
to może być to właściwa droga.

103
00:04:22,180 --> 00:04:23,330
>> Hash tabele.

104
00:04:23,330 --> 00:04:25,850
Wstawiania w tabeli mieszania
jest dość oczywiste.

105
00:04:25,850 --> 00:04:26,980
Jest to proces dwuetapowy.

106
00:04:26,980 --> 00:04:30,700
Najpierw musimy uruchomić nasze dane przez
funkcja skrótu, aby uzyskać kod skrótu,

107
00:04:30,700 --> 00:04:37,550
a następnie wstawić element do
tablica mieszająca w tym miejscu kod skrótu.

108
00:04:37,550 --> 00:04:40,879
>> Wykreślenie, podobny do połączonej listy,
jest łatwe po znalezieniu elementu.

109
00:04:40,879 --> 00:04:43,170
Musisz go najpierw znaleźć,
ale wtedy, gdy go usunąć,

110
00:04:43,170 --> 00:04:45,128
po prostu trzeba wymieniać
kilka wskazówek,

111
00:04:45,128 --> 00:04:47,250
jeśli używasz oddzielnego łańcuchowym.

112
00:04:47,250 --> 00:04:49,942
Jeśli używasz sondowania,
lub jeśli nie jesteś

113
00:04:49,942 --> 00:04:51,650
za pomocą łączenia w ogóle
w tabeli mieszania,

114
00:04:51,650 --> 00:04:53,040
Skreślenie jest rzeczywiście bardzo proste.

115
00:04:53,040 --> 00:04:57,134
Wszystko, co musisz zrobić, to obliczenia skrótu
Dane, a następnie udać się do tego miejsca.

116
00:04:57,134 --> 00:04:58,925
I zakładając, że nie
mają żadnych kolizji,

117
00:04:58,925 --> 00:05:01,650
będziesz w stanie bardzo szybko usunąć.

118
00:05:01,650 --> 00:05:04,930
>> Teraz, wyszukiwanie jest gdzie rzeczy
trochę bardziej skomplikowane.

119
00:05:04,930 --> 00:05:06,910
To średnio lepiej
niż związane list.

120
00:05:06,910 --> 00:05:09,560
Jeśli używasz łańcuchowym,
nadal masz połączonej listy,

121
00:05:09,560 --> 00:05:13,170
co oznacza, że ​​wciąż mają
wyszukiwarka szkodą połączonej listy.

122
00:05:13,170 --> 00:05:18,390
Ale dlatego, że przyjmowanie połączone
lista i dzielenie go na 100 lub 1000

123
00:05:18,390 --> 00:05:25,380
lub n elementów w tabeli hash, jesteś
Listy są powiązane z jednym n-te wielkości.

124
00:05:25,380 --> 00:05:27,650
Oni wszyscy są znacznie mniejsze.

125
00:05:27,650 --> 00:05:32,080
Masz n związane list zamiast
jednej połączonej listy rozmiarze n.

126
00:05:32,080 --> 00:05:34,960
>> I tak to w świecie rzeczywistym stała
Czynnikiem, który na ogół

127
00:05:34,960 --> 00:05:39,730
nie mówić o złożoności go w czasie,
czy rzeczywiście zrobić tutaj różnicę.

128
00:05:39,730 --> 00:05:43,020
Więc wyszukiwania jest wciąż liniowa
szukaj jeśli używasz łańcuchowym,

129
00:05:43,020 --> 00:05:46,780
jednak długość listy
jesteś przeszukiwania

130
00:05:46,780 --> 00:05:50,080
Jest bardzo, bardzo krótki w porównaniu.

131
00:05:50,080 --> 00:05:52,995
Ponownie, jeśli sortowanie jest Twój
Naszym celem, hash stołu

132
00:05:52,995 --> 00:05:54,370
prawdopodobnie nie właściwa droga.

133
00:05:54,370 --> 00:05:56,830
Wystarczy użyć tablicę, jeśli sortowania
jest naprawdę ważne dla Ciebie.

134
00:05:56,830 --> 00:05:58,590
>> I mogą uruchomić gama rozmiarów.

135
00:05:58,590 --> 00:06:01,640
Trudno powiedzieć, czy
tablica mieszająca jest małe czy duże,

136
00:06:01,640 --> 00:06:04,110
bo to zależy od tego,
jak duży tabeli mieszania jest.

137
00:06:04,110 --> 00:06:07,340
Jeśli tylko będzie przechowywanie
pięć elementów w tabeli mieszania,

138
00:06:07,340 --> 00:06:10,620
i masz tabeli mieszania
z 10.000 elementów w nim,

139
00:06:10,620 --> 00:06:12,614
jesteś prawdopodobnie tracić dużo przestrzeni.

140
00:06:12,614 --> 00:06:15,030
Kontrast jest ci mogą również
mają bardzo kompaktowe tabel mieszania,

141
00:06:15,030 --> 00:06:18,720
ale mniejsza tabela hash dostaje,
dłuższy każda z tych połączonych list

142
00:06:18,720 --> 00:06:19,220
wystąpią.

143
00:06:19,220 --> 00:06:22,607
I tak naprawdę nie ma sposobu, aby zdefiniować
dokładnie rozmiar tabeli mieszania,

144
00:06:22,607 --> 00:06:24,440
ale to chyba bezpieczne
powiedzieć, że jest na ogół

145
00:06:24,440 --> 00:06:27,990
będzie większe niż związane
Lista przechowywania tych samych danych,

146
00:06:27,990 --> 00:06:30,400
ale mniejszą niż trie.

147
00:06:30,400 --> 00:06:32,720
>> I stara się czwarty
z tych struktur

148
00:06:32,720 --> 00:06:34,070
że rozmawialiśmy o.

149
00:06:34,070 --> 00:06:36,450
Wstawianie do trie jest złożona.

150
00:06:36,450 --> 00:06:38,400
Istnieje wiele dynamicznych
alokacji pamięci,

151
00:06:38,400 --> 00:06:40,780
szczególnie na początku
jak zaczynasz budować.

152
00:06:40,780 --> 00:06:43,700
Ale to stała czasowa.

153
00:06:43,700 --> 00:06:47,690
To tylko element ludzki
tutaj sprawia, że ​​trudne.

154
00:06:47,690 --> 00:06:53,250
Mając na spotkanie z pustego wskaźnika, malloc
przestrzeń, tam, ewentualnie malloc przestrzeń

155
00:06:53,250 --> 00:06:54,490
stamtąd ponownie.

156
00:06:54,490 --> 00:06:58,880
Rodzaj czynnika zastraszania
wskaźniki w dynamicznej alokacji pamięci

157
00:06:58,880 --> 00:07:00,130
jest przeszkodą, aby wyczyścić.

158
00:07:00,130 --> 00:07:04,550
Ale gdy już straciła gola, wprowadzenie
faktycznie jest dość prosty,

159
00:07:04,550 --> 00:07:06,810
i to na pewno jest stała czasowa.

160
00:07:06,810 --> 00:07:07,680
>> Skreślenie jest łatwe.

161
00:07:07,680 --> 00:07:11,330
Wszystko, co musisz zrobić, to przejdź w dół
Kilka wskazówek i bezpłatnym węzła,

162
00:07:11,330 --> 00:07:12,420
więc to całkiem nieźle.

163
00:07:12,420 --> 00:07:13,930
Lookup jest również dość szybko.

164
00:07:13,930 --> 00:07:16,780
Opiera się tylko na
długość danych.

165
00:07:16,780 --> 00:07:19,924
Więc jeśli wszystkie dane jest
pięć ciągi znaków,

166
00:07:19,924 --> 00:07:22,590
na przykład, jesteś przechowywania pięć
ciągi znaków w twojej trie,

167
00:07:22,590 --> 00:07:25,439
to tylko pięć kroków do
znaleźć to, czego szukasz.

168
00:07:25,439 --> 00:07:28,480
Pięć jest tylko czynnikiem stałym, więc
znowu, wstawianie, usuwanie i wyszukiwanie

169
00:07:28,480 --> 00:07:31,670
tutaj są stałe w czasie, skutecznie.

170
00:07:31,670 --> 00:07:34,880
>> Inną rzeczą jest to, że trie jest
faktycznie niby już klasyfikowane, prawda?

171
00:07:34,880 --> 00:07:36,800
Na podstawie tego, jak jesteśmy
wstawianie elementów,

172
00:07:36,800 --> 00:07:40,060
przechodząc litera po literze
Klucz lub cyfra po cyfrze klucza,

173
00:07:40,060 --> 00:07:45,084
zwykle, twój trie kończy się
rodzaj klasyfikowane jak go zbudować.

174
00:07:45,084 --> 00:07:47,250
Tak naprawdę nie robi
sensu myśleć o sortowaniu

175
00:07:47,250 --> 00:07:49,874
w ten sam sposób myślimy o
to z tablicami lub powiązanych list,

176
00:07:49,874 --> 00:07:51,070
lub tabele mieszania.

177
00:07:51,070 --> 00:07:54,780
Ale w pewnym sensie, twój
trie jest klasyfikowane jak przejść.

178
00:07:54,780 --> 00:07:58,630
>> Wadą Oczywiście, jest to, że
trie szybko staje się ogromna.

179
00:07:58,630 --> 00:08:02,970
Z każdego punktu połączenia, to polubisz
have-- jeśli klucz składa się z cyfr,

180
00:08:02,970 --> 00:08:04,880
masz 10 Inne
miejsca można przejść, które

181
00:08:04,880 --> 00:08:07,490
Oznacza to, że każdy węzeł
zawiera informacje

182
00:08:07,490 --> 00:08:11,440
o danych, które chcesz przechowywać
na tym węźle, plus 10 wskaźników.

183
00:08:11,440 --> 00:08:14,430
Które na CS50 IDE, jest 80 bajtów.

184
00:08:14,430 --> 00:08:17,220
Więc to co najmniej 80 bajtów
każdy węzeł, aby tworzyć,

185
00:08:17,220 --> 00:08:19,240
i że nawet nie licząc danych.

186
00:08:19,240 --> 00:08:24,950
A jeśli węzły są
litery zamiast cyfr,

187
00:08:24,950 --> 00:08:27,825
teraz masz 26 wskazówek
z każdego miejsca.

188
00:08:27,825 --> 00:08:32,007
I 26 razy 8 jest chyba 200
bajtów, czy coś takiego.

189
00:08:32,007 --> 00:08:33,840
I masz kapitału
i lowercase-- można

190
00:08:33,840 --> 00:08:35,381
zobaczyć, gdzie mam zamiar z tym, prawda?

191
00:08:35,381 --> 00:08:37,500
Węzły mogą się naprawdę
duży, a więc trie

192
00:08:37,500 --> 00:08:40,470
Sam, ogólnie rzecz biorąc, można
uzyskać naprawdę duże, zbyt.

193
00:08:40,470 --> 00:08:42,630
Więc jeśli przestrzeń jest na wysokim
premii w systemie,

194
00:08:42,630 --> 00:08:45,830
trie może nie być właściwym sposobem
przejść, chociaż jego inne zalety

195
00:08:45,830 --> 00:08:47,780
wchodzą w grę.

196
00:08:47,780 --> 00:08:48,710
Jestem Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
To CS50.

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