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

2
00:00:10,900 --> 00:00:15,860
>> Sprecher 1: Okay, das ist so
CS50 Dies ist das Ende der fünften Woche.

3
00:00:15,860 --> 00:00:19,220
Und erinnern daran, dass wir das letzte Mal
begann man die Züchter Daten

4
00:00:19,220 --> 00:00:22,310
Strukturen, die zu lösen begonnen
Probleme, die die Einführung begonnen

5
00:00:22,310 --> 00:00:25,640
neue Probleme, doch der Schlüssel dazu
war die Art von Einfädeln, dass wir

6
00:00:25,640 --> 00:00:27,940
begonnen, von Knoten zu Knoten zu tun.

7
00:00:27,940 --> 00:00:30,085
Also das ist natürlich,
eine einfach verkettete Liste.

8
00:00:30,085 --> 00:00:31,960
Und einfach verkettete,
Ich meine, es gibt nur eine

9
00:00:31,960 --> 00:00:33,380
Faden zwischen jedem dieser Knoten.

10
00:00:33,380 --> 00:00:35,890
Stellt sich heraus, die Sie tun können, Züchter
Dinge wie doppelt verkettete Listen

11
00:00:35,890 --> 00:00:38,470
wobei Sie einen Pfeil haben
in beide Richtungen, die

12
00:00:38,470 --> 00:00:40,320
kann mit bestimmten Wirkungsgrade zu helfen.

13
00:00:40,320 --> 00:00:42,000
Aber dies das Problem gelöst?

14
00:00:42,000 --> 00:00:43,500
Welches Problem hat dieses Problem zu lösen?

15
00:00:43,500 --> 00:00:46,620
Warum haben wir am Montag, kümmern?

16
00:00:46,620 --> 00:00:49,820
Warum, in der Theorie, wir kümmern wir am Montag?

17
00:00:49,820 --> 00:00:50,630
Was tut es?

18
00:00:50,630 --> 00:00:51,950
>> Publikum: Wir können dynamisch ändern Sie die Größe.

19
00:00:51,950 --> 00:00:53,740
>> Sprecher 1: OK, also wir können
dynamisch ändern Sie die Größe.

20
00:00:53,740 --> 00:00:54,710
Gut gemacht, alle beide.

21
00:00:54,710 --> 00:00:57,560
So können Sie dynamisch die Größe dieses
Datenstruktur, wobei eine Anordnung,

22
00:00:57,560 --> 00:01:00,760
Recall, müssen Sie eine kennen
priori, wie viel Platz Sie wollen

23
00:01:00,760 --> 00:01:03,870
und wenn Sie ein wenig mehr
Art von Raum, sind Sie kein Glück.

24
00:01:03,870 --> 00:01:05,560
Sie müssen sich eine ganz neue Palette erstellen.

25
00:01:05,560 --> 00:01:07,893
Sie müssen alle bewegen Sie
Daten von einem zum anderen,

26
00:01:07,893 --> 00:01:10,600
schließlich befreien das alte Array
wenn du kannst, und dann fortzufahren.

27
00:01:10,600 --> 00:01:13,891
Was fühlt sich einfach sehr teuer und sehr
ineffizient, und in der Tat kann es sein.

28
00:01:13,891 --> 00:01:14,890
Aber das ist nicht alles gut.

29
00:01:14,890 --> 00:01:18,180
Wir zahlen einen Preis, was einem
der offensichtlicheren Preise, die wir

30
00:01:18,180 --> 00:01:20,550
bezahlen, indem Sie eine verkettete Liste?

31
00:01:20,550 --> 00:01:22,825
>> ZIELGRUPPE: Wir haben zu bedienen
Doppelraum für jeden einzelnen.

32
00:01:22,825 --> 00:01:25,200
Sprecher 1: Ja, so müssen wir uns
mindestens doppelt so viel Platz.

33
00:01:25,200 --> 00:01:27,700
In der Tat, erkannte ich, das Bild der
sogar ein wenig irreführend,

34
00:01:27,700 --> 00:01:32,200
denn am CS50 IDE in eine Menge von modernen
Computer, ein Zeiger oder eine Adresse

35
00:01:32,200 --> 00:01:33,700
ist in der Tat nicht vier Byte.

36
00:01:33,700 --> 00:01:36,090
Es ist sehr oft diese
Tage acht Bytes, die

37
00:01:36,090 --> 00:01:38,530
bedeutet die unterste
Rechtecke gibt es in der Realität

38
00:01:38,530 --> 00:01:40,900
sind so eine Art doppelt so
groß wie das, was ich gezeichnet habe,

39
00:01:40,900 --> 00:01:44,409
was bedeutet, dass Sie drei Mal so sind
viel Platz, da wir sonst haben könnte.

40
00:01:44,409 --> 00:01:46,700
Jetzt zur gleichen Zeit, wir sind
noch im Gespräch Bytes, nicht wahr?

41
00:01:46,700 --> 00:01:49,140
Wir sind nicht unbedingt sprechen
Megabyte oder Gigabyte,

42
00:01:49,140 --> 00:01:51,000
es sei denn, diesen Datenstrukturen zu groß.

43
00:01:51,000 --> 00:01:54,510
>> Und so beginnen wir heute zu prüfen,
wie wir Daten untersuchen könnten

44
00:01:54,510 --> 00:01:57,310
effizienter, wenn in
Tatsächlich werden die Daten immer größer.

45
00:01:57,310 --> 00:02:00,360
Aber lassen Sie uns versuchen, kanonisieren
die Operationen ersten

46
00:02:00,360 --> 00:02:02,460
dass Sie sich auf diese tun können
Arten von Datenstrukturen.

47
00:02:02,460 --> 00:02:04,790
So etwas wie eine verknüpfte
Liste in der Regel unterstützt

48
00:02:04,790 --> 00:02:07,514
Operationen wie Löschen,
einzufügen, und zu suchen.

49
00:02:07,514 --> 00:02:08,639
Und was mache ich damit?

50
00:02:08,639 --> 00:02:11,222
Das bedeutet nur, dass in der Regel,
wenn Menschen nutzen verknüpften Liste,

51
00:02:11,222 --> 00:02:14,287
sie oder jemand anderes eingeführt hat
Funktionen wie Löschen, Einfügen,

52
00:02:14,287 --> 00:02:16,120
und suchen, so können Sie
tatsächlich etwas zu tun

53
00:02:16,120 --> 00:02:18,030
nützlich bei der Datenstruktur.

54
00:02:18,030 --> 00:02:20,760
Werfen wir also einen Blick
an, wie wir implementieren

55
00:02:20,760 --> 00:02:24,530
ein Code für eine verkettete Liste wie folgt.

56
00:02:24,530 --> 00:02:27,885
>> Das ist also nur einige C-Code,
nicht einmal ein komplettes Programm

57
00:02:27,885 --> 00:02:29,260
dass ich wirklich schnell aufgepeitscht.

58
00:02:29,260 --> 00:02:32,300
Es ist nicht online in der Distribution
Code, weil es nicht tatsächlich ausgeführt.

59
00:02:32,300 --> 00:02:33,790
Aber ich habe gerade bemerkt
mit einem Kommentar sagte:

60
00:02:33,790 --> 00:02:36,130
Punkt Punkt Punkt, es gibt etwas,
dort, Punkt Punkt Punkt, dort etwas.

61
00:02:36,130 --> 00:02:38,410
Und lassen Sie uns einfach betrachten
was die saftige Teile sind.

62
00:02:38,410 --> 00:02:40,790
Also auf Linie drei,
daran erinnern, dass dies jetzt

63
00:02:40,790 --> 00:02:45,960
Wir haben vorgeschlagen, die Vereinbarkeit eines Knotens letzten
Zeit, eine jener rechteckige Objekte.

64
00:02:45,960 --> 00:02:48,790
Es verfügt über einen int, die wir N nennen,
aber wir nennen es könnte alles,

65
00:02:48,790 --> 00:02:51,920
und dann ein struct node Stern neben bezeichnet.

66
00:02:51,920 --> 00:02:55,520
Und genauso klar zu sein, dass die zweite
Linie, auf der Linie sechs, was ist das?

67
00:02:55,520 --> 00:02:57,930
Wie ist es für uns tut?

68
00:02:57,930 --> 00:03:01,044
Denn es sieht mehr
kryptisch als unsere üblichen Variablen.

69
00:03:01,044 --> 00:03:02,740
>> Publikum: Es macht es mehr als eine zu bewegen.

70
00:03:02,740 --> 00:03:04,650
>> Sprecher 1: Es macht es mehr als eine zu bewegen.

71
00:03:04,650 --> 00:03:08,580
Und um genauer zu sein,
es wird die Adresse zu speichern

72
00:03:08,580 --> 00:03:11,582
des Knotens, der gemeint hat, um sein
semantisch daneben, nicht wahr?

73
00:03:11,582 --> 00:03:13,540
So dass es nicht zu gehen
unbedingt etwas zu bewegen.

74
00:03:13,540 --> 00:03:15,290
Es ist gerade dabei,
speichern Wert, das ist,

75
00:03:15,290 --> 00:03:17,170
gehen, um die Adresse sein,
von einem anderen Knoten,

76
00:03:17,170 --> 00:03:20,810
und das ist, warum wir die Struktur
Knoten Stern, der Stern bezeichnet

77
00:03:20,810 --> 00:03:22,370
ein Zeiger oder eine Adresse.

78
00:03:22,370 --> 00:03:26,390
OK, so jetzt, wenn Sie annehmen, dass wir
Diese N zur Verfügung zu uns, und lassen Sie uns

79
00:03:26,390 --> 00:03:29,490
davon ausgehen, dass jemand anderes hat
eingefügt eine ganze Reihe von ganzen Zahlen

80
00:03:29,490 --> 00:03:30,400
in einer verketteten Liste.

81
00:03:30,400 --> 00:03:35,640
Und das verknüpfte Liste ist
die von einem gewissen Punkt hingewiesen

82
00:03:35,640 --> 00:03:39,040
eine Variable namens Liste, die ist
hier als Parameter übergeben,

83
00:03:39,040 --> 00:03:43,120
wie gehe ich über Linie gehen
14 Umsetzung Suche?

84
00:03:43,120 --> 00:03:45,990
Mit anderen Worten, wenn ich die Umsetzung
Funktion, deren Zweck im Leben

85
00:03:45,990 --> 00:03:48,889
ist es, eine int und dann das zu nehmen
beginnend von einer verknüpften Liste,

86
00:03:48,889 --> 00:03:50,430
das ist ein Zeiger auf die verbundene Liste.

87
00:03:50,430 --> 00:03:52,992
Wie erste, die ich denke, David
war unsere Freiwilligen am Montag,

88
00:03:52,992 --> 00:03:54,700
er wurde bei weis
die gesamte verknüpfte Liste,

89
00:03:54,700 --> 00:03:57,820
es ist, als ob wir vorbei
David in unser Argument hier.

90
00:03:57,820 --> 00:03:59,990
Wie sprechen wir über das Durchlaufen dieser Liste gehen?

91
00:03:59,990 --> 00:04:04,640
Nun stellt sich heraus, dass, obwohl
Zeiger sind relativ neu jetzt an uns,

92
00:04:04,640 --> 00:04:07,010
wir können dies relativ zu tun
unkompliziert.

93
00:04:07,010 --> 00:04:09,500
>> Ich werde weitermachen und
deklarieren Sie eine temporäre Variable,

94
00:04:09,500 --> 00:04:12,364
per Konvention wird nur gehen
Zeiger aufgerufen werden, oder PTR,

95
00:04:12,364 --> 00:04:14,030
aber Sie es nennen könnte, was Sie wollen.

96
00:04:14,030 --> 00:04:16,470
Und ich werde nicht initialisiert werden
der auf den Anfang der Liste.

97
00:04:16,470 --> 00:04:20,050
So können Sie Art denken Sie an dieses
wie ich dem Lehrer den anderen Tag,

98
00:04:20,050 --> 00:04:23,580
Art auf jemand zeigt
unter unseren Menschen als Freiwillige.

99
00:04:23,580 --> 00:04:26,470
Ich bin also eine temporäre Variable, die ist
nur zeigt auf die gleiche Sache

100
00:04:26,470 --> 00:04:31,390
dass unsere zufällig benannt
Freiwilliger David wurde auch darauf hingewiesen.

101
00:04:31,390 --> 00:04:35,440
Jetzt, während Zeiger
nicht null ist, weil Rückruf

102
00:04:35,440 --> 00:04:40,350
dass null ist einige spezielle Sentinelwert
das grenzt das Ende der Liste,

103
00:04:40,350 --> 00:04:44,280
so, während ich nicht das Zeige
Boden wie unsere letzte Freiwilligen

104
00:04:44,280 --> 00:04:47,190
war, lassen Sie uns weitermachen
und gehen Sie folgendermaßen vor.

105
00:04:47,190 --> 00:04:51,820
Wenn pointer-- und jetzt bin Art von wollen
zu tun, was wir mit dem Schüler haben

106
00:04:51,820 --> 00:04:57,410
structure-- wenn Zeiger Punkt neben
equals-- eher, wenn Zeiger dot N gleich

107
00:04:57,410 --> 00:05:02,290
entspricht die Variable N, die
Argument, die übergeben worden ist,

108
00:05:02,290 --> 00:05:05,370
dann will ich voran gehen
und sagen, return true.

109
00:05:05,370 --> 00:05:11,020
Ich habe die Anzahl N Innenseite gefunden
einem der Knoten meiner verketteten Liste.

110
00:05:11,020 --> 00:05:13,500
Aber der Punkt nicht mehr
arbeitet in diesem Zusammenhang,

111
00:05:13,500 --> 00:05:17,260
weil Zeiger PTR ist
tatsächlich ein Zeiger, um eine Adresse,

112
00:05:17,260 --> 00:05:20,632
Wir können tatsächlich wunderbar
benutzen endlich ein Stück Syntax

113
00:05:20,632 --> 00:05:22,590
diese Art von Marken
intuitiven Sinn und tatsächlich

114
00:05:22,590 --> 00:05:27,870
verwenden einen Pfeil hier, was bedeutet, gehen von
diese Adresse auf den ganzzahligen dort.

115
00:05:27,870 --> 00:05:30,160
So ist es in sehr ähnlich
Grundprinzip her der Punkt-Operator,

116
00:05:30,160 --> 00:05:33,860
sondern weil Zeiger kein Zeiger
und nicht eine tatsächliche Struktur selbst,

117
00:05:33,860 --> 00:05:35,380
wir benutzen Sie einfach auf den Pfeil.

118
00:05:35,380 --> 00:05:40,620
>> Also, wenn der aktuelle Knoten daß ich, der
temporäre Variable, bin am Zeige

119
00:05:40,620 --> 00:05:43,060
nicht N, was will ich machen?

120
00:05:43,060 --> 00:05:45,910
Na ja, mit meinem menschlichen Freiwilligen
dass wir hier den anderen Tag,

121
00:05:45,910 --> 00:05:49,710
wenn meine erste Mensch ist nicht der, den ich
wollen, und vielleicht der zweite Mensch ist nicht

122
00:05:49,710 --> 00:05:52,660
die, die ich will, und der dritte, I
müssen körperlich in Bewegung bleiben.

123
00:05:52,660 --> 00:05:54,690
Wie, wie kann ich Schritt durch eine Liste?

124
00:05:54,690 --> 00:05:57,470
Als wir ein Array Sie,
gerade getan hast, wie ich plus plus.

125
00:05:57,470 --> 00:06:03,660
Aber in diesem Fall ist es ausreichend,
tun Zeiger, bekommt, Zeiger, neben.

126
00:06:03,660 --> 00:06:07,580
Mit anderen Worten, das nächste Feld,
ist wie alle der linken Hände

127
00:06:07,580 --> 00:06:10,880
dass unsere menschlichen Freiwilligen am Montag,
wurden mit den an einem anderen Knotenpunkt.

128
00:06:10,880 --> 00:06:12,890
Das waren ihre nächsten Nachbarn.

129
00:06:12,890 --> 00:06:17,060
>> Also, wenn ich durch diese Liste zu treten,
Ich kann nicht einfach zu tun I plus plus mehr,

130
00:06:17,060 --> 00:06:20,120
Ich muss sagen, statt
I, Zeiger, wird

131
00:06:20,120 --> 00:06:24,650
um gleiche, was auch immer das nächste Feld ist,
Das nächste Feld ist, ist das nächste Feld,

132
00:06:24,650 --> 00:06:28,350
nach all diesen linke Hand
dass wir auf der Bühne hatten Zeige

133
00:06:28,350 --> 00:06:30,000
zu einigen Folgewerte.

134
00:06:30,000 --> 00:06:32,590
Und wenn ich durchkommen
dass ganze Iteration

135
00:06:32,590 --> 00:06:39,330
und schließlich, schlug ich null nicht mit
fand N noch, ich habe gerade return false.

136
00:06:39,330 --> 00:06:44,100
Also noch einmal, alles, was wir hier tun,
nach dem Bild vor einem Augenblick,

137
00:06:44,100 --> 00:06:47,840
beginnt mit dem Hinweis auf die
Anfang der Liste vermutlich.

138
00:06:47,840 --> 00:06:50,970
Und dann habe ich zu prüfen, ist der Wert
Ich suche nach gleich neun?

139
00:06:50,970 --> 00:06:52,650
Wenn dem so ist, kehre ich wahr und ich fertig bin.

140
00:06:52,650 --> 00:06:56,450
Wenn nicht, ich meine Hand zu aktualisieren,
Alias-Zeiger, darauf hinzuweisen

