1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> Głośnik 1: Dobra, więc to jest
CS50 To jest koniec tygodnia pięć.

3
00:00:15,860 --> 00:00:19,220
I pamiętam, że ostatnim razem
zaczął patrząc na hodowcy danych

4
00:00:19,220 --> 00:00:22,310
Struktury, które rozpoczęły się rozwiązać
Problemy, które zaczęły wprowadzać

5
00:00:22,310 --> 00:00:25,640
nowe problemy, ale kluczem do tego
był typem gwintu, że

6
00:00:25,640 --> 00:00:27,940
zacząłem robić od węzła do węzła.

7
00:00:27,940 --> 00:00:30,085
Więc to jest oczywiście
pojedynczo połączonej listy.

8
00:00:30,085 --> 00:00:31,960
I pojedynczo związany,
Mam na myśli nie tylko jeden

9
00:00:31,960 --> 00:00:33,380
wątku pomiędzy każdym z tych węzłów.

10
00:00:33,380 --> 00:00:35,890
Okazuje się, że można zrobić hodowcy
takie rzeczy jak podwójnie związane list

11
00:00:35,890 --> 00:00:38,470
w którym masz strzałę
dzieje się w obu kierunkach, co

12
00:00:38,470 --> 00:00:40,320
może pomóc w pewnych korzyści.

13
00:00:40,320 --> 00:00:42,000
Ale to rozwiązało problem?

14
00:00:42,000 --> 00:00:43,500
Jaki problem miał rozwiązać ten problem?

15
00:00:43,500 --> 00:00:46,620
Dlaczego dbamy w poniedziałek?

16
00:00:46,620 --> 00:00:49,820
Dlaczego, w teorii, nie dbamy w poniedziałek?

17
00:00:49,820 --> 00:00:50,630
Co to robi?

18
00:00:50,630 --> 00:00:51,950
>> PUBLICZNOŚCI: Możemy dynamicznie zmienić jego rozmiar.

19
00:00:51,950 --> 00:00:53,740
>> Głośnik 1: OK, więc możemy
dynamicznie zmienić jego rozmiar.

20
00:00:53,740 --> 00:00:54,710
Brawo was obu.

21
00:00:54,710 --> 00:00:57,560
Więc można dynamicznie zmieniać rozmiar tego
Struktura danych, natomiast tablicy,

22
00:00:57,560 --> 00:01:00,760
Przypomnijmy, co musisz wiedzieć
priori, jak chcesz dużo miejsca

23
00:01:00,760 --> 00:01:03,870
a jeśli potrzebujesz trochę więcej
Przestrzeń, jesteś trochę pecha.

24
00:01:03,870 --> 00:01:05,560
Musisz stworzyć zupełnie nową tablicę.

25
00:01:05,560 --> 00:01:07,893
Musisz się przenieść wszystkie swoje
dane z jednego do drugiego,

26
00:01:07,893 --> 00:01:10,600
w końcu uwolnić starą tablicę
jeśli możesz, a następnie kontynuować.

27
00:01:10,600 --> 00:01:13,891
Które po prostu czuje się bardzo kosztowne i bardzo
nieskuteczne, a nawet może być.

28
00:01:13,891 --> 00:01:14,890
Ale to nie jest dobre.

29
00:01:14,890 --> 00:01:18,180
Płacimy cenę, co było jednym
z bardziej oczywistych cenach mamy

30
00:01:18,180 --> 00:01:20,550
zapłacić za pomocą połączonej listy?

31
00:01:20,550 --> 00:01:22,825
>> PUBLICZNOŚCI: Musimy wykorzystać
podwójna przestrzeń dla każdego z nich.

32
00:01:22,825 --> 00:01:25,200
1 głośnik: Tak, tak, musimy
co najmniej dwukrotnie więcej przestrzeni.

33
00:01:25,200 --> 00:01:27,700
W rzeczywistości, zdałem sobie sprawę, ten obraz na
nawet trochę mylące,

34
00:01:27,700 --> 00:01:32,200
ze względu na CS50 IDE w wielu nowoczesnych
komputery, wskaźnik lub adres

35
00:01:32,200 --> 00:01:33,700
Nie ma w istocie cztery bajty.

36
00:01:33,700 --> 00:01:36,090
Jest to bardzo często są
dni osiem bajtów, które

37
00:01:36,090 --> 00:01:38,530
Oznacza dno najbardziej
prostokąty tam w rzeczywistości

38
00:01:38,530 --> 00:01:40,900
to rodzaj dwa razy
duży jak co ja wyciągnąć,

39
00:01:40,900 --> 00:01:44,409
co oznacza, że ​​używasz trzy razy
dużo miejsca, jak możemy mieć inaczej.

40
00:01:44,409 --> 00:01:46,700
Obecnie w tym samym czasie, jesteśmy
jeszcze mówić bajtów, prawda?

41
00:01:46,700 --> 00:01:49,140
My nie musi mówić
MB lub GB,

42
00:01:49,140 --> 00:01:51,000
chyba tych danych struktur uzyskać duże.

43
00:01:51,000 --> 00:01:54,510
>> I tak dzisiaj zaczynamy rozważać
jak możemy zbadać dane

44
00:01:54,510 --> 00:01:57,310
bardziej efektywne, jeśli w
Fakt dane robi się coraz większy.

45
00:01:57,310 --> 00:02:00,360
Ale spróbujmy canonicalize
Pierwsze operacje

46
00:02:00,360 --> 00:02:02,460
że można to zrobić na nich
rodzaje struktur danych.

47
00:02:02,460 --> 00:02:04,790
Więc coś jak powiązane
Lista ogólnie popiera

48
00:02:04,790 --> 00:02:07,514
operacji jak usuwanie,
włóż i wyszukiwania.

49
00:02:07,514 --> 00:02:08,639
I co mam na myśli?

50
00:02:08,639 --> 00:02:11,222
To tylko oznacza, że ​​zwykle,
jeśli ludzie są przy użyciu połączonej listy,

51
00:02:11,222 --> 00:02:14,287
oni lub ktoś wdrożył
funkcje, takie jak usuwanie, wstawianie,

52
00:02:14,287 --> 00:02:16,120
i wyszukiwania, dzięki czemu można
rzeczywiście coś zrobić

53
00:02:16,120 --> 00:02:18,030
użyteczne struktury danych.

54
00:02:18,030 --> 00:02:20,760
Więc rzućmy okiem
w jaki sposób możemy wdrożyć

55
00:02:20,760 --> 00:02:24,530
niektóre kodują listy połączonej w sposób następujący.

56
00:02:24,530 --> 00:02:27,885
>> Więc to tylko niektóre kod C,
nawet kompletny program

57
00:02:27,885 --> 00:02:29,260
że bardzo szybko bita.

58
00:02:29,260 --> 00:02:32,300
To nie jest online w dystrybucji
Kod, ponieważ nie będzie właściwie prowadzony.

59
00:02:32,300 --> 00:02:33,790
Zauważmy jednak, mam po prostu
o komentarz powiedział:

60
00:02:33,790 --> 00:02:36,130
kropka kropka kropka, jest coś
tam, kropka kropka kropka, coś tam.

61
00:02:36,130 --> 00:02:38,410
I niech to wystarczy spojrzeć na
co soczyste części są.

62
00:02:38,410 --> 00:02:40,790
Więc na linii trzech,
Przypomnijmy, że to jest teraz

63
00:02:40,790 --> 00:02:45,960
Zaproponowaliśmy deklarując węzeł ostatni
razem z tych prostokątnych przedmiotów.

64
00:02:45,960 --> 00:02:48,790
Ma int, że zadzwonimy N,
ale możemy nazwać to coś,

65
00:02:48,790 --> 00:02:51,920
a następnie gwiazdą węzeł struktura zwana dalej.

66
00:02:51,920 --> 00:02:55,520
I żeby była jasność, że druga
linii, w wierszu szóstym, co to jest?

67
00:02:55,520 --> 00:02:57,930
Co on robi dla nas?

68
00:02:57,930 --> 00:03:01,044
Bo to na pewno wygląda bardziej
tajemnicze, niż naszych zwykłych zmiennych.

69
00:03:01,044 --> 00:03:02,740
>> PUBLICZNOŚCI: To sprawia, że ​​przejście na jednego.

70
00:03:02,740 --> 00:03:04,650
>> Głośnik 1: To sprawia, że ​​przejście na jednego.

71
00:03:04,650 --> 00:03:08,580
A dokładniej,
będzie przechowywać adres

72
00:03:08,580 --> 00:03:11,582
węzła, że ​​to znaczy być
semantycznie obok niego, prawda?

73
00:03:11,582 --> 00:03:13,540
Więc to nie będzie
musi przenieść wszystko.

74
00:03:13,540 --> 00:03:15,290
To po prostu będzie
przechowywania wartości, która jest

75
00:03:15,290 --> 00:03:17,170
będzie adres
pewnego innego węzła,

76
00:03:17,170 --> 00:03:20,810
i dlatego mamy powiedział struct
gwiazda węzeł, gwiazda oznaczająca

77
00:03:20,810 --> 00:03:22,370
wskaźnik lub adres.

78
00:03:22,370 --> 00:03:26,390
OK, więc teraz, jeśli założymy, że mamy
to N dla nas dostępne, i niech

79
00:03:26,390 --> 00:03:29,490
Zakładam, że ktoś inny ma
włożona cała masa liczb całkowitych

80
00:03:29,490 --> 00:03:30,400
w połączonej listy.

81
00:03:30,400 --> 00:03:35,640
I że związane lista jest
wskazywanego przez pewnym momencie

82
00:03:35,640 --> 00:03:39,040
zmienna o nazwie lista to
przeszedł tu jako parametr,

83
00:03:39,040 --> 00:03:43,120
jak mam go o linię
14 wdrażania wyszukiwanie?

84
00:03:43,120 --> 00:03:45,990
Innymi słowy, jeśli jestem realizacji
Funkcja, której celem w życiu

85
00:03:45,990 --> 00:03:48,889
jest podjęcie int a potem
początek połączonej listy,

86
00:03:48,889 --> 00:03:50,430
które jest wskaźnikiem do połączonej listy.

87
00:03:50,430 --> 00:03:52,992
Podobnie jak pierwszy, który myślę, że David
był wolontariuszem w poniedziałek,

88
00:03:52,992 --> 00:03:54,700
był wskazując na
cała związana lista,

89
00:03:54,700 --> 00:03:57,820
to tak, jakby przekazujemy
David jako naszego argumentu tutaj.

90
00:03:57,820 --> 00:03:59,990
Jak mamy go o przejeżdżające tą listę?

91
00:03:59,990 --> 00:04:04,640
Cóż, okazuje się, że nawet jeśli
Wskaźniki są stosunkowo nowe teraz do nas,

92
00:04:04,640 --> 00:04:07,010
możemy to zrobić stosunkowo
wprost.

93
00:04:07,010 --> 00:04:09,500
>> Mam zamiar iść do przodu i
zadeklarować zmienną tymczasową, że

94
00:04:09,500 --> 00:04:12,364
umownie jest po prostu będzie
być nazywany wskaźnikiem lub PTR,

95
00:04:12,364 --> 00:04:14,030
ale można je nazwać jak chcesz.

96
00:04:14,030 --> 00:04:16,470
I mam zamiar zainicjować
że na początku listy.

97
00:04:16,470 --> 00:04:20,050
Tak więc można trochę pomyśleć o tym
jak mnie nauczyciela na drugi dzień,

98
00:04:20,050 --> 00:04:23,580
rodzaj wskazując na kogoś
wśród naszych ludzi jako wolontariuszy.

99
00:04:23,580 --> 00:04:26,470
Więc jestem tymczasową zmienną, która jest
po prostu wskazując na to samo

100
00:04:26,470 --> 00:04:31,390
że nasz przypadkowo nazwany
Wolontariusz Dawid również wskazanie.

101
00:04:31,390 --> 00:04:35,440
Teraz, gdy wskaźnik jest
nie jest pusta, ponieważ odzyskanie

102
00:04:35,440 --> 00:04:40,350
że null jest jakaś specjalna wartość sentinel
rozgranicza koniec listy

103
00:04:40,350 --> 00:04:44,280
tak, a ja nie jestem wskazując na
ziemi jak nasz ostatni wolontariusz

104
00:04:44,280 --> 00:04:47,190
było, idziemy do przodu
i wykonaj następujące czynności.

105
00:04:47,190 --> 00:04:51,820
Jeśli pointer-- i teraz niby chcą
na to, co zrobiliśmy z uczniem

106
00:04:51,820 --> 00:04:57,410
structure-- jeśli wskaźnik kropka obok
equals-- raczej, jeśli wskaźnik dot N równa

107
00:04:57,410 --> 00:05:02,290
wynosi zmienna N, przy czym
Argument, że został przekazany,

108
00:05:02,290 --> 00:05:05,370
to chcę iść do przodu
i powiedzieć return true.

109
00:05:05,370 --> 00:05:11,020
Znalazłem numer N wewnątrz od
jeden z węzłów w moim połączonej listy.

110
00:05:11,020 --> 00:05:13,500
Ale kropka nie
Prace w tym kontekście

111
00:05:13,500 --> 00:05:17,260
ponieważ wskaźnik, PTR, jest
rzeczywiście wskaźnik, adres,

112
00:05:17,260 --> 00:05:20,632
faktycznie może cudownie
używać wreszcie kawałek składni

113
00:05:20,632 --> 00:05:22,590
tego rodzaju marek
intuicyjny sens i rzeczywiście

114
00:05:22,590 --> 00:05:27,870
użyj strzałek tutaj, co oznacza, przejść od
że adres do liczby całkowitej tam w.

115
00:05:27,870 --> 00:05:30,160
Więc to jest bardzo podobne w
Duch do operatora kropki,

116
00:05:30,160 --> 00:05:33,860
ale dlatego, że wskaźnik nie jest wskaźnikiem
a nie rzeczywista sama struktura,

117
00:05:33,860 --> 00:05:35,380
po prostu użyj strzałki.

118
00:05:35,380 --> 00:05:40,620
>> Tak więc, jeśli bieżący węzeł I,
zmienna tymczasowa, wskazuję na

119
00:05:40,620 --> 00:05:43,060
Nie dotyczy to, co chcę zrobić?

120
00:05:43,060 --> 00:05:45,910
Cóż, z moich ochotników
że mieliśmy tutaj na drugi dzień,

121
00:05:45,910 --> 00:05:49,710
jeśli mój pierwszy ludzki nie jest tym, że
chcą, a może drugi ludzki nie jest

122
00:05:49,710 --> 00:05:52,660
jeden chcę, a trzeci, ja
trzeba zachować fizycznie ruchu.

123
00:05:52,660 --> 00:05:54,690
Podobnie jak w jaki sposób krok po kroku listy?

124
00:05:54,690 --> 00:05:57,470
Kiedy mieliśmy tablicę, ciebie
po prostu tak jak ja plus plus.

125
00:05:57,470 --> 00:06:03,660
Jednak w tym przypadku, wystarczy
to wskaźnik, dostaje, wskaźnik obok.

126
00:06:03,660 --> 00:06:07,580
Innymi słowy, obok pola
jest jak wszyscy opuścili ręce

127
00:06:07,580 --> 00:06:10,880
że nasi ochotnicy w poniedziałek
stosował wskazać na inny węzeł.

128
00:06:10,880 --> 00:06:12,890
To były ich najbliższych sąsiadów.

129
00:06:12,890 --> 00:06:17,060
>> Więc jeśli chcę przejść przez liście,
Nie mogę po prostu zrobić ja plus oraz więcej,

130
00:06:17,060 --> 00:06:20,120
Zamiast tego mają do powiedzenia
I, wskaźnik, będzie

131
00:06:20,120 --> 00:06:24,650
równa co następne pole jest
następny obszar, tym następne pole jest

132
00:06:24,650 --> 00:06:28,350
po tych wszystkich lewej ręce
że mieliśmy na scenie, wskazując

133
00:06:28,350 --> 00:06:30,000
niektórych kolejnych wartości.

134
00:06:30,000 --> 00:06:32,590
A jeśli się przez
że cała iteracji,

135
00:06:32,590 --> 00:06:39,330
i wreszcie, uderzę null, nie mając
Znaleziono N jeszcze, po prostu return false.

136
00:06:39,330 --> 00:06:44,100
Więc jeszcze raz, wszystko, co tu robimy,
jak na zdjęciu przed chwilą,

137
00:06:44,100 --> 00:06:47,840
zaczyna od wskazując na
początku listy zapewne.

138
00:06:47,840 --> 00:06:50,970
A następnie sprawdzić, czy wartość
Szukam równa dziewiątej?

139
00:06:50,970 --> 00:06:52,650
Jeśli tak, to powrót prawdziwe i skończę.

140
00:06:52,650 --> 00:06:56,450
Jeśli nie, mogę zaktualizować moją rękę,
AKA wskaźnik, punkt

141
00:06:56,450 --> 00:06:59,540
na miejscu następnego strzały, a
to miejsce następnego strzały,