141
00:06:56,450 --> 00:06:59,540
am Standort des nächsten Pfeils, und
dann Standort der nächsten Pfeils,

142
00:06:59,540 --> 00:07:00,480
und dem nächsten.

143
00:07:00,480 --> 00:07:03,770
Ich bin einfach zu Fuß durch dieses Array.

144
00:07:03,770 --> 00:07:06,010
>> Also noch einmal, wer sich interessiert?

145
00:07:06,010 --> 00:07:07,861
Wie, was ist dies ein Bestandteil für?

146
00:07:07,861 --> 00:07:10,360
Nun, daran erinnern, dass wir uns vorgestellt
die Vorstellung von einem Stapel, der

147
00:07:10,360 --> 00:07:15,400
ist ein abstrakter Datentyp, soweit es
kein C Sache, es ist nicht eine Sache, CS50,

148
00:07:15,400 --> 00:07:19,430
es ist eine abstrakte Idee, diese Idee der
Stapel Dinge aufeinander

149
00:07:19,430 --> 00:07:21,820
Das kann umgesetzt werden
Bündeln von verschiedenen Möglichkeiten.

150
00:07:21,820 --> 00:07:25,600
Und eine Möglichkeit, die wir vorgeschlagen war mit
ein Array oder eine verknüpfte Liste.

151
00:07:25,600 --> 00:07:29,570
Und es stellt sich heraus, dass kanonisch ein
Stack unterstützt mindestens zwei Operationen.

152
00:07:29,570 --> 00:07:32,320
Und die Schlagworte sind Push, um
drücken Sie etwas auf dem Stapel,

153
00:07:32,320 --> 00:07:34,770
wie ein neues Fach in der
Speisesaal, oder Pop,

154
00:07:34,770 --> 00:07:39,000
was bedeutet, den obersten entfernen
Tablett aus dem Stapel im Speisesaal

155
00:07:39,000 --> 00:07:41,500
Flur, und dann vielleicht noch einige
andere Operationen als auch.

156
00:07:41,500 --> 00:07:45,770
Also, wie können wir definieren die Struktur
dass wir fordern nun einen Stapel?

157
00:07:45,770 --> 00:07:50,020
>> Nun, wir haben alle die erforderliche
Syntax zur Verfügung in C, sage ich,

158
00:07:50,020 --> 00:07:53,830
geben Sie mir eine Typdefinition
eine Struktur innerhalb eines Stapels,

159
00:07:53,830 --> 00:07:58,030
Ich werde sagen, ein Array ist, der eine
ganze Reihe von Zahlen und dann deine Größe.

160
00:07:58,030 --> 00:08:00,930
Also mit anderen Worten, wenn ich will,
dies im Code zu implementieren,

161
00:08:00,930 --> 00:08:03,830
lassen Sie mich gehen und nur irgendwie
zu ziehen, was dieser sagt.

162
00:08:03,830 --> 00:08:06,317
Also das ist zu sagen, gib mir ein
Struktur, die ein Array bekam ist,

163
00:08:06,317 --> 00:08:09,400
und ich weiß nicht, was Kapazität ist,
es ist offensichtlich eine Konstante, die ich

164
00:08:09,400 --> 00:08:10,858
an anderer Stelle definiert ist, und das ist in Ordnung.

165
00:08:10,858 --> 00:08:15,260
Aber angenommen, es ist nur eine,
zwei, drei, vier, fünf.

166
00:08:15,260 --> 00:08:16,700
So Kapazität ist 5.

167
00:08:16,700 --> 00:08:21,730
Dieses Element Innenseite meiner
Struktur Zahlen genannt werden.

168
00:08:21,730 --> 00:08:24,020
Und dann, eines muss ich
andere nicht fest offenbar

169
00:08:24,020 --> 00:08:27,814
genannte Größe, die zunächst werde ich
zu bestimmen, wird auf Null initialisiert.

170
00:08:27,814 --> 00:08:29,730
Wenn es nichts in
der Stapel, Größe Null ist,

171
00:08:29,730 --> 00:08:31,420
und es ist Müll Werte in Zahlen.

172
00:08:31,420 --> 00:08:33,450
Ich habe keine Ahnung, was da drin nur noch.

173
00:08:33,450 --> 00:08:36,059
>> Also, wenn ich drücken
etwas in den Stapel,

174
00:08:36,059 --> 00:08:40,780
nehme ich die Funktion Push anrufen, und
Ich sage zu schieben 50, wie die Zahl 50,

175
00:08:40,780 --> 00:08:44,090
wo würden Sie vorschlagen
Ich ziehe es in diesem Array?

176
00:08:44,090 --> 00:08:47,124
Es gibt fünf verschiedene mögliche Antworten.

177
00:08:47,124 --> 00:08:48,790
Wo wollen Sie, um die Zahl 50 zu schieben?

178
00:08:48,790 --> 00:08:51,899
Wenn das Ziel ist hier, wieder, rufen Sie die
Funktionsdruck, übergeben in einem Argument

179
00:08:51,899 --> 00:08:52,940
von 50, wo soll ich sagen?

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

181
00:08:55,680 --> 00:08:59,052
Fünf possible-- Chance von 20%
richtig zu raten.

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

183
00:08:59,896 --> 00:09:00,740
>> ZIELGRUPPE: Ganz rechts.

184
00:09:00,740 --> 00:09:01,990
>> Sprecher 1: Ganz rechts.

185
00:09:01,990 --> 00:09:08,359
Es gibt nun eine Chance von 25%
richtig zu raten.

186
00:09:08,359 --> 00:09:09,650
Also das wäre eigentlich in Ordnung sein.

187
00:09:09,650 --> 00:09:12,770
Gemäß der Konvention, werde ich mit einer Reihe sagen,
wir würden in der Regel auf der linken Seite zu beginnen,

188
00:09:12,770 --> 00:09:14,519
aber wir konnten auf jeden Fall
beginnen an der rechten Seite.

189
00:09:14,519 --> 00:09:17,478
So der Spoiler hier wäre ich
wahrscheinlich, um es auf der linken Seite zu ziehen,

190
00:09:17,478 --> 00:09:20,060
genau wie in einem normalen Array, in dem
Ich beginnen werde links nach rechts.

191
00:09:20,060 --> 00:09:21,780
Aber wenn Sie drehen können
der arithmetische, fein.

192
00:09:21,780 --> 00:09:23,060
Es ist einfach nicht üblich.

193
00:09:23,060 --> 00:09:24,880
OK, ich brauche eine zu machen
weitere Änderung though.

194
00:09:24,880 --> 00:09:27,710
Nun, da ich etwas geschoben
auf den Stapel, was kommt als nächstes?

195
00:09:27,710 --> 00:09:29,400
>> Also gut, ich habe, um die Größe zu erhöhen.

196
00:09:29,400 --> 00:09:32,600
Also lassen Sie mich voran und gehen Sie einfach
aktualisieren diese, die Null war.

197
00:09:32,600 --> 00:09:35,950
Und statt jetzt, ich werde
in den Wert eins gesetzt.

198
00:09:35,950 --> 00:09:39,460
Und jetzt nehme ich eine andere schieben
auf den Stapel, wie 51.

199
00:09:39,460 --> 00:09:42,680
Nun, ich habe noch einen machen
Änderung, die bis zu einer Größe zwei ist.

200
00:09:42,680 --> 00:09:46,100
Und dann nehme ich noch einen Push
Nummer auf den Stapel, wie 61,

201
00:09:46,100 --> 00:09:52,530
jetzt brauche ich, um die Größe zu aktualisieren, noch eine
Zeit, und erhalten Sie den Wert 3 als Größe.

202
00:09:52,530 --> 00:09:54,690
Und jetzt nehme ich als Pop.

203
00:09:54,690 --> 00:09:57,250
Jetzt öffnet, durch Konvention,
nicht ein Argument.

204
00:09:57,250 --> 00:10:00,430
Mit einem Stapel, der ganze
Punkt des Fachs Metapher

205
00:10:00,430 --> 00:10:03,450
ist, dass Sie keinen Ermessensspielraum
zu holen, dass Tablett, alles, was Sie tun können,

206
00:10:03,450 --> 00:10:06,330
Pop ist das oberste eine aus
der Stapel, nur weil.

207
00:10:06,330 --> 00:10:08,010
Das ist, was diese Datenstruktur tut.

208
00:10:08,010 --> 00:10:12,250
>> So nach dieser Logik, wenn ich
sagen, pop, was kommt aus?

209
00:10:12,250 --> 00:10:13,080
So 61.

210
00:10:13,080 --> 00:10:15,402
Also, was ist wirklich der Computer
gehen, um in Erinnerung zu tun?

211
00:10:15,402 --> 00:10:16,610
Was bedeutet mein Code zu tun haben?

212
00:10:16,610 --> 00:10:20,330
Was würden Sie vorschlagen,
wir auf dem Bildschirm zu ändern?

213
00:10:20,330 --> 00:10:23,410
Was sollte sich ändern?

214
00:10:23,410 --> 00:10:24,960
Es tut uns leid?

215
00:10:24,960 --> 00:10:26,334
So bekommen wir von 61 zu befreien.

216
00:10:26,334 --> 00:10:27,500
So kann ich auf jeden Fall tun.

217
00:10:27,500 --> 00:10:28,640
Und ich kann von 61 loszuwerden.

218
00:10:28,640 --> 00:10:30,980
Und dann, was andere
Veränderung muss geschehen?

219
00:10:30,980 --> 00:10:33,160
Größe hat wohl wieder auf zwei zu gehen.

220
00:10:33,160 --> 00:10:34,210
Und so ist das in Ordnung.

221
00:10:34,210 --> 00:10:36,690
Aber warten Sie eine Minute, Größe
vor einem Augenblick war drei.

222
00:10:36,690 --> 00:10:38,240
Lassen Sie uns einfach eine schnelle Plausibilitätsprüfung zu tun.

223
00:10:38,240 --> 00:10:41,810
Wie haben wir uns, dass wir
wollte von 61 loswerden?

224
00:10:41,810 --> 00:10:42,760
Weil wir knallen.

225
00:10:42,760 --> 00:10:46,450
Und so habe ich diese zweite Eigenschaft Größe.

226
00:10:46,450 --> 00:10:48,470
>> Warten Sie eine Minute, ich bin
Denken zurück zu Woche zwei

227
00:10:48,470 --> 00:10:51,660
wenn wir kamen ins Gespräch über
Arrays, wo dies Lage Null,

228
00:10:51,660 --> 00:10:55,920
dies war ein Ort, war dies Lage
Zwei, ist dies Lage drei, vier,

229
00:10:55,920 --> 00:10:58,460
es sieht aus wie die
Beziehung zwischen Größe

230
00:10:58,460 --> 00:11:02,780
und das Element, das möchte ich entfernen
aus dem Feld erscheint nur, was?

231
00:11:02,780 --> 00:11:05,120
Größe minus eins.

232
00:11:05,120 --> 00:11:07,786
Und so das ist, wie als Menschen
wir wissen, 61 an erster Stelle.

233
00:11:07,786 --> 00:11:09,160
Wie geht der Computer geht zu wissen?

234
00:11:09,160 --> 00:11:11,701
Wenn Sie Ihren Code, wo Sie wahrscheinlich
wollen Größe minus eins zu tun,

235
00:11:11,701 --> 00:11:14,950
so drei minus eins ist zwei, und das
bedeutet, wollen wir von 61 loszuwerden.

236
00:11:14,950 --> 00:11:18,000
Und dann werden wir in der Tat zu aktualisieren können
die Größe, so dass die Größe jetzt

237
00:11:18,000 --> 00:11:20,300
geht von drei auf zwei.

238
00:11:20,300 --> 00:11:24,520
Und nur um pedantisch zu sein, werde ich
vorzuschlagen, dass ich fertig bin, nicht wahr?

239
00:11:24,520 --> 00:11:27,660
Sie schlug intuitiv
korrekt sollte ich von 61 loszuwerden.

240
00:11:27,660 --> 00:11:30,700
Aber haben nicht die Art von I
Art bekommen von 61 zu befreien?

241
00:11:30,700 --> 00:11:33,790
Ich habe effektiv vergessen
dass es tatsächlich gibt.

242
00:11:33,790 --> 00:11:37,680
Und denken Sie zurück an PSET4, wenn Sie gelesen haben,
Der Artikel über Forensik, die PDF-

243
00:11:37,680 --> 00:11:40,780
dass wir euch zu lesen, oder Sie
wird diese Woche für PSET4 lesen.

244
00:11:40,780 --> 00:11:44,300
Erinnern, dass dies tatsächlich relevant für
die ganze Idee der Computer-Forensik.

245
00:11:44,300 --> 00:11:47,820
Was ein Computer in der Regel tut, ist,
es einfach vergisst, wo etwas ist,

246
00:11:47,820 --> 00:11:51,300
aber es funktioniert nicht in zu gehen und wie
versuchen, es auskratzen oder Override-

247
00:11:51,300 --> 00:11:54,560
jene Bits mit Nullen und Einsen
oder eine andere Zufallsmuster

248
00:11:54,560 --> 00:11:56,690
es sei denn, Sie selbst tun, so bewusst.

249
00:11:56,690 --> 00:11:58,930
So Ihre Intuition war
Okay, lassen Sie von 61 zu befreien.

250
00:11:58,930 --> 00:12:00,650
Aber in Wirklichkeit haben wir nicht zu stören.

251
00:12:00,650 --> 00:12:04,040
Wir müssen nur vergessen, dass
es ist da durch Veränderung unserer Größe.

252
00:12:04,040 --> 00:12:05,662
>> Jetzt gibt es ein Problem mit diesem Stack.

253
00:12:05,662 --> 00:12:07,620
Wenn ich weiter pushen Dinge
auf den Stapel, was ist

254
00:12:07,620 --> 00:12:11,167
offensichtlich passieren
in nur ein paar Augenblicke Zeit?

255
00:12:11,167 --> 00:12:12,500
Wir werden aus dem Raum laufen.

256
00:12:12,500 --> 00:12:13,580
Und was machen wir jetzt?

257
00:12:13,580 --> 00:12:14,680
Wir Art verschraubt.

258
00:12:14,680 --> 00:12:19,000
Diese Implementierung nicht lassen
uns die Größe des Array, denn mit

259
00:12:19,000 --> 00:12:21,240
diese Syntax, wenn Sie
denken Sie zurück an der Woche zwei,

260
00:12:21,240 --> 00:12:23,520
wenn Sie erklärt haben
die Größe eines Arrays,

261
00:12:23,520 --> 00:12:26,780
haben wir nicht einen Mechanismus noch nicht, wo zu sehen
Sie können die Größe des Arrays ändern.

262
00:12:26,780 --> 00:12:29,020
Und in der Tat C nicht über diese Funktion.

263
00:12:29,020 --> 00:12:32,524
Wenn Sie sagen, gib mir fünf
Nths, nennen sie Zahlen,

264
00:12:32,524 --> 00:12:33,940
das ist alles, du gehst, es zu bekommen sind.

265
00:12:33,940 --> 00:12:38,790
So tun wir jetzt ab Montag, haben
die Fähigkeit, eine Lösung zu äußern

266
00:12:38,790 --> 00:12:42,480
aber, müssen wir nur noch zwicken
die Definition unserer Stapel

267
00:12:42,480 --> 00:12:46,840
einige hartcodierte Array nicht sein,
aber nur, um eine Adresse zu speichern.

268
00:12:46,840 --> 00:12:47,890
>> Nun, warum ist das?

269
00:12:47,890 --> 00:12:51,690
Jetzt müssen wir nur komfortabel mit zu sein
die Tatsache, dass, wenn mein Programm läuft,

270
00:12:51,690 --> 00:12:53,730
Ich bin vermutlich werde
haben, um die menschliche stellen,

271
00:12:53,730 --> 00:12:55,110
wie viele Zahlen Sie speichern möchten?

272
00:12:55,110 --> 00:12:56,776
So der Eingang von irgendwoher kommen.

273
00:12:56,776 --> 00:12:59,140
Aber sobald ich weiß, dass
Zahl ist, dann kann ich nur

274
00:12:59,140 --> 00:13:02,470
verwenden, welche Funktion zu geben,
mich ein Teil des Speichers?

275
00:13:02,470 --> 00:13:03,580
Ich kann malloc verwenden.

276
00:13:03,580 --> 00:13:06,710
Und ich kann sagen, dass eine beliebige Anzahl von
bytes Ich möchte wieder für diese Nths.

277
00:13:06,710 --> 00:13:10,910
Und alles, was ich in den Nummern speichern
variable hier innerhalb dieser Struktur

278
00:13:10,910 --> 00:13:13,480
sollten, was sein?

279
00:13:13,480 --> 00:13:18,440
Was tatsächlich in der geht
Zahlen in diesem Szenario?

280
00:13:18,440 --> 00:13:21,300
Ja, ein Zeiger auf das erste
Byte dieser Teil des Speichers,

281
00:13:21,300 --> 00:13:24,940
oder genauer gesagt, die Adresse,
der erste dieser Bytes.

282
00:13:24,940 --> 00:13:27,300
Egal, ob es eines
Byte oder eine Milliarde Bytes,

283
00:13:27,300 --> 00:13:28,890
Ich muss nur um die erste zu kümmern.

284
00:13:28,890 --> 00:13:31,530
Denn was malloc Garantien und
mein Betriebssystem garantiert,

285
00:13:31,530 --> 00:13:34,170
ist, dass der Teil des Speichers I
zu erhalten, wird es zusammenhängend sein.

286
00:13:34,170 --> 00:13:35,378
Es wird nicht zu Lücken aufweisen kann.

287
00:13:35,378 --> 00:13:38,576
Also, wenn ich für 50 gebeten
Bytes oder 1000 Bytes,

288
00:13:38,576 --> 00:13:40,450
sie alle sein wird
zurück zu zurück zu zurück.

289
00:13:40,450 --> 00:13:44,500
Und so lange ich mich erinnern, wie groß, wie
viel fragte ich nach, alles, was ich wissen muss

290
00:13:44,500 --> 00:13:46,230
ist die erste Adresse.

291
00:13:46,230 --> 00:13:48,660
>> So, jetzt haben wir die Möglichkeit im Code.

292
00:13:48,660 --> 00:13:51,280
Wenn auch nur, es geht um uns zu nehmen
mehr Zeit, dies zu schreiben up,

293
00:13:51,280 --> 00:13:55,900
wir könnten jetzt umzuschichten, dass der Speicher durch
nur eine andere Adresse speichert es

294
00:13:55,900 --> 00:13:59,060
wenn wir wollen, eine größere oder sogar
ein kleinerer Teil des Speichers.

295
00:13:59,060 --> 00:14:00,170
So, hier zu einem Kompromiss.

296
00:14:00,170 --> 00:14:01,360
Jetzt bekommen wir Dynamik.

297
00:14:01,360 --> 00:14:03,350
Wir haben noch
contiguousness ich behaupten.

298
00:14:03,350 --> 00:14:05,881
Weil malloc wird uns
ein zusammenhängender Teil des Speichers.

299
00:14:05,881 --> 00:14:08,630
Aber das wird ein Schmerz in sein
der Hals für uns, der Programmierer,

300
00:14:08,630 --> 00:14:09,770
um tatsächlich Code oben.

301
00:14:09,770 --> 00:14:10,730
Es ist nur mehr Arbeit.

302
00:14:10,730 --> 00:14:13,930
Wir benötigen Code verwandt, was ich
eben noch hämmern.

303
00:14:13,930 --> 00:14:16,120
Sehr machbar, aber es erhöht die Komplexität.

304
00:14:16,120 --> 00:14:19,520
Und so Entwicklungszeit, Programmierer
Es ist noch eine weitere Ressource

305
00:14:19,520 --> 00:14:22,520
dass wir brauchen, um zu verbringen
einige Zeit, um neue Funktionen zu erhalten.

306
00:14:22,520 --> 00:14:24,020
Und dann natürlich gibt es eine Warteschlange.

307
00:14:24,020 --> 00:14:26,227
Wir werden nicht in diese zu gelangen
eine in vielen Details.

308
00:14:26,227 --> 00:14:27,560
Aber es ist im Geiste sehr ähnlich.

309
00:14:27,560 --> 00:14:31,220
Ich konnte eine Warteschlange zu implementieren, und
ihre entsprechenden Operationen,

310
00:14:31,220 --> 00:14:35,660
Enqueue oder dequeue, wie hinzuzufügen oder zu entfernen,
es ist nur ein schicker Art zu sagen, ist es,

311
00:14:35,660 --> 00:14:38,100
enqueue oder dequeue, wie folgt.

312
00:14:38,100 --> 00:14:41,170
Ich kann mir selbst eine struct
hat, dass wieder ein Zahlen-Array,

313
00:14:41,170 --> 00:14:44,000
hat, dass wieder eine Größe,
aber warum muss ich jetzt brauchen

314
00:14:44,000 --> 00:14:46,940
zu verfolgen, der vor einer Warteschlange zu halten?

315
00:14:46,940 --> 00:14:50,630
Ich brauchte nicht zu wissen,
die vor meinem Stack.

316
00:14:50,630 --> 00:14:53,570
Nun, wenn ich wieder für ein
queue-- lassen Sie uns nur schwer

317
00:14:53,570 --> 00:14:57,870
Code als mit wie fünf
Zahlen hier möglicherweise.

318
00:14:57,870 --> 00:15:00,940
So dass dieser null, eins, zwei, drei, vier.

319
00:15:00,940 --> 00:15:03,430
Dies wird sein,
rufenen Nummern erneut.

320
00:15:03,430 --> 00:15:06,940
Und dies wird genannt Größe sein.

321
00:15:06,940 --> 00:15:10,056
>> Warum ist es nicht ausreichend,
nur Größe haben?

322
00:15:10,056 --> 00:15:11,680
Nun, lassen Sie schieben die gleichen Zahlen auf.

323
00:15:11,680 --> 00:15:14,220
So pushed-- ich eingereiht, oder geschoben.

324
00:15:14,220 --> 00:15:20,150
Jetzt werde ich Enqueue 50, und dann
51, und 61 und Punkt Punkt Punkt.

325
00:15:20,150 --> 00:15:21,070
Also das ist, Enqueue.

326
00:15:21,070 --> 00:15:23,176
Ich reiht 50, dann 51, dann 61.

327
00:15:23,176 --> 00:15:25,050
Und das sieht identisch
zu einem Stapel so weit,

328
00:15:25,050 --> 00:15:27,190
außer ich tun müssen, um eine Änderung vorzunehmen.

329
00:15:27,190 --> 00:15:33,680
Ich brauche, um diese Größe zu aktualisieren, so dass ich gehen
von null auf eins, zwei bis drei bekommen.

330
00:15:33,680 --> 00:15:35,760
Wie kann ich aus der Warteschlange entfernt?

331
00:15:35,760 --> 00:15:36,890
Was passiert mit dequeue?

332
00:15:36,890 --> 00:15:41,950
Wer sollte zuerst kommen aus dieser Liste
ob es die Zeile im Apple Store?

333
00:15:41,950 --> 00:15:42,780
So 50.

334
00:15:42,780 --> 00:15:44,700
So ist es Art von komplizierter diesmal.

335
00:15:44,700 --> 00:15:47,880
Während im letzten Mal war es Super-
leicht, einfach zu tun Größe minus eins,

336
00:15:47,880 --> 00:15:51,440
Ich zum Ende meiner Array effektiv erhalten
wobei die Zahlen sind, entfernt es 61.

337
00:15:51,440 --> 00:15:52,920
Aber ich will nicht zu entfernen 61.

338
00:15:52,920 --> 00:15:55,030
Ich möchte 50 zu nehmen, der
war es um 5:00 Uhr

339
00:15:55,030 --> 00:15:56,790
um sich für die
neue iPhone oder Dingsbums.

340
00:15:56,790 --> 00:16:01,200
Und so, um von 50 loszuwerden, I
können nicht einfach tun, nicht wahr?

341
00:16:01,200 --> 00:16:02,547
Ich kann streiche 50.

342
00:16:02,547 --> 00:16:04,380
Aber wir gesagt, dass wir nur
haben nicht so anal zu sein

343
00:16:04,380 --> 00:16:06,330
wie zu kratzen oder die Daten zu verstecken.

344
00:16:06,330 --> 00:16:08,090
Wir können einfach vergessen, wo es ist.

345
00:16:08,090 --> 00:16:12,330
>> Aber wenn ich meine Größe jetzt zu ändern
Zwei, ist dies ausreichend Informationen

346
00:16:12,330 --> 00:16:15,711
zu wissen, was los ist in meiner Warteschlange?

347
00:16:15,711 --> 00:16:16,680
Nicht wirklich.

348
00:16:16,680 --> 00:16:19,830
Wie meine Größe zwei, sondern
Woher kommt die Warteschlange zu beginnen,

349
00:16:19,830 --> 00:16:22,980
vor allem, wenn ich noch
die gleichen Nummern im Speicher.

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

351
00:16:24,260 --> 00:16:27,090
Also muss ich daran erinnern,
Jetzt, wo die Front ist.

352
00:16:27,090 --> 00:16:29,630
Und so wie ich vorgeschlagen up
da wir gerade genannt haben werde

353
00:16:29,630 --> 00:16:33,729
Nth Front, deren Anfangs
Wert gewesen sein sollte, was?

354
00:16:33,729 --> 00:16:35,270
Zero, nur der Anfang der Liste.

355
00:16:35,270 --> 00:16:40,876
Aber jetzt zusätzlich zum Dekrementieren
die Größe, wir erhöhen die Front.

356
00:16:40,876 --> 00:16:42,000
Nun, hier ist ein anderes Problem.

357
00:16:42,000 --> 00:16:43,030
Also, wenn ich weiterzumachen.

358
00:16:43,030 --> 00:16:47,520
Angenommen, dies ist die Anzahl von
wie 121, 124, und dann, verdammt noch mal,

359
00:16:47,520 --> 00:16:48,610
Ich bin aus dem Raum.

360
00:16:48,610 --> 00:16:50,390
Aber warten Sie eine Minute, ich bin mir nicht.

361
00:16:50,390 --> 00:16:55,630
So an diesem Punkt in der Geschichte,
Angenommen, dass die Größe ein, zwei,

362
00:16:55,630 --> 00:17:00,370
drei, vier, so angenommen, daß die
Größe ist vier, die Front ist eine,

363
00:17:00,370 --> 00:17:01,621
so 51 ist an der Vorderseite.

364
00:17:01,621 --> 00:17:04,329
Ich möchte eine andere Zahl hier zu setzen,
aber, verdammt, ich bin aus dem Raum.

365
00:17:04,329 --> 00:17:06,710
Aber ich bin nicht wirklich, oder?

366
00:17:06,710 --> 00:17:11,192
Wo könnte ich einige setzen
Mehrwert wie 171?

367
00:17:11,192 --> 00:17:13,400
Ja, könnte ich nur irgendwie
gehen Sie zurück dort, nicht wahr?

368
00:17:13,400 --> 00:17:18,161
Und dann über die 50 oder
einfach überschreiben ihn mit 171.

369
00:17:18,161 --> 00:17:20,410
Und wenn Sie sich fragen, warum
unsere Zahlen wurden so zufällig,

370
00:17:20,410 --> 00:17:24,150
diese sind häufig Computer übernommen
Wissenschaftskurse in Harvard, nachdem CS50.

371
00:17:24,150 --> 00:17:27,510
Aber das war eine gute Optimierung,
denn jetzt bin ich nicht Platzverschwendung.

372
00:17:27,510 --> 00:17:30,750
Ich habe immer noch daran zu erinnern,
wie groß das Ding ist total.

373
00:17:30,750 --> 00:17:31,500
Es ist fünf insgesamt.

374
00:17:31,500 --> 00:17:33,375
Weil ich nicht möchte
Start überschreiben 51.

375
00:17:33,375 --> 00:17:36,260
So, jetzt bin ich immer noch der Platz,
so dass das gleiche Problem wie zuvor.

376
00:17:36,260 --> 00:17:39,140
Aber Sie sehen, wie jetzt
in Ihrem Code, werden Sie wahrscheinlich

377
00:17:39,140 --> 00:17:41,910
noch ein wenig mehr zu schreiben
Komplexität, um dies zuzulassen.

378
00:17:41,910 --> 00:17:44,510
Und in der Tat, was für Betreiber
in C wahrscheinlich lässt

379
00:17:44,510 --> 00:17:48,110
Sie magisch tun dies die Rund?

380
00:17:48,110 --> 00:17:50,160
Ja der Modulo-Operator,
das Prozentzeichen.

381
00:17:50,160 --> 00:17:53,160
Also, was ist irgendwie cool zu einer Warteschlange,
obwohl wir zeichnen Arrays zu halten

382
00:17:53,160 --> 00:17:56,520
da diese wie gerade Linien, wenn Sie
Art darüber nachzudenken, wie geschwungene

383
00:17:56,520 --> 00:18:00,341
rund wie ein Kreis, dann nur
intuitiv es irgendwie funktioniert mental

384
00:18:00,341 --> 00:18:01,590
Ich denke, ein wenig sauberer.

385
00:18:01,590 --> 00:18:05,190
Sie würden immer noch zu implementieren
dass mentales Modell in Code.

386
00:18:05,190 --> 00:18:07,550
Also nicht so schwer,
letztlich zu implementieren,

387
00:18:07,550 --> 00:18:12,430
aber wir verlieren die size-- vielmehr die
Fähigkeit, Größe ändern, wenn wir dies tun.

388
00:18:12,430 --> 00:18:15,310
>> Wir müssen uns des Arrays zu entfernen, die wir
ersetzen Sie es mit einem einzigen Zeiger,

389
00:18:15,310 --> 00:18:20,010
und dann irgendwo in meinem Code ich habe
a nennen, was funktioniert, um tatsächlich zu erstellen

390
00:18:20,010 --> 00:18:23,720
das Array angerufenen Nummern?

391
00:18:23,720 --> 00:18:26,190
Malloc, oder eine ähnliche
Funktion, genau.

392
00:18:26,190 --> 00:18:30,481
Irgendwelche Fragen zu Stapeln oder Warteschlangen.

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

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

395
00:18:33,657 --> 00:18:34,240
Gute Frage.

396
00:18:34,240 --> 00:18:35,830
Was für Modulo würden Sie hier verwenden.

397
00:18:35,830 --> 00:18:38,520
So im Allgemeinen, bei der Verwendung von
mod, können Sie es tun würde

398
00:18:38,520 --> 00:18:40,620
mit der Größe des
gesamte Datenstruktur.

399
00:18:40,620 --> 00:18:44,120
So etwas wie fünf oder Kapazität, wenn
konstant ist, ist wahrscheinlich beteiligt.

400
00:18:44,120 --> 00:18:47,100
Aber nur tun, Modulo fünf
wahrscheinlich nicht ausreichend ist,

401
00:18:47,100 --> 00:18:51,380
weil wir wissen müssen, tun wir
Wrap-around hier oder hier oder hier.

402
00:18:51,380 --> 00:18:54,160
So sind Sie sicher auch
gehen zu beteiligen zu wollen,

403
00:18:54,160 --> 00:18:57,220
die Größe der Sache oder
die vordere variable als auch.

404
00:18:57,220 --> 00:19:00,140
So ist es nur diese relativ
einfachen arithmetischen Ausdruck,

405
00:19:00,140 --> 00:19:02,000
aber Modulo würde der Hauptbestandteil ist.

406
00:19:02,000 --> 00:19:03,330
>> So kurzen Film, wenn man so will.

407
00:19:03,330 --> 00:19:05,780
Eine Animation, die einige
Leute an einer anderen Hochschule

408
00:19:05,780 --> 00:19:08,060
zusammen, dass wir
für diese Diskussion angepasst.

409
00:19:08,060 --> 00:19:12,630
Es geht um das Lernen der Jack
Fakten über Warteschlangen und Statistiken.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Es war einmal,
gab es einen Mann namens Jack.

412
00:19:21,890 --> 00:19:25,330
Wenn es um Freunde kamen,
Jack hatte nicht ein Talent.

413
00:19:25,330 --> 00:19:28,220
Also ging Jack zu sprechen, die
beliebteste Kerl wusste er.

414
00:19:28,220 --> 00:19:30,920
Er ging zu Lou und fragte: Was soll ich tun?

415
00:19:30,920 --> 00:19:33,400
Lou sah, dass sein Freund
war wirklich verzweifelt.

416
00:19:33,400 --> 00:19:36,050
Nun begann er, nur
schauen, wie Sie angezogen sind.

417
00:19:36,050 --> 00:19:38,680
Glauben Sie nicht keine Kleidung haben
mit einem anderen Blick?

418
00:19:38,680 --> 00:19:39,660
Ja, sagte Jack.

419
00:19:39,660 --> 00:19:40,840
Ich mache es auf jeden Fall.

420
00:19:40,840 --> 00:19:43,320
Komm in mein Haus und
Ich werde sie Ihnen zeigen.

421
00:19:43,320 --> 00:19:44,550
So gingen sie aus, um Jacks.

422
00:19:44,550 --> 00:19:47,520
Und Jack zeigte Lou die Box
wo er behielt alle seine Hemden,

423
00:19:47,520 --> 00:19:49,260
und seine Hose, und seine Socken.

424
00:19:49,260 --> 00:19:52,290
Lou sagte: Ich sehe, Sie haben
Ihre Kleidung in einem Haufen.

425
00:19:52,290 --> 00:19:54,870
Warum gehst du nicht einige tragen
andere einmal in eine Weile?

426
00:19:54,870 --> 00:19:58,020
>> Jack sagte: Nun, als ich
Kleidung und Socken zu entfernen,

427
00:19:58,020 --> 00:20:00,780
Ich wasche sie und legte
sie weg in die Box.

428
00:20:00,780 --> 00:20:03,210
Dann kommt die nächste
Morgen, und bis ich hüpfen.

429
00:20:03,210 --> 00:20:06,380
Ich gehe in die Box und erhalten
meine Kleider aus der Spitze.

430
00:20:06,380 --> 00:20:09,070
Lou erkannte schnell,
das Problem mit Jack.

431
00:20:09,070 --> 00:20:12,080
Er hielt Kleidung, CDs,
und Bücher in den Stapel.

432
00:20:12,080 --> 00:20:14,420
Als er zum Erreichen
etwas zu lesen oder zu tragen,

433
00:20:14,420 --> 00:20:17,100
er würde die obere Buch oder Unterwäsche zu wählen.

434
00:20:17,100 --> 00:20:19,500
Dann, als er fertig war, er
würde es gleich wieder setzen.

435
00:20:19,500 --> 00:20:21,970
Zurück es gehen würde, oben auf dem Stapel.

436
00:20:21,970 --> 00:20:24,460
Ich weiß, dass die Lösung,
sagte eine triumphale Laute.

437
00:20:24,460 --> 00:20:27,090
Sie brauchen, um zu lernen,
starten Sie mit einer Warteschlange.

438
00:20:27,090 --> 00:20:29,870
Lou nahm Jacks Kleidung und
hängte sie in den Schrank.