142
00:06:59,540 --> 00:07:00,480
i następne.

143
00:07:00,480 --> 00:07:03,770
Jestem po prostu spaceru po tej tablicy.

144
00:07:03,770 --> 00:07:06,010
>> Więc jeszcze raz, kogo to obchodzi?

145
00:07:06,010 --> 00:07:07,861
Podobnie jak to, co jest tym składnikiem dla?

146
00:07:07,861 --> 00:07:10,360
Cóż, pamiętam, że wprowadziliśmy
pojęcie stosie, które

147
00:07:10,360 --> 00:07:15,400
Jest to abstrakcyjny typ danych, o ile jest to
nie C rzecz, to nie jest rzecz, CS50,

148
00:07:15,400 --> 00:07:19,430
jest to abstrakcyjny pomysł, idea
układanie rzeczy na jeden na drugim

149
00:07:19,430 --> 00:07:21,820
który może być realizowany
bukiety różne sposoby.

150
00:07:21,820 --> 00:07:25,600
I jeden sposób zaproponowaliśmy był z
tablica, lub z połączonej listy.

151
00:07:25,600 --> 00:07:29,570
I okazuje się, że kanonicznie, A
Stos obsługuje co najmniej dwie operacje.

152
00:07:29,570 --> 00:07:32,320
I słowa Buzz są Push, aby
wcisnąć coś na stos,

153
00:07:32,320 --> 00:07:34,770
jak nowy tacy w
jadalnia, lub pop,

154
00:07:34,770 --> 00:07:39,000
co oznacza usunięcie najwyższy
taca ze stosu w restauracji

155
00:07:39,000 --> 00:07:41,500
hol, a potem być może niektóre
inne operacje, jak również.

156
00:07:41,500 --> 00:07:45,770
Więc jak możemy zdefiniować strukturę
że jesteśmy teraz dzwoniąc stos?

157
00:07:45,770 --> 00:07:50,020
>> Cóż, wszyscy mamy do wymaganej
Składnia do naszej dyspozycji w C. mówię,

158
00:07:50,020 --> 00:07:53,830
daj mi definicję typu
struct wewnątrz stosu,

159
00:07:53,830 --> 00:07:58,030
Mam zamiar powiedzieć, jest tablicą, znaczny
cała masa liczb i wielkości.

160
00:07:58,030 --> 00:08:00,930
Więc innymi słowy, jeśli chcę
zaimplementować to w kodzie,

161
00:08:00,930 --> 00:08:03,830
pozwól mi iść i po prostu rodzaj
narysuj, co to mówi.

162
00:08:03,830 --> 00:08:06,317
Tak to jest, mówiąc: daj mi
struktura, która ma tablicę,

163
00:08:06,317 --> 00:08:09,400
a ja nie wiem, co pojemność jest,
to widocznie niektórzy stała Mam

164
00:08:09,400 --> 00:08:10,858
zdefiniowane w innym miejscu, i to jest w porządku.

165
00:08:10,858 --> 00:08:15,260
Ale załóżmy, że to tylko jedna,
dwa, trzy, cztery, pięć.

166
00:08:15,260 --> 00:08:16,700
Więc pojemność wynosi 5.

167
00:08:16,700 --> 00:08:21,730
Ten element wewnątrz mojego
Struktura będzie nazwany numery.

168
00:08:21,730 --> 00:08:24,020
I wtedy potrzebny
inne zmienne najwidoczniej

169
00:08:24,020 --> 00:08:27,814
Rozmiar że początkowo nazywany idę
zastrzec, jest ustawiany na zero.

170
00:08:27,814 --> 00:08:29,730
Jeśli nie ma nic w
stos, rozmiar wynosi zero,

171
00:08:29,730 --> 00:08:31,420
i to wartości śmieci w liczbach.

172
00:08:31,420 --> 00:08:33,450
Nie mam pojęcia, co tam jeszcze.

173
00:08:33,450 --> 00:08:36,059
>> Więc jeśli chcę naciskać
coś na stos,

174
00:08:36,059 --> 00:08:40,780
Przypuśćmy, że funkcja push zadzwonić, a
Mówię wcisnąć 50, jak liczba 50,

175
00:08:40,780 --> 00:08:44,090
gdzie proponujesz
Rysuję go w tej tablicy?

176
00:08:44,090 --> 00:08:47,124
Istnieje pięć różnych możliwych odpowiedzi.

177
00:08:47,124 --> 00:08:48,790
Gdzie chcesz wcisnąć numer 50?

178
00:08:48,790 --> 00:08:51,899
Jeśli celem tutaj znowu, nazywamy
Funkcja Push, przechodzi w kłótnię

179
00:08:51,899 --> 00:08:52,940
50, gdzie mogę umieścić go?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Pięć possible-- 20% szans
zgadywać poprawnie.

182
00:08:59,052 --> 00:08:59,896
Tak?

183
00:08:59,896 --> 00:09:00,740
>> PUBLICZNOŚCI: Daleko w prawo.

184
00:09:00,740 --> 00:09:01,990
>> Głośnik 1: Daleko w prawo.

185
00:09:01,990 --> 00:09:08,359
Obecnie istnieje 25% szans
zgadywać poprawnie.

186
00:09:08,359 --> 00:09:09,650
Tak, że faktycznie będzie.

187
00:09:09,650 --> 00:09:12,770
Zgodnie z konwencją, powiem z tablicą,
będzie na ogół zaczynają się w lewo,

188
00:09:12,770 --> 00:09:14,519
ale z pewnością mogą
rozpoczyna się na prawo.

189
00:09:14,519 --> 00:09:17,478
Więc spoiler tutaj byłoby jestem
prawdopodobnie będzie zwrócić go po lewej stronie,

190
00:09:17,478 --> 00:09:20,060
tak jak w normalnej tablicy gdzie
I zacząć chodzić lewej do prawej.

191
00:09:20,060 --> 00:09:21,780
Ale czy można odwrócić
arytmetyka, w porządku.

192
00:09:21,780 --> 00:09:23,060
To nie tylko konwencjonalne.

193
00:09:23,060 --> 00:09:24,880
OK, muszę zrobić jeden
więcej Zmiana chociaż.

194
00:09:24,880 --> 00:09:27,710
Teraz kiedy pchnął coś
na stosie, co dalej?

195
00:09:27,710 --> 00:09:29,400
>> Dobra, muszę zwiększyć rozmiar.

196
00:09:29,400 --> 00:09:32,600
Więc pozwól mi iść dalej i po prostu
aktualizuje, która była zero.

197
00:09:32,600 --> 00:09:35,950
I zamiast teraz, zamierzam
umieścić w wartości jednego.

198
00:09:35,950 --> 00:09:39,460
A teraz załóżmy, wciskam innym
Numer na stosie, jak 51.

199
00:09:39,460 --> 00:09:42,680
Cóż, muszę zrobić jeszcze jeden
Zmiana, która jest do wielkości dwóch.

200
00:09:42,680 --> 00:09:46,100
I wtedy przypuszczać, wciskam jeden więcej
Numer na stosie, jak 61,

201
00:09:46,100 --> 00:09:52,530
teraz muszę zaktualizować rozmiar jeden
czas i uzyskać wartość 3 jako wielkości.

202
00:09:52,530 --> 00:09:54,690
A teraz załóżmy, nazywam pop.

203
00:09:54,690 --> 00:09:57,250
Teraz pop, zgodnie z konwencją,
nie bierze argument.

204
00:09:57,250 --> 00:10:00,430
W stos, cała
punkt metafory tacy

205
00:10:00,430 --> 00:10:03,450
jest to, że nie masz dyskrecję
przejść się, że tacy, wszystko może zrobić

206
00:10:03,450 --> 00:10:06,330
jest pop najwyższą jednego z
stos, tylko dlatego.

207
00:10:06,330 --> 00:10:08,010
To co robi to struktura danych.

208
00:10:08,010 --> 00:10:12,250
>> Więc w tej logiki, jeśli
powiedzieć, pop, co wypada?

209
00:10:12,250 --> 00:10:13,080
Więc 61.

210
00:10:13,080 --> 00:10:15,402
Więc co tak naprawdę jest komputer
zamiar zrobić w pamięci?

211
00:10:15,402 --> 00:10:16,610
Co mój kod trzeba zrobić?

212
00:10:16,610 --> 00:10:20,330
Co byś zaproponować
zmieniamy się na ekranie?

213
00:10:20,330 --> 00:10:23,410
Co należy zmienić?

214
00:10:23,410 --> 00:10:24,960
Przepraszam?

215
00:10:24,960 --> 00:10:26,334
Więc pozbyć 61.

216
00:10:26,334 --> 00:10:27,500
Mogę więc na pewno to zrobić.

217
00:10:27,500 --> 00:10:28,640
I mogę się pozbyć 61.

218
00:10:28,640 --> 00:10:30,980
A to co innego
Zmiana musi się zdarzyć?

219
00:10:30,980 --> 00:10:33,160
Rozmiar prawdopodobnie ma wrócić do dwóch.

220
00:10:33,160 --> 00:10:34,210
I tak to jest w porządku.

221
00:10:34,210 --> 00:10:36,690
Ale zaraz, wielkość
przed chwilą było trzech.

222
00:10:36,690 --> 00:10:38,240
Zróbmy szybki test dla pewności.

223
00:10:38,240 --> 00:10:41,810
Skąd wiemy, że
chciał się pozbyć z 61?

224
00:10:41,810 --> 00:10:42,760
Ponieważ jesteśmy popping.

225
00:10:42,760 --> 00:10:46,450
I tak mam ten drugi rozmiar własności.

226
00:10:46,450 --> 00:10:48,470
>> Chwileczkę, jestem
myśli z powrotem do tygodnia dwóch

227
00:10:48,470 --> 00:10:51,660
kiedy zaczął mówić o
tablice, gdzie było to miejsce zerowe,

228
00:10:51,660 --> 00:10:55,920
jest to położenie pierwsze, jest to położenie
dwa, to jest położenie trzy, cztery,

229
00:10:55,920 --> 00:10:58,460
wygląda na to,
związek między wielkością

230
00:10:58,460 --> 00:11:02,780
i element, który chcę usunąć
z tablicy wydaje się być tylko co?

231
00:11:02,780 --> 00:11:05,120
Rozmiar minus jeden.

232
00:11:05,120 --> 00:11:07,786
I tak to jest, jak się ludzi
wiemy, 61 jest na pierwszym miejscu.

233
00:11:07,786 --> 00:11:09,160
Jak komputer będzie wiedział?

234
00:11:09,160 --> 00:11:11,701
Gdy kod, gdzie prawdopodobnie
chcesz zrobić jeden rozmiar minus,

235
00:11:11,701 --> 00:11:14,950
ogółem trzy minus jeden jest dwa, a
Oznacza chcemy się pozbyć 61.

236
00:11:14,950 --> 00:11:18,000
I wtedy możemy rzeczywiście aktualizacji
rozmiar tak, że wielkość teraz

237
00:11:18,000 --> 00:11:20,300
idzie od trzech do zaledwie dwóch.

238
00:11:20,300 --> 00:11:24,520
I po prostu być pedantyczny, zamierzam
zaproponować, że skończę, prawda?

239
00:11:24,520 --> 00:11:27,660
Ty zaproponował intuicyjnie
prawidłowo powinno się pozbyć 61.

240
00:11:27,660 --> 00:11:30,700
Ale nie mam rodzaj
rodzaj pozbyć 61?

241
00:11:30,700 --> 00:11:33,790
Mam skutecznie zapomniał
że faktycznie istnieje.

242
00:11:33,790 --> 00:11:37,680
I wracam do PSET4, jeśli czytałeś
artykuł o kryminalistyce, PDF

243
00:11:37,680 --> 00:11:40,780
że mieliśmy wy czytać, lub
odczyta ten tydzień dla PSET4.

244
00:11:40,780 --> 00:11:44,300
Przypomnijmy, że to jest rzeczywiście germane do
cała idea śledczej.

245
00:11:44,300 --> 00:11:47,820
Jaki komputer na ogół nie jest
to po prostu zapomina, gdzie coś jest,

246
00:11:47,820 --> 00:11:51,300
ale nie iść i jak
spróbować zarysować go lub nadpisanie

247
00:11:51,300 --> 00:11:54,560
te bity z zer i jedynek
lub jakiś inny losowy wzór

248
00:11:54,560 --> 00:11:56,690
chyba że samemu to zrobić świadomie.

249
00:11:56,690 --> 00:11:58,930
Więc twoja intuicja była
Dobra, pozbyć 61.

250
00:11:58,930 --> 00:12:00,650
Ale w rzeczywistości, nie musimy się martwić.

251
00:12:00,650 --> 00:12:04,040
Musimy tylko pamiętać, że
to nie poprzez zmianę rozmiaru.

252
00:12:04,040 --> 00:12:05,662
>> Teraz jest problem z tego stosu.

253
00:12:05,662 --> 00:12:07,620
Gdybym przeć rzeczy
na stosie, co jest

254
00:12:07,620 --> 00:12:11,167
oczywiście będzie się działo
W zaledwie kilka czasie chwile?

255
00:12:11,167 --> 00:12:12,500
Jedziemy do zabrakło miejsca.

256
00:12:12,500 --> 00:12:13,580
A co mamy zrobić?

257
00:12:13,580 --> 00:12:14,680
Jesteśmy trochę pijany.

258
00:12:14,680 --> 00:12:19,000
Ta implementacja nie pozwala
nam zmienić rozmiar tablicy, ponieważ za pomocą

259
00:12:19,000 --> 00:12:21,240
składnia, jeśli Ciebie
wracam na tydzień dwa,

260
00:12:21,240 --> 00:12:23,520
kiedy już zadeklarował
wielkość tablicy,

261
00:12:23,520 --> 00:12:26,780
nie widzieliśmy jeszcze, gdzie mechanizm
można zmienić rozmiar tablicy.

262
00:12:26,780 --> 00:12:29,020
I rzeczywiście C nie posiada takiej funkcji.

263
00:12:29,020 --> 00:12:32,524
Jeśli powiesz mi dać pięć
Nths, nazywają ich numery,

264
00:12:32,524 --> 00:12:33,940
to wszystko masz zamiar zdobyć.

265
00:12:33,940 --> 00:12:38,790
Więc teraz zrobić od poniedziałku, mają
zdolność do wyrażania rozwiązanie

266
00:12:38,790 --> 00:12:42,480
choć, po prostu trzeba podkręcić
Definicja naszego stosu

267
00:12:42,480 --> 00:12:46,840
aby nie być pewne zakodowane tablica,
ale po prostu zapisać adres.

268
00:12:46,840 --> 00:12:47,890
>> Teraz, dlaczego to jest?

269
00:12:47,890 --> 00:12:51,690
Teraz po prostu musimy być wygodne,
fakt, że kiedy mój program działa,

270
00:12:51,690 --> 00:12:53,730
Jestem prawdopodobnie będzie
trzeba zapytać człowieka,

271
00:12:53,730 --> 00:12:55,110
ile liczb chcesz przechowywać?

272
00:12:55,110 --> 00:12:56,776
Więc wejście musi skądś pochodzić.

273
00:12:56,776 --> 00:12:59,140
Ale gdy wiem, że
Numer, to mogę po prostu

274
00:12:59,140 --> 00:13:02,470
wykorzystać to, co funkcjonuje dać
mi fragment pamięci?

275
00:13:02,470 --> 00:13:03,580
Można używać malloc.

276
00:13:03,580 --> 00:13:06,710
I mogę powiedzieć dowolną liczbę
bajty Chcę z powrotem do tych Nths.

277
00:13:06,710 --> 00:13:10,910
I wszystko, co mam do przechowywania w liczbach
Zmienna tutaj wewnątrz tej struktury

278
00:13:10,910 --> 00:13:13,480
powinno być to, co?

279
00:13:13,480 --> 00:13:18,440
Co faktycznie idzie do
Liczby w tym scenariuszu?

280
00:13:18,440 --> 00:13:21,300
Tak, wskaźnik do pierwszego
bajt tym fragmencie pamięci,

281
00:13:21,300 --> 00:13:24,940
a bardziej konkretnie, adres
pierwszego z tych bajtów.

282
00:13:24,940 --> 00:13:27,300
Nie ma znaczenia, czy jest to jeden
bajtów lub miliard bajtów,

283
00:13:27,300 --> 00:13:28,890
Po prostu muszę się martwić o pierwszym.

284
00:13:28,890 --> 00:13:31,530
Bo to, co gwarantuje malloc i
moje gwarancje systemu operacyjnego,

285
00:13:31,530 --> 00:13:34,170
jest to, że fragment pamięci I
uzyskać, to będzie graniczyć.

286
00:13:34,170 --> 00:13:35,378
Nie będzie przerwy.

287
00:13:35,378 --> 00:13:38,576
Tak jakbym poprosił o 50
bajtów lub 1000 bajtów,

288
00:13:38,576 --> 00:13:40,450
oni wszystko będzie
z powrotem do tyłu na plecach.