439
00:20:29,870 --> 00:20:32,710
Und wenn er geleert hatte
die Box, er hat nur warf sie.

440
00:20:32,710 --> 00:20:36,500
>> Dann sagte er, jetzt Jack, am Ende des
der Tag, setzen Sie Ihre Kleidung auf der linken Seite

441
00:20:36,500 --> 00:20:37,990
wenn man sie entfernt.

442
00:20:37,990 --> 00:20:41,300
Dann morgen früh, wenn Sie
finden Sie in der Sonne, erhalten Sie Ihre Kleidung

443
00:20:41,300 --> 00:20:43,440
auf der rechten Seite, aus dem Ende der Leitung.

444
00:20:43,440 --> 00:20:44,880
Siehst du denn nicht? , sagte Lou.

445
00:20:44,880 --> 00:20:46,370
Es wird so schön sein.

446
00:20:46,370 --> 00:20:49,770
Hier finden Sie alles einmal zu tragen
bevor Sie etwas zweimal zu tragen.

447
00:20:49,770 --> 00:20:52,670
Und mit allem, was in Warteschlangen
in seinem Schrank und Regal,

448
00:20:52,670 --> 00:20:55,160
Jack begann zu fühlen,
sehr von sich überzeugt.

449
00:20:55,160 --> 00:20:59,720
Alle durch Lou und
seine wunderbare Warteschlange.

450
00:20:59,720 --> 00:21:01,220
Sprecher 1: In Ordnung, es ist entzückend.

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

452
00:21:05,920 --> 00:21:10,080
Also, was hat sich wirklich
auf unter der Haube jetzt?

453
00:21:10,080 --> 00:21:12,370
Dass wir Hinweise,
dass wir malloc,

454
00:21:12,370 --> 00:21:15,680
dass wir die Fähigkeit haben, zu erstellen
Stücke von Speicher für uns selbst

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

456
00:21:16,344 --> 00:21:18,510
Das ist also ein Bild, das wir
erblickte nur den anderen Tag.

457
00:21:18,510 --> 00:21:21,180
Wir haben nicht wirklich zu wohnen
darauf aber dieses Bild

458
00:21:21,180 --> 00:21:24,180
hat schon unter
die Haube seit Wochen.

459
00:21:24,180 --> 00:21:27,050
Und so stellt dies nur
ein Rechteck, die wir gezogen haben,

460
00:21:27,050 --> 00:21:28,180
Arbeitsspeicher Ihres Computers.

461
00:21:28,180 --> 00:21:31,850
Und vielleicht Ihren Computer oder CS50
ID, verfügt über ein Gigabyte Arbeitsspeicher oder RAM

462
00:21:31,850 --> 00:21:33,050
oder zwei oder vier Gigabyte.

463
00:21:33,050 --> 00:21:34,450
Es spielt eigentlich keine Rolle.

464
00:21:34,450 --> 00:21:37,240
Ihr Betriebssystem
Windows oder Mac OS oder Linux,

465
00:21:37,240 --> 00:21:41,120
Wesentlichen ermöglicht Ihrem Programm
zu denken, dass sie Zugang hat

466
00:21:41,120 --> 00:21:42,982
auf die Gesamtheit
Arbeitsspeicher Ihres Computers,

467
00:21:42,982 --> 00:21:45,440
auch wenn Sie vielleicht laufen
mehrere Programme auf einmal.

468
00:21:45,440 --> 00:21:46,990
So in der Realität bedeutet das nicht wirklich funktionieren.

469
00:21:46,990 --> 00:21:49,448
Aber es ist eine Art einer Illusion
um alle Ihre Programme gegeben.

470
00:21:49,448 --> 00:21:53,110
Also, wenn Sie hatte zwei GB RAM, dies
ist, wie der Computer könnte daran denken.

471
00:21:53,110 --> 00:21:57,110
>> Jetzt zufällig einer von ihnen
Dinge, wobei eine dieser Speichersegmente,

472
00:21:57,110 --> 00:21:58,350
heißt eines Stapels.

473
00:21:58,350 --> 00:22:01,680
Und in der Tat jedes Mal,
bisher in das Schreiben von Code

474
00:22:01,680 --> 00:22:05,900
dass Sie angerufen haben ein
Funktion, zum Beispiel Haupt.

475
00:22:05,900 --> 00:22:08,410
Daran erinnern, dass jedes Mal, wenn ich
Speicher gezogen Computers,

476
00:22:08,410 --> 00:22:10,640
Ich habe immer irgendwie zu ziehen
die Hälfte eines Rechtecks ​​hier

477
00:22:10,640 --> 00:22:12,520
und nicht die Mühe sprechen
über das, was oben.

478
00:22:12,520 --> 00:22:15,980
Denn als Haupt heißt, behaupten I
dass Sie diese Splitter der Erinnerung erhalten

479
00:22:15,980 --> 00:22:16,970
das geht hier unten.

480
00:22:16,970 --> 00:22:20,650
Und wenn Haupt genannt Funktion
wie Swaps, gut Swap goes here.

481
00:22:20,650 --> 00:22:23,720
Und es stellt sich heraus, das ist,
wo sie landen.

482
00:22:23,720 --> 00:22:26,277
Auf einem so genannten Stack
Innere des Arbeitsspeichers Ihres Computers.

483
00:22:26,277 --> 00:22:28,360
Nun am Ende des Tages,
dies ist nur Adressen.

484
00:22:28,360 --> 00:22:30,680
Es ist wie das Byte Null ist,
Byte eine, Byte 2 Milliarden.

485
00:22:30,680 --> 00:22:33,130
Aber wenn man darüber nachdenkt,
wie diese rechteckiges Objekt,

486
00:22:33,130 --> 00:22:35,130
alles, was wir tun jeden
Zeit rufen wir eine Funktion

487
00:22:35,130 --> 00:22:37,180
Schichtung eine neue Scheibe des Speichers.

488
00:22:37,180 --> 00:22:41,700
Wir geben diese Funktion eine Scheibe
von seinen eigenen Speicher, mit zu arbeiten.

489
00:22:41,700 --> 00:22:44,490
>> Und jetzt daran erinnern, dass dies wichtig ist.

490
00:22:44,490 --> 00:22:46,400
Denn wenn wir nicht haben
so etwas wie Swap-

491
00:22:46,400 --> 00:22:51,610
und zwei lokale Variablen wie A und B und
wir die Werte von einem und zwei ändern

492
00:22:51,610 --> 00:22:55,130
um zwei und eins, Rückruf
dass, wenn Swap zurückkehrt,

493
00:22:55,130 --> 00:22:58,330
es ist, als ob dieser Scheibe
der Speicher ist einfach weg.

494
00:22:58,330 --> 00:23:00,080
In Wirklichkeit ist es immer noch
es forensisch.

495
00:23:00,080 --> 00:23:01,940
Und noch etwas ist immer noch wirklich da.

496
00:23:01,940 --> 00:23:05,410
Aber konzeptionell, es ist so
obwohl es komplett verschwunden.

497
00:23:05,410 --> 00:23:10,910
Und so Haupt weiß nicht, irgendwelche der Arbeit
das war in diesem Swap-Funktion durchgeführt,

498
00:23:10,910 --> 00:23:14,890
es sei denn, es ist eigentlich in denen übergeben
Argumente Zeiger oder durch Bezugnahme.

499
00:23:14,890 --> 00:23:17,790
Nun, die grundlegende Lösung
zu diesem Problem mit Swap-

500
00:23:17,790 --> 00:23:19,970
ist vorbei Dinge nach Adresse.

501
00:23:19,970 --> 00:23:23,250
Aber es zeigt sich auch, was ist
nun schon über diesem Teil

502
00:23:23,250 --> 00:23:26,330
des Rechtecks ​​während dieser ganzen Zeit ist
doch gibt es mehr Speicher oben.

503
00:23:26,330 --> 00:23:28,790
Und wenn Sie dynamisch
Speicher zuweisen,

504
00:23:28,790 --> 00:23:32,020
ob es innerhalb der GetString, die
haben wir für Sie tun in der CS50 wurde

505
00:23:32,020 --> 00:23:34,710
Bibliothek, oder wenn Sie Kerle
anrufen malloc und fragen

506
00:23:34,710 --> 00:23:37,950
das Betriebssystem für ein Stück aus
Speicher, ist es nicht von dem Stapel zu kommen.

507
00:23:37,950 --> 00:23:40,960
Es kommt aus einem anderen Ort
im Arbeitsspeicher Ihres Computers

508
00:23:40,960 --> 00:23:42,220
dass heißt die Heap.

509
00:23:42,220 --> 00:23:43,430
Und das ist nicht anders.

510
00:23:43,430 --> 00:23:44,285
Es ist das gleiche RAM.

511
00:23:44,285 --> 00:23:45,160
Es ist das gleiche Speicher.

512
00:23:45,160 --> 00:23:49,080
Es ist nur der RAM, die ist
es anstelle von hier unten.

513
00:23:49,080 --> 00:23:50,750
>> Und was bedeutet das?

514
00:23:50,750 --> 00:23:53,650
Nun, wenn Ihr Computer über
eine endliche Menge an Arbeitsspeicher

515
00:23:53,650 --> 00:23:57,450
und der Stapel wächst, so
zu sprechen, und der Haufen nach

516
00:23:57,450 --> 00:23:59,349
dieser Pfeil, wächst nach unten.

517
00:23:59,349 --> 00:24:01,140
Mit anderen Worten, jedes
Zeit anruft malloc,

518
00:24:01,140 --> 00:24:03,430
melden wir Sie ein Stück gegeben
Arbeitsspeicher von oben,

519
00:24:03,430 --> 00:24:06,630
dann vielleicht ein wenig niedriger, dann ein wenig
niedriger, jedes Mal wenn Sie malloc nennen,

520
00:24:06,630 --> 00:24:10,100
der Haufen ist es Nutzung,
ist Art von wachsenden,

521
00:24:10,100 --> 00:24:11,950
wachsen näher und näher an was?

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

523
00:24:13,382 --> 00:24:14,840
So scheint dies wie eine gute Idee?

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

525
00:24:18,420 --> 00:24:22,140
Ich meine, wo es ist nicht wirklich klar,
was Sie sonst noch, wenn nur Sie tun können

526
00:24:22,140 --> 00:24:23,910
haben eine begrenzte Menge an Speicher.

527
00:24:23,910 --> 00:24:25,200
Aber das ist sicherlich schlecht.

528
00:24:25,200 --> 00:24:27,920
Diese beiden Pfeile sind auf einer
Crashkurs für einander.

529
00:24:27,920 --> 00:24:31,930
>> Und es stellt sich heraus, dass die schlechte Kerl, Leute,
sind besonders gut mit der Programmierung,

530
00:24:31,930 --> 00:24:36,140
und zu versuchen, in Computer zu hacken,
kann diese Realität zu nutzen.

531
00:24:36,140 --> 00:24:38,290
In der Tat, betrachten
ein kleiner Ausschnitt.

532
00:24:38,290 --> 00:24:41,350
Das ist also ein Beispiel können Sie lesen,
etwa im Detail auf Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Registrieren Sie an der Stelle,
Artikel, wenn neugierig.

534
00:24:43,100 --> 00:24:45,650
Aber es gibt ein Angriff in der Regel
wie Pufferüberlauf bekannt, dass

535
00:24:45,650 --> 00:24:49,570
hat, solange Menschen bestanden
haben die Fähigkeit zur Manipulation hatten

536
00:24:49,570 --> 00:24:53,120
Speicher Computers, insbesondere in C.
Das ist also ein sehr willkürlich Programm,

537
00:24:53,120 --> 00:24:55,130
aber lassen Sie las es von unten nach oben.

538
00:24:55,130 --> 00:24:57,650
Haupt in argC char Sterne argv.

539
00:24:57,650 --> 00:24:59,830
So ist es ein Programm, das dauert
Befehlszeilenargumente.

540
00:24:59,830 --> 00:25:03,620
Und alle Haupt hat offenbar Anruf
eine Funktion, nennen es F der Einfachheit halber.

541
00:25:03,620 --> 00:25:04,610
Und es geht in was?

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

543
00:25:05,490 --> 00:25:09,320
So ist es in F verläuft unabhängig
das Wort ist, dass der Benutzer eingetippt

544
00:25:09,320 --> 00:25:11,500
an der Eingabeaufforderung, nachdem die
Programmnamen überhaupt.

545
00:25:11,500 --> 00:25:15,730
So viel wie Cäsar oder Vigenere, die
Sie erinnern sich vielleicht tun mit argv.

546
00:25:15,730 --> 00:25:16,680
>> Also, was ist F?

547
00:25:16,680 --> 00:25:19,760
F erfolgt in einem String
als einziges Argument,

548
00:25:19,760 --> 00:25:22,100
Alias ​​ein char Sterne, gleiche
Sache, als String zurück.

549
00:25:22,100 --> 00:25:24,920
Und es ist willkürlich genannt
bar in diesem Beispiel.

550
00:25:24,920 --> 00:25:27,710
Und dann char c 12,
nur in juristischer Hinsicht,

551
00:25:27,710 --> 00:25:31,750
was ist char c Konsole 12 für uns tun?

552
00:25:31,750 --> 00:25:33,440
Was ist es?

553
00:25:33,440 --> 00:25:36,490
Zuweisen von Speicher, und zwar
12 Bytes für 12 Zeichen.

554
00:25:36,490 --> 00:25:36,990
Genau.

555
00:25:36,990 --> 00:25:40,000
Und dann die letzte Zeile, umrühren und
Kopie, haben Sie wahrscheinlich nicht gesehen.

556
00:25:40,000 --> 00:25:43,360
Dies ist ein String Kopie
Funktion, deren Zweck im Leben

557
00:25:43,360 --> 00:25:48,160
ist vor dem zweiten Argument kopieren
in seine erste Argument,

558
00:25:48,160 --> 00:25:51,190
aber nur bis zu einem
bestimmte Anzahl von Bytes.

559
00:25:51,190 --> 00:25:53,860
Also das dritte Argument, sagt,
wie viele Bytes sollten Sie kopieren?

560
00:25:53,860 --> 00:25:56,720
Die Länge der Bar,
was auch immer der Benutzer eingetippt.

561
00:25:56,720 --> 00:25:59,320
Und der Inhalt der
Bar, diesen String sind

562
00:25:59,320 --> 00:26:02,330
in den Speicher kopiert zeigte auf bei C.

563
00:26:02,330 --> 00:26:04,060
>> So scheint Art von dumm, und es ist.

564
00:26:04,060 --> 00:26:06,300
Es ist ein konstruiertes Beispiel,
aber es Vertreters

565
00:26:06,300 --> 00:26:10,100
einer Klasse von Angriffsvektoren,
ein Weg, der Angriff auf ein Programm.

566
00:26:10,100 --> 00:26:15,050
Alles ist schön und gut, wenn der Benutzer
Typen in einem Wort, das 11 Zeichen ist

567
00:26:15,050 --> 00:26:18,040
oder weniger, plus der Rückstrich Null.

568
00:26:18,040 --> 00:26:22,830
Was ist, wenn der Benutzer in mehr als
11 oder 12 oder 20 oder 50 Zeichen?

569
00:26:22,830 --> 00:26:25,090
Was ist das Programm vor?

570
00:26:25,090 --> 00:26:29,360
Potenziell seg Fehler. Es geht
blindlings alles in bar up kopieren

571
00:26:29,360 --> 00:26:31,750
zu seiner Länge, das ist
buchstäblich alles in bar,

572
00:26:31,750 --> 00:26:36,307
in die Adress zeigte auf C. Aber C
nur präventiv als 12 Byte angegeben.

573
00:26:36,307 --> 00:26:37,640
Aber es gibt keine zusätzliche Überprüfung.

574
00:26:37,640 --> 00:26:38,700
Es gibt keinen, wenn die Bedingungen.

575
00:26:38,700 --> 00:26:40,580
Es gibt keine Fehlerüberprüfung hier.

576
00:26:40,580 --> 00:26:43,270
>> Und was ist dieses Programm
zu tun ist einfach blind

577
00:26:43,270 --> 00:26:45,750
Kopieren einer Sache zur anderen.

578
00:26:45,750 --> 00:26:47,880
Und so, wenn wir ziehen diese
als Bild, hier ist

579
00:26:47,880 --> 00:26:49,860
nur ein Splitter des Speicherplatzes.

580
00:26:49,860 --> 00:26:53,470
So bemerken an der Unterseite, die wir
haben die lokalen Variablen bar.

581
00:26:53,470 --> 00:26:57,330
So dass Zeiger, die gehen, um store--
vielmehr, dass lokale Argument, das ist

582
00:26:57,330 --> 00:26:58,672
gehen, um die Zeichenfolge bar zu speichern.

583
00:26:58,672 --> 00:27:00,380
Und dann einfach feststellen,
darüber in einem Stapel,

584
00:27:00,380 --> 00:27:02,505
denn jedes Mal, wenn Sie fragen,
für Speicher auf dem Stapel,

585
00:27:02,505 --> 00:27:04,310
es geht ein wenig
darüber bildhaft,

586
00:27:04,310 --> 00:27:06,270
Beachten Sie, dass wir 12 Bytes dort ankamen.

587
00:27:06,270 --> 00:27:10,690
Die obere linke ist C Halterung Null und
die untere rechte ist C Halterung 11.

588
00:27:10,690 --> 00:27:12,870
Das ist nur, wie die Computer
werde es auslegen.

589
00:27:12,870 --> 00:27:18,300
Also einfach intuitiv, wenn bar mehr
als 12 Zeichen insgesamt, einschließlich

590
00:27:18,300 --> 00:27:25,790
der Backslash Null, wo ist der
12 oder der C Konsole 12 hingehen?