289
00:13:40,450 --> 00:13:44,500
I tak długo, jak pamiętam, jak duży, jak
bardzo prosiłem, wszystko co musisz wiedzieć

290
00:13:44,500 --> 00:13:46,230
Jest to pierwszy taki adres.

291
00:13:46,230 --> 00:13:48,660
>> Więc teraz mamy możliwość w kodzie.

292
00:13:48,660 --> 00:13:51,280
Aczkolwiek, to będzie nas
więcej czasu, aby napisać to w górę,

293
00:13:51,280 --> 00:13:55,900
możemy teraz realokacji, że pamięć
po prostu przechowywania inny adres nie

294
00:13:55,900 --> 00:13:59,060
jeśli chcemy większy lub nawet
mniejszy fragment pamięci.

295
00:13:59,060 --> 00:14:00,170
Więc tutaj na kompromis.

296
00:14:00,170 --> 00:14:01,360
Teraz mamy dynamizm.

297
00:14:01,360 --> 00:14:03,350
Mamy jeszcze
contiguousness ja twierdzę.

298
00:14:03,350 --> 00:14:05,881
Ponieważ malloc da nam
sąsiedni fragment pamięci.

299
00:14:05,881 --> 00:14:08,630
Ale to będzie ból w
szyja dla nas, programista,

300
00:14:08,630 --> 00:14:09,770
faktycznie zakodowanie.

301
00:14:09,770 --> 00:14:10,730
To jest po prostu więcej pracy.

302
00:14:10,730 --> 00:14:13,930
Musimy kod podobny do tego, co było
walić się chwilą.

303
00:14:13,930 --> 00:14:16,120
Bardzo wykonalne, ale dodaje złożoności.

304
00:14:16,120 --> 00:14:19,520
A więc czas developer, programista
Czas jest kolejnym zasobem

305
00:14:19,520 --> 00:14:22,520
że może trzeba wydać
jakiś czas, aby uzyskać nowe funkcje.

306
00:14:22,520 --> 00:14:24,020
I to oczywiście nie ma kolejki.

307
00:14:24,020 --> 00:14:26,227
Nie będziemy w to
jeden na wiele szczegółów.

308
00:14:26,227 --> 00:14:27,560
Ale to jest bardzo podobne w duchu.

309
00:14:27,560 --> 00:14:31,220
Może zaimplementować kolejkę, a
jego odpowiednie operacje,

310
00:14:31,220 --> 00:14:35,660
enqueue lub z kolejki, jak dodać lub usunąć,
to tylko hodowcy sposób powiedzenia to,

311
00:14:35,660 --> 00:14:38,100
enqueue lub z kolejki, co następuje.

312
00:14:38,100 --> 00:14:41,170
Mogę tylko dać sobie struct
że znów ma szereg szereg, w

313
00:14:41,170 --> 00:14:44,000
że znów ma rozmiar,
ale dlaczego teraz trzeba

314
00:14:44,000 --> 00:14:46,940
śledzić przodu kolejki?

315
00:14:46,940 --> 00:14:50,630
Nie musisz wiedzieć
przód mojego stosu.

316
00:14:50,630 --> 00:14:53,570
Cóż, gdybym jeszcze raz na
queue-- niech po prostu trudne

317
00:14:53,570 --> 00:14:57,870
kodować go jako posiadające jak pięć
liczby całkowite tutaj potencjalnie.

318
00:14:57,870 --> 00:15:00,940
Tak więc jest to zero, jeden, dwa, trzy, cztery.

319
00:15:00,940 --> 00:15:03,430
To będzie
znowu numerów.

320
00:15:03,430 --> 00:15:06,940
A to nazwać rozmiar.

321
00:15:06,940 --> 00:15:10,056
>> Dlaczego nie jest wystarczająca
mieć tylko rozmiar?

322
00:15:10,056 --> 00:15:11,680
Cóż, wcisnąć te same numery.

323
00:15:11,680 --> 00:15:14,220
Więc pushed-- I skolejkowany lub pchnął.

324
00:15:14,220 --> 00:15:20,150
Teraz będę enqueue 50, a następnie
51, a następnie 61 i kropka kropka kropka.

325
00:15:20,150 --> 00:15:21,070
Więc to enqueue.

326
00:15:21,070 --> 00:15:23,176
I skolejkowany 50, potem 51, potem 61.

327
00:15:23,176 --> 00:15:25,050
A że wygląda identycznie
do stosu dotąd

328
00:15:25,050 --> 00:15:27,190
poza tym, że trzeba zrobić jedną zmianę.

329
00:15:27,190 --> 00:15:33,680
Muszę zaktualizować ten rozmiar, więc idę
od zera do jednego do dwóch do trzech obecnie.

330
00:15:33,680 --> 00:15:35,760
Jak mogę z kolejki?

331
00:15:35,760 --> 00:15:36,890
Co się dzieje z rozkolejkowania?

332
00:15:36,890 --> 00:15:41,950
Kto powinien spaść do tej listy pierwszej
czy jest to linia w sklepie Apple Store?

333
00:15:41,950 --> 00:15:42,780
Więc 50.

334
00:15:42,780 --> 00:15:44,700
Więc to trochę trudniejsze, tym razem.

335
00:15:44,700 --> 00:15:47,880
Podczas gdy ostatni raz to było super
łatwo po prostu zrobić jeden rozmiar minus,

336
00:15:47,880 --> 00:15:51,440
I dostać się do końca mojej tablicy skutecznie
w którym liczby są, usuwa 61.

337
00:15:51,440 --> 00:15:52,920
Ale nie chcę, aby usunąć 61.

338
00:15:52,920 --> 00:15:55,030
Chcę wziąć 50, który
był tam o 5:00 AM

339
00:15:55,030 --> 00:15:56,790
do linii dla
Nowy iPhone lub cokolwiek.

340
00:15:56,790 --> 00:16:01,200
I tak, aby pozbyć się 50, I
Nie można po prostu to zrobić, prawda?

341
00:16:01,200 --> 00:16:02,547
Mogę wykreślić 50.

342
00:16:02,547 --> 00:16:04,380
Ale tylko, że my
nie muszą być tak analny

343
00:16:04,380 --> 00:16:06,330
jak drapać się lub ukrywanie danych.

344
00:16:06,330 --> 00:16:08,090
Możemy po prostu zapomnieć, gdzie to jest.

345
00:16:08,090 --> 00:16:12,330
>> Ale jeśli mogę zmienić rozmiar teraz
dwa, jest to wystarczające informacje

346
00:16:12,330 --> 00:16:15,711
wiedzieć, co dzieje się w mojej kolejce?

347
00:16:15,711 --> 00:16:16,680
Nie całkiem.

348
00:16:16,680 --> 00:16:19,830
Podobnie jak mój rozmiar jest dwa, ale
skąd kolejka zacząć,

349
00:16:19,830 --> 00:16:22,980
zwłaszcza jeśli nadal mam
te same liczby w pamięci.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Więc trzeba pamiętać
teraz, gdy z przodu jest.

352
00:16:27,090 --> 00:16:29,630
I tak jak proponuje się
nie, będziemy właśnie nazywa

353
00:16:29,630 --> 00:16:33,729
N-ty z przodu, których początkowa
wartość powinna być co?

354
00:16:33,729 --> 00:16:35,270
Zero, tylko początek listy.

355
00:16:35,270 --> 00:16:40,876
Ale teraz oprócz odlicza
rozmiar, po prostu zwiększyć przód.

356
00:16:40,876 --> 00:16:42,000
Teraz tutaj jest inny problem.

357
00:16:42,000 --> 00:16:43,030
Więc po I wracamy.

358
00:16:43,030 --> 00:16:47,520
Załóżmy, że jest to numer
jak 121, 124, a następnie, do cholery,

359
00:16:47,520 --> 00:16:48,610
Jestem miejsca.

360
00:16:48,610 --> 00:16:50,390
Ale zaraz, ja nie.

361
00:16:50,390 --> 00:16:55,630
Więc w tym momencie w historii,
przypuszczać, że rozmiar jest jeden, dwa,

362
00:16:55,630 --> 00:17:00,370
trzy, cztery, więc przypuszczam, że
rozmiar jest cztery, z przodu jest jeden,

363
00:17:00,370 --> 00:17:01,621
tak 51 znajduje się z przodu.

364
00:17:01,621 --> 00:17:04,329
Chcę umieścić inny numer tutaj,
ale, do cholery, mam miejsca.

365
00:17:04,329 --> 00:17:06,710
Ale nie jestem, prawda?

366
00:17:06,710 --> 00:17:11,192
Gdzie mogę umieścić niektóre
Dodatkowym atutem, podobnie jak 171?

367
00:17:11,192 --> 00:17:13,400
Tak, mogłem po prostu rodzaj
wrócić tam, prawda?

368
00:17:13,400 --> 00:17:18,161
A potem przekreślić 50, lub
po prostu zastąpienie go 171.

369
00:17:18,161 --> 00:17:20,410
A jeśli zastanawiacie się, dlaczego
nasze numery, ale tak przypadkowe,

370
00:17:20,410 --> 00:17:24,150
Te elementy są zwykle brane komputer
Kursy nauki w Harvardzie po CS50.

371
00:17:24,150 --> 00:17:27,510
Ale to była dobra optymalizacja,
bo teraz nie jestem marnowania miejsca.

372
00:17:27,510 --> 00:17:30,750
Mam jeszcze do zapamiętania
jak duże to jest to całkowity.

373
00:17:30,750 --> 00:17:31,500
To pięć sumie.

374
00:17:31,500 --> 00:17:33,375
Bo nie chcę
rozpocząć nadpisywanie 51.

375
00:17:33,375 --> 00:17:36,260
Więc teraz jestem jeszcze z miejsca,
tak że ten sam problem jak poprzednio.

376
00:17:36,260 --> 00:17:39,140
Ale można zobaczyć, jak teraz
w kodzie, prawdopodobnie

377
00:17:39,140 --> 00:17:41,910
napisać trochę więcej
Złożoność, aby tak się stało.

378
00:17:41,910 --> 00:17:44,510
I rzeczywiście, jakie operator
w C prawdopodobnie pozwala

379
00:17:44,510 --> 00:17:48,110
magicznie to kołowość zrobić?

380
00:17:48,110 --> 00:17:50,160
Tak operator modulo,
znak procent.

381
00:17:50,160 --> 00:17:53,160
Więc co to za fajne o kolejce,
chociaż utrzymać tablice rysunkowe

382
00:17:53,160 --> 00:17:56,520
jako tych, takich jak linie proste, jeśli Ciebie
rodzaj myśleć o tym, jak zakrzywienie

383
00:17:56,520 --> 00:18:00,341
wokół jak koło, a potem po prostu
intuicyjnie to niby działa psychicznie

384
00:18:00,341 --> 00:18:01,590
Myślę, że trochę bardziej czysto.

385
00:18:01,590 --> 00:18:05,190
Nadal będą musiały wdrożyć
ten model psychicznego w kodzie.

386
00:18:05,190 --> 00:18:07,550
Tak więc nie jest trudno,
doprowadzenie do wdrożenia,

387
00:18:07,550 --> 00:18:12,430
ale nadal stracić size-- raczej
Możliwość zmiany rozmiaru, chyba, że ​​możemy to zrobić.

388
00:18:12,430 --> 00:18:15,310
>> Musimy pozbyć tablicy, możemy
zastąpić go jednym wskaźnikiem,

389
00:18:15,310 --> 00:18:20,010
a następnie gdzieś w moim kodu mam
transmisją, co działać, by tworzyć

390
00:18:20,010 --> 00:18:23,720
tablica zwane numery?

391
00:18:23,720 --> 00:18:26,190
Malloc lub innej podobnej
Funkcja, dokładnie.

392
00:18:26,190 --> 00:18:30,481
Wszelkie pytania dotyczące stosów lub kolejek.

393
00:18:30,481 --> 00:18:30,980
Tak?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Dobre pytanie.

396
00:18:34,240 --> 00:18:35,830
Co modulo należy użyć tutaj.

397
00:18:35,830 --> 00:18:38,520
Tak więc ogólnie, przy użyciu
mod, by to zrobić

398
00:18:38,520 --> 00:18:40,620
z wielkością z
Cała struktura danych.

399
00:18:40,620 --> 00:18:44,120
Więc coś w pięciu lub zdolności, jeżeli
jest to stała, prawdopodobnie jest zaangażowana.

400
00:18:44,120 --> 00:18:47,100
Ale po prostu robi modulo pięć
prawdopodobnie nie jest wystarczające

401
00:18:47,100 --> 00:18:51,380
bo musimy wiedzieć, jak my
owinąć wokół tutaj lub tutaj lub tutaj.

402
00:18:51,380 --> 00:18:54,160
Więc jesteś prawdopodobnie również
będzie chciał zaangażować

403
00:18:54,160 --> 00:18:57,220
rozmiar rzeczy, albo
zmienna z przodu, jak również.

404
00:18:57,220 --> 00:19:00,140
Więc to jest właśnie to stosunkowo
proste wyrażenie arytmetyczne,

405
00:19:00,140 --> 00:19:02,000
ale modulo będzie kluczowym składnikiem.

406
00:19:02,000 --> 00:19:03,330
>> Tak krótki film, jeśli będzie.

407
00:19:03,330 --> 00:19:05,780
Animacja, że ​​niektóre
Ludzie na innej uczelni

408
00:19:05,780 --> 00:19:08,060
ułożyła, że ​​mamy
przystosowane do tej dyskusji.

409
00:19:08,060 --> 00:19:12,630
Polega ona Jack nauki
fakty na temat kolejek i statystyki.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: Dawno, dawno temu,
był facet o imieniu Jack.

412
00:19:21,890 --> 00:19:25,330
Gdy przyszło do nawiązywania przyjaźni,
Jack nie miał dryg.

413
00:19:25,330 --> 00:19:28,220
Więc Jack poszedł porozmawiać z
Najbardziej popularne facet wiedział.

414
00:19:28,220 --> 00:19:30,920
Udał się do Lou i zapytał: Co mam zrobić?

415
00:19:30,920 --> 00:19:33,400
Lou zobaczył, że jego przyjaciel
był bardzo zmartwiony.

416
00:19:33,400 --> 00:19:36,050
Cóż, zaczął po prostu
wyglądają jak jesteś ubrany.

417
00:19:36,050 --> 00:19:38,680
Nie masz żadnych ubrań
z innym spojrzeniem?

418
00:19:38,680 --> 00:19:39,660
Tak, powiedział Jack.

419
00:19:39,660 --> 00:19:40,840
Ja na pewno nie.

420
00:19:40,840 --> 00:19:43,320
Przyjdź do mojego domu i
Pokażę je do Ciebie.

421
00:19:43,320 --> 00:19:44,550
Więc poszedł do Jacka.

422
00:19:44,550 --> 00:19:47,520
I Jack pokazał pole Lou
gdzie trzymał wszystkie swoje koszule,

423
00:19:47,520 --> 00:19:49,260
i jego spodnie i skarpetki.

424
00:19:49,260 --> 00:19:52,290
Lou powiedział: Widzę, że masz
wszystkie ubrania w stos.

425
00:19:52,290 --> 00:19:54,870
Dlaczego nie nosisz niektóre
inni raz na jakiś czas?

426
00:19:54,870 --> 00:19:58,020
>> Jack powiedział, dobrze, kiedy
zdjąć ubrania i skarpetki,

427
00:19:58,020 --> 00:20:00,780
I umyć je i umieścić
je się w polu.

428
00:20:00,780 --> 00:20:03,210
Potem przychodzi następna
rano, a nawet ja skaczę.

429
00:20:03,210 --> 00:20:06,380
Idę do okna i uzyskać
moje ubrania off góry.

430
00:20:06,380 --> 00:20:09,070
Lou szybko zorientował się,
problem z Jackiem.

431
00:20:09,070 --> 00:20:12,080
Trzymał ubrania, płyty CD,
i książek w stosie.

432
00:20:12,080 --> 00:20:14,420
Kiedy dotarł do
coś do czytania lub do noszenia,

433
00:20:14,420 --> 00:20:17,100
że on wybrać górną książkę lub bieliznę.

434
00:20:17,100 --> 00:20:19,500
Potem, kiedy skończył, on
by umieścić go z powrotem.

435
00:20:19,500 --> 00:20:21,970
Powrót byłoby to, na szczycie stosu.

436
00:20:21,970 --> 00:20:24,460
Wiem, że rozwiązanie,
powiedział triumfalny Loud.

437
00:20:24,460 --> 00:20:27,090
Musisz nauczyć się
uruchomić za pomocą kolejki.

438
00:20:27,090 --> 00:20:29,870
Lou wziął ubrania Jacka i
powiesił je w szafie.

439
00:20:29,870 --> 00:20:32,710
A kiedy opróżnił
okno, on po prostu rzucił ją.

440
00:20:32,710 --> 00:20:36,500
>> Potem powiedział, teraz Jack, w końcu
dzień, umieścić swoje ubrania po lewej stronie