591
00:27:25,790 --> 00:27:28,440
Oder besser gesagt, wo ist der 12.
Zeichen oder der 13. Charakter,

592
00:27:28,440 --> 00:27:30,900
der hundertste Charakter gehen
auf dem Bild am Ende?

593
00:27:30,900 --> 00:27:33,400
Über oder unter?

594
00:27:33,400 --> 00:27:36,300
>> Richtig, denn obwohl
der Stapel selbst wächst nach oben,

595
00:27:36,300 --> 00:27:39,590
wenn Sie Sachen in gesteckt haben
es, ist es aus konstruktiven Gründen,

596
00:27:39,590 --> 00:27:41,294
setzt den Speicher von oben nach unten.

597
00:27:41,294 --> 00:27:44,460
Also, wenn Sie mehr als 12 Byte haben,
Sie gehen zu beginnen, bar zu überschreiben.

598
00:27:44,460 --> 00:27:47,280
Nun, das ist ein Problem, aber es ist
nicht wirklich eine große Sache.

599
00:27:47,280 --> 00:27:51,130
Aber es ist eine große Sache, weil es
mehr Sachen passiert im Speicher.

600
00:27:51,130 --> 00:27:53,074
Also hier ist, wie wir
legte hallo, klar zu sein.

601
00:27:53,074 --> 00:27:54,490
Wenn ich tippte hallo an der Eingabeaufforderung.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O umgekehrten Schrägstrich Null, endet in
diese 12 Bytes, und wir sind super sicher.

603
00:27:59,330 --> 00:28:00,330
Alles ist gut.

604
00:28:00,330 --> 00:28:03,020
Aber wenn ich etwas
mehr potentiell es

605
00:28:03,020 --> 00:28:05,860
werde in bar Raum kriechen.

606
00:28:05,860 --> 00:28:08,405
Aber schlimmer noch, es stellt sich
out all dieser Zeit,

607
00:28:08,405 --> 00:28:11,530
obwohl wir nie darüber gesprochen
es wird der Stapel für die anderen Sachen verwendet wird.

608
00:28:11,530 --> 00:28:13,560
Es ist nicht nur lokale Variablen.

609
00:28:13,560 --> 00:28:15,100
>> C ist eine sehr geringe Sprachniveau.

610
00:28:15,100 --> 00:28:17,810
Und es Art von heimlich
verwendet den Stack auch

611
00:28:17,810 --> 00:28:21,260
sich daran zu erinnern, wenn ein
Funktion aufgerufen wird, welche

612
00:28:21,260 --> 00:28:26,040
die Adresse des vorherigen Funktion,
so dass es zurück zu dieser Funktion springen.

613
00:28:26,040 --> 00:28:29,980
Als Haupt Anrufen zu wechseln, unter
die Dinge, die auf dem Stapel abgelegt

614
00:28:29,980 --> 00:28:34,380
sind nicht nur vertauscht lokalen Variablen,
oder ihre Argumente, auch heimlich geschoben

615
00:28:34,380 --> 00:28:37,510
auf dem Stapel als vertreten
durch die rot scheibe hier,

616
00:28:37,510 --> 00:28:40,520
ist die Adresse des Hauptkörper
im Arbeitsspeicher Ihres Computers,

617
00:28:40,520 --> 00:28:44,180
so dass beim Austausch wird durchgeführt, wobei das Computer
weiß, ich muss zurück zur Haupt gehen

618
00:28:44,180 --> 00:28:46,760
und schliessen Sie die Hauptfunktion ausführt.

619
00:28:46,760 --> 00:28:51,960
Also das ist jetzt gefährlich, denn wenn
der Benutzer in gut mehr als hallo,

620
00:28:51,960 --> 00:28:57,030
derart, dass die Eingabe des Benutzers clobbers
oder überschreibt, dass roten Bereich,

621
00:28:57,030 --> 00:28:59,820
logisch, wenn der Computer
gerade dabei, blind übernehmen

622
00:28:59,820 --> 00:29:03,830
dass die Bytes in dieser rot scheibe sind
die Adresse, auf die sie zurückkehren sollen,

623
00:29:03,830 --> 00:29:09,020
was ist, wenn der Gegner ist intelligent genug, oder
Glück, eine Folge von Bytes gesetzt

624
00:29:09,020 --> 00:29:13,450
gibt, die wie eine Adresse aussieht,
aber es ist die Adresse des Codes

625
00:29:13,450 --> 00:29:18,730
dass er oder sie den Computer will
anstelle von Haupt ausführen?

626
00:29:18,730 --> 00:29:21,670
>> Mit anderen Worten, wenn, was die
Benutzer an der Eingabeaufforderung eingeben,

627
00:29:21,670 --> 00:29:23,850
ist nicht nur etwas
harmlos wie hallo,

628
00:29:23,850 --> 00:29:28,210
aber es ist eigentlich Code, der äquivalent ist
Um alle Dateien des Nutzers löschen?

629
00:29:28,210 --> 00:29:30,060
Oder mailen Sie ihr Passwort zu mir?

630
00:29:30,060 --> 00:29:31,940
Oder starten Sie die Protokollierung ihrer
Tastatureingaben, oder?

631
00:29:31,940 --> 00:29:34,920
Es gibt einen Weg, lasst uns vor, heute,
dass sie nicht nur geben könnte hallo

632
00:29:34,920 --> 00:29:36,711
Welt oder ihren Namen,
sie konnten im wesentlichen

633
00:29:36,711 --> 00:29:39,570
Pass in Code, Nullen und
Lieben, dass der Computer

634
00:29:39,570 --> 00:29:43,450
Fehler sowohl für Code und einer Adresse.

635
00:29:43,450 --> 00:29:48,950
So wenngleich etwas abstrakt, wenn der
Benutzertypen in genug kontradiktorischen Code

636
00:29:48,950 --> 00:29:52,330
dass wir hier verallgemeinern
A. Ein Angriff ist oder Gegner.

637
00:29:52,330 --> 00:29:53,140
Also nur schlechte Sachen.

638
00:29:53,140 --> 00:29:55,306
Wir wissen nicht über die Pflege
Zahlen oder die Nullen oder Einsen

639
00:29:55,306 --> 00:29:59,470
heute, so dass Sie am Ende
überschreibt diese roten Bereich,

640
00:29:59,470 --> 00:30:01,580
feststellen, dass die Folge von Bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C null acht Null.

642
00:30:05,020 --> 00:30:08,960
Und jetzt als Wikipedia-Artikel hier
hat vorgeschlagen, wenn Sie jetzt tatsächlich beginnen

643
00:30:08,960 --> 00:30:12,460
Markierung der Bytes in Ihren Computer
Gedächtnis, was der Wikipedia-Artikel ist

644
00:30:12,460 --> 00:30:19,060
vorschlagen, ist, dass, was ist, wenn die Adresse
dieser oberen linken Byte ist 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> In anderen Worten, wenn der Bösewicht ist
intelligent genug, mit seinen oder ihren Code

646
00:30:22,200 --> 00:30:26,650
um tatsächlich legte eine Reihe hier, dass
entspricht der Adresse des Code

647
00:30:26,650 --> 00:30:29,180
er oder sie injiziert
in den Computer, die Sie

648
00:30:29,180 --> 00:30:31,050
können Sie den Computer Trick
in etwas zu tun.

649
00:30:31,050 --> 00:30:34,140
Entfernen von Dateien, E-Mails
Dinge, schnüffeln Ihren Traffic,

650
00:30:34,140 --> 00:30:36,710
buchstäblich alles sein könnte
in den Computer eingespritzt.

651
00:30:36,710 --> 00:30:39,220
Und so ein Pufferüberlauf
Angriff in seinem Kern

652
00:30:39,220 --> 00:30:43,530
ist nur ein dumm, dumm
wiegendes eines Arrays,

653
00:30:43,530 --> 00:30:45,840
nicht über seine Grenzen überprüft.

654
00:30:45,840 --> 00:30:48,850
Und das ist, was ist super gefährlich
und gleichzeitig super leistungsfähiges

655
00:30:48,850 --> 00:30:52,560
in C ist, dass wir haben in der Tat
Zugang zu jedem Ort in der Erinnerung.

656
00:30:52,560 --> 00:30:55,320
Es liegt an uns, die Programmierer,
die das Original-Code schreiben

657
00:30:55,320 --> 00:30:59,330
um die verflixte Länge jeder überprüfen
Arrays, die wir manipulieren.

658
00:30:59,330 --> 00:31:00,750
So klar zu sein, was ist die Lösung?

659
00:31:00,750 --> 00:31:03,190
Wenn wir zurückrollen, um diese
Code, sollte ich nicht einfach

660
00:31:03,190 --> 00:31:08,000
ändern Sie die Länge der Stange, was
sollte ich sonst werden überprüft?

661
00:31:08,000 --> 00:31:10,620
Was muss ich tun, um
diesen Angriff zu verhindern vollständig?

662
00:31:10,620 --> 00:31:14,110
Ich will nicht einfach blind sagen
dass Sie so viele Bytes kopieren

663
00:31:14,110 --> 00:31:16,140
so ist die Länge der Stange.

664
00:31:16,140 --> 00:31:18,910
Ich möchte sagen, zu kopieren, wie
viele Bytes, wie es in bar

665
00:31:18,910 --> 00:31:24,090
bis der zugewiesene
Speicher oder 12 maximal.

666
00:31:24,090 --> 00:31:27,450
Also brauche ich eine Art, wenn die Bedingung
das tut überprüfen Sie die Länge der Stange,

667
00:31:27,450 --> 00:31:32,800
aber wenn es 12, wir haben nur schwer Code überschreitet
12 als der größtmöglichen Abstand.

668
00:31:32,800 --> 00:31:35,910
Ansonsten die sogenannte Puffer
Überlauf-Angriff kann passieren.

669
00:31:35,910 --> 00:31:38,451
An der Unterseite des auf den Folien,
wenn Sie neugierig, mehr zu lesen sind

670
00:31:38,451 --> 00:31:41,200
ist das eigentliche Original-Artikel
wenn Sie möchten, um einen Blick zu nehmen.

671
00:31:41,200 --> 00:31:44,550
>> Aber jetzt, unter den Preisen
Hier bezahlt war Ineffizienzen.

672
00:31:44,550 --> 00:31:46,680
Das war also eine schnelle
niedrigen Niveau Blick auf, was

673
00:31:46,680 --> 00:31:49,709
Probleme können nun ergeben, dass wir
Zugriff auf Speicher Computers.

674
00:31:49,709 --> 00:31:51,750
Aber ein anderes Problem, das wir
bereits am Montag, stolperte

675
00:31:51,750 --> 00:31:53,800
war nur die Ineffizienz
einer verketteten Liste.

676
00:31:53,800 --> 00:31:56,019
Wir sind wieder in linearer Zeit.

677
00:31:56,019 --> 00:31:57,560
Wir müssen nicht mehr einen zusammenhängenden Array.

678
00:31:57,560 --> 00:31:58,980
Wir haben nicht mit wahlfreiem Zugriff.

679
00:31:58,980 --> 00:32:00,710
Wir können nicht mit eckigen Klammern.

680
00:32:00,710 --> 00:32:04,590
Wir haben buchstäblich in einer while-Schleife verwenden
wie die, die ich vorhin geschrieben habe.

681
00:32:04,590 --> 00:32:09,740
Aber am Montag, behauptete wir, dass wir
kriechen zurück in das Reich der Effizienz

682
00:32:09,740 --> 00:32:13,040
etwas, das es zu erreichen
logarithmische vielleicht, oder am besten noch,

683
00:32:13,040 --> 00:32:16,120
vielleicht sogar etwas, das ist
sogenannte konstante Zeit.

684
00:32:16,120 --> 00:32:19,840
Also, wie können wir das tun, indem Sie diese neue
Werkzeuge, diese Adressen, diese Zeiger,

685
00:32:19,840 --> 00:32:22,210
und Gewinde Dinge unserer eigenen?

686
00:32:22,210 --> 00:32:23,960
Nun, nehme an, dass
Hier handelt es sich um ein Bündel

687
00:32:23,960 --> 00:32:27,170
von Zahlen, die wir in einem Geschäft wollen
Datenstruktur und Such effizient.

688
00:32:27,170 --> 00:32:30,960
Wir können absolut zu Woche zurückspulen
zwei, werfen diese in einem Array,

689
00:32:30,960 --> 00:32:33,150
und suchen Sie sie mit binäre Suche.

690
00:32:33,150 --> 00:32:34,040
Teile und herrsche.

691
00:32:34,040 --> 00:32:37,720
Und in der Tat Sie geschrieben
binäre Suche in PSET3,

692
00:32:37,720 --> 00:32:40,100
wo Sie die Fund-Programm implementiert.

693
00:32:40,100 --> 00:32:40,890
Aber wissen Sie was.

694
00:32:40,890 --> 00:32:45,060
Es ist eine Art mehr
cleverer Weg, dies zu tun.

695
00:32:45,060 --> 00:32:47,390
Es ist ein wenig mehr
anspruchsvoll und es vielleicht

696
00:32:47,390 --> 00:32:50,830
ermöglicht es uns, zu sehen, warum binären
Suche so viel schneller ist.

697
00:32:50,830 --> 00:32:52,980
Lassen Sie uns zunächst vorstellen
der Begriff eines Baumes.

698
00:32:52,980 --> 00:32:54,730
Welche, obwohl in
Realität Bäumen Art

699
00:32:54,730 --> 00:32:57,730
wachsen wie dieser, in der Welt der Computer-
Wissenschaft sie Art von unten wachsen

700
00:32:57,730 --> 00:33:00,830
wie ein Stammbaum, wo Sie
Ihre Großeltern oder Urgroßeltern

701
00:33:00,830 --> 00:33:04,580
oder was auch an der Spitze, dem Patriarchen und
die Matriarchin der Familie, nur ein

702
00:33:04,580 --> 00:33:07,930
so genannte Wurzel, Knoten, unten
die ihre Kinder sind,

703
00:33:07,930 --> 00:33:11,442
unterhalb dessen sind ihre Kinder oder
ihre Nachkommen im Allgemeinen.

704
00:33:11,442 --> 00:33:13,400
Und wer hängen aus
der Boden der Familie

705
00:33:13,400 --> 00:33:16,070
Baum, abgesehen davon, das
Jüngste in der Familie,

706
00:33:16,070 --> 00:33:19,520
können auch einfach generisch sein
rief die Blätter des Baumes.

707
00:33:19,520 --> 00:33:21,800
>> Also das ist nur ein Haufen
von Wörtern und Definitionen

708
00:33:21,800 --> 00:33:25,790
für so etwas wie einen Baum im Computer
Wissenschaft, ähnlich wie ein Stammbaum.

709
00:33:25,790 --> 00:33:28,770
Aber es gibt noch schicker Inkarnationen
von Bäumen, von denen eine

710
00:33:28,770 --> 00:33:30,780
heißt ein binärer Suchbaum.

711
00:33:30,780 --> 00:33:34,380
Und Sie können Art von tease
auseinander, was dieses Ding funktioniert.

712
00:33:34,380 --> 00:33:37,180
Nun, es ist binär in welchem ​​Sinne?

713
00:33:37,180 --> 00:33:41,455
Woher kommt das binäre aus hierher gekommen?

714
00:33:41,455 --> 00:33:41,955
Es tut uns leid?

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

716
00:33:45,961 --> 00:33:47,210
Es ist nicht so sehr ein entweder oder.

717
00:33:47,210 --> 00:33:52,000
Es ist mehr, dass jeder der Knoten hat keine
mehr als zwei Kinder, wie wir hier sehen.

718
00:33:52,000 --> 00:33:54,990
Im Allgemeinen ist eine tree-- und
Ihre Eltern und Großeltern

719
00:33:54,990 --> 00:33:57,640
können so viele Kinder zu haben oder
grandkids, als sie eigentlich wollen,

720
00:33:57,640 --> 00:34:00,820
und so zum Beispiel gibt uns drei haben
Kinder ab diesem rechten Knoten,

721
00:34:00,820 --> 00:34:05,480
aber in einer Binärbaum besitzt eine Knoten
null, eine oder zwei Kinder maximal.

722
00:34:05,480 --> 00:34:08,496
Und das ist ein schönes Anwesen,
denn wenn es von beiden mit einer bedeckt,

723
00:34:08,496 --> 00:34:10,620
werden wir in der Lage zu sein,
noch ein wenig Protokollbasis zwei

724
00:34:10,620 --> 00:34:11,975
Aktion geht hier schließlich.

725
00:34:11,975 --> 00:34:13,350
Also müssen wir etwas logarithmisch.

726
00:34:13,350 --> 00:34:14,558
Aber mehr dazu in einem Moment.

727
00:34:14,558 --> 00:34:19,810
Suchbaum bedeutet, dass die Zahlen
angeordnet, dass die linken Kindes

728
00:34:19,810 --> 00:34:22,429
Wert größer als die Wurzel.

729
00:34:22,429 --> 00:34:26,010
Und seine rechte Kind
größer als die Wurzel.

730
00:34:26,010 --> 00:34:29,290
Mit anderen Worten, wenn Sie eines der nehmen
Knoten, die Kreise in diesem Bild,

731
00:34:29,290 --> 00:34:31,840
und schaut auf seiner linken
Kind und seine rechte Kind,

732
00:34:31,840 --> 00:34:34,739
die erste sollte kleiner sein,
der zweite sollte größer sein.

733
00:34:34,739 --> 00:34:36,159
So Plausibilitätsprüfung 55.

734
00:34:36,159 --> 00:34:37,780
Es verließ Kind ist 33.