441
00:20:36,500 --> 00:20:37,990
kiedy je dalej.

442
00:20:37,990 --> 00:20:41,300
Następnie jutro rano, kiedy
zobaczyć słońca, dostać ubrania

443
00:20:41,300 --> 00:20:43,440
z prawej strony, od końca linii.

444
00:20:43,440 --> 00:20:44,880
Czy nie widzisz? powiedział Lou.

445
00:20:44,880 --> 00:20:46,370
To będzie tak miło.

446
00:20:46,370 --> 00:20:49,770
Będziesz nosić wszystko raz
zanim dwa razy nosić coś.

447
00:20:49,770 --> 00:20:52,670
A wszystko w kolejkach
w swojej szafy i półki,

448
00:20:52,670 --> 00:20:55,160
Jack zaczął odczuwać
bardzo pewny siebie.

449
00:20:55,160 --> 00:20:59,720
Wszystko dzięki Lou i
Jego wspaniała kolejka.

450
00:20:59,720 --> 00:21:01,220
Głośnik 1: Dobrze, że to urocze.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Więc to, co zostało naprawdę dzieje
na pod maską teraz?

453
00:21:10,080 --> 00:21:12,370
Że mamy wskazówki,
że mamy malloc,

454
00:21:12,370 --> 00:21:15,680
że mamy możliwość tworzenia
kawałki pamięci dla siebie

455
00:21:15,680 --> 00:21:16,344
dynamicznie.

456
00:21:16,344 --> 00:21:18,510
Więc jest to, że obraz
dostrzegł dopiero drugi dzień.

457
00:21:18,510 --> 00:21:21,180
Tak naprawdę nie mieszkać
na nim, ale ten obraz

458
00:21:21,180 --> 00:21:24,180
ma już od spodu
kaptur od tygodni.

459
00:21:24,180 --> 00:21:27,050
A więc to oznacza, po prostu
prostokąt, że mamy wyciągnąć,

460
00:21:27,050 --> 00:21:28,180
pamięci komputera.

461
00:21:28,180 --> 00:21:31,850
A może komputer lub CS50
ID, ma gigabajt pamięci lub pamięci RAM

462
00:21:31,850 --> 00:21:33,050
lub dwa gigabajty lub cztery.

463
00:21:33,050 --> 00:21:34,450
To naprawdę nie ma znaczenia.

464
00:21:34,450 --> 00:21:37,240
Twój system operacyjny
System Windows lub Mac OS lub Linux,

465
00:21:37,240 --> 00:21:41,120
zasadniczo umożliwia program
myśleć, że ma dostęp

466
00:21:41,120 --> 00:21:42,982
do całości
pamięci komputera,

467
00:21:42,982 --> 00:21:45,440
chociaż może być uruchomiony
wiele programów na raz.

468
00:21:45,440 --> 00:21:46,990
Tak więc w rzeczywistości, to naprawdę nie działa.

469
00:21:46,990 --> 00:21:49,448
Ale to rodzaj iluzji
podane do wszystkich programów.

470
00:21:49,448 --> 00:21:53,110
Więc jeśli miał dwóch gigabajtów pamięci RAM, to
to, w jaki sposób komputer może myśleć.

471
00:21:53,110 --> 00:21:57,110
>> Teraz jest przypadkiem, jednym z nich
rzeczy, jeden z tych segmentów pamięci,

472
00:21:57,110 --> 00:21:58,350
nazywa stos.

473
00:21:58,350 --> 00:22:01,680
I rzeczywiście, za każdym razem
do tej pory w pisania kodu

474
00:22:01,680 --> 00:22:05,900
, że nazywa się
funkcji, na przykład głównego.

475
00:22:05,900 --> 00:22:08,410
Przypomnijmy, że za każdym razem mam
Rysowane pamięci komputera,

476
00:22:08,410 --> 00:22:10,640
Zawsze zwrócić rodzaj
połowa prostokąta tutaj

477
00:22:10,640 --> 00:22:12,520
i nie przeszkadza rozmawiać
o tym, co powyżej.

478
00:22:12,520 --> 00:22:15,980
Bo gdy głównym nazywa, mam prawo
że masz ten skrawek pamięci

479
00:22:15,980 --> 00:22:16,970
że idzie tutaj.

480
00:22:16,970 --> 00:22:20,650
A jeśli głównym nazywany funkcją
jak swap, oraz wymiany idzie tutaj.

481
00:22:20,650 --> 00:22:23,720
I okazuje się, że to
gdzie jest kończąc.

482
00:22:23,720 --> 00:22:26,277
Na coś, co nazywa stos
wewnątrz pamięci komputera.

483
00:22:26,277 --> 00:22:28,360
Teraz na koniec dnia
to jest po prostu adresy.

484
00:22:28,360 --> 00:22:30,680
To jak bajt zerowy,
bajt jeden bajt 2 mld.

485
00:22:30,680 --> 00:22:33,130
Ale jeśli myślisz o tym
jak tego prostokątnego obiektu,

486
00:22:33,130 --> 00:22:35,130
wszystko robimy na co
Czas nazywamy funkcją jest

487
00:22:35,130 --> 00:22:37,180
warstw nowy kawałek pamięci.

488
00:22:37,180 --> 00:22:41,700
Dajemy tę funkcję kawałek
własnej pamięci pracy.

489
00:22:41,700 --> 00:22:44,490
>> I przypominam sobie teraz, że to jest ważne.

490
00:22:44,490 --> 00:22:46,400
Bo jeśli mamy
coś jak zamiana

491
00:22:46,400 --> 00:22:51,610
oraz dwie zmienne lokalne, takie jak A i B,
możemy zmienić te wartości z jednego i dwóch

492
00:22:51,610 --> 00:22:55,130
do jednego, dwóch i przypominania
że podczas wymiany zwraca,

493
00:22:55,130 --> 00:22:58,330
to tak, jakby ten kawałek
pamięci jest po prostu zniknął.

494
00:22:58,330 --> 00:23:00,080
W rzeczywistości, to nadal
nie forensically.

495
00:23:00,080 --> 00:23:01,940
I coś jeszcze faktycznie istnieje.

496
00:23:01,940 --> 00:23:05,410
Ale koncepcyjnie, to tak
choć to całkowicie zniknęły.

497
00:23:05,410 --> 00:23:10,910
I tak głównym nie zna żadnej pracy
które zostało zrobione w tej funkcji wymiany,

498
00:23:10,910 --> 00:23:14,890
chyba, że ​​jest to rzeczywiście przekazywane w tych
argumenty przez wskaźnik lub przez odniesienie.

499
00:23:14,890 --> 00:23:17,790
Teraz, podstawowym rozwiązaniem
do tego problemu z wymiany

500
00:23:17,790 --> 00:23:19,970
przechodzi rzeczy przez adres.

501
00:23:19,970 --> 00:23:23,250
Ale okazuje się, też, co jest
trwa powyżej tej części

502
00:23:23,250 --> 00:23:26,330
prostokąta cały ten czas jest
jeszcze nie ma więcej pamięci tam.

503
00:23:26,330 --> 00:23:28,790
A kiedy dynamicznie
przydzielić pamięci,

504
00:23:28,790 --> 00:23:32,020
czy to wewnątrz getString, które
robiliśmy dla Ciebie w CS50

505
00:23:32,020 --> 00:23:34,710
biblioteka, lub jeśli faceci
malloc zadzwonić i zapytać

506
00:23:34,710 --> 00:23:37,950
system operacyjny na fragmencie
pamięci, nie pochodzi ze stosu.

507
00:23:37,950 --> 00:23:40,960
Pochodzi z innego miejsca
w pamięci komputera

508
00:23:40,960 --> 00:23:42,220
które nazywa się sterty.

509
00:23:42,220 --> 00:23:43,430
I to nie jest inaczej.

510
00:23:43,430 --> 00:23:44,285
To jest to samo RAM.

511
00:23:44,285 --> 00:23:45,160
To jest ta sama pamięć.

512
00:23:45,160 --> 00:23:49,080
To tylko RAM to się
tam zamiast tutaj.

513
00:23:49,080 --> 00:23:50,750
>> I tak, co to oznacza?

514
00:23:50,750 --> 00:23:53,650
Cóż, jeśli komputer ma
skończoną ilość pamięci

515
00:23:53,650 --> 00:23:57,450
a stos rośnie, więc
mówić, a kupa, zgodnie

516
00:23:57,450 --> 00:23:59,349
do tej strzałki, rośnie w dół.

517
00:23:59,349 --> 00:24:01,140
Innymi słowy, każda
Czas zadzwonić malloc,

518
00:24:01,140 --> 00:24:03,430
jesteś z nich otrzymuje kawałek
pamięć z powyższego

519
00:24:03,430 --> 00:24:06,630
to może trochę niżej, potem trochę
niższe, za każdym razem dzwonić malloc,

520
00:24:06,630 --> 00:24:10,100
kupa, to wykorzystanie,
jest rodzaj uprawy,

521
00:24:10,100 --> 00:24:11,950
coraz bliżej i bliżej do czego?

522
00:24:11,950 --> 00:24:13,382
Stos.

523
00:24:13,382 --> 00:24:14,840
Więc czy to wydawać się dobrym pomysłem?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Chodzi mi o to, gdzie tak naprawdę nie jest jasne,
Co jeszcze można zrobić, jeśli tylko

526
00:24:22,140 --> 00:24:23,910
mają ograniczoną wielkość pamięci.

527
00:24:23,910 --> 00:24:25,200
Ale to jest na pewno złe.

528
00:24:25,200 --> 00:24:27,920
Te dwa strzały są na zasadzie
Crash Course dla siebie.

529
00:24:27,920 --> 00:24:31,930
>> I okazuje się, że facet, ludzie, którzy
są szczególnie dobre z programowaniem,

530
00:24:31,930 --> 00:24:36,140
i próbuje włamać się do komputerów,
może wykorzystać tę rzeczywistość.

531
00:24:36,140 --> 00:24:38,290
W rzeczywistości, rozważmy
mały fragment.

532
00:24:38,290 --> 00:24:41,350
Więc to jest przykład można przeczytać
o bardziej szczegółowo na Wikipedii.

533
00:24:41,350 --> 00:24:43,100
Będziemy wskazywać na Państwa
Artykuł jeśli ciekawi.

534
00:24:43,100 --> 00:24:45,650
Ale jest na ogół atak
znany jako przepełnienie bufora, które

535
00:24:45,650 --> 00:24:49,570
istnieje tak długo, jak ludzie
miały możliwość manipulowania

536
00:24:49,570 --> 00:24:53,120
pamięci komputera, zwłaszcza w C
Więc jest to bardzo arbitralne programu,

537
00:24:53,120 --> 00:24:55,130
ale niech ją przeczytać od dołu do góry.

538
00:24:55,130 --> 00:24:57,650
Główna pod gwiazdkowy argC char argv.

539
00:24:57,650 --> 00:24:59,830
Więc jest to program, który ma
Argumenty wiersza poleceń.

540
00:24:59,830 --> 00:25:03,620
A wszystko podobno jest głównym ma połączenia
funkcja, nazywamy to F dla uproszczenia.

541
00:25:03,620 --> 00:25:04,610
I przechodzi w co?

542
00:25:04,610 --> 00:25:05,490
Argv jednego.

543
00:25:05,490 --> 00:25:09,320
Tak przechodzi się do F, co
Słowo to, że użytkownik wpisze

544
00:25:09,320 --> 00:25:11,500
w wierszu od wyprodukowania
Nazwa programu w ogóle.

545
00:25:11,500 --> 00:25:15,730
Więc tak jak Cezara lub Vigenère które
Może pamiętacie robi argv.

546
00:25:15,730 --> 00:25:16,680
>> Więc co to jest F?

547
00:25:16,680 --> 00:25:19,760
F odbywa się w ciąg
jako jedyny argument,

548
00:25:19,760 --> 00:25:22,100
AKA gwiazdą char, sam
rzeczą, jako ciąg znaków.

549
00:25:22,100 --> 00:25:24,920
I to się nazywa arbitralnie
Pasek w tym przykładzie.

550
00:25:24,920 --> 00:25:27,710
A potem char c 12,
tylko w laika,

551
00:25:27,710 --> 00:25:31,750
co jest char c uchwyt 12 robi dla nas?

552
00:25:31,750 --> 00:25:33,440
Jak to zrobić?

553
00:25:33,440 --> 00:25:36,490
Przydzielania pamięci, w szczególności
12 bajtów do 12 znaków.

554
00:25:36,490 --> 00:25:36,990
Dokładnie.

555
00:25:36,990 --> 00:25:40,000
A następnie w ostatniej linii, wymieszać i
kopiowania, chyba pan nie widział.

556
00:25:40,000 --> 00:25:43,360
To jest kopia ciąg
Funkcja, której celem w życiu

557
00:25:43,360 --> 00:25:48,160
jest skopiować drugi argument
w pierwszym argumentem,

558
00:25:48,160 --> 00:25:51,190
lecz tylko do
Pewna liczba bajtów.

559
00:25:51,190 --> 00:25:53,860
Więc trzeci argument mówi,
ile bajtów należy skopiować?

560
00:25:53,860 --> 00:25:56,720
Długość paska,
co użytkownik wpisał w.

561
00:25:56,720 --> 00:25:59,320
Oraz treść
bar, ten ciąg, są

562
00:25:59,320 --> 00:26:02,330
kopiowane do pamięci wskazał na C

563
00:26:02,330 --> 00:26:04,060
>> Tak więc wydaje się głupie, i ona jest.

564
00:26:04,060 --> 00:26:06,300
Jest to wymyślony przykład,
ale to przedstawiciel

565
00:26:06,300 --> 00:26:10,100
klasy wektorów ataku,
sposób atakuje program.

566
00:26:10,100 --> 00:26:15,050
Wszystko jest w porządku i dobrze, jeśli użytkownik
typy w słowie, które jest 11 znaków

567
00:26:15,050 --> 00:26:18,040
lub mniej, plus backslash zero.

568
00:26:18,040 --> 00:26:22,830
Co zrobić, jeśli użytkownik wpisze więcej niż
11 lub 12 lub 20 lub 50 znaków?

569
00:26:22,830 --> 00:26:25,090
Co znajduje się ten program zrobi?

570
00:26:25,090 --> 00:26:29,360
Potencjalnie seg winy. To się dzieje
ślepo kopiować wszystko w barze się

571
00:26:29,360 --> 00:26:31,750
na jego długości, co jest
dosłownie wszystko w barze,

572
00:26:31,750 --> 00:26:36,307
na adres wskazał na C, ale C
dopiero zapobiegawczo podaje się 12 bajtów.

573
00:26:36,307 --> 00:26:37,640
Ale nie ma dodatkowego wyboru.

574
00:26:37,640 --> 00:26:38,700
Jeśli warunki nie ma.

575
00:26:38,700 --> 00:26:40,580
Nie ma tu kontroli błędów.

576
00:26:40,580 --> 00:26:43,270
>> A więc to, co ten program jest
zamiar zrobić, to po prostu ślepo

577
00:26:43,270 --> 00:26:45,750
skopiować jedno do drugiego.

578
00:26:45,750 --> 00:26:47,880
I tak, jeśli zwracamy tym
jako obraz, oto

579
00:26:47,880 --> 00:26:49,860
tylko skrawek przestrzeni pamięci.

580
00:26:49,860 --> 00:26:53,470
Tak więc zauważyć na dole, że
mają zmienną lokalną bar.

581
00:26:53,470 --> 00:26:57,330
Więc tego wskaźnika, który będzie store--
a tym lokalnym argumentu, który jest

582
00:26:57,330 --> 00:26:58,672
będzie przechowywać pasek ciąg.

583
00:26:58,672 --> 00:27:00,380
I wtedy zauważył tylko
nad nim w stosie

584
00:27:00,380 --> 00:27:02,505
bo za każdym razem prosić
dla pamięci na stosie,

585
00:27:02,505 --> 00:27:04,310
to idzie trochę
ponad to obrazowo,

586
00:27:04,310 --> 00:27:06,270
Ogłoszenie, że mamy 12 bajtów tam.

587
00:27:06,270 --> 00:27:10,690
W lewym górnym jeden jest uchwyt C zero i
prawy dolny uchwyt jest C 11.

588
00:27:10,690 --> 00:27:12,870
To tylko jak komputery
zamiar położyć go na zewnątrz.

589
00:27:12,870 --> 00:27:18,300
Więc po prostu intuicyjnie, jeśli pasek ma więcej
niż 12 znaków w sumie, w tym

590
00:27:18,300 --> 00:27:25,790
odwrotny ukośnik zero, gdzie jest
12 lub wspornik C12 zamiar iść?

591
00:27:25,790 --> 00:27:28,440
Albo raczej, gdzie jest 12
znaków lub 13 znaków,

592
00:27:28,440 --> 00:27:30,900
setna charakter będzie
do końca się na zdjęciu?

593
00:27:30,900 --> 00:27:33,400
Powyżej lub poniżej?