735
00:34:37,780 --> 00:34:38,620
Es ist weniger als.

736
00:34:38,620 --> 00:34:40,929
55, sein Recht Kind ist 77.

737
00:34:40,929 --> 00:34:41,783
Es ist größer als.

738
00:34:41,783 --> 00:34:43,199
Und das ist eine rekursive Definition.

739
00:34:43,199 --> 00:34:46,480
Wir konnten jeden einer von denen zu prüfen
Knoten und das gleiche Muster halten würde.

740
00:34:46,480 --> 00:34:49,389
>> Also, was ist schön, in ein
binären Suchbaum ist

741
00:34:49,389 --> 00:34:52,204
dass man, können wir es umsetzen
mit einer Struktur, wie diese.

742
00:34:52,204 --> 00:34:54,620
Und auch wenn wir werfen
viele Strukturen in Ihrem,

743
00:34:54,620 --> 00:34:56,560
sie sind etwas
intuitive nun hoffentlich.

744
00:34:56,560 --> 00:35:00,570
Die Syntax ist immer noch geheimnisvollen sicher,
aber der Inhalt eines Knotens in dieser

745
00:35:00,570 --> 00:35:02,786
context-- und wir halten
Verwendung der Wortknoten,

746
00:35:02,786 --> 00:35:04,910
ob es sich um ein Rechteck
auf dem Bildschirm oder einem Kreis,

747
00:35:04,910 --> 00:35:08,970
es ist nur einige generischen Container,
in diesem Fall aus einem Baum, wie einer

748
00:35:08,970 --> 00:35:11,780
wir sahen, wir brauchen eine ganze Zahl
in jedem der Knoten

749
00:35:11,780 --> 00:35:15,460
und dann muss ich zwei Zeiger Zeige
auf der linken und der rechten Kind Kind,

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

751
00:35:16,590 --> 00:35:20,730
Also das ist, wie wir
umzusetzen, dass in einer Struktur.

752
00:35:20,730 --> 00:35:22,315
Und wie könnte ich zu implementieren es im Code?

753
00:35:22,315 --> 00:35:26,730
Nun, lassen Sie uns einen kurzen
Blick auf dieses kleine Beispiel.

754
00:35:26,730 --> 00:35:29,820
Es ist nicht funktionsfähig, aber ich habe
kopiert und eingefügt werden, dass die Struktur.

755
00:35:29,820 --> 00:35:33,510
Und wenn meine Funktion für ein binäres
Suchbaum Such genannt,

756
00:35:33,510 --> 00:35:36,980
und dies nimmt zwei Argumente,
eine ganze Zahl N und einen Zeiger

757
00:35:36,980 --> 00:35:41,400
zu einem Knoten, so dass ein Zeiger auf dem Baum
oder einen Zeiger zu der Wurzel eines Baums,

758
00:35:41,400 --> 00:35:43,482
Wie kann ich über die Suche nach N hin?

759
00:35:43,482 --> 00:35:45,440
Nun, zunächst einmal, weil ich
Umgang mit Zeigern,

760
00:35:45,440 --> 00:35:46,750
Ich werde eine Plausibilitätsprüfung zu tun.

761
00:35:46,750 --> 00:35:54,279
Wenn tree ist gleich ist gleich null, ist N
In diesem Stammbaum oder nicht in diesem Stammbaum?

762
00:35:54,279 --> 00:35:55,070
Es kann nicht sein, oder?

763
00:35:55,070 --> 00:35:56,870
Wenn ich mich Vergangenheit null,
dort nichts zu finden.

764
00:35:56,870 --> 00:35:59,230
Ich könnte auch einfach
blind sagen return false.

765
00:35:59,230 --> 00:36:04,050
Wenn Sie mir nichts zu geben, ich kann sicher nicht
finden eine beliebige Anzahl N. Was anderes könnte ich

766
00:36:04,050 --> 00:36:04,750
Jetzt prüfen?

767
00:36:04,750 --> 00:36:12,830
Ich werde auch sonst, wenn N sagen
weniger als was auch immer an der Baumknoten

768
00:36:12,830 --> 00:36:16,300
dass ich N-Wert übergeben worden.

769
00:36:16,300 --> 00:36:20,270
Mit anderen Worten, wenn die Anzahl ich
sucht, N, kleiner ist als der Knoten

770
00:36:20,270 --> 00:36:21,340
dass ich freue mich auf.

771
00:36:21,340 --> 00:36:23,190
Und der Knoten Ich suche
bei nennt Baum,

772
00:36:23,190 --> 00:36:26,370
und daran erinnern, aus dem vorherigen Beispiel
zu dem Wert in einem Zeiger zu erhalten,

773
00:36:26,370 --> 00:36:28,310
Ich benutze die Pfeilnotation.

774
00:36:28,310 --> 00:36:35,960
Also, wenn N kleiner als Baum Pfeil
N, ich will konzeptionell links zu gehen.

775
00:36:35,960 --> 00:36:38,590
Wie kann ich express Benutzer überlassen?

776
00:36:38,590 --> 00:36:41,560
Um es klar, ob dies
das Bild in Frage,

777
00:36:41,560 --> 00:36:44,612
und ich habe bestanden, dass oberste
arrow das ist nach unten zeigt.

778
00:36:44,612 --> 00:36:45,570
Das ist mein Baum-Zeiger.

779
00:36:45,570 --> 00:36:48,060
Ich zeigte auf die Wurzel des Baumes.

780
00:36:48,060 --> 00:36:52,100
Und ich freue mich sagen wir, für
die Zahl 44, willkürlich.

781
00:36:52,100 --> 00:36:55,300
44 kleiner oder
mehr als 55 offensichtlich?

782
00:36:55,300 --> 00:36:56,360
So ist es weniger als.

783
00:36:56,360 --> 00:36:58,760
Und so, wenn die Bedingung zutrifft.

784
00:36:58,760 --> 00:37:03,981
So konzeptionell, was will ich, um
Suche starten, wenn ich mich für 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Genau, ich will
suchen Sie die linke Kind,

788
00:37:11,100 --> 00:37:12,789
oder der linke Unterbaum des Bildes.

789
00:37:12,789 --> 00:37:14,830
Und in der Tat, lassen Sie mich durch
Das Bild hier unten

790
00:37:14,830 --> 00:37:17,770
nur für einen Augenblick, da
Ich kann nicht kratzen this out.

791
00:37:17,770 --> 00:37:21,150
Wenn ich hier beginnen bei 55, und
Ich weiß, dass der Wert 44

792
00:37:21,150 --> 00:37:23,180
Ich suche ist es,
der linke, es ist eine Art

793
00:37:23,180 --> 00:37:26,010
der wie Reißen Sie das Telefonbuch in
die Hälfte oder Reißen Sie den Baum in der Mitte.

794
00:37:26,010 --> 00:37:29,660
Ich habe nicht mehr zu kümmern
diese ganze Hälfte des Baumes.

795
00:37:29,660 --> 00:37:33,270
Und doch neugierig im Hinblick auf die
Struktur, dieses Ding hier, dass

796
00:37:33,270 --> 00:37:36,682
beginnt bei 33, dass sich
ist ein binärer Suchbaum.

797
00:37:36,682 --> 00:37:39,890
Ich sagte, das Wort rekursive vor, weil
tatsächlich ist eine Datenstruktur,

798
00:37:39,890 --> 00:37:41,707
per Definition ist rekursiv.

799
00:37:41,707 --> 00:37:44,540
Vielleicht haben Sie einen Baum, der dies ist haben
groß, aber jeder von seinen Kindern

800
00:37:44,540 --> 00:37:46,870
stellt einen Baum nur ein wenig kleiner.

801
00:37:46,870 --> 00:37:50,910
Statt wobei Opa
oder Großmutter, jetzt ist es nur mom

802
00:37:50,910 --> 00:37:54,300
oder-- Ich kann nicht sagen-- nicht mom
oder Papa, das wäre seltsam.

803
00:37:54,300 --> 00:37:59,000
Statt die beiden Kinder gibt
würde wie Bruder und Geschwister zu sein.

804
00:37:59,000 --> 00:38:01,120
Eine neue Generation von der Familie Baum.

805
00:38:01,120 --> 00:38:02,900
Aber strukturell, es ist die gleiche Idee.

806
00:38:02,900 --> 00:38:06,790
Und es stellt sich heraus, Ich habe eine Funktion
mit dem ich eine binäre Suche Suche

807
00:38:06,790 --> 00:38:07,290
Baum.

808
00:38:07,290 --> 00:38:08,680
Es wird Suche aufgerufen.

809
00:38:08,680 --> 00:38:17,870
Ich suche für N im Baum Pfeil links
sonst wenn N größer ist als der Wert,

810
00:38:17,870 --> 00:38:18,870
dass ich mich derzeit auf.

811
00:38:18,870 --> 00:38:20,800
55 in der Geschichte vor einem Augenblick.

812
00:38:20,800 --> 00:38:23,780
Ich habe eine Funktion mit dem Namen
Such, ich kann nur

813
00:38:23,780 --> 00:38:29,660
geben N dieses und rekursiv suchen
die Sub-Baum und nur Rück

814
00:38:29,660 --> 00:38:30,620
was auch immer die Antwort.

815
00:38:30,620 --> 00:38:33,530
Else Ich habe einige abschließende Basisfall hier.

816
00:38:33,530 --> 00:38:35,310
>> Was ist der letzte Fall ist?

817
00:38:35,310 --> 00:38:36,570
Baum ist entweder Null.

818
00:38:36,570 --> 00:38:39,980
Der Wert ich entweder suche, ist
geringer als oder größer als derjenige

819
00:38:39,980 --> 00:38:42,610
oder gleich ist.

820
00:38:42,610 --> 00:38:44,750
Und ich konnte gleich sagen,
gleich, aber logisch ist es

821
00:38:44,750 --> 00:38:46,500
entspricht einfach nur sagen andere hier.

822
00:38:46,500 --> 00:38:49,150
So wahr ist, wie ich etwas zu finden.

823
00:38:49,150 --> 00:38:51,710
Hoffentlich ist dies ein
noch mehr überzeugendes Beispiel

824
00:38:51,710 --> 00:38:54,900
als der dumme Sigma-Funktion
wir haben ein paar Vorträge zurück,

825
00:38:54,900 --> 00:38:58,360
wo es war so einfach, um eine Schleife zu verwenden
zu zählen bis alle Zahlen von eins

826
00:38:58,360 --> 00:39:02,390
N. Hier mit einer Datenstruktur
daß selbst rekursiv

827
00:39:02,390 --> 00:39:07,050
definiert ist und rekursiv gezogen, jetzt sind wir
haben die Fähigkeit, uns auszudrücken

828
00:39:07,050 --> 00:39:09,780
im Code, die selbst rekursiv.

829
00:39:09,780 --> 00:39:12,580
Das ist also die exakt gleichen Code hier.

830
00:39:12,580 --> 00:39:14,400
>> Also, was andere Probleme können wir lösen?

831
00:39:14,400 --> 00:39:18,160
So ein schneller Schritt davon entfernt
Bäume für einen Moment.

832
00:39:18,160 --> 00:39:20,130
Hier ist, sagen wir, die deutsche Flagge.

833
00:39:20,130 --> 00:39:22,020
Und es gibt eindeutig ein
Muster dieser Flagge.

834
00:39:22,020 --> 00:39:23,811
Und es gibt viele
Flaggen der Welt,

835
00:39:23,811 --> 00:39:27,560
sind so einfach wie dies in Bezug auf
der Farben und Muster.

836
00:39:27,560 --> 00:39:31,930
Aber nehmen wir an, dass dies als eine gespeicherte
GIF- oder JPEG-oder Bitmap oder ein Ping,

837
00:39:31,930 --> 00:39:34,240
beliebige grafische Dateiformat
, mit denen Sie vertraut sind,

838
00:39:34,240 --> 00:39:36,460
einige davon sind wir
spielt mit in PSET4.

839
00:39:36,460 --> 00:39:41,550
Dies scheint nicht sinnvoll zu speichern
schwarzes Pixel, schwarzes Pixel, schwarzes Pixel,

840
00:39:41,550 --> 00:39:44,790
Punkt, Punkt, Punkt, eine ganze Reihe von
schwarzer Pixel für das erste Abtastlinie

841
00:39:44,790 --> 00:39:47,430
oder Zeile, dann eine ganze Reihe von
gleich sind, dann eine ganze Reihe

842
00:39:47,430 --> 00:39:49,530
derselben, und dann ein
ganze Reihe von roten Pixel,

843
00:39:49,530 --> 00:39:53,020
roten Pixel, roten Pixel, dann eine ganze
Bündel gelbe Pixel, gelb, oder?

844
00:39:53,020 --> 00:39:55,050
>> Es gibt eine solche Ineffizienz hier.

845
00:39:55,050 --> 00:39:59,040
Wie würden Sie intuitiv
komprimieren die deutsche Flagge

846
00:39:59,040 --> 00:40:01,320
wenn die Umsetzung als Datei?

847
00:40:01,320 --> 00:40:04,940
Wie, was Informationen können wir nicht
stört die Speicherung auf der Festplatte, um

848
00:40:04,940 --> 00:40:08,040
zu unserem Dateigröße aus, wie zu verringern
ein Megabyte bis ein Kilobyte, etwas,

849
00:40:08,040 --> 00:40:09,430
kleiner?

850
00:40:09,430 --> 00:40:13,130
Worin liegt die Redundanz
hier klar zu sein?

851
00:40:13,130 --> 00:40:13,880
Was könnten Sie tun?

852
00:40:13,880 --> 00:40:14,380
Ja?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Genau.

855
00:40:21,970 --> 00:40:24,550
Warum nicht statt erinnern
die Farbe eines jeden Pixels darn

856
00:40:24,550 --> 00:40:28,200
genau wie Sie in PSET4 tust
mit der Bitmap-Datei-Format,

857
00:40:28,200 --> 00:40:32,060
warum du nicht einfach darstellen, die
ganz linken Spalte von Pixeln, zum Beispiel

858
00:40:32,060 --> 00:40:35,370
ein Haufen von schwarzen Pixeln, ein Haufen
roter und ein Bündel von Gelb,

859
00:40:35,370 --> 00:40:39,210
und dann einfach irgendwie kodieren die
Idee der Wiederholen Sie diese 100-mal

860
00:40:39,210 --> 00:40:41,020
oder wiederholen Sie diesen 1.000 Mal?

861
00:40:41,020 --> 00:40:43,430
Wo 100 oder 1.000 ist
nur eine ganze Zahl, so dass Sie

862
00:40:43,430 --> 00:40:47,290
kann mit nur einer einzigen Zahl weg
anstelle von hunderten oder tausenden

863
00:40:47,290 --> 00:40:48,270
zusätzlicher Pixel.

864
00:40:48,270 --> 00:40:50,990
Und in der Tat, das ist, wie wir
konnte die deutsche Flagge zu komprimieren.

865
00:40:50,990 --> 00:40:51,490
Und

866
00:40:51,490 --> 00:40:53,470
Was ist nun mit dem Französisch-Flag?

867
00:40:53,470 --> 00:40:58,930
Und ein bisschen eine Art von
geistige Übung, die Flagge

868
00:40:58,930 --> 00:41:01,040
kann mehr auf der Festplatte komprimiert werden?

869
00:41:01,040 --> 00:41:05,720
Die deutsche Flagge oder Französisch
Flagge, wenn wir diesen Ansatz?

870
00:41:05,720 --> 00:41:08,490
Die deutsche Flagge, weil es
Weitere horizontale Redundanz.

871
00:41:08,490 --> 00:41:12,190
Und Design, viele grafische Datei
Formate tatsächlich arbeiten, wie Scan-Linien

872
00:41:12,190 --> 00:41:12,830
horizontal.

873
00:41:12,830 --> 00:41:14,674
Sie konnten arbeiten
vertikal, nur die Menschlichkeit

874
00:41:14,674 --> 00:41:17,090
Vor Jahren beschlossen, dass wir
in der Regel der Dinge Reihe denken

875
00:41:17,090 --> 00:41:18,880
Zeile statt der Spalte für Spalte.

876
00:41:18,880 --> 00:41:20,820
So in der Tat, wenn Sie waren
an der Datei zu suchen

877
00:41:20,820 --> 00:41:24,670
Größe einer Deutschlandflagge und Französisch
Flagge, solange die Auflösung

878
00:41:24,670 --> 00:41:27,530
die gleichen sind, die gleiche Breite
und Höhe, dieser

879
00:41:27,530 --> 00:41:31,580
Hier wird größer sein, weil Sie
muss sich dreimal zu wiederholen.

880
00:41:31,580 --> 00:41:35,570
Sie müssen blau, wiederholen Sie angeben,
sich selbst, weiß, wiederholen Sie sich, rot,

881
00:41:35,570 --> 00:41:36,740
wiederholen sich.

882
00:41:36,740 --> 00:41:39,000
Man kann nicht einfach alle gehen
die Art und Weise nach rechts.

883
00:41:39,000 --> 00:41:41,200
Und nebenbei, um
deaktivieren Sie die Komprimierung

884
00:41:41,200 --> 00:41:43,910
ist überall, wenn es sich um
vier Bilder von einer video-- Sie

885
00:41:43,910 --> 00:41:45,890
vielleicht, dass ein Film erinnern
oder Video ist in der Regel

886
00:41:45,890 --> 00:41:47,286
wie 29 oder 30 Bildern pro Sekunde.

887
00:41:47,286 --> 00:41:50,410
Es ist wie ein kleines Daumenkino, wo Sie
nur Bild, Bild, Bild, Bild sehen

888
00:41:50,410 --> 00:41:54,410
Bild einfach super schnell, so dass es aussieht,
die Schauspieler auf dem Bildschirm bewegen.

889
00:41:54,410 --> 00:41:57,130
Hier ist eine Hummel auf
oben auf einem Blumenstrauß.

890
00:41:57,130 --> 00:41:59,790
Und wenn es vielleicht Art sein
schwer, auf den ersten Blick zu sehen,

891
00:41:59,790 --> 00:42:04,020
das einzige, was sich in
dieser Film ist die Biene.

892
00:42:04,020 --> 00:42:06,880
>> Was ist dumm zu speichern
Video unkomprimiert?

893
00:42:06,880 --> 00:42:11,420
Es ist irgendwie eine Verschwendung, um Video zu speichern
vier nahezu identische Bilder,

894
00:42:11,420 --> 00:42:13,670
unterscheiden sich nur insofern, als wo die Biene ist.

895
00:42:13,670 --> 00:42:16,280
Sie können wegwerfen meisten
dieser Informationen

896
00:42:16,280 --> 00:42:20,190
und nur daran erinnern, zum Beispiel,
der erste Rahmen und der letzte Rahmen,

897
00:42:20,190 --> 00:42:22,180
Keyframes Wenn Sie auch
überhaupt das Wort hören,

898
00:42:22,180 --> 00:42:24,337
und nur in den Laden
Mitte, wo die Biene.

899
00:42:24,337 --> 00:42:26,170
Und Sie müssen nicht zu haben,
speichern alle der rosa,

900
00:42:26,170 --> 00:42:28,330
und die blaue und die
grüne Werte auch.

901
00:42:28,330 --> 00:42:31,200
Das ist also nur sagen, dass
Komprimierung ist überall.

902
00:42:31,200 --> 00:42:34,900
Es ist eine Technik, die wir verwenden oft
oder nehmen Sie für diese Tage gewährt.

903
00:42:34,900 --> 00:42:38,750
>> Aber wie wollen Sie Text komprimieren?

904
00:42:38,750 --> 00:42:40,450
Was denken Sie über Komprimieren Text gehen?

905
00:42:40,450 --> 00:42:45,410
Nun, jedes der Zeichen in
ASCII ist einem Byte oder acht Bits.

906
00:42:45,410 --> 00:42:47,360
Und das ist irgendwie dumm, nicht wahr?

907
00:42:47,360 --> 00:42:51,160
Da Sie wahrscheinlich Typ A
und E und E und A und U eine Menge

908
00:42:51,160 --> 00:42:55,270
mehr als oft wie W oder Q oder Z,
in Abhängigkeit von der Sprache, in der

909
00:42:55,270 --> 00:42:56,610
Sie sicherlich schreibst.

910
00:42:56,610 --> 00:42:59,600
Und warum sind wir mit
acht Bits für jeden Buchstaben,

911
00:42:59,600 --> 00:43:02,040
einschließlich des mindestens
beliebte Briefe, nicht wahr?

912
00:43:02,040 --> 00:43:05,300
Warum nicht mit weniger Bits für
die super beliebt Briefe,

913
00:43:05,300 --> 00:43:07,760
wie E, das, was Sie sich vorstellen
zuerst in Glücksrad,

914
00:43:07,760 --> 00:43:10,450
und verwenden Sie mehr Bits für
die weniger populären Buchstaben?

915
00:43:10,450 --> 00:43:10,950
Warum?

916
00:43:10,950 --> 00:43:13,130
Weil wir gerade dabei,
benutzen sie weniger häufig.

917
00:43:13,130 --> 00:43:15,838
>> Nun stellt sich heraus, dass es haben
wurden Versuche unternommen, um dies zu tun.

918
00:43:15,838 --> 00:43:18,630
Und wenn Sie von Grad erinnern
Schule oder Gymnasium, Morse-Code.

919
00:43:18,630 --> 00:43:20,400
Morse-Code hat dots
und Striche, die sein können,

920
00:43:20,400 --> 00:43:24,270
entlang eines Drahtes übertragen
Töne oder Signale von einer Art.

921
00:43:24,270 --> 00:43:25,930
Aber Morse-Code ist ein super sauber.

922
00:43:25,930 --> 00:43:29,010
Es ist Art von einem binären System in
dass Sie Punkte oder Striche.

923
00:43:29,010 --> 00:43:30,977
Aber wenn Sie, zum Beispiel, zwei Punkte zu sehen.

924
00:43:30,977 --> 00:43:33,810
Oder wenn Sie an den Bediener zurückdenke
die geht so piep, piep, piep,

925
00:43:33,810 --> 00:43:36,760
Signalton, der Kollision mit einem kleinen Trigger
dass ein Signal überträgt,

926
00:43:36,760 --> 00:43:40,360
wenn Sie, der Empfänger erhält zwei
Punkte, welche Botschaft haben Sie erhalten?

927
00:43:40,360 --> 00:43:43,490
Völlig willkürlich.

928
00:43:43,490 --> 00:43:44,450
>> ICH?

929
00:43:44,450 --> 00:43:45,060
ICH?

930
00:43:45,060 --> 00:43:47,500
Oder was about-- oder ich?

931
00:43:47,500 --> 00:43:49,570
Vielleicht war es nur zwei richtige E ist?

932
00:43:49,570 --> 00:43:52,480
Also gibt es dieses Problem
von Decodierbarkeit mit Morse

933
00:43:52,480 --> 00:43:54,890
Code, wobei es sei denn,
Person Senden Sie die Nachricht

934
00:43:54,890 --> 00:43:59,510
eigentlich Pausen, so dass Sie von zu sortieren
sehen oder hören, die Lücken zwischen den Buchstaben,

935
00:43:59,510 --> 00:44:02,990
ist es nicht ausreichend, nur um
schickt einen Strom von Nullen und Einsen,

936
00:44:02,990 --> 00:44:05,610
oder Punkten und Strichen,
denn es gibt Mehrdeutigkeiten.

937
00:44:05,610 --> 00:44:08,640
E ist ein einzelner Punkt, wenn Sie also
sehe zwei Punkte oder hören zwei Punkte,

938
00:44:08,640 --> 00:44:11,254
vielleicht ist es zwei E oder vielleicht ist es eine I.

939
00:44:11,254 --> 00:44:13,670
Also brauchen wir ein System, das eine ist
wenig klüger als das.

940
00:44:13,670 --> 00:44:16,851
So ein Mann namens Huffman Jahre
Vor kam mit genau dies.

941
00:44:16,851 --> 00:44:18,600
So dass wir gerade gehen
um einen schnellen Blick zu nehmen

942
00:44:18,600 --> 00:44:20,114
an, wie Bäume sind relevant für diese.

943
00:44:20,114 --> 00:44:22,530
Angenommen, dass dies einige
dumm Nachricht, die Sie senden wollen,

944
00:44:22,530 --> 00:44:26,342
nur A, B besteht, C D's und E ist,
aber es gibt eine Menge von Redundanz hier.

945
00:44:26,342 --> 00:44:27,550
Es ist nicht dazu gedacht, Englisch.

946
00:44:27,550 --> 00:44:28,341
Es ist nicht verschlüsselt.

947
00:44:28,341 --> 00:44:30,540
Es ist nur eine dumme Nachricht
mit viel Wiederholung.

948
00:44:30,540 --> 00:44:34,010
Also, wenn Sie wirklich zählen alle die
A, B, C-Schema, D und E ist, ist hier,

949
00:44:34,010 --> 00:44:34,890
die Frequenz ist.

950
00:44:34,890 --> 00:44:37,800
20% der Briefe
A, 45% der Briefe

951
00:44:37,800 --> 00:44:39,660
sind E ist, und drei weitere Frequenzen.

952
00:44:39,660 --> 00:44:41,960
Wir zählten dort manuell
und gerade habe die Mathematik.

953
00:44:41,960 --> 00:44:44,579
>> So stellt sich heraus, dass
Huffman, vor einiger Zeit,

954
00:44:44,579 --> 00:44:46,620
erkannte, dass, Sie wissen,
Was, wenn ich mit dem Bau

955
00:44:46,620 --> 00:44:51,172
ein Baum oder Wald von Bäumen, wenn man so will,
wie folgt, was ich tun kann die folgende.

956
00:44:51,172 --> 00:44:53,880
Ich gehe, um einen Knoten zu jedem zu geben
der Briefe, die mich interessiert,

957
00:44:53,880 --> 00:44:55,530
und ich werde speichern
innerhalb dieses Knotens

958
00:44:55,530 --> 00:44:58,610
die Frequenzen als eine Gleitkommazahl
Wert oder Sie es verwenden, könnte ein N, auch,

959
00:44:58,610 --> 00:45:00,210
aber wir werden nur mit einem Schwimmer hier.

960
00:45:00,210 --> 00:45:03,100
Und der Algorithmus,
er vorgeschlagen ist, dass man

961
00:45:03,100 --> 00:45:07,210
nehmen diese Wald von einzelnen Knoten
Bäume, so super kurzen Bäumen,

962
00:45:07,210 --> 00:45:11,920
und Sie können mit sie verbindenden starten
neue Gruppen, neue Eltern, wenn man so will.

963
00:45:11,920 --> 00:45:16,150
Und Sie dies, indem Sie das tun,
zwei kleinsten Frequenzen zu einem Zeitpunkt.

964
00:45:16,150 --> 00:45:18,110
Also nahm ich 10% und 10%.

965
00:45:18,110 --> 00:45:19,090
Ich erstelle einen neuen Knoten.

966
00:45:19,090 --> 00:45:20,910
Und ich fordere den neuen Knoten 20%.

967
00:45:20,910 --> 00:45:22,750
>> Welche zwei Knoten kombiniere ich als nächstes?

968
00:45:22,750 --> 00:45:23,810
Es ist ein wenig zweideutig.

969
00:45:23,810 --> 00:45:26,643
So gibt es einige Sonderfälle zu
zu betrachten, sondern die Dinge recht zu halten,

970
00:45:26,643 --> 00:45:29,300
Ich werde auf 20% zu wählen -
Ich jetzt ignorieren die Kinder.

971
00:45:29,300 --> 00:45:33,640
Ich werde auf 20% zu wählen und
15% und zeichnen Sie zwei neue Kanten.

972
00:45:33,640 --> 00:45:35,624
Und nun, welche zwei Knoten
ich logisch zu kombinieren?

973
00:45:35,624 --> 00:45:38,540
Ignorieren alle Kinder, alle
Enkel, nur an den Wurzeln zu suchen

974
00:45:38,540 --> 00:45:39,070
Jetzt.

975
00:45:39,070 --> 00:45:42,220
Welche zwei Knoten kann ich zusammen zu binden?

976
00:45:42,220 --> 00:45:44,530
Punkt zwei und 0,35.

977
00:45:44,530 --> 00:45:45,890
Also lassen Sie mich zu ziehen zwei neue Kanten.

978
00:45:45,890 --> 00:45:47,570
Und dann habe ich nur noch einer übrig.

979
00:45:47,570 --> 00:45:48,650
Also hier ist ein Baum.

980
00:45:48,650 --> 00:45:51,160
Und es ist ganz bewusst gezogen worden
zu Art hübsch aussehen,

981
00:45:51,160 --> 00:45:55,870
aber feststellen, dass die Kanten
ebenfalls null und eins bezeichnet.

982
00:45:55,870 --> 00:45:59,510
So dass alle von den linken Rändern Null
beliebig, aber konsequent.

983
00:45:59,510 --> 00:46:01,170
Alle rechte Rand sind solche.

984
00:46:01,170 --> 00:46:05,070
>> Und was Hoffman vorgeschlagen,
wenn Sie ein B darstellen wollen,

985
00:46:05,070 --> 00:46:10,080
anstatt für die Zahl 66 als
einer ASCII, die acht gesamten Bits ist,

986
00:46:10,080 --> 00:46:13,360
Sie wissen, was, nur store
das Muster null, null, null,

987
00:46:13,360 --> 00:46:17,030
Null, denn das ist der Weg
von meinem Baum, Mr. Huffman-Baum,

988
00:46:17,030 --> 00:46:18,600
zur Blatt von der Wurzel.

989
00:46:18,600 --> 00:46:20,970
Wenn Sie eine speichern möchten
E hingegen nicht

990
00:46:20,970 --> 00:46:26,290
schickt acht Bits, die eine E. vertreten
Stattdessen schickt welche Muster von Bits?

991
00:46:26,290 --> 00:46:26,890
Ein.

992
00:46:26,890 --> 00:46:30,410
Und was ist schön daran ist,
dass E ist die beliebteste Brief,

993
00:46:30,410 --> 00:46:32,340
und Sie verwenden die
kürzesten Code dafür.

994
00:46:32,340 --> 00:46:34,090
Die nächste beliebtesten
Brief sieht aus wie es

995
00:46:34,090 --> 00:46:37,380
war A. Und so, wie viele Bits
er schlage mit dafür?

996
00:46:37,380 --> 00:46:38,270
Null, eins.

997
00:46:38,270 --> 00:46:41,060
>> Und weil es umgesetzt
wie dieses Baumes, für jetzt

998
00:46:41,060 --> 00:46:43,350
lassen Sie mich vor, es gibt
keine Zweideutigkeit in Morse

999
00:46:43,350 --> 00:46:46,090
Code, da alle
Briefe, die Sie interessieren

1000
00:46:46,090 --> 00:46:48,780
sind am Ende dieser Kanten.

1001
00:46:48,780 --> 00:46:50,580
Also das ist nur ein
Anwendung eines Baumes.

1002
00:46:50,580 --> 00:46:52,538
Dies ist-- und ich werde winken
meine Hand auf diese, wie Sie

1003
00:46:52,538 --> 00:46:55,570
könnte dies als eine C-Struktur zu realisieren.

1004
00:46:55,570 --> 00:46:58,260
Wir müssen nur zu kombinieren
ein Symbol, wie ein char,

1005
00:46:58,260 --> 00:46:59,910
und die Frequenz in links und rechts.

1006
00:46:59,910 --> 00:47:02,510
Aber schauen wir uns zwei
Abschluss Beispiele, die Sie

1007
00:47:02,510 --> 00:47:06,070
zu sehr vertraut mit, nachdem
Quiz Null Problem stellte fünf.

1008
00:47:06,070 --> 00:47:09,210
>> So gibt es die Datenstruktur
als Hash-Tabelle bekannt.

1009
00:47:09,210 --> 00:47:12,247
Und eine Hash-Tabelle ist eine Art
kühlen, dass sie Eimer hat.

1010
00:47:12,247 --> 00:47:14,830
Und angenommen, es gibt vier Eimer
Hier, nur vier Leerstellen.

1011
00:47:14,830 --> 00:47:20,830
Hier ist ein Kartenspiel, und wird hier
verein, spaten, verein, Diamanten, verein,

1012
00:47:20,830 --> 00:47:25,960
Diamanten, Club, Diamanten,
clubs-- so ist dies die zufällig.

1013
00:47:25,960 --> 00:47:30,330
Herzen, also bin ich hearts--
bucketizing alle Eingänge hier.

1014
00:47:30,330 --> 00:47:32,430
Und eine Hash-Tabelle Bedürfnissen
auf Ihre Eingabe suchen,

1015
00:47:32,430 --> 00:47:34,850
und dann legen Sie sie in einem bestimmten
legen auf der Grundlage, was Sie sehen.

1016
00:47:34,850 --> 00:47:35,600
Es ist ein Algorithmus.

1017
00:47:35,600 --> 00:47:37,980
Und ich wurde mit einem Super-
einfache visuelle Algorithmus.

1018
00:47:37,980 --> 00:47:40,030
Der schwierigste Teil davon war
zu erinnern, was die Bilder waren.

1019
00:47:40,030 --> 00:47:41,590
Und dann gibt es insgesamt vier Dinge.

1020
00:47:41,590 --> 00:47:45,440
>> Jetzt wurden die Stapel wächst, die
ist eine bewusste Gestaltung Sache hier.

1021
00:47:45,440 --> 00:47:46,540
Aber was könnte ich machen?

1022
00:47:46,540 --> 00:47:49,080
Also eigentlich hier haben wir eine
Haufen alter Schulprüfung Bücher.

1023
00:47:49,080 --> 00:47:51,240
Nehmen wir an, ein Bündel von
Studenten Namen sind hier.

1024
00:47:51,240 --> 00:47:52,570
Hier ist eine größere Hash-Tabelle.

1025
00:47:52,570 --> 00:47:54,867
Anstelle von vier Schaufeln,
Ich habe, sagen wir, 26.

1026
00:47:54,867 --> 00:47:57,950
Und wir wollten nicht gehen, leihen 26
Dinge von außen [? Annenberg?], So

1027
00:47:57,950 --> 00:48:00,289
hier ist fünf, die darstellen
A bis Z. Und wenn ich

1028
00:48:00,289 --> 00:48:03,580
sehen einen Schüler, deren Name mit A,
Ich werde seine Quiz dort setzen.

1029
00:48:03,580 --> 00:48:08,850
Wenn jemand beginnt mit C, dort drüben,
A-- eigentlich nicht wollte, das zu tun.

1030
00:48:08,850 --> 00:48:10,060
B geht hier.

1031
00:48:10,060 --> 00:48:13,390
Also ich habe A und B und C und
Jetzt hier ist ein weiterer Student.

1032
00:48:13,390 --> 00:48:16,212
Aber wenn das Hash-Tabelle ist
mit einer Anordnung implementiert,

1033
00:48:16,212 --> 00:48:17,920
Ich bin ein bisschen geschraubt
an diesem Punkt, nicht wahr?

1034
00:48:17,920 --> 00:48:19,510
Ich Art müssen diese irgendwo unterbringen.