594
00:27:33,400 --> 00:27:36,300
>> Racja, bo choć
sam stos rośnie w górę,

595
00:27:36,300 --> 00:27:39,590
kiedy już umieścić rzeczy w
to, że ze względów konstrukcyjnych,

596
00:27:39,590 --> 00:27:41,294
umieszcza pamięci z góry do dołu.

597
00:27:41,294 --> 00:27:44,460
Więc jeśli masz więcej niż 12 bajtów,
masz zamiar rozpocząć nadpisywanie bar.

598
00:27:44,460 --> 00:27:47,280
Teraz, że to błąd, ale to
naprawdę nie jest wielka sprawa.

599
00:27:47,280 --> 00:27:51,130
Ale to jest wielka sprawa, bo nie ma
więcej rzeczy dzieje się w pamięci.

600
00:27:51,130 --> 00:27:53,074
Więc oto jak może
umieścić komentarzy, być jasne.

601
00:27:53,074 --> 00:27:54,490
Jeśli witam mam wpisane w wierszu.

602
00:27:54,490 --> 00:27:59,330
Backslash zerowa H-E-L-L-O, kończy się w ciągu
te 12 bajtów, a my jesteśmy bardzo bezpieczne.

603
00:27:59,330 --> 00:28:00,330
Wszystko dobrze.

604
00:28:00,330 --> 00:28:03,020
Ale jeśli coś typu
dłużej, potencjalnie to

605
00:28:03,020 --> 00:28:05,860
zamiar wkraść się Spacja.

606
00:28:05,860 --> 00:28:08,405
Ale co gorsza, okazuje
z całym tym czasie,

607
00:28:08,405 --> 00:28:11,530
chociaż nigdy nie mówił o
to, że stos jest używany do innych rzeczy.

608
00:28:11,530 --> 00:28:13,560
To nie tylko zmienne lokalne.

609
00:28:13,560 --> 00:28:15,100
>> C jest językiem bardzo niski poziom.

610
00:28:15,100 --> 00:28:17,810
I jakby potajemnie
wykorzystuje stos również

611
00:28:17,810 --> 00:28:21,260
pamiętać, gdy
Funkcja jest wywoływana, co

612
00:28:21,260 --> 00:28:26,040
adres jest poprzedniej funkcji
więc może wrócić do tej funkcji.

613
00:28:26,040 --> 00:28:29,980
Kiedy więc zamienić główne połączenia między
rzeczy odkładana na stos

614
00:28:29,980 --> 00:28:34,380
nie są po prostu zamienia zmienne lokalne,
lub jego argumenty, także potajemnie pchnął

615
00:28:34,380 --> 00:28:37,510
na stosie, jak pokazano
przez plasterek tutaj

616
00:28:37,510 --> 00:28:40,520
jest adres główny fizycznie
w pamięci komputera,

617
00:28:40,520 --> 00:28:44,180
tak, że podczas wymiany odbywa komputer
wie, że trzeba wrócić do głównego

618
00:28:44,180 --> 00:28:46,760
i zakończenia wykonywania funkcji main.

619
00:28:46,760 --> 00:28:51,960
Więc teraz jest to niebezpieczne, bo jeśli
użytkownik wpisze w dobrze ponad komentarzy,

620
00:28:51,960 --> 00:28:57,030
takie, że wejście użytkownika clobbers
lub nadpisuje ten czerwony punkt,

621
00:28:57,030 --> 00:28:59,820
logicznie, jeśli w komputerze
po prostu będzie ślepo zakładać,

622
00:28:59,820 --> 00:29:03,830
że bajtów, że Red plaster są
adres, na który należy zwrócić,

623
00:29:03,830 --> 00:29:09,020
co, jeśli przeciwnik jest na tyle sprytny, lub
szczęście, aby umieścić sekwencję bajtów

624
00:29:09,020 --> 00:29:13,450
tam, że wygląda jak adres,
ale jest to adres z kodem

625
00:29:13,450 --> 00:29:18,730
że on lub ona chce komputer
wykonać zamiast Głównym?

626
00:29:18,730 --> 00:29:21,670
>> Innymi słowy, jeśli to, co
użytkownik wpisując w wierszu,

627
00:29:21,670 --> 00:29:23,850
nie tylko coś
nieszkodliwe jak cześć,

628
00:29:23,850 --> 00:29:28,210
ale w rzeczywistości jest to odpowiednik kodu
usunąć wszystkie pliki tego użytkownika?

629
00:29:28,210 --> 00:29:30,060
Lub napisz do mnie swoje hasło?

630
00:29:30,060 --> 00:29:31,940
Lub rozpocząć rejestrowanie ich
klawiszy, prawda?

631
00:29:31,940 --> 00:29:34,920
Jest na to sposób, niech przewidują dziś
że mogą wpisywać nie tylko komentarzy

632
00:29:34,920 --> 00:29:36,711
świecie lub ich nazwa,
mogli w zasadzie

633
00:29:36,711 --> 00:29:39,570
przechodzą w kodzie, zer i
z nich, że komputer

634
00:29:39,570 --> 00:29:43,450
błędy zarówno dla kodu i adresem.

635
00:29:43,450 --> 00:29:48,950
Więc choć nieco abstrakcyjnie, jeśli
użytkownik wpisze w tyle kodu kontradyktoryjności

636
00:29:48,950 --> 00:29:52,330
że będziemy tu generalizować
A. jest atak lub przeciwnicy.

637
00:29:52,330 --> 00:29:53,140
Więc po prostu złe rzeczy.

638
00:29:53,140 --> 00:29:55,306
Nie dbamy o
numerów lub zera lub te,

639
00:29:55,306 --> 00:29:59,470
dzisiaj, tak że w końcu
nadpisanie, że czerwony punkt,

640
00:29:59,470 --> 00:30:01,580
zauważyć, że kolejność bajtów.

641
00:30:01,580 --> 00:30:05,020
O 835 C zera osiem zero.

642
00:30:05,020 --> 00:30:08,960
A teraz, jak artykule Wikipedii tutaj
zaproponowała, jeśli teraz zacząć

643
00:30:08,960 --> 00:30:12,460
oznaczania bajtów komputera
pamięci, co w artykule Wikipedia jest

644
00:30:12,460 --> 00:30:19,060
proponującą jest, że to, co jeśli adres
tej górnym lewym bajt jest 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Innymi słowy, jeśli zły to
tyle sprytny ze swoim kodem

646
00:30:22,200 --> 00:30:26,650
faktycznie umieścić numer tutaj
odpowiada adresowi kodu

647
00:30:26,650 --> 00:30:29,180
on wstrzykiwany
do komputera,

648
00:30:29,180 --> 00:30:31,050
Można oszukać komputer
do robienia czegokolwiek.

649
00:30:31,050 --> 00:30:34,140
Usuwanie plików, wysyłanie e-maili
rzeczy, wąchania ruchu,

650
00:30:34,140 --> 00:30:36,710
dosłownie wszystko może być
wtryskiwane do komputera.

651
00:30:36,710 --> 00:30:39,220
I tak przepełnienie bufora
Atak w swej istocie

652
00:30:39,220 --> 00:30:43,530
jest po prostu głupi, głupi
Nadrzędnym tablicy, że

653
00:30:43,530 --> 00:30:45,840
nie mają sprawdzać jego granice.

654
00:30:45,840 --> 00:30:48,850
I to jest to, co jest bardzo niebezpieczne
i jednocześnie potężny

655
00:30:48,850 --> 00:30:52,560
w C jest to, że naprawdę mamy
dostęp do każdego miejsca w pamięci.

656
00:30:52,560 --> 00:30:55,320
To do nas, programistów,
którzy piszą oryginalny kod

657
00:30:55,320 --> 00:30:59,330
aby sprawdzić długość cerować którejkolwiek
macierze, że jesteśmy manipulacji.

658
00:30:59,330 --> 00:31:00,750
Więc być jasne, co to naprawić?

659
00:31:00,750 --> 00:31:03,190
Jeśli cofnąć się do tego
Kod, że nie powinienem tak

660
00:31:03,190 --> 00:31:08,000
zmiana długości paska, co
jeszcze powinien być sprawdzanie?

661
00:31:08,000 --> 00:31:10,620
Co mam robić, aby jeszcze
uniknąć tego ataku w całości?

662
00:31:10,620 --> 00:31:14,110
Nie chcę, aby ślepo powiedzieć
że należy skopiować tyle bajtów

663
00:31:14,110 --> 00:31:16,140
jak długość pręta.

664
00:31:16,140 --> 00:31:18,910
Chcę powiedzieć, skopiować, jak
jak wiele bajtów są w barze

665
00:31:18,910 --> 00:31:24,090
do przydzielona
pamięci lub 12 maksymalnie.

666
00:31:24,090 --> 00:31:27,450
Więc muszę jakąś jeśli warunek
że nie sprawdzić długość paska,

667
00:31:27,450 --> 00:31:32,800
ale jeśli przekracza 12, mamy kod po prostu dysk
12 w maksymalnej możliwej odległości.

668
00:31:32,800 --> 00:31:35,910
W przeciwnym razie, tak zwany bufor
atak przepełnienia może się zdarzyć.

669
00:31:35,910 --> 00:31:38,451
W dolnej części tych preparatów,
Jeśli jesteś ciekaw, aby przeczytać więcej

670
00:31:38,451 --> 00:31:41,200
jest rzeczywisty oryginalny artykuł
jeśli chcesz spojrzeć.

671
00:31:41,200 --> 00:31:44,550
>> Ale teraz, wśród ceny
wypłacane tutaj był nieefektywność.

672
00:31:44,550 --> 00:31:46,680
Tak to było szybkie
niski poziom spojrzenie na to, co

673
00:31:46,680 --> 00:31:49,709
Teraz mogą pojawić się problemy, które
mają dostęp do pamięci komputera.

674
00:31:49,709 --> 00:31:51,750
Ale inny problem, jaki
już natknął się w poniedziałek

675
00:31:51,750 --> 00:31:53,800
właśnie nieefektywność
z połączonej listy.

676
00:31:53,800 --> 00:31:56,019
Jesteśmy z powrotem do czasu linearnego.

677
00:31:56,019 --> 00:31:57,560
Nie mamy już ciągłą tablicę.

678
00:31:57,560 --> 00:31:58,980
Nie mamy swobodny dostęp.

679
00:31:58,980 --> 00:32:00,710
Nie możemy używać notacji nawiasu kwadratowego.

680
00:32:00,710 --> 00:32:04,590
Dosłownie użyć pętli while
jak ten napisałem przed chwilą.

681
00:32:04,590 --> 00:32:09,740
Ale w poniedziałek, że twierdził, że możemy
skradać się z powrotem do królestwa efektywności

682
00:32:09,740 --> 00:32:13,040
osiągnięcia coś, co jest
Może logarytmiczna, lub najlepiej jeszcze,

683
00:32:13,040 --> 00:32:16,120
może nawet coś, co jest
tak zwana stała czasowa.

684
00:32:16,120 --> 00:32:19,840
Więc jak możemy to zrobić za pomocą tych nowych
narzędzia, te adresy, te wskaźniki,

685
00:32:19,840 --> 00:32:22,210
i gwintowania rzeczy sami?

686
00:32:22,210 --> 00:32:23,960
Cóż, przypuszczam, że
tutaj są to banda

687
00:32:23,960 --> 00:32:27,170
liczb, które chcemy przechowywać w
Struktura danych i wyszukiwarka sprawnie.

688
00:32:27,170 --> 00:32:30,960
Możemy absolutnie przewinąć do tygodnia
dwa, wrzuć je do tablicy,

689
00:32:30,960 --> 00:32:33,150
i szukać ich za pomocą wyszukiwania binarnego.

690
00:32:33,150 --> 00:32:34,040
Dziel i rządź.

691
00:32:34,040 --> 00:32:37,720
I faktycznie napisał
binarne wyszukiwania w PSET3,

692
00:32:37,720 --> 00:32:40,100
gdzie realizowany program find.

693
00:32:40,100 --> 00:32:40,890
Ale wiesz co.

694
00:32:40,890 --> 00:32:45,060
Jest to trochę bardziej
sprytny sposób to zrobić.

695
00:32:45,060 --> 00:32:47,390
To trochę więcej
wyrafinowany i być może

696
00:32:47,390 --> 00:32:50,830
pozwala nam zrozumieć, dlaczego binarny
wyszukiwania jest o wiele szybciej.

697
00:32:50,830 --> 00:32:52,980
Najpierw wprowadzenie
pojęcie drzewa.

698
00:32:52,980 --> 00:32:54,730
Które chociaż w
drzewa rzeczywistości rodzaj

699
00:32:54,730 --> 00:32:57,730
rosną jak to w świecie komputera
nauka to rodzaj rosną w dół

700
00:32:57,730 --> 00:33:00,830
jak drzewo genealogiczne, gdzie trzeba
Twoi dziadkowie lub pradziadkowie

701
00:33:00,830 --> 00:33:04,580
lub cokolwiek na górze, patriarchy i
macierz rodziny, tylko jeden

702
00:33:04,580 --> 00:33:07,930
tak zwany korzeń, węzeł, poniżej
które są jego dzieci,

703
00:33:07,930 --> 00:33:11,442
poniżej, które są jego dzieci, lub
jego potomkowie bardziej ogólnie.

704
00:33:11,442 --> 00:33:13,400
I każdy zawieszony
spód rodziny

705
00:33:13,400 --> 00:33:16,070
drzewo, oprócz bycia
Najmłodszy w rodzinie,

706
00:33:16,070 --> 00:33:19,520
Można też po prostu być ogólnie
nazywa liście drzewa.

707
00:33:19,520 --> 00:33:21,800
>> Więc to jest tylko kilka
słów i definicji

708
00:33:21,800 --> 00:33:25,790
coś nazywa się drzewo w komputerze
nauka, podobnie jak drzewa.

709
00:33:25,790 --> 00:33:28,770
Ale jest bardziej wyszukane wcieleń
drzew, z których jeden

710
00:33:28,770 --> 00:33:30,780
Wyszukiwarka nazywamy drzewo binarne.

711
00:33:30,780 --> 00:33:34,380
I można rodzaju Tease
od siebie, co robi ta rzecz.

712
00:33:34,380 --> 00:33:37,180
Cóż, to binarny, w jakim sensie?

713
00:33:37,180 --> 00:33:41,455
Skąd pochodzą z binarny tutaj?

714
00:33:41,455 --> 00:33:41,955
Przepraszam?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
To nie jest tak dużo lub.

717
00:33:47,210 --> 00:33:52,000
Jest to bardziej, że każdy z węzłów nie ma
więcej niż dwoje dzieci, jak widzimy tutaj.

718
00:33:52,000 --> 00:33:54,990
W ogóle, tree-- i
Twoi rodzice i dziadkowie

719
00:33:54,990 --> 00:33:57,640
może mieć tyle dzieci, lub
wnuki, jak rzeczywiście chcą,

720
00:33:57,640 --> 00:34:00,820
i tak na przykład nie mamy trzy
dzieci, poza tym węźle prawej stronie,

721
00:34:00,820 --> 00:34:05,480
ale w binarnym drzewie, węzeł ma
zero, jeden lub dwoje dzieci maksymalnie.

722
00:34:05,480 --> 00:34:08,496
A to ładny obiekt,
bo jeśli jest ograniczona przez dwa,

723
00:34:08,496 --> 00:34:10,620
będziemy w stanie
trochę bazę dziennika dwóch

724
00:34:10,620 --> 00:34:11,975
Akcja dzieje się tutaj, w końcu.

725
00:34:11,975 --> 00:34:13,350
Mamy więc coś logarytmiczną.

726
00:34:13,350 --> 00:34:14,558
Ale o tym za chwilę.

727
00:34:14,558 --> 00:34:19,810
Szukaj drzewo oznacza, że ​​liczby te są
ustawione tak, aby lewy dziecka

728
00:34:19,810 --> 00:34:22,429
jest większa od korzenia.

729
00:34:22,429 --> 00:34:26,010
Dziecko i jego prawo jest
większy niż root.

730
00:34:26,010 --> 00:34:29,290
Innymi słowy, jeśli wziąć którykolwiek z
węzły, kręgi na tym zdjęciu,

731
00:34:29,290 --> 00:34:31,840
i patrzy na jej lewej stronie
dziecka i jego prawo dziecka,

732
00:34:31,840 --> 00:34:34,739
pierwszy powinien być mniejszy niż
druga powinna być większa.

733
00:34:34,739 --> 00:34:36,159
Więc rozsądek sprawdzić 55.

734
00:34:36,159 --> 00:34:37,780
To co pozostało dziecka jest 33.

735
00:34:37,780 --> 00:34:38,620
To mniej niż.

736
00:34:38,620 --> 00:34:40,929
55, jego prawo dziecka jest 77.

737
00:34:40,929 --> 00:34:41,783
Jest większa niż.

738
00:34:41,783 --> 00:34:43,199
I to jest rekurencyjna definicja.

739
00:34:43,199 --> 00:34:46,480
Możemy sprawdzić każdy z tych
węzły i ten sam wzór będzie posiadał.