1035
00:48:19,510 --> 00:48:24,380
>> So eine Art, wie ich dieses Problem zu lösen ist, alle
rechts, ist eine geschäftige, B besetzt ist, C ist besetzt.

1036
00:48:24,380 --> 00:48:28,880
Ich werde ihn in D. Also zumin setzen
zuerst, ich habe zufällig den sofortigen Zugriff

1037
00:48:28,880 --> 00:48:31,064
zu jeder der Schaufeln für die Schüler.

1038
00:48:31,064 --> 00:48:33,230
Aber jetzt ist es ein bisschen übergegangen
in etwas linear,

1039
00:48:33,230 --> 00:48:36,750
weil, wenn ich für jemanden suchen
deren Name mit A, überprüfe ich hier.

1040
00:48:36,750 --> 00:48:38,854
Sollte dies jedoch nicht der A
Student Ich suche nach,

1041
00:48:38,854 --> 00:48:41,520
Ich Art haben zu Beginn überprüfen
die Eimer, weil das, was ich tat,

1042
00:48:41,520 --> 00:48:44,530
war irgendwie linear
Sonde die Datenstruktur.

1043
00:48:44,530 --> 00:48:47,710
Eine dumme Art zu sagen, nur schauen
nach dem ersten verfügbaren Öffnung,

1044
00:48:47,710 --> 00:48:51,850
und als Plan B gesetzt, so zu sprechen,
oder Plan D in diesem Fall wird der Wert

1045
00:48:51,850 --> 00:48:53,340
an diesem Ort statt.

1046
00:48:53,340 --> 00:48:56,470
Dies ist nur so, dass, wenn Sie haben,
erhielt 26 Standorten und Studenten

1047
00:48:56,470 --> 00:49:00,600
mit dem Namen Q oder Z, oder so ähnlich
, dass zumindest Sie den Raum bist.

1048
00:49:00,600 --> 00:49:03,140
>> Aber wir haben schon mehr zu sehen
clevere Lösungen hier, nicht wahr?

1049
00:49:03,140 --> 00:49:04,870
Was würden Sie stattdessen tun
wenn Sie eine Kollision?

1050
00:49:04,870 --> 00:49:06,670
Wenn zwei Menschen
der Name A, was würden

1051
00:49:06,670 --> 00:49:09,160
haben eine intelligentere oder mehr gewesen
intuitive Lösung als nur

1052
00:49:09,160 --> 00:49:12,840
Putting A, wobei D sein soll?

1053
00:49:12,840 --> 00:49:14,810
Warum ich nicht einfach gehen nicht
außerhalb [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
wie malloc, einen anderen Knoten, legte es
hier, und dann, dass ein Student hier setzen.

1055
00:49:19,960 --> 00:49:22,120
So daß ich im Grunde haben
eine Art eines Arrays,

1056
00:49:22,120 --> 00:49:25,590
oder vielleicht mehr elegant wie wir sind
beginnen, eine verknüpfte Liste zu sehen.

1057
00:49:25,590 --> 00:49:29,520
>> Und so eine Hash-Tabelle ist eine Struktur,
das könnte nur so aussehen,

1058
00:49:29,520 --> 00:49:33,900
aber klüger, Sie so etwas wie
getrennte Verkettung, wobei eine Hash-Tabelle

1059
00:49:33,900 --> 00:49:38,340
ganz einfach ist eine Anordnung, wobei jede
deren Elemente keine Zahl ist,

1060
00:49:38,340 --> 00:49:40,470
ist selbst eine verknüpfte Liste.

1061
00:49:40,470 --> 00:49:45,080
So dass Sie super schnell anmelden
entscheiden, wo Sie Ihren Wert für Hash.

1062
00:49:45,080 --> 00:49:48,059
Ähnlich wie mit der Karten Beispiel
Ich habe Super schnelle Entscheidungen.

1063
00:49:48,059 --> 00:49:49,600
Herz geht hier, Diamanten goes here.

1064
00:49:49,600 --> 00:49:52,180
Same here, geht ein hier
D Hier steht, B goes here.

1065
00:49:52,180 --> 00:49:55,740
So super schnelle Look-ups, und wenn
Sie in eine Falle laufen passieren,

1066
00:49:55,740 --> 00:49:59,429
wo hast du Kollisionen, zwei
Personen mit dem gleichen Namen, auch dann

1067
00:49:59,429 --> 00:50:00,970
Sie gerade beginnen sie miteinander zu verbinden.

1068
00:50:00,970 --> 00:50:03,900
Und vielleicht haben Sie halten sie sortiert
alphabetisch, vielleicht auch nicht.

1069
00:50:03,900 --> 00:50:05,900
Aber wenigstens haben wir jetzt die Dynamik.

1070
00:50:05,900 --> 00:50:10,250
Also auf der einen Seite haben wir super schnell
konstante Zeit und Art der linearen Zeit

1071
00:50:10,250 --> 00:50:14,110
Wenn diese verkettete Listen beteiligt
beginnen, ein wenig lang zu erhalten.

1072
00:50:14,110 --> 00:50:16,880
>> Also diese Art von albern,
geeky Witz Jahren.

1073
00:50:16,880 --> 00:50:19,590
Am CS50-Hack-a-thon,
wenn die Schüler in zu überprüfen,

1074
00:50:19,590 --> 00:50:22,040
einige TF oder CA jedes Jahr
denkt, es ist lustig zu setzen,

1075
00:50:22,040 --> 00:50:27,772
ein Zeichen dafür, wie diese, wo es gerade
bedeutet, wenn Ihr Name beginnt mit einem A,

1076
00:50:27,772 --> 00:50:28,870
gehen Sie auf diese Weise.

1077
00:50:28,870 --> 00:50:31,110
Wenn Ihr Name beginnt
mit einem B, gehen this-- OK,

1078
00:50:31,110 --> 00:50:33,290
es ist lustig, vielleicht später im Semester.

1079
00:50:33,290 --> 00:50:36,420
Aber es gibt eine andere
Möglichkeit dies zu tun, zu.

1080
00:50:36,420 --> 00:50:37,410
Komm zurück zu, dass.

1081
00:50:37,410 --> 00:50:38,600
>> Also gibt es diese Struktur.

1082
00:50:38,600 --> 00:50:40,420
Und dies ist unsere letzte
Struktur für heute,

1083
00:50:40,420 --> 00:50:42,400
Das ist so etwas wie ein Trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, die aus irgendeinem Grund kurz
zum Abruf, aber es heißt trie.

1085
00:50:47,140 --> 00:50:51,389
Also ein Trie ist ein weiterer interessanter
Amalgam aus einer Menge von diesen Ideen.

1086
00:50:51,389 --> 00:50:52,930
Es ist ein Baum, der wir zuvor gesehen haben.

1087
00:50:52,930 --> 00:50:54,180
Es ist nicht ein binärer Suchbaum.

1088
00:50:54,180 --> 00:50:58,410
Es ist eine Struktur mit einer beliebigen Anzahl von Kindern,
aber jedes der Kinder in einem Trie

1089
00:50:58,410 --> 00:51:00,090
ein Array ist.

1090
00:51:00,090 --> 00:51:04,790
Ein Array von Größe, sagen, 26 oder vielleicht 27
wenn Sie Namen getrennt unterstützen

1091
00:51:04,790 --> 00:51:06,790
oder Apostrophe in Namen von Personen.

1092
00:51:06,790 --> 00:51:08,280
>> Und dies ist eine Datenstruktur.

1093
00:51:08,280 --> 00:51:10,290
Und wenn Sie von oben sehen
nach unten, wie wenn Sie

1094
00:51:10,290 --> 00:51:13,710
Blick auf die oberen Knoten gibt, M, ist
Hinweis auf die am weitesten links, was es gibt,

1095
00:51:13,710 --> 00:51:17,665
die dann A, X, W, E, L, L. Dies ist
nur eine Datenstruktur, die willkürlich

1096
00:51:17,665 --> 00:51:19,120
speichert die Namen von Personen.

1097
00:51:19,120 --> 00:51:25,720
Und Maxwell durch nur folgende gespeicherte
ein Weg der Array Array Array.

1098
00:51:25,720 --> 00:51:30,050
Aber was ist erstaunlich, zu einem Trie ist
dass, während eine verknüpfte Liste und sogar

1099
00:51:30,050 --> 00:51:34,520
ein Array ist, ist die beste, die wir je bekommen haben
linearen Zeit oder logarithmische Zeit auf der Suche

1100
00:51:34,520 --> 00:51:35,600
jemanden.

1101
00:51:35,600 --> 00:51:40,530
In dieser Datenstruktur einer Trie wenn
meine Daten-Struktur hat einen Namen in es

1102
00:51:40,530 --> 00:51:43,720
und ich bin für Maxwell, ich bin
würde ihn ziemlich schnell zu finden.

1103
00:51:43,720 --> 00:51:47,910
Ich habe gerade für M-A-X-B-E-L-L zu suchen. Wenn
Diese Datenstruktur hingegen

1104
00:51:47,910 --> 00:51:51,830
wenn N eine Million, wenn es ein
Millionen Namen in dieser Datenstruktur,

1105
00:51:51,830 --> 00:51:57,100
Maxwell ist noch im Gange zu sein
erkennbar nach nur M-A-X-B-E-L-L

1106
00:51:57,100 --> 00:51:58,090
Schritte.

1107
00:51:58,090 --> 00:52:01,276
Und David-- D-A-V-I-D Schritte.

1108
00:52:01,276 --> 00:52:03,400
Mit anderen Worten, indem
eine Datenstruktur, ist

1109
00:52:03,400 --> 00:52:07,240
erhielt, von denen alle diese Anordnungen alle
sich selbst zu versorgen mit wahlfreiem Zugriff,

1110
00:52:07,240 --> 00:52:11,090
Ich kann beginnen, bis Volks
Namen über einen Betrag von Zeit, die ist

1111
00:52:11,090 --> 00:52:14,340
proportional zu der Anzahl nicht
der Dinge in der Datenstruktur,

1112
00:52:14,340 --> 00:52:16,330
wie eine Million vorhandenen Namen.

1113
00:52:16,330 --> 00:52:20,135
Die Zeit, die es nimmt mich zu finden
M-A-X-W-E-L-L in dieser Datenstruktur ist

1114
00:52:20,135 --> 00:52:22,260
proportional nicht der
Größe der Datenstruktur,

1115
00:52:22,260 --> 00:52:25,930
sondern auf die Länge des Namens.

1116
00:52:25,930 --> 00:52:28,440
Und realistisch die
Namen wir nachschlagen

1117
00:52:28,440 --> 00:52:29,970
werden nie verrückt lang.

1118
00:52:29,970 --> 00:52:32,600
Vielleicht hat jemand einen 10 Charakter hat
zu nennen, 20 Charakternamen.

1119
00:52:32,600 --> 00:52:33,900
Es ist sicherlich endlichen, nicht wahr?

1120
00:52:33,900 --> 00:52:37,110
Es ist ein Menschen auf der Erde,
hat die längste mögliche Namen,

1121
00:52:37,110 --> 00:52:39,920
aber dieser Name ist eine Konstante
Wertlänge, nicht wahr?

1122
00:52:39,920 --> 00:52:41,980
Es ist nicht in irgendeiner Weise zu variieren.

1123
00:52:41,980 --> 00:52:45,090
Also auf diese Weise, haben wir
erreicht eine Datenstruktur

1124
00:52:45,090 --> 00:52:47,800
dh konstante Zeit Look-up.

1125
00:52:47,800 --> 00:52:50,670
Es dauert eine Reihe von Schritten
abhängig von der Länge der Eingabe,

1126
00:52:50,670 --> 00:52:54,250
aber nicht die Anzahl der Namen
in der Datenstruktur.

1127
00:52:54,250 --> 00:52:58,700
Wenn wir also das Doppelte der Anzahl der Namen
im nächsten Jahr von einer Milliarde auf zwei Milliarden,

1128
00:52:58,700 --> 00:53:03,720
Befund Maxwell dauern wird
genau die gleiche Anzahl von sieben Schritten

1129
00:53:03,720 --> 00:53:04,650
um ihn zu finden.

1130
00:53:04,650 --> 00:53:08,810
Und so scheinen wir erreicht haben
unsere heilige Gral der Laufzeit.

1131
00:53:08,810 --> 00:53:10,860
>> So ein paar schnellen Ankündigungen.

1132
00:53:10,860 --> 00:53:11,850
Quiz Null steht vor der Tür.

1133
00:53:11,850 --> 00:53:14,600
Mehr dazu auf der Website der Kurs
über die nächsten paar Tage.

1134
00:53:14,600 --> 00:53:17,120
Montag lecture-- es ist ein Ferien
hier in Harvard am Montag.

1135
00:53:17,120 --> 00:53:18,850
Es ist nicht in New Haven,
so wir nehmen die Klasse

1136
00:53:18,850 --> 00:53:20,310
nach New Haven zum Vortrag am Montag.

1137
00:53:20,310 --> 00:53:22,550
Alles wird gefilmt werden
und live über wie üblich,

1138
00:53:22,550 --> 00:53:24,900
aber wir beenden heute
mit einem 30-Sekunden-Clip

1139
00:53:24,900 --> 00:53:26,910
namens "Deep Thoughts"
von Daven Farnham, die

1140
00:53:26,910 --> 00:53:30,850
wurde im vergangenen Jahr von Samstag inspiriert
Night Live zu "Deep Thoughts"

1141
00:53:30,850 --> 00:53:35,700
von Jack Handlich, die
sollte nun sinnvoll.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Und jetzt, "Deep
Thoughts "von Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hashtabelle.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> Sprecher 1: Okay, das ist es für jetzt.

1147
00:53:47,660 --> 00:53:48,805
Wir sehen uns nächste Woche.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Um es in Aktion zu sehen.

1150
00:53:56,680 --> 00:53:58,304
Werfen wir also einen Blick auf, dass gerade jetzt.

1151
00:53:58,304 --> 00:53:59,890
Also hier haben wir eine unsortierte Array.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, können Sie voran gehen und neu starten
dies nur eine Sekunde, bitte.

1153
00:54:04,860 --> 00:54:08,562
Alle Rechte, sind Kameras rollen, so
Aktion, wenn Sie bereit, Doug sind, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Okay, so was wir
haben hier eine unsortierte Array.

1155
00:54:11,020 --> 00:54:13,960
Und ich habe alle Elemente farbig
rot, um anzuzeigen, dass es in der Tat,

1156
00:54:13,960 --> 00:54:14,460
unsortiert.

1157
00:54:14,460 --> 00:54:17,960
So erinnern daran, dass das erste, was wir tun,
ist sortieren wir die linke Hälfte des Feldes.

1158
00:54:17,960 --> 00:54:20,630
Dann sortieren wir uns das Recht
Hälfte des Feldes.

1159
00:54:20,630 --> 00:54:22,830
Und ya-da, ya-da, ya-da,
wir sie miteinander verschmelzen.

1160
00:54:22,830 --> 00:54:24,520
Und wir haben eine komplett sortierten Array.

1161
00:54:24,520 --> 00:54:25,360
Also das ist, wie Mergesort funktioniert.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, whoa, whoa,
Schnitt, Schnitt, Schnitt, geschnitten.

1163
00:54:27,109 --> 00:54:30,130
Doug, können Sie nicht nur ya-da, ya-da,
ya-da, Ihren Weg durch merge sort.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: ich gerade tat.

1165
00:54:31,970 --> 00:54:32,832
Es ist in Ordnung.

1166
00:54:32,832 --> 00:54:33,540
Wir sind gut zu gehen.

1167
00:54:33,540 --> 00:54:34,760
Lassen Sie uns einfach weiter ins Rollen.

1168
00:54:34,760 --> 00:54:35,380
Wie auch immer,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Sie haben zu erklären,
es vollständiger als die.

1170
00:54:37,800 --> 00:54:39,999
Das ist einfach nicht genug.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, wir nicht
müssen zurück zu einem gehen.

1172
00:54:41,790 --> 00:54:42,350
Es ist in Ordnung.

1173
00:54:42,350 --> 00:54:45,690
Wie auch immer, wenn wir mit merge-- weiter
Ian, wir sind in der Mitte der Dreharbeiten.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Ich weiß.

1175
00:54:46,612 --> 00:54:49,320
Und wir können nicht einfach ya-da, ya-da,
ya-da, durch den gesamten Prozess.

1176
00:54:49,320 --> 00:54:52,200
Sie müssen erklären, wie die
zwei Seiten zusammengefügt zu werden.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Aber wir haben bereits
erklärte, wie die beiden sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Sie haben gerade gezeigt,
ihnen ein Merge-Array.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Sie kennen den Prozess.

1180
00:54:56,486 --> 00:54:57,172
Es geht ihnen gut.

1181
00:54:57,172 --> 00:54:58,380
Wir haben über sie zehn Mal verschwunden.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Sie übersprungen genau richtig darüber.

1183
00:55:00,330 --> 00:55:03,360
Wir gehen zurück auf eine, die Sie
kannst du nicht ya-da, ya-da über sie.

1184
00:55:03,360 --> 00:55:05,480
Also gut, zurück zu einem.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Ich muss zurück
durch alle Folien?

1186
00:55:07,833 --> 00:55:08,332
Mein Gott.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Es ist wie das sechste Mal, Ian.

1189
00:55:13,004 --> 00:55:13,940
Es ist in Ordnung.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Alles klar.

1191
00:55:15,200 --> 00:55:16,590
Bereit?

1192
00:55:16,590 --> 00:55:17,400
Groß.

1193
00:55:17,400 --> 00:55:18,950
Aktion.