740
00:34:46,480 --> 00:34:49,389
>> Więc co jest miłe w sposób
binarne drzewo poszukiwań, jest

741
00:34:49,389 --> 00:34:52,204
że jeden, możemy go wdrożyć
ze struktury, po prostu lubię to.

742
00:34:52,204 --> 00:34:54,620
I mimo, że mamy do rzucania
wiele struktur do Państwa,

743
00:34:54,620 --> 00:34:56,560
są nieco
Intuicyjny teraz z nadzieją.

744
00:34:56,560 --> 00:35:00,570
Składnia jest wciąż arcane na pewno,
ale zawartość węzła w tym

745
00:35:00,570 --> 00:35:02,786
context-- i trzymamy
za pomocą węzła słowo,

746
00:35:02,786 --> 00:35:04,910
czy jest to prostokąt
na ekranie lub okręgu

747
00:35:04,910 --> 00:35:08,970
to tylko niektóre rodzajowe kontenera,
W tym przypadku drewna, takiego jak ten

748
00:35:08,970 --> 00:35:11,780
widzieliśmy, musimy liczbę całkowitą
w każdym z węzłów

749
00:35:11,780 --> 00:35:15,460
i wtedy muszę dwa wskaźniki wskazujące
do lewego i prawego dziecka dziecka

750
00:35:15,460 --> 00:35:16,590
odpowiednio.

751
00:35:16,590 --> 00:35:20,730
Tak to jest, jak może
wdrożenie, że do struktury.

752
00:35:20,730 --> 00:35:22,315
I jak można wdrożyć go w kodzie?

753
00:35:22,315 --> 00:35:26,730
Cóż, weźmy szybkie
spójrz na ten mały przykład.

754
00:35:26,730 --> 00:35:29,820
To nie jest funkcjonalny, ale mam
kopiować i wklejać tej struktury.

755
00:35:29,820 --> 00:35:33,510
A jeśli moja funkcja binarny
wyszukiwarka drzewo nazywane jest wyszukiwarka,

756
00:35:33,510 --> 00:35:36,980
i to ma dwa argumenty,
liczba całkowita N i wskaźnik

757
00:35:36,980 --> 00:35:41,400
do węzła, więc wskaźnik na drzewie
lub wskaźnik do korzenia drzewa,

758
00:35:41,400 --> 00:35:43,482
jak mogę iść o poszukiwaniu N?

759
00:35:43,482 --> 00:35:45,440
Cóż, po pierwsze, dlatego, że jestem
czynienia ze wskaźnikami,

760
00:35:45,440 --> 00:35:46,750
Mam zamiar zrobić test dla pewności.

761
00:35:46,750 --> 00:35:54,279
Jeśli równi drzewo równa null, to N
w tym drzewie, czy nie na tym drzewie?

762
00:35:54,279 --> 00:35:55,070
To nie może być, prawda?

763
00:35:55,070 --> 00:35:56,870
Jeśli jestem obok null,
tam nic nie ma.

764
00:35:56,870 --> 00:35:59,230
Mógłbym równie dobrze
ślepo powiedzieć return false.

765
00:35:59,230 --> 00:36:04,050
Jeśli dasz mi nic, ja na pewno nie może
znaleźć żadnego numeru N. Więc co jeszcze mogę

766
00:36:04,050 --> 00:36:04,750
Sprawdź teraz?

767
00:36:04,750 --> 00:36:12,830
Mam zamiar powiedzieć, jak inni, jeśli N jest
mniej niż to, co jest z węzła drzewa

768
00:36:12,830 --> 00:36:16,300
że byłem podał wartość N.

769
00:36:16,300 --> 00:36:20,270
Innymi słowy, liczba mi
szuka, N jest mniejsza niż węzeł

770
00:36:20,270 --> 00:36:21,340
że patrzę.

771
00:36:21,340 --> 00:36:23,190
Oraz węzeł szukam
co nazywa się drzewo,

772
00:36:23,190 --> 00:36:26,370
i pamiętam z poprzedniego przykładu
aby dostać się w wartości wskaźnika,

773
00:36:26,370 --> 00:36:28,310
Używam notacji strzałki.

774
00:36:28,310 --> 00:36:35,960
Tak więc, gdy liczba N jest mniejsza niż drzewa strzałką
N, chcę koncepcyjnie iść w lewo.

775
00:36:35,960 --> 00:36:38,590
W jaki sposób mogę wyrazić poszukiwań w lewo?

776
00:36:38,590 --> 00:36:41,560
Żeby było jasne, czy jest to
obraz, o którym mowa,

777
00:36:41,560 --> 00:36:44,612
a ja już minęło, że najwyższy
strzałka skierowana w dół, że jest.

778
00:36:44,612 --> 00:36:45,570
To moje drzewo wskaźnik.

779
00:36:45,570 --> 00:36:48,060
Jestem wskazując na korzenia drzewa.

780
00:36:48,060 --> 00:36:52,100
I szukam powiedzmy, na
numer 44, arbitralnie.

781
00:36:52,100 --> 00:36:55,300
Jest 44 mniejsza niż lub
większa niż 55 oczywiście?

782
00:36:55,300 --> 00:36:56,360
Więc to jest mniej niż.

783
00:36:56,360 --> 00:36:58,760
A więc to, czy dotyczy warunek.

784
00:36:58,760 --> 00:37:03,981
Tak koncepcyjnie, co chcę
szukaj w przyszłym, jeśli szukam 44?

785
00:37:03,981 --> 00:37:04,480
Tak?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Dokładnie, ja chcę
szukaj lewy dziecko,

788
00:37:11,100 --> 00:37:12,789
lub w lewo poddrzewo tego obrazu.

789
00:37:12,789 --> 00:37:14,830
I rzeczywiście, niech mnie przez
obraz tutaj

790
00:37:14,830 --> 00:37:17,770
na chwilę, ponieważ
Nie mogę drapać to.

791
00:37:17,770 --> 00:37:21,150
Jeśli zacznę tutaj na 55, oraz
Wiem, że wartość 44

792
00:37:21,150 --> 00:37:23,180
Szukam jest
lewica, jest to swego rodzaju

793
00:37:23,180 --> 00:37:26,010
jakby rozrywanie książki telefonicznej w
pół lub łzawienie drzewo na pół.

794
00:37:26,010 --> 00:37:29,660
I nie muszą już dbać o
Cały pół drzewa.

795
00:37:29,660 --> 00:37:33,270
A jednak, co ciekawe w kategoriach
struktury, to coś tu, że

796
00:37:33,270 --> 00:37:36,682
zaczyna się od 33, która sama w sobie
Wyszukiwarka jest drzewo binarne.

797
00:37:36,682 --> 00:37:39,890
I powiedział, że słowo rekurencyjne wcześniej, bo
W rzeczywistości jest to struktura danych

798
00:37:39,890 --> 00:37:41,707
z definicji jest rekurencyjne.

799
00:37:41,707 --> 00:37:44,540
Możesz mieć drzewa, które jest w tym
duży, ale każdy z jej dzieci

800
00:37:44,540 --> 00:37:46,870
reprezentuje drzewo tylko trochę mniejszy.

801
00:37:46,870 --> 00:37:50,910
Zamiast niego jest dziadek
lub babcia, teraz to tylko mama

802
00:37:50,910 --> 00:37:54,300
or-- nie mogę nie say-- mama
lub tata, to byłoby dziwne.

803
00:37:54,300 --> 00:37:59,000
Zamiast tego dwoje dzieci
będzie jak brat i rodzeństwo.

804
00:37:59,000 --> 00:38:01,120
Nowa generacja drzewa genealogicznego.

805
00:38:01,120 --> 00:38:02,900
Ale strukturalnie, że to ten sam pomysł.

806
00:38:02,900 --> 00:38:06,790
I okazuje się, mam funkcji
z których można przeszukiwać przeszukiwanie binarne

807
00:38:06,790 --> 00:38:07,290
drzewo.

808
00:38:07,290 --> 00:38:08,680
Nazywana jest wyszukiwarka.

809
00:38:08,680 --> 00:38:17,870
Szukam N w drzewo strzałka w lewo
inaczej, jeśli n jest większe od wartości

810
00:38:17,870 --> 00:38:18,870
że jestem obecnie.

811
00:38:18,870 --> 00:38:20,800
55 w historii przed chwilą.

812
00:38:20,800 --> 00:38:23,780
Mam funkcję o nazwie
wyszukiwarka, że ​​mogę po prostu

813
00:38:23,780 --> 00:38:29,660
przekazać N to i rekurencyjnie wyszukiwania
sub-tree i po prostu powrót

814
00:38:29,660 --> 00:38:30,620
cokolwiek to odpowiedź.

815
00:38:30,620 --> 00:38:33,530
Jeszcze mam jakiś ostateczny wariant podstawowy tutaj.

816
00:38:33,530 --> 00:38:35,310
>> Jaki jest ostateczny przypadek?

817
00:38:35,310 --> 00:38:36,570
Drzewo jest albo wartość null.

818
00:38:36,570 --> 00:38:39,980
Wartość ja albo szukasz jest
mniejsze niż lub większa niż

819
00:38:39,980 --> 00:38:42,610
lub jej równa.

820
00:38:42,610 --> 00:38:44,750
I mogę powiedzieć, równa
równe, ale logicznie to

821
00:38:44,750 --> 00:38:46,500
równowartość tylko, że jeszcze tutaj.

822
00:38:46,500 --> 00:38:49,150
Tak więc prawdą jest, jak coś znajdę.

823
00:38:49,150 --> 00:38:51,710
Więc mam nadzieję, że jest to
jeszcze bardziej atrakcyjne przykładem

824
00:38:51,710 --> 00:38:54,900
niż funkcja głupiego sigma
zrobiliśmy kilka wykładów z powrotem,

825
00:38:54,900 --> 00:38:58,360
gdzie to było tak łatwe w użyciu pętli
liczyć się wszystkie numery z jednego

826
00:38:58,360 --> 00:39:02,390
N. tu ze struktury danych
które samo w sobie jest rekurencyjnie

827
00:39:02,390 --> 00:39:07,050
zdefiniowane i rekurencyjnie rysowane, teraz my
mają zdolność do wyrażania siebie

828
00:39:07,050 --> 00:39:09,780
w kodzie, który sam w sobie jest rekurencyjny.

829
00:39:09,780 --> 00:39:12,580
Więc to jest dokładnie ten sam kod tutaj.

830
00:39:12,580 --> 00:39:14,400
>> Więc jakie inne problemy możemy rozwiązać?

831
00:39:14,400 --> 00:39:18,160
Tak szybkie krok od
drzew na chwilę.

832
00:39:18,160 --> 00:39:20,130
Oto, mówi, niemiecką flagę.

833
00:39:20,130 --> 00:39:22,020
I jest wyraźnie
wzór do tej flagi.

834
00:39:22,020 --> 00:39:23,811
I jest mnóstwo
flagi w świecie,

835
00:39:23,811 --> 00:39:27,560
są proste, ponieważ w warunkach
ich kolorów i wzorów.

836
00:39:27,560 --> 00:39:31,930
Jednak przypuszczać, że jest to zapisane jako
GIF lub JPEG lub bitmapy, lub ping,

837
00:39:31,930 --> 00:39:34,240
dowolny format pliku graficznego
z których znasz,

838
00:39:34,240 --> 00:39:36,460
niektóre z których jesteśmy
gry z w PSET4.

839
00:39:36,460 --> 00:39:41,550
Nie wydaje się opłaca przechowywać
czarny piksel, czarny piksel, czarny piksel,

840
00:39:41,550 --> 00:39:44,790
kropka, kropka, kropka, cała masa
czarne piksele na pierwszy scanline,

841
00:39:44,790 --> 00:39:47,430
lub wiersza, to cała masa
takie same, wówczas cała masa

842
00:39:47,430 --> 00:39:49,530
to samo, a potem
cała masa czerwonych pikseli,

843
00:39:49,530 --> 00:39:53,020
czerwonych pikseli, czerwony pikseli, a następnie całość
kilka żółtych pikseli, żółty, prawda?

844
00:39:53,020 --> 00:39:55,050
>> Jest takie nieefektywność tutaj.

845
00:39:55,050 --> 00:39:59,040
Jak byś intuicyjnie
skompresować niemiecką flagą

846
00:39:59,040 --> 00:40:01,320
jeśli wdrożenie go jako plik?

847
00:40:01,320 --> 00:40:04,940
Jak to, co my informacje nie mogą
przeszkadza przechowywania na dysku, w celu

848
00:40:04,940 --> 00:40:08,040
aby zmniejszyć rozmiar pliku z naszego jak
megabajt do kilobajtów, coś

849
00:40:08,040 --> 00:40:09,430
mniejsze?

850
00:40:09,430 --> 00:40:13,130
Na czym polega zwolnienie
tutaj, aby być jasne?

851
00:40:13,130 --> 00:40:13,880
Co można zrobić?

852
00:40:13,880 --> 00:40:14,380
Tak?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Dokładnie.

855
00:40:21,970 --> 00:40:24,550
Dlaczego nie, a nie pamiętam
kolor każdego piksela absolutnie znakomite

856
00:40:24,550 --> 00:40:28,200
jak robisz w PSET4
z formatem plików graficznych,

857
00:40:28,200 --> 00:40:32,060
dlaczego nie można po prostu reprezentują
skrajnej lewej kolumnie pikseli, na przykład

858
00:40:32,060 --> 00:40:35,370
kilka czarnych pikseli, banda
czerwony, i kilka żółty,

859
00:40:35,370 --> 00:40:39,210
a potem po prostu w jakiś sposób zakodowania
Pomysł powtórzyć ten 100 razy

860
00:40:39,210 --> 00:40:41,020
lub powtórzyć to 1000 razy?

861
00:40:41,020 --> 00:40:43,430
Gdzie 100 lub 1000 jest
po prostu liczbą całkowitą, więc Ciebie

862
00:40:43,430 --> 00:40:47,290
może uciec z tylko jednym numerem
zamiast setek lub tysięcy

863
00:40:47,290 --> 00:40:48,270
dodatkowych pikseli.

864
00:40:48,270 --> 00:40:50,990
I rzeczywiście, to w jaki sposób
może skompresować niemiecką flagą.

865
00:40:50,990 --> 00:40:51,490
I

866
00:40:51,490 --> 00:40:53,470
Teraz co z francuską banderą?

867
00:40:53,470 --> 00:40:58,930
I trochę jakiś
ćwiczenia umysłowe, które flagi

868
00:40:58,930 --> 00:41:01,040
mogą być kompresowane bardziej na dysku?

869
00:41:01,040 --> 00:41:05,720
Flaga niemiecki lub francuski
flaga, jeśli weźmiemy to podejście?

870
00:41:05,720 --> 00:41:08,490
Niemiecka flaga, bo nie ma
więcej pozioma redundancji.

871
00:41:08,490 --> 00:41:12,190
I projektowania, wiele graficznym pliku
formaty rzeczywiście działają linie jako skanowania

872
00:41:12,190 --> 00:41:12,830
poziomo.

873
00:41:12,830 --> 00:41:14,674
Mogą one pracować
pionowo, tak ludzkość

874
00:41:14,674 --> 00:41:17,090
lat temu zdecydowali, że będziesz
ogólnie myślę o rzeczach rzędu

875
00:41:17,090 --> 00:41:18,880
po rzędzie zamiast kolumna po kolumnie.

876
00:41:18,880 --> 00:41:20,820
Więc rzeczywiście, jeśli były
patrzeć na pliku

877
00:41:20,820 --> 00:41:24,670
wielkość niemiecką flagą i francusku
flaga, tak długo, jak rozdzielczość to

878
00:41:24,670 --> 00:41:27,530
tym samym, o takiej samej szerokości
i wysokość, ten

879
00:41:27,530 --> 00:41:31,580
tutaj będzie większy, bo Ciebie
trzeba powtarzać sobie trzy razy.

880
00:41:31,580 --> 00:41:35,570
Musisz określić, niebieski, powtórki
sam, biały, powtarzam się, czerwony,

881
00:41:35,570 --> 00:41:36,740
powtarzaj się.

882
00:41:36,740 --> 00:41:39,000
Nie można po prostu pójść na całość
droga w prawo.

883
00:41:39,000 --> 00:41:41,200
I tak na marginesie, aby
usunąć kompresję

884
00:41:41,200 --> 00:41:43,910
Jest wszędzie, o ile są one
cztery ramki ze video-- ci

885
00:41:43,910 --> 00:41:45,890
może przypomnieć, że film
lub wideo jest na ogół

886
00:41:45,890 --> 00:41:47,286
jak 29 lub 30 klatek na sekundę.

887
00:41:47,286 --> 00:41:50,410
To jak książeczki odwrotną, gdzie
po prostu zobaczyć obraz, wizerunek, wizerunek, obraz,

888
00:41:50,410 --> 00:41:54,410
Obraz po prostu super szybko, więc wygląda na to,
aktorzy na ekranie poruszają.

889
00:41:54,410 --> 00:41:57,130
Oto trzmieli na
góry bukietem kwiatów.

890
00:41:57,130 --> 00:41:59,790
I choć może to być rodzaj
trudno zobaczyć na pierwszy rzut oka,

891
00:41:59,790 --> 00:42:04,020
jedyne, co porusza się w
ten film jest pszczoła.

892
00:42:04,020 --> 00:42:06,880
>> Co to jest głupi temat przechowywania
sygnał wideo?

893
00:42:06,880 --> 00:42:11,420
Jest to swego rodzaju odpadów do sklepu wideo
w czterech niemal identycznych obrazów

894
00:42:11,420 --> 00:42:13,670
różnią się jedynie w zakresie, gdzie pszczoły jest.

895
00:42:13,670 --> 00:42:16,280
Możesz wyrzucić najbardziej
tej informacji

896
00:42:16,280 --> 00:42:20,190
i tylko pamiętać, na przykład
pierwszy i ostatni rama rama,

897
00:42:20,190 --> 00:42:22,180
klatki kluczowe, jeśli już
słyszał słowa,

898
00:42:22,180 --> 00:42:24,337
i po prostu przechowywać w
Pszczoła w średnim gdzie jest.

899
00:42:24,337 --> 00:42:26,170
A ty nie musisz
przechowywać wszystkie różowe,

900
00:42:26,170 --> 00:42:28,330
i niebieski, i
Wartości zielone, jak również.

901
00:42:28,330 --> 00:42:31,200
Więc to jest tylko powiedzieć, że
Kompresja jest wszędzie.

902
00:42:31,200 --> 00:42:34,900
Jest to technika często używamy
lub wziąć za pewnik te dni.

903
00:42:34,900 --> 00:42:38,750
>> Ale w jaki sposób skompresować tekst?

904
00:42:38,750 --> 00:42:40,450
Jak idziesz na temat kompresji tekstu?

905
00:42:40,450 --> 00:42:45,410
Cóż, każda z postaci w
ASCII jest jeden bajt lub osiem bitów.

906
00:42:45,410 --> 00:42:47,360
A to niby głupie, prawda?

907
00:42:47,360 --> 00:42:51,160
Bo prawdopodobnie typu A
i E oraz I i O i U wielu

908
00:42:51,160 --> 00:42:55,270
częściej niż jak W lub Q lub Z,
w zależności od języka, w którym

909
00:42:55,270 --> 00:42:56,610
piszesz na pewno.

910
00:42:56,610 --> 00:42:59,600
A więc dlaczego używamy
osiem bitów na każdy list,

911
00:42:59,600 --> 00:43:02,040
w tym co najmniej
popularne litery, prawda?

912
00:43:02,040 --> 00:43:05,300
Dlaczego nie skorzystać z mniejszej liczby bitów dla
Super popularne litery,

913
00:43:05,300 --> 00:43:07,760
jak E, rzeczy się domyślić
Pierwszy w Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
i korzystać z większej liczby bitów dla
mniej popularne litery?

915
00:43:10,450 --> 00:43:10,950
Czemu?

916
00:43:10,950 --> 00:43:13,130
Ponieważ jesteśmy po prostu będzie
używać ich rzadziej.

917
00:43:13,130 --> 00:43:15,838
>> Cóż, okazuje się, że nie mają
były podejmowane próby, aby to zrobić.

918
00:43:15,838 --> 00:43:18,630
A jeśli pamiętacie z klasy
szkoły lub szkoły, alfabet Morse'a.

919
00:43:18,630 --> 00:43:20,400
Kod Morse'a ma kropki
i kresek, które może być

920
00:43:20,400 --> 00:43:24,270
przekazywane wzdłuż drutu jako
dźwięków lub sygnały pewnego rodzaju.

921
00:43:24,270 --> 00:43:25,930
Ale Morse'a jest super czyste.

922
00:43:25,930 --> 00:43:29,010
Jest to rodzaj systemu binarnego w
że masz kropki lub kreski.

923
00:43:29,010 --> 00:43:30,977
Ale jeśli widzisz, na przykład, dwie kropki.

924
00:43:30,977 --> 00:43:33,810
Lub jeśli myślisz, że z powrotem do operatora
kto idzie jak Beep, beep, beep,

925
00:43:33,810 --> 00:43:36,760
dźwięk, uderzając trochę spust
że wysyła się sygnał,

926
00:43:36,760 --> 00:43:40,360
Jeśli odbiorca, otrzymuje dwa
punktów, jakie otrzymał pan wiadomość?

927
00:43:40,360 --> 00:43:43,490
Całkowicie arbitralne.

928
00:43:43,490 --> 00:43:44,450
>> JA?

929
00:43:44,450 --> 00:43:45,060
JA?

930
00:43:45,060 --> 00:43:47,500
Albo co about-- czy ja?

931
00:43:47,500 --> 00:43:49,570
Może to była tylko dwa prawy E jest?

932
00:43:49,570 --> 00:43:52,480
Więc nie ma tego problemu
z dekodowalność z Morse

933
00:43:52,480 --> 00:43:54,890
Kod, w którym chyba że
osoba, wysyłając wiadomość

934
00:43:54,890 --> 00:43:59,510
faktycznie wstrzymuje więc można sortować z
zobaczyć lub usłyszeć luki między literami,

935
00:43:59,510 --> 00:44:02,990
to nie wystarczy po prostu
wysyłać strumień zer i jedynek,

936
00:44:02,990 --> 00:44:05,610
lub kropki i kreski,
bo nie ma dwuznaczności.

937
00:44:05,610 --> 00:44:08,640
E jest jednym punktem, więc jeśli
zobacz dwie kropki lub usłyszeć dwie kropki,

938
00:44:08,640 --> 00:44:11,254
może to dwie E czy też może jest to jeden I.

939
00:44:11,254 --> 00:44:13,670
Musimy więc system, który jest
trochę mądrzejszy niż to.

940
00:44:13,670 --> 00:44:16,851
Więc człowiek, imieniem Huffman lat
temu wpadł właśnie to.

941
00:44:16,851 --> 00:44:18,600
Więc my po prostu się
podjąć szybkie spojrzenie

942
00:44:18,600 --> 00:44:20,114
w jaki sposób drzewa są germane do tego.

943
00:44:20,114 --> 00:44:22,530
Przypuszczać, że jest to nieco
głupia wiadomość chcesz wysłać,

944
00:44:22,530 --> 00:44:26,342
składa się z tylko A, B, C w D's i E'S,
ale jest wiele redundancji tutaj.

945
00:44:26,342 --> 00:44:27,550
To nie tak miało być angielski.

946
00:44:27,550 --> 00:44:28,341
To nie jest szyfrowane.

947
00:44:28,341 --> 00:44:30,540
To tylko głupia wiadomość
z dużą ilością powtórzeń.

948
00:44:30,540 --> 00:44:34,010
Więc jeśli naprawdę liczą się wszystkie
A'S, B, C'S, D's, i E, oto jest

949
00:44:34,010 --> 00:44:34,890
częstotliwość.

950
00:44:34,890 --> 00:44:37,800
20% z liter są
A w 45% z liter

951
00:44:37,800 --> 00:44:39,660
to E, a trzy inne częstotliwości.

952
00:44:39,660 --> 00:44:41,960
Liczyliśmy się tam ręcznie
i po prostu nie matematyka.

953
00:44:41,960 --> 00:44:44,579
>> Tak więc okazuje się, że
Huffman, jakiś czas temu,

954
00:44:44,579 --> 00:44:46,620
sobie sprawę, że, wiesz,
co, jeśli zacznę budynku

955
00:44:46,620 --> 00:44:51,172
drzewo lub las drzew, jeśli chcesz,
w następujący sposób, można wykonać następujące czynności.

956
00:44:51,172 --> 00:44:53,880
Mam zamiar dać węzeł do każdego
z listów, że dbają o

957
00:44:53,880 --> 00:44:55,530
i mam zamiar zapisać
wewnątrz tego węzła

958
00:44:55,530 --> 00:44:58,610
częstotliwości jak zmiennoprzecinkowych
wartości, lub można go używać N, zbyt,

959
00:44:58,610 --> 00:45:00,210
ale użyjemy tutaj pływaka.

960
00:45:00,210 --> 00:45:03,100
Oraz algorytm
zaproponował, że można

961
00:45:03,100 --> 00:45:07,210
wziąć ten las pojedynczego węzła
drzewa, więc bardzo krótkie drzewa,

962
00:45:07,210 --> 00:45:11,920
i rozpocząć łączenie ich z
nowe grupy, nowe rodzice, jeśli będzie.

963
00:45:11,920 --> 00:45:16,150
I można to zrobić, wybierając opcję
dwa najmniejsze częstotliwości jednocześnie.

964
00:45:16,150 --> 00:45:18,110
Wziąłem więc 10% i 10%.

965
00:45:18,110 --> 00:45:19,090
Utworzyć nowy węzeł.

966
00:45:19,090 --> 00:45:20,910
I wzywam nowy węzeł 20%.

967
00:45:20,910 --> 00:45:22,750
>> Których dwa węzły Łączę dalej?

968
00:45:22,750 --> 00:45:23,810
To trochę niejednoznaczne.

969
00:45:23,810 --> 00:45:26,643
Więc jest kilka przypadków rożny dla
rozważyć, ale do przechowywania rzeczy ładne,

970
00:45:26,643 --> 00:45:29,300
Mam zamiar wybrać 20% -
I teraz ignorować dzieci.

971
00:45:29,300 --> 00:45:33,640
Mam zamiar wybrać 20% i
15% i narysować dwie nowe krawędzie.

972
00:45:33,640 --> 00:45:35,624
A teraz czego dwa węzły
mam logicznie połączyć?

973
00:45:35,624 --> 00:45:38,540
Ignoruj ​​wszystkie dzieci, wszystkie
wnuki, wystarczy spojrzeć na korzenie

974
00:45:38,540 --> 00:45:39,070
teraz.

975
00:45:39,070 --> 00:45:42,220
Które węzły dwa mogę powiązać?

976
00:45:42,220 --> 00:45:44,530
Punkt dwa i 0,35.

977
00:45:44,530 --> 00:45:45,890
Więc pozwól mi wyciągnąć dwa nowe krawędzie.

978
00:45:45,890 --> 00:45:47,570
A potem mam tylko jeden.

979
00:45:47,570 --> 00:45:48,650
Więc oto drzewo.

980
00:45:48,650 --> 00:45:51,160
I to było rysowane celowo
szukać rodzaju dość,

981
00:45:51,160 --> 00:45:55,870
ale zauważ, że krawędzie mają
również oznaczony zera do jeden.

982
00:45:55,870 --> 00:45:59,510
Więc wszystkie lewej krawędzi są zerowe
arbitralnie, ale konsekwentnie.

983
00:45:59,510 --> 00:46:01,170
Wszystkie prawa krawędź są te.

984
00:46:01,170 --> 00:46:05,070
>> A więc to, co Hoffman proponuje się,
jeśli chcesz do reprezentowania B,

985
00:46:05,070 --> 00:46:10,080
zamiast reprezentują liczbę 66 a
ASCII, który jest osiem całych bitów,

986
00:46:10,080 --> 00:46:13,360
Wiesz co, tylko sklep
wzór zero, zero, zero,

987
00:46:13,360 --> 00:46:17,030
zero, bo to droga
z mojego drzewa, drzewo pana Huffman, w

988
00:46:17,030 --> 00:46:18,600
do liści z korzenia.

989
00:46:18,600 --> 00:46:20,970
Jeśli chcesz się zapisać
E, natomiast nie

990
00:46:20,970 --> 00:46:26,290
wysłać osiem bitów, które reprezentują E.
Zamiast wysyłać jaki wzór bitów?

991
00:46:26,290 --> 00:46:26,890
Jeden.

992
00:46:26,890 --> 00:46:30,410
A co jest miłe jest to,
że E jest najbardziej popularne pismo,

993
00:46:30,410 --> 00:46:32,340
i że używasz
najkrótszy kod dla niego.

994
00:46:32,340 --> 00:46:34,090
Kolejnym najbardziej popularne
Pismo to wygląda

995
00:46:34,090 --> 00:46:37,380
A. I tak było, ile bitów
on zaproponować używając do tego?

996
00:46:37,380 --> 00:46:38,270
Zero, jeden.

997
00:46:38,270 --> 00:46:41,060
>> A ponieważ jest realizowany
w tym drzewie, na razie

998
00:46:41,060 --> 00:46:43,350
pozwól mi przewidują tam
dwuznaczności jak w Morse

999
00:46:43,350 --> 00:46:46,090
Kod, ponieważ wszystkie
Litery dbasz o

1000
00:46:46,090 --> 00:46:48,780
znajdują się na końcu tych brzegów.

1001
00:46:48,780 --> 00:46:50,580
Więc to jest tylko jeden
Zastosowanie drzewa.

1002
00:46:50,580 --> 00:46:52,538
To jest-- i będę machać
moja ręka na to, w jaki sposób

1003
00:46:52,538 --> 00:46:55,570
Może to realizować jako struktura C.

1004
00:46:55,570 --> 00:46:58,260
Musimy po prostu połączyć
symbolem, jak char,

1005
00:46:58,260 --> 00:46:59,910
a częstotliwość w lewo i prawo.

1006
00:46:59,910 --> 00:47:02,510
Ale spójrzmy na dwa
przykłady końcowe, które będziesz

1007
00:47:02,510 --> 00:47:06,070
się dość dobrze po
Quiz zero problemu ustawić pięć.

1008
00:47:06,070 --> 00:47:09,210
>> Tak więc jest struktura danych
znany jako tabeli mieszania.

1009
00:47:09,210 --> 00:47:12,247
I tabeli mieszania jest rodzajem
ochłodzenia się tym, że ma wiadra.

1010
00:47:12,247 --> 00:47:14,830
I przypuśćmy, że istnieje cztery wiadra
tu, zaledwie cztery spacje.

1011
00:47:14,830 --> 00:47:20,830
Oto talia kart, a tu jest
Klub, łopata, klub, diamenty, klub,

1012
00:47:20,830 --> 00:47:25,960
diamenty, club, diamenty,
clubs-- więc jest to przypadkowe.

1013
00:47:25,960 --> 00:47:30,330
Serca, hearts-- więc jestem
bucketizing wszystkich wejściach tutaj.

1014
00:47:30,330 --> 00:47:32,430
I potrzeby tabeli mieszania
patrzeć na wejściu,

1015
00:47:32,430 --> 00:47:34,850
a następnie umieścić go w pewien
umieścić w oparciu o to, co widzisz.

1016
00:47:34,850 --> 00:47:35,600
Jest to algorytm.

1017
00:47:35,600 --> 00:47:37,980
A ja za pomocą super,
prosty algorytm wideo.

1018
00:47:37,980 --> 00:47:40,030
Najtrudniejszą częścią, która była
pamiętając, co zdjęcia były.

1019
00:47:40,030 --> 00:47:41,590
A jeszcze cztery łączne rzeczy.

1020
00:47:41,590 --> 00:47:45,440
>> Teraz rosły stosy, które
Jest to celowe projektowanie rzecz tutaj.

1021
00:47:45,440 --> 00:47:46,540
Ale co jeszcze mogę zrobić?

1022
00:47:46,540 --> 00:47:49,080
Czyli tutaj mamy
kilka starych książek egzaminacyjnych szkoły.

1023
00:47:49,080 --> 00:47:51,240
Załóżmy, że grono
Nazwiska studentów są tutaj.

1024
00:47:51,240 --> 00:47:52,570
Oto większy tabeli mieszania.

1025
00:47:52,570 --> 00:47:54,867
Zamiast czterech wiader,
I, powiedzmy, 26.

1026
00:47:54,867 --> 00:47:57,950
I nie chcę iść pożyczyć 26
rzeczy z zewnątrz [? Annenberg?], Więc

1027
00:47:57,950 --> 00:48:00,289
Oto pięć, które stanowią
A do Z. A jeśli

1028
00:48:00,289 --> 00:48:03,580
zobacz ucznia, którego nazwa zaczyna się od A,
Mam zamiar umieścić swoje quizu istnieje.

1029
00:48:03,580 --> 00:48:08,850
Jeśli ktoś zaczyna z C, tam,
A-- faktycznie, nie chcę tego robić.

1030
00:48:08,850 --> 00:48:10,060
B idzie tutaj.

1031
00:48:10,060 --> 00:48:13,390
Więc mam A i B i C. A
Teraz oto kolejny uczniowi.

1032
00:48:13,390 --> 00:48:16,212
Ale jeśli ta tabela mieszania jest
realizowane z tablicy,

1033
00:48:16,212 --> 00:48:17,920
Jestem rodzaju wkręca
w tym miejscu, prawda?

1034
00:48:17,920 --> 00:48:19,510
I niby trzeba umieścić to gdzieś.

1035
00:48:19,510 --> 00:48:24,380
>> Więc jeden sposób mogę rozwiązać to wszystko
w prawo, A jest zajęty, B jest zajęty, C jest zajęty.

1036
00:48:24,380 --> 00:48:28,880
Mam zamiar umieścić go w D. Tak więc w
Pierwszy, mam losowy natychmiastowy dostęp

1037
00:48:28,880 --> 00:48:31,064
każdej z kubłów dla studentów.

1038
00:48:31,064 --> 00:48:33,230
Ale teraz to rodzaj przekazane
w coś liniowych,

1039
00:48:33,230 --> 00:48:36,750
bo jeśli chcę szukać kogoś
którego nazwa zaczyna się na literę A, sprawdzić tutaj.

1040
00:48:36,750 --> 00:48:38,854
Jeśli jednak tak nie jest A
studentka szukam,

1041
00:48:38,854 --> 00:48:41,520
I niby zacząć sprawdzanie
wiadra, bo to, co zrobiłem

1042
00:48:41,520 --> 00:48:44,530
był rodzaj liniowo
badać strukturę danych.

1043
00:48:44,530 --> 00:48:47,710
Głupi sposób powiedzenia tylko patrzeć
do pierwszego dostępnego otworu

1044
00:48:47,710 --> 00:48:51,850
i umieścić jako plan B, że tak powiem,
lub planu D w tym przypadku wartość

1045
00:48:51,850 --> 00:48:53,340
w tym miejscu zamiast.

1046
00:48:53,340 --> 00:48:56,470
To jest tak, że jeśli masz
ma 26 miejsc i nie studentów

1047
00:48:56,470 --> 00:49:00,600
o nazwie Q lub Z, lub coś podobnego
że przynajmniej używasz miejsca.

1048
00:49:00,600 --> 00:49:03,140
>> Ale widzieliśmy już więcej
Rozwiązanie, tutaj, prawda?

1049
00:49:03,140 --> 00:49:04,870
Co byś zrobił, zamiast
jeśli masz kolizję?

1050
00:49:04,870 --> 00:49:06,670
Jeśli dwie osoby mają
Nazwa A, co by

1051
00:49:06,670 --> 00:49:09,160
były inteligentniejsze lub więcej
intuicyjne rozwiązanie, niż tylko

1052
00:49:09,160 --> 00:49:12,840
Umieszczenie gdzie D ma być?

1053
00:49:12,840 --> 00:49:14,810
Dlaczego nie mogę po prostu iść
poza [? Annenberg?]

1054
00:49:14,810 --> 00:49:19,960
jak malloc, innego węzła, umieścić go
tutaj, a następnie umieścić, że student tutaj.

1055
00:49:19,960 --> 00:49:22,120
Tak, że zasadniczo mają
jakiś rodzaj tablicy,

1056
00:49:22,120 --> 00:49:25,590
a może bardziej elegancko, jak jesteśmy
zaczynają widzieć połączonej listy.

1057
00:49:25,590 --> 00:49:29,520
>> I tak tabeli mieszania jest strukturą
że może wyglądać podobnie jak ten,

1058
00:49:29,520 --> 00:49:33,900
ale bardziej inteligentnie, to coś, co nazywa
oddzielna łańcuchowym, w której tabeli mieszania

1059
00:49:33,900 --> 00:49:38,340
prostu jest tablicą, każdy z
którego elementy nie jest liczbą,

1060
00:49:38,340 --> 00:49:40,470
sama jest związana lista.

1061
00:49:40,470 --> 00:49:45,080
Tak, że masz super szybki dostęp
podejmowaniu decyzji, gdzie do mieszania swoją wartość.

1062
00:49:45,080 --> 00:49:48,059
Podobnie jak w przykładzie kart,
Zrobiłem bardzo szybkich decyzji.

1063
00:49:48,059 --> 00:49:49,600
Miłość idzie tutaj, diamenty idzie tutaj.

1064
00:49:49,600 --> 00:49:52,180
Sama Tutaj, idzie tutaj,
D idzie tutaj, B idzie tutaj.

1065
00:49:52,180 --> 00:49:55,740
Więc bardzo szybko look-up, a jeśli
zdarzy ci się uruchomić w przypadku

1066
00:49:55,740 --> 00:49:59,429
gdzie mam kolizji, dwie
osób z tej samej nazwie, a następnie

1067
00:49:59,429 --> 00:50:00,970
po prostu zacząć łącząc je razem.

1068
00:50:00,970 --> 00:50:03,900
A może i ty zachować je klasyfikowane
alfabetycznie, a może nie.

1069
00:50:03,900 --> 00:50:05,900
Ale przynajmniej teraz mamy dynamizm.

1070
00:50:05,900 --> 00:50:10,250
Tak więc z jednej strony mamy super szybki
Stała czasowa i rodzaj czasie liniowym

1071
00:50:10,250 --> 00:50:14,110
udział, jeśli tych powiązanych list
zaczynają się trochę długo.

1072
00:50:14,110 --> 00:50:16,880
>> Więc tego rodzaju głupie,
geeky lat żart temu.

1073
00:50:16,880 --> 00:50:19,590
Na CS50 hack-a-Thon,
kiedy uczniowie sprawdzenia,

1074
00:50:19,590 --> 00:50:22,040
niektóre TF lub CA co roku
uważa, że ​​to zabawne, aby umieścić

1075
00:50:22,040 --> 00:50:27,772
to znak, jak ten, w którym po prostu
Oznacza jeśli nazwa zaczyna się na A,

1076
00:50:27,772 --> 00:50:28,870
go w ten sposób.

1077
00:50:28,870 --> 00:50:31,110
Jeśli nazwa zaczyna
z B, przejdź this-- OK,

1078
00:50:31,110 --> 00:50:33,290
to zabawne, a może jeszcze w tym semestrze.

1079
00:50:33,290 --> 00:50:36,420
Ale nie ma innego
sposób w ten sposób, też.

1080
00:50:36,420 --> 00:50:37,410
Wrócić do tego.

1081
00:50:37,410 --> 00:50:38,600
>> Więc jest ta struktura.

1082
00:50:38,600 --> 00:50:40,420
I to jest nasz ostatni
Struktura na dziś

1083
00:50:40,420 --> 00:50:42,400
co jest coś nazywa się trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, które z jakiegoś powodu jest krótki
do wyszukiwania, ale to się nazywa trie.

1085
00:50:47,140 --> 00:50:51,389
Więc trie to kolejna ciekawa
amalgamat wiele z tych pomysłów.

1086
00:50:51,389 --> 00:50:52,930
Jest to drzewo, które widzieliśmy wcześniej.

1087
00:50:52,930 --> 00:50:54,180
To nie jest przeszukiwanie binarne drzewo.

1088
00:50:54,180 --> 00:50:58,410
Jest to drzewo z dowolnej liczby dzieci,
a każdy z dzieci w trie

1089
00:50:58,410 --> 00:51:00,090
jest tablicą.

1090
00:51:00,090 --> 00:51:04,790
Tablica wielkości, powiedzmy, 26 czy może 27
jeśli chcesz obsługuje nazw łącznikiem

1091
00:51:04,790 --> 00:51:06,790
lub apostrofy w nazwach ludzi.

1092
00:51:06,790 --> 00:51:08,280
>> A więc jest to struktura danych.

1093
00:51:08,280 --> 00:51:10,290
A jeśli spojrzeć od góry
do dołu, tak jakby Ciebie

1094
00:51:10,290 --> 00:51:13,710
spojrzeć na najwyższym węźle tam, M, jest
wskazując na skrajnej lewej rzeczy tam,

1095
00:51:13,710 --> 00:51:17,665
który następnie A, X, W, E, L, L. To
tylko struktura danych arbitralnie

1096
00:51:17,665 --> 00:51:19,120
jest zapisywanie nazwisk ludzi.

1097
00:51:19,120 --> 00:51:25,720
Maxwell są przechowywane tylko przez następujące
ścieżka tablicy do tablicy do tablicy.

1098
00:51:25,720 --> 00:51:30,050
Ale to, co niesamowite, około trie jest
że, podczas połączonej listy, a nawet

1099
00:51:30,050 --> 00:51:34,520
tablica, najlepsza, jaką kiedykolwiek dostał się
Czas czas liniowy lub logarytmiczny patrząc

1100
00:51:34,520 --> 00:51:35,600
ktoś się.

1101
00:51:35,600 --> 00:51:40,530
W tej strukturze danych z trie, jeżeli
moja struktura danych ma jedną nazwę w nim

1102
00:51:40,530 --> 00:51:43,720
i szukam Maxwell, jestem
będzie dość szybko go znaleźć.

1103
00:51:43,720 --> 00:51:47,910
I wystarczy spojrzeć na M-A-X-W-E-L-L. Gdyby
Ta struktura danych, natomiast

1104
00:51:47,910 --> 00:51:51,830
jeśli N jest milion, jeśli istnieje
milion nazw w tej strukturze danych,

1105
00:51:51,830 --> 00:51:57,100
Maxwell nadal będzie
wykrywalne po prostu M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
kroki.

1107
00:51:58,090 --> 00:52:01,276
I kroki David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
Innymi słowy, poprzez tworzenie
struktura danych, która jest

1109
00:52:03,400 --> 00:52:07,240
ale w których wszystkie z tych tablic, wszystkie
sami wspierać swobodny dostęp,

1110
00:52:07,240 --> 00:52:11,090
Mogę zacząć patrząc Ludowej
wymienić stosując ilość czasu, który jest

1111
00:52:11,090 --> 00:52:14,340
proporcjonalne do nie liczba
rzeczy w strukturze danych,

1112
00:52:14,340 --> 00:52:16,330
jak milion istniejące nazwy.

1113
00:52:16,330 --> 00:52:20,135
Ilość czasu zajmuje mi znaleźć
M-A-X-W-E-L-L w strukturze danych jest

1114
00:52:20,135 --> 00:52:22,260
proporcjonalna nie do
Wielkość struktur danych,

1115
00:52:22,260 --> 00:52:25,930
lecz długość nazwy.

1116
00:52:25,930 --> 00:52:28,440
A realnie
Nazwy szukamy się

1117
00:52:28,440 --> 00:52:29,970
nigdy nie będą szalone długo.

1118
00:52:29,970 --> 00:52:32,600
Może ktoś ma 10 charakter
wymienić, 20 nazwę postaci.

1119
00:52:32,600 --> 00:52:33,900
Na pewno skończona, prawda?

1120
00:52:33,900 --> 00:52:37,110
Jest człowiekiem na Ziemi, który
ma najdłuższą nazwę,

1121
00:52:37,110 --> 00:52:39,920
ale ta nazwa jest stałą
Długość wartości, prawda?

1122
00:52:39,920 --> 00:52:41,980
Nie różni się ona w jakimkolwiek sensie.

1123
00:52:41,980 --> 00:52:45,090
Tak więc w ten sposób mamy
osiągnąć strukturę danych

1124
00:52:45,090 --> 00:52:47,800
to stała czasowa przeglądowa.

1125
00:52:47,800 --> 00:52:50,670
To ma podjąć szereg kroków
W zależności od długości wkładu,

1126
00:52:50,670 --> 00:52:54,250
ale nie numer nazwy
w strukturze danych.

1127
00:52:54,250 --> 00:52:58,700
Jeśli więc podwoić liczbę nazw
w przyszłym roku od miliarda do dwóch miliardów,

1128
00:52:58,700 --> 00:53:03,720
Odkrycie Maxwell zajmie
dokładnie taka sama liczba siedmiu krokach

1129
00:53:03,720 --> 00:53:04,650
aby go odnaleźć.

1130
00:53:04,650 --> 00:53:08,810
A więc wydaje się, że osiągnięty
nasz Święty Graal czasu pracy.

1131
00:53:08,810 --> 00:53:10,860
>> Więc kilka szybkich ogłoszeń.

1132
00:53:10,860 --> 00:53:11,850
Quiz zera jest wymyślanie.

1133
00:53:11,850 --> 00:53:14,600
Więcej na ten temat na stronie internetowej kursu jest
w ciągu najbliższych kilku dni.

1134
00:53:14,600 --> 00:53:17,120
Poniedziałkowa lecture-- To święto
tutaj na Harvardzie w poniedziałek.

1135
00:53:17,120 --> 00:53:18,850
To nie jest w New Haven,
więc bierzemy klasę

1136
00:53:18,850 --> 00:53:20,310
do New Haven na wykładzie w poniedziałek.

1137
00:53:20,310 --> 00:53:22,550
Wszystko będzie sfilmowane
i transmitowane na żywo, jak zwykle,

1138
00:53:22,550 --> 00:53:24,900
ale niech kończy dziś
z 30 drugiego zacisku

1139
00:53:24,900 --> 00:53:26,910
zwane "głębokich myśli"
przez Daven Farnham, który

1140
00:53:26,910 --> 00:53:30,850
został zainspirowany w zeszłym roku przez sobotę
"Głębokie Myśli" Night Live

1141
00:53:30,850 --> 00:53:35,700
Jack Handy, który
powinien teraz sensu.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: A teraz, "Głębokie
Myśli "przez Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Tablica mieszająca.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> Głośnik 1: Dobra, to wszystko na teraz.

1147
00:53:47,660 --> 00:53:48,805
Do zobaczenia w przyszłym tygodniu.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Aby zobaczyć go w akcji.

1150
00:53:56,680 --> 00:53:58,304
Warto więc przyjrzeć się, że właśnie teraz.

1151
00:53:58,304 --> 00:53:59,890
Więc, mamy nieposortowanej tablicy.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, można iść dalej i restart
to tylko na jedną sekundę, proszę.

1153
00:54:04,860 --> 00:54:08,562
Dobrze, kamery są toczenia, więc
działania, jeżeli jesteś gotowy, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: No dobrze, więc co my
tu jest bez sortowania tablicy.

1155
00:54:11,020 --> 00:54:13,960
A ja kolorowe wszystkie elementy
czerwonego, co wskazuje na to, w rzeczywistości

1156
00:54:13,960 --> 00:54:14,460
nieposortowane.

1157
00:54:14,460 --> 00:54:17,960
Tak więc przypomnieć, że pierwszą rzeczą, jaką możemy zrobić
jest sortujemy lewą połowę tablicy.

1158
00:54:17,960 --> 00:54:20,630
Następnie sortować prawo
połowa macierzy.

1159
00:54:20,630 --> 00:54:22,830
I ya-da, ya-da, ya-da,
możemy je połączyć razem.

1160
00:54:22,830 --> 00:54:24,520
I mamy zupełnie posortowaną tablicę.

1161
00:54:24,520 --> 00:54:25,360
Tak to jest, jak sortowanie przez scalanie działa.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Zaraz, zaraz, zaraz,
cięcia, cięcia, cięcia, cięcia.

1163
00:54:27,109 --> 00:54:30,130
Doug, nie możesz po prostu ya-da, ya-da,
ya-da, na swój sposób przez sortowanie przez scalanie.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Właśnie tak.

1165
00:54:31,970 --> 00:54:32,832
Jest dobrze.

1166
00:54:32,832 --> 00:54:33,540
Jesteśmy dobrze iść.

1167
00:54:33,540 --> 00:54:34,760
Miejmy tylko utrzymać toczenia.

1168
00:54:34,760 --> 00:54:35,380
W każdym razie,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: trzeba wyjaśnić
to dokładniej niż.

1170
00:54:37,800 --> 00:54:39,999
To nie jest po prostu za mało.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, nie robimy
trzeba wrócić do jednego.

1172
00:54:41,790 --> 00:54:42,350
Jest dobrze.

1173
00:54:42,350 --> 00:54:45,690
W każdym razie, jeśli mamy kontynuować merge--
Ian, jesteśmy w środku kręcenia.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Wiem.

1175
00:54:46,612 --> 00:54:49,320
I nie możemy po prostu ya-da, ya-da,
ya-da, w całym procesie.

1176
00:54:49,320 --> 00:54:52,200
Trzeba wyjaśnić, w jaki sposób
Obie strony scalone razem.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Ale już mam
wyjaśnia, w jaki sposób dwie sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Po prostu pokazane
im tablica seryjnej.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Wiedzą, że ten proces.

1180
00:54:56,486 --> 00:54:57,172
Oni są w porządku.

1181
00:54:57,172 --> 00:54:58,380
Przeszliśmy nad nim dziesięć razy.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Po prostu pomijane tuż nad nim.

1183
00:55:00,330 --> 00:55:03,360
Wracamy do jednego,
Nie możesz ya-da, ya-da się nad nim.

1184
00:55:03,360 --> 00:55:05,480
Dobra, z powrotem do jednego.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Muszę wrócić
przez wszystkie prowadnice?

1186
00:55:07,833 --> 00:55:08,332
Mój Boże.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
To tak, jakby po raz szósty, Ian.

1189
00:55:13,004 --> 00:55:13,940
Jest dobrze.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Wszystko w porządku.

1191
00:55:15,200 --> 00:55:16,590
Jesteś gotowy?

1192
00:55:16,590 --> 00:55:17,400
Wielki.

1193
00:55:17,400 --> 00:55:18,950
Akcja